Encryption is an important tool for protecting information. One of the major breakthroughs in this area is public- and private-key cryptography, which enables people who have never contacted each other before to exchange encrypted information. The RSA encryption algorithm, one of the most common today, uses basic tools from number theory to pass information securely in this way. A large part of our everyday activity, such as online shopping, relies on this algorithm.
Advertisement
When we shop online, we send the merchant our credit-card details. The information passes through many servers. So, who guarantees that malicious actors will not steal our credit-card data, read our e-mail, or peek at our private conversations?
The solution is called encryption: Altering a message before sending it so that a third party sees only meaningless text, while the recipient can decipher it. Encryption is an ancient idea; it is claimed that Julius Caesar used a (simple) encryption method [1]. However, the kind of encryption used on the Internet was invented only in the 1970s: Public-key encryption, and the best-known method of this type is RSA [2], named after its inventors—Ronald Rivest, the Israeli Adi Shamir, and Leonard Adleman.
In “classical” encryption methods, data is encrypted and decrypted using secret information known to both the encrypter and the decrypter, called a “key”, e.g., a shared password or a large number. The difficulty with this approach is that the two parties must first agree on the password securely. Yet, when we buy something from a random online store, we have never agreed with it on a password beforehand. So, how can we send it encrypted information?
In the public-key method, the store prepares two keys in advance: a public key and a private key. It publishes the public key and keeps the private key secret. To encrypt, one needs to know only the public key, but to decrypt one must use the private key—even the person who encrypted the message cannot decrypt what they encrypted!
You can imagine it like this: The store buys thousands of padlocks that can all be opened with a single key and ships them to the whole world. It keeps the key for itself. Anyone who wants to send something securely to the store takes a padlock and locks the package they are sending. Once it is locked, only the store can open the package.
Public-key encryption is one of many innovations in modern cryptography, which addresses numerous information-security challenges [3]—for example, digital signatures (a way to verify a sender’s identity) and distributed computing [4].
Despite its relative simplicity, the idea was proposed only in 1976 in a paper by Whitfield and Hellman [5], without a practical implementation. In 1977, Rivest, Shamir, and Adleman published the RSA method, the first public implementation of the idea. Why “public”? There are claims that British intelligence agencies and the NSA had discovered the method earlier. An interesting aspect is that the method relies on basic results in number theory, which until then was considered a “useless” field. Subsequent public-key encryption methods are also based on number theory [6].
A nice aspect of RSA is its simplicity. First we encode a message as a large number, denoted X. The public key consists of two numbers—a large number N (hundreds of digits long) and a number e that can be smaller but is still large. Encryption is simply raising X to the power e, dividing by N, and taking the remainder. This requires arithmetic with large numbers, but on modern computers such calculations are done in fractions of a second.
This would be our equation:
y=xe mod N
Decryption is similarly simple. The private key is just a number d, calculated from N and e so that if y is an encrypted message, after raising y to the power d and dividing by N, the remainder is exactly the original message x.
The equation:
x=yd mod N
So, the encryption system relies on the three numbers N, e, and d. How can we generate them? Here Euler’s totient function φ [7] comes into play: For each number, it returns how many smaller numbers share no common divisor with it [8]. A basic theorem of Euler states that for any natural number a, if we raise x to the power a·φ(N)+1, divide by N, and take the remainder, we get x again. Now, if φ(N) is known, it is easy to find e and d whose product has the form a·φ(N)+1 for some a; the only difficulty is computing φ(N), which is computationally hard when N is large. This difficulty is precisely the strength of the encryption method! If it were easy, anyone who knew N and e could compute d. In other words, anyone sending packages to the store could open other people’s packages.
How are the numbers for the encryption system chosen? Here additional information available to the system builder is used. If N is chosen as the product of two prime numbers, N = p*q, then φ is simple: φ(N) = (p-1)*(q-1). Now the system can be built: Randomly generate two prime numbers p and q (each hundreds of digits long, to prevent cracking by computation). Multiply them to obtain N, and proceed to find e and d using our extra knowledge of φ(N). Finally, publish N and e publicly. The primes p and q are discarded and forgotten, because they are no longer needed.
How can we find prime numbers with hundreds of digits, required for building the system? This seemingly difficult problem has a simple mathematical solution (the Miller–Rabin algorithm [9]), but that is a topic for a separate post.
We also note that, although modern encryption may seem to rely mainly on number theory, in practice it is a broad field with methods drawn from various areas of mathematics and computer science.
It is hard to imagine how the Internet could function without information security. Sometimes, even mathematical methods once considered useless can change our daily lives.
English editing: Elee Shimshoni
References:
