[messaging] Bounding hash 2d preimage bits (was Re:...Test Data)

[Joseph Bonneau]

On Jul 23, 2014 10:53 AM, "David Leon Gil" <coruus at gmail.com> wrote:

> (I suspect perhaps Joseph was thinking about prime-based-crypto in his
> comment. Or is there a good way of cheaply generating (strong) RSA keys?
> The obvious approach is to just pick two strong primes and then just
> multiply by, say, all primes less than 2^w, where w is the word length,
> which is a factor of N/w cheaper for schoolbook, at least.)


I was thinking about RSA which still dominates for PGP keys, but I wasn't
thinking too carefully beyond a naive attacker who does full key
generation. Robert rightly pointed out this is the wrong approach.

For RSA one could generate n primes and then test n^2 public keys with just
one multiply each. There are probably further speedups as well, though I'm
not sure they're as good as Robert's suggestion which is really neat. It
would be nice to have a rough catalog of public key types and the cost of
brute-forcing them compared to the cost of basic hash operations.

Another thought though is that instead of relying on brute-forcing
fingerprints being slowed by public key generation being inherently slow,
it's better to explicitly add itreated hashing to the fingerprint
generation. One way to do this is to enforce that the hash of the public
key starts with x consecutive zeros. This imposes no cost on verification
and has the benefit that fingerprints are effectively shorter by x bits
(with equivalent security) as the zeros don't need to be transmitted,
stored or checked. I'd imagine in most cases we could afford x=20-30. The
downside is that x must be set universally and can't be upgraded. That's
why I'd suggest tying x to the public-key size so when key sizes are
upgraded x can be as well.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140723/d1456fc0/attachment.html>