应用密码学---浅谈秘密分割与共享[课件]

1、浅谈秘密分割作者：蚍蜉撼青松主页主页：http:/ 纲 一、最简单的秘密分割方案一、最简单的秘密分割方案 二、秘密分割门限方案二、秘密分割门限方案 Shamir门限方案门限方案 Asmuth-Bloom门限方案门限方案 三、门限数字签名方案三、门限数字签名方案基于基于ElGamal体制的门限数字签名方案体制的门限数字签名方案基于基于Schnorr体制的门限数字签名方案体制的门限数字签名方案一、最简单的秘密分割方案一、最简单的秘密分割方案可口可乐公司的烦恼秘密分割的概念秘密分割的概念2人秘密分割的数学实现人秘密分割的数学实现共享人数为共享人数为n(n2)时的推广时的推广安全性分析安全性分析秘密分

2、割 有各种方法把消息分割成许多碎片。每一片本身有各种方法把消息分割成许多碎片。每一片本身并不代表什么，但把这些碎片放到一块，消息就会重并不代表什么，但把这些碎片放到一块，消息就会重现出来。现出来。 如前例，消息是一个饮品配方，每一个董事有一如前例，消息是一个饮品配方，每一个董事有一部分，那么只有他们放在一起才能还原这种配方。如部分，那么只有他们放在一起才能还原这种配方。如果任意一董事撤股或被竞争对手收买而带走一部分配果任意一董事撤股或被竞争对手收买而带走一部分配方碎片，这个碎片本身是毫无用处的。方碎片，这个碎片本身是毫无用处的。分割的一个简单数学实现 以两个人之间的消息分割为例，下面是Tren

3、t把一消息分割给Alice和Bob的一个协议：（1）Trent产生一随机比特串产生一随机比特串R，和消息，和消息M一样长。一样长。（2）Trent用用R异或异或M得到得到S：M R = S（3）Trent把把R给给Alice，将，将S给给Bob。 为了重构此消息，Alice和Bob只需一起做一步：（4）Alice和和Bob将他们的消息异或就可得到此消息：将他们的消息异或就可得到此消息：R S = M推广：从2人分割到n人分割 这种方案推广到多人是很容易的。为了在多个人中分割一秘密消息，将此消息与多个随机比特异或成混合物即可。在下面的例子中，Trent把信息划分成四部分：1）Trent产生三个与

4、消息产生三个与消息M一样长的随机比特串一样长的随机比特串R,S,T；2）Trent用这三个随机串和用这三个随机串和M异或得到异或得到U：M R S T = U3）Trent将将R给给Alice，S给给Bob，T给给Carol，U给给Dave。 Alice、Bob和Carol、Dave在一起可以重构此消息：4）Alice、Bob、Carol和和Dave一起计算：一起计算：R S T U = M安全性分析1-保密性好 如果做得适当，这种技术是绝对安全的。因为每如果做得适当，这种技术是绝对安全的。因为每一个人所持有的部分消息本身是毫无价值的。一个人所持有的部分消息本身是毫无价值的。 前述协议的实质，

5、是前述协议的实质，是TrentTrent用用一次一密一次一密的方式加密的方式加密消息，并将密文给一人，密钥给另一人。消息，并将密文给一人，密钥给另一人。 一次一密加密方式，它们具有完全的保密性。无一次一密加密方式，它们具有完全的保密性。无论有多大计算能力都不能根据消息碎片之一就确定出论有多大计算能力都不能根据消息碎片之一就确定出秘密消息来。秘密消息来。安全性分析2-缺陷过于依赖秘密分割者过于依赖秘密分割者。 这是一个裁决协议，这是一个裁决协议，TrentTrent有绝对的权力，并且能够做他想做的任何事情。有绝对的权力，并且能够做他想做的任何事情。他可以把毫无意义的东西拿出来，并且申明是秘密的他

