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 three 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$ and $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, 2019 at 13:58
  • 2
    $\begingroup$ I can't help linking this fantastic blog post dissecting Gueron's trick: blog.quarkslab.com/… $\endgroup$ Jan 8, 2019 at 21:00


Your Answer

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

Browse other questions tagged or ask your own question.