[14874] in cryptography@c2.net mail archive
Re: safety of Pohlig-Hellman with a common modulus?
daemon@ATHENA.MIT.EDU (David Wagner)
Sun Dec 7 11:57:46 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
To: cryptography@metzdowd.com
From: daw@taverner.cs.berkeley.edu (David Wagner)
Date: Sun, 7 Dec 2003 06:20:29 +0000 (UTC)
Reply-To: daw-usenet@taverner.cs.berkeley.edu (David Wagner)
X-Complaints-To: usenet@abraham.cs.berkeley.edu
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@metzdowd.com
