Re: Parameters for Diffie-Hellman-Merkle

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 06/09/03 

Date: 8 Jun 2003 16:07:37 -0700

In article <32124ecf.0306081339.48e2bfbc@posting.google.com>,
David James Spillett <google@spillett.net> wrote:
>I'm toying with the idea of using the Diffie-Hellman-Merkle key

The key agreement scheme is just called
"Diffie-Hellman". While Merkle is acknowledged as
a co-inventor of public-key schemes generally, he
wasn't involved in this particular one.

>My question... [assuming you haven't given up and stopped reading my
>blabber by now!]:
>
>When discussing the public parameters of DHM [the Y and P of 'Y^x mod
>P'] some sources imply that there are few restrictions on chosing
>these values - in fact The Code Book by Simon Signh states this quite
>plainly. Other sources state that P must be prime and others still
>[i.e. Handbook of Applied Cryptography, which is for the most part
>significantly above my head!] state restrictions for Y relative to P.

P must be prime, and P-1 needs to have at least
one large factor. Common wisdom is to either have
Q=(P-1)/2 also be prime, or to start with a prime Q
of about 160 bits, and then find a P = Q*k + 1
that's also prime for some random k.

Y (often called "G" for generator) should be a
member of the order Q subgroup.

>Would the DHM be 'secure enough' if I were to choose arbitrary
>[random] large [by large I am thinking a few hundred bits or more,
>assuming my MP maths code is fast enough to cope] values for P and Y?

There's no reason at all for Y to be large. P, on
the other hand, needs to be much larger than "a
few hundred bits". It's approximately valid to say
that 1024-bit P, 160-bit Q, and 80-bit symmetric
keys are roughly matched.

>I'm not trying to stop the NSA, just the not-so-idle eves-dropper.

"A few hundred bits" is an hour on a PC.

Greg. 

-- 
Greg Rose                                       INTERNET: ggr@qualcomm.com
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/ 
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C