safety of Pohlig-Hellman with a common modulus?

[David Wagner]

Peter Fairbrother  wrote:
>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?

Ok, I was being slightly loose.  To be more precise, the security of
Pohlig-Hellman is based on the Decision Diffie-Hellman (DDH) problem,
I believe.  But the best known attack on DDH (when you're working in
a prime-order subgroup) is to compute discrete logs.

>Not usually.  In general index calculus attacks don't work on P-H, [...]

Sure they do.  If I have a known plaintext pair (M,C), where
C = M^k (mod p), then with two discrete log computations I can
compute k, since k = dlog_g(C)/dlog_g(M) (mod p-1).  This works for
any generator g, so I can do the precomputation for any g I like.

>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.

Ok, that sounds like it should work.  To break the composed scheme,
one would need to break both P-H and the other symmetric cipher.

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