4
$\begingroup$

I'm implementing logic on an FPGA (programmable chip) that does the key verification part of ECDSA on the curve secpk256k1, in which all operations are mod p where $p = 2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$ (a Mersenne prime).

I'm starting with building a circuit to do the modular reduction, I know about Barret's and Montgomery's algorithm, but I have been reading in several guides that because of the $2^n - c$ form, as well as it being a Mersenne prime that there are simpler ways to do the modulo reduction.

But I'm getting stuck on understanding the actual logic underneath this, I was wondering if any one have any good example or pointers to understand how to do this modulo operation a bit better?

There was a similar question here (except I'm doing this on FPGA not CPU, so the word size is irrelevant) but I don't totally understand the answers reply, so even just some helpful comments explaining the same thing would be a huge help. Fast modular reduction

This paper also has a fast implementation on page 7 (http://cse.iitkgp.ac.in/~debdeep/osscrypto/psec/downloads/PSEC-KEM_prime.pdf) which looks like it came from one of these optimizations above, but I would like to try understand how to get there myself.

$\endgroup$
  • $\begingroup$ When I have a prime modulo, you are simply just running your XOR sums of registers and then adding them with a programmable overflow. You just MUX out some of the upper bits and add them to the lower bits. $\endgroup$ – b degnan Mar 17 at 18:59
  • $\begingroup$ Note that $2^{256} - 2^{32} - 977$ is not a Mersenne prime, though to varying degrees it might be considered a generalized Mersenne prime. (Exactly where the boundary between generalized Mersenne primes and mere primes lies has never been clear to me.) $\endgroup$ – Squeamish Ossifrage Mar 17 at 19:04
6
$\begingroup$

Let $p = 2^n - c$. Then $2^n - c \equiv 0 \pmod p$, so $2^n \equiv c \pmod p$. Suppose you have an integer $$x = 2^n x_{\mathrm{hi}} + x_{\mathrm{lo}}.$$ Then $$x \equiv c\cdot x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p.$$ In other words, you can compute a reduction step by shift/multiply/add: shift right by $n$, multiply by $c$, and add to the low $n$ bits.

The best case is when $c = 1$, so $p$ is a Mersenne prime: then you can skip the multiplication altogether. But you can generalize this further for $p = 2^n - 2^m - d$, since $2^n \equiv 2^m + d \pmod p$, so $$2^n x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 2^m x_{\mathrm{hi}} + d \cdot x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p.$$ That is, you can compute a reduction step by an $n$-bit shift, an $m$-bit shift, a multiply by $d$, and two adds.

Similarly, if $p = 2^{2m} - 2^m - 1$, like Ed448-Goldilocks uses, then you can compute a reduction step $$2^{2m} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 2^m x_{\mathrm{hi}} + x_{\mathrm{hi}} + x_{\mathrm{lo}}$$ with two $n$-bit shifts and two additions.

Obviously, you can always write any modulus as a sum of powers of two; the more terms there are, the more costly the reduction step is to write as a series of shifts and adds. In software implementations, at some point it may be faster to use the CPU's multiplier than your own shift-and-add steps. For instance, in secp256k1, I'd guess that it is fastest to write it as $2^{256} - 2^{32} - 977$ if you can take advantage of a CPU's 32x32->64-bit multiplier, but you should consult libsecp256k1 for the state of the art in arithmetic modulo this prime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.