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
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.
Distributing secret keys to aircraft in flight
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
▶▶▶ with ▶▶▶
red key which is used
to encrypt today's
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
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:
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!
Suppose Alice sends a contract agreement to Bob. To avoid legal
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:
- 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 does crypto.
Your CAC supports a number of different cryptographic
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.
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
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