6、可以把毫无意义的东西拿出来，并且申明是秘密的有效部分。在他们将秘密重构出来之前，没有人能够有效部分。在他们将秘密重构出来之前，没有人能够知道它。知道它。可靠性太低可靠性太低。 如果任何一部分丢失了，并且如果任何一部分丢失了，并且TrentTrent又不在，就等于将整个秘密消息丢掉了。又不在，就等于将整个秘密消息丢掉了。QUESTION: 怎么才能在保证秘密消息的保密性的同时提升其可靠性呢？秘密分割秘密分割门限方案门限方案SOLUTION:二、秘密分割门限方案2.1 概述概述2.2 Shamir门限方案门限方案2.3 Asmuth-Bloom门限方案门限方案再来看两个有意思的问题美军核弹发射控制

7、问题花旗银行金库控制问题 把一个秘密把一个秘密s分为分为n个子密钥个子密钥s1,s2,sn,并将每个子并将每个子密钥（也称为密钥（也称为shadow影子影子或或share份额份额）安全分配给）安全分配给n个参与者持有，使得个参与者持有，使得由由k k个或多于个或多于k k个参与者所持有的部分信息可重构个参与者所持有的部分信息可重构s s；由少于由少于k k个参与者所持有的部分信息无法重构个参与者所持有的部分信息无法重构s s。 这种方案被称之为这种方案被称之为(k,n)秘密分割门限方案秘密分割门限方案（k称为称为门门限值限值），也简称为也简称为门限方案门限方案、阈值方案阈值方案。问题的抽象解决

8、方案问题的抽象解决方案完善条件完善条件： 如果少于如果少于k个参与者所持有的个参与者所持有的部分信息得不到秘密部分信息得不到秘密s的任何信息的任何信息，则称该门限方案是，则称该门限方案是完善完善的的。门限值门限值 K 的设定的设定 K的具体取值其实是由方案的保密性要求和可靠性要求的具体取值其实是由方案的保密性要求和可靠性要求共同决定的共同决定的。高门限，提供高安全性（指保密性），低可靠性高门限，提供高安全性（指保密性），低可靠性低门限，提供低安全性（指保密性），高可靠性低门限，提供低安全性（指保密性），高可靠性 以美军核弹发射控制问题为例，以美军核弹发射控制问题为例，K的值越大，那么核的值越大

9、，那么核弹发射受到疯子干扰的程度就越小，核弹发射控制系统弹发射受到疯子干扰的程度就越小，核弹发射控制系统的安全性就越高，但同时遇到紧急情况时因为有人缺席的安全性就越高，但同时遇到紧急情况时因为有人缺席而造成核弹无法及时发射的概率就越大；反之亦然。而造成核弹无法及时发射的概率就越大；反之亦然。2.3 Shamir门限方案l作者：作者：Adi Shamirl基于基于多项式的拉格朗日插值公式多项式的拉格朗日插值公式ShamirShamir门限方案的原理门限方案的原理 对于有限域对于有限域 GF(q) 上的一个上的一个 k-1 次多项式次多项式 f(x) ,若把若把秘密秘密s取做取做 f(0) ，将将

10、 f( (xi i)()(i=1,=1,n) ) 作为作为 n 个个shadow, ,那么利用其中任意那么利用其中任意 k 个个shadow可以重构可以重构 f(x) ，从而可，从而可以得到秘密以得到秘密s。ShamirShamir门限方案门限方案系统初始化系统初始化 有限域有限域GF(q),q为大素数，为大素数，qn+1。秘密。秘密s是是GF(q)0上上均匀选取的随机数，表示为均匀选取的随机数，表示为sRGF(q)0. k-1个系数个系数a1,a2,ak-1选取选取ai RGF(q)0.在在GF(q)上构造一个上构造一个k-1次多项式：次多项式： f(x)= s +a1x+ak-1xk-1秘

