Re: Parameters for Diffie-Hellman-Merkle
From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 8 Jun 2003 16:07:37 -0700
In article <email@example.com>,
David James Spillett <firstname.lastname@example.org> 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 Rose INTERNET: email@example.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