Cryptography Reference
In-Depth Information
CHAPTER
14
Exponential Ciphers
In the last chapter, we discussed how to solve congruences of the form
a
x
b
(mod
p
)
for
x
, where
a
and
b
are known, and
p
is prime. Cryptosystems based on exponential con-
gruences can be quite difficult to crack. We will consider such ciphers now.
14.1
DIFFIE-HELLMAN KEY EXCHANGE
The first public key scheme was invented by Diffie and Hellman. Though it could not be
used to send messages, it could establish secret keys for use in secret key cryptosystems. An
eavesdropper “tapping the line” would be unable to determine what the generated key was.
The steps to Diffie-Hellman (DFH) are as follows:
1.
Two users agree on using a large prime
p
, and
g
, a generator modulo
p
. At current lev-
els of computing power,
p
should be at least 1024 bits in length. It doesn't matter if a third
party hears this exchange and knows these numbers
g
and
p
.
2.
Next, user 1 chooses a private number, say
x
. User 2 chooses his own secret number, say
y
.
User 1 then calculates
g
x
(mod
p
) and sends this quantity to User 2. User 2 similarly
computes
g
y
(mod
p
) and sends this to User 1.
3.
4.
User 1 then takes the value received from User 2 and raises it to his
x
power, and User
2 likewise computes the value received from User 1 to his
y
power. Thus, they both com-
pute
K
(
g
y
)
x
(mod
p
). This value
K
can then be used as a key in subse-
quent secret key sessions.
(
g
x
)
y
g
xy
Search WWH ::
Custom Search