safety of Pohlig-Hellman with a common modulus?

[Jerrold Leichter]

| 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.)
The question seems equivalent to:  Is P-H with a *known* modulus safe?  The
only difference, from the point of view of an attacker, is that with a shared
modulus, he gets to see a whole bunch of values X^e_i mod P, including (if he
is a member of the system) some where he knows X and e.  But with a known
modulus, he can easily generate as many of these as he likes.  The safety of
P-H had better depend on the difficulty of solving the discrete log problem
mod P, not on keeping P secret.  (Keeping P secret would require great care in
the protocol, in particular in how you respond to messages that are greater
than P.  Otherwise, an attacker can guess the rough size of P - based on the
maximum sizes of messages he observes - and then try to do a binary division
by sending messages of differing sizes.)

The situation is different in RSA since there are *two* secrets:  The
factorization of N, and the correspondence between public and private keys.
These secrets are so closely related that revealing one reveals the other as
well.  We usually only consider the implication "factoring N lets you get the
private key from the public", but the other one is present as well. Giving
someone a public/private key pair for a given N is *not* zero knowledge!

							-- Jerry

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com