The spat about WhatsApp’s new user agreement has prompted another flurry of discussion of online security. We often see messages stating “this conversation is encrypted” – but how exactly does modern day encryption work, and how safe are we?

If you’ve been to an escape room, you’ve probably encountered a cipher or two – scrambled messages that you have to solve in order to escape. The best known of encryption methods is probably the Caesar cipher, dating back to the Romans, which shifts all the letters by a certain number of positions in the alphabetical order. Unfortunately, this is also the easiest cipher to break, because of something called frequency analysis. In English, certain characters occur most frequently; for example, at this point in the article (*), the letter “e” has appeared 81 times, more than any other letter. One can look at a Caesar cipher text and see which letter appears the most; it is then not very difficult to figure out the amount of shifting involved.

Thus began the evolution of ciphers; instead of shifting by one letter, people tried shifting with a so-called code word, then by sentences, using the so-called Vigenère cipher. This culminated in the famous Enigma, which basically amounts to a series of rather clever shifts, but that was also famously cracked during the Second World War by Alan Turing at Bletchley Park. When that happened, people realized that a new way of encryption was needed.

Enter RSA. Named after its inventors (footnote 1), Rivest, Shamir and Adleman, RSA is the main method of encryption in the modern day, but is fundamentally different from the ciphers I mentioned above. The difference lies in the types of keys used; while the Caesar cipher and Enigma both use symmetric keys, RSA is an example of asymmetric, or public key cryptography. In symmetric cryptography the key used to encrypt the message and decrypt the received message is the same; however, RSA makes use of two different keys, the public and private keys ­–­ the key locking up the box is not the same key used to unlock it! It all seems rather unintuitive at first, but the encryption actually relies on only two concepts – prime numbers and modular arithmetic.

Prime numbers are numbers greater than one that can only be divided by one and itself; they have been the subject of a previous article in Science Focus (Issue 020), and are very interesting in their own right. Primes can also get arbitrarily large – currently the largest known prime that we can actually write down has 24,862,048 digits. RSA encryption relies on the fact that factoring large numbers is generally very slow, even for people with enormous computing power, so breaking the code requires a huge amount of computing power that is simply not worth it (footnote 2).

Another technique is what mathematicians call modular arithmetic, which is, essentially, a generalization of telling the time. In 24-hour time system, we would tell the time modulo 24 – three hours after 23:00 is always 02:00 and never 26:00 (footnote 3). This is actually just division in disguise: to get the value of n mod a, just divide n by a enough times until you reach some value that is smaller than a – the remainder of our division is exactly the value we require.

With these two concepts in mind, the RSA algorithm is not too complicated – we’ll break down the steps in some detail here [1].

To demonstrate, we pick two prime numbers, say p = 11 and q = 13. Multiply them together to get the public key n = 143. (In reality these primes are huge – the current recommendation is 2048 bits (footnote 4), but for the sanity of our editor, we’ll keep them relatively small!) We also choose another number e which has no common factors, i.e. coprime, with 10 (i.e. p – 1) and 12 (i.e. q – 1); here we choose e = 7. The choice of n is unique for everyone, and e and n are known as the “public key”. They are published in a public directory that computers can use when their owners want to send messages to each other.

Say Cliff wants to send me a very simple message – the most simple one possible – “Hi”. As expected, if you want a computer to work, you have to turn letters into numbers. Thankfully, a system already exists – American Standard Code for Information Interchange (ASCII), which turns letters and symbols into 7-bit numbers, works just fine. In ASCII “H” is represented by the number 72, and “i” by the number 105.

To encrypt the letter “H”, Cliff now has to find my public key. He reads from the directory that n = 143 and e = 7. The encrypted text is given by c = T^e (mod n). Here our text T₁ = 72, so the encrypted text is c₁ = 72^7 (mod 143), a very intimidating expression that seems impossible to compute by hand. But we can enlist the help of computers – and a quick Google reveals that c₁ = 19 (mod 143). So the first number we need to send is 19. We repeat the above procedure for the letter “i”: c₂ = 105^7 (mod 143), so the second number is c₂ = 118 (mod 143). So the message “Hi” becomes “19 118”.

To the outsider, it is impossible to recover the original message, since you cannot reverse your way from a modular number; however, you have one extra edge – the values of p and q – that sets you apart. Without them, you would need to factorize n, which is extremely time consuming since n is very large. The key to decryption is calculated from the following formula: take the least common multiple of p – 1 and q – 1, lcm (10, 12) = 60. The decryption key d is given by the following equation: 1 = (e x d) mod (lcm (p – 1, q – 1)). In our case, 1 = (7 x d) mod 60; so d = 43. This is our magical number to get back the message. And finally the decrypted message, m, is given by m = c^d (mod n). We have received two letters, so we will decrypt them separately: The first letter is 19^43 (mod 143), which gives us 72 (mod 143), the letter “H”; similarly, the letter “i” comes from 118^43 (mod 143) = 105 (mod 143). These look like calculations involving awfully large numbers, but computers can do them extremely easily. Also, with d, you can now decrypt every single message that Cliff sends you afterwards (footnote 5).

The encryption works because of a theorem known as Fermat’s Little Theorem – although by the same person, it is not the infamous Fermat’s Last Theorem. The theorem looks rather innocent at first sight: a^p ≡ a (mod p) for any prime p (footnote 6) – but is in fact key (pardon the pun) to why the encryption works, since the exponential features multiple times. The proof requires a bit of machinery that can be easily found on Wikipedia, and we will skip that for now.

Currently the RSA cryptosystem is seen as the default choice for encrypting small amounts of data, such as keys to symmetric key cryptography (footnote 7). The largest known factorized n is 250 digits long (829 bits), which took 2700 core years (footnote 8), and was factorized in 2019 [2]. The usual length used for encryption, in contrast, is 2048 bits, so we are still safe for the time being. However, history tells us that the codebreakers will always catch up – and we will need to find a new encryption method in the future.

 1 Actually, the first inventor of the RSA was Clifford Cocks, an English mathematician, who described the algorithm four years ahead (1973) of Rivest, Shamir and Adleman (1977); sadly, he worked for the British Intelligence Agency, and his work wasn’t released until more than 20 years later in 1997, so RSA got all the credit.

2 That, however, may change with quantum computing, but at the moment quantum computers are not fast enough to hack RSA yet. If you’re interested, try Googling “Shor’s Algorithm”.

3 There is a slight catch, however; in 12-hour time system, when telling the time we say 12 o’clock when the clock strikes twelve, but in modular arithmetic we say 12 ≡ 0 (mod 12) instead.

4 Bit is short for “binary (base 2) digit”– so a 7 bit number ranges from 1 to 2⁷ – 1 = 127, and 2048 bits range from 1 to 2²⁰⁴⁸ – 1, around 617 digits.

5 The equation always has a unique solution d because we assumed that e is coprime with 10 and 12 from the beginning.

6 This equation is in modular arithmatic, not the algebra that most of us are familiar with. It actually means a^p (mod p) ≡ a (mod p).

7 RSA is the key (pun intended) component of the larger cryptographic protocol called TLS (Transport Layer Security), used for many online transactions and communication.

8 The term “core year” refers to the equivalent of using one CPU core continuously for a year (365 days). The author uses Intel Xeon Gold 6130 CPUs as a reference [2].

References:

[1] Singh, S. (2003). The Code Book: The Secrets Behind Codebreaking. New York, NY: Delacorte Press.

[2] Zimmermann, P. (2020, February 28). Factorization of RSA-250. Retrieved from https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html