[14872] in cryptography@c2.net mail archive
Re: safety of Pohlig-Hellman with a common modulus?
daemon@ATHENA.MIT.EDU (Peter Fairbrother)
Sun Dec 7 00:47:18 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sun, 07 Dec 2003 03:58:06 +0000
From: Peter Fairbrother <zenadsl6186@zen.co.uk>
To: David Wagner <daw-usenet@taverner.cs.berkeley.edu>,
<cryptography@metzdowd.com>
In-Reply-To: <bqtm75$dcl$1@abraham.cs.berkeley.edu>
David Wagner wrote:
> 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.
Nope. In P-H there is no g. A ciphertext is M^k mod p. An attacker won't
know k, and usually won't know M, but see below. I don't know what the
problem is called, but it isn't DLP. Anyone?
> 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.
Not usually. In general index calculus attacks don't work on P-H, except in
chosen plaintext attacks (where the chosen plaintext sort-of substitutes for
g).
When using P-H I usually pre-encrypt data in any old symmetric cipher with a
random IV and any old key, to avoid known plaintext attacks. There are
several other attacks to be aware of, including some nasty
adaptive-chosen-plaintext and chosen-ciphertext attacks.
--
Peter Fairbrother
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
