[Cryptech Tech] Storage of curve parameters for ECDSA

[Pavel Shatov]

On 14.01.2016 16:54, Rob Austein wrote:
> At Thu, 14 Jan 2016 11:01:38 +0300, Pavel Shatov wrote:
>>
>> Rob, could you please dump "rho" for all the three curves in
>> ecdsa_curves.h? I have a feeling, that "rho" will always be just 1 (one).
>
> Ah.  Hadn't noticed that, I'm just calling libtfm setup function:
>
>    sw/thirdparty/libtfm/tomsfastmath/src/mont/fp_montgomery_setup.c
>
> but you're correct that the computed value is one for all three of
> those curves.

That's what I thought. Well, the "trick" of Montgomery reduction is to 
shift the temporary product to the right after every iteration to 
prevent bit width growth. This can only be done if lower bits are 
zeroes. Lower bits can be zeroed out by adding multiples of the modulus.

Now if reduction is done bit-by-bit, then one modulus is added to the 
temporary result, if its lowest bit is set (given that the modulus must 
be odd, adding it to an odd temporary result will produce an even number 
with the lowest bit set to zero). This lowest zero bit can then be 
safely shifted away.

Reduction can also be done word-by-word, which is much faster. That's 
how FPGA (and apparently libtfm) works. In that sense "fp_digit" is 
actually a 32-bit number, so the algorithm zeroes out 32 bits a time. To 
do this one needs a special speed-up factor, that depends on lower 32 
bits of the modulus. Btw, that's why you have to toggle the init bit of 
ModExpS6 core after you change modulus -- the core has to pre-calculate 
the new speed-up factor. I guess setup function in libtfm does the same.

NIST primes all have their lower 32 bits set to ones, so the speed-up 
factor becomes just 1, there's no need for FPGA to calculate it at all. 
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.


-- 
With best regards,
Pavel Shatov