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
_______________________________________________
Gcrypt-devel mailing list
Gcrypt-devel@gnupg.org
https://lists.gnupg.org/mailman/listinfo/gcrypt-devel
