Multiplication over the binary finite field GF(2^m)

The multGF2() function shown in the Python script below implements the element (polynomial) multiplication over a binary finite field $GF(2^{m})$. The second function, setGF2(), sets the three constants needed for its colleague to perform its multiplication task: "mask1" and "mask2" (used in “and” operations) and "polyred", a polynomial constant used in the polynomial reduction of the product. These constants are defined from the parameters passed to setGF2(): "degree" (the extension degree of the binary field $GF(2^{m})$) and "irPoly" (the irreducible polynomial used for the product reduction). The version of multGF2() in the post AES implementation in Python, dubbed “mult()“, was configured specifically for the AES binary finite field used in the MixColumns operation, $GF(2^{8})/x^{8} + x^{4} + x^{3} + x + 1$.

#!/usr/bin/python3
#
# Author: Joao H de A Franco (jhafranco@acm.org)
#
# Description: Binary finite field multiplication in Python 3
#
# Date: 2012-02-16
#
#          (CC BY-NC-SA 3.0)
#===========================================================
from functools import reduce

# constants used in the multGF2 function

def setGF2(degree, irPoly):
"""Define parameters of binary finite field GF(2^m)/g(x)
- degree: extension degree of binary field
- irPoly: coefficients of irreducible polynomial g(x)
"""
if sum(irPoly) <= len(irPoly):
polyred = reduce(lambda x, y: (x << 1) + y, irPoly[1:])
else:
polyred = poly2Int(irPoly[1:])

def multGF2(p1, p2):
"""Multiply two polynomials in GF(2^m)/g(x)"""
p = 0
while p2:
if p2 & 1:
p ^= p1
p1 <<= 1
p1 ^= polyred
p2 >>= 1

#=============================================================================
#                        Auxiliary formatting functions
#=============================================================================
def int2Poly(bInt):
"""Convert a "big" integer into a "high-degree" polynomial"""
exp = 0
poly = []
while bInt:
if bInt & 1:
poly.append(exp)
exp += 1
bInt >>= 1
return poly[::-1]

def poly2Int(hdPoly):
"""Convert a "high-degree" polynomial into a "big" integer"""
bigInt = 0
for exp in hdPoly:
bigInt += 1 << exp
return bigInt

def i2P(sInt):
"""Convert a "small" integer into a "low-degree" polynomial"""
return [(sInt >> i) & 1 for i in reversed(range(sInt.bit_length()))]

def p2I(ldPoly):
"""Convert a "low-degree" polynomial into a "small" integer"""
return reduce(lambda x, y: (x << 1) + y, ldPoly)

def ldMultGF2(p1, p2):
"""Multiply two "low-degree" polynomials in GF(2^n)/g(x)"""
return multGF2(p2I(p1), p2I(p2))

def hdMultGF2(p1, p2):
"""Multiply two "high-degree" polynomials in GF(2^n)/g(x)"""
return multGF2(poly2Int(p1), poly2Int(p2))

if __name__ == "__main__":

# Define binary field GF(2^3)/x^3 + x + 1
setGF2(3, [1, 0, 1, 1])

# Alternative way to define GF(2^3)/x^3 + x + 1
setGF2(3, i2P(0b1011))

# Check if (x + 1)(x^2 + 1) == x^2
assert ldMultGF2([1, 1], [1, 0, 1]) == p2I([1, 0, 0])

# Check if (x^2 + x + 1)(x^2 + 1) == x^2 + x
assert ldMultGF2([1, 1, 1], [1, 0, 1]) == p2I([1, 1, 0])

# Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
setGF2(8, [1, 0, 0, 0, 1, 1, 0, 1, 1])

# Alternative way to define GF(2^8)/x^8 + x^4 + x^3 + x + 1
setGF2(8, i2P(0b100011011))

# Check if (x)(x^7 + x^2 + x + 1) == x^4 + x^2 + 1
assert ldMultGF2([1, 0], [1, 0, 0, 0, 0, 1, 1, 1]) == p2I([1, 0, 1, 0, 1])

# Check if (x + 1)(x^6 + x^5 + x^3 + x^2 + x) == x^7 + x^5 + x^4 + x
assert ldMultGF2([1, 1], [1, 1, 0, 1, 1, 1, 0]) == p2I([1, 0, 1, 1, 0, 0, 1, 0])

# Define binary field GF(2^571)/x^571 + x^10 + x^5 + x^2 + x
setGF2(571, [571, 10, 5, 2, 1])

# Calculate the product of two polynomials in GF(2^571)/x^571 + x^10 + x^5 + x^2 + x,
# x^518 + x^447 + x^320 + x^209 + x^119 + x + 1 and x^287 + x^145 + x^82 + + x^44
print(int2Poly(hdMultGF2([518, 447, 320, 209, 119, 1, 0], [287, 145, 82, 44])))

The output of the above script is:

[562, 529, 496, 491, 465, 406, 402, 364, 354, 291, 288, 287, 264, 253, 244,
239, 235, 201, 173, 168, 165, 164, 163, 146, 145, 102, 97, 94, 93, 83, 82,
46, 45, 44, 41, 39, 38, 37, 34, 30, 26, 23, 22]

This means that the product of the polynomials $x^{518} + x^{447} + x^{320} + x^{209} + x^{119} + x + 1$ and $x^{287} + x^{145} + x^{82} + x^{44}$ is:

x^562 + x^529 + x^496 + x^491 + x^465 + x^406 + x^402 + x^364 + x^354 +
x^291 + x^288 + x^287 + x^264 + x^253 + x^244 + x^239 + x^236 + x^235 +
x^201 + x^173 + x^168 + x^165 + x^164 + x^163 + x^146 + x^145 + x^102 +
x^97 + x^94 + x^93 + x^83 + x^82 + x^46 + x^45 + x^44 + x^41 + x^39 +
x^38 + x^37 + x^34 + x^30 + x^26 + x^23 + x^22