Diffie-Hellman Encryption

Edit online

The public key scheme used in DES authentication is Diffie-Hellman with 192-bit keys. The Diffie-Hellman encryption scheme includes two constants: BASE and MODULUS.

Their values for these for the DES authentication protocol are:


const BASE = 3;
const MODULUS = "d4a0ba0250b6fd2ec626e7efd637df76c716e22d0944b88b"; /* hex */

Two programmers, A and B, can send encrypted messages to each other in the following manner. First, programmers A and B independently generate secret keys at random, which can be represented as SK(A) and SK(B). Both programmers then publish their public keys PK(A) and PK(B) in a public directory. These public keys are computed from the secret keys as follows:


PK(A) = ( BASE ** SK(A) ) mod MODULUS
PK(B) = ( BASE ** SK(B) ) mod MODULUS

The ** (double asterisk) notation represents exponentiation. Programmers A and B can both arrive at the common key, represented here as CK(A, B), without revealing their secret keys.

Programmer A computes:


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

while programmer B computes:


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

These two can be shown to be equivalent:


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

If the mod MODULUS parameter is omitted, modulo arithmetic can simplify things as follows:


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

Then, if the result of the previous computation on B replaces PK(B) and the previous computation of A replaces PK(A), the equation is:


((BASE ** SK(B)) ** SK(A) = (BASE ** SK(A)) ** SK(B)

This equation can be simplified as follows:


BASE ** (SK(A) * SK(B)) = BASE ** (SK(A) * SK(B))

This produces a common key CK(A, B). This common key is not used directly to encrypt the time stamps used in the protocol. Instead, it is used to encrypt a conversation key that is then used to encrypt the time stamps. In this way, the common key is used as little as possible to prevent it from being broken. Breaking the conversation key usually has less serious consequences because conversations are relatively shortlived.

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