It is widely known, that using a GCM nonce twice or even more often can be used to disclose the authentication key H. I understand, why this is theoretically possible. However, I have no feeling about the computational effort behind obtaining polynomial roots in GF($2^{128}$). Is there a straightforward algorithm available or do we need to apply some brute-force methods to factor a given polynomial according to a given field polynomial.?


"Straightforward" is a relative term. There are algorithms. The basic outline for one of them is

  1. First factor the polynomial into square-free factors using the Square-Free Factorization Algorithm.
  2. For each square-free factor found in step 1, factor it into a products or factors of the same degree (Distinct Degree Factorization).
  3. Use the Cantor-Zassenhaus algorithm to factor each result of step 2.

For a more detailed description see e.g. [Section 3.4, Cohen].


[Cohen] Henri Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, Berlin, 1993.

  • $\begingroup$ Tis is what I was looking for ;-) $\endgroup$
    – MichaelW
    Jul 20 at 7:01

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.