Python implementation of the RSA Encryption Algorithm.
Quick reference
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[0] 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]
Encryption
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[0]) % public_key[1] for i in M]
>>> CT = encrypt(M, public_key) # [121, 5, 77, 77, 108, 13, 160, 209, 108, 162, 77, 130, 310]
Decryption
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[0]) % private_key[1]) 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!
Algorithm requirements
- 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
Resources:
- 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)