Diffie-Hellman Encryption

In this scheme, there are two constants, PROOT and HEXMODULUS. The particular values chosen for these for the DES authentication protocol are:

const PROOT = 3;
const HEXMODULUS =	/* hex */
 "d4a0ba0250b6fd2ec626e7efd637df76c716e22d0944b88b";

The way this scheme works is best explained by an example. Suppose there are two people "A" and "B" who want to send encrypted messages to each other. A and B each generate a random secret key that they do not disclose to anyone. Let these keys be represented as SK(A) and SK(B). They also publish in a public directory their public keys. These keys are computed as follows:

PK(A) = (PROOT ** SK(A)) mod HEXMODULUS
PK(B) = (PROOT ** SK(B)) mod HEXMODULUS

The ** notation is used here to represent exponentiation.

Now, both A and B can arrive at the common key between them, represented here as CK(A,B), without disclosing their secret keys.

A computes:

CK(A, B) = (PK(B) ** SK(A)) mod HEXMODULUS

while B computes:

CK(A, B) = (PK(A) ** SK(B)) mod HEXMODULUS

These two can be shown to be equivalent: (PK(B)**SK(A)) mod HEXMODULUS = (PK(A)**SK(B)) mod HEXMODULUS. Drop the mod HEXMODULUS parts and assume modulo arithmetic to simplify the process:

PK(B) ** SK(A) = PK(A) ** SK(B)

Then replace PK(B) by what B computed earlier and likewise for PK(A).

((PROOT ** SK(B)) ** SK(A) = (PROOT ** SK(A)) ** SK(B)

which leads to:

PROOT ** (SK(A) * SK(B)) = PROOT ** (SK(A) * SK(B))

This common key CK(A,B) is not used to encrypt the timestamps used in the protocol. It is used only to encrypt a conversation key that is then used to encrypt the timestamps. The reason for doing this is to use the common key as little as possible, for fear that it could be broken. Breaking the conversation key is a far less serious offense, because conversations are comparatively short-lived.

The conversation key is encrypted using 56-bit DES keys, yet the common key is 192 bits. To reduce the number of bits, 56 bits are selected from the common key as follows. The middle-most 8 bytes are selected from the common key, and then parity is added to the lower order bit of each byte, producing a 56-bit key with 8 bits of parity.