Though we have studied RSA algorithm in college, it was just for the sake of theory examination. I never had thought about its practical implementation and how it is successfully existing over these many years. Here is an attempt to implement RSA encryption/decryption using python:
Generate 2 distinct random prime numbers
p = generate_prime() while True: q = generate_prime() if q != p: break
# generate random prime function def generate_prime(): x = randint(100, 9999) while True: if is_prime(x): break else: x += 1 return x # primality check function def is_prime(x): i = 2 root = math.ceil(math.sqrt(x)) while i <= root: if x % i == 0: return False i += 1 return True
n = pq. n is used as the modulus for both the public and private keys. Its length is the key length.
n = p * q
φ(n) = φ(p)φ(q) = (p − 1)(q − 1) where φ is Euler’s totient function.
n1 = (p - 1) * (q - 1)
Choose an integer e such that
1 < e < φ(n) and
gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime. e is released as the public key exponent.
r = randint(2,100) # For efficiency 2 < e < 100 while True: if gcd(r, n1) == 1: break else: r += 1 e = r
# function to find gcd def gcd(a, b): while b: a, b = b, a%b return a
Determine d as
d ≡ e−1 (mod φ(n)); i.e., d is the multiplicative inverse of
e (modulo φ(n)).
d = modinv(e, n1)
modinv is calculated using Extended Euclidean Algorithm.
# function to find modular inverse def modinv(a,m): g,x,y = egcd(a,m) if g != 1: return None else: return x%m # function to find extended gcd def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y)
Step 6: Encryption
If ’m' is the message to be transmitted, it is encrypted as
c ≡ m^e * (mod n) and c is send over network.
c = (m**e) % n
Step 7: Decryption
Upon recieving the encrypted message c, it is descrypted as
m ≡ c^d * (mod n) to retrieve original message m.
m = (c**d) % n
With my Macbook Pro of 4GB & Ci5 2.4GHz, to run this decryption function successfully,
- The random primes generated
qare kept below 10000.
- Message to be encrypted
m, which is entered via console, should be <= 4 digits.
As the size of the
q increases, the value of
d increases rapidly. Since the decryption function takes
d as exponent, decryption becomes very time consuming process with my machine.
Here is the complete python program: