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

minimal requirement is that the discrete logarithm problem should be hard in G
and, taking into account the Pohlig-Hellman algorithm, this excludes cyclic groups
whose orders are products of powers of small primes. Hence an obvious possibility
is to use groups of (suitably large) prime order. These groups have the additional
advantage that finding a generator is very easy because any element 1 has this

property. Elliptic curve groups of prime order, which we study in Chap. 11 , are very
interesting in this regard because the discrete logarithm in these groups is thought to
be especially difficult.
Another class of groups where the discrete logarithm problem is believed to be
hard is given by the groups

=

Z p , where p is a prime; more specifically, it is conjectured
that the discrete logarithm problem is hard relative to an algorithm that, on input 1 n ,
chooses a random n -bit prime p and a generator g of Z p . But this does not mean

Z p are suitable for implementation of the DH protocol. One minor
disadvantage is the fact that the order of these groups p

that the groups

1 is not prime and, in
addition to the factor 2, it may have other small prime factors and hence subgroups
in which the discrete logarithm problem is not hard. But there is a much more serious
problem: as we have seen in Example 7.1, the DDH problem is easy in these groups
and hence the DH protocol is automatically insecure. As we shall see later, this also
implies that these groups are also inadequate for other cryptographic applications
whose security relies on the hardness of the DDH problem.
The DDH problem is easy in

−

Z p because some of the elements of this group are
squares and some are non-squares, and they can easily be distinguished by computing
Legendre symbols. Thus a natural idea is to consider only the squares, i.e., the
quadratic residues modulo p which, as can easily be checked, form a subgroup of
Z p . Moreover, since exactly one-half of the elements of Z p are quadratic residues by

Proposition 2.11, we see that this subgroup has order 2. But this group may

still have elements of small order that, as we have seen, can be troublesome when
implementing the DH protocol. Thus one of the preferred solutions to implement
the protocol is to ensure that this group has prime order, something that happens
if we take p to be a safe prime which, as seen in Sect. 6.3 , is a prime of the form
p

( p − 1 )/

1, where q is also prime ( q is then a Sophie Germain prime). Then the
group of quadratic residues modulo p has prime order equal to q and so it has the
advantages we have just mentioned. Note that this group is cyclic (in general, every
subgroup of a cyclic group is cyclic but here this also follows in a straightforward
way from the fact that the group has prime order, using Lagrange's theorem) and
every element distinct from the identity is a generator. Thus finding a generator is
very easy: just pick a random element c

= 2 q +

∈ Z p different from 1 and − 1, and take the

c 2 Z p and the protocol element g = ∈ QR p .Now g is an element of order q in

proceeds as indicated above picking random elements x ∈ Z q .

A variant of the “safe prime method” consists of taking a prime p of the form

, y

p 1 / 10 , and finding an element g of p = rq + 1 where q is also prime with, say, q >

Z p . Since now q is smaller relative to
the size of p , this approach is more efficient because it requires smaller exponents
(as x

Z p , to work in the subgroup order q in g of

, <

y q ), although p will usually be noticeably larger than in the safe prime

case.