# The RSA problem

The RSA algorithm is heavily relied upon to secure communication on the Internet. Primarily this is done in the form of certificates used to secure SSL/TLS connections as is done to secure the HTTPS protocol. But would you believe that the RSA algorithm cannot be shown mathematically to be secure? It’s true! This fact is known as the RSA problem.

To understand why the RSA problem exists, it is necessary to understand how the RSA algorithm works. It turns out there’s not that much to it. RSA is a public/private key encryption algorithm, also known as an asymmetric key encryption algorithm. With a public/private key pair, a value can be encrypted using the public key and can only decrypted using the corresponding private key. I’ll first explain how to generate and use an RSA public/private key pair and then attempt to describe the mathematics behind why it works. Once that’s out of the way, it will be possible to explain the challenge of mathematically proving that the RSA algorithm is secure.

To generate an RSA public/private key pair, you first choose two large prime numbers. Let’s call them p and q. The product of p and q we’ll call n. Using p and q, knowing they are prime, we can easily compute φ(n) = (pq)(q – 1) where φ is Euler’s totient function. Next, we’ll choose an exponent which we’ll call e, which is less than φ(n) and coprime with φ(n). Next we’ll calculate the multiplicative modualar inverse of e (mod φ(n)), which we’ll call d. The combination of n and e is the public key. The combination of n and d is the private key.

To encrypt a value m, which must be less than n, using the public key we calculate

c = me (mod n)

To decrypt c using the private key we can obtain the original value m by calculating

m = cd (mod n)

Why does this work? The answer lies in Euler’s theorem. Euler’s theorem proves that for any coprime integers a and n,

aφ(n) ≡ 1 (mod n)

If you’re not familiar with modular congruence, this states that if you divide aφ(n) by n, the remainder will be 1.

What we need to do is show that (me)dm (mod n). Note that (me)d can also be written as med.

Since we chose d such that ed ≡ 1 (mod φ(n)), we can also say that ed = 1 + hφ(n) where h is some positive integer. Therefore

medm1 + hφ(n)m(mhφ(n)) ≡ m(mφ(n))h (mod n)

Now, using Euler’s theorem we can convert the last term into

m(1)hm (mod n)

which is what we intended to show. As long as m is a positive integer less than n then m is equal to the least positive member of the congruence class of (me)d (mod n), meaning m is the remainder when dividing by n. Note that if m is too small then me may be less than n and it may be possible to derive m from me by taking the eth root of me.

So what’s the problem? The problem is that the security of the RSA algorithm rests on an unproven assumption. The assumption is that it is easier to find two very large prime numbers than it is to factor their product. It turns out it’s very easy to find large primes, or rather to find very large integers that are very likely prime. For example, choosing two random 512-bit numbers that are likely prime can be done in a small fraction of a second with a modern computer. However, using the most efficient currently known integer factorization algorithm, factoring the 1024-bit product of those two primes would take many thousands of CPU-years of computation.

But why does the complexity of factorizing the product of two primes matter with respect to the security of RSA? The reason is that if the two primes chosen, p and q can be obtained by factoring their product, n, which is part of the public key, then it becomes trivial to calculate φ(n), and then it becomes trivial to calculate d. Being able to easily calculate d given n means that the private key can easily be recovered from the public key. Being able to easily recover the private key from the public key would completely invalidate the security of the RSA algorithm.

So, again, what’s the problem? It takes far longer to factor the product of two large prime numbers than it takes to choose them. We’re safe using RSA, right? Well, the problem is that while the currently known algorithms for factoring the product of two large primes take far longer to factor than it takes to choose them, nobody has so far been able to prove that a much faster algorithm doesn’t exist. That doesn’t mean that one does exist, just that we can’t say for sure that one does not.

In fact, at least one such algorithm is known to exist, but it is currently impractical to implement on the scale necessary to defeat RSA. The algorithm is known as Shor’s algorithm and it relies on quantum computers able to process numbers as large as n, which currently do not exist for values of n currently used in RSA public keys. Quantum computers are getting more and more powerful all the time, however, so it’s a good bet that the days of RSA are numbered since eventually quantum computers will be able to factor numbers large enough to make the use of RSA impractical.

