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.)

  • $\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$ – CodesInChaos Aug 2 '15 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 '15 at 14:30

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.

|improve this answer|||||

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.