Cryptography Reference
In-Depth Information
> BA := NewBitGenerator(198668606742102093450006022245851260905,
numbits = 1023, output = integer):
> x := BA();
3643057828008536321618059789049351954101526396296701497885630167462426003983501005\
26344087230618848312296820273171583278986620474290982693535407941122963256991600\
14674567985097618913200285042709893102585598603050926789141813273635482363218167\
913800888478068684904318274980204118455155665997418127639788413412
> evalb(x < q-1);
true
g
x
∈
QR
p
and sends it to Bob through the public
channel. This element is obtained below but we do not print it:
Then Alice computes
u
=
> u := Power(g, x) mod p:
Similarly, Bob chooses a random (or, rather, pseudo-random in this case)
y
∈ Z
q
,
g
y
computes
v
∈
QR
p
and sends this element to Alice (again, we do not print
v
in order to save space):
> BB := NewBitGenerator(302161507654569763504767421009617402763,
numbits = 1023, output = integer):
=
> y := BB();
2719572573092285394726145843960706748498199703735491492919328770821846888012960535\
40521405141674641253919327924090569790170783923031962779251734546447113929321574\
75914233262293694521107857970533065864670883914490241428522287292324141483346046\
068297947540353250235715294437776422169804829292077951399566979773
> evalb(y < q-1);
true
> v := Power(g, y) mod p:
Now both Alice and Bob have the information necessary to compute the key
k
they are going to share. Bob computes:
> k := Power(u, y) mod p;
4490487731305085052430441099514943913122263466394205778464075743588941346343827822\
28272057961841982111040707032452446034256872738930165691435572289242566174659133\
71068787919199266418278126095941497322286370391757334334268318786873857504238324\
103742048047270263709831203146386081644955581637071123001523188989
Alice computes:
> k := Power(v, x) mod p;
4490487731305085052430441099514943913122263466394205778464075743588941346343827822\
28272057961841982111040707032452446034256872738930165691435572289242566174659133\
71068787919199266418278126095941497322286370391757334334268318786873857504238324\
103742048047270263709831203146386081644955581637071123001523188989
Alice and Bob now share the same element
k
∈
QR
p
, whose length is 1022 bits:
> ilog2(k)+1;
1022
Even knowing
u
and
v
,
k
appears to be hard to distinguish from a random element
of
QR
p
but what Alice and Bob require is, say, a 128-bit key. To obtain it from
k
they should apply a
Key Derivation Function
(KDF) as discussed, for example, in
[10] to which we refer for details.
Now, as mentioned before, if Eve observes the entire exchange and knows
p
,
g
,
u
, and
v
, the best passive attack she has to recover
k
seems to be to solve the
discrete logarithm in
QR
p
and to compute
x
from the relation
g
x
mod
p
u
(or,
similarly, to compute
y
). This is thought to be infeasible with our present knowledge
=
Z
p
