#RSA
#select P and Q
#n = P*Q,m=(P-1)*(Q-1)
#select public key e, gcd(e,m)=1
#select private key d, (d*e) mod m
#encryption c=(p**e)mod n
#decryption p= (c**d)mod n
import random
import math
def is_prime(n):
if n < 2:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
#step 1: P,Q
def generate_prime():
while True:
random_no1 = random.randint(100, 1000)
if is_prime(random_no1):
break
while True:
random_no2 = random.randint(100, 1000)
if is_prime(random_no2) and random_no2 != random_no1:
break
return random_no1, random_no2
#step 2:n,m
def n_m(P,Q):
n = P*Q
m = (P-1)*(Q-1)
return n,m
def gcd(a, b):
while b:
a, b = b, a % b
return a
# Function to find modular inverse
def mod_inverse(e, m):
m0, x0, x1 = m, 0, 1
while e > 1:
q = e // m
m, e = e % m, m
x0, x1 = x1 - q * x0, x0
return x1 + m0 if x1 < 0 else x1
P, Q = generate_prime()
print("P:", P)
print("Q:", Q)
n,m = n_m(P,Q)
print("n:", n)
print("m:", m)
# Step 3: Choose Public Key e (such that gcd(e, m) = 1)
while True:
e = random.randint(2, m - 1)
if gcd(e, m) == 1:
break
print("Public Key (e):", e)
# Step 4: Compute Private Key d (modular inverse of e mod m)
d = mod_inverse(e, m)
print("Private Key (d):", d)
# Step 5: Encryption
def encrypt(plaintext, e, n):
ciphertext = pow(plaintext, e, n)
return ciphertext
# Step 6: Decryption
def decrypt(ciphertext, d, n):
plaintext = pow(ciphertext, d, n)
return plaintext
# Example message (must be less than n)
plaintext = random.randint(2, n - 1)
print("Original Message (Plaintext):", plaintext)
# Encrypt the plaintext
ciphertext = encrypt(plaintext, e, n)
print("Encrypted Message (Ciphertext):", ciphertext)
# Decrypt the ciphertext
decrypted_text = decrypt(ciphertext, d, n)
print("Decrypted Message:", decrypted_text)
# Check if decryption is successful
assert decrypted_text == plaintext, "Decryption failed!"
print("Decryption Successful!")
