These slides talk about how GCM can be sped up if one uses $x^{128}+x^{127}+x^{126}+x^{121}+1$ as the reduction polynomial instead of $x^{128}+x^7+x^2+x^1+1$.

When one is doing that one needs to multiply the polynomial you're attempting to reduce by $x^{-127}$, "better written as" $x \cdot x^{-128}$. I have two questions about this...

  • Does this need to be done in addition to and prior to the method described on page 20 of those slides? Like do I need to explicitly multiply every polynomial I'm trying to reduce (let's call this polynomial $y$) by $x^{-1}$ and add $y \ll 1$ to $y \ll 128$? My assumption is that it does but idk

  • When page 20 of those slides say $x_0 \cdot C200000000000000_{16}$ does it mean to do integer multiplication or polynomial multiplication? Like with integer multiplication $5\cdot5=25 = 19_{16}$ whereas with polynomial multiplication over a binary finite field $5 \cdot 5$ could be interpreted as $(x^2 + 1)(x^2 + 1) = x^4+ x^2 + x^2 + 1 = x^4 + 1 = 11_{16}$. I'm assuming you're supposed to do integer multiplication but idk

  • Is $C200000000000000_{16}$ supposed to be in big endian format or little endian format? I'm guessing little endian since that's what GCM uses? In that scenario then $C200000000000000_{16}$ could be rewritten more simply as $C2_{16}$ just as $0099$ can be rewritten as $99$.

  • 2
    $\begingroup$ Hint: $x^{-1}$ is the number that multiplied by $x$, modulo the reduction polynomial, makes $1$. You can find it and then compute its powers to obtain $x^{-2},...,x^{-127}$. However I believe that in this specific case the trick is to understand Montgomery reduction and that $R=x^{128}$ $\endgroup$ – Ruggero Jan 8 at 13:58
  • 2
    $\begingroup$ I can't help linking this fantastic blog post dissecting Gueron's trick: blog.quarkslab.com/… $\endgroup$ – SquareRootOfTwentyThree Jan 8 at 21:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.