Cryptography and RSA Encryption

(Note: For a brief introduction to the basis behind RSA encryption, visit the expii article on Primality testing and significance)

Cryptography: the reason behind why the unimaginable amounts of data on the internet are kept safe and protected. Cryptography itself is the art of code-breaking, but today we have implemented things called cryptosystems to keep our information safe.

Public-key cryptography is a system that requires a public key and a private key: one to encode the message and one to decode the message respectively. As implied by the names, everybody can see the public key, but only the person with the private key will be able to decode the public key's meaning. The algorithms for public-key cryptography are based off of mathemathical algorithms that are extremely inefficient for computers to solve quickly.

The most widely used public-key cryptosystem today is called RSA, which was developed at MIT by Rivest, Shamir, and Adleman. The core idea behind breaking the RSA encryption (more commonly known as the RSA problem) is based on multiplying two extremely large prime numbers to form a semiprime, which is used as a public key to encrypt data transmissions. To solve the RSA problem, one must know the private key, which is one of the large prime numbers that were multiplied to form the public key. If you don't know the private key - well, conventional computers are remarkably inefficient in factoring semiprimes! The most commonly used algorithms are the general number field sieve and the quadratic sieve; however, even with these incredibly powerful tools of number theory, classical computers take an incredibly long time to solve semiprimes. For example, RSA-200, a 200 digit semiprime, was successfully factored in 2005 using the general number field sieve and a collection of parallel computers. It would have taken approximately 75 years of CPU work if it was factored by a single 2.2 GHz Opteron-based computer. Likewise, it “would essentially take the age of the universe”, according to MIT mechanical engineer Seth Lloyd, for any conventional computer to find the factorization of a 500 digit semiprime.

The process for generating public keys via the RSA encryption algorithm is as follows:

The RSA algorithm defines n = pq, where p and q are primes, a private key d, and a public key e such that $de\equiv 1 \pmod{\phi(n)}$

$(e, \phi(n)) = 1$

where $\phi(n) = (p-1)(q-1)$ represents the secret message itself. The private key must be calculated using the congruence statement stated above. However, a prospective attacker can only see the public key, e.

Suppose the message sent using RSA encryption is denoted M. To encode this message, M, the sender chooses a value n = pq and a public key e and sends message E:

$E\equiv M^{e} \pmod{n}$

To decode this message, the receiver - who is the only person who is supposed to know d, the private key! - computes:

$E^{d} \equiv M^{(e)d} \equiv M^{ed} \equiv M^{N\phi(n) + 1} \equiv M \pmod{n}$

Phew! That's a lot of math! Let's see an easy example.

Alice and Bob (the two conventional names used in cryptography for receivers and senders) are friends. Alice wants to send a secret message, M = 65, to Bob. As a result, Alice gives Bob n = pq = 61 * 53 = 3233.

$\phi(n) = (p-1)(q-1) = (61 - 1)(53 - 1) = 3120$

Suppose Alice chooses e, the public key, as 17 - e can be any number that is relatively prime to 3120 and 1 < e < 3120.

Now Alice has to encrypt her message, M = 65, and send the encrypted message E to Bob.

$E\equiv65^{17} \pmod{3233}\equiv2790$

Now d, the private key, must be calculated. As shown by the first equation, d is the modular multiplicative inverse of e (mod(p-1)(q-1)). In other words, it is the smallest number for which $d * e \equiv 1 (mod(p-1)(q-1))$. A quick brute force search reveals that d = 2753.

Now Bob receives his private key in the form (n, d). He can now decode the message like so:

$E^{d} \equiv 2790^{2753} \pmod{3233} \equiv 65$

Cool! Now Bob has the secret message 65. You might be wondering why Alice wanted to send Bob a number in the first place, but this can be an actual message with words! Say that Alice and Bob have a secret version of the alphabet in which they've assigned special values to each letter. Combining these letters in a certain way will yield a number. This number can be sent as a secret message, which Bob can then decode into plaintext. Depending on how their cipher works, Alice could have just been saying, "Hello!".

As you might imagine, attackers who don't know certain parts of the equations shown above may have a difficult time if they are presented with only the public key! Conventional computers are exceedingly slow at finding prime factors manually, which is one of the reasons why the RSA encryption system is so efficient.

However, since the future is fast coming upon us, a new type of technology called quantum computing has been developed. If and when the age of quantum computers (essentially computers that due to superposition, can perform multiple calculations in a single moment while normal computers can only perform one) comes upon us, the RSA problem will not be as much of a problem anymore. In 1994 when Peter Shor derived his eponymous algorithm which essentially proved that quantum computers could factor large numbers with extreme speed. Furthermore (this is a bit abstract), imagine that a 500-digit prime number is described as a wave. Peter Shor showed that if given the wave for a 500 digit semiprime, a quantum computer could find the periodicity of the two 250 digit numbers that multiply to form the semiprime and thereby determine the factors. Unfortunately, for the moment, quantum computers are still in their developmental stages. The RSA encyrption is still an efficient cryptosystem!

If you'd like to see some of the effort that's been put into cracking the RSA encryption, check out the RSA Factoring Challenge! It's been discontinued, but there are still some crazy semiprimes out there that still haven't been factored. See if you can figure them out!