Cryptography Reference
In-Depth Information
Example 4.2
Let
p
= 167
, and set
e
=69
, with plaintext
12
,
4
,
18
,
0
,
6
.Then
we encipher each by exponentiating as follows, where all congruences are modulo
167
.
12
69
85; 4
69
50; 18
69
96; 0
69
0; 6
69
27
.
Then we send off the ciphertext.To decipher, we need the inverse of
e
modulo
166 =
p
≡
≡
≡
≡
≡
1
, and this is achieved by using the Euclidean algorithm
(
see Theorem
A.3 on page 470
)
to solve
−
69
d
+ 166
x
=1
,
which has a solution
d
=77
for
x
=
−
32
, and this is the least positive such value
of
d
.So we may decipher via,
85
77
≡
12
and so on to retrieve the plaintext.
Analysis
Since knowledge of
e
and
p
would allow a cryptanalyst to obtain
d
, then
both
p
and
e
must be kept secret. The security of this cipher is based on the
di8culty of solving the DLP, namely, an adversary, without knowledge of
e
or
d
, would have to compute
e
≡
log
m
(
c
) (mod
p
−
1).
The Pohlig-Hellman cipher is an example of the use of
fixed-exponent ex-
ponentiation
where the base may vary but the exponent is fixed. The next
algorithm, which we mentioned briefly on page 99, is an example of the use of
fixed-base exponentiation
where the exponent may vary but the base is fixed.
This algorithm is a prime motivator for PKC, and its security depends upon
the DLP.
The Di$e-Hellman Key Exchange Protocol
Suppose that Alice and Bob have not yet met nor exchanged keys, but
they want to establish a shared secret key
k
by exchanging messages over an
unsecured channel. First Alice and Bob agree on a large prime
p
and a generator
α
of
F
p
(2
2). These need not be kept secret, so Alice and Bob can
agree over an unsecured channel. Then the protocol proceeds as follows.
≤
α
≤
p
−
(1) Alice chooses a random (large)
x
and computes the least positive
residue
X
of
α
x
modulo
p
, then sends
X
to Bob (and keeps
x
secret).
∈
N
(2) Bob chooses a random (large)
y
and computes the least positive
residue
Y
of
α
y
modulo
p
, then sends
Y
to Alice (and keeps
y
secret).
∈
N
(3) Alice computes the least positive residue of
Y
x
modulo
p
, and Bob com-
putes the least positive residue of
X
y
modulo
p
. Since
Y
x
α
yx
α
xy
X
y
≡
≡
≡
≡
k
(mod
p
)
,
they have a shared secret key
k
.
Search WWH ::
Custom Search