Cryptography Reference
In-Depth Information
and realizes that when Alice and Bob exchange through the public channel elements
u
g
y
(where
x
and
y
are unknown to
Eve),
1
she can raise both equations to the
q
th power and convert them to equations
in the subgroup of
g
x
and
v
∈
QR
p
,
v
∈
QR
p
such that
u
=
=
QR
p
generated by
g
q
which, according to Proposition 2.5, has
order
qr
r
. Since
r
is a product of small primes, the resulting discrete logarithm
problems will be easily vulnerable to a Pohlig-Hellman attack.
Next, with the notation used in Sect.
7.3
Alice chooses the integer
x
pseudo-
randomly in the range 2
/
q
=
g
x
:
> x := 478102462533983344003559675456410402993169493474887722228457198981799310031\
879420761110285218224033878299885643799471218472532582760252177313118997079166\
758249500299842531774844881554793294171659848884903967641304732277437661170389\
297898752269846239128420448010914228685743560524141112767221785073287929428204\
1096744317363795748457800998:
..
qr
−
1 and computes
u
=
> u := Power(g, x) mod p:
Before sending
u
to Bob over the public channel, Alice makes sure that
u
does
not have low order for, otherwise, an eavesdropper could solve the DLP problem in
a small group. The probability that the order of
u
is not a multiple of
q
(and hence
≤
r
) is very small, but Alice checks it out nonetheless. By Proposition 2.5, the order
of
u
is equal to
qr
/
gcd
(
x
,
qr
)
and she checks that this value is, in fact, equal to
qr
(or that gcd
(
x
,
qr
)
=
1):
> evalb(q*r/igcd(q*r, x) = q*r);
true
Alice then sends
u
to Bob over the public channel. Similarly, Bob chooses
y
and
sends
v
g
y
to Alice after checking that the order of
v
is also
qr
:
> y := 110207575942943043852713079114598597108824655307581744725008817858659047435\
901458788248026977143468995548827892373152994470026855147783295754547025855865\
202889811994814529899263851564268492873363736444126778931211861494711726742873\
356688199423479205816599143927296681758794337258749327459177835270354124070320\
41987493033050828314340624458:
=
> v := Power(g, y) mod p:
> igcd(q*r, y);
1
Eve knows that computing log
g
u
or log
g
v
is infeasible as the group generated by
g
has order
qr
. But she knows the factorization of
p
1 and she also knows that by
raising
u
to the
q
th power, the problem of computing log
g
u
is in some sense reduced
to the problem of computing log
g
q
u
q
. As already mentioned,
g
q
has order
r
, which
is a product of small primes, and hence computing log
g
q
u
q
is feasible using Pohlig-
Hellman combined with a generic method such as BSGS. Thus Eve intercepts both
u
and
v
and replaces them by
u
2
−
v
q
, respectively, sending the first
to Bob, who thinks it came from Alice, and the second to Alice, who thinks it came
from Bob. The group elements sent by Eve are:
u
q
and
v
2
=
=
1
Here and in what follows we use the generic notation to indicate an exponentiation in the group
Z
p
but if we want to be specific and the elements of the group are viewed as integers, then this is
really
u
g
x
mod
p
.
=