 |
Unlike symmetric cryptography, public key cryptography uses two different keys -
one public and one private. The keys are mathematically related, yet
it is computationally infeasible to deduce one from the other. Anyone with
the public key can encrypt a message but not decrypt it. Only
the person with the private key can decrypt the message.
Bruce Schneier compares public-key cryptography with a mailbox. He writes:
"Putting mail in the mailbox is analogous to encrypting with the public key;
anyone can do it. Just open the slot and drop it in. Getting mail out of a mailbox
is analogous to decrypting with the private key. Generally it's hard; you need welding torches.
However, if you have the secret (the physical key to the mailbox), it's easy to get
mail out of a mailbox." [1]
Using public-key cryptography, Alice and Bob can communicate
securely using the following simple protocol:
- Alice and Bob agree on a public key algorithm.
- Bob sends Alice his public key.
- Alice encrypts her message with Bob's public key and sends it to Bob.
- Bob decrypts Alice's message with his private key.
Notice that this protocol does not require any prior arrangements (such
as agreeing on a key) for Alice and Bob to communicate securely.
In real-world implementations, public keys are rarely used to encrypt
actual messages as public-key cryptography is very slow,
about 1000 times slower that conventional cryptography [1]. Instead,
public-key cryptography is used to distribute symmetric keys which are then used
to encrypt and decrypt actual messages, as follows:
- Bob sends Alice his public key.
- Alice generates a random symmetric key (usually called a session key), encrypts it with Bob's
public key and sends it to Bob.
- Bob decrypts the session key with his private key.
- Alice and Bob exchange messages using the session key.
Systems that use both symmetric and public-key cryptography
in this manner are called hybrid.
Certain public-key algorithms such as RSA allow
both the public and private key to be used for encryption. If a message
is encrypted with someone's private key it can
only be decrypted with the corresponding public key.
This feature can be used to create digital signatures, as follows:
- Alice encrypts the document with her private key. The encrypted
document becomes her digital signature.
- Alice sends the signature to Bob.
- Bob decrypts the document with Alice's public key thereby verifying
the signature.
Once again, encrypting an actual message with a private key is very inefficient.
Instead of signing the entire document, the document's hash can be signed,
as follows:
- Alice computes a one-way hash of a document.
- Alice encrypts the hash with her private key. The encrypted
hash becomes the document's signature.
- Alice sends the document along with the signature to Bob.
- Bob produces a one-way hash function of the document received from
Alice, decrypts the signature with Alice's public key and compares the two values.
If they match, Bob knows that: (1) the document really came from Alice and (2) the document
was not tampered with during transmission.
RSA is by far the most popular public-key cryptography algorithm.
It supports both encryption and digital signatures. It is also the easiest
one to describe and implement. RSA has withstood years of
extensive cryptoanalysis and is a de facto standard in much of the World [1].
RSA is named after the three inventors - Ron Rivest,
Adi Shamir and Leonard Adleman.
In RSA, a public key is based on the product of two large prime numbers. These two
numbers must be kept secret as they are used to compute the private key.
The product of the two prime numbers is referred to as modulus.
The security of RSA lies in the difficulty of factoring large numbers.
The Microsoft Base Cryptographic Provider implements RSA with a 512-bit
modulus. With the Microsoft Enhanced and Strong Providers, the default modulus
is 1024 bits, and valid moduli can be in the range of 384 bits to 16,384 bits in 8 bit increments.
The hybrid communication protocol described above is vulnerable to a man-in-the-middle
attack. Let's assume that Mallory, an enemy hacker, not only can listen to
the traffic between Alice and Bob, but also can modify, delete, and substitute
Alice's and Bob's messages, as well as introduce new ones.
Mallory can impersonate Alice when talking to Bob and impersonate Bob
when talking to Alice. Here is how the attack goes:
- Bob sends Alice his public key. Mallory intercepts the key and sends his
own public key to Alice.
- Alice generates a random session key, encrypts it with "Bob"'s public
key (which is really Mallory's) and sends it to Bob.
- Mallory intercepts the message. He decrypts the session key
with his private key, encrypts it with Bob's public key and sends it to Bob.
- Bob receives the message thinking it came from Alice. He decrypts it
with his private key and obtains the session key.
- Alice and Bob start exchanging messages using the session key. Mallory,
who also has that key, can now read the entire conversation.
A man-in-the-middle attack works because Alice and Bob have no way
to verify they are talking to each other. An independent
third party that everyone trusts is needed to foil the attack.
This third party could bundle the name "Bob"
with Bob's public key and sign the package with its own private key.
When Alice receives the signed public key from Bob, she can verify
the third party's signature. This way she knows that the public key
really belongs to Bob, and not Mallory.
A signed package containing a person's name (and possibly some other information
such as an email address and company name) and his/her public key is called
a digital certificate (or digital ID). An independent third party that everyone
trusts whose responsibility is to issue certificates is called a
Certification Authority (CA). Digital certificates are the topic of the
next chapter.
|
|
|
|
|
