shamir Algorithm is introduced
Lagrangian interpolation decryption
Use of G_hash yes National secret algorithm SM3,
g_p yes Miller_Rabin Algorithm generates a large prime algorithm
ModReverse yes Generating inverse element algorithm
from random import randint
from algorithm.g_hash import G_hash
from algorithm.g_keypairs import g_p, ModReverse
""" Instructions Only encryption and decryption 64 position hash value When encrypting , G_si(S,n,k) Encrypt data S, to n personal , At least k Can decrypt return share[] Yes n term When decrypting shamir_decrypt(Share) Share by share[] At least k Array of elements Return the value to be encrypted """
# Enter the data to be protected , Generate secret shared data n strip , structure k Multivariate polynomial
# The prime number generated is （2**64,2**65） Namely 16*16 Bit binary number hash by 64*16
# hold hash It is divided into 4 End 16*16 encryption
# The return is si yes s[1][i]+s[2][i]+s[3][i]+s[4][i]
# Decryption is use k-1 individual i,s[1][i] （0<i<k） figure out hash[1]..
def G_si(S,n,k):
nimi_key=k
hash =[int(S[0:16], 16), int(S[16:32], 16), int(S[32:48], 16), int(S[48:64], 16)]
# print(" Secret ：hash value ",hash)
a=[0]
prime=g_p()
s = [prime,[], [], [], []]
# print("prime",prime)
# Generate k-1 A coefficient of --> a[1 <---> k-1] a0 Is a secret value
while k-1:
temp=randint(2**10,prime)
if temp not in a:
a.append(temp)
k=k-1
# print(a)
# Generate shared key Si n A little bit
# hash_num Namely s[] The subscript , Record 4 Group n A little bit
# i Namely x Value
# hash[] Is the secret value
# j Namely x The first few items of ,x Several power
# The last generation s[[prime,y1,y2,y3...],[],[],[]]
for hash_num in range(1,5):
for i in range(1,n+1):
temp=hash[hash_num-1]
for j in range(1,k):
temp=(temp+a[j]*(i**j))%prime
s[hash_num].append([i,temp])
share=[]
for i in range(0, n):
share.append([[s[0],nimi_key], s[1][i], s[2][i], s[3][i], s[4][i]])
# print("share=",share)
# share = [[ prime number , nimikey],[point1],[point2],point[3],point[4]] * n individual key
return share
def shamir_decrypt(s):
# s=[[ prime number , nimikey],[point1],[point2],point[3],point[4]] * n
# k Is a polynomial coefficient a0+ a1*x^1+....a(k-1)*x^(k-1)
k=s[0][0][1]
p=s[0][0][0]
if len(s)<k:
print(" Not enough keys , Can't decrypt ")
return
# Obtain the abscissa value and the corresponding s Subscript [x,i] Array of
x=[]
for i in range(len(s)):
x.append([s[i][1][0],i])
# print(" The abscissa has ",x)
hash = ""
for hash_i in range(1,5):
L = 0
# j Corresponding x Abscissa And Storage y It's worth it i Subscript
for j in x:
Lx=1
Lx1=1
# Except Abscissa for j Of x
xx=[]
for some in x:
if some!=j:
xx.append(some)
# print(xx)
for i in xx:
Lx=(-1)*Lx*i[0]
Lx1=Lx1*(j[0]-i[0])
# Lj Of molecular Lx The denominator Lx1
Lx=(Lx+p)%p
Lx1=(Lx1+p)%p
# print("Lx,",Lx,"Lx1",Lx1)
Lx1=ModReverse(Lx1,p)
L=(L+s[j[1]][hash_i][1]*Lx*Lx1)%p
# print(L)
hash=hash+str(hex(L))[2:]
# print(" length ",len(hash))
return hash
# hash=G_hash("zazal")
# print(hash)
# # print(int(hash,16))
#
# share=G_si(hash,3,3)
#
# print(shamir_decrypt(share))
# s=[share[0],share[1],share[2]]
#
#
# print(shamir_decrypt(s))
