Toy-RSA in python

toy_rsa.py

import math

def lcm(a, b):
    return abs(a*b) // math.gcd(a, b)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception(f"modular inverse does not exist for {a} and {m}")
    else:
        return x % m

p, q = 7, 11 # some random primes; normally RSA keys are 1024, 2048, or 4096 bits long
n = p * q
e = 11 # some exponent, can be anything as long as there is an inverse for it
t = lcm(p - 1, q - 1)
d = modinv(e, t) # inverse of the exponent mod n, such that: inverse*exponent = 1 mod n

# private key = d, n 
# public_key = e, n
message = 25
encrypted = message**e % n
decrypted = encrypted**d % n

# prints message: 25; encrypted: 58; decrypted: 25
print(f"message: {message}; encrypted: {encrypted}; decrypted: {decrypted}") 
assert message == decrypted