On Sat, Oct 17, 2009 at 02:23:25AM -0700, John Gilmore wrote:

> DSA was (designed to be) full of covert channels.

True, but TCP and UDP are also full of covert channels. And if you are
worried that your signing software or hardware is compromised and
leaking key bits, you have larger problems, no matter what algorithm
you use; for instance, with RSA, the signer could intentionally
miscalculate 1 in 2^32 signatures, which would immediately leak the
entire private key to someone who knew to watch for it. (I would have
said that using PSS also introduces a covert channel, but it appears
DNSSEC is using the scheme from PKCS1 v1.5.)

And, for that matter, one can make DSA deterministic by choosing the k
values to be HMAC-SHA256(key, H(m)) - this will cause the k values to
be repeated, but only if the message itself repeats (which is fine,
since seeing a repeated message/signature pair is harmless), or if one
can induce collisions on HMAC with an unknown key (which seems a
profoundly more difficult problem than breaking RSA or DSA).

> RSA was the obvious choice because it was (and is) believed that if
> you can break it, you can factor large numbers (which mathematicians
> have been trying to do for hundreds of years).  No other algorithm
> available at the time came with such a high pedigree.  As far as I
> know, none still does.

As far as I know even now nobody has proven that breaking RSA is
equivalent to factoring; there are results that suggest it, for
instance [http://eprint.iacr.org/2008/260] shows there is no 'generic'
attack that can break RSA without factoring - meaning such an the
attack would have to examine the bit representation of the modulus.  A
full proof of equivalence still seems to be an open problem.

If for some reason one really wanted to ensure their public key
primitives reduces to a hard problem, it would have made much more
sense to use Rabin-Williams, which does have a provable reduction to


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Reply via email to