A History Lesson in Public Key Cryptography – What is Public Key Encryption and How Does It Work?
The RSA Conference is upon us. Considered the biggest security event of the year, its name also has a well-known algorithmic meaning. But perhaps less well-known are the names of the people responsible for the acronym – Rivest, Shamir and Adelman. These three brought fame to “public-key cryptography” and to two individuals: Alice and Bob. At the heart of this matter is riddle-solving, and for those who enjoy the intrigues, the secrecy and even the gossip behind the riddles- cryptography is for you. In this column we’ll take a look at the basics of public key cryptography.
Beginning the Journey with Diffie and Hellman
Let’s start with a riddle: a queen wants to send her cousin a treasure chest full of gold. She locks up the chest with a padlock and sends it along with her trusted knight. As the sole holder of the padlock’s key, she keeps it on her necklace. How can the queen’s cousin now open the box?
The solution requires the knight to make two more trips. First, the cousin adds to the chest his own padlock and sends the treasure chest back to the queen. Then, the queen opens her padlock with the key she owns and sends the treasure chest back to her cousin. Finally, the cousin can then unlock the remaining padlock with his key and open up the treasure chest.
This mathematical (i.e. encryption) solution came in the form of the Diffie-Hellman (DH) algorithm. In 1976, this pair of cryptography researchers wrote the seminal paper introducing the problem of communicating over an insecure, or public, channel, a.k.a., public key cryptography. In this scenario, two parties are interested in communicating in an encrypted manner. Up until the publication of this paper, the assumption was that both parties had to encrypt the messages using the same key. In the riddle, this would mean that both the queen and her cousin would hold copies of the padlock. Therefore, the two parties needed to somehow obtain the keys prior to communicating. But as mentioned, only the queen is the sole bearer of key. Likewise, in most real world scenarios – sharing keys does not make sense. After all, it’s not reasonable to consider that every bank holds a key for every past and present customer for eternity. Amazingly, DH had the foresight to see this approaching problem, noting: “The development of computer controlled communication networks promises effortless and inexpensive contact between people or computers on opposite sides of the world, replacing most mail and many excursions with telecommunications.” Remember, this was written in the mid ‘70s!
Coming Across the Man in the Middle
Let’s complicate the riddle. What if the knight – the courier of the treasure chest -is a thief, or was asked by the queen’s step-brother to check what valuables are contained within the queen’s treasure exchanges? The knight could simply add his padlock to the chest and send it back to the queen. The queen, not knowing who the additional padlock belongs to, would continue with the plan and open up her padlock. In case the cousin was anticipating the chest, the knight could continue and impersonate the queen by adding his own padlock to the now-unlocked chest and running as “courier” to the cousin. The queen and her cousin would have no idea that they weren’t communicating with one another.
Getting By with Help from Rivest, Shamir and Adelman
Since the queen and her cousin realize that their knight cannot be trusted, they devise their own scheme to keep him in check. First, the queen requests the cousin send her his padlock – unlocked. With the cousin’s padlock in hand, the queen then closes the padlock on the treasure chest and sends it to her cousin. Since only the cousin has the key to his padlock, only he can open the treasure chest. In a similar fashion, if the cousin wants to send a treasure chest to the queen, he uses the unlocked padlock of the queen and seals the chest by closing it.
This break-through solution was proposed (PDF) by Rivest, Adelman and Shamir (RSA) in 1978. Corroborated by the mathematical strength of problems more than 2000 years-old, this algorithm was an instant hit. The mathematical foundations were built upon the notion that given a product of two prime numbers, it is not easy to calculate any of these prime numbers. In this public-key cryptography scheme, the prime numbers (the padlock’s key) is considered the “private key” while the product of the primes (the open padlock) is the corresponding “public” key and may be known to all. There is only a single pair of private-public keys that together allow the encryption and decryption of the message.
These researchers not only had the foresight to realize the need for secrecy in email communications – their paper even begins with the statement: “The era of ‘electronic mail’ may soon be upon us” – they also realized that cryptography requires an established set of names.
Living Next Door to Alice
We can proceed talking about the communications of party A with party B, or in the riddle analogy – the queen and her cousin. But this could start getting confusing, and most of all, it ruins all the fun. Enter Alice (Party A) and Bob (Party B). In time, another player named Eve entered the crypto scene. Eve is the evil eavesdropper, whereas cryptography solutions focus on conducting proper communications even under Eve’s scrutiny. As further public key algorithms were invented under different scenarios, even more characters entered the scene. Mallory, for instance, is also one notorious gal. Not only does she eavesdrop, but she has the audacity to go ahead and intercept the communications- forging messages in Bob’s name or not forwarding messages from Alice. (While Alice and Bob may seem to you like any normal people, think again – as sordid details about them do emerge every once in a while.)
Getting More Out of RSA
RSA is brilliant. Not only does it provide secrecy and confidentiality, but it can also act as a signature. After all, Bob wants to ensure that the messages are sent by Alice. In this case, Alice signs the message with her private key. Since only Alice’s corresponding public key can “open” that message it is implicitly understood that she signed it.
Taking it further, say Alice is in a hurry and is not interested in encrypting the entire message. However, she wants to ensure that her message to Bob was not tampered by Mallory. She can then compute a value based on the message contents and sign that value (a “digest”) with her private key. From there, Bob can verify that the digest came from Alice by “opening” the digest with Alice’s public key. He can then run the message through the function and compare it with the one that was signed by Alice.
Shaking Hands with RSA RSA became a very common key-exchange protocol. In fact, SSL and its successor, TLS use RSA in their first stage of communication. Since exchanging information using RSA carries a computing burden, in practice protocols create a shared private key, per session, using RSA. For example, when you log into your bank, you may use the bank’s public key to establish a shared key.
Attacking RSA
While there are no direct attacks against the RSA algorithm itself, there are attacks which try to bypass it. The algorithm is known to all – what differs from key to key is simply that prime number. As such, attacks focus on finding that prime number. One way is to simply try and guess it (brute-force). For this reason, it is important to have a long enough key. RSA recommends at least 1024 bits for corporate use and 2048 bits for extremely valuable keys like the root key pair used by a certifying authority.
Another method of attack is to infer the key according to different characteristics. Returning to our queen riddle, say she and her cousin are plotting to attack the kingdom ruled by her step-brother. Although her step-brother cannot know what the treasure chests contain, he can make some reasonable assumptions on whether there is a plot in the making (because of the increase in travel of knights between the queen and the cousin), how much money is involved (by the how heavy the treasure chests seem), and the timing of the attack (an increase in frequency of the knights as the “D”-day approaches). In a similar fashion, adversaries were able to guess the private keys by calculating the time it takes to encrypt a message or by tapping into the communication lines and seeing how much power is being consumed.
Just a few days ago, researchers showed that the prime numbers are not as totally randomly generated as they should be.
Additionally, there are more concerning, practical issues regarding the distribution of the public keys. The Public Key Infrastructure (PKI) attempts to solve this problem, but as shown in the last entry – this comes with its own myriad of problems.
Where are they all today?
You can catch most of the individuals behind DH and RSA at the Cryptographer’s panel on Tuesday, Feb. 28th at 10:30am. As for Adelman, it’s best to catch him at the theater near you; that is, giving Gauss some famous ratings in the ultimate hacker movie – Sneakers.
Related Reading: Examining Threats Facing Public Key Infrastructure (PKI) and SSL
