Cryptography Reference
In-Depth Information
1). If
p is “properly chosen”, this is a very di8cult problem to solve. One of the ways
that p has to be properly chosen is to insist upon p
The DLP is often called simply discrete log . Here e
log m ( c ) (mod p
1 having at least one large
prime factor. This is due to the Silver-Pohlig-Hellman algorithm, which allows
for e8cient calculation of discrete logs when p
1 has only small prime factors.
Due to the technical nature of the algorithm, we have placed a description of it
in Appendix D on page 530.
It can be shown that the complexity of finding e in (4.2) when p has n digits
is roughly the same as factoring an n -digit number (for instance, see [183]).
Therefore, computing discrete logs is virtually of the same degree of di8culty
as factoring, and since there are no known tractable factoring algorithms, we
assume that the integer factoring problem (IFP) is intrinsically di8cult (see
page 509). Hence, cryptosystems based upon the discrete log problem are as-
sumed to be secure. Yet, there is no verification of this abstractly in the sense
that no nontrivial lower bounds have been found for the complexity of integer
factorization. (See the discussion of complexity on pages 500-505 in Appendix
A.)
A symmetric-key cipher whose security depends upon the discrete log prob-
lem is our next topic. It involves the name of a contributor whom we will see
often; a brief discussion of his achievements follows.
Martin E. Hellman was born on October 2, 1945. He obtained all his aca-
demic degrees in electrical engineering: his bachelor's degree from New York
University in 1966; his master's degree in 1967; and his Ph.D. in 1969, the lat-
ter two from Stanford. He was employed at IBM and at MIT, but returned
to Stanford in 1971. He remained there until 1996, when he received his Pro-
fessor Emeritus status. We already learned on page 99 that he was one of the
pioneers of PKC. He has been involved in computer privacy issues going back
to the debate over the DES keylength in 1975 (see Levy's topic [151] for some
background to this fascinating story). He has not only demonstrated his schol-
arship with numerous publications, but also has excelled in teaching. He was
recognized with four teaching awards; three of these were from minority-student
organizations. He is now retired from research and teaching. He and Dorothie,
his wife of some 35 years, live on campus at Stanford.
Now it is time for us to go back to symmetric-key cryptography (SKC) and
learn about an exponentiation cipher that will help us to set the stage for PKC
in general and RSA in particular.
The Pohlig-Hellman Symmetric-Key Exponentiation Cipher
(a) A secret prime p is chosen and a secret enciphering key e
N
with e
p
2.
(b) A secret deciphering key d is computed via ed
1 (mod p
1).
m e (mod p ) .
(c) Encryption of plaintext message units m is: c
c d (mod p ).
(d) Decryption is achieved via m
Search WWH ::




Custom Search