Asymmetric encryption,
often called "public key" encryption,
allows Alice to send Bob an encrypted message without a shared secret
key; there is a secret key, but only Bob knows
what it is, and he does not share it with anyone, including Alice.
Figure 1 provides an overview of this asymmetric
encryption, which works as follows:
Bob creates a pair
of keys, one of which he keeps
secret and one of which he sends to Alice.
Alice composes a confidential message and encrypts it using the key
that Bob has sent to her.
Alice sends the encrypted data to Bob.
Bob uses his secret key to decrypt the data and reads the
confidential message.
The key that Bob sends to Alice is the public key, and the key he
keeps to himself is the "private"
key; jointly, they form Bob's "key
pair."
The most striking aspect of asymmetric encryption is that Alice is
not involved in selecting the key: Bob creates a pair of keys without
any input or agreement from Alice and simply sends her the public
key. Bob retains the private key and keeps it secret. Alice uses an
asymmetric algorithm to encrypt a message with Bob's
public key and sends him the encrypted data, which he decrypts using
the private key.
Asymmetric algorithms include a "key
generation"
protocol that Bob uses to create his
key pair, as shown by Figure 2. Following the
protocol results in the creation of a pair of keys that have a
mathematical relationship—the exact detail of the protocol and
the relationship between the keys is different for each algorithm.
When we talk about an asymmetric encryption
algorithm, we are actually
referring to two related functions that perform specific tasks: an
encryption function that encrypts a message using a public key, and a
decryption function that uses a secret key to decrypt a message
encrypted with the corresponding public key.
The encryption function can
only encrypt data. Alice cannot decrypt
ciphertext that she has created using the encryption function. This
means that Bob can send his public key to several people, and
each of them can create ciphertext that only Bob's
secret key can decrypt, as shown in Figure 3.
The one-way nature of the encryption function means that messages
created by one sender cannot be read by another (i.e., Alice cannot
decrypt the ciphertext that Anthony has created, even though they
both have Bob's public key). Bob can give out the
public key to anyone who wants to send him a message, and he can even
print his public key on his business card and hand it out to anyone
who might want to send him a message. He can add the public key to an
Internet directory of keys, allowing people Bob has never met to
create messages that only he can read.
If Bob suspects that Eve has guessed his private key, he simply
creates a new key pair and sends out the new public key to anyone who
might send him a message. This is a lot easier than arranging to meet
in a secure location to agree on a new symmetric secret key with
every person that might want to communicate with him.
Bob's pair of keys allows Alice to send him
encrypted messages, but Bob cannot use them to send a message back to
Alice because of the one-way nature of the encryption and decryption
functions. If Bob needs to send Alice a confidential message, Alice
must create her own pair of keys and send the public key to Bob, who
can then use the encryption function to create ciphertext that only
Alice can decrypt with her private key.
The main limitation of public key encryption is that it is very slow
relative to symmetric encryption and is not practical for encrypting
large amounts of data. In fact, the most common use of public key
encryption is to solve the key agreement problem for symmetric
encryption algorithms.
In the following sections, we demonstrate how an asymmetric
encryption algorithm works. We use the RSA
algorithm for our illustration because it is the only one implemented
in the .NET Framework. Ronald Rivest, Adi Shamir, and Leonard Adleman
created the RSA algorithm in 1977, and the name is the first letter
of each of the inventors' last names. The RSA
algorithm is the basis for numerous security systems, and remains the
most widely used and understood asymmetric algorithm.
1. Creating Asymmetric Keys
Most asymmetric algorithms
use keys that are very large numbers,
and the RSA algorithm is no exception. In this section, we
demonstrate the RSA key generation protocol and provide you with some
general information about the structure and usage of asymmetric keys.
We step through the RSA key generation protocol, using small test
values. The protocol is as follows:
Choose two large random prime numbers, p and
q, of equal length and multiply them together to
create n, the RSA key modulus.
Select p as 23 and q as 31,
so that the modulus, n, is:
n = p x q = 23 x 31 = 713
Randomly choose e, the public exponent, so that
e and (p -
1)(q - 1) are relatively prime.
Numbers are "relatively" prime when
they share no common factors except 1. For these test values 
select a value for
e that has no common factors with 660. Select
e as 19.
Compute the private exponent, d, where
d = e-1mod((p -
1)(q - 1)).
For our example, we calculate d as follows:
d = 19-1mod(22 x
30) = 139
The public key consists of e and
n. The private key is d.
Discard p and q, but do not
reveal their values.
You can see how simple it is to create an RSA key pair. Bob sends the
value of e (19) and n (713)
to Alice and keeps the value of d (139) secret.
Most asymmetric encryption algorithms use a similar approach to key
generation.
|
Selecting prime numbers at random is a requirement of many
different key generation protocols. It is very time-consuming to
check that a random number is truly a prime number, especially when
dealing with numbers that have hundreds of digits.
The compromise between the need for prime numbers and the need to
generate them in a reasonable time is to create numbers that are
"probably" prime, which means that
there is a small possibility that a number seems to be a prime
number, but is actually not. Probable prime numbers are subject to a
level of confidence, so that a level of 16 means that the probability
that a number is a true prime number exceeds:
Some asymmetric encryption algorithms are significantly less secure
if numbers that are supposed to be prime numbers turn out not to be,
and so care must be taken when generating numbers with a low level of
confidence. There is a balance between the confidence in a prime
number and the amount of computation that is required to attain that
confidence level.
|
