1 from functools
import reduce
11 # constants used in the multGF2 function
12 mask1
= mask2
= polyred
= None
15 """Define parameters of binary finite field GF(2^m)/g(x)
16 - irPoly: coefficients of irreducible polynomial g(x)
18 # degree: extension degree of binary field
19 degree
= gf_degree(irPoly
)
22 """Convert an integer into a polynomial"""
23 return [(sInt
>> i
) & 1
24 for i
in reversed(range(sInt
.bit_length()))]
26 global mask1
, mask2
, polyred
27 mask1
= mask2
= 1 << degree
29 polyred
= reduce(lambda x
, y
: (x
<< 1) + y
, i2P(irPoly
)[1:])
33 """Multiply two polynomials in GF(2^m)/g(x)"""
46 fDegree
, vDegree
= gf_degree(f
), gf_degree(v
)
52 res ^
= (1 << (i
- vDegree
))
53 rem ^
= ( v
<< (i
- vDegree
))
60 """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
61 x0
, x1
, y0
, y1
= 0, 1, 1, 0
63 (q
, a
), b
= divmodGF2(b
, a
), a
64 y0
, y1
= y1
, y0 ^
multGF2(q
, y1
)
65 x0
, x1
= x1
, x0 ^
multGF2(q
, x1
)
68 def gf_invert(a
, mod
=0x11B) :
70 mod_degree
= gf_degree(mod
) - 1
74 j
= gf_degree(a
) - mod_degree
77 # print (bin(a), j, bin(g1), bin(g2))
87 j
= gf_degree(a
) - gf_degree(v
)
89 a
%= (1<<mod_degree
) # Emulating 8-bit overflow
90 g1
%= (1<<mod_degree
) # Emulating 8-bit overflow
94 if __name__
== "__main__":
96 # Define binary field GF(2^3)/x^3 + x + 1
97 setGF2(0b1011) # degree 3
99 # Evaluate the product (x^2 + x + 1)(x^2 + 1)
100 x
= multGF2(0b111, 0b101)
103 # Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
104 # (used in the Advanced Encryption Standard-AES)
105 setGF2(0b100011011) # degree 8
107 # Evaluate the product (x^7 + x^2)(x^7 + x + 1)
111 print("%02x * %02x = %02x" % (x
, y
, z
))
113 # divide z by y into result/remainder
114 res
, rem
= divmodGF2(z
, y
)
115 print("%02x / %02x = (%02x, %02x)" % (z
, y
, res
, rem
))
117 # reconstruct x by multiplying divided result by y and adding the remainder
119 print("%02x == %02x" % (z
, x1 ^ rem
))
127 #for i in range(1, 256):
128 # print (i, gf_invert(i))
130 # this is not quite functional as expected, gf_invert is incomplete
131 y1
= gf_invert(y
, polyred
)
133 print(hex(y1
), hex(z1
))