openpower/sv/gf2.py

   1 from functools import reduce
   2
   3 def gf_degree(a) :
   4   res = 0
   5   a >>= 1
   6   while (a != 0) :
   7     a >>= 1;
   8     res += 1;
   9   return res
  10
  11 # constants used in the multGF2 function
  12 mask1 = mask2 = polyred = None
  13
  14 def setGF2(irPoly):
  15     """Define parameters of binary finite field GF(2^m)/g(x)
  16        - irPoly: coefficients of irreducible polynomial g(x)
  17     """
  18     # degree: extension degree of binary field
  19     degree = gf_degree(irPoly)
  20
  21     def i2P(sInt):
  22         """Convert an integer into a polynomial"""
  23         return [(sInt >> i) & 1
  24                 for i in reversed(range(sInt.bit_length()))]
  25
  26     global mask1, mask2, polyred
  27     mask1 = mask2 = 1 << degree
  28     mask2 -= 1
  29     polyred = reduce(lambda x, y: (x << 1) + y, i2P(irPoly)[1:])
  30
  31
  32 def multGF2(p1, p2):
  33     """Multiply two polynomials in GF(2^m)/g(x)"""
  34     p = 0
  35     while p2:
  36         if p2 & 1:
  37             p ^= p1
  38         p1 <<= 1
  39         if p1 & mask1:
  40             p1 ^= polyred
  41         p2 >>= 1
  42     return p & mask2
  43
  44
  45 def divmodGF2(f, v):
  46     fDegree, vDegree = gf_degree(f), gf_degree(v)
  47     res, rem = 0, f
  48     i = fDegree
  49     mask = 1 << i
  50     while (i >= vDegree):
  51         if (mask & rem):
  52             res ^= (1 << (i - vDegree))
  53             rem ^= ( v << (i - vDegree))
  54         i -= 1
  55         mask >>= 1
  56     return (res, rem)
  57
  58
  59 def xgcd(a, b):
  60     """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
  61     x0, x1, y0, y1 = 0, 1, 1, 0
  62     while a != 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)
  66     return b, x0, y0
  67
  68 def gf_invert(a, mod=0x11B) :
  69
  70   mod_degree = gf_degree(mod) - 1
  71   v = mod
  72   g1 = 1
  73   g2 = 0
  74   j = gf_degree(a) - mod_degree
  75
  76   while (a != 1) :
  77     # print (bin(a), j, bin(g1), bin(g2))
  78     if (j < 0) :
  79       a, v = v, a
  80       g1, g2 = g2, g1
  81       j = -j
  82
  83     a ^= v << j
  84     g1 ^= g2 << j
  85
  86
  87     j = gf_degree(a) - gf_degree(v)
  88
  89   a %= (1<<mod_degree)  # Emulating 8-bit overflow
  90   g1 %= (1<<mod_degree) # Emulating 8-bit overflow
  91   return g1
  92
  93
  94 if __name__ == "__main__":
  95
  96     # Define binary field GF(2^3)/x^3 + x + 1
  97     setGF2(0b1011) # degree 3
  98
  99     # Evaluate the product (x^2 + x + 1)(x^2 + 1)
 100     x = multGF2(0b111, 0b101)
 101     print("%02x" % x)
 102
 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
 106
 107     # Evaluate the product (x^7 + x^2)(x^7 + x + 1)
 108     x = 0b10000100
 109     y = 0b10000011
 110     z = multGF2(x, y)
 111     print("%02x * %02x = %02x" % (x, y, z))
 112
 113     # divide z by y into result/remainder
 114     res, rem = divmodGF2(z, y)
 115     print("%02x / %02x = (%02x, %02x)" % (z, y, res, rem))
 116
 117     # reconstruct x by multiplying divided result by y and adding the remainder
 118     x1 = multGF2(res, y)
 119     print("%02x == %02x" % (z, x1 ^ rem))
 120
 121
 122     print(xgcd(x, y))
 123
 124
 125     exit(0)
 126
 127     #for i in range(1, 256):
 128     #   print (i, gf_invert(i))
 129
 130     # this is not quite functional as expected, gf_invert is incomplete
 131     y1 = gf_invert(y, polyred)
 132     z1 = multGF2(z, y1)
 133     print(hex(y1), hex(z1))
 134