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

[David Leon Gil]

(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.)


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.)
—
Sent using alpine: an Alternatively Licensed Program for Internet News and Email

On Wed, Jul 23, 2014 at 8:10 AM, Robert Ransom <rransom.8774 at gmail.com>
wrote:

> On 7/22/14, Joseph Bonneau <jbonneau at 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 at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140723/18763392/attachment.html>