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

P k ( p 1) 1

(Since ed 1 (mod p 1), ed = k ( p 1) + 1 for some integer k .)

( P p 1 ) k P

1 k P

(Here is where FLT comes in.)

P (mod p ).
Note that the conditions in the hypothesis of Fermat's Little Theorem are satisfied; that
is, p is prime and does not divide P , a nonnegative integer less than p .

14.4 WEAKNESSES OF THE POHLIG-HELLMAN CIPHER

Suppose we are using Pohlig-Hellman and manage to get our hands on the plaintext P asso-
ciated with some ciphertext C . Finding the encryption key e then means solving the con-
gruence

C P e (mod p )
for e . This is an exponential congruence, and as we know, these are quite difficult to solve.
Thus, when using this cipher, even if we obtain some plaintext knowing that it corresponds
to certain ciphertext, it still does not help us in cracking the cipher. Hence, the Pohlig-Hell-
man cipher is resistant even to a known plaintext attack. It is very important that a cipher
not be vulnerable to such an attack, since it is considered too great a security risk. This
exponentiation cipher is quite resistant to cryptanalysis, provided the proper precautions
are taken. We list some of the potential weaknesses of this cipher.

Inadequate Block Size The block size (and thus the prime modulus p ) must be cho-
sen large enough; say greater than 500 decimal digits for the prime p .

Weak Primes The quantity p 1 should have at least one large prime factor, otherwise
p could be vulnerable to certain discrete log finding algorithms.

Low Order Messages modulo Since we encrypt with Pohlig-Hellman using the

p

transformation

C P e (mod p ),

the plaintext message may not be a generator modulo p , and in fact may have low order. This
makes the discrete logarithm problem easier to solve. Some method must be employed to
ensure the message is of high order modulo p ; perhaps by judicious use of salt. Note finally
that Pohlig-Hellman is a secret key cipher. Divulging the encryption key e to anyone is the
same as handing them the decryption key d, since finding it merely means solving the con-
gruence ed 1 (mod p 1) for d , which is very easily done.

Memoryless Cipher Pohlig-Hellman is a static cipher. That is, it always maps a par-
ticular plaintext block to the same ciphertext block. We discussed CBC earlier to cope with