On 7/23/14, David Leon Gil <[email protected]> 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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
