Page 323 - Discrete Mathematics and Its Applications

302 4 / Number Theory and Cryptography

it will be necessary to use larger primes to ensure secrecy of messages. Unfortunately, messages
that were considered secure earlier can be saved and subsequently decrypted by unintended
recipients when it becomes feasible to factor the n = pq in the key used for RSA encryption.
The RSA method is now widely used. However, the most commonly used cryptosystems
are private key cryptosystems. The use of public key cryptography, via the RSA system, is
growing. Nevertheless, there are applications that use both private key and public key systems.
For example, a public key cryptosystem, such as RSA, can be used to distribute private keys
to pairs of individuals when they wish to communicate. These people then use a private key
system for encryption and decryption of messages.

Cryptographic Protocols

So far we have shown how cryptography can be used to make messages secure. However,
there are many other important applications of cryptography. Among these applications are
cryptographic protocols, which are exchanges of messages carried out by two or more parties
to achieve a particular security goal. In particular, we will show how cryptography can be used
to allow two people to exchange a secret key over an insecure communication channel. We will
also show how cryptography can be used to send signed secret messages so that the recipient
can be sure that the message came from the purported sender. We refer the reader to [St05] for
thorough discussions of a variety of cryptographic protocols.

KEY EXCHANGE We now discuss a protocol that two parties can use to exchange a secret
key over an insecure communications channel without having shared any information in the
past. Generating a key that two parties can share is important for many applications of cryp-
tography. For example, for two people to send secure messages to each other using a private
key cryptosystem they need to share a common key. The protocol we will describe is known as
the Diffie-Hellman key agreement protocol, after Whitfield Diffie and Martin Hellman, who
described it in 1976. However, this protocol was invented in 1974 by Malcolm Williamson in
secret work at the British GCHQ. It was not until 1997 that his discovery was made public.

Suppose that Alice and Bob want to share a common key. The protocol follows these steps,
where the computations are done in Z p .

(1) Alice and Bob agree to use a prime p and a primitive root a of p.
k 1
(2) Alice chooses a secret integer k 1 and sends a mod p to Bob.
k 2
(3) Bob chooses a secret integer k 2 and sends a mod p to Alice.
k 2 k 1
(4) Alice computes (a ) mod p.
(5) Bob computes (a ) mod p.
k 1 k 2
At the end of this protocol, Alice and Bob have computed their shared key, namely

(a ) mod p = (a ) mod p.
k 2 k 1
k 1 k 2
To analyze the security of this protocol, note that the messages sent in steps (1), (2), and
(3) are not assumed to be sent securely. We can even assume that these communications were
k 1
k 2
in the clear and that their contents are public information. So, p, a, a mod p, and a mod p
are assumed to be public information. The protocol ensures that k 1 , k 2 , and the common key
(a ) mod p = (a ) mod p are kept secret. To find the secret information from this pub-
k 1 k 2
k 2 k 1
lic information requires that an adversary solves instances of the discrete logarithm problem,