# A simple explanation of SSL/TLS

#### What is SSL/TLS?

SSL, which stands for Secure Sockets Layer, was originally created by Netscape Communications to secure eCommerce applications. Version 1.0 was never released but version 2.0 was released in 1995 followed by version 3.0 in 1996. SSL was adopted as an open standard by the Internet Engineering Task Force and renamed to TLS, which stands for Transport Layer Security. TLS version 1.0 was released in 1999. Version 1.1 of TLS was released in 2006 followed by version 1.2 in 2008.

In the interest of full disclosure, Netscape Communications was purchased by AOL Inc. in 1999. I was employed by AOL Inc. from September 2002 through December 2003. I don’t feel this necessarily biases me in respect to this discussion but you may choose to interpret this information however you wish.

SSL and TLS are algorithms for secure communication over an insecure medium by two parties who have not necessarily previously interacted. Typically SSL/TLS are used over TCP connections but there have been proposals for their use over UDP as well. SSL/TLS is the mechanism used to secure the HTTPS protocol.

SSL and TLS provide security by way of three key mechanisms:

• Endpoint Authentication
• Message Integrity
• Secrecy
##### Endpoint Authentication

Endpoint Authentication means that while communicating electronically with a party at the other end of a communication channel, I can be certain that the party I’m communicating with is actually the party I think I’m communicating with. In SSL/TLS, this is provided by the use of server and optionally client digital certificates as well as a trust network in the form of a database of Certificates of Authority.

##### Message Integrity

Message Integrity means that while communicating electronically with a party at the other end of a communication channel, I can be certain that the content of the message I receive has not been altered while in transit. The data I receive is exactly what the sender sent. Message Integrity is provided by the inclusion of a MAC with each message.

##### Secrecy

Most people think only of Secrecy when they think of SSL/TLS. Secrecy means that while communicating electronically with a party at the other end of a communication channel, other parties observing my conversation cannot know the content. Secrecy is provided by SSL/TLS through the use of symmetric encryption.

#### Why do we need SSL/TLS?

The reason we need SSL/TLS is because we often need to communicate over insecure media. The Internet is an insecure medium. When you send network packets from your computer to another computer via network infrastructure not directly under your control, you can’t be certain what exactly happens to it in between. You can’t even be certain it will ever arrive at its intended destination. “Network infrastructure not directly under your control” can also mean the space all around you if you happen to be using a wireless network at a Starbucks, for example.

Vulnerabilities to unsecured communications can include active or passive attacks. Man in the middle attacks can be either active or passive. Firesheep would be an example of a passive attack. The bottom line is that when you send data over an insecure medium, you don’t know where that data is going or who is going to intercept it and when you receive data over an insecure medium, you can’t be sure where it came from or who sent it. An unsecured communication channel over an insecure network cannot be trusted.

#### How does SSL/TLS work?

I won’t go too far into details, but here’s a set of illustrations that show both the problem and how SSL/TLS solves them. The illustrations will chronicle a riveting love story between Steve and Sally with Joe passing messages between them. Steve and Sally will initially just pass messages to Joe, trusting him to deliver them unaltered to their true love. We’ll see what Joe can do to the messages in transit and we’ll figure out ways to keep Joe from being such a jerk. In this way, we’ll derive the fundamentals that SSL/TLS uses to provide Endpoint Authentication, Message Integrity, and Secrecy.

#### Let’s meet the cast in our story

Steve is our manly hero who is in love with Sally.

Sally is our beautiful heroin who is in love with Steve.

Joe is the villain who is Jealous of Steve and Sally’s love and who is also greedy and completely lacking integrity.

#### He said, She said

Scenario: Steve wants to send a love letter to Sally, but he doesn’t know exactly where Sally lives, so he writes it and gives it to Joe because Joe says he knows where Sally lives.

