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.

Check out the
Chicken
and Egg problem solution!

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

encrypt

▶▶▶ with ▶▶▶

KEK

▶▶▶ with ▶▶▶

KEK

red key which is used
to encrypt today's
communications

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.

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.

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 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!

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:

- Alice must've sent it, because only Alice can encrypt something that decrypts properly with Alice's public key.
- 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.

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

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
arstechnica.com
overview of asymmetric/public-key encryption and how it's
commonly used.