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 = divmod(b, a), a
  64         y0, y1 = y1, y0 - q * y1
  65         x0, x1 = x1, x0 - q * x1
  66     return b, x0, y0
  67
  68
  69 if __name__ == "__main__":
  70
  71     # Define binary field GF(2^3)/x^3 + x + 1
  72     setGF2(0b1011) # degree 3
  73
  74     # Evaluate the product (x^2 + x + 1)(x^2 + 1)
  75     x = multGF2(0b111, 0b101)
  76     print("%02x" % x)
  77
  78     # Define binary field GF(2^8)/x^8 + x^4 + x^3 + x + 1
  79     # (used in the Advanced Encryption Standard-AES)
  80     setGF2(0b100011011) # degree 8
  81
  82     # Evaluate the product (x^7 + x^2)(x^7 + x + 1)
  83     x = 0b10000100
  84     y = 0b10000011
  85     z = multGF2(x, y)
  86     print("%02x * %02x = %02x" % (x, y, z))
  87
  88     # divide z by y into result/remainder
  89     res, rem = divmodGF2(z, y)
  90     print("%02x / %02x = (%02x, %02x)" % (z, y, res, rem))
  91
  92     # reconstruct x by multiplying divided result by y and adding the remainder
  93     x1 = multGF2(res, y)
  94     print("%02x == %02x" % (z, x1 ^ rem))
  95