应用密码学---浅谈秘密分割.pptVIP

举例引入 任何一个方程无法确定x 任何两个方程可唯一确定x x ≡ 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 9*11 =99 问题:已知 任何三个方程存在容余信息: 有一个冗余方程 可构造(2,3)门限方案 x = 74 x = 74 系统初始化 首先选取n个严格递增的m1,m2,…,mn,满足 (mi,mj)=1(对所有i≠j) m1m2…mt mnmn-1…mn-t+2 S是秘密,满足 m1m2…m t s mnmn-1…mn-t+2 （等价：s 大于任意 t-1 个mi的乘积 s 小于任意 t 个mi的乘积 ） 此时，可构造(t,n)门限方案。 简化的Asmuth-Bloom门限方案 子密钥的分发 计算 si = s(mod mi) (i=1,…, N)， （mi,si）为一子密钥. 密钥的恢复 当k个参与者提供子密钥时，可建立方程组 由中国剩余定理可以求得 s ≡ s’ mod N ’ ，N’为k个mi的乘积 显然，当 sN 时可以唯一确定 。 简化的Asmuth-Bloom门限方案 门限性分析 若 k = t,则由系统初始化条件 因为s小于任意 t 个mi的乘积，所以sN. 故，s ≡ s mod N 的解唯一确定。 若 k t,则由系统初始化条件 因为s 大于任意 t-1 个mi的乘积，所以sN 故，s ≡ s mod N 的解无法确定。 简化的Asmuth-Bloom门限方案 (9,2),(11,8),(13,9)构成（2,3）门限方案 s ≡ 2 (mod 9) s ≡ 8 (mod 11) s ≡ 9 (mod 13) 方案举例 例：k=2,n=3, m1=9,m2=11,m3=13，m1m2=99s13=m3, 此范围选取s=74。 子秘密分发： 若已知(9,2),(11,8)，可建立方程组 解得s ≡(11×5×2＋9×5×8) mod 99 ≡ 74, 故s=74 s ≡ 2 (mod 9) s ≡ 8 (mod 11) 参考过的资料（特别鸣谢以下资料的作者！） 《现代密码学_第15讲秘密分割》/view/35105b0a79563c1ec5da71a9.html 《应用密码学 秘密分割 秘密共享 影子》http://lcx.cc/?i=961 《应用密码学》主编:刘嘉勇,清华大学出版社,2008年5月 本人联系方式 个人主页：/Ping_Fani07 通信邮箱：tuobaye2006@ 浅谈秘密分割 作者：刘庆聪 提 纲 一、最简单的秘密分割方案 二、秘密分割门限方案 Asmuth-Bloom门限方案 一、最简单的秘密分割方案 可口可乐公司的烦恼 秘密分割的概念 2人秘密分割的数学实现 共享人数为n(n2)时的推广 安全性分析 秘密分割 有各种方法把消息分割成许多碎片。每一片本身并不代表什么，但把这些碎片放到一块，消息就会重现出来。 如前例，消息是一个饮品配方，每一个董事有一部分，那么只有他们放在一起才能还原这种配方。如果任意一董事撤股或被竞争对手收买而带走一部分配方碎片，这个碎片本身是毫无用处的。 分割的一个简单数学实现 以两个人之间的消息分割为例，下面是Trent把一消息分割给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产生三个与消息M一样长的随机比特串R,S,T； 2）Trent用这三个随机串和M异或得到U： M ⊕ R ⊕ S ⊕ T = U 3）Trent将R给Alice，S给Bob，T给Carol，U给Dave。 Alice、Bob和Carol、Dave在一起可以重构此消息： 4）Alice、Bob、Carol和Dave一起计算： R ⊕