秘密共享方案ppt课件.ppt

1、第13章 秘密共享方案,1,有些场合，秘密不能由一个人独自拥有，必须由两人或多人同时参与才能打开秘密，这时都需要将秘密分给多人掌管，而且必须有一定人数的掌管秘密的人同时到场才能恢复这一秘密，这种技术就称为秘密分割(SECRET SPLITTING) ，也称为秘密共享(SECRET SHARING)。例如： 导弹控制发射 开启核按钮 重要场所通行检验等 为了实现上述意义上的秘密共享，人们引入了门限方案(THRESHOLD SCHEME)的一般概念,2/,13.1引言,2,秘密分割门限方案的定义 定义1 设秘密 S 被分成N个部分信息，每一部分信息称为一个子密钥或影子(SHARE OR SHADO

2、W)，由一个参与者持有，使得： 由K个或多于K个参与者所持有的部分信息可重构S 由少于K个参与者所持有的部分信息则无法重构S 则称这种方案为(K,N)秘密分割门限方案，K称为方案的门限值。 极端的情况下是(N,N) 秘密分割门限方案，此时用户必须都到场才能恢复密钥,3/,13.1引言,3,如果一个参与者或一组未经授权的参与者在猜测秘密S时，并不比局外人猜秘密时有优势，即 由少于K个参与者所持有的部分秘密信息得不到秘密S的任何信息 则称这个方案是完善的，即(K, N)秘密分割门限方案是完善的 攻击者除了试图恢复秘密外，还可能从可靠性方面进行攻击，如果他能阻止多于N-K个人参与秘密恢复，则用户的秘

3、密就难于恢复 所以(K,N)门限的安全性在于既要防止少于K个人合作恢复秘密，又要防止对T个人的攻击而阻碍秘密的恢复 当N=2T+1时K=T=(N-1)/2的取值最佳 秘密分割应该由可信第三方执行，或者托管设备完成。,4/,13.1引言,4,13.1 引言,秘密的分割 假设是一个(K, N)门限方案 选取一个K1次多项式F(X)A0+A1X+AK-1XK-1 该多项式有K个系数 令A0=F(0)=S，即把常数项指定为待分割的秘密 其它K1个系数可随机选取 显然，对于该多项式，只要知道该多项式的K个互不相同的点的函数值F(XI)(I=1,2,K)，就可恢复F(X) 生成N个子秘密 任取N个不同的点

4、XI(I=1,N) 并计算函数值F(XI)(I=1,N) 则(XI, F(XI), I=1,N, 即为分割的N个子秘密 显然，这N个子秘密中的任意K个子秘密即可重构F(X)，从而可得秘密S,5/,5,13.2 SHAMIR门限方案,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

5、)，可构造K-1次LAGRANGE插值多项式 显然，如果将函数(X)就选定F(X)，则差值多项式刚好完全恢复了多项式(X) F(X),6/,6,13.2 SHAMIR门限方案,根据上述的思想，在有限域GF(Q)上实现上述方案，即可得到SHAMIR秘密分割门限方案 （1）秘密的分割 设GF(Q)是一有限域，其中Q是一个大素数，满足QN1 秘密S是在GF(Q)0上均匀选取的一个随机数，表示为SRGF(Q)0 令S等于常系数A0 其它K-1个系数A1,A2,AK-1的选取也满足AIRGF(Q)0 (I=1,K-1) 在GF(Q)上构造一个K-1次多项式F(X)A0+A1X+AK-1XK-1 N个参与

