[14008] in Cypherpunks
Is my DH exchange secure?
daemon@ATHENA.MIT.EDU (Eric Hughes)
Sat May 21 10:16:10 1994
Date: Sat, 21 May 94 07:08:59 -0700
From: hughes@ah.com (Eric Hughes)
To: cypherpunks@toad.com
In-Reply-To: catalyst-remailer@netcom.com's message of Fri, 20 May 1994 22:12:14 -0700 <199405210512.WAA04068@mail.netcom.com>
[Please don't quote entire messages. It's a good way to make sure
your words afterwards get read by far fewer people.]
The one precaution I did not take is: (from discussion above)
[looking for number of small order]
Does the careful choosing of n and g eliminate this problem, or do I need
to modify my Diffie-Hellman code to check g^a for short order? How do you
check a number for short order?
If you wish to use generators mod p, proper choice of the prime will
minimize the problem; the generator has nothing to do with it. All
generators are symmetric, or, more precisely, the automorphism group
takes each generator to every other. Picking the prime p so that
p=2q+1 and q prime will reduce the number of elements with small order
to 2, namely 1 and -1.
In the more general case, let p=kq+1, where q is the large prime
factor of p-1 necessary for security. Now the order of an element x
must divide p-1, so if it's not of order q or larger, i.e. safe, then
it must be of order k. So calculate x^k (mod p) and see if it's equal
to 1. If it is, then x has small order.
On the other hand, the tests for small order can be minimized by using
a generator of the subgroup of size q inside the group mod p, rather
than a generator of the full group. Let p=kq+1 and let g be a
generator of Z/pZ (notation for the group of integers modulo p). Then
g^k has order q in Z/pZ. Since g generates the group, kq is the
smallest positive integer t such that g^t = 1 (mod p). g^(kq) =
(g^k)^q, so g^k has order q.
Now if you use h=g^k as the base for the D-H exchange, the only h^x
with small order happens when x=0. One can simply make the range of
the random numbers from 1 to q-1. Because h has order q, and since q
is prime, every h^x except x=0 will also have order q. Therefore
there are no "bad" values for x. They have been removed by
construction in advance.
Eric
