How can Alice send out a message that everyone can verify that it is from her?

In this lesson we will learn about Asymmetric Cryptography (also called Public Key Cryptography). Asymmetric / Public-key Cryptography allows us to establish secure communications even when we have no opportunity to agree on a secret key ahead of time or via another communication channel. This is crucial for secure transactions over the internet. Additionally, asymmetric/public-key cryptography will provide us with a mechanism to digitally "sign" files, which allows us to provide non-repudiation.

Limitations of Symmetric (Secret Key) Encryption

Navy and Marine Corps aircraft need to be able to communicate with each other and with ground forces and ships and, of course, this communication should be secure. One standard used by Navy and Marine Corps aircraft is "KY-58", which uses a symmetric (i.e. secret key) encryption algorithm develped by NSA. The key (called the "red key") is thought to be 128-bit, but we don't know for sure because the details are classified!

With secret key encryption it's generally a good idea not to use one key for too long. So KY-58 keys change frequently. However, if you are in the air when the key changes, you have a problem: how are you going to get the new key? The solution employed by KY-58 is to keep a special key called a "Key Encrypting Key" (KEK) on the aircraft. The red key, which is actually used for secure communication is produced by encrypting another key, called the "black key", with the KEK. So, when it's time to switch to a new red key, the new black key is actually broadcast "in the clear" (unencrypted) for all the world to hear. All the aircraft (and other good guys) receive the black key and use their KEK to produce the new red key. The bad guys know the new black key but, not knowing the KEK, they don't know the new red key, which is what's actually used to encrypt communication.

today's black key which is broadcast in the clear

red key which is used to encrypt today's communications


The fundamental limitation of symmetric (secret key) encryption is ... how do two parties (we may as well assume they are Alice and Bob) agree on a key? In order for Alice and Bob to communicate securely they need to agree on a secret key. In order to agree on a secret key, they need to be able to communicate securely. In terms of the pillars of IA, To provide CONFIDENTIALITY, a secret key must first be shared. But to initially share the key, you must already have CONFIDENTIALITY. It's a whole chicken-and-egg problem.

This problem is especially common in the digital age. We constantly end up at websites with whom we decide we want to communicate securely (like online stores) but with whom we there is not really an option to communicate "offline" to agree on some kind of secret key. In fact, it's usually all done automatically browser-to-server, and for the browser and server there's not even a concept of "offline" — they only exist online. We need to be able to establish secure communications over an insecure channel. Symmetric (secret key) encryption can't do this for us.

Asymmetric (Public-key) Encryption

In asymmetric (public key) cryptography, both communicating parties (i.e. both Alice and Bob) have two keys of their own — just to be clear, that's four keys total. Each party has their own public key, which they share with the world, and their own private key which they ... well, which they keep private, of course but, more than that, which they keep as a closely guarded secret. The magic of public key cryptography is that a message encrypted with the public key can only be decrypted with the private key. Alice will encrypt her message with Bob's public key, and even though Eve knows she used Bob's public key, and even though Eve knows Bob's public key herself, she is unable to decrypt the message. Only Bob, using his secret key, can decrypt the message ... assuming he's kept it secret, of course.

It's impossible to overstate the importance of this: Alice and Bob do not need to plan anything ahead of time to communicate securely: they generate their public-private key pairs independently, and happily broadcast their public keys to the world at large. Alice can rest assured that only Bob can decrypt the message she sends, because she has encrypted it with his public key. Note, however, that while this provides a solution to Alice's confidentiality problem (she knows only Bob can read the message), Bob has an authentication problem on his hands. Yes, he's received a message only he could read, and the message claims to have been sent by Alice, but he has no guarantees that it really did come from Alice. Some public key cryptography algorithms, including the RSA algorithm that we'll cover in some depth, have the special property of being commutative, which means that the roles of private versus public key are interchangeable. Thus, Alice could encrypt a message with her private key that is decryptable only with her public key. Since everyone knows her public key, you may well ask what the point would be. Well, this message would be readable by anyone, but only Alice could have created it! (Because only her private key produces messages decryptable by her public key.) This provides a form of authentication. So, if Alice's plaintext message is M, and she first encrypts M with her private key, then with Bob's public key, Bob can take the message he receives and decrypt first with his private key and then with Alice's public key, and he'll recover M. The guarantees are that only Bob can read the message, and only Alice could have sent it. This process, in a relatively compact form is illustrated below.

RSA (Rivest, Shamir & Adleman) Encryption)

The RSA encryption scheme provides commutative, asymmetric (public key) encryption. The public key consists of two large integers (e,n) and the private key consists of two large integers (d,n). Note that the second number, n, is the same in both! The three numbers e,d,n are related in a special way, which requires a bit more mathematics to go into. The crucial point is that n is guaranteed to be the product of two prime numbers, i.e. n = pq for two primes p and q. If you know e and n, and you've found the factorization of n into pq, you can compute d easily. So the security of RSA requires that factoring a large integer is difficult. And when we say large, we're not kidding! Today, RSA implementations might use a 4096-bit number for n. Nobody currently knows how to factor numbers of that size quickly, which is to say before we and our planet are long dead, so RSA seems pretty secure. However, nobody has proved that it's impossible to factor numbers quickly either, so RSA may be broken some day.

Here's a sample public/private key pair for Alice:

