On 14.01.2016 22:46, Peter Stuge wrote:
Rob Austein wrote:
Since I'm trying to write ECDSA core, not general-purpose EC math core,
I thought, that it would make sense to take advantage of the fact and
get rid of that redundant coefficient.
Is there a security concern with such an optimization - side-channel
or otherwise?
I don't think so. The curve parameters are public information.
Please continue through all layers.
Could such an optimization somehow influence operations which use
private information to e.g. leak some of it?
This optimization affects how the modular multiplier works. The second
phase of Montgomery reduction algorithm adds multiples of modulus to
zero out the lowest word. The trick is to determine, how many moduli we
need to add. Suppose that t is the intermediate result, t0 is its lowest
word, q is the modulus and rho is the speed-up factor. Also note, that
rho is actually -q0^-1.
Without optimization the second phase is:
k = t0 * rho; // determine, how many multiplies of modulus to add
t += k * q; // add multiples of modulus to zero out the lowest word
Given that q0 is 0xFFFFFFFF and rho is 1, the second phase becomes:
t += t0 * q; // add multiples of modulus to zero out the lowest word
I can't think of how this optimization can cause leakage or something,
but I understand your concern. For example, http://safecurves.cr.yp.to/
says under "Efficiency" section, that optimizations of this kind (I
mean, primes with lower bits set to all ones) in fact damage efficiency,
they are bad for security, etc. Unfortunately, my level of math is not
enough beyond this point.
--
With best regards,
Pavel Shatov
_______________________________________________
Tech mailing list
Tech@cryptech.is
https://lists.cryptech.is/listinfo/tech
