Cryptography Reference
In-Depth Information
QR
p
may be obtained by squaring such a primitive root modulo
p
, but Alice (or Bob) can also use the following Maple function that chooses ele-
ments of
QR
p
pseudo-randomly and checks whether they are generators by means
of Proposition 2.6 (in contrast with the case when
p
is a safe prime, this is necessary
here since the order of
QR
p
is not prime).
> findqrgenerator := proc(p)
uses RandomTools:-MersenneTwister;
local n, primefactors, found, g;
SetState();
n := iquo(p-1, 2);
primefactors := [seq(x[1], 'in'(x, ifactors(n, 'pollard')[2]))];
found := false;
while not found do
g := GenerateInteger(range = 2 .. p-1)ˆ2 mod p;
found := andmap(x -> x<>1, [seq(Power(g, iquo(n,i)) mod p, i in primefactors)])
end do;
g;
end proc:
The generator of
QR
p
shared by Alice and Bob is then:
> g := findqrgenerator(p);
4006139267833019314263281087196655148600498727889017421538173530051744588908252626\
56934581865202674817386049580900176924684939078071816502463941738188627254776808\
26253412965225290392357111896467686644247208709573914070598773738658180540949332\
88322290369402817649171337284783695401285795169124110784836378348660138163557353\
50984814997013
Eve observes
p
and
g
and suspects that
p
1 has a large prime factor and hence
it should be easy to factor with the rho method, because all its prime factors except
the largest one should be small (note that, if
p
is chosen at random subject to the
condition that
p
−
1 has a large prime factor
q
, it is likely that the cofactor of
q
is a product of relatively small primes). Thus she uses the rho method embodied
in Maple's
ifactor
with the option
'pollard'
(a good alternative would be
the Elliptic Curve Method, which is the option
'lenstra'
of
ifactor
). The
factorization of
p
−
−
1 also tells Eve that
p
is not a safe prime:
> ifactor(p-1, 'pollard');
(2)(3)(13)(10740895172706974336835790232145029570183055562678907163274057642810\
10474564285224138802516233522861623662835287092605143143520618045567592051213003\
02317619055051753810948058681230600944442783772186964499655858154770852745807823\
36154463865135778340978000462384573554579349222720520095416182644216485243538671\
9) (56526273169) (71729243) (650152379)
Eve sees that
p
2
qr
, where
> q:= 107408951727069743368357902321450295701830555626789071632740576428101047456\
428522413880251623352286162366283528709260514314352061804556759205121300302317\
619055051753810948058681230600944442783772186964499655858154770852745807823361\
544638651357783409780004623845735545793492227205200954161826442164852435386719:
−
1
=
> r := 3*13*71729243*650152379*56526273169:
> ilog2(q)+1;
1024
q
is a 1024-bit prime and
r
is a product of small primes, the largest of which has 11
decimal digits. Thus
|
QR
p
|=
(
p
−
1
)/
2
=
qr
and, by Corollary 2.1, the order of
an element of
QR
p
is a divisor of
qr
and hence either a multiple of
q
or a divisor of
r
. Eve checks that
g
has order
qr
=|
QR
p
|
QR
p
)
(so that
g
is really a generator of
