[Cryptech Tech] Storage of curve parameters for ECDSA

[Pavel Shatov]

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