“I love you, marry me”
“Send me money”
“Go to hell”
“I hate you, asshole”

The problem is that Joe, acting as the middle man, has altered the communication before passing it on. What Steve and Sally need is a way of protecting their messages from Joe.

#### Symmetric Key Cryptography

Symmetric Key Cryptography is a form of cryptography where the same key used to encrypt a message can also be used to decrypt the encrypted message.

In cryptography, we speak of data as being in plaintext or cyphertext. Plaintext is unencrypted whereas cyphertext has been obscured using some cryptographic algorithm.

A symmetric key encryption algorithm is an invertible function that takes plaintext and a key as input and produces cyphertext. The inverse of the function takes the same key and the cyphertext and produces the original plaintext.

```Encrypt(key, plaintext) -> cyphertext
Decrypt(key, cyphertext) -> plaintext```

To be useful to exchange information securely between two parties, the key must be known to both of them. This is known as a shared secret.

#### Steve Uses Encryption

Scenario: Steve chooses a key and uses it to encrypt his love letter to Sally. Steve gives the encrypted letter to Joe to give to Sally.

“@#\$%!”
“???”
“@#\$%!”
“???”

Now Joe can’t read Steve’s letter. Now Sally can’t read it either. Steve needs to share the key he chose to encrypt his love letter with Sally.

#### Steve Shares his Key

Scenario: Steve chooses a key and uses it to encrypt his love letter to Sally. Steve gives the encrypted letter and the key to Joe to give to Sally.

“I love you, marry me + key”
“Send me money”
“Go to hell + key”
“I hate you, asshole”

Now Sally can read Steve’s letter. But now Joe can read Steve’s letter. Worse, Joe can also choose a different key and change the message and encrypt it with his key and give Sally the altered letter and Joe’s key. We’re back where we started. Steve needs a way to get the key he used to encrypt his letter to Sally without Joe being able to access it.

#### Public Key Cryptography

Public Key Cryptography works similarly to symmetric key cryptography except that there are a pair of keys rather than just one. The pair of keys consists of a public key and a private key. The public key can be used to encrypt data and the private key can be used to decrypt it. The public key can be freely shared while the private key must be kept secret. If you generate a public/private key pair, anyone who has your public key can encrypt a message and send it to you and it doesn’t matter who sees the encrypted message because nobody can decrypt it without the private key, which only you have.

```Encrypt(key_pub, plaintext) -> cyphertext
Decrypt(key_priv, cyphertext) -> plaintext```

This method of encryption totally avoids the need for a shared secret. Our hero and heroin could each choose a public/private key pair, exchange the public keys through Joe and just encrypt all their love letters with the others’ public key and send the encrypted letters through Joe as well. The problem is that public key cryptography algorithms are orders of magnitude slower than symmetric key cryptography algorithms. Fortunately, we can get the best of both worlds. All we need to do is choose a symmetric key and share that securely by encrypting it with a public key. Now we can exchange a shared secret through Joe and Joe can’t read it.

Additionally, Public Key Cryptography can be used in the reverse direction to produce a digital signature. This is done by encrypting a digest of a message using the private key. Anyone with the public key can decrypt it can compare it to the digest of the message. In this way, anyone can verify that the signature was generated by the holder of the private key.

```Hash_priv(key_priv, plaintext) -> signature
Hash_pub(key_pub, plaintext, signature) -> match/no-match```

#### Steve Asks For Sally’s Public Key

Scenario: Steve wants Sally’s public key so he can send her an encrypted love letter and the key he used to encrypt it. Joe gives Steve Joe’s public key. Steve encrypts his love letter with his symmetric key and he encrypts the symmetric key with Joe’s public key and he gives both to Joe. Joe now can decrypt the symmetric key and then he can decrypt the love letter.

“Here you go”

“I love you, marry me + key”
“Send me money”
“Go to hell + key”
“I hate you, asshole”

