Tales from the Cryptography: The Terrifying Math Explained - Part 1

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.

Key Generation

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=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.

E = 23

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.

D*23 (mod 160) = 1
7 * 23 = 161
161 mod 160 = 1
D = 7

As a quick overview, we now have our public key (N and E) and our private key (N and D).

Encryption

We have just completed the key generation phase. Now, we have all the components needed to encrypt and decrypt a message. The encryption and decryption used in RSA are performed by using modular exponentiations. A modular exponentiations takes the form below:

C = b^e (mod n)

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 E^th 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.

C = M^E (mod n)
We just need to substitute our values from the running example. This will give us.
C = 42²³ (mod 187)
C=168

Decryption

Now, if we want to decrypt this message, we will do another modular exponentiation in the form:

M = C^D (mod n)
Again, we just substitute our values. This will give us:
M = 168⁷ (mod 187)
M= 42

And just like that we have our original message back. Pretty cool, right?

Closing Remarks

As I mentioned before, public key cryptosystems are centered around mathematically hard problems to provide security. The mathematically hard problem that RSA revolves around is large integer factorization. In RSA, the large integer is the public key N. It is very difficult to find the factors that multiply together to get the large integer unless you know the recipient’s private key. It is very important to note that in practice these numbers are much larger than in our example. It is very typical for key sizes to range from 1,024 to 4,096 bits in length, making for much larger calculations than our example. To show how hard this integer factorization problem is, the best known cryptanalysis of RSA occurred in 2009 when several researchers “factored a 232-digit number (768 bit length), utilizing hundreds of machines over a span of 2 years” [1]

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.

Works Cited [1] Kleinjung, et al (2010-02-18). Factorization of a 768-bit RSA modulus