Score:0

Query about arithmetic finite fields

kw flag

I was working on implementing shamir secret sharing in GF(2^256), According to my knowledge multiplication in a finite field is defined as mul(a,b) = (a*b)%mod, where mod is the irreducible polynomial.

But when I saw the implementation here, It uses bitmasking to multiply and when I compare my multiplication results with this it doesn't matches, what could be the reason?

Score:1
ng flag

A field $(\mathbb F,+,*)$ is a set closed under two operations $+$ and $*$, with $(\mathbb F,+)$ a commutative group having identity element noted $0$, $(\mathbb F\setminus\{0\},*)$ a commutative group with identity noted $1$, and $*$ distributive w.r.t. $+$. Equivalently, it's a commutative ring $(\mathbb F,+,*)$ in which every element except $0$ has a multiplicative inverse.

A Galois field is a field with a finite number of elements $q$. It can be shown that:

  • It must be that $q=p^k$ with $p$ prime and $k$ a strictly positive integer.
  • Any two Galois fields with the same number $q$ of elements are isomorphic. The set of such Galois fields (or for short, the Galois field with $q$ elements) is noted $\operatorname{GF}(q)$ or $\mathbb F_q$.
  • When $k=1$, the isomorphism between two fields of $\operatorname{GF}(p)$ with $p$ prime is uniquely defined by the mere correspondence of each field's identity elements $0$ and $1$. The fields then are isomorphic to the ring of integers modulo the prime $p$, noted $\mathbb Z/p\mathbb Z$ or (somewhat less properly) $\mathbb Z_p$. That field is assimilated to $\mathbb F_p$.
  • More generally, any field of (or the field) $\operatorname{GF}(p^k)$ is isomorphic to the set of polynomials of degree less than $k$ with coefficients in $\mathbb F_p$ (equivalently, the set of tuples with $k$ elements each an integer modulo $p$), with addition $+$ defined by polynomial addition (equivalently, addition modulo $p$ of tuple elements of the same indexes), and multiplication $*$ defined by polynomial multiplication followed by taking the remainder by Euclidean polynomial division of that product by some irreducible polynomial $P$ of degree exactly $k$.

When $p=2$ as is the case in $\operatorname{GF}(2^{256})$ of the question or $\operatorname{GF}(2^{128})$ of the code linked in the question (with $k=256$ or $k=128$ respectively), it's convenient to assimilate an element of the field to an integer in $[0,2^k)$. The most natural mapping, used by the linked code, is to assimilate a binary polynomial to the integer obtained by evaluating the polynomial in $\mathbb Z$ at $x=p=2$. That is, the polynomial $\sum x^j$ for $j$ in some finite subset of $\mathbb N$ is represented by the integer $\sum2^j$ with $j$ in that same subset. Addition is then bitwise eXclusive OR, implemented by the Python operator ^. Much like this is is addition without carry, multiplication is carry-less product, and modular reduction also is bitwise. These can be implemented as two separate operations like _mult_gf2 and _div_gf2 in the linked code, or they can be interleaved, as in __mul__.

when I compare my multiplication results with this it doesn't matches, what could be the reason?

  • Confusing * or % as implemented by Python for int operands with polynomial multiplication or polynomial remainder as applicable to operands that are representation of polynomials as int.
  • Not using the same $k$: the question is about $\operatorname{GF}(2^{256})$, the linked code is about $\operatorname{GF}(2^{128})$ and has $128$ hardcoded in multiple places.
  • Not using the same irreducible polynomial of degree $k$ as reduction polynomial. The linked code uses $1+x+x^2+x^7+x^{128}$.
  • Not using the same mapping of polynomial to integer, for the field elements or the reduction polynomial. An alternate representation for polynomial $\sum x^j$ of degree less than $k$ could use $\sum2^{k-j-1}$, but that's highly unusual, and that convention can't apply for the reduction polynomial itself.
Score:1
my flag

According to my knowledge multiplication in a finite field is defined as mul(a,b) = (a*b)%mod, where mod is the irreducible polynomial.

Actually, there are other plausible ways to represent values in a finite field; these other plausible ways yield different ways of multiplication.

However, that's not the case here.

But when I saw the implementation here, It uses bitmasking to multiply

Well, yes, it is effectively implementing $(a \times b) \bmod mod$; it's just doing it in a different way.

Instead of during the full multiplication $a \times b$ and then doing to modular reduction, instead, it scans through the bit representation of $a$, and for each bit $i$ which is set, it does $result = result + 2^i \times a$. The modular reduction effectively happens when they update $2^i \times a$ for the next value of $i$ (which it stores in the variable $v$). The shifting and masking of $v$ is the update of $v$ as $i$ is being incremented.

Oh, and they do the conditional addition in an obscure way - instead of a straightforward "if bit-is-set then z = z ^ v" (addition in $GF(2^k)$ is implemented by xor), then instead play with mask2 to replace z with either z or z^v, depending on the bit setting. This obscure way would make sense if they were interested in constant time, however they're in python, which makes no constant time guarantees, and more importantly, they iterate until they run out of set bits (that is, until f2 is zero), and so the number of iterations they take depends on one of the inputs.

As for why you're not getting the same result, well:

  • Are you in the same field? You said $GF(2^{256})$, however the python code you cited works in $GF(2^{128})$. Did you convert the python code to work with 256 bits?

  • Are you using the same irreducible polynomial?

  • Are you using the same endianness?

CipherNewbie avatar
kw flag
I am in the same field, and the irreducible polynomial is same as well, mostly not in the same endianness, and hence the difference in results. How does the endianness affects the results? and Which endianness is used here in pycryptodome?
poncho avatar
my flag
@CipherNewbie: I don't know the endianness used in pycryptodome; however one quick test: try to represent the value '2' and ask it to compute $2 \times 2$. If it returns the value '4' in the same representation, you've likely verified it
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.