（应用数学专业论文）秘密共享中若干方面的研究.pdf

山东大学硕士学位论文 奠皇舅量舅曼皇皇量曼量| 鼍曼曼量量曼舅曼皇量曼鼍曼皇量喜置量罾詈量詈曼量暑皇曼蔓曼i 一 。 一一| i 摘要 网络技术正在飞速发展，网络服务给人类生活带来了巨大的便利，与此同时， 也面临着前所未有的威胁。如何使数据在网络上的传送时，保密性、完整性和可 用性得到保证是一个十分紧迫的问题，密码安全技术是应对这一问题的有效方 法。 在密码和信息安全领域中，秘密共享是一个非常重要的研究领域。秘密共享 能够将秘密分割成若干份额共享在多个服务器上，每个服务器持有秘密的一个份 额，只有多于特定数量的份额才能重构秘密，少于特定数量的份额则计算不出秘 密值。秘密共享可广泛应用于多方安全计算、门限签名、门限加密、数据的安全 存储等许多领域。 在这篇论文中，我们首先介绍了秘密共享的当前研究状况，然后主要探讨了 在秘密共享领域中几个方面的研究工作。这些工作主要包括：动态秘密共享的研 究、数据内容秘密共享方案和秘密共享中多成员的加入协议。 上述这些工作的研究成果可广泛应用于：数据的分布式安全存储、电子商务 中电子货币系统、多方计算等许多领域。 关键词：秘密共享：可验证秘密共享；公开可验证秘密共享；门限方案： 多方安全计算 山东大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l p m e n to ft h et e c h n i q u ea b o u tc o m p u t e rn e t w o r k , n e t w o r ks e v i c e s h a v eb r o u g h tm a n yc o n v i e n c e st op e o p l e sl i f e o nt h eo t h e rh a n d , t h e y 晡n ga n u n p a r a l l e l e dt h r e a t h o wt og u a r a n t e et h ec o n f i d e n t i a l i t y , i n t e g r i t ya n da v a i l a b i l i t yo f t h ed a t at r a n s f e r r e di nn e t w o r ki sa l lu r g e n tp r o b l e m t h et e c h n i q u eo fc r y p t o l o g ya n d i n f o r m a t i o ns e c u r i t yi sa r te f f e c t i v em e a n st od e a lw i t ht h i sp r o b l e m i ne r y p t o l o g ya n di n f o r m a t i o ns e c u r i t y , s e c r e ts h a r i n gi sa ni m p o r t a n tr e s e a r c h d o m a i n t h es e c r e ts h a r i n gs c h e m ec a nd i v i d et h es e c r e tk e yi n t os e v e r a ls h a r e sa n d s h a r et h e mi nm u l t i p l es e r v e r s e a c hs e r v e rh o l d so n es h a r eo ft h es e c r e t o n l yn o f e w e rt h a nac e r t a i nn u m b e ro fs h a r e sc a nr c c o n s t r u c tt h es e c r e t ，w h i l ef e w e rt h a nt h e c e r t a i nn u m b e rc 缸tc o m p u t e rt h i ss e c r e t t h es e c r e ts h a r i n gc a nb ea p p l i e dt o m u l t i p l es e c u r ec o m p u t a t i o n , t h r e s h o l ds i g n a t u r e ，t h r e s h o l de n c r y p t i o n , s e c u r es t o r a g e a n ds 0 0 1 1 i nt h i sp a p e r , w ef i r s t l yi n t r o d u c et h ec u r r e n tr e s e a r c hb a c k g r o u po fs e c r e ts h a r i n g a n dt h e nd i s c u s ss e v e r a la s p e c t so fr e s e a r c hw o r ki ns e c r e ts h 撕n gi n c l u d i n gp r o a c t i v e s e c r e ts h a r i n g , d a t ac o n t e n ts e c r e ts h a r i n gs c h e m e ，a n dv e r i f i a b l em u l t i p l e - p l a y e r s e n r o l l m e n tp r o t o c o lf o rs e c r e ts h a r i n g t h e s er e s e a r c hr e s u l t sc a nw i d e l ya p p l i e dt od i s t r i b u t i v e l ys e c u r cs t o r a g eo ft h e d a t a , e - c a s hs y s t e mi ne l e c t r o n i cc o m m e r c e ，a n dm u l t i p l e p a r t i e sc o m p u t a t i o na n ds o o n n k e y w o r d s ：s e c r e ts h a r i n g ，v e r i f i a b l e s e c r e ts h a r i n g ，p u b l i c l yv e r i f i a b l es e c r e t s h a r i n g t h r e s h o l ds c h e m e ；m u l t i p l e - p a r t i e s 戳圮倜呛c o m p u a t i o n 山东大学硕士学位论文 i i p q 乙 z g | 乙【x 】 足 d v s s p v s s p s s 符号说明和缩写词 素数易g 模为g 的有限域 模为的剩余类环凇 阶为素数g 的有限群 有限域z ，上的多项式 随机选取 秘密分发者 可验证秘密共享 公开可验证秘密共享 动态秘密共享 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：二址 日 关于学位论文使用授权的声明 本人同意学校保留或向国家有关部门或机构送交论文的印刷件 和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：堑窆兰 导师签名：旦圣奎日期：丝堑主! 盈箩 山东大学硕士学位论文 第一章引言 当今的信息社会中，i n t c m e t 发挥着重大的作用，这使得人们的日常生活产生 了巨大的变革。电子邮件、网上购物、网上银行、远程教育和各种网络服务使人 们的生活日益丰富和便利。密码和信息安全技术可以保证网络通信时信息的保密 性、完整性和可用性。密码学是结合数学、计算机科学、信息科学等多学科为一 身的交叉学科。密码学不但能够提供信息的保密性功能，而且还可以确保信息的 完整性和不可否认性，能有效的防止信息的篡改和伪造。秘密共享作为密码学中 的一个重要研究领域，已经吸引了很多学者的关注。 1 1 秘密共享的作用 秘密共享将秘密共享在多个服务器上，每个服务器持有秘密的一个份额( 又 称子密钥、碎片或者影子) ，只有多于特定数量的份额才能重构秘密，要进行签 名操作，需要服务器的一个子集重构秘密，然后进行签名操作。这种方法仍然存 在不足：重构秘密的位置可能成为安全的盲点，容易成为攻击者攻击的目标。门 限签名可以解决这个问题，在( t , n ) f - j 限签名中，密钥被分割成刀个份额并共享在刀 个服务器上，签名时各服务器用他们自己的密钥份额进行签名形成部分签名，任 何，个成员的部分签名可以通过特定方法形成最终签名。这样，密钥份额只在各 自的服务器上出现，即便攻破某( 几) 个( 不超过，1 个) 服务器，也不会泄漏 密钥。在现实的系统中，敌手往往会攻破一个或多个签名服务器，秘密共享就需 要在原来的集合中增加或删除成员，有时甚至需要修改门限值，这样的方案具有 更大的弹性，可以有更广的应用价值。 另外一种更强大的方法是动态秘密共享和动态安全的方法。这种方法对于一 些敏感的，长期有效的密钥的保护作用尤其明显，由于使用这些密钥的服务器往 往会面临攻击者长期的攻击，所以，攻击者可能用很长时间来攻破多于门限数目 个服务器，得到密钥。动态安全的主要思想是：将密钥的有效时间分成若干短的 时间阶段，每个阶段结束时都生成新的随机密钥份额，并删除旧的密钥份额，而 新份额重构的密钥保持不变。这样攻击者得到的密钥份额在份额更新后没有任何 价值此外，更新阶段可以构造被破坏的密钥份额。这就使得攻击者必须在一个 时间周期中，攻破不少于t 个服务器。如果密钥几年有效，而更新周期为一个周， 山东大学硕士学位论文 攻击者面临的问题是，用一个周的时间完成原来几年时间的攻击，这是十分困难的。 1 2 本文的研究内容和取得的成果 本篇论文主要对秘密共享中若干方面进行研究，所取得的成果如下： ( 1 ) 提出了一个新的基于加法秘密共享的动态安全秘密共享方案，与以往方案不 同，提出的方案能适合于要求不能公开共享秘密所在域的r s a 体制( 否则可 以计算出密钥) ，方便形成高效动态r s af - j 限签名方案，也方便的转化为基 于离散对数的动态门限签名方案。 ( 2 ) 提出了本章提出了一种新的数据内容秘密共享方案，方案具有良好的弹性， 当有新的服务器想参与系统时，它可以在服务器组的帮助下自由加入。相反， 当有服务器想退出系统，它也可以离开。同时也可以自由修改门限值。 ( 3 )提出了一个可验证的秘密共享多成员加入协议，方案需要很少的广播数据和 广播次数，新成员可以验证他们份额的正确性，并能抵御移动的恶意敌手。 方案另一个重要的优点是当多个新成员同时加入时，其他成员的份额不需要 修改，从而降低了密钥管理的复杂性。 1 3 本文的组织 文章以下的章节是这样组织的： 第二章主要介绍了一些秘密共享相关的内容，包括：秘密共享( s s ) 、可验证 秘密共享( v s s ) 、公开可验证秘密共享0 v s s ) 、动态秘密共享0 s s ) 的一些基本思 想及研究状况。 第三章提出了_ 个新的动态秘密共享。方案提供对子密钥周期性的更新，子 密钥更新后共享的密钥仍然不变，提供对子密钥正确性的检测，提供对错误子密 钥的恢复等动态属性；方案实现的各子协议十分简单，可方便形成高效动态r s a 门限签名方案。 第四章，提出了一个新的数据内容秘密共享方案，方案具有良好的弹性，可 应用于保护各种重要的信息内容。我们给出了相关的安全性分析。 第五章主要对秘密共享中多成员的加入协议进行研究。提出了一个秘密共享 中多成员的加入协议，分析了协议的安全性并与相关工作的性能进行了对比。 第六章对本篇论文进行了总结，并对未来工作进行了展望。 2 山东大学硕士学位论文 + l 2 1 秘密共事 第二章相关研究工作的现状 秘密共享是信息安全及信息保密的重要工具，它可以直接应用于密钥的安全 存储。其主要思想是将一个秘密( 密钥) s 计算成一个份额瓯，品，并将这些份 额分发给刀个服务器成员p = 最9 * o o ，只) ，每个成员都持有一个份额，只有p 中的 特定子集( 授权子集) 才能恢复出秘密j ，而其它子集( 非授权子集) 则不能恢 复秘密s 。如果对每个非授权子集都得不到关于秘密s 的任何有用信息，就称为 完美的秘密共享。如果份额和秘密所在的空间相同，就称理想的秘密共享。秘密 共享可以有效的防止密钥的泄漏和损坏，这是因为敌手攻破授权子集中的所有成 员获得密钥是非常困难的。秘密共享最早由s h a m i r 1 和b l a l d e y 2 提出，而文献 【3 6 】对一般访问结构的秘密共享进行了研究。其中，s h a m i r 的( f ) 秘密共享是最 为常用的秘密共享方案。下面，简单介绍一下s h a m i r 的( ， 刀) 门限秘密共享方案。 分发者d 要分发的秘密为七e 乙，任意选择卜1 个值a j 钿z 口，俨l t - 1 ) ，构 成多项式八对= 七+ a j x j ( m o d q ) ，为所有成员i t , ep 产生秘密的份额： 而= ( d = 七+ a p ( m o d q ) 将秘密份额毋秘密传送给成员毋。 重构秘密憾通过任何t 个成员的授权子集s ( b r p ，i b i - ，) ，可以插值计算 七= g 西( m o d d ，其中c 厦=兀舟o d q ) t b 乃e 矗、 毋 u ， s h a m i r 的( f ，哪门限秘密共享方案是完美的秘密共享，但这个方案存在以下问 题：( 1 ) 分发者的诚实性问题。没有解决如何验证分发者发给各成员秘密份额正确 性的问题。( 2 ) 各成员的诚实性问题。成员发送秘密份额或部分签名时，无法验证 其正确性。 2 2 可验证秘密共享o t s s ) 为了解决上述问题，v s s ( 可验证秘密共享) 协议形成了，首先提出v s s 的 思想并形成协议的是文献【刀，而f e l d m a n 提出的协议【8 】和p e d e r s e n 提出的协议【9 】 是两个著名的v s s 协议，在他们的协议中，分发者不但分发秘密的份额，而且广 播对其的承诺，当各成员收到其份额时，要验证其份额是否正确，在密钥重构阶 段，参与成员也采用同样的方法来验证其它成员密钥份额的正确性，协议【7 】是计 3 山东大学硕士学位论文 j ii 罾 算上安全的，而协议【8 】则是信息论上安全的。文献【9 】提出的v s s 协议不但可以 得到两个共享秘密的乘，而且不增加共享多项式的指数。v s s 协议在密码学中具 有重要的基础性地位，它是分布式密钥生成协议【1 0 】的基础，是多方安全计算 【1 1 一1 4 】的基础，也是构成许多门限方案的基础。 下面，我们主要介绍最为著名的两个v s s 协议：f l e d m a n v s s 协议和 p e d e r s e n - v s s 协议，前者是计算上安全的，而后者则是信息论上安全。这两个协 议是后面章节需要用到的知识。 2 2 1f l e d m a n v s s 协议 分发者d 选择要分发的秘密为je 乙，随机选择乙【x 】中的多项式 t - i ( 曲= j + a j x j ( m o d q ) ，为每个成员刀( j = l 帕产生秘密的影子母= 厂( f ) ，将毋秘 密传送给毋。分发者广播承诺s o = g ，和白= 9 4 j ( m o d p ) ，( j ；= l t - 1 ) ，成员露利用等 t - i 式g 而兰兀句( m o d p ) 来验证岛的正确性。 重构时：任何，个成员的集合艿拿出他们的份额，计算墨= 丹。口g 函。通过 等式g k 岛来验证s 的正确性。 2 2 2p e d e r s e n - v s s 协议 分发者d 选择要分发的秘密为s 乙，广播对其的承诺扇= 胪，这里 k 乙。 t - i 随机选择乙【x 】中的多项式( x ) = s + a x j ( m o d q ) 和 ，- i ，” g ( x ) = 七+ b j x j ( m o d q ) ，为计算岛= 厂( f ) 和七f = g ( 力，将 ，毛) 秘密传送给曰， 并广播对多项式系数的承诺易= g 乃胂。成员异利用等式g 卸h 南二兀马( r o o d p ) i = o 验证 ，毛) 的正确性。 重构时：任何f 个成员构成的集合b 中的成员露拿出他们的份额 ，局) ，计 算s = 毋。口g 毋和七= ，j 。占g 毛。通过等式h t 三岛来验证s 的正确性。 4 山东大学硕士学位论文 - i i ii _ 2 3 公开可验证的秘密共享( p ，s s ) 协议 在可验证秘密共享协议0 5 1 7 】中，还有一类称为公开可验证秘密共享 ( p v s s ) 协议。p v s s 协议克服了一般可验证秘密共享中，各成员只能知道自己 的份额的正确性，而不知道其它成员的份额是否正确的问题。p v s s 应用非常广， 可用于设计新的密钥托管系统，可撤销匿名性的电子支付协议及电子选举协议 等。考虑到p v s s 的协议不多，但具有非常广阔的应用，构建新的高效安全的p v s s 协议也是一项有意义的工作。 2 4 动态秘密共享 秘密共享和门限密码的方法大大提高了密钥的安全性。但对于一些敏感的， 长期有效的密钥( 如c a 的密钥，银行对电子货币签名的密钥) ，往往受到攻击者 长期、逐步的攻击。攻击者可能用很长时间来攻破多个服务器，从而得到密钥。 动态秘密共享就是用来解决这个问题的。它通过周期性的更新密钥份额，使得攻 击者得到的份额在密钥份额更新后没有任何价值，更新周期一般是一个比较短的 时间，而更新的份额重构的密钥保持不变。此外，更新阶段可以构造被破坏的份 额。这就使得攻击者必须在一个时间周期中，攻破不少于，个服务器。如果密钥 几年有效，而更新周期为一个周，攻击者面临的问题是，用一个周的时间完成原 来几年时间的攻击。文献【1 8 】提出了一个动态秘密共享的方法，它对于后来形成 的动态公钥加密系统和动态签名系统具有重要的作用。 o s t r o v s k y 和y u n g 1 9 1 第一次提出了动态敌手的模型和动态安全的概念，文献 2 0 1 第一次完成这个概念的实际应用。随后文献【2 l 】则给出了动态签名的概念和基 于离散对数动态签名的模型，结合文献【2 2 】的方法g e n n a r o 等人给出了动态d s s 签名算法瞄】，动态的r s a 方案的构造要复杂的多，文献【2 4 2 6 】等文献给出了一 些动态r s a 方案。 动态秘密共享可应用于：长期有效的认证中心的密钥管理，电子商务中银行 电子货币的签名密钥管理，公开的时间邮戳服务器，安全数据库的密钥管理等很 多场合。因此，研究新型的动态秘密共享方案具有很强的现实意义。 山东大学硕士学位论文 2 5 ( - - j - 验证) 秘密再分发协议 在门限签名中，由于攻击者可能攻破签名服务器或者对签名成员动态管理 ( 加入或退出) 的需求，我们就希望通过影子瓯，晶重新分发秘密k 的新影子 耐，西到一个新的个服务器成员的集合。由于信任的分发中心在首次秘密分发 后就已经离线，而服务器成员又是不可信任的( 可以被敌手破坏) 。因此我们要 求协议在重新分发秘密的时候不需要进行秘密的重构。这就是秘密再分发( s r ) 协 议，如果各成员能够验证分发秘密的正确性，就称为可验证秘密再分发( v s r ) 协议。 m a r t i n 等【2 7 】引入了一些评价秘密再分发协议效率的框架和技术。文献 2 9 】 首次提出一个改变访问结构的秘密再分发协议，不需要新旧成员集合保持特定的 关系，但其方案假定各分发成员是诚实的，没有提供对秘密影子和子影子正确性 的验证。文献 2 9 1 针对 2 8 1 的不足，提出了一个可验证秘密再分发( v s r ) 协议， 它利用了f e l d m a n 的v s s 协议来保证子影子的正确性，同时也可验证秘密影子的 正确性，但无法鉴别错误秘密影子的来源。文献【3 0 】给出了v s r 协议在安全数据 库中的应用。文献【3 i 】给出了一个基于加法共享可验证再分发协议，解决了文献 【2 0 】中不能鉴定错误成员的问题。文献【3 2 】提出的方案则可以解决动态秘密共 享中的强假设问题。 6 山东大学硕士学位论文 , _i i 3 1 主要思想 第三章新的动态秘密共享 提出了一个新型的动态秘密共享方案。其主要思想是：各服务器成员露持有 共享密钥d 的子密钥4 ，满足二4 - d ( m o d q ) ，对子密钥碣的备份采用的是门 限的方法，即，毋将其子密钥4 以( f + l ，刀) 门限的方式共享于刀个成员，当检测到 露被攻破时，其它成员它利用西的备份插值恢复正确的西。鲁棒性和安全性：从 协议的描述的简单性考虑，我们采用计算安全的f e l d m a n 的v s s ( 可验证秘密共 享) 方法，也可用信息论安全的p e d e r s e n 的v s s 方法替换，使用v s s 的方法可 以防止主动敌手的攻击，来保证鲁棒性。动态性：t 时间段时，子密钥的更新满 足： s d ( ，) 鲁二l 。而( ，- 1 ) = d ( m o d q ) ，并保证更新结束时，毋子密钥的备份可恢 复的是新的子密钥面一 本章的贡献如下：提出的新方案提供对子密钥周期性的更新，子密钥更新后 共享的密钥仍然不变，提供对子密钥正确性的检测，提供对错误子密钥的恢复等 动态属性；方案实现的各子协议十分简单，特别是错误子密钥恢复协议，与以往 方案不同，不需要v s s 操作；方案的另一个很大的优点是，由于采用的是加法秘 密共享的方式，正适合于要求不能公开共享秘密所在域的r s a 体制( 否则可以计 算出密钥) ，可以用f e l d m a n z 一i , s s 的方法( x q ，形成高效动态r s a 门限签名 方案，密钥的大小可以被r s a 模的常数倍界定，而以前动态秘密共享方案难于形 成高效的动态r s a 门限签名方案，不具备这种属性，同时本方案也可方便的转化 为基于离散对数的动态门限签名方案。 3 2 采用的模型 假定系统由刀个服务器成员 层，最，只) 构成，共享的密钥为d ，使用的是 o + l ，刀) 秘密共享。 ( 1 ) 服务器和通信模型： 假定每个服务器成员都有各自的随机数生成器，而系统是同步的，即，各服 务器使用一个公共的全局时钟。各服务器成员连接到一个公共的广播介质c 上， 7 一 山东大学硕士学位论文 发送到c 上的信息可立即到达与之相连的实体，各成员可以识别消息的来源。各 成员之间有分别存在一条秘密通道，不考虑签名和加密的密钥更新，假定广播信 息的格式错误，或通信错误( 重发同一信息多次或没有发送应该发送的信息) 系 统可以直接检测到，这些假设有助于更关注于协议的高层描述。 ( 2 ) 时间段： 整个生命周期分成若干时间段。每个时间段包含一个短时间的u p d a t a 阶段， 此阶段执行一个交互的更新协议，得到密钥d 更新的子密钥；然后是密钥恢复阶 段，各成员用子密钥恢复密钥d 。 ( 3 ) 移动敌手： 敌手在每个时间段的任何时刻都可以攻破服务器。如果一个服务器在更新阶 段被攻破，我们就认为它在相邻的两个阶段都被攻破。敌手不能在一个时间段内 攻破多于t 个的服务器。攻破一个服务器就意味着：可以了解这个服务器的秘密 信息，修改其数据，改变其行为，终止其与通信通道c 的连接。敌手连接到c 上， 就可以窃听到上面的所有信息，但不能修改它们，也不能阻止没被攻破的服务器 收到信息。 ( 4 ) 敌手在服务器上的可清除性 假定当敌手入侵某个服务器被检测到时，就可以将敌手从这个服务器上清除 ( 如重起这个服务器) ，重起操作是由于多个服务器申请，系统管理员触发的， 重起操作时间十分短暂。 3 3 方案描述 选取大素数bq ，满足qlp - i ，q 是z ；的唯一q 阶子群，g 是q 的生成元， ( p ，q ，g ) 是由信任实体或由分布协议生成。 整个协议是子协议：i n i t , u p d a t e ，r e c o n s t r u c t 构成的三元组( 1 n i t , u p d a t e ， r e c o n s t r u c t ) 。 3 3 1l n i t 协议 i n i t 协议是由可信中心d 完成的，虽然我们信任d ，但我们设计的协议仍然 可以监督d 的行为是否正确，保证系统的鲁棒性。 d 随机选择秘密d r 乙，然后，随机选择4 ( o 旬乙( ie 1 。a - t ) ，令 n - i 以o ) = d - 4 ( 。) ( m o d q ) l = l 8 山东大学硕士学位论文 - _ l _ - - _ 曼昌| 寞薯皇曼皇鲁量量鼍_ 一i i i l ( 1 ) 显然有鄙o ) - d ( m o d q ) ，秘密传送妒 给毋，计算并广播占= 矿( m o d p ) 和 蜀( o ) = g 群m ( m o d p ) ，o l 。j l ) d 为只o l 。j ，) ) 选择t 个随机数q o 钿乙，伽 1 ，) ) ，形成多项式 f o ( 工) = + 珥( o ) x ( m o d q ) ez q x i l i ( 2 ) 计算西。o ) = f o ( 歹) 并秘密传送给乃，计算并广播g q 一( m o dp ) ，( me 1 j ) 和 局。，( ) = 矿j 们( m o d p ) ，( ， 1 j ， ) 毋( f l 。j ， ) 收到所有广播后，验证： 7 岛o ) 善( m o d p ) ( 3 ) 兀句( o ) 皇占( m o d p ) j = i ( 4 ) 句0 兀( 驴7 - _ _ 5 g d j 0 ( m o d p ) m r = l ( 5 ) 其中j l 。柚。如果三个等式都通过验证，则说明d 行为正确；反之，不正 确。 3 3 2u p d a t e 协议 u p d a t e 协议是由子协议： s h a r e r e n e w a l ，b a d _ s h a r ed e t e c t i o n ， b a d _ s h a r e _ r e c o v e r y ，a c c u s e c h e c k 组成的四元组( s h a r e r e n e w a l ， b a d _ s h a r e _ d e t e c t i o n ，b a d _ s h a r e _ r e c o v e r y ，a c c u s e c h e c k ) ( 1 ) s h a r e _ r e n e w a l 协议 此协议完成对各成员对其子密钥的更新，更新要保证新的子密钥仍然是密钥 d 的有效子密钥，其备份恢复的是正确的更新子密钥 对于每个成员毋o l 。j ， ) ： 随机选择毋乙u e l 。鼻一l ) ，令 西= d 一) - - 毋t ) 9 山东大学硕士学位论文 i i i 一i 一 显然有毋。尸- - d h ) ( m o d q ) ，秘密传送毋给( _ ， l 。， f ) ，计算并广 1 1 播白。，) = 旷”( m o d p ) ，u e 1 ， ) 只收到所有广播信息后，验证： 白j ( oz g 冉n ( m o d 力 ( 7 ) 兀白_ ( ，) 主岛，- 1 ) ( m o dp ) m - i ( 8 ) 若不成立则执行a c c u s e _ c h e c k ( 毋，毋) ，令不诚实的为e ，执行 b a d _ s h a r i n g _ r e c o v e r y ( p , ，t - 1 ) ，转。 只更新子秘密：鄙n = s j ，i ) ( m o d q ) ，然后计算： 乃( ，) = 兀e m j o ( r o o dp ) ，( _ ， 1 ，l ) m - i ( 9 ) 毋选取选择，个随机数口，。( ，白z 叮，( me l m ，形成多项式 石( ， ( 力= 面( o + q 。- o z 一( m o dq ) z a x j - ，l l ( 1 0 ) 计算并将4 ，) = o ( j f ) 秘密传送给乃，计算并广播矿( m o d p ) ，伽e 1 砧) 和岛，n = g 也，n ( m o d p ) ，u l 。啦) 只收到所有广播信息后，验证： ， 蜀，( ) 兰驴，( n ( m o dp ) ( 1 1 ) 蜀( ，) 兀( g q ) 厂量句”( m o d p ) m = l ( 1 2 ) 若不成立，执行a c c u s ec h e c k ( 乃，露) ，令不诚实的为只，执行 b a d s h a r i n g _ r e c o v e r y ( p , ，t - 1 ) ，转。 所有成员都成功更新子秘密后，删除过时信息。 l o 山东大学硕士学位论文 - _ l _ 一i mm n n m m - n n i l l l _ ( 2 ) b a ds h a r e _ d e t e c t i o n 协议 每个刀都广播 乃， 旭 ， 刀得到所有的广播后，找出与大多数成员值 不同的所有成员( 不诚实成员) e ，执行b a d _ s h a r i n g _ _ r e c o v e r y ( p , ，f ) 。 ( 3 ) b a d _ _ s h a r er e c o v e r y ( 只，乃 毋o ，) 秘密传送4 ，r ) 给毋。 只验证： g d , n - - - 6 , - ，( r ( m o dp ) ( 1 3 ) 如果不成立执行a c c u s e _ c h e c k ( p , ，只) 协议。 e 选择，+ 1 个正确的d , , r ) ( i e c ，i c i - t + 1 ) ，利用l a g r a n g e 插值恢复r ) ( 4 ) a c c u s e _ c h e c k ( 只，昂) 协议 当指控是由等式( 7 ) ( 8 ) ( 1 3 x 1 4 ) 验证引起的，则尼公开锄，j 、如一，) 、如一( r ) 或 如，) ，其它成员通过等式( 7 ) ( 8 ) ( 1 3 ) ( 1 4 ) 和构成秘密通道的s o j ， 、如j ，) 、如一r ) 、 如的密文判断谁不诚实。当由等式( n l x l 2 ) 验证引起的，其它成员可简单的用公 开消息验证等式是否成立，从而判断谁不诚实。 当发现不诚实成员只时，首先报告给系统管理员，当系统管理员收到大多数 成员报告e 是不诚实时，它就重起毋。解除敌手对其的控制。 p j ( j e 1 川、m ) 把它的子密钥以。) 秘密传给指定信任成员毋，刀验证： p ) - g d 9 ( 1 4 ) 若不成立a c c u s e c h e c k ( 露，弓) ，执行b a d _ s h a r i n g _ r e c o v e r y ( 乃，d ，最后恢 复秘密： d 詈d j ( m o d q ) j _ 0 5 ) 3 4 安全性分析 引理1 假定离散对数问题是难解的， 定理1 假定离散对数问题是难解的， 则f e l d m a n v s s 协议是安全的 则本方案是正确的和鲁棒的。 山东大学硕士学位论文 量| | 一i i i i 皇皇鼍量鼍量i 证明：首先在i n i t 阶段，第步的等式( 3 ) ( 4 ) 的验证，保证了每个成员 曰( ， l 。，) ) 持有的子秘密4 ( 。) 满足：西o ) = d ( m o d q ) ，假定离散对数问题是难 解的，由引理l ，第步等式( 5 ) 的f e l d m a n - v s s 验证方法保证了p , ( i e l 。j l ) 持 有的弓子秘密的正确的影子办j ( o ) ，即，任意什1 个成员的力，o ) 可以l a g r a n g e 插 值形成一( o ) 。满足正确性和鲁棒性。 使用归纳法，假设在第f 1 个时阿段，各成员持有的子密钥是正确的，即， 4 ( 一) - - d ( m o d q ) 。在第t 个时间段，子密钥只有在s h a r e r e n e w a l 和 b a d _ s h a r e _ r e c o v e r y 协议中改变。s h a r e r e n e w a l 中步中等式( 7 x 8 ) 的验证保证 了v ie 1 。j l ，所有成员的函尸u 1 刀 ) ，s j 墨，( ，) = d 纠) ( m o d q ) ，又由归纳 假设得，d 墨碣( ，_ 1 ) 量毋尸) 善乃j ( ，) 暑刃( ，j ( m o d q ) ，显然保证更新后 子密钥的正确性，由引理l ，假定离散对数问题是难解的，的步中的 f e l d m a n - v s s 的验证方法保证了任意什1 个诚实成员的面，t ) ，都可以l a g r a n g e 插 值形成正确的面，) ，满足鲁棒性。b a ds h a r e _ r e c o v e r y 中，等式( 1 3 ) 的验证保证了 任意什1 个诚实成员的4 。r ) ，都可以l a g r a n g p 插值恢复正确的影r ) 。所以整个协 议具有正确性和鲁棒性。 引理2 对于多项式( x ) = s + 岛一( m o d q ) ，s j 厂( d = ，( ，e l 。j ) ，存 在一个算法彳：当输入，嘞，嘶和g 一( m o d p ) 时，可以计算驴，g 吃，g q 的值。 证明：多项式可定义为另一种表达形式： 删。骞州乳哥暑喜南归风卜y ( m 咖) ，其中铴鄙展开 扣 o ， i f l 多项式整理的妒项的系数口i 善亍= ! 冬私( m o d q ) ，其中七 l 。， ，五，是可 丽ilu 一，j j e 一o 一永l f 计算的已知常数。构造算法a 对所有的k l 。n 做以下计算： 1 2 山东大学硕士学位论文 _ _ _ _ _ 一i l i _ | 曼曼曼曹_ 曩鼍圈鼍_ 墨 矿暑g套枣aalo-tp4nj 一量血g 丁而幻删| ，g q 暑g 量ii g 月“。 毫，争q ，血g 京幻 吡矿一和- ，卉( 一矿 删力 定理2 假定离散对数问题是难解的，即使出现t 个不诚实的恶意成员，本方 案仍然是安全的。 证明：定理2 的证明等价于证明：对于恶意敌手a ，存在虚拟器s i m ，满足 v e w a 和s i m 计算上没有不同。 对于l n i t 协议，输入：g ，。 构造s i m - 计算： 1 ) ( a ) 选择孑( o z q o 2 t l 时，即使出现f 1 个不诚实成 员，仍然有超过半数以上( 至少为t 个) 成员是正确的，错误的份额或者备份可 以由等式( 3 搿) ( 5 ) ( 7 ) ( 1 2 ) ( 1 3 ) ( 1 7 ) ( 1 8 ) 检验到，错误的服务器可以通过重起操作解 除敌手对其的控制。而正确的成员可以通过他们正确的备份来恢复出重起的服务 器的份额和备份，方案仍然可以正常运行，又由定理l 得，方案可以执行得到正 确的结果，因此是鲁棒的。 定理3 ( 安全性) 假定q 中计算以g 为底的离散对数是不可行的，即使一 个敌手可以攻破上述方案中扣1 个存取份额的服务器，他仍然得不到关于共享秘 密信息的任何有用知识。 证明：首先，因为a 中，- 1 成员知道的只是它们各自的份额和持有的其他成 员份额的备份份额，彳中所有成员用来份额备份的秘密多项式是f 1 次，卜1 个成 员所知道的多项式上点的个数不超过f _ 1 个，由s h a m i r 的( f ，刀) 方案的安全性，可 知他们无法计算其他成员份额，也就无法得到所有份额的和，即，不能得到关于 秘密的任何有用信息。其次，因为假定g 口中计算以g 为底的离散对数是不可行的， 又由f e l d m a n 的v s s 方案的安全性可得：协议执行中所有的公开承诺都不会泄漏 共享的影子信息，所以，即使一个敌手可以攻破上述方案中，- 1 个存取份额的服 务器，他仍然得不到关于秘密的任何有用信息。 4 4 小结 提出了一个弹性分布式信息内容安全方案，可用于保护密钥、机密文档、敏 感信息、私人数据等重要信息，方案采用的技术结合了加法共享和秘密共享的各 自优点，并可以动态的加入和删除服务器成员，并修改门限值。最后，证明了方 案是正确的和安全的。 山东大学硕士学位论文 第五章秘密共享中多成员的加入协议 5 1 符号和假设 假定p 和g 是素数，满足q i p - i ，g 是阶为q 的群z ，的生成元，令l | p 表 示整数p 的比特长度。 旧份额持有者集合尸是由成员眉，b ，只构成，秘密后通过s h a m i r 的( ，力秘 密共享在这些成员中共享。 要加入的成员集合，是由成员耳，恳，吖构成。新的集合为 p u p = 露，以，耳，爿 ，最终秘密通过s h a m i r 的( f ，n + r ) 秘密共享在这些成员 中共享。 5 2 提出的多成员加入协议 假定每一个成员只都有一个公私钥对 ，4 ) e n c 和d e c 是安全的公钥加 密和公钥解密算法弓使用公钥白加密数据e n c 畸( d a t a ) ，只可以通过 d e c , i , ( e n c 日( d a t a ) ) 解密数据。 初始化：分发者选择一个随机多项式 厂( 力= s + ：= ：珥一引蝴 ( 1 ) 计算：岛= ( 力，i = l ，2 ，刀。分发者广播g s ，g q o = l ，2 ，t - i ) 并将毋告 诉刀。每个毋( f = l ，2 ，玎) 验证下列等式是否成立： 矿= g 。n ：( 舻ym o d p ( 2 ) 如果成立，他就相信他的份额是正确的，并存储承诺g ，和舻u = l ，乙，t - i ) 。 每个成员刀( ，= 1 , 2 ，疗) 选择一个私钥以，并广播公钥e t 加入协议：当成员厅( ，= l ，2 ，刀) 想加入集合p f p , ，恳，只) ，$ i l - j 限值不变 时，执行以下协议。首先，加入成员从集合尸中联合选择2 t - 1 个成员，不失一般 性，假定选择的成员是毋，忍，最，- 令集合石= e = 彩。加入协议描述如下： ( 1 ) 假如成员( ，= l ，2 ，刀7 ) 随机选择一个秘密刃并广播公钥信息l e l ( 2 ) 每一个旧份额持有者e , ( i - i ，2 ，2 t 1 ) 选择个随机多项式 ( x ) = = 一( m o d q ) ez q x 2 1 山东大学硕士掌位论文 ( 3 ) 这里，= l ，2 ，刀 露计算彰= f ，) ( j f ) ，j = l ，2 ，2 i - 1 ，n + l ，并广播消息2 e ，( 硝) l ，。 i 2 ，2 ，i i 、 l ，i i 2 ，j ， ，e 7 ( 6 澎_ ) ) l ，i i 工 ， 彰= g 口：，l i o 凡。j - i ；t , 1 2 ，一 ， 硝= g 衫价 1 2 一，2 ，i 一+ ， ， f l 闰k ，以) ( 3 ) 每个成员p j ( y = l ，2 ，2 t - 1 ) 解密消息 彰= d e c d , ( e n c , , ( 岛i ”， ，= l ，2 ，f 1 ，2 ，2 t 1 ) j ，验证下面等式是否成立： 甜= g 彰( m o d p ) ( 4 ) 彰) = 兀t 。- 小i _ 。( ，) ) ，( m o dp )