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... ]