Exponential Ciphers - Introduction to Cryptography with Java Applets - page 259

14.2

WEAKNESSES OF DIFFIE-HELLMAN
Why is this secure? Note that even if a third party is listening, and hears all of the follow-
ing transmissions, he will know the value of g , p , g x , and g y . Is this enough to compute the
K value? No! In order to compute K , the eavesdropper must do either of two things:
• Raise g x to the y power (mod p ), which he cannot do because he does not know y , or
• Raise g y to the x power (mod p ), which he cannot do because he does not know x .
Note that though the eavesdropper does not know x or y , he does know g x and g y . How
easy is it to obtain x , for example, if you know what g x is? Nearly impossible! This is, of
course, the discrete logarithm problem, and it means solving a congruence of the form
z g x (mod p )
for x . We know this problem is intractable when the modulus p is large, and when g is a gen-
erator modulo p . Thus, anyone using DFH with confidence in the difficulty of the discrete
logarithm problem can generate as many keys as desired and use them with other cryp-
tosystems.
Later we will see a Diffie-Hellman Key Exchange. To do this, we will need to cover
some of the Java networking classes, so I've saved this topic for the upcoming chapter,
Establishing Keys and Message Exchange.

14.3 THE POHLIG-HELLMAN EXPONENTIATION CIPHER

This cipher is based on Fermat's Little Theorem (FLT), and is called the Pohlig-Hellman
exponentiation cipher. Let p be a large safe prime, and let e be some integer relatively prime
to p 1. At current levels of computing power, p should be at least 1024 bits in length. Our

plaintext message P is a nonnegative integer less than p . The enciphering transformation is
C P e (mod p ), 0 ≤ P < p , 0 ≤ C < p .

To decrypt, we must first find an inverse of e modulo p 1, call it d . We know this

inverse exists because e is relatively prime to p 1; thus, d must satisfy the congruence

ed 1 (mod p 1).
This congruence has a unique solution for d modulo p 1 and is easily solved using the
extended Euclidean algorithm. Once d is calculated, one may decrypt in the following way:
P C d (mod p ).
Why does this work? Why does raising the ciphertext to the d power recover the plain-
text? If we recall Fermat's Little Theorem, it is easy to show why:

C d

( P e ) d
P ed