safety of Pohlig-Hellman with a common modulus?

[Peter Fairbrother]

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.

Two simple ways around that - use longer prime moduli, or change the modulus
from time to time.


The attack on RSA has no equivalent here. That attack involves using a key
pair to find phi(n) or a divisor of it, but in Pohlig-Hellman the value of
phi(p) is not secret (= p-1).

I am presently using Pohlig-Hellman in a construction for universal
re-encryption, taking advantage of it's key-multiplicative property. See
http://www.zenadsl6186.zen.co.uk/ICURpaper3.pdf or
http://www.zenadsl6186.zen.co.uk/ICURpaper3.ps for the messy math details,
my application is in the online observable SFS for m-o-o-t.



Pohlig-Hellman is still however very slow compared to modern symmetric
ciphers, and in most cases where P-H is used a group cipher with the
required key properties would be more efficient.

No such cipher exists, but I am thinking of building one. I have already got
a few indications of interest, if anyone else wants to contribute please let
me know. I'm not committed to doing it, but if enough people want it..

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