Cryptography Reference
In-Depth Information
We are going to give an example of the DH protocol with Maple, using a safe
prime of realistic size. Current estimates that take into account the effectiveness of
the DLP algorithms studied in Chap.
6
suggest that the safe prime should have at
least 1024 bits.
Example 7.2
Alice and Bob want to use the DH protocol to agree on a key. We will
show how they can share a secret integer of size close to 1024 bits from which a
secret key such as, for example, an AES key, can be derived.
First, Alice and Bob have to agree on a safe prime
p
and a generator
g
of the
group
QR
p
of quadratic residues modulo
p
. They want a 1024-bit prime and they
will use the one in Example 6.7 (we do not print it to save space):
> p := PseudoRandomSafePrime(294779833764425581873162947825807970808, 1024):
A check that
p
is indeed (very probably) a safe prime of the form
p
=
2
q
+
1
with
q
also prime and that
p
has 1024 bits is the following:
> q := (p-1)/2:
isprime
∼
([p, q]);
ilog2(p)+1;
[true, true]
1024
To complete the previous setup for the DH protocol, Alice and Bob must also
agree on a generator of
Z
p
, which is found by
taking a pseudo-random element of the latter group and squaring it. They choose an
integer in the range 0
QR
p
, i.e., an element of order
q
of
2
1024
and, after checking that it is less than
p
..
−
1, they square
it modulo
p
to obtain the generator
g
:
> with(RandomTools:-BlumBlumShub):
BG := NewBitGenerator(279804548445444154496400548857816873066,
numbits = 1024, output = integer):
> h := BG():
evalb(h < p-1);
true
> g := hˆ2 mod p;
1450173935555822106709369719335212069719191005254827087741500466003182492175155345\
29158619254011275924886195136639928354611756421750921112915513729227452396966579\
11973701153921856873632070033620717694570204542600860102469425822689202721234806\
8428227760707731430240736041178430018867013774664644720409345383696
An alternative way to find a generator of
QR
p
would be to just pick elements at
Z
p
until one is found which is different from 1 and has Legendre symbol
equal to 1. We already know that this is the case for g (because it is a square):
random in
> numtheory:-legendre(g, p);
1
Alice and Bob agree on using
p
(which determines the group) and
g
, and this
information can be exchanged through the public channel. Now Alice chooses at
random an element of
Z
q
that she will use as exponent. In fact, she will settle by
choosing it pseudo-randomly using Blum-Blum-Shub and a 128-bit random seed.
She will choose an integer
x
of 1023 bits or less (since
q
has 1023 bits) and she will
check that
x
1; if this turns out not to be the case she chooses another integer
until one is found that satisfies this condition:
<
q
−
