Most public key cryptosystems are mathematically hard and hard on the eyes. If you visit some of the Wikipedia pages for these cryptosystems, your eyes may start to get sore from looking at the intense mathematical equations. In this multipart series of blog posts, I will go over some popular public key cryptosystems and present the hard mathematical problems behind them at an accessible level.
First up is RSA. RSA is named after the designers of the algorithm: Ron Rivest, Adi Shamir and Leonard Adleman. First published in 1977, the trio’s system is still widely in use to this day. RSA consists of three phases: key generation, encryption, and decryption. In the key generation phase, the public and private keys are created. The encryption phase takes in a plaintext message, uses the recipient’s public key, and returns a cipher text. The decryption phase takes in a cipher text, uses the recipient’s private key, and returns a plain text message. Each of these phases revolves around rigorous mathematical problems.
For the purpose of this example, our public key will consist of two values (N and E). Our private key will also consist of two values (N and D). The first step of the key generation phase is to pick two different prime numbers. In our running example, we will choose the values:
P=11 and Q = 17
The next step is to calculate N - which is simply just the product of P*Q.
N = 11*17 = 187
We must then calculate Euler’s totient function (φ) for N. Put more clearly, find the product of (P-1)*(Q-1).
φ(N) = (P − 1)(Q − 1)
φ(N) = (11 − 1)(17 − 1)
φ(N) = 160
To choose E, we must pick an integer such that 1 < E < 160 that is coprime to 160. Meaning to pick E, we must satisfy two conditions. First, E must be greater than one but less than our φ(N) value (160). Secondly, E must also be coprime to 160. In order to be “coprime,” the greatest common divisor (gcd) of φ(N) and E must equal one.
Let’s try 23. It satisfies our first condition as 23 is greater than 1 and also less than 160. Let’s check the second condition. Since 1 is in fact the largest divisor common to 160 and 23, we have satisfied both conditions.
The last value that we need to compute is D. D is the modular multiplicative inverse of E (mod φ(N)). Now I know that may have been a confusing sentence, so let me try to clarify. In order to compute D, we will have to find 23-1 = D (mod 160) which is the same as 23D= 1 mod(160). Simply put, we must find a number (D) that when multiplied by 23 and modulus divided by 160 will have a remainder of 1. The most basic way to determine D is to iterate the value of D from 0 onward until our conditions are satisfied. There are more efficient ways of performing this calculation, see Extended Euclidean algorithm. In our case, 7 will satisfy these conditions.
This function may sound/look intimidating at first, but it is a simple function at heart. Take an integer B and raise it to the Eth power, then modulus divide by n. Back to our example, we will pick a plaintext message of 42 to encrypt. So we have M=42. The output of this step, C, will be our ciphertext. Our encryption function is just like the modular exponentiation example above. It will be in the form.
Any suggestions, questions or corrections, leave a comment below. Also, if you feel that I could have explained something more clearly, don’t hesitate to let me know.
 Kleinjung, et al (2010-02-18). Factorization of a 768-bit RSA modulus