From: hughes@ah.com (Eric Hughes)
Date: Sat, 21 May 94 07:05:14 PDT
To: cypherpunks@toad.com
Subject: Is my DH exchange secure?
In-Reply-To: <199405210512.WAA04068@mail.netcom.com>
Message-ID: <9405211408.AA12666@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


[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