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 [EMAIL PROTECTED]
