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

[Robert Ransom]

On 7/23/14, David Leon Gil <coruus at gmail.com> wrote:
> (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.)

I would reserve the term “prime-based crypto” for
discrete-logarithm-based cryptosystems in prime-field multiplicative
groups.  You seem to be talking about factorization-based
cryptosystems.

If the system uses RSA, the cheapest approach is usually to vary the
public exponent.  (This search can be performed on untrusted hardware,
e.g. botnet nodes, so it poses a greater threat than one that exposes
the secret key to the device which finds the winning public key.  All
reasonable discrete-logarithm public key search procedures can also
use untrusted hardware.)

If the system uses RSA with a fixed public exponent, what you describe
may work if no one tries to actively detect and prevent that attack.
(This search can also be performed on untrusted hardware.)

If the system uses RSA with a fixed public exponent and you must
ensure that no prime factor of the modulus is ever found, the cheapest
approach is to generate a bunch of secret primes and multiply together
each pair of distinct primes.  (This search requires trusted
hardware.)


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

For Ed448-Goldilocks, I'm not sure.  The earlier versions used Mike
Hamburg's 1/sqrt(u) point format (where u is the Montgomery-form x
coordinate), and I don't think that can be batch-scaled.

For ECC with the more common point formats, at the very least, you can
batch the inversions together using ‘Montgomery's trick’ (on a serial
or mostly-serial computer), at least until your working storage
reaches the processor's cache size.  On top of that speedup,
short-Weierstrass batched affine addition uses a batched inversion
within the formula, and is considerably faster than projective
addition followed by scaling.


Robert Ransom