diff --git a/src/gf256.py b/src/gf256.py --- a/src/gf256.py +++ b/src/gf256.py @@ -3,47 +3,47 @@ """Arithmetic operations on Galois Field 2**8. See https://en.wikipedia.org/wiki/Finite_field_arithmetic""" -def _gfmul(a,b): +def _gfmul(a, b): """Basic multiplication. Russian peasant algorithm.""" - res=0 + res = 0 while a and b: - if b&1: res^=a - if a&0x80: a=0xff&(a<<1)^0x1b - else: a<<=1 - b>>=1 + if b&1: res ^= a + if a&0x80: a = 0xff&(a<<1)^0x1b + else: a <<= 1 + b >>= 1 return res -g=3 # generator -E=[None]*256 # exponentials -L=[None]*256 # logarithms -acc=1 +g = 3 # generator +E = [None]*256 # exponentials +L = [None]*256 # logarithms +acc = 1 for i in range(256): - E[i]=acc - L[acc]=i - acc=_gfmul(acc, g) -L[1]=0 -inv=[E[255-L[i]] if i!=0 else None for i in range(256)] # multiplicative inverse + E[i] = acc + L[acc] = i + acc = _gfmul(acc, g) +L[1] = 0 +inv = [E[255-L[i]] if i != 0 else None for i in range(256)] # multiplicative inverse def gfmul(a, b): """Fast multiplication. Basic multiplication is expensive. a*b==g**(log(a)+log(b))""" assert 0<=a<=255, 0<=b<=255 if a==0 or b==0: return 0 - t=L[a]+L[b] - if t>255: t-=255 + t = L[a]+L[b] + if t>255: t -= 255 return E[t] -def evaluate(coefs,x): +def evaluate(coefs, x): """Evaluate polynomial's value at x. :param coefs: [a0, a1, ...].""" - res=0 - xK=1 + res = 0 + xK = 1 for a in coefs: - res^=gfmul(a,xK) - xK=gfmul(xK,x) + res ^= gfmul(a, xK) + xK = gfmul(xK, x) return res @@ -51,14 +51,14 @@ def getConstantCoef(*points): """Compute constant polynomial coefficient given the points. See https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing#Computationally_Efficient_Approach""" - k=len(points) - res=0 + k = len(points) + res = 0 for i in range(k): - (x,y)=points[i] - prod=1 + (x, y) = points[i] + prod = 1 for j in range(k): if i==j: continue - (xj,yj)=points[j] - prod=gfmul(prod, (gfmul(xj,inv[xj^x]))) - res^=gfmul(y,prod) + (xj, yj) = points[j] + prod = gfmul(prod, (gfmul(xj, inv[xj^x]))) + res ^= gfmul(y, prod) return res