Public-Key Cryptography

The author recently watched a TV show called La Femme Nikita about a woman named Nikita who is forced to be an agent for a shady anti-terrorist organization called Section One. Nikita has strong feelings for fellow agent Michael, and she most trusts Walter, Section One's ex-biker gadgets and explosives expert. Often Nikita's worst enemies are her superiors and coworkers at Section One.

A synopsis for a season three episode is as follows:

PLAYING WITH FIRE

On a mission to secure detonation chips from a terrorist organization's heavily armed base camp, Nikita is captured as a hostage by the enemy. Or so it is made to look. Michael and Nikita have actually created the scenario in order to secretly rendezvous with each other. The ruse works, but when Birkoff [Section One's master hacker] accidentally discovers encrypted messages between Michael and Nikita sent with Walter's help, Birkoff is forced to tell Madeline. Suspecting that Michael and Nikita may be planning a coup d'état, Operations and Madeline use a second team of operatives to track Michael and Nikita's next secret rendezvous... killing them if necessary.

What sort of encryption might Walter have helped them to use? I let my imagination run free, and this is what I came up with. After being captured at the base camp, Nikita is given a phone by her captors, in hopes that she'll use it and they'll be able to figure out what she is really up to. Everyone is eagerly listening in on her calls.

Remark 3. 0   In this book we will assume available a method for producing random integers. Methods for generating random integers are involved and interesting, but we will not discuss them in this book. For an in depth treatment of random numbers, see [#!knuth2!#, Ch. 3].

Nikita remembers a conversation with Walter about a public-key cryptosystem called the ``Diffie-Hellman key exchange''. She remembers that it allows two people to agree on a secret key in the presence of eavesdroppers. Moreover, Walter mentioned that though Diffie-Hellman was the first ever public-key exchange system, it is still in common use today (e.g., in OpenSSH protocol version 2, see http://www.openssh.com/).

Figure 3.1: Diffie and Hellman (photos from [#!singh:crypto!#])

$\qquad$

Nikita pulls out her handheld computer and phone, calls up Michael, and they do the following, which is wrong (try to figure out what is wrong as you read it).

1. Together they choose a big prime number $p$ and a number $g$ with $1<g<p$ .
2. Nikita secretly chooses an integer $n$ .
3. Michael secretly chooses an integer $m$ .
4. Nikita tells Michael $ng \pmod{p}$ .
5. Michael tells $mg\pmod{p}$ to Nikita.
6. The ``secret key'' is $s=nmg\pmod{p}$ , which both Nikita and Michael can easily compute.

Here's a very simple example with small numbers that illustrates what Michael and Nikita do. (They really used much larger numbers.)

1. $p=97$ , $g=5$
2. $n=31$
3. $m=95$
4. $ng\equiv 58\pmod{97}$
5. $mg \equiv 87\pmod{97}$
6. $s = nmg = 78\pmod{97}$

Nikita and Michael are foiled because everyone easily figures out $s$ :

1. Everyone knows $p$ , $g$ , $ng \pmod{p}$ , and $mg\pmod{p}$ .
2. Using Algorithm 2.3.7, anyone can easily find $a, b\in \mathbb {Z}$ such that $ag + bp = 1$ , which exist because $\gcd(g,p)=1$ .
3. Then $ang \equiv n\pmod{p}$ , so everyone knows Nikita's secret key $n$ , and hence can easily compute the shared secret $s$ .

To taunt her, Nikita's captors give her a paragraph from a review of Diffie and Hellman's 1976 paper ``New Directions in Cryptography'' [#!dh76!#]:

``The authors discuss some recent results in communications theory [...] The first [method] has the feature that an unauthorized `eavesdropper' will find it computationally infeasible to decipher the message [...] They propose a couple of techniques for implementing the system, but the reviewer was unconvinced.''