RSA and Python

Summary

Understanding RSAInfoTo keep this guide sweet and simple we restrain ourself to using small primes.(We also won’t use padding schemes or other security measures)Should you use RSA in production always make sure to use numbers which are at least 512 Bit / 64 Byte long.RSA is an asymmetric cryptographic method consisting of a public key for encryption and a private key for decyption.This means that the ascii value of a letter, for example, is converted into a cipher using the public key and converted back into plaintext using the private key.RSA provides security if the public key and the private key are sufficiently long (min. 64bytes). This is the case because it is theoretically possible to calculate the private key from the public key with immense effort for small prime numbers.Private and Public keyChoose NumbersThe first step of key generation consists of choosing p and q such that:$$ \begin{align} p \not= q \end{align} $$and that both numbers are prime.Here, for example, we can choose p and q as follows:$$ \begin{align} p = 61 \\\ q = 97 \end{align} $$PYTHONCalculating the product of p and qNow n has to be determined from the multiplication of the two previously selected numbers:$$ \begin{align} n &= p \cdot q \\\ &= 61 \cdot 97 \\\ n &= \underline{5917} \end{align} $$PYTHON1p = 61 2q = 97 3print(f"n={p*q}") 4# n=5917Calculating phi of n and eAfter we have chosen p and q and calculated n, now follows the calculation of a number by calculating phi of n:$$ \begin{align} \phi(n) &= (p-1) \cdot (q-1) \\\ &= (61-1) \cdot (97-1) \\\ &= (60) \cdot (96) \\\ \phi(n) &= \underline{5760} \\\ \end{align} $$PYTHON 1p = 61 2q = 97 3 4print(f"n={p*q}") 5# n=5917 6 7phi = (p-1)*(q-1) 8 9print(f"phi={phi}") 10# phi=5760is relatively prime, i.e. the following applies:$$ \begin{align} \gcd(e, \phi(n)) &= 1 \\\ \gcd(e, 5760) &= 1 \\\ \gcd(\underline{47}, 5760) &= 1 \end{align} $$Our goal is to choose a small but not too small odd number for e, therefore i use the 47 for e.PYTHON 1...