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 .
=
 
Search WWH ::




Custom Search