In a previous post, I introduced the RSA algorithm and outlined its importance. Here, I will present a naive Python implementation. Later, I will highlight its shortcomings and address the flaws.

The code can be found here: https://github.com/o-lenczyk/rsa

Lets explain two helper functions:

def gcd(candidate_exponent, totient_phi):
    while totient_phi != 0:
        candidate_exponent, totient_phi = totient_phi, candidate_exponent % totient_phi
    return candidate_exponent

This function computes greatest common divisor. Example:

If you call gcd(14, 8), the steps are:

• (14, 8) → (8, 14 % 8 = 6)
• (8, 6) → (6, 8 % 6 = 2)
• (6, 2) → (2, 6 % 2 = 0)
• (2, 0) → returns 2

So, the GCD of 14 and 8 is 2.

def mod_inverse(encryption_exponent_e, totient_phi):
    m0, x0, x1 = totient_phi, 0, 1
    if totient_phi == 1:
        return 0
    while encryption_exponent_e > 1:
        q = encryption_exponent_e // totient_phi
        totient_phi, encryption_exponent_e = encryption_exponent_e % totient_phi, totient_phi
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += m0
    return x1

This function finds a number that, when multiplied by encryption_exponent_e and divided by totient_phi, leaves a remainder of 1. This is needed in RSA to calculate the private key.

• Save the original value of totient_phi (call it m0).
• Set up two numbers, x0 and x1, to help keep track of the calculation.
• If totient_phi is 1, return 0 (no inverse exists).
• Repeat these steps while encryption_exponent_e is greater than 1:
  • Divide encryption_exponent_e by totient_phi and get the whole number part (call it q).
  • Update encryption_exponent_e and totient_phi to the next pair of numbers in the process (like in the Euclidean algorithm).
  • Update x0 and x1 to keep track of the calculation.
• If the answer (x1) is negative, add m0 to make it positive.
• Return x1 — this is the modular inverse.

def generate_keypair(p, q):
    if p == q:
        raise ValueError('p and q cannot be equal.')
    
    n = p * q
    phi = (p-1) * (q-1)
    
    # Choose an integer e such that e and phi(n) are coprime
    e = random.randrange(1, phi)
    
    # Use Euclid's Algorithm to verify that e and phi(n) are coprime
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)
        
    # Use Extended Euclidean Algorithm to generate the private key
    d = mod_inverse(e, phi)
    
    # Return public and private keypair
    # Public key is (e, n) and private key is (d, n)
    return ((e, n), (d, n))

By having two above functions already, generating keypair is fairly straightforward

Last two functions are encrypt and decrypt

def encrypt(public_key, plaintext):
    e, n = public_key
    cipher = [pow(ord(char), e, n) for char in plaintext]
    return cipher

What is happening here:

• ord(char) converts a character (like 'A') into its ASCII numeric value (e.g., 65)
• pow(ord(char), e, n) computes (m ^ e) mod n – RSA encryption formula
• [ … for char in plaintext] does this for every character in the plaintext, producing a list of encrypted numbers

def decrypt(private_key, ciphertext):
    d, n = private_key
    plain = [chr(pow(char, d, n)) for char in ciphertext]
    return ''.join(plain)

Last but not least:

• for each number, compute (char ^ e) mod n – the RSA decryption formula
• chr(…) – Converts the resulting number back to a character using its ASCII code
• return ”.join(plain) – Joins the list of characters into a single string

Rest is the matter of generating key pair, and using encrypt and decrypt function.