Files
@ 90fb179128d4
Branch filter:
Location: Shamira/src/gf256.py - annotation
90fb179128d4
1.3 KiB
text/x-python
core tests and related fixes
dae5ae50a2cf 9ccd379021d5 9ccd379021d5 dae5ae50a2cf dae5ae50a2cf dae5ae50a2cf dae5ae50a2cf dae5ae50a2cf dae5ae50a2cf dae5ae50a2cf dae5ae50a2cf dae5ae50a2cf 86a5417085ef 86a5417085ef 9ccd379021d5 9ccd379021d5 9ccd379021d5 86a5417085ef 86a5417085ef 86a5417085ef 86a5417085ef dae5ae50a2cf 86a5417085ef 9ccd379021d5 86a5417085ef 86a5417085ef dae5ae50a2cf 9ccd379021d5 90fb179128d4 86a5417085ef 86a5417085ef 86a5417085ef 86a5417085ef 438dcebc9c63 438dcebc9c63 438dcebc9c63 9ccd379021d5 9ccd379021d5 9ccd379021d5 438dcebc9c63 438dcebc9c63 438dcebc9c63 dae5ae50a2cf dae5ae50a2cf 438dcebc9c63 db65075fe7e0 db65075fe7e0 9ccd379021d5 dae5ae50a2cf dae5ae50a2cf dae5ae50a2cf 9ccd379021d5 db65075fe7e0 db65075fe7e0 db65075fe7e0 db65075fe7e0 db65075fe7e0 db65075fe7e0 db65075fe7e0 dae5ae50a2cf dae5ae50a2cf db65075fe7e0 | """Arithmetic operations on Galois Field 2**8. See https://en.wikipedia.org/wiki/Finite_field_arithmetic"""
def _gfmul(a,b):
"""Basic multiplication. Russian peasant algorithm."""
res=0
while a and b:
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
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
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
return E[t]
def evaluate(coefs,x):
"""Evaluate polynomial's value at x.
:param coefs: [a0, a1, ...]."""
res=0
xK=1
for a in coefs:
res^=gfmul(a,xK)
xK=gfmul(xK,x)
return res
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
for i in range(k):
(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)
return res
|