RSA algorithm in Python

Python implementation of the RSA Encryption Algorithm.

Quick reference

1. Generating the keys
2. Encrypting
3. Decrypting
4. Algorithm requirements

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[0]
       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 = M^e 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 = C^d 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: M^ed mod n = M < n
• it must be relatively simple to calculate M^e mod n and C^d 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)

---