Less Leaky ECDSA signature generation (in master)

[Jacob Bachmeyer]

On 3/28/25 08:11, Ian Goldberg via Gcrypt-devel wrote:
> On Fri, Mar 28, 2025 at 10:21:43AM +0900, NIIBE Yutaka via Gcrypt-devel wrote:
>> While, arbitrary integers can be represented in the MPI representation,
>> for a specific curve, the finite field is the one of integers module P
>> (P: a prime defined by the curve).  Thus, for an ECC point, we can keep
>> the integer value in the range from 0 to P-1.  For an intermediate value
>> of integer (like multiplication), 2*P is enough size.
> Do you mean P^2, not 2*P, as the bound of the intermediate result of a
> multiplication?

I believe that the multiplications are performed modulo P, with 
incremental modular reductions as the calculation proceeds.  I seem to 
recall that this can be done (perhaps even most efficiently) on a 
per-bit basis.  I clearly recall my calculator being able to do "modular 
exponentiation" much faster than "exponentiation followed by modulus".  
(Unfortunately, that calculator has since been severely damaged by 
leaking batteries and the model is discontinued...)

That raises another question:  is the modular reduction (or more 
importantly its bypass if unneeded) constant-time?  In other words, is 
the choice of "use intermediate result (0<X<P) as-is" or "reduce 
intermediate result (P<X<2*P)" constant-time?  (It should already be; 
this would be a fairly severe timing leak if it is not.)


-- Jacob