[14866] in cryptography@c2.net mail archive
Re: safety of Pohlig-Hellman with a common modulus?
daemon@ATHENA.MIT.EDU (David Wagner)
Sat Dec 6 19:57:06 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
To: cryptography@metzdowd.com
From: daw@taverner.cs.berkeley.edu (David Wagner)
Date: Sat, 6 Dec 2003 22:45:57 +0000 (UTC)
Reply-To: daw-usenet@taverner.cs.berkeley.edu (David Wagner)
X-Complaints-To: usenet@abraham.cs.berkeley.edu
Steve Bellovin wrote:
>Is it safe to use Pohlig-Hellman encryption with a common modulus?
>That is, I want various parties to have their own exponents, but share
>the same prime modulus. In my application, a chosen plaintext attack
>will be possible. (I know that RSA with common modulus is not safe.)
Yes, I believe so. The security of Pohlig-Hellman rests on the difficulty
of the discrete log problem. Knowing the discrete log of g^y doesn't help
me learn the discrete log of g^x (assuming x,y are picked independently).
This is not like RSA, where using a common modulus allows devastating
attacks.
There is a small caveat, but it is pretty minor. There are some
precomputation attacks one can do which depend only on the prime p; after
a long precomputation, one can compute discrete logs mod p fairly quickly.
The more people who use the same modulus, the more attractive such a
precomputation effort will be. So the only reason (that I know of)
for using different modulii with Pohlig-Hellman is to avoid putting all
your eggs in one basket.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
