Python implementation of the RSA Encryption Algorithm.
Generating the keys
Choose two prime numbers (p, q), such as p is not equal to q.
# TODO implement prime number generator # For now, we assign two primes to p and q p = 11 q = 29
Find n – the product of these numbers. This number n becomes modulus in both keys.
n = p * q
Calculate ϕ(n) function (Euler’s totient), that is, how many coprime with n are in range (1, n). To put it simply, how many numbers in that range do not share common factors with n. The formula for this is
phi_of_n = (p - 1) * (q - 1)
- Choose encryption key e, such that:
- 1 < e < ϕ(n)
- e must be coprime with N and ϕ(n). In other words, the greatest common divisor for (e, n) and for (e, ϕ(n)) should be 1.
import random def get_gcd(x, y): while(y): x, y = y, x % y return x def get_encryption_key(n, phi_of_n): lst = [i for i in range(1, N+1)] e_list =  for i in lst: if (1 < i) and (i < phi_of_n): gcd = get_gcd(i, n) gcd_phi = get_gcd(i, phi_of_n) if (gcd == 1) and (gcd_phi == 1): e_list.append(i) if len(e_list) == 1: return e_list else: return e_list[random.randint(1, len(e_list)-1)]
Choose decryption key d, such that
d*e(mod ϕ(n)) = 1. In the example below, we expand the range for d by multiplying e by 25 (this is an arbitrary number).
def get_decryption_key(e, phi_of_n): d_list =  for i in range(e * 25): if (e * i) % phi_of_n == 1: d_list.append(i) return d_list[random.randint(1, len(d_list) - 1)]
The procedure to create encryption keys
p = 11 q = 29 n = get_N(p, q) # 319 phi_func = phi_of_n(p, q) # 280 e = get_encryption_key(n, phi_func) d = get_decryption_key(e, phi_func) # to avoid key collision while d == e: d = get_decryption_key(e, phi_func) public_key = [e, n] # [137, 319] private_key = [d, n] # [1633, 319]
Plaintext must be less than n. M < n
As the encryption function works on numbers, first, we need to translate letters into digits.
I won’t be creative and choose “Hello, world!” as my message.
import string def text_to_digits(PT): pool = string.ascii_letters + string.punctuation + " " M =  for i in PT: M.append(pool.index(i)) return M >>> PT = "Hello, world!" >>> M = text_to_digits(PT) # [33, 4, 11, 11, 14, 63, 84, 22, 14, 17, 11, 3, 52]
To encrypt a message (M) to ciphertext (CT), we take every digit in M, raise it to the power of e and take the modulus of n. CT = Me mod n
def encrypt(M, public_key): return [(i ** public_key) % public_key for i in M] >>> CT = encrypt(M, public_key) # [121, 5, 77, 77, 108, 13, 160, 209, 108, 162, 77, 130, 310]
To decrypt the ciphertext, we raise every number to the power of d and take the modulus of n. Decrypted text, DT = Cd mod n
def decrypt(CT, private_key): return [((i ** private_key) % private_key) for i in CT] >>> DT = decrypt(CT, private_key) # [33, 4, 11, 11, 14, 63, 84, 22, 14, 17, 11, 3, 52]
Finally, to make the message readable, let’s transform numbers back to letters.
def digits_to_text(DT): pool = string.ascii_letters + string.punctuation + " " msg = '' for i in DT: msg += pool[i] return msg >>> original_PT = digits_to_text(DT) # Hello, world!
- it must be possible to find values of e, d, n such that: Med mod n = M < n
- it must be relatively simple to calculate Me mod n and Cd mod n for all values of M < n
- both sender and receiver must know the value of n
- the sender knows the value of e, and the only receiver knows the value of d
- plaintext must be M < n
- Encryption and HUGE numbers – Numberphile
- Rivest, Shamir, Adleman – The RSA Algorithm Explained
- RSA-129 – Numberphile.Featuring Ron Rivest, co-inventor of RSA
- RSA (step-by-step)
- The RSA Encryption Algorithm (1 of 2: Computing an Example)
- The RSA Encryption Algorithm (2 of 2: Generating the Keys)