Introduction to Public-Key Cryptography:The Diffie–Hellman Protocol - Introduction to Cryptography with Maple - page 408

corresponds to a 530-bit safe prime. Moreover, the DDH problem is also thought to
be hard in the groups

QR p so Eve will likely not have any information that allows
her to distinguish k from a random element of

QR p .

Exercise 7.4 Maple's built-in function numtheory:-safeprime takes as input
a natural number i and generates (with high probability) the smallest safe prime
greater than i . Write a Maple procedure that uses this function to generate a safe
prime of specified length by choosing a random integer and then the safe prime
numtheory:-safeprime (

. Perform an experiment that highlights the fact that
this way of choosing safe primes is not uniform.

i )

7.2.4 Attacking the Diffie-Hellman Protocol with Maple

We have seen that the Diffie-Hellman protocol is vulnerable to “man-in-the-middle”
attacks and, in particular, to an attack of this type that allows the attacker to learn
the key that the parties share and to passively eavesdrop the messages exchanged
afterwards. A central component of this attack is the Pohlig-Hellman algorithm and,
using it, we are now going to demonstrate the attack in detail with Maple.
So, suppose that Eve is going to mount a “woman-in-the-middle” attack against
the DH protocol that Alice and Bob are using to establish their shared key. Alice and
Bob will choose a large prime p and work within the group Z p . Thus they agree to

use as modulus a 1121-bit prime p such that p 1 has a 1024-bit prime factor. This

seems to provide sufficient security because it is estimated that the discrete logarithm
problem is currently infeasible in a subgroup of

−

Z p whose order is a 1024-bit prime,

Z p , such as the index calculus algorithms
mentioned in Sect. 6.5.5 . In fact, Alice and Bob, being aware that the use of the
full group

even using powerful specific methods for

Z p

is not secure because the DDH problem is not hard in it, will use the

Z p

subgroup QR p of quadratic residues instead. This subgroup has index 2 in (in

Z p are quadratic residues) so its order is other words, exactly half of the elements of

equal to 2, which is a 1120-bit integer with a 1024-bit prime factor. Hence

Alice and Bob feel secure against a combination of Pohlig-Hellman with an index
calculus algorithm such as NFS. But Eve thinks otherwise ...
The prime that Alice and Bob are going to use is the following:
> p := 220849711986000048615500785722433535044512700235430103789980446254974133021\
461477292489017725817055785637474162300115434849858654725296350488496855039691\
322956915905600120898303906154077836085999961987701384029726747628686113935125\
733655700496960558134503861761086311917712877236967733259729722015236806428168\
52105468022493285647627940227:
This is a 1121-bit (probable) prime:
> isprime(p);
ilog2(p)+1;

( p − 1 )/

true
1121
In addition, Alice and Bob choose a generator of the group QR p . In order to

find this generator one can apply a method similar to that used in the function