6、者记为P1,P2,PN，其中PI分配到的子密钥为（I, F(I)）,7/,7,13.2 SHAMIR门限方案,(2) 秘密的恢复 如果任意K个参与者PI1,PI2,PIK (1I1I2IKN)要想得到秘密S，可使用它们所拥有的K个子秘密(IL,F(IL)|L=1,K构造如下的线性方程组 A0A1(I1)AK-1(I1)K-1=F(I1) A0A1(I2)AK-1(I2)K-1=F(I2) A0A1(IK)AK-1(IK)K-1=F(IK) （13-1）,8/,8,13.2 SHAMIR门限方案,因为IL(L=1,K)均不相同，所以可由LAGRANGE插值公式构造如下的多项式： F(X) 从而可

7、得秘密SF(0) 然而参与者仅需知道F(X)的常数项F(0)而无需知道整个多项式F(X)，所以令X0，仅需以下表达式就可以求出S： S= ，（ 可以预计算不需保密 ）,9/,9/,方案的完善性分析 如果K-1个参与者想获得秘密S，他们可构造出由K-1个方程构成的线性方程组，其中有K个未知量 对GF(Q)中的任一值S0，可设F(0)S0，再加上上述的K-1个方程就可得到K个方程，并由LAGRANGE插值公式得出F(X)。因此对每一S0GF(Q)都有一个惟一的多项式满足 13-1方程组 所以已知K-1个子密钥得不到关于秘密S的任何信息，因此这个方案是完善的。,10/,13.2 SHAMIR门限方案

8、,10,【例81】设门限K=3，份额数为N=5，模值Q=19，待分割的秘密S=11，随机选取A1=2，A2=7，可构造多项式 F(X)=(7X2+2X+11) MOD 19 将秘密分割成5份 分别计算 F(1)=(712+21+11) MOD 191 F(2)=(722+22+11) MOD 195 F(3)=(732+23+11) MOD 194 F(4)=(742+24+11) MOD 1917 F(5)=(752+25+11) MOD 196 得5个子密钥。,11/,13.2 SHAMIR门限方案,11,13.2 SHAMIR门限方案,秘密的恢复 如果知道其中的3个子密钥,如F(2)=

9、5，F(3)4，F(5)6，就可重构F(X)，事实上我们可直接根据差值公式 计算S= F(0),12/,12/89,13.2 SHAMIR门限方案,简化的（T , T）门限方案： D 秘密的选取（独立随机选取） 中的 T-1 个元素，记为 ， D计算 ， 对于 ，D 把共享 的值发给 。,13,中国剩余定理，又称孙子定理 设m1,m2, , mk是k个两两互素的正整数，m=m1m2mk, Mi(i=1,k)满足m=miMi，则同余式组 x=b1 (mod m1) x=b2 (mod m2) x=bk (mod mk) 有唯一解：x=M1M1b1+M2M2b2+ MkMkbk (mod m) 其

10、中MiMi=1 mod mi (i=1,2,k),14/,(补充) 基于中国剩余定理的门限方案,14,1. 参数的选择 设m1mnmn-1mn-k+2 注意这里的条件m1mnmn-1mn-k+2表明最小的k个数的乘积也比最大的k-1个数的乘积大 显然，m1, m2, , mn中任意k个数的乘积都比m1m2mk大,15/,(补充) 基于中国剩余定理的门限方案,15,2. 秘密的分割 设s是待分割的秘密数据，令s满足 mnmn-1mn-k+2sm1m2mk 即s比最大的k-1个数的成绩大，同时比最小的k个数的乘积小 从而： 对任意k个数的乘积T，ss mod T，模运算不起作用 而任意k-1个数的

11、乘积R有s mod R在数值上不等于s,16/,(补充) 基于中国剩余定理的门限方案,16/,为了分发秘密，计算m=m1m2mn 然后计算 si=s(mod mi) (i=1,2,n) 以(si,mi,m)作为一个子秘密 集合(si,mi,m)i=1n即构成了一个(k,n)门限方案,17/,(补充) 基于中国剩余定理的门限方案,17/,秘密的恢复 对任取的k个参与者，不失一般性，设这k个参与者为P1Pk中，每个参与则Pi计算 Mim/mi，NiMi-1(mod mi)，yi=siMiNi 结合起来根据中国剩余定理可求得 s 由于任意k个或k个以上的模数相乘都比s大，它们恢复出来的s必然相同，而

12、少于k个参与者则不行,18/,(补充) 基于中国剩余定理的门限方案,18/,13.3 访问结构和一般的秘密共享,定义：在W 个参与者（记为集合P）中共享密钥K的方法称为是实现访问结构 的一个完善的秘密共享方案，如果满足以下两个条件： （1）对于一个授权的参与者子集 ，如果把他们的共享集中到一起，那么就可以确定密钥K的值。 （2）对于一个未授权的参与者子集 ，如果把他们的共享集中到一起，那么他们也不能确定关于K值的任何信息。 如果 且 ，则 ，我们称访问结构满足单调性（本章假设均为单调）,19,13.3 访问结构和一般的秘密共享,设 是一个访问结构，称 是一个最小授权子集，如果对于任何满足 和

13、的集合A 都有 。 的最小授权集合记为 ，称为 的基。 在（T,W）门限访问结构的情况中，基恰好是由所有T 个参与者的所有子集组成。 定义：子集 是最大的非授权子集， 如果对于所有的 ，都有 。,20,13.3.1 单调电路构造,设 我们得到布尔公式 算法：单调电路构造（C） 当存在线 使得 未定义时，循环以下操作： 找到C的一个门G使得 已经被定义，其中 是G的输出线，但是对于G的任意出入线来说， 都没定义过。 （1）如果G是一个“或”门，那么对于G的每一个输入线W， （2）否则，令G的输入线是 ，独立的选择 中的 个元素，记为 FOR DO,21,例题A,非授权子集,13.3.1 单调电路

14、构造,22,变成合取范式： 例题B 定理： 设C是任意的单调布尔电路，则单调电路的构造可产生一个能够实现访问结构 的完善秘密共享方案。（略）,13.3.1 单调电路构造,非授权子集,23,假设 是一个访问结构并且 是分发规则的集合。我们称 是一个实现访问结构 的完善秘密共享方案，如果下面两个性质： 对于任何的授权子集 ，不存在两个分发准则 和 ，其中 使得 （即对于授权子集B中的参与者，共享的任何分发都可以确定密钥K的值） 对于任何非授权子集 和任何共享的分发 ，有下式成立 对于任意 （即对于非授权的子集B，给定共享的分发 ,K 上的条件概率分布和K 上的先验概率分布是相同的。换句话说，B 的

15、共享的分发没有提供关于K 值的任何信息 ）,13.3.2 单调电路构造(正式定义),24,定义： 假设我们有一个实现访问结构 的完善秘密共享方案。 的信息率定义为比率 （ 注意， 表示 所有可能收到的共享集合：当然， ）。方案的信息率记为 并定义为 例题： ， （ ） 因此 例题： 所以 。我们更倾向于方案一，其信息率高些。,13.4 信息率和高效方案的构造,25,定理13.2：设C是任意的单调布尔电路，则存在一个实现访问结构 的完善秘密共享方案，其信息率是 其中 是C中带有输入线的根数。 可以看出，shamir门限方案的信息率是 1，下面会证明这是一个最优值。相比之下，使用析取范式的布尔电路

16、实现的（t, w）门限方案的信息率是 ，当 这是一个非常低的值（因此是不佳的） 定理13.3：对于实现一个访问结构的任何完善的秘密共享方案，都有 。,13.4 信息率和高效方案的构造,26,设 是一个访问结构， 是 上所有d元组组成的向量空间，假设存在函数 满足性质 话句话说，向量 可以表示为 中向量的线性组合当且仅当B是一个授权子集。 对于给定的访问结构，只要我们找到满足该性质的向量的集合，那么就可以建立相应的秘密共享方案，这个方案被称为Brickell 秘密共享方案。,13.4.1向量空间构造,27,密码体制13.3 Brickel 秘密共享方案 输入：满足上述性质的向量 初始化阶段 对于

17、 ， D把向量 给 D ，这些向量公开。 共享分发 假设D 想要共享密钥K。 D定义 ， 并且他秘密的选择 中的d-1个元素 对于 ，D 计算 ，其中 对于 ， D 把 的值作为共享分发给 。,13.4.1向量空间构造,28,定理13.4 假设 满足性质 ，则分法规则 ， 的集合组成了一个实现访问结构 的理想秘密共享方案。 证明： 首先， 我们证明 如果B 是一个授权子集，那么B中参与者能够计算K。因为 所以我们将其写成 其中每个 。 的共享是 ，其中 是由D选定的未知向量，并且 . 由内积运算的线性性，可得,13.4.1向量空间构造,29,如果B不是授权子集，假设对于某个 ，B 假设 。 我

18、们证明这样的猜测和她们所拥有的信息是一致的。我们用 表示子空间 的维数考虑方程组： 这是一个含有 个未知量的线性方程组，因为 则这个方程组是相容的，系数矩阵的秩是 ，解空间的维数为 （对任意的值 这样在每个 恰好有 个分发规则，这和B共享的可能分发是一致的。有,13.4.1向量空间构造,（详解参考例题13.8）,30,定理 13.5 假设 是一个完整的多划分图，则存在一个理想秘密共享方案实现了参与者V上的基为 E 上的访问结构。,13.4.1向量空间构造,31,32,33,定义 13.5 设 是一个访问结构， 是分布规则的集合，则称 是实现访问结构的一个完善的秘密共享方案，如果满足以下两个条件： 对于任何参与者的授权子集 ， 。 对于任何参与者的非授权子集 ， 。 引理13.7 假设设 是一个访问结构， 是实现 的分发规则的集合，设 ，其中 则 引理13.8 假设 是一个访问结构， 是实现 的分发规则的集合，设 其中 ，则 。,13.4.2 信息率上界,34,定理 13.9 假定 是一个访问结构使得 和 令 是任意实现 的完善秘密共享方案，则 。 推论13.10假定 是满足定理13.9中假设的访问结构，并设密钥值是等概率选取的， 则 。 定理13.11 假设G 是一个非完全多划分的连通图，令 是具有基 的访问结构，其中 是的边集，那么。 由