safety of Pohlig-Hellman with a common modulus?
Anton Stiglic
astiglic at okiok.com
Sun Dec 7 12:36:04 EST 2003
----- Original Message -----
From: "Peter Fairbrother" <zenadsl6186 at zen.co.uk>
To: "David Wagner" <daw-usenet at taverner.cs.berkeley.edu>;
<cryptography at metzdowd.com>
Sent: Saturday, December 06, 2003 7:58 PM
Subject: Re: safety of Pohlig-Hellman with a common modulus?
> 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?
If you don`t know M and k, there are several values M', k' such that
M'^k' mod p == M^k mod p. For example, if M is a generator of the
group mod p, than all other generators M' will have a corresponding k'
that will give you this value.
Think about known plaintext attack or chosen plaintext attack. A symmetric
cipher should be secure against these attacks and much more...
In these attacks you know the bases of several values...
--Anton
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list