Shamira Changeset - dae5ae50a2cf

Changeset - dae5ae50a2cf

Parent rev.

Child rev.

[Not reviewed]

default

0 1 0

Laman - 7 years ago 2017-09-23 16:22:59

linked to finite field arithmetic explanation at wikipedia

1 file changed with 19 insertions and 18 deletions:

src/gf256.py

0 comments (0 inline, 0 general)

src/gf256.py

➞

Show inline comments

 """Arithmetic operations on Galois Field 2**8."""
+"""Arithmetic operations on Galois Field 2**8. See https://en.wikipedia.org/wiki/Finite_field_arithmetic"""
 def _ffmul(a, b):
 	"""Basic multiplication."""
 	r=0
 	while a!=0:
 		if (a&1)!=0: r^=b
 		t=b&0x80
 		b=(b<<1)&255
 		if t!=0: b^=0x1b
 		a>>=1
 	return r
 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=_ffmul(acc, g)
+	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 ffmul(a, b):
+def gfmul(a, b):
 	"""Fast multiplication. Basic multiplication is expensive. a*b==g**(log(a)+log(b))"""
 	if a==0 or b==0: return 0
 	t=L[a]+L[b]
 	if t>255: t-=255
 	return E[t]
@@ @@ -37,24 +36,26 @@ def evaluate(coefs,x): @@
 	"""Evaluate polynomial's value at x.
 	:param coefs: [a0, a1, ...]."""
 	res=0
 	xK=1
 	for a in coefs:
 		res^=ffmul(a,xK)
 		xK=ffmul(xK,x)
 		res^=gfmul(a,xK)
 		xK=gfmul(xK,x)
 	return res
 def getConstantCoef(*points):
 	"""Compute constant polynomial coefficient given the 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=ffmul(prod, (ffmul(xj,inv[xj^x])))
 		res^=ffmul(y,prod)
 			prod=gfmul(prod, (gfmul(xj,inv[xj^x])))
 		res^=gfmul(y,prod)
 	return res

0 comments (0 inline, 0 general)