#045: Exchanging Keys
Last Week, I wrote about how symmetric encryption algorithms like AES do the hard work of securing the actual bits and bytes. But at the end, Alice and Bob still had a problem: In order for AES to work, both need to have the secret key; unless you have the secret key, you can’t encrypt your data, but to securely exchange the key, you need to encrypt your data. So how can you solve this? Well, you could meet up and physically exchange the key, or you could use a trusted courier to send a copy of the key to your opposite side. Neither one is very practical though, so Alice and Bob need a different scheme to establish secure communications.
(As before, I’ll gloss over a lot of both the mathematical and technical details, but hopefully the links provided will satisfy your curiosity, should you want to know more)
This is where asymmetric encryption algorithms come into play, also known as public key cryptography. Instead of having a shared key, you start out by generating a private and public key pair. The public key can be freely published and distributed to everyone, as its name implies, while the private key, well, stays private and secure. And Eve cannot deduce the private key from the public key alone (or vice versa). To decrypt anything, she needs to have both public and private keys. A well-known algorithm in this family is one developed by Ron Rivest, Adi Shamir, and Leonard Adleman (RSA).
Now, if Alice wants to send Bob a message using RSA, all she has to do is take Bob’s public key, use that to encrypt the message, and send it to Bob. Eve can read the encrypted message, but even though she too has access to Bob’s public key, she would need his private key to decrypt it, and thus is unable to read the message. Bob, on the other hand, can decrypt the message, and read it just fine, since he does have the private key needed. The Simple English Wikipedia provides an excellent example with actual values to illustrate how the RSA algorithm works.
Another effect of this system is that both Alice and Bob can authenticate themselves to each other. If Alice encrypts the message with her private key first, and then encrypts the result again using Bob’s public key, Bob first uses his private key to decrypt the first layer, and then uses Alice’s public key to decrypt the second layer. Since decrypting a message using someone’s public key is only possible if their private key was used to encrypt it, Bob knows Alice was the one who sent the message.
Even if you don’t care about encrypting a message, you can still use this scheme to securely sign a message from yourself, so anyone can securely verify that it was indeed you. To do so, after you write your message, you create a hash signature of it, and then use your private key to encrypt this hash, and attach it to the message. If someone else wants to verify that it was indeed you who wrote the message, they first decrypt the hash signature you attached using your public key, and then compare that hash signature with the one they computed from your message.
RSA et al. do have a weakness, though. They rely on choosing a very large number (let’s call it N) that is the product of two very large prime numbers (We’re talking over 600 digits here). If you are able to determine the prime factors of N, you break all such encryption schemes. Modern hardware as well as modern factoring algorithms have become quite good at doing so, so to ensure RSA stays ahead & safe, you have to choose larger and larger values of N. And since RSA isn’t the most efficient algorithm in the first place, it is impractical to use it alone to encrypt all of your communications, especially on mobile devices.
However, since we already have perfectly good & fast encryption algorithm with AES, you can combine those two into a new scheme: Exchange a secret key for AES using RSA, and then encrypt the rest of the communication with AES.
This is also why AES is indirectly threatened by improvements in factoring huge numbers, because even if Eve can’t decrypt Alice’s and Bob’s communication right now, she can store all the communication between her targets for later. Once Eve can crack Alice’s and Bob’s RSA keys, she can get at the AES key used to encrypt their actual messages, and read them all.
There is, however, a third way, which protects us even against this method of attack. I’ll write about it next week.