<div dir="ltr"><p dir="ltr">On Jul 23, 2014 10:53 AM, "David Leon Gil" <<a href="mailto:coruus@gmail.com" target="_blank">coruus@gmail.com</a>> wrote:<br></p><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">



<span><span style="background-color:rgba(255,255,255,0)">(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.)</span></span></blockquote>

<div><br></div><div><p dir="ltr">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.</p>

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

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

</div></div>
</div>