<span id="mailbox-conversation"><span style="-webkit-text-size-adjust: auto; 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><div><br></div>
<div>In general, the speedup of just doing adds or doubles is very roughly the bit length of the EC key, right? (I have a factor of 515 for Ed448-Goldilocks based on benchmarks, which seems in accord with my intuition.)</div></span><div class="mailbox_signature">—<br>Sent using alpine: an Alternatively Licensed Program for Internet News and Email</div>
<br><br><div class="gmail_quote"><p>On Wed, Jul 23, 2014 at 8:10 AM, Robert Ransom <span dir="ltr"><<a href="mailto:rransom.8774@gmail.com" target="_blank">rransom.8774@gmail.com</a>></span> wrote:<br></p><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><p>On 7/22/14, Joseph Bonneau <jbonneau@gmail.com> wrote:<br><br>> It's never possible to precisely compare brute-force but we should try to<br>> steer it around basic symmetric-key crypto block operations as a standard.<br>> On which note, steering back to public key search, the cost of generating a<br>> new public key when trying to come up with colliding fingerprints is far<br>> more costly than the hash, so setting 80 bits is probably at least 1000x<br>> more expensive than doing 2^80 SHA-256 ops.<br><br>No -- start each search node with Q = n*P for n secret and random, and<br>optionally Q' = n'*P for n' random; in each search step, replace Q<br>with either 2*Q or Q + Q', depending on which operation is faster for<br>your group.  (In multiplicative groups or curves represented in<br>Edwards form, doubling is faster; if you're doing a search for a<br>short-Weierstrass form point, ‘batched affine addition’ is faster (as<br>the SafeCurves page on ‘rho’ security says).  I don't know which<br>operation is faster in Montgomery form, since the conversion between<br>Montgomery and short-Weierstrass consists of adding/subtracting a<br>constant.)<br><br><br>Robert Ransom<br>_______________________________________________<br>Messaging mailing list<br>Messaging@moderncrypto.org<br>https://moderncrypto.org/mailman/listinfo/messaging<br></p></blockquote></div><br>