From owner-coderpunks@toad.com Fri Feb 16 14:13:07 1996
Received: from hofmann.CS.Berkeley.EDU (hofmann.CS.Berkeley.EDU [128.32.35.123]) by orodruin.CS.Berkeley.EDU (8.7.Gamma.0/8.7.Gamma.0) with SMTP id OAA10549 for ; Fri, 16 Feb 1996 14:13:06 -0800 (PST)
Received: from relay3.UU.NET (relay3.UU.NET [192.48.96.8]) by hofmann.CS.Berkeley.EDU (8.6.11/8.6.6.Beta11) with ESMTP id OAA21468 for ; Fri, 16 Feb 1996 14:13:04 -0800
Received: from toad.com by relay3.UU.NET with SMTP
id QQadfj04636; Fri, 16 Feb 1996 16:50:54 -0500 (EST)
Received: by toad.com id AA12246; Fri, 16 Feb 96 13:50:42 PST
Received: from dawn7.CS.Berkeley.EDU by toad.com id AA12234; Fri, 16 Feb 96 13:50:32 PST
Received: (from daw@localhost) by dawn7.CS.Berkeley.EDU (8.6.11/8.6.9) id NAA00533; Fri, 16 Feb 1996 13:50:23 -0800
From: David A Wagner
Message-Id: <199602162150.NAA00533@dawn7.CS.Berkeley.EDU>
Subject: Re: Lucas Sequences in Cryptography
To: weidai@eskimo.com (Wei Dai)
Date: Fri, 16 Feb 1996 13:50:22 -0800 (PST)
Cc: coderpunks@toad.com
In-Reply-To: from "Wei Dai" at Feb 16, 96 11:16:26 am
Reply-To: daw@CS.Berkeley.EDU
X-Mailer: ELM [version 2.4 PL25]
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: owner-coderpunks@toad.com
Precedence: bulk
Status: RO
[ ... re: Lucas sequences ... ]
> > constructed. Compared to DH and ElGamal, for the same level of security
> > they only require modulus half the size because they are based on
> > discrete log modulo p^2 rather than p. Because of the smaller modulus
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> This should be "discrete log in GF(p^2) rather than GF(p)".
Hrmm, I had a thought about discrete logs in GF(p^2).
We're used to using GF(p). |GF(p)| = p-1, and the multiplicative group
of GF(p) is cyclic, so for each small prime factor q dividing p-1, we
can lever out some information about the discrete log. (It's just the
familiar trick: if y = g^x in GF(p), y known, then look at y^{(p-1)/q},
which has only q possible values.)
This observation has been used (with much more sophisticated techniques!)
to attack Diffie-Hellman with small exponents [Wiener & van Oorschot's]
as well as forge El Gamal signatures [Bleichenbacher].
The typical fix is to first choose p so that p-1 has as few small prime
factors as possible: i.e. choose p so that (p-1)/2 is prime. Furthermore,
one can use g^2 as a base for the discrete log systems, instead of g
(where g is a generator of GF(p)).
But now we're talking about GF(p^2). |GF(p^2)| = p^2 - 1 = (p-1)(p+1),
and the multiplicative group of GF(p^2) is again cyclic, so now we can
use the same trick when any small prime q divides p^2 - 1. (In fact,
when any prime power divides p^2 - 1.)
Note that 8 always divides p^2 - 1, since p-1 and p+1 are both even and
one of the two must be a multiple of 4. So the best we can hope for is
that p^2 - 1 = (p-1)(p+1) = 8 ((p-1)/2) ((p+1)/4) with (p-1)/2, (p+1)/4
both prime, or that p^2 - 1 = 8 ((p-1)/4) ((p+1)/2) with (p-1)/4, (p+1)/2
both prime. A little algebra shows that we can look for q so that q,
2q+1, and 4q+1 are all prime, and set p = 4q+1; or we can look for q so
that q, 2q-1, 4q-1 are all prime, and set p = 4q-1. This should be the
best type of p to use for discrete log systems in GF(p^2), yes?
Furthermore, one can use g^8 as a base for the discrete log systems, instead
of g (where g is a generator of GF(p^2)); this eliminates all leakage of
the discrete log exponent, assuming we've chosen p as above.
So it seems prudent to use p of this special form and g^8 as a base, right?
Is this well known already?
[ Thanks, Ian, for fixing the algebra up there... ]