Alice's  Public Key: (e,n) = (1109b2300a79fff51384a909ce9b00df,1640a0dc17d31a9d49a2581a452f98ef)
Alice's Private Key: (d,n) = (7b3b397def11a1821c883c5ab66290f, 1640a0dc17d31a9d49a2581a452f98ef)
and here's a sample public/private key pair for Bob:
  Bob's  Public Key: (e,n) = (106d231ecc13338084a1b857bb82a20b,a265d9387a8a395527c98eeb024806dd)
 Bob's Private Key: (d,n) = (969256f3feb06827b793bf8450f6d623,a265d9387a8a395527c98eeb024806dd)
Below is a little demo of RSA encryption to use. Try to encrypt a message as if you were Alice and decrypt the message as if you were Bob. Keeping straight which key to use is the important point here. Note, however, that this is just a 128-bit key, which is nowhere near a length that is currently considered to be secure:
Check out the SI110 RSA Demo Page which is linked off of SI110 Resources.

The Security of RSA

We won't go into too much detail about how RSA works: block size, padding schemes, key-generation etc., even though getting these kinds of details right when implementing RSA is actually tricky. However, it is important to understand one fundamental fact: it is always possible to crack RSA by computing someone's private key from their public key. All it it takes is being able to factor the modulus (the number n that's common to both the public and private key) into its two prime factors. However, if the modulus is big enough, even though it will be possible to do the factorization, it will not be feasible — meaning that the time/computing-power required to do it is simply too great. After all, if Eve dies of old age before her computer factors the modulus from Bob's public key, it doesn't do her a lot of good.

The power of RSA, and the reason that even though it has been in use since the 1970's it can still be secure, stems from the fact that as computers and algorithms get faster, so that it becomes feasible to factor bigger and bigger numbers, we can simply use bigger (and therefore harder to factor) numbers for the modulii in our RSA keys. Moreover, increasing the size of the modulus even a relatively small amount vastly increases the difficulty of factorization.

Generally, when you read N-bit RSA it means that the modulus (the number n that's shared by the public and private keys) is N-bits long. In 1990, 512-bit RSA keys were deemed pretty secure. In the intervening years, the computing power of a typical desktop computer has increased several thousandfold. Still, today 2048-bit RSA is deemed pretty secure. That means that we've only had to increase our RSA key size by a factor of four to make up for the more than 1,000-fold increase in the computing power of a typical desktop PC. If you are really worried about security, simply increase the bit-size of your RSA keys!

Digital Signatures

Suppose Alice sends a contract agreement to Bob. To avoid legal troubles, we'd like this communication of contracts to have the property of non-repudiation — Bob should be assured that Alice can't back out of the deal by claiming she never sent the contract. Likewise, we want the property of integrity — Alice should be assured that Bob can't modify the contract and claim that the modified version is what Alice sent him. There's a nice technique called a digital signature that provides these guarantees. Alice simply computes a hash of the contract agreement, encrypts that hash with her private key, and sends the result (which is the electronic signature) along with the contract to Bob.

Anyone can take the contract, hash it, and compare the result with what you get when you decrypt the electronic signature with Alice's public key. If it matches then the contract must be exactly the same as what Alice sent, because:

  1. Alice must've sent it, because only Alice can encrypt something that decrypts properly with Alice's public key.
  2. The contract can't have been modified, because the hash value would've changed.

Your CAC supports a number of different cryptographic algorithms, including:
Hashing: SHA-512
Symmetric encryption: AES-256
Asymmetric cryptography: RSA-2048
... and others. Included on your CAC are public/private key pairs that you can use to decrypt e-mails intended only for you, and to ditigally sign documents.

Man-in-the-Middle Attack

Asymmetric (public key) encryption is almost magical — you create security out of insecurity. However, there is still one weakness in the system that's fundamental: you see on a website something like
Hi, I'm Bob and my public key is (106d231ecc13338084a1b857bb82a20b,a265d9387a8a395527c98eeb024806dd)
But how do you know that public key really belongs to the guy you know as "Bob"? While you can be assured that, if you encrypt a message with this key, only the key's owner will be able to decrypt it, how can you be sure that the key's owner is really "Bob"? If you trust the website on which the public key is posted, you might be comfortable. But at the end of the day, you have to trust whoever is presenting this key as belonging to "Bob", and that trust is a security weakness. It's an inescapable weakness, but one that we'll try to control and minimize in the next lab. In the meantime, let's see how Eve, our nefarious eavesdropper, might listen in on an encrypted conversation between Alice and Bob by misrepresenting which keys belong to which people. In the following class, we will go through this process in detail. It's called a man-in-the-middle attack.

Public key cryptography is a big topic. It gets used in lots of interesting ways — often in combination with hashing and secret key encryption, as we'll see. You might like to check out this overview of asymmetric/public-key encryption and how it's commonly used.

How can Alice send Bob a message in a way that assures Bob that the message came from Alice?

She used Bob's public key to encrypt the message. That way she knows only Bob who is the only one who has this private key can read it, but Alice wants Bob to know that the message came from Alice and no one else. Alice uses a hashing algorithm to make a special type of encryption of her message.

What information does Bob need to encrypt a message for Alice with RSA?

However, only Bob has the blue key that is needed to actually see Bob's mail. Thus, for Alice to send a secret message all she would have to do was encrypt it using Bob's public key, and no one would be able to decipher it except Bob. That's how RSA encryption works.

When Bob receives the encrypted message from Alice What key does he use to decrypt the message's plaintext content?

When Bob has a message he wishes to securely send to Alice, he will use Alice's Public Key to Encrypt the message. Bob will then send the encrypted message to Alice. Alice will then use her Private Key to Decrypt the message and extract the original message.

Are public and private keys interchangeable?

Some public key cryptography algorithms, including the RSA algorithm that we'll cover in some depth, have the special property of being commutative, which means that the roles of private versus public key are interchangeable.