The problem now is that Steve thinks he has gotten Sally’s public key but he’s really gotten Joe’s public key. He thinks he’s sending a message that only Sally can read but he’s wrong. Joe needs a way to know that he’s gotten Sally’s public key rather than Joe’s.

#### Trusted Third Party

Meet Sam, a new cast member in our story. Steve has met Sam and has gotten Sam’s public key. Sally has met Sam and has gotten Sam’s public key. Joe doesn’t like Sam because, unlike Joe, Sam is very trustworthy.

Sam is able to digitally sign Steve and Sally’s public keys. The way this is really done is by packaging up the public key with some metadata about it in something called a certificate. Importantly, the certificate contains the public key and the name of the owner.

Scenario: Sally generates a certificate with her name and public key and asks Sam to sign it. Sam signs it and returns the signed version to Sally. Steve now asks Sally for her certificate through Joe and she gives it to him, also through Joe. Steve can now encrypt his love letter with a symmetric key and encrypt the symmetric key with Sally’s public key and send both to Sally through Joe. Joe can’t read the messages in transit.

“Here you go”
“Here you go”
“I love you, marry me + key”
“???”
“Go to hell + key”
“I hate you, asshole”

The problem now is that while Joe can’t know the content of the message Steve is sending to Sally, he can still choose his own symmetric key, send any message he wants to Sally, encrypt it with his symmetric key, encrypt his symmetric key with Sally’s public key, and send his own encrypted message and encrypted key to Sally. Sally won’t know that Joe altered the message in transit. Joe won’t be able to send a message to Steve using the symmetric key that Steve chose because he can’t know it because Joe doesn’t have Sally’s private key. Steve will probably know something’s wrong, but Sally won’t.

#### Message Authenticity Codes

The final piece of the puzzle comes in the form of Message Authenticity Codes or MAC. A MAC is a hash of the combination of a message and a shared secret key. When two parties are communicating over an insecure medium and both have access to a shared key, the sender can generate a MAC of the message and send both the message and the MAC. The recipient can generate the MAC of the message using the same key and know if the message has been altered in transit based on whether the calculated MAC matches the one received with the message.

Using a MAC, Steve and Sally can exchange a public key, a shared secret, and any number of messages, all through Joe without Joe being able to read the messages or alter them.

“Here you go”
“Here you go”
“I love you, marry me + key + MAC”
“I will! + MAC”
“I love you, marry me + key + MAC”
“I will! + MAC”

Now our hero and heroin can live happily ever after…

#### A Less Contrived Explanation

I’ve taken a lot of liberties with the details of the protocol in the illustrations above. In actuality, an SSL/TLS conversation is quite a bit more complicated. Nevertheless, I’ve covered all the principles involved. To give these illustrations more context, Steve could be you, Sally could be the website of your bank, and Joe could be any number of switches or proxies operating between your computer and your bank’s computers and that may or may not be controlled by unscrupulous people wishing to drain your bank account.

Who’s Sam? Sam represents an entity you may not have heard of. Sam is a Certificate of Authority or CA. A CA is a certificate that is allowed to digitally sign other certificates. A CA may or may not be signed by some other CA. If not it’s known as a root certificate. Certificates of Authority are distributed in a trust database which is basically just a list of trusted root certificates, although it may contain some non-root certificates as well. Your browser may have been downloaded with its own trust database (Firefox contains its own trust database) or it may use the trust database of your OS (Chrome and Internet Explorer do this).

Who controls the CAs? CAs are owned by companies or other organizations that are presumably trustworthy. Who decides what CA owners are trustworthy? That’s done by companies that make browsers, like Mozilla and Microsoft. Ultimately, it’s up to you to decide whether you trust Mozilla and Microsoft to make these decisions for you. Regardless of whether your browser uses its own trust database or the trust database of your OS, it likely gives you the opportunity to manage your trust database for yourself. The trouble is that most people wouldn’t know how to do this, much less how to make good decisions. Most people just have to trust Mozilla and Microsoft.

