Cryptography Reference
In-Depth Information
Proposition 7.1
The CDH problem on a finite cyclic group is random self-reducible.
Proof
Suppose that we have a CDH instance on
G
=
g
, where
|
G
|=
t
.This
instance is given by two elements
u
G
and to solve it we have to compute
g
(
log
g
u
)(
log
g
v
)
. To obtain the reduction, we choose uniformly at random and inde-
pendently two elements
r
,
v
∈
← Z
t
and consider the instance of the CDH problem
corresponding to the pair of elements
ug
r
,
s
vg
s
ug
r
vg
s
,
∈
G
. Observe that the pairs
(
,
)
obtained this way are uniformly distributed in
G
G
, so that we have obtained a
random instance of the problem in polynomial time. Now, if the solution for this new
instance is the element
a
×
∈
G
, the solution to the original instance is
u
−
s
v
−
r
g
−
rs
a
∈
G
.
This can easily be checked because, if we set
x
=
log
g
u
and
y
=
log
g
v
,wehave
g
(
log
g
ug
r
log
g
vg
s
)(
)
g
(
x
+
r
)(
y
+
s
)
g
xy
g
(
xs
+
ry
+
rs
)
g
xy
u
s
v
r
g
rs
. Then
that
a
=
=
=
=
we have that
u
−
s
v
−
r
g
−
rs
a
g
xy
which gives the solution to the original instance of
the problem. It is also clear that this solution can be obtained from
a
in polynomial
time (assuming, as usual, that multiplication and inverses in
G
may be efficiently
computed).
=
7.2.2 Man-in-the-Middle Attacks
The preceding discussion of the security of the DH protocol focuses on the case
of an eavesdropping adversary but one should also bear in mind the possibility of
active attacks, where the adversary sends messages to one or both of the parties. To
prevent active attacks, the messages exchanged between Alice and Bob should be
authenticated using, for example, digital signatures as we will see later on. If this is
not the case, then the DH protocol is vulnerable to a
man-in-the-middle-attack
which
can be described as follows:
•
Eve intercepts the message
g
x
that Alice sends to Bob and the message
g
y
that
Bob sends to Alice.
) and sends
g
y
to Alice
Then Eve chooses elements
x
,
y
•
∈ Z
t
(where
t
=|
G
|
and
g
x
to Bob.
At this point Alice believes that
g
y
came fromBob and Bob believes that
g
x
came
from Alice. So they both follow the DH protocol and Alice computes
k
A
=
(
•
g
y
x
)
g
x
y
.
while Bob computes
k
B
=
(
)
y
and
k
B
=
(
x
.
Eve knows
g
x
g
y
x
,
y
and so she also computes
k
A
=
(
g
x
g
y
•
,
,
)
)
•
Now Eve shares the key
k
A
with Alice and the key
k
B
with Bob, while Alice and
Bob think that they share a key with each other.
•
When Alice sends a message to Bob, Eve intercepts it, decrypts it and then
re-encrypts it (or encrypts a different message) before sending it to Bob. This
way Eve can read all messages exchanged between Alice and Bob and even alter
them if she so chooses, without Alice and Bob noticing anything.
