Purfe

Learn, create and have fun with Python

# RSA algorithm in Python

Python implementation of the RSA Encryption Algorithm.

Quick reference

## Generating the keys

1. 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``````
2. Find n – the product of these numbers. This number n becomes modulus in both keys.

`` n = p * q ``
3. 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)``
4. 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)]    ``````
5. 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) % public_key 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) % 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!

``````

### 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: