3
$\begingroup$

I currently try to implement Ed25519 following this draft. I have implemented every field operation except the reduction by the group order $q$ (in chapter 5). I looked for a reduction algorithm and found montgomery reduction and barrett reduction. Because Barrett reduction seems to be more fitting I tried to understand how to implement it (mainly using this).

What I don't understand is how I can reduce a SHA512 hash by $q$, as the maximum possible value to reduce is ca. $2^{504}$ ($q$ is $2^{252}$, meaning $q^{2} = 2^{504}$). Is there a trick to reduce it in a step before that (like in curve25519 with $2^{256-38}$) or is Barrett reduction simply not usable here? (I don't necessarily need the fastest method available, a simple working one would be enough.)

$\endgroup$
2
  • $\begingroup$ The order is still pretty close to a power-of-two, so you can use a variant of the approach described at: What are the computational benefits of primes close to the power of 2? $\endgroup$ Aug 2, 2015 at 10:25
  • 1
    $\begingroup$ A simple (but inefficient) method to reduce X, goes somehow as follows: You initialize $t=q<<256$. Then, you make a loop with 257 repetitions and in each step you subtract $t$ from $X$ if you have $X>t$, and you set $t=t>>1$. $\endgroup$
    – Chris
    Aug 3, 2015 at 14:30

1 Answer 1

3
$\begingroup$

Note that $q = 2^{252} + n$ for $n < 2^{125}$. Consequently, $2^{252} \equiv -n \pmod q$, so $$2^{504} \equiv (2^{252})^2 \equiv (-n)^2 \equiv n^2 \pmod q.$$ Since $n^2 < 2^{250}$, you can reduce $$2^{504} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv n^2 x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod q.$$ Since the original input was only 512 bits long, $x_{\mathrm{hi}} < 2^8$, so we can set the bound $$n^2 x_{\mathrm{hi}} < 2^{250} 2^8 = 2^{253} < 2^{253} n + n^2 = q^2 - 2^{504},$$ which puts the reduced sum $n^2 x_{\mathrm{hi}} + x_{\mathrm{lo}} < q^2$ in the range of Barrett reduction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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