Despite the blog’s title, this post is not about bitcoin. However, it is about what makes (most) bitcoin and other cyber transactions safe from the prying eyes of hackers. The “magic” referred to in the title is almost literal. I’m going to talk about how seemingly useless, abstract mathematics now form the backbone of most of the world’s cybersecurity systems, from banking to online retail transactions to national security. The algorithm I’m going to talk about has the flavor of a magician’s card tricks. After a certain number of times of shuffles, it looks as though the card order is completely random. But the magician knows that a few more shuffles will bring the pack back to what it started. You should keep this shuffling analogy in mind as we get into today’s discussion. I’ve divided the posts into 2 parts. Part 1 (today) will introduce the first and still the most widely cryptographic algorithm, one that is based on the “magical” properties of prime numbers. Part 2 will dive into something even more magical, a strange type of curve known as elliptic curves and their relevance for the practical world of cryptography.

Let’s get going!

The seminal moment in cryptography was in 1977. That was the year when the RSA algorithm and the Diffie-Hellman key exchange algorithm were introduced. These algorithms were revolutionary because they represented the first viable cryptographic solutions where security was grounded in the pristine world of abstract mathematics, specifically prime number factorization. They ensured that communication between two parties such as a bank and its customer doing online transactions was secure without worrying about an unauthorized party listening in on the key exchange.

RSA is the most widely used of these systems. It is named after the three scientists who discovered it: Ron Rivest, Adi Shamir and Leonard Adelman. They worked on the basic idea that two keys must be used to obtain a high level of security. First, a public key to encrypt the customer’s data, and which can be made public and a private key to decrypt the data.  Such systems are known as public key cryptographic systems.

Easy to Perform, Difficult to Undo

What is needed is for a public key cryptographic system to work is a set of algorithms that is easy to process in one direction but difficult to undo. For RSA, the easy part is multiplying two prime numbers, and the difficult part is to unscramble the product into their components or prime factors. For example, it is easy to see that 2 x 2 x 3 x 19 is 228, but doing the reverse isn’t as straightforward. And it gets much harder with as prime factors become very large.

A Simple Example

Suppose Alice wishes to send Bob a valuable diamond, but the jewel will be stolen if sent unsecured. Both Alice and Bob have a variety of padlocks, but they don’t own the same ones (i.e., their keys cannot open the other’s locks). How did Alice send the diamond to Bob?

This graphic shows the key idea (pun intended) behind the RSA algorithm:

As you can see, the solution is as follows:

1. Bob first sends Alice an unlocked padlock.
2. Alice uses Bob’s padlock and sends the package to Bob
3. Bob removes his lock and opens the package.

This example demonstrates the ideas behind public-key cryptography. Alice encrypts her message using Bob’s public key, which can only be decoded by Bob’s private key.

In practice, the concept is somewhat different. In the case of the RSA cryptosystem, the public key is generated by multiplying two large prime numbers p and q together (the easy part) while the private key is generated through a more complicated mathematical process involving p and q as detailed below.

RSA: The Mathematical Foundations

The implementation of RSA draw upon modular arithmetic and Euler’s Theorem. Euler’s theorem is in turn a generalization of Gauss’s abstract clock calculator based on modular arithmetic and Fermat’s little theorem dealing with powers of integers modulo positive integers.

Euler’s theorem states the following:

Let n be a positive integer, and let a be an integer that is relatively prime to n. Then

aϕ(n)≡1 (mod n),

where is Euler’s totient function, which counts the number of positive integers ≤n which are relatively prime to n.

For example, suppose a is relatively prime to 10. Since ϕ(10)=4, Euler’s theorem says that  , i.e. the units digit of  is always 1. 

Implementing RSA

Here’s how Euler’s theorem comes to life in the RSA algorithm. Note that each step of the algorithm only involves multiplication, which is easy for a computer to perform:

1. First, the receiver (say a bank) chooses two large prime numbers p and q. Their product, n=pq, will be half of the public key.
2. For the other half of the public key, the receiver calculates ϕ(pq)=(p−1)(q−1) and chooses a number e relatively prime to  ϕ(pq). In practice, e is often chosen to have five digits though it can be as small as two digits like 33. e will be the other half of the public key.
3. The receiver calculates the modular inverse d of e modulo ϕ(n). In other words, de≡1(mod ϕ(n)). d is the private key.
4. The receiver distributes both parts of the public key: n and e. d is kept secret.

Because d is linked to ϕ(pq)=(p−1)(q−1), which involves the prime factors of a potentially very large prime product, the RSA system is virtually impregnable.

In Summary

The RSA algorithm is a marvelous demonstration of the “unreasonable effectiveness of pure mathematics”. Few people care about prime numbers such as 2, 3, 5, 7, 11, 13 etc. But thanks to the insights of three brilliant mathematicians who lived between the 17^th and 19^th centuries: Leonhard Euler, Pierre de Fermat and Carl Friedrich Gauss, seemingly “useless” prime numbers became the cornerstone one of the most high-profile applications of abstract mathematics of our time.

Coming up next: The strange world of elliptic curves cryptography.

Reference

This post, including the graphic above post draws heavily on the following source: https://brilliant.org/wiki/rsa-encryption/ which provides more details of the RSA algorithm.