safety of Pohlig-Hellman with a common modulus?

Peter Fairbrother zenadsl6186 at zen.co.uk
Sat Dec 6 13:15:03 EST 2003


I 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.)
> 
> --Steve Bellovin, http://www.research.att.com/~smb

As far as I can tell it's safe - the main danger is that it that if an
attacker does the work to calculate the factor base for an index calculus
attack, the factor base is useful for attacking all ciphertext which uses
the modulus. It's fairly easy to find an individual discreet log with a
factor base, so such an attacker would get a bigger return on investment.



Sorry, the above is complete nonsense, and only applies in a few situations.

There are some chosen plaintext attacks, and especially adaptive chosen
plaintext attacks, but they apply whether or not the modulus is shared.

But P-H with a shared modulus is pretty much as safe as with different
moduli, afaict.

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



More information about the cryptography mailing list