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