<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html><body>
<span id="mailbox-conversation"><div>
<span style="-webkit-tap-highlight-color: transparent;">> If the system uses RSA, the cheapest approach is usually to vary the </span><span style="-webkit-tap-highlight-color: transparent;">public exponent. </span>
</div>
<div><br></div>
<div>Actually done that. (64-bit OpenPGP key collisions, see https://github.com/cooperpair). But fingerprints that include the RSA exponent are a design mistake. (It isn't a part of the 'hard problem'; and > 99% of normal users' keys use the top three exponents, IIRC.)[*]</div>
<div><br></div>
<div>And thanks for the exceedingly helpful suggestions on EC keys; I may play around with figuring out a more precise cost estimate</div>
<div><br></div>
<div>Joseph: Attacker's hardware is much more parallel than users' hardware... See, e.g., djb's current microcluster[**]: <a href="http://blog.cr.yp.to/20140602-saber.html" style="-webkit-tap-highlight-color: transparent;">http://blog.cr.yp.to/20140602-saber.html</a> </div>
<div><br></div>
<div>(Background on the zero-prefix cost issue: Experimentally verified when I was looking at OpenPGP key collisions. Did a slightly larger plain collision search than is reflected by results in my repo; selecting targets with a zero byte needed to hide memory latency on target architecture. At some point I'll clean up the source...<span style="-webkit-tap-highlight-color: transparent;">)</span>
</div></span><br><br><span class="mailbox-reply"><div id="orc-email-signature" style="display: block;"><br></div>
<div id="orc-email-signature" style="display: block;">[*] Adam Langley has pointed out that protocols which allow arbitrary exponents are subject to DoS attacks. <a href="https://www.imperialviolet.org/2012/03/17/rsados.html" style="-webkit-tap-highlight-color: transparent;">https://www.imperialviolet.org/2012/03/17/rsados.html</a> So perhaps not requiring e fixed was the design mistake.</div>
<div id="orc-email-signature" style="display: block;"><br></div>
<div id="orc-email-signature" style="display: block;">[**] <span style="-webkit-text-size-adjust: auto; background-color: rgba(255, 255, 255, 0);">Why can't cryptographers get funding for real clusters? I know plenty of physicists with as much compute power in their office. And cluster-builders who have wasted more real cluster time running Linpack than, well...alas.</span>
</div>
<div id="orc-email-signature" style="display: block;"></div>
<span class="mailbox-inline-edit"></span><div id="orc-email-signature" style="display: block;"><div class="mailbox_signature">—<br>Sent using alpine: an Alternatively Licensed Program for Internet News and Email</div></div>
<br><span id="orc-full-body-initial-text" style="display: inline;">On Wed, Jul 23, 2014 at 11:56 AM, Robert Ransom<<a href="mailto:rransom.8774@gmail.com" target="_blank">rransom.8774@gmail.com</a>>, wrote:<br></span><blockquote class="gmail_quote">On 7/23/14, David Leon Gil <coruus@gmail.com> wrote:
<br>> (I suspect perhaps Joseph was thinking about prime-based-crypto in his
<br>> comment. Or is there a good way of cheaply generating (strong) RSA keys? The
<br>> obvious approach is to just pick two strong primes and then just multiply
<br>> by, say, all primes less than 2^w, where w is the word length, which is a
<br>> factor of N/w cheaper for schoolbook, at least.)
<br><br>I would reserve the term “prime-based crypto” for
<br>discrete-logarithm-based cryptosystems in prime-field multiplicative
<br>groups. You seem to be talking about factorization-based
<br>cryptosystems.
<br><br>If the system uses RSA, the cheapest approach is usually to vary the
<br>public exponent. (This search can be performed on untrusted hardware,
<br>e.g. botnet nodes, so it poses a greater threat than one that exposes
<br>the secret key to the device which finds the winning public key. All
<br>reasonable discrete-logarithm public key search procedures can also
<br>use untrusted hardware.)
<br><br>If the system uses RSA with a fixed public exponent, what you describe
<br>may work if no one tries to actively detect and prevent that attack.
<br>(This search can also be performed on untrusted hardware.)
<br><br>If the system uses RSA with a fixed public exponent and you must
<br>ensure that no prime factor of the modulus is ever found, the cheapest
<br>approach is to generate a bunch of secret primes and multiply together
<br>each pair of distinct primes. (This search requires trusted
<br>hardware.)
<br><br><br>> In general, the speedup of just doing adds or doubles is very roughly the
<br>> bit length of the EC key, right? (I have a factor of 515 for
<br>> Ed448-Goldilocks based on benchmarks, which seems in accord with my
<br>> intuition.)
<br><br>For Ed448-Goldilocks, I'm not sure. The earlier versions used Mike
<br>Hamburg's 1/sqrt(u) point format (where u is the Montgomery-form x
<br>coordinate), and I don't think that can be batch-scaled.
<br><br>For ECC with the more common point formats, at the very least, you can
<br>batch the inversions together using ‘Montgomery's trick’ (on a serial
<br>or mostly-serial computer), at least until your working storage
<br>reaches the processor's cache size. On top of that speedup,
<br>short-Weierstrass batched affine addition uses a batched inversion
<br>within the formula, and is considerably faster than projective
<br>addition followed by scaling.
<br><br><br>Robert Ransom
<br>
</blockquote></span>
</body></html>