秘密共享方案

第13章秘密共享方案报告人：孙宗臣•有些场合，秘密不能由一个人独自拥有，必须由两人或多人同时参与才能打开秘密，这时都需要将秘密分给多人掌管，而且必须有一定人数的掌管秘密的人同时到场才能恢复这一秘密，这种技术就称为秘密分割(SECRETSPLITTING)，也称为秘密共享(SECRETSHARING)。例如：•导弹控制发射•开启核按钮•重要场所通行检验等•为了实现上述意义上的秘密共享，人们引入了门限方案(THRESHOLDSCHEME)的一般概念2/13.1引言•秘密分割门限方案的定义•定义1设秘密S被分成N个部分信息，每一部分信息称为一个子密钥或影子(SHAREORSHADOW)，由一个参与者持有，使得：•①由K个或多于K个参与者所持有的部分信息可重构S•②由少于K个参与者所持有的部分信息则无法重构S则称这种方案为(K,N)－秘密分割门限方案，K称为方案的门限值。•极端的情况下是(N,N)－秘密分割门限方案，此时用户必须都到场才能恢复密钥3/13.1引言•如果一个参与者或一组未经授权的参与者在猜测秘密S时，并不比局外人猜秘密时有优势，即•③由少于K个参与者所持有的部分秘密信息得不到秘密S的任何信息则称这个方案是完善的，即(K,N)－秘密分割门限方案是完善的•攻击者除了试图恢复秘密外，还可能从可靠性方面进行攻击，如果他能阻止多于N-K个人参与秘密恢复，则用户的秘密就难于恢复•所以(K,N)门限的安全性在于既要防止少于K个人合作恢复秘密，又要防止对T个人的攻击而阻碍秘密的恢复•当N=2T+1时K=T=(N-1)/2的取值最佳•秘密分割应该由可信第三方执行，或者托管设备完成。4/13.1引言13.1引言•秘密的分割假设是一个(K,N)门限方案•选取一个K－1次多项式F(X)＝A0+A1X+…+AK-1XK-1•该多项式有K个系数•令A0=F(0)=S，即把常数项指定为待分割的秘密•其它K－1个系数可随机选取•显然，对于该多项式，只要知道该多项式的K个互不相同的点的函数值F(XI)(I=1,2,…,K)，就可恢复F(X)•生成N个子秘密•任取N个不同的点XI(I=1,…,N)并计算函数值F(XI)(I=1,…,N)•则(XI,F(XI)),I=1,…,N,即为分割的N个子秘密•显然，这N个子秘密中的任意K个子秘密即可重构F(X)，从而可得秘密S5/13.2SHAMIR门限方案•SHAMIR门限方案基于多项式的LAGRANGE插值公式•插值：数学分析中的一个基本问题•已知一个函数(X)在K个互不相同的点的函数值(XI)(I=1,2,…,K)，寻求一个满足F(XI)＝(XI)(I=1,2,…,K)的函数F(X)来逼近(X)，F(X)称为(X)的插值函数，也称插值多项式•LAGRANGE插值：•已知(X)在K个互不相同的点的函数值(XI)(I=1,2,…,K)，可构造K-1次LAGRANGE插值多项式•显然，如果将函数(X)就选定F(X)，则差值多项式刚好完全恢复了多项式(X)＝F(X)6/kjllljlkjjxxxxxxf11)()(13.2SHAMIR门限方案•根据上述的思想，在有限域GF(Q)上实现上述方案，即可得到SHAMIR秘密分割门限方案•（1）秘密的分割•设GF(Q)是一有限域，其中Q是一个大素数，满足QN＋1•秘密S是在GF(Q)\{0}上均匀选取的一个随机数，表示为SRGF(Q)\{0}•令S等于常系数A0•其它K-1个系数A1,A2,…,AK-1的选取也满足AIRGF(Q)\{0}(I=1,…,K-1)•在GF(Q)上构造一个K-1次多项式F(X)＝A0+A1X+…+AK-1XK-1•N个参与者记为P1,P2,…,PN，其中PI分配到的子密钥为（I,F(I)）7/13.2SHAMIR门限方案•(2)秘密的恢复•如果任意K个参与者PI1,PI2,…,PIK(1I1I2…IKN)要想得到秘密S，可使用它们所拥有的K个子秘密{(IL,F(IL))|L=1,…,K}构造如下的线性方程组•A0＋A1(I1)＋…＋AK-1(I1)K-1=F(I1)•A0＋A1(I2)＋…＋AK-1(I2)K-1=F(I2)•……•A0＋A1(IK)＋…＋AK-1(IK)K-1=F(IK)（13-1）8/13.2SHAMIR门限方案•因为IL(L=1,…,K)均不相同，所以可由LAGRANGE插值公式构造如下的多项式：•F(X)＝从而可得秘密S＝F(0)然而参与者仅需知道F(X)的常数项F(0)而无需知道整个多项式F(X)，所以令X＝0，仅需以下表达式就可以求出S：•S=，（可以预计算不需保密）)(mod)(mod)(111qybqiiiifkjijkjlljllkjjj9/kjllljlkjjqiiixif11)(mod)(jb•方案的完善性分析•如果K-1个参与者想获得秘密S，他们可构造出由K-1个方程构成的线性方程组，其中有K个未知量•对GF(Q)中的任一值S0，可设F(0)＝S0，再加上上述的K-1个方程就可得到K个方程，并由LAGRANGE插值公式得出F(X)。因此对每一S0GF(Q)都有一个惟一的多项式满足13-1方程组•所以已知K-1个子密钥得不到关于秘密S的任何信息，因此这个方案是完善的。10/13.2SHAMIR门限方案•【例8－1】设门限K=3，份额数为N=5，模值Q=19，待分割的秘密S=11，随机选取A1=2，A2=7，可构造多项式•F(X)=(7X2+2X+11)MOD19•将秘密分割成5份•分别计算F(1)=(7×12+2×1+11)MOD19＝1•F(2)=(7×22+2×2+11)MOD19＝5•F(3)=(7×32+2×3+11)MOD19＝4•F(4)=(7×42+2×4+11)MOD19＝17•F(5)=(7×52+2×5+11)MOD19＝6•得5个子密钥。11/13.2SHAMIR门限方案13.2SHAMIR门限方案•秘密的恢复•如果知道其中的3个子密钥,如F(2)=5，F(3)＝4，F(5)＝6，就可重构F(X)，事实上我们可直接根据差值公式•计算S=F(0)kjllljlkjjkqiiiif111)(mod)()1(19mod)353252)5()535232)3()525323)2(()1(13fff12/1113.2SHAMIR门限方案•简化的（T,T）门限方案：1.D秘密的选取（独立随机选取）中的T-1个元素，记为，2.D计算，3.对于，D把共享的值发给。中国剩余定理，又称孙子定理设m1,m2,…,mk是k个两两互素的正整数，m=m1m2…mk,Mi(i=1,…,k)满足m=miMi，则同余式组x=b1(modm1)x=b2(modm2)…x=bk(modmk)有唯一解：x=M1M1b1+M2M2b2+…+MkMkbk(modm)其中MiMi=1modmi(i=1,2,…,k)14/(补充)基于中国剩余定理的门限方案1.参数的选择设m1m2…mn是n个大于1的整数，满足(mi,mj)＝1(对任意的i，j，i≠j)，及两两互素，和m1m2…mkmnmn-1…mn-k+2注意这里的条件m1m2…mn是必须的，在此条件下，m1m2…mkmnmn-1…mn-k+2表明最小的k个数的乘积也比最大的k-1个数的乘积大显然，m1,m2,…,mn中任意k个数的乘积都比m1m2…mk大15/(补充)基于中国剩余定理的门限方案2.秘密的分割设s是待分割的秘密数据，令s满足mnmn-1…mn-k+2sm1m2…mk即s比最大的k-1个数的成绩大，同时比最小的k个数的乘积小从而：对任意k个数的乘积T，s＝smodT，模运算不起作用而任意k-1个数的乘积R有smodR在数值上不等于s16/(补充)基于中国剩余定理的门限方案为了分发秘密，计算m=m1m2…mn然后计算si=s(modmi)(i=1,2,…,n)以(si,mi,m)作为一个子秘密集合{(si,mi,m)}i=1n即构成了一个(k,n)门限方案17/(补充)基于中国剩余定理的门限方案秘密的恢复对任取的k个参与者，不失一般性，设这k个参与者为P1…Pk中，每个参与则Pi计算Mi＝m/mi，Ni＝Mi-1(modmi)，yi=siMiNi结合起来根据中国剩余定理可求得s＝由于任意k个或k个以上的模数相乘都比s大，它们恢复出来的s必然相同，而少于k个参与者则不行18/(补充)基于中国剩余定理的门限方案kjkjiijjmy11)(mod13.3访问结构和一般的秘密共享•定义：在W个参与者（记为集合P）中共享密钥K的方法称为是实现访问结构的一个完善的秘密共享方案，如果满足以下两个条件：•（1）对于一个授权的参与者子集，如果把他们的共享集中到一起，那么就可以确定密钥K的值。•（2）对于一个未授权的参与者子集，如果把他们的共享集中到一起，那么他们也不能确定关于K值的任何信息。如果且，则，我们称访问结构满足单调性（本章假设均为单调）13.3访问结构和一般的秘密共享•设是一个访问结构，称是一个最小授权子集，如果对于任何满足和的集合A都有。的最小授权集合记为，称为的基。在（T,W）门限访问结构的情况中，基恰好是由所有T个参与者的所有子集组成。•定义：子集是最大的非授权子集，如果对于所有的，都有。ABABA00{:,}CPBCB11,BBBB1B13.3.1单调电路构造•设我们得到布尔公式•算法：单调电路构造（C）当存在线使得未定义时，循环以下操作：•找到C的一个门G使得已经被定义，其中是G的输出线，但是对于G的任意出入线来说，都没定义过。（1）如果G是一个“或”门，那么对于G的每一个输入线W，（2）否则，令G的输入线是，独立的选择中的个元素，记为FORDO012413423{{,,},{,,},{,}}PPPPPPPP12413423()()()PPPPPPPP()outfWK()fW()GfWGW()fW()()GfWfW1,...tWW1t,1,1,...,GGtyy1,,1()modtGtGGiiyfWym1,...,it,()iGifWy•例题A12413423()()()PPPPPPPP12Kaa1Kc12Kbb121111(,)(,)yyab122221(,)(,)yyac123321(,)(,)yybKc12441212(,)(,)yyKaaKbb012413423{{,,},{,,},{,}}PPPPPPPP1213142434{,},{,},{,},{,},{,}PPPPPPPPPP非授权子集13.3.1单调电路构造12413423()()()PPPPPPPP变成合取范式：例题B定理：设C是任意的单调布尔电路，则单调电路的构造可产生一个能够实现访问结构的完善秘密共享方案。（略）1213142434()()()()()PPPPPPPPPP1234Kaaaa()C13.3.1单调电路构造1213142434{,},{,},{,},{,},{,}PPPPPPPPPP非授权子集假设是一个访问结构并且是分发规则的集合。我们称是一个实现访问结构的完善秘密共享方案，如果下面两个性质：对于任何的授权子集，不存在两个分发准则和，其中使得（即对于授权子集B中的参与者，共享的任何分发都可以确定密钥K的值）对于任何非授权子集和任何共享的分发，有下式成立对于任意（即对于非授权的子集B，给定共享的分发,K上的条件概率分布和K上的先验概率分布是相同的。换句话说，B的共享的分发没有提供关于K值的任何信息）13.3.2单调电路构造(正式定义)kkKFFFBPkfF''kfF'kk|'|BBf