I won’t go too deep into the details, but let’s just take a minute to examine how the SSL/TLS protocol really works. The following describes how the most basic SSL/TLS conversation looks like. It can get a lot more complicated than this, but now that you know the principles from the earlier illustrations, all of this should make a lot of sense.

First, a client will contact a server to establish a TCP connection. Next, the client will send a Client Hello message which contains the protocol version the client wants to use, a client random data, and a list of cypher suites the client wants to use. The Client Hello message is sent in plaintext so anyone observing the conversation will see the client random value. That’s OK because it’s just going to be combined with other random data later.

If the server accepts the protocol version and cypher suites offered by the client, the server will respond with a Server Hello message followed by a Server Certificate message and a Server Hello Done message. The Server Hello message contains the negotiated protocol version and cypher suite and a server random data. The important thing to note here is that the server sends its certificate in the Server Certificate message which should have previously been digitally signed by a CA that the client trusts.

Next, the client will verify that the certificate is owned by the organization that the client intended to contact, typcially by comparing the Common Name field of the X.509 certificate to the domain name of the website it was trying to connect to and by validating that the certificate was signed by a CA that it trusts and that the digital signature is valid. The client will then send a Client Key Exchange message that contains what is called a premaster secret. The premaster secret is generated by the client using the client and server random data. The premaster secret is encrypted using the public key of the server provided to the client in the server’s certificate. Only the server that the client is intending to communicate with should have the private key corresponding to the public key in the server’s certificate so only that server should be able to decrypt the premaster secret.

Both the client and server will separately derive what’s called the master secret from the premaster secret. The master secret is used by both client and server to derive the symmetric keys and hash keys used for the remainder of the conversation. While these are all shared, it turns out that client and server use separate symmetric keys to encrypt the data they send. The keys used to calculate the message MACs are also separate for client and server as well as separate from the encryption keys.

Next, the client will send a Change Cipher Spec message that verifies the protocol version that the client believes the server has agreed to, followed by a Client Finished message. The Client Finished message contains a hash of the entire SSL/TLS handshake as seen by the client using the client hash key. The server will verify that the hash generated by the client matches the hash that the server generates for the conversation using the client’s hash key. If the hashes don’t match then the server knows that the handshake has been manipulated in transit.

If the handshake hash from the client is validated by the server, the server will send a Change Cipher Spec message followed by a Server Finished message. The Server Finished message contains a hash of the entire handshake conversation as seen by the server and hashed using the hash key of the server. The client will generate the hash of the handshake conversation using the server’s hash key and compare it to the hash received from the server. If it doesn’t match then the client will know the handshake was manipulated in transit.

At this point the handshake is completed and application data can be sent and received according to whatever application protocol is in use. Any message that is sent is encrypted using the symmetric key of the sender and coupled with a MAC generated using the message combined with the hash key of the sender. Upon receipt, the message is decrypted using the hash key of the sender and the MAC is validated using the hash key of the sender. Remember that both sides have their own symmetric and hash keys but all four keys are possessed by both sides.

The client can validate that it is communicating with the intended server because it validated the server’s certificate. Both client and server can be certain of the integrity of the data they receive by verifying the MAC that accompanies each message. All data sent and received following the handshake is encrypted using keys derived from the premaster secret which was shared by the client with the server using the server’s public key. These components have, respectively, provided the SSL/TLS conversation with endpoint authentication, message integrity, and secrecy.

But wait, there are two endpoints involved in any TCP conversation and only one of them was authenticated with a certificate. In the example I’ve just covered, only the server provided a certificate. In fact, SSL/TLS have a facility for the server to demand during the handshake that the client also provide a certificate. While the authenticity of the server is always verified since the Server Certificate message is a required part of the handshake, the request by the server for a client certificate is optional. Most of the time, this facility is not used. This is because clients are typically authenticated using a password at the application layer after the SSL/TLS conversation is already established. If everyone could be authenticated using certificates all the time, the world would be a better place. Unfortunately, key management is somewhat complicated. For this reason, client certificates are most often used for server to server communication.