Cryptography Reference
In-Depth Information
> u_2 := Power(u, q) mod p;
5546540639810120079424239635047914910196610035096576508170669329311949258015541670\
94958015856638005428939669449469433911745185775251333728696879170780138915156993\
08722692378817709170089453219603920675824390456727491292259230024313128048075995\
85793016480434644761037063385737148024002457613180765260021723529345463267022162\
935580911245812
> v_2 := Power(v, q) mod p;
3427236785635535834554071403723806410581019901287930071292896099064173851612344821\
99885453097426962176646565249982654334776731685092944379916783446009722843550403\
05881058955992952522550917075719671984235527014574411529530466165388574812922643\
65588848241391058421089816511799498771432352454392331699441103310362178181282622\
112641462805445
Now, Alice and Bob don't notice anything wrong and perform the computations
established in the DH protocol to obtain the shared number
k
. Alice obtains
k
by
computing:
> k := Power(v_2, x) mod p;
1096593742937918145892898362071670579054234265509830899063001655253802633559312429\
70981982792160465888056295213439655698455878221271793328349622023667240044953929\
46517083455315842342109032130919132401957214654526012049254120035676345023718192\
79845372761554473117315398054900172310042524111423748077967296205061920884973159\
8614284230480561
Similarly, Bob obtains
k
by computing
> k := Power(u_2, y) mod p:
and, from this point on, Alice and Bob use the key
k
to exchange encrypted messages
with their favorite private-key encryption scheme. Meanwhile, in order to carry out
her attack, Eve first computes
g
2
=
g
q
, namely the group element:
> g_2 := Power(g, q) mod p;
8713470628918576585402727643895909322756033471741234314451338063757772980923094991\
79793648190327932364805855938858575504931745782327894529339482215615968896567881\
44991421755962013451806254500868888208264434467618987546702348939354317329037857\
58206781097944898050376001902031823259659629628952777961895032983011713168249643\
658418696952190
Now Eve knows
p
,
g
2
u
q
and she will use this information to
in order to discharge Maple from the burden of computing the order of
g
2
in
g
q
and
u
2
=
=
Z
p
,she
passes the order
r
to the function directly. She uses the option
BSGS
(with the rho
method, Maple may give an error because numbers that are too large for the function
Roots
are being used):
> l := PohligHellman(p, g_2, u_2, r, method = BSGS);
64413781753853186629011731261
Observe that what Eve has obtained is not quite
x
, because the logarithm of an
element to the base
g
2
is only defined modulo the order
r
of
g
2
, whereas
x
is an
integer in the range 2
1. Since
u
q
x
l
we have that
x
..
qr
−
=
(
g
2
)
=
(
g
2
)
≡
l
(
mod
r
)
and since
l
x
mod
r
. Trying to find
x
from
l
would
still be pretty much infeasible but Eve does not need to know
x
to find
k
. Since
k
<
r
we actually have that
l
=
x
mod
p
and the order of
v
2
divides
r
(it is actually equal to
r
), she knows
that also
k
=
(
v
2
)
l
mod
p
, so Eve finds
k
this way. We will not print
k
again, but we
show that this holds:
=
(
v
2
)
> evalb(Power(v_2,l) mod p = k);
true
