shamir秘密共享算法_密码学算法：shamir门限密钥共享算法

算法原理

(t，w)门限密钥共享方案，该方案是Shamir在1979年提出。Shamir(t，w)门限方案是通过构造一个t-1次多项式，将需要共享的主密钥S作为常数项，碎片密钥分成w部分给w个参与者，当碎片密钥数量大于或者等于t的话，就可以求解出这个主密钥S。

子密钥生成

构造多项式

其中s为密钥，p为素数(s

取w个不相等的x带入F(x)中，得到w组子密钥，分发给w个人保管

将p公开，销毁子密钥生成多项式，每个人保管自己的子密钥

恢复密钥

构造多项式

此多项式为上面多项式的变形

取x=0，代入t组密钥可以求解出F(0)，也就是主密钥s

算法实现代码

python代码

import random
import math

# 输入p, w, t, s 程序入口 
def runCode(predefineData):
    p = 0
    w = 0
    t = 0
    s = 0
    if not predefineData:
        tempstr = input("输入素数(p)n")
        p = int(tempstr)
        p = testPrimality(p)    

        w = input("输入持有子密钥的人数n")
        t = input("请输入门限人数n")

        
        if(int(w)>=int(t)):
            print("建立 (" + str(t) + ", " + str(w) + ")门限密钥")
            s = input("输入你的主密钥(s))
            s = int(s)
            print("secret:",s)else:
            print("门限值大于拥有密钥的人数")
            runCode([])
        predefineData = [w,t,p,s]else:
        w = predefineData[0]
        t = predefineData[1]
        p = predefineData[2]
        s = predefineData[3]
    generatesubKey(t,w,s,p) # 生成子密钥
    generateMainKey(s,p,t)  # 求解主密钥# 生成子密钥def generatesubKey(t_str,w_str,s,p):
    a_j=[0]     # 存放多项式系数列表
    x_i=[0]     # 多项式x取值列表
    t = int(t_str)
    w = int(w_str)
    x_i = randomList(1,w,w,True)      # 获取x 不相同
    a_j = randomList(1,5,t-1,False)   # 多项式参数
    x_i.sort()      # 升序排列x
    print("x_i:",x_i)
    print("a_j:",a_j)
    subKey = {}     #子密钥字典for i in range(0,w):
        polynomialSum = s;      #多项式求和
        x = x_i[i]for j in range(0,t-1):
            a = a_j[j]
            polynomialSum += (a*math.pow(x,j+1))
        regsubK = polynomialSum % p      # 得到其中一个子密钥
        subKey[x] = int(regsubK)         # 添加到密钥字典# print(subKey)# 处理输出多项式字符串
    polynomialStr = "f(x) = ("+str(s)+" + "for i in range(0,t-1):
        polynomialStr += str(a_j[i])+"x^"+str(i+1)+" + "
    polynomialStr = "".join(list(polynomialStr)[:-3])
    polynomialStr += ") mod("+str(p)+")"
    print("表达式：",polynomialStr)
    print("生成的密钥：n")# 打印子密钥for key,value in subKey.items():
        print("("+str(key)+","+str(value)+")")return subKey# 获取子密钥def getSubset(t):
    print("n输入大于"+t+"组密钥进行解密")
    Subset_RAWstr = input("n获取子密钥n请输入x值n")
    Subset_str = Subset_RAWstr.split()
    Subset = {}
    Subset_mm = input("请输入x对应的子密钥n")
    Subset_mm = Subset_mm.split()
    ind = 0for ID in Subset_str:try:
            ID = int(ID)
            Subset_mm[ind] = int(Subset_mm[ind])
            Subset[ID] = Subset_mm[ind]
            ind = ind +1except:
            print("Error in list entered, try again")
            Subset = getSubset(t)#ADD RECURSIVE FUNCTIONreturn Subset# 生成主密钥def generateMainKey(s,p,t):
    x_list = []
    y_list = []
    subSet = getSubset(t)   # 输入密钥
    recoveredS = 0# 遍历输入密钥字典 生成x yfor key,value in subSet.items():
        x_list.append(key)
        y_list.append(value)
        print("("+str(key)+","+str(value)+")")# 生成解密表达式 for i in range(0,len(x_list)):
        x_i = x_list[i]
        temp_j = 1for j in range(0,len(x_list)):if(j!=i):
                x_j = x_list[j]
                temp_one = float(x_j)/(x_j-x_i)
                temp_j = temp_j * temp_one# print("("+str(x_i)+","+str(y_list[i])+"):",y_list[i] * temp_j)
        recoveredS += y_list[i] * temp_j# print("recoveredS ",recoveredS)
    recoveredS = int(round(recoveredS)) # 四舍五入 int
    recoveredS = recoveredS % p 
    print("密钥值为: ",recoveredS)if recoveredS == s:
        print("解密成功n")else:
        print("解密失败n")
    resp = input("是否再次解密？n")if resp.upper() == "Y":
        generateMainKey(s,p,t)else:pass
    print("OVERn")return recoveredS# 检测素数def testPrimality(p):
    temp = p;
    p = math.sqrt(p)
    p = int(p)for i in range(2, (p+1)):
        f = temp / iif(f.is_integer()):
            newP = input("Enter prime number")
            newP = int(newP)
            newP = testPrimality(newP)
            temp = newPbreakreturn temp# 得到一个随机数 state: true 不重复 false 可以重复def getRandomNum(xlist, start, stop, state): # x_subi = []
    x = random.randint(start, stop)if state is True:if not x in xlist:return xelse:
            x = getRandomNum(xlist,start, stop, state)return xelse:return x# 得到随机列表 state: true 不重复 false 可以重复def randomList(start,stop,length,state):if length>=0:
        length=int(length)
    start, stop = (int(start), int(stop)) if start <= stop else (int(stop), int(start))
    random_list = []for i in range(length):
        num = getRandomNum(random_list,start, stop, state)  
        random_list.append(num)return random_list# runCode(["5","3",11,5])
runCode([])

解密成功

输入素数(p)
11
输入持有子密钥的人数
5
请输入门限人数
3
建立 (3, 5)门限密钥  
输入你的主密钥(s)10
secret: 10
x_i: [1, 2, 3, 4, 5]
a_j: [1, 1]
表达式：f(x) = (10 + 1x^1 + 1x^2) mod(11)
生成的密钥：

(1,1)
(2,5)
(3,0)
(4,8)
(5,7)

输入大于3组密钥进行解密

获取子密钥
请输入x值
1 2 3
请输入x对应的子密钥
1 5 0
(1,1)
(2,5)
(3,0)
密钥值为:  10
解密成功

解密失败

是否再次解密？
Y

输入大于3组密钥进行解密

获取子密钥
请输入x值
1 2
请输入x对应的子密钥
1 5
(1,1)
(2,5)
密钥值为:  8
解密失败

对你有用的话点个“在看”和“喜欢”吧！?