0
$\begingroup$

I was considering algorithm 2.40 (arbitrary reduction polynomials) in the Guide to Elliptic Curve Cryptography and... it doesn't appear to work when the order of the polynomial you're trying to reduce is less than the order of the reduction polynomial.

Say you have a reduction polynomial of $x^{128}+x^7+x^2+x^1+1$ (the GCM reduction polynomial) and are trying to reduce $x^{127}$.

With polynomial division the quotient is $0$ and the remainder is $x^{127}$ but algorithm 2.40 in the ... seems to give $0$ as the answer.

In the for loop $i$ is going from the $2m - 2$'th bit (more specifically, the coefficient of $x^i$) downto the $m$'th, where $m$ is the order of the reduction polynomial ($128$). So you never actually get to $x^{127}$ and so nothing is ever added to $C\{j\}$ and thus the return value is $0$.

Is my analysis correct? If so that would seem to imply that the algorithm given n the Guide to Elliptic Curve Cryptography is insufficient and it's inclusion probably ought to be considered errata?

$\endgroup$
2
$\begingroup$

In the for loop $i$ is going from the $2m - 2$'th bit (more specifically, the coefficient of $x^i$) downto the $m$'th, where $m$ is the order of the reduction polynomial ($128$). So you never actually get to $x^{127}$ and so nothing is ever added to $C\{j\}$ and thus the return value is $0$.

Actually, $C$ starts off initialized to the input polynomial $c(z)$, and so by not adding anything, the final $C$ value is precisely the initial value, which is the correct answer.

They could have written the algorithm clearer by explicitly stating that, and using the same case for $C$ consistently...

$\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.