Join Log in
Score:3
MichaelW avatar Crypto

Factorization of polynomial in GF(2^128) used in GCM

in flag
MichaelW

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

105
1 + 0
gcm
Score:2
avatar Crypto
cn flag
Nicklas Börbacke

"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].

References:

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

0 + 1
MichaelW avatar
in flag
MichaelW
Tis is what I was looking for ;-)
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.