Shamir密钥分享方案的分析与实现.pdf

2023年9月计算机应用文摘第39卷第17 期Shamir密钥分享方案的分析与实现黄绍龙，曹建立（洛阳师范学院数学科学学院,河南洛阳47 1934)摘要：文章讨论了Shamir密钥分享方案中的恢复主密钥过程，主要利用Cramer法则求解有限域GF(p)上关于拉格朗日插值多项式系数的线性方程组来确定主密钥，给出了解的存在性证明，并在MATLAB环境下进行了实现。关键词：密钥分享；有限域；克拉默法则；乘法逆元；扩展的欧几里得算法中图法分类号：TP311Analysis and implementation of Shamir key sharing scheme(Faculty of Mathematical Sciences,Luoyang Normal University,Luoyang,Henan 471934,China)Abstract:This paper mainly introduces how to solve linear system of equations with unknowns ofcoefficients in Lagrange interpolation polynomial using Cramers Rule over finite fields GF(p),andprograms the functions in MATLAB to carry the idea out.Key words:key sharing,finite fields,Cramers Rule,multiplicative inverse,extended Euclideanalgorithm并在MATLAB环境下编写函数对其进行了实现。1引言2算法分析安全且可靠的密钥分发和管理机制是保证网络安全的重要环节。一般来说，重要的决策需要足够多的人意见一致才能够实施。例如，发射核武器的按钮只由一个人掌握是非常危险的。通常而言，一个主密钥要分解成若干子密钥分别由若干人掌握，只有足够多的人把子密钥放在一起才能获取主密钥，即密钥共享问题。1979年,Shamir提出一种门限为t的密钥分享方案,其又被称作(t,n）阈值方案。该方案非常适合一组必须进行合作但具有利益冲突并相互怀疑的个体间的应用场景。它基于有限域GF（p）上的拉格朗日插值多项式进行子密钥的生成和主密钥的恢复，在理论上它具有无条件的安全性。在有限域GF（p）上进行的运算是封闭的，因为只包含整数运算，不会像在实数域上产生误差,所以具有较高的可靠性和效率。本文讨论Shamir密钥分享方案的恢复主密钥过程,利用Cramer法则求解有限域GF（p）上关于拉格朗日插值多项式系数的线性方程组来确定主密钥,给出了有限域GF(p)上解的存在性证明以及求解方法，文献标识码：AHUANG Shaolong,CAO Jianli有限域在密码学中发挥了重要的作用。大量的密码学算法依赖有限域的性质，尤其是高级加密标准（A ES)和椭圆曲线密码学。有限域是域的子集,与有理数域、实数域和复数域一样,具有域的公共性质，但有限域包含有限数目的元素，使其具有许多特别的性质。有一类阶为素数p的有限域包含0,1,2，,p-1这p个元素,记作GF（p），可定义其上模p的加法和乘法运算。一些非对称加密算法使用CF（p）有限域 1 2 OShamir给出的基于GF（p）上拉格朗日插值公式的密钥分享方案是：有n个人需要分享主密钥，记第i个人为A,(1in)。控制中心随机选取 GF(p)中的一个元素k,并将其作为主密钥，同时随机选取一个t-1(tn)次拉格朗日插值多项式：h(x)=o+a1 x+a-2x*-+a-1-x-(a;E GF(p),at-1+0)(1)取o为主密钥k(（即h(0)=k),控制中心再取 GF(p)中n个不同的非零元素x1,x2，,x n,并将p,1，基金项目：河南省自然科学基金（2 12 30 0 410 0 6 2）(10)2023年第17 期x2，,x n 公开。针对每个i(1in),控制中心把yi=（h(;)modp)秘密分配给A;,并将其作为A;的子密钥。由此可知：（1)任意t个人联手可以直接算出主密钥；(2)如果l(1lt-1)个人联手,不能得到主密钥的任何信息 3 5在Shamir的密钥分享方案中,t个人联手恢复主密钥，也就是要得到拉格朗日插值多项式h（）的常数项，需要解有限域GF（p）上形如Cx=b的t元线性方程组,其中C为系数矩阵;b为常数项列矩阵,由t个人的子密钥构成;x为多项式h（)的系数构成的列矩阵，x是未知量。其中：11X2M=(m;)ixt=21x31C=(cj)txt=(mjmod p)xtaoa1x=a2at-1yo1b=y2Ly2.1解的存在性证明因为cj=m;(mod p),利用行列式的标准定义有：det(M)=s,sign(0)m1o,m2o2-mto,gES,那么：det(M)mod p=(Z sign(o)m1o,ma2-mo,)modP=(Esign(0)m1o,mg,*-mo,mod)mod pQES,=(Z,sign(o)(mio,mod p).(mua,mod p)mod pGES,=det(C)mod p因此得到det(M)=det(C)(mod p)由于矩阵M的行列式是范德蒙德行列式，x1，x2，x，中的任意一项均取自CF(p)且两两互不相计算机应用文摘同,可知 det(M)=x;和x,满足-p(x;-x;)p,且p是素数,所以 det(M)modp0,由同余关系式（7)可知det(C)modp0。由于线性方程组的系数行列式不为零,可知 Cx=b 的解是存在且唯一的。2.2习求解的方法C;是用常数项列矩阵b替换C中的第i列而得到的方阵，根据克拉默法则有：det(C,)a;=det(C)mod p.2QES,105I（x;-x;）0。又因为任意的1jitmod p=（d e t （C;）:(det(C)-l)mod p(0it-1)(8)式中,除以det(C)mod p相当于乘以det(C)的模p意义下的乘法逆元(det(C)）-1。(2)2.3计算GF(p）中元素的乘法逆元的方法利用扩展的欧几里得算法可以得到GF(p）中元素的乘法逆元。(3)对于给定的正整数和b,扩展的欧几里得算法不仅可以计算出它们的最大公约数d,还可以计算出另外的2 个整数x和y,且满足以下方程：(4)ax+by=d=gcd(a,b)很明显，x和y是异号的。根据整数的带余除法，假设在第i步得到的整数x；和y；满足r;=ax;+by;，有以下序列：a=qib+r1(5)b=q2fi+r2Ti=q3r2+r3：In-2=qn/n-1+rn(In-1=In+1n+0移项可得递推关系式：T;=ri-2-ri-1qi将 ri-2=axi-2+by i-2 和 Ti-1=axi-1+byi-1 代人式(11)可得：T;=a(xi-2-q;xi-1)+b(yi-2-qiyi-1)而根据假设,r;=ax;+byi,对比可得递推公式：x;=xi-2-q;xi-1,y;=yi-2-qiyi-1初始条件为：r-1=a,x-1=1,y-1=0(ro=b,xo=0,yo=1(6)计算会在余数为0 时停止,此时正整数和b的最大公因数为d=gcd(a,b)=rn,同时算法也确定了d(7)=r,=ax,+byn。因此,在式(7)中x=xn,y=yn。在有限域 GF(p)中,aE GF(p),取 b=p,则 gcd(a,b)=gcd(a,p)=1=ax+py,(ax+py)mod p=1,即 ax(9)Ti=ax;+by1T2=ax2+by2T3=ax3+by3：T,=ax,+byn(14)(11)(12)(13)106+py=ax=1(modp）。可能为负整数,而我们需要确定在GF(p)中对应的乘法逆元,因此取乘法逆元为xmodp可满足要求,故GF（p）中元素的乘法逆元a-1就是 xmod p。3算法实现本文采用MATLAB环境实现Shamir密钥分享方案中的主密钥恢复过程。由算法分析可知，实现恢复主密钥的关键是变换系数矩阵和计算乘法逆元。利用矩阵特定列的赋值可以得到C;。利用扩展的欧几里得算法,可实现有限域GF（p）中元素乘法逆元的计算。(1)扩展的欧几里得算法。根据算法分析，利用MATLAB实现扩展的欧几里得算法的函数参见如下xgcd 函数。例如，x,y=xgcd(550,1 759)的返回值是x=355,y=-111。function x,y=xgcd(a,b)r0=a;rl=b;x0=1;y0=0;xl=0;yl=l;while 1r=mod(r0,r1);if r=0break;endq=floor(r0/r1);x=x0-q*xl;y=yo-q*yl;r0=rl;rl=r;x0=xl;xl=x;y0=yl;yl=y;end(2)求有限域GF(p)中元素的乘法逆元。利用MATLAB求有限域GF（p）中元素的乘法逆元的函数参见如下inverse_mod函数。例如,i=inverse_mod(550,1759)的返回值是i=355,表示在有限域GF（17 59）中550 的乘法逆元是355。function i=inverse_mod(a,b)%,求出a 的乘法逆元(mod b),要求 1=abm,n=xgcd(a,b);i=mod(m,b);(3)求解有限域GF(p)上线性方程组以恢复主密钥的主程序。主程序通过以下4个步骤进行。输入系数矩阵C、常数项列矩阵b和有限域GF(p)的阶数p。计算系数矩阵的行列式的值det(C)及其对应GF(p)中的乘法逆元(det(C)-l。用常数项列矩阵b依次替换系数矩阵的第i列得到 C;,计算 a;=(det(C;）（d e t(C)）-1)mo d p(0计算机应用文摘it-1),将结果存储在行矩阵中。输出存储拉格朗日插值多项式系数的行矩阵。例如,取 x1=2,x2=5,x3=8,x4=9,x5=11,b=27,20,13,10,9,p=29,则;1241525M=(m86451211981729L1111211 33114 6411248161525916C=(ci;)=(m;mod29)186197192347L11152625(16)主程序运行时将上述参数输人可得解向量6,5,3,2,8,从而恢复出主密钥k=o=6。求解有限域GF(p）上线性方程组的主程序实现代码如下：clear;a=;p=29;A=input(输入系数矩阵）；B=input（输人常数项列矩阵）；p=input(输人素数模);d=inverse_mod(det(A),p);for n=1:size(A,2)%size(A,2)表示矩阵A的列数A1=A;A1(:,n)=B;%常数项列矩阵替换系数矩阵A的第n列存储为A1a(end+1)=mod(mod(det(A1),p)*d,p);%计算得到的多项式系数依次存放在行矩阵a中enddisp(a);4结束语Shamir密钥分享方案是安全多方计算问题，在理论上它具有无条件的安全性，在电子投票和可验证随机数生成方面被广泛应用。因此,求解有限域GF(p)上关于拉格朗日插值多项式系数的线性方程组来确定主密钥,在密码学的理论和实践研究过程中都有重要的意义。本文提出的利用克拉默法则求解的方法只(下转第10 9 页)2023年第17 期8161256254 0966 561(15)2023年第17 期时的耗能处于31.0 6 8 4.2 3GJ之间；而在运行策略二下，热力站每2 个小时的耗能处于2 9.6 3 7 1.2 8 GJ之间。这表明基于负荷预测热力站调控系统的应用相比原系统有更低的耗热量。此外,经过对运行策略一耗热量与运行策略二耗热量的整体对比发现，运行策略二下每2 个小时的节热率在3.2 9%16.2 4%，特别是在12:0 0 至16：0 0 时间段内，节热率达到了10%。这表明基于负荷预测的热力站调控系统应用后，节热效果明显。