11、密分发秘密分发 N个参与者个参与者P1,Pn，Pi的的Shadow为（为（i, f (i)）。）。3. 秘密重构秘密重构 任意任意k个参与者得到秘密，可使用个参与者得到秘密，可使用(il,f(il)|l=1,k构造方程组，从而算出构造方程组，从而算出f(x)。)()()()()()(11101111110kkkkkkkifiaiaaifiaiaa多项式的第二种重构多项式的第二种重构由由LagrangeLagrange插值公式插值公式)(mod)()()(11qiiixifxfkjkjllljlj)(mod)() 1(111qiiiifskjkjllljljkShamirShamir门限方案的安

12、全性分析门限方案的安全性分析 如果如果k-1-1个参与者想获得个参与者想获得s,可构造可构造k-1-1个方程，有个方程，有k个未知量。个未知量。 对任一对任一s0 0, ,设设f(0)= (0)= s0.0.这样可以得到这样可以得到第第k个方程，得到个方程，得到f( (x) )。 对每个对每个s s0 0都有唯一的多项式满足，所都有唯一的多项式满足，所有由有由k-1-1个个shadowshadow得不到任何得不到任何s的信息。的信息。因此此方案是完善的。因此此方案是完善的。ShamirShamir门限方案的主要特点门限方案的主要特点主要优点：主要优点：（1）是完善的门限方案；）是完善的门限方案

13、；（2）每个份额的大小与秘密值的大小相近；）每个份额的大小与秘密值的大小相近；（3）易于扩充新用户，即计算要分配的新份额不影响原）易于扩充新用户，即计算要分配的新份额不影响原来的各个份额。来的各个份额。（4）安全性不依赖于未经证明的假设。）安全性不依赖于未经证明的假设。主要缺点主要缺点：（5）门限值固定）门限值固定(即不区分参与者即不区分参与者)；（6）秘密分发者知道参与者的份额；）秘密分发者知道参与者的份额；（7）不能防止秘密分发者和参与者的欺诈。）不能防止秘密分发者和参与者的欺诈。ShamirShamir门限方案的示例门限方案的示例【例例】设设 k=3，n=5，q=19，s=11。随机选随

14、机选a1=2，a2=7 使使 f(x)=7x2+2x11 mod 19 计算计算f (1)=1，f(2)=5，f(3)=4，f(4)=17，f(5)=6将将i，f(i)(i=1，2，3，4，5)分发给五个用户。分发给五个用户。1127)35)(25()3)(2(6)53)(23()5)(2(4)52)(32()5)(3(5)(2xxxxxxxxxf若已知若已知f(2)，f(3)，f(5)，重构，重构f(x)如下：如下：2.2 Asmuth-Bloom门限方案l作者：作者：Asmuth-Blooml基于基于中国剩余定理中国剩余定理举例引入举例引入任何一个方程无法确定x任何两个方程可唯一确定xx

15、9 (mod 13)显然不满足显然不满足,其他一样其他一样x 2 (mod 9)x 8 (mod 11)x 74 (mod 99)x 2 (mod 9)x 8 (mod 11)x 9 (mod 13)x 74 (mod 1287)x 2 (mod 9)x 8 (mod 11)x 9 (mod 13)13 x m mn nmmn-1n-1mmn-n-t t+2+2n S S是秘密是秘密, ,满足满足 m1m2m t s mnmn-1mn-t+2（等价：（等价：s s 大于任意大于任意 t-1 t-1 个个mmi i的乘积的乘积 s s 小于任意小于任意 t t 个个mmi i的乘积的乘积 ）此时

16、，此时，可构造可构造( (t t,n),n)门限方案。门限方案。简化的简化的Asmuth-Bloom门限方案门限方案u子密钥的分发子密钥的分发n计算计算 si = s(mod mi) (i=1, N)， （mi,si）为一子密钥为一子密钥. . u密钥的恢复密钥的恢复n当当k k个参与者提供子密钥时，可建立方程组个参与者提供子密钥时，可建立方程组n由中国剩余定理可以求得由中国剩余定理可以求得 s s s s mod N mod N ，NN为为k k个个mi的乘积的乘积显然，当显然，当 s= t,则由系统初始化条件则由系统初始化条件因为因为s小于任意小于任意 t 个个mi的乘积，所以的乘积，所以

17、sN. .故，故，s s mod N 的解唯一确定。的解唯一确定。n若若 k N故，故，s s mod N 的解无法确定。的解无法确定。简化的简化的Asmuth-Bloom门限方案门限方案(9,2),(11,8),(13,9)(9,2),(11,8),(13,9)构成构成（2,32,3）门限方案）门限方案s 2 (mod 9)s 8 (mod 11)s 9 (mod 13)方案举例方案举例例：例：k=2,n=3, mk=2,n=3, m1 1=9,m=9,m2 2=11,m=11,m3 3=13=13，m m1 1m m2 2=99=99ss13=m13=m3,3, 此范围选取此范围选取s=7

18、4s=74。 子秘密分发：子秘密分发： 若已知若已知(9,2),(11,8)，可建立方程组，可建立方程组 解得解得s (1152958) mod 99 74,故故s=74s 2 (mod 9)s 8 (mod 11)安全性分析安全性分析 此方法存在的欺骗问题包括在重建阶段的参此方法存在的欺骗问题包括在重建阶段的参与者欺骗与分割阶段的分派者欺骗。与者欺骗与分割阶段的分派者欺骗。 参与者欺骗是指参与者可能丢出假的子秘密，参与者欺骗是指参与者可能丢出假的子秘密，使得只有他自己能解出共享的秘密，而其它使得只有他自己能解出共享的秘密，而其它人无法解出该秘密。人无法解出该秘密。 分派者欺骗是指分派者可能把

19、假的子秘密给分派者欺骗是指分派者可能把假的子秘密给参与者，使得该参与者无法在日后重建共享参与者，使得该参与者无法在日后重建共享的秘密。的秘密。 解决方案包括子秘密应具备可验证性解决方案包括子秘密应具备可验证性(verifiable)(verifiable)与通过数字签名解决。与通过数字签名解决。三、门限数字签名方案3.1 概述概述3.2 基于基于Schnorr体制的体制的(t,n)门限签名方案门限签名方案3.3 基于基于ElGamal体制的体制的(t,n)门限签名方案门限签名方案（t,nt,n）门限签名是指，群体的签名密钥被所有）门限签名是指，群体的签名密钥被所有n n个成员共享，使得任意不少

20、于个成员共享，使得任意不少于t t个成员的子集个成员的子集可以代表群体产生签名，而任意少于可以代表群体产生签名，而任意少于t t个成员的个成员的子集不能代表群体产生签名；同时任何人都可子集不能代表群体产生签名；同时任何人都可以利用群的唯一公钥，验证签名的正确性。以利用群的唯一公钥，验证签名的正确性。总经理总经理n位副总经理位副总经理已签名文件已签名文件未签名文件未签名文件t位经理签名位经理签名3.3 基于Schnorr体制的(t,n)门限数字签名方案Schnorr数字签名方案基本思路：基本的签名方案参照Schnorr数字签名方案；签名用的私钥 x 不再单独分发给个人，而是作为一个共享秘密，分割

21、后发放给 n 个成员；分发时采用Shamir等 (t,n) 秘密分割门限方案，由于私钥 x 的重构需要满足门限条件，故此有效签名的产生也满足门限条件。方案实现-1.系统初始化大素数p和q满足 q|(p-1)，q2160是整数，p2512是整数，确保在Zp中求解离散对数的困难性; gZp，且满足gq=1(mod p)，g1; h为单向哈希函数。 有限域GF(w),w为大素数，wn+1(n为系统参与者数)。系统私钥系统私钥：分发者在GF(q)0上均匀选取随机数 s 作为私钥,且满足1sq，保密。系统公钥系统公钥：分发者计算y=gs(mod p)作为公钥，公开。p、q、g、w作为系统参数，供所有用户

22、使用，在系统内公开。方案实现-2.成员子密钥分发在GF(w)上构造一个k-1次多项式：f(x)= s + a1x + + ak-1xk-1,其中 k-1 个系数a1,a2,ak-1选取ai RGF(w)0设n个参与者为P1,P2,Pn,身份标识为i1,i2,in。分发者利用ik(1=k=n)和f(x)计算f(ik)，并将结果f(ik)秘密分发给ik，作为其子密钥。方案实现-3.签名过程对于一个待签名消息m，可信中心选择t个参与者：Pj1,Pj2,Pjt。由t个参与者提供的私钥f(ijk)，根据拉格朗日插值公式可以计算出系统私钥s；可信中心按照与系统私钥s相同的条件生成一个随机数K，计算出 r=

23、gK mod p令 e=h(r,m)，求出 u=(K-s*e) mod p(e,u)即为系统对m的签名。 方案实现-4.验证过程接收者收到消息m和签名(e,u)。 先计算r=guye(mod p)，然后计算e=h(r，m)，检验e=e是否成立。 如果成立，则签名有效; 否则，签名无效。若(e，u)为合法签名，则有guye=gk-xegxe=gk=r(mod p) 所以当签名有效时，上式成立，从而说明验证过程是正确的。3.2 基于ElGamal体制的(t,n)门限数字签名方案ElGamal数字签名方案可信第三方可信第三方签名合成者签名合成者成员成员谢谢观看！附 录可口可乐公司的烦恼 假设假设Co

24、ca-ColaCoca-Cola公司最近新研发出了一种特别的饮品，公司最近新研发出了一种特别的饮品，饮品的配方将由公司董事会负责保管。饮品的配方将由公司董事会负责保管。 把配方交给某位董事而忽略其他董事？当然不行，把配方交给某位董事而忽略其他董事？当然不行，董事会的成员都是平等的，每个人都应该享有保管权利。董事会的成员都是平等的，每个人都应该享有保管权利。 那么把配方给每位董事都发一份吗？不，绝对不行，那么把配方给每位董事都发一份吗？不，绝对不行，万一有一位董事被竞争对手收买了怎么办？配方将被泄万一有一位董事被竞争对手收买了怎么办？配方将被泄露，特别的饮品将不再特别露，特别的饮品将不再特别 董

25、事会为此争论不休，烦恼之极！董事会为此争论不休，烦恼之极！如果你是公司的安全顾问，你该怎么为如果你是公司的安全顾问，你该怎么为你的你的bossboss们解忧？们解忧？返回返回美军核弹发射控制问题 你正在为核导弹设计发射装置，导弹的发射权力你正在为核导弹设计发射装置，导弹的发射权力将交给五位官员。但五个官员中潜藏有至多两个疯子，将交给五位官员。但五个官员中潜藏有至多两个疯子，而疯子们没理由得想要轰炸多伦多。而疯子们没理由得想要轰炸多伦多。 为了不会因为疯子们的失控而发生一起多伦多炮为了不会因为疯子们的失控而发生一起多伦多炮轰事件，你确信当仅有疯子在场的情况下是不应拥有轰事件，你确信当仅有疯子在场

26、的情况下是不应拥有启动导弹发射权力的。启动导弹发射权力的。 当然，出于对合众国安全的考虑，你当然，出于对合众国安全的考虑，你同样必须保证在有个别官员休假的情况下，同样必须保证在有个别官员休假的情况下，我们照样能够启动导弹发射。我们照样能够启动导弹发射。 求发射装置的控制方案设计。求发射装置的控制方案设计。可口可乐配方保管问题 Coca-Cola公司的董事会有12位董事，他们想保护可乐的配方。他们不希望每个董事都拥有独立取得配方的权利，因为这样的话配方的秘密很容易泄露。而当所有董事都在场的时候，则可以顺利取得配方。 一旦处于紧急的情况下，董事会需要及时取得配方。但总有各种意外导致有的董事来不了，

27、从而导致配方无法取出。为此董事会希望有一种机制，使得只要同时有5位董事在场就能取得配方，而不用等所有人到齐。 作为公司的安全维护人员，你要怎样设计才能达到董事们的要求？花旗银行金库开启问题 花旗银行某支行有一位正行长和五位副行长，要对花旗银行某支行有一位正行长和五位副行长，要对其某下属金库实施开启控制。其某下属金库实施开启控制。 如果银行每位正副行长都有可以打开金库的钥匙，如果银行每位正副行长都有可以打开金库的钥匙，虽然很方便但却极不安全；虽然很方便但却极不安全； 反之，如果要求所有行长到齐并同时使用各自的钥反之，如果要求所有行长到齐并同时使用各自的钥匙才能打开金库，虽然安全却极不可靠。因为我

28、们不能匙才能打开金库，虽然安全却极不可靠。因为我们不能排除某位行长由于航空或交通意外而躺在医院某个角落排除某位行长由于航空或交通意外而躺在医院某个角落的可能的可能 如果你是该支行的安全维护人员，如果你是该支行的安全维护人员，你该怎样设计金库开启控制方案？你该怎样设计金库开启控制方案？返回返回 设设(x1,y1),(xk,yk)是平面上是平面上k个点构个点构成的点集，其中成的点集，其中xi(i=1,k,)各不相同，那么各不相同，那么在平面上存在唯一的在平面上存在唯一的k-1次多项式次多项式f(x)通过这通过这k个点。个点。 且有如下关系式：且有如下关系式：)(mod)()()(11qiiixif

29、xfkjkjllljlj拉格朗日插值公式拉格朗日插值公式返回返回设设m1, m2, mk是是 k 个两两互素的正整数，个两两互素的正整数，并记并记 M = m1 m2 mk，Mi= M/mi， 则同余方程组：则同余方程组：在模在模 M 同余的意义下同余的意义下有唯一解有唯一解： x M1 M1 b1 M2 M2 b2 Mk Mk bk mod M （2）其中其中 Mi Mi 1 mod mi中国剩余定理，中国剩余定理，CRTChina Residue Theorem )(mod.)(mod)(mod2211kkmbxmbxmbx（1）返回返回ElGamal数字签名算法描述：数字签名算法描述：

30、(1) 系统初始化：系统初始化：选取大素数选取大素数 p， Zp*是一个本原元。是一个本原元。 p， 作为系统参数公开。作为系统参数公开。 每个用户每个用户U随机选取整数随机选取整数 dU，2 dU p2。 计算：计算： eU = dU mod p 将将 eU 作为用户作为用户U的公开密钥，的公开密钥， dU作为用于签名的秘作为用于签名的秘密密钥，并严格保密。密密钥，并严格保密。(2) 签名变换：签名变换： 给定消息给定消息M，签名方，签名方A将进行下述签名计算：将进行下述签名计算： 选择随机数选择随机数 rZp* ，且，且r与（与（p1)互素互素 用单向散列函数用单向散列函数H对消息对消息M

31、进行压缩。签名方进行压缩。签名方A计算计算H(M)，并计算：，并计算： R r mod pS(H(M) dAR) r1 (mod p1) 用户用户A将将Sig(M, r) = (R, S) 作为自己对消息作为自己对消息M的数字签的数字签名，与消息名，与消息M一起传送给接收方。一起传送给接收方。(3) 验证签名：验证签名：接收方在收到消息接收方在收到消息M与数字签名与数字签名(R，S)后：后： 计算计算H(M)； 计算计算eAR RS (mod p) 和和 H(M) (mod p) 若若两式相等，即两式相等，即 eAR RS (mod p) H(M) (mod p) 则确认则确认(R, S)为有

32、效签名。为有效签名。 eA = dA mod p，R r mod pS(H(M) dAR) r1 (mod p1)由于由于 eAR RS ( dA ) R ( r )S dA R r S dA Rr S (mod p) 又由又由 S(H(M) dAR) r1 (mod p1)由模运算规则，上式为：由模运算规则，上式为： r S+ dAR = H(M) (mod p1)即：即： dAR + r S = H(M) (mod p1)再由模运算的指数性质有：再由模运算的指数性质有： dA Rr S H(M) (mod p) 所以有：所以有： eAR RS (mod p) H(M) (mod p) 完整

33、地，验证算法可表述如下：完整地，验证算法可表述如下：Ver(M, (R, S)(eAR RS (mod p) = H(M) (mod p) )? True : false 在在ElGamal签名方案中，签名过程需要保密的密钥签名方案中，签名过程需要保密的密钥dA和一个秘和一个秘密的随机数密的随机数 r ，而对签名进行验证则只需要公开的参数，而对签名进行验证则只需要公开的参数(eA, p, )。ElGamal 数字签名算法举例数字签名算法举例 设设 p = 11， 2是是Z11* 的一个本原元。用户的一个本原元。用户A选择随机整选择随机整数数 dA = 8，计算：，计算： eA = dA mod p=28 mod 11= 3 系统参数系统参数 p ， 和和用户用户A的的公钥公钥eA公开，签名私钥公开，签名私钥dA保密。保密。 假设假设用户用户A要对消息要对消息M进行签名进行签名 ，且，且H(M) 5 。(1) 用户用户A选择随机数选择随机数 r = 9; 因为因为 (9, 10) = 1，所以，所以9模模10的逆一定存在，根据扩展的的逆一定存在，根据扩展的Euclid算法，算法， 有：有： r1 (mod p1) 91 (mod 10)9 用户用户A计算：计算：R r mod