# RSA operation

Key generation

p # prime number
q # prime number
n # modulus
n = p * q

totien(n) = (p - 1) * (q - 1)

e # public key exponent
1 < e < totien(n) and gcd(e, n) = 1

d # private key exponent

# Method 1
d =  gmpy.invert(e, totien(n))

# Method 2
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:
  return None  # modular inverse does not exist
 else:
  return x % m

d = modinv(e, totien(n))

# Method 3
d = 1
while True:
 if (e * d - 1) % totien_n == 0:
  print d
  break
 else:
  d += 1

(e, n) # public key
(d, n) # private key

Example

p = 61
q = 53
n = 53 * 61 = 3233
totien(3233) = (53 - 1) * (61 - 1) = 3120
e = 17
d = modinv(e, totien(3233)) = 2753

(17, 3233) # public key
(2753, 3233) # private key

m = 65 # message
c # ciphertext

Encryption

c = m**e % n = pow(m, e, n)
c = 65**17 % 3233 = pow(65, 17, 3233) = 2790

Decryption

m = c**d % n = pow(c, d, n)
m = 2790**2753 % 3233 = pow (2790, 2753, 3233) = 65

# CRT (to speed up calculation)
dp = d % (p - 1) = 2753 % (61 - 1) = 53
dq = d % (q - 1) = 2753 % (53 - 1) = 49
qinv = modinv(q, p) = modinv(53, 61) = 38
m1 = c**dp % p = 2790**53 % 61 = 4
m2 = c**dq % q = 2790**49 % 53 = 12
h = (qinv * (m1 - m2)) % p = (38 * (4 - 12)) % 61 = 1
m = m2 + (h * q) = 12 + (1 * 53)= 65

References

https://en.wikipedia.org/wiki/RSA_(cryptosystem)
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
https://factordb.com