This post is about the slowest and worst-ish implementation of RSA, RSA is an important public key encryption algorithm. From wiki:

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym “RSA” comes from the surnames of Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977

The math behind RSA requires more mental calories than i can afford on Saturday morning. Anyway, The algorithm is simple (simple-ish). These are steps to calculate integer public and private keys

Example image

For public key, I am using naive shot in the dark to generate random e and check if gcd(e,phi) == 1.

17         self.e = random.randrange(1, self.phi)
18         res = math.gcd(self.e, self.phi)
19         while res != 1:
20             self.e = random.randrange(1, self.phi)
21             res = math.gcd(self.e , self.phi)

For private key, We need to calculate d where e.d = 1 mod n. apparently d can be calculated with Extended Euclidean algorithm but i am too lazy to write it. So, After little googling I found that it’s the same as “Modular multiplicative inverse”

"y = invmod(x, p) such that x*y == 1 ( mod p)"

And that can be done with pow()

8     return pow(e, -1, phi)

  4 import math
  5 import random
  6
  7 def calc_private(e, phi):
  8     return pow(e, -1, phi)
  9
 10 class RSA():
 11     def __init__(self, a ,b):
 12         self.a, self.b = (a,b)
 13         self.n = self.a * self.b
 14         self.phi = (self.a - 1) * (self.b - 1)
 15
 16         # public key
 17         self.e = random.randrange(1, self.phi)
 18         res = math.gcd(self.e, self.phi)
 19         while res != 1:
 20             self.e = random.randrange(1, self.phi)
 21             res = math.gcd(self.e, self.phi)
 22
 23         # private key
 24         self.d = calc_private(self.e, self.phi)
 25
 26         print(f"n:{self.n} phi:{self.phi} public key:{self.e} private key:{self.d}")
 27
 28     def encrypt(self, text):
 29         cipher = (text ** self.e) % self.n
 30         return cipher
 31
 32     def decrypt(self, text):
 33         cipher = (text ** self.d) % self.n
 34         return cipher
 35
 36
 37 rsa = RSA(11,17)
 38
 39 i = 5
 40 y  = rsa.encrypt(i)
 41 z = rsa.decrypt(y)
 42 print(f"text:{i} encrypted:{y} decrepted:{z}")
 43