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