SHamir分发密钥机制.pdf

发布时间：2022-06-11 发布人：admin 分类：说明书资料大小：0.48M 资料格式：pdf 举报版权申诉

liquan_-10776549-4744302542858236810.pdf-第1页.png

第1页 / 共10页

liquan_-10776549-4744302542858236810.pdf-第2页.png

第2页 / 共10页

liquan_-10776549-4744302542858236810.pdf-第3页.png

第3页 / 共10页

liquan_-10776549-4744302542858236810.pdf-第4页.png

第4页 / 共10页

liquan_-10776549-4744302542858236810.pdf-第5页.png

第5页 / 共10页

liquan_-10776549-4744302542858236810.pdf-第6页.png

第6页 / 共10页

liquan_-10776549-4744302542858236810.pdf-第7页.png

第7页 / 共10页

liquan_-10776549-4744302542858236810.pdf-第8页.png

第8页 / 共10页

2015083

第 36 卷第 3 期 2015 年 3 月 doi:10.11959/j.issn.1000-436x.2015083 通信学报 Journal on Communications Vol.36 No.3 March 2015 基于 Shamir 秘密共享的密钥分发与恢复算法 1 1 1 2 荣辉桂，莫进侠，常炳国，孙光，龙飞 3 （1. 湖南大学信息科学与工程学院，湖南长沙 410082； 2. 湖南财政经济学院信息管理系，湖南长沙 410205；3. 长沙大学经济管理系，湖南长沙 410003) 摘要：在经典的 Shamir 秘密共享方案中，秘密分发者把秘密 s 分为 n 个影子秘密并分发给持有者；其中任意不少于 t 个影子秘密均能恢复秘密 s，少于 t 个影子秘密则得不到秘密 s 的任何信息。现实的秘密恢复过程中可能存在超过 t 个参与者的情形。因此，在 Shamir 的秘密共享方案基础上讨论此种情形下秘密共享问题，通过引入影子秘密的线性组合——拉格朗日因子来恢复秘密，并进一步将其扩展为一个多秘密共享方案。理论分析与仿真实验表明：改进算法在同样复杂度条件下既保证影子秘密的安全，又能阻止欺骗者得到秘密，提高了整体安全性。关键词：秘密共享；密钥分发；拉格朗日因子；密钥恢复中图分类号：TP393 文献标识码：A Key distribution and recovery algorithm based on Shamir's secret sharing RONG Hui-gui1, MO Jin-xia1, CHANG Bing-guo1, SUN Guang2, LONG Fei3 (1. College of Computer Science and Engineering, Hunan University, Changsha 410082, China; 2. Department of Information Management, Hunan University of Finance and Economics, Changsha 410205, China; 3. Department of Economics and Management, Changsha University, Changsha 410003, China） Abstract: In Shamir's secret sharing scheme, the dealer divided the secret s into n shadows and distributed it to share- holders in such a way that any t or more than t shadows can recover this secret, while fewer than t shadows cannot obtain any information about the secret s. During the actual secret recovery process, there exist other cases with more than t par- ticipants. The case of secret sharing problem was discussed based on Shamir's secret sharing scheme and reconstructs the secret by introducing a linear combination of shadows—Lagrange factor. Then, the improved algorithm of key distribu- tion and recovery was proposed and extended to a multi-secret sharing scheme. Theoretical analysis and simulation show that the improved scheme improves its security under the same conditions of complexity. Key words: secret sharing; key distribution; Lagrange factor; key recovery 1 引言影子秘密并分发给持有者，其中任意不少于 t 个影子秘密均能恢复秘密，少于 t 个影子秘密则得不到秘密共享技术是密码学和信息安全的一个重主秘密的任何信息。它的出现解决了密钥安全保管要研究内容，被广泛应用于密钥管理及数字签名领的基本问题，既能保证秘密的安全性、完整性，又域。它最早由 Shamir[1] 基于 Lagrange 插值多项式和矢量方法提出。其基在 1979 年分别和 Blackly[2] 能防止秘密过于集中而带来的风险。由于秘密共享在数据保密及信息安全中扮演重要角色，对信息保本思想是分发者通过秘密多项式将秘密 s 分为 n 个存、传输及使用过程起着非常关键作用，在现实应收稿日期：2014-09-14；修回日期：2015-02-10 基金项目：国家自然科学基金资助项目(61304184)；国家科技支撑计划基金资助项目(2013BAH45F02)；科技部创新基金资助项目(13C26214304053)；湖南重点建设学科基金资助项目；湖南大学“青年教师成长计划”基金资助项目(531107021115) Foundation Items: The National Natural Science Foundation of China (61304184); The National Key Technology Support Program (2013BAH45F02); The Innovation Foundation of Science and Technology Ministry (13C26214304053); The Construct Program of the Key Discipline in Hunan; The Young Teachers Development Plan of Hunan University (531107021115) 2015083-1

第 3 期荣辉桂等：基于 Shamir 秘密共享的密钥分发与恢复算法用中应严格保证其安全性能。早期的秘密共享是基于分发者和参与者的诚实性建立的，但在实际应用中经常会存在以下 2 类安全隐患：外部攻击和内部欺骗。外部攻击是指 [3] 具有可验证性，可防止分发者和参与者欺骗；是一个理想的秘密共享方案，即信息率 1 r = ；方案不需要安全通道，降低通信开销；通过更新访问结构即可更新参与者或秘密。Hu C 等 [10] 提出 2 个安全有授权子集外的人伪装成授权子集的成员去骗取他效的可验证秘密共享方案，方案Ⅰ使用拉格朗日们的影子秘密，从而恢复出秘密。内部欺骗分为 2 插值多项式把秘密分成影子秘密并通过基于 LFSR 种情况：授权子集中的某个参与者提供假的影子秘的公开密码系统验证数据的有效性；方案Ⅱ通过密，从而使秘密恢复失败；秘密分发者欺骗，即分 LFSR 序列和基于 LFSR 的公开密码系统实现。这 2 发者在下发影子秘密时可能会给参与者无效的影个方案具有更好性能和更低的计算复杂度，能有效子秘密。为了解决上述问题，已经有许多学者做了地检测出各类型欺骗行为，保证秘密恢复的安全性诸多探索与研究，主要可分为如下 2 种类型：可验和可靠性，在实际应用中更易于实现，但它们不能证秘密共享和动态秘密共享。动态地增加或者减少秘密个数。 Chor 于 1985 年首次提出可验证秘密共享的概预防欺骗的另一种方法是 Laih 等 [11] 在 1990 年 [4] 念，通过在秘密共享过程中添加一个认证过程，提出的动态秘密共享方案，该方案中参与者所拥有实现了秘密恢复过程中对子秘密的验证以防止欺的影子秘密始终保持不变，而秘密可以任意更新。骗。但是该方案需要秘密分发者与参与者进行多次假如欺骗者获得有效个数影子秘密恢复出秘密，由交互，造成通信带宽的浪费；且在验证过程中参与于秘密是任意更新的，他得到的秘密不一定是有效者仅能验证或收到影子秘密的正确性，仅能检测秘的，这在一定程度上保证了秘密安全。但是该方案密分发者诚实性而无法抵抗参与者欺骗。针对 Chor 的安全性会因秘密更新次数的增加而降低。李大伟等提出方案的欺骗问题，很多学者对其进行了深入等基于单向散列链特征构造更新多项式，从而避 [12] 研究并取得丰硕成果。其中，Kamer Kaya 等 [5] 以中免计算开销；秘密共享过程基于 IBE 公钥体制，具国剩余定理为基础提出了一个可验证秘密共享方有较好的安全性；在影子秘密的验证过程中基于有案，该方案能够阻止秘密分发者以及参与者之间相限域上离散对数难解问题有效避免了参与者欺骗。互欺骗的行为，但采用的范围证明技术导致其验证文献[13]基于单向散列函数及异或逻辑运算提出了过程繁琐，运算量较大。文献[6]提出一个密钥分发一个动态多秘密共享方案，影子秘密能重复用于多存储方案，该方案以中国剩余定理、可验证秘密共个秘密恢复；使用动态更新秘密可防止欺骗者的攻享和可信计算为基础，解决可验证秘密共享方案中击，并且有较好的复杂度。Qu J 等在文献[13]的 [14] 存在的欺骗问题及 Shamir 方案中的指数运算；基于基础上通过增加离散对数难解性使每个参与者能中国剩余定理和可验证秘密共享提出分布式椭圆自主选择影子秘密，这样可以杜绝分发者欺骗问数字曲线签名标准认证方案，可以消除传统 DoS 攻击及故障攻击可能性，并证明了其安全性。Kaya K [7] 题；方案可避免使用安全通道传送影子秘密，降低通信开销。但 MH Tadayon 等证明了文献[13]方 [15] 等分析已有可验证秘密共享方案中不能保证分发案需要安全通道及验证过程，并对其改进提出一个者欺骗情况，基于中国剩余定理提出一个新的可验无需安全通道的秘密共享方案，方案基于椭圆曲线证秘密共享方案，它能保证秘密分发过程中分发者和双线性映射的离散对数难解性假设并比文献和参与者欺骗；应用上述方案构建第一个联合随机 [11,13]更具实用性。贾秀芹等 [16] 针对圆性质的动态秘密共享协议，协议可使一组参与者在无可信分发门限秘密共享方案中分发者和参与者欺骗、秘密传者时共同生成并共享一个秘密。在文献[8]中，Harn 输需要安全通道等问题，基于 RSA 和离散对数密 L 等基于中国剩余定理提出了无任何计算假设且无条件安全的 VSS 方案，它是 Azimuth- Bloom rU 秘码体制、单向双变量函数和圆性质，提出一种抗欺诈的动态秘密共享方案，用于检测并识别秘密分发密共享方案的一个简单延伸，在验证阶段中使用秘者对参与者的欺骗以及参与者之间的欺骗，并能减密和验证秘密的一个线性组合来保护秘密及影子少重构步骤，提高重构秘密的成功率。由于在整个秘密的安全性。文献[9]基于 LUC 密码体制提出一动态过程中，圆心和秘密份额始终不变，从而减小个可验证的多秘密共享方案，在分发和恢复阶段均该方案的实施代价，使其具有更高的安全性和实用 2015083-2

通信学报第 36 卷性。文献[17]基于双线性映射提出一种无需安全通改善秘密共享过程的安全性提供新的方案。道的动态门限多秘密共享方案，该方案中秘密可以改变且门限值更具灵活性，通过双线性映射检测欺骗者。 2 Shamir 秘密共享机制 2.1 秘密共享同态除了上述动态秘密共享方案外，目前还存在一 Benaloh[25] 提出了秘密共享同态的概念，下面种与其相类似的方案——主动秘密共享方案 [18] ，通过在一个秘密共享方案周期内更新影子秘密而不改变原有秘密，欺骗者在一个周期内获得的信息在对其进行论述。 S 为主秘密空间（secret domain）， T 为对应主秘密的影子秘密空间，函数 :lF T 是 ( , ) t n 秘密共享的诱导函数（induced function）。 S 刷新之后变得毫无用处。Sun H 等在文献[19]中基该函数把基于任意包含 t 个影子秘密于椭圆和双线性对的离散对数问题提出了一个有效的主动秘密共享方案，通过周期性地刷新影子秘密提高了其安全性，并能验证影子秘密的真实性，可应用于现实中秘密及数据库的长期保护。Wang X [20] 等基于离散对数难解性假设提出一种无可信方的可适应主动秘密共享方案，参与者数及门限值在 2 个相邻时间间隔内可变保证了方案安全性，但该方案的复杂度为 )O n 。文献[21]基于曲线密码体制 3( 提出一种主动秘密共享方案，每个成员既作分发者又作验证者，由秘密生命期的变化和成员间相互验证来实现动态性和不需第三可信方，并解决了秘密更新和影子密钥复用问题；方案在安全性上有所提 2.2 Shamir 的(t,n)秘密共享方案高，具有较高实践工程价值。 Shamir 提出的 ( , ) t n 秘密共享方案是基于 { , s i 1 s i 2 , s⋯ i t , } ⋯ ，其中 , s i t ) 子集的秘密 s 定义为 = I { , s i 1 s i 2 , ⋯ 。 s , } i t = s F s ( i 1 I , s i 2 , 定义 1 秘密共享同态 [25] ：假设 ¯ 和 ˜ 分别是在集合 S 和 T 元素上的 2 个函数，如果对于任意子集 I 和 = s s , = s F s ( i 1 I , s i 2 , F s ( i 1 I , s i 1 , s i 2 , ) s i t ⋯ ， ˜⋯ , s i 2 , , , s s i t , ( F s i 1 I , , s i 2 , ⋯ 有 ) , , s i t , s i t ) ，就可认为一 = 个 ( , ) t n 秘密共享方案具有 ( , ) 同态性。由定义 1 可知，Shamir 的 ( , ) 足同态 ( , )+ + 性，即有 s + = , , ( F s i 1 I , , s i 2 , ⋯ , , s i t ) = ( F s i 1 I + , s i 1 , s i 2 t n 秘密共享方案满 tis + ) 成立。 F s s i 2 + ⋯ ⋯ , ( ) , , , , i 1 I , s i t s i t , s i 2 s + Lagrange 插值公式构造的，它可以描述如下。 [1] 域 ( ) 1) 初始化阶段：秘密分发者 D 随机地从有限 xL 标 2, x x GF p 中选取 n 个不同的非零元素 1 { , U U 1 = L ，公开 rx 及其对应的 rU 。 1, 2, 2) 秘密分发阶段： D 要分发的秘密为 , n , U L , ) n = U , , 2 r } n 识每一个影子秘密持有者 s Z˛ t - 个元素 1) q 1) +∑ 1 = 1 t i = i i p a 0 ( ) f x a x mod s> ，秘密 s 其中，p 是一个大素数且 p D 为所有的 rU U˛ 生成 n 个影子秘密 = = = + t mod ( p r f x r ( ) i a x r i ∑ 1 = 1 i a 0 s r = f (0) = 。 a 0 1, 2, L , ) n 然后把 rs 安全地发送给相应的 rU 。 3) 秘密恢复过程：任何 t 个影子秘密持有者 UL 发送他们的影子秘密并使用拉格朗 , , }t { , U U 1 2 性假设。该类方法在验证欺骗时由于需要进行数字签名和信息交互，增加了通信量和公开参数。第二 ( ia i = -L , t 1, 2, 1) （ q 为大素数），在 ( ) GF p 内任意选择 ( t - 阶多项式构成 ( 此外，防止欺骗的秘密共享方案还可以依据解决方法分为以下 3 类：公钥体制加密方案、纠错编码方案、方案本身特点。对于第一类，分发者使用公钥体制将影子秘密进行加密后分发给参与者，参与者在收到影子秘密后可利用私钥进行验证或解密，可检测影子秘密的真实性，如文献[12,14,16,19,20]，影子秘密 ( r 的验证基于离散对数的难解性，大整数分解的困难类是参与者收到分发者分发的一个编码后利用纠错码将其自动恢复，如文献[22]中方案，但若参与恢复过程中欺骗者过多时会增大通信量且验证方式有限制，一般适合于欺骗者较少的情况。另外还有一种就是使用方案本身特点防止欺骗，比如文献 [23,24]中方案利用线性集合特点、散列函数、差集等数学工具来降低欺骗的概率。显然，对于秘密共享过程中的欺诈问题，目前仍然缺乏保证高安全性、高扩展性、低复杂度的方案。本文在 Shamir 的秘密共享基础上，考虑多于 t 日插值公式个参与者时所出现的安全问题，改进其影子秘密生成方案；在保证复杂度的前提下提高其安全性，为 = s f (0) = ∑ t i = 1 ( f x l ) t = 1, v v l x v x v x l mod p 2015083-3 ﬁ ¯ ˜ ˜ ¯ ˜ - - „ - -

第 3 期荣辉桂等：基于 Shamir 秘密共享的密钥分发与恢复算法便可以恢复出秘密 s 。话说，传统的用户身份认证方案或可验证秘密共享 Shamir 的方案满足秘密共享方案的安全需求，方案需要在秘密恢复之前确保所有参与者的影子即：①任意不少于 t 个影子秘密能恢复出主秘密；秘密是有效的。由于 2 种方案一次分别仅能验证一 ②少于 t 个影子秘密不能得到主秘密的任何信息。个用户和一个影子秘密，增加了额外复杂度。此外， 3 基于 Shamir 的秘密共享改进算法在 Shamir 的秘密共享方案中，秘密分发者把秘密 s 分为 n 个影子秘密并分发给持有者，其中任意不少于 t 个影子秘密均能恢复秘密 s ，少于 t 个影子秘密则得不到秘密 s 的任何信息。现实的秘密恢复过程中可能存在超过 t 个参与者的情形，在 Shamir 的秘密共享方案基础上，通过引入影子秘密的线性组合——拉格朗日因子（Lagrange factor）来恢复秘密，并进一步扩展为一个多秘密共享方案，增强其安全性及可靠性。 3.1 秘密共享模型秘密恢复成功与否与仅与影子秘密有关。在秘密恢复过程中，欺骗者通过提供无效影子欺骗诚实的 rU 。内部欺骗者能唯一地恢复秘密，而诚实的 rU 得到无效秘密。 3.2 安全性需求在 Shamir 的秘密共享方案基础上，为满足当前的实际安全要求，提出新的安全属性需求如下。 1) 对于秘密 s ：每个秘密仅能通过任意不少于 t 个拥有有效影子秘密参与者恢复，而不能被攻击者恢复。 2) 对于影子秘密：多秘密共享方案中， rU 的影子秘密能重复用于恢复多个秘密。因此，在秘密本节对秘密共享过程中包含欺骗者模型成员恢复过程中要保证其安全，否则不能重复使用。在与过程进行描述。 3.1.1 秘密共享成员 1) 秘密分发者 D ：把秘密 s 分为 n 个影子秘密，并分发给影子秘密持有者 rU 。 2) 影子秘密持有者 rU ：拥有分发者分发有效影子秘密的成员。 3) 敌手 A ：秘密恢复过程中的敌手可以分为 2 类：内部敌手和外部敌手，外部敌手指秘密恢复时没有分发者分发有效影子秘密的攻击者，简称攻击者。内部敌手指参加秘密恢复时影子秘密持有者 rU 中的共谋成员，简称欺骗者。 4) 参与者 jP ：参与秘密恢复过程成员，包括部分影子秘密持有者 rU 和敌手 A 。 3.1.2 模型描述进行安全分析时，应检测在攻击者能得到最多信息用于恢复秘密情形的安全性，即攻击者试图获取在恢复最后一个秘密过程的影子秘密，攻击者是最后一个发送拉格朗日因子给其他参与者的成员，并可获取所有另外的拉格朗日因子。因此假设秘密恢复阶段均有 n 个影子秘密参与。 3) 对于门限值：恢复的秘密不应该妥协任何未恢复秘密的隐秘性。因为每个恢复的秘密是影子秘密的一个函数， rU 依据每个恢复的秘密建立影子秘密方程。这些方程不应该妥协影子秘密和未恢复秘密的隐秘性，否则未恢复秘密的门限值将减少。在门限安全分析阶段，将检测在敌手得到最多信息情形下门限值安全性，应假设有 1t - 个欺骗者试图在其余秘密已恢复情形下去恢复最后一个秘密，即恢复最后一个秘密时欺骗者最后发送他们的文中讨论在外部敌手参与秘密恢复过程并试拉格朗日因子。图获取秘密的安全性。当有多于 t 个参与者参与秘 3.3 改进算法流程密恢复过程时，外部敌手仍可获取秘密。下面提出文中提出的改进算法主要分为初始化。秘密分一个安全秘密恢复方案的概念。发和秘密恢复 3 个阶段，每个阶段既有它独立的过定义 2 安全秘密恢复方案。方案保证秘密仅程，又有相互联系的方面。流程图可以简要地表述能通过拥有有效影子秘密的参与者恢复，即外部敌整个秘密共享算法执行过程，如图 1 所示。手参与秘密恢复过程得不到秘密。改进算法具体过程如下。秘密恢复过程中超过 t 个参与者时，大部分论文仅讨论 t 个参与者情形。这可能存在一个安全问题：攻击者伪装成影子秘密持有者但提供无效影子 1) 初始化秘密分发者 D 随机地从有限域 ( ) GF p 中选择 = L 个非零常数 rx 并对 rU 进行标记，公 1, 2, n , ) r r ( 秘密，得到 t 个影子秘密后即可恢复出秘密。换句开 rx 及其对应的 rU 。 2015083-4

通信学报第 36 卷 rU ，并广播整数 ld 和 lw 。 3) 秘密恢复需要恢复秘密 s 的参与者 rP 向参与者成员发送恢复秘密请求，通过接 j , , j ) n L ≤ ≤ P t }( P P { , 1 2 收 1j - 个参与者发送的拉格朗日因子 rC f 密。拉格朗日因子 rC = ∑ 为秘密 s f k = 1 l 来恢复秘 d f w l ( l l ) 的一个线性组合，在秘密共享过程中的敌手得到其余参与者发送的拉格朗日因子也恢复不了真正有效的影子秘密，从而恢复出秘密 s ，可提高影子秘密和秘密的安全性；此外，秘密恢复时拉格朗日因子可以直接防止欺骗问题，从而不需要对各参与者影子秘密进行逐个验证，提高了秘密恢复效率。设 rU 中 j 个参与者组成的授权子集为f ，其执行操作如下。 f x ，参与 l Step1 通过由 D 发送的影子秘密 ( ) r 者 rP 使用式 (4) 得到其唯一的拉格朗日因子 f rC ≤ ≤ (1 r ) j f r C = ∑ k = 1 l ( d f x r ( l l ) j = 1, v v r w w v l x r x v (4) f 其中，{ 1, 2, L f n , },| | ≥ t 。 Step2 参与者 rP 在收到成员发送的秘密恢复 f 申请后，将其拉格朗日因子 rC 其余 1j - 个参与者。通过秘密通道发送给 Step3 rP 通过收到的 1j - 个拉格朗日因子 rC f 使用式(5)计算出需恢复的秘密 s 。 = ∑ s f r C j = 1 r (5) 3.4 多秘密共享扩展算法在上述改进算法描述基础上，将其扩展为多秘密共享。需要满足如下 2 个安全要求：1)每个有效的影子秘密可重复用于恢复另外的秘密；2)为了保证门限值安全，每个恢复的秘密不能妥协未恢复秘密的隐秘性。下面就扩展为 h 个秘密的算法进行描述并在 4.2.2 节证明其安全性。 1) 秘密分发 D 选择 k (其中 k 为常数且) { < k { kt - + n t 1)( 1) 2} t - 阶随机多项式 h ( = L ，并对每个对应标记 rx 的 rU 生成 1, 2, = L 。对任何一个秘密 1, 2, t 2)} ( 个 ( h n , ) k , ) k )( l 1) 1) ( lf x l ( )( 影子秘密 ( + - > f x l r , ) h = L ， D 在有限域 ( ) 1, 2, ∑ ( w l d f w w w w i = L 1,2, x x { , 1 2 , 且 ,1 ( d d i , , L k = 1 , ) k )( d ( i l , ,2 , , l i l l i j l , , i k 、 GF p 内能找到满足 L , }) x n i = )( 1,2, 的整数 , )hL 即有 f x l r ( ) = ∑ ( t m 1 = 0 m a x 1 m r , ∑ t 1 = m 0 m a x m r 2 , ∑L , t 1 = m 0 m a x km r ) (2) Step3 对任意秘密 s ， D 在有限域 ( ) GF p 内总能找到整数 ld 和 lw (其中， 1, 2, l = L , k w ; i w ; j w i { , x x 1 2 , L )满足 , } x n = s ∑ k = 1 l d f w l ( l l = ) d f w 1 1 1 ( + ) + L d f w k ( k k ) (3) ( is i = s i Step4 通过私有安全信道发送 ( f x 给对应的 l ) r d , i l 2015083-5 图 1 改进算法流程 2) 秘密分发分发过程由可信的秘密分发者 D 执行，主要用于生成分发给每个 rU 的影子秘密。秘密分发者执行影子秘密生成算法生成 n 个影子秘密并将其分发给对应的 rU 。 1) n> - 个非零系数 m t 0} 1; 构 a lm Step1 随机选择 ( kt kt { a lm | a lm GF p ( );1 l k ,0 ≤ ≤ ≤ ≤ 造 k ( k 为常数)个 ( ( ) f x l = ∑ t m 1 = 0 t - 阶多项式 + 1) = + a x l 1 a l 0 a lm + a L Step2 计算 rU 的影子秘密 ( )( f x l l r t 1 ( 1) l t x (1) = L 。 1,2, , ) k ˛ - „ - - - - - - „ ˇ „ - - ˛ ˙ - - „ ˛

第 3 期荣辉桂等：基于 Shamir 秘密共享的密钥分发与恢复算法是线性独立矢量。之后 D 公开整数 ,i ld 、 lw 及 rx 。 2) 秘密恢复 j t 在秘密恢复阶段有 ( n≤ ≤ 个参与者 ) j P P { , 1 2 , PL 来恢复秘密 is ，每个参与者使用他的影 }j , 子秘密 ( f x 计算并秘密发送一个拉格朗日因子 l ) r w x v l x r x v f ≥ t | f r C = ∑ k = 1 l d f x r ( i l , l ) j = 1, v v r = L ； {1, 2, 1, 2, f ˛ , r 给所有的参与者，每个参与者在知道另外 1j - L ， | , }n j f 个 rC 后均可使用 = ∑ k = 1 r f r ( C i = s i 1, 2, L 来恢复 , ) h 秘密。 4 算法分析与仿真 4.1 改进算法复杂度计算影子秘密 ( f x ； l ) r } } //执行 ③找到整数 ld 和 lw 计算秘密 s //执行 k 次 2nk 次 //秘密恢复 ①计算拉格朗日因子 for(l=1; l

法是正确的。通信学报第 36 卷证明要证明命题 1 只需证明式(3)和式(5)右边相等即可。由式(1)知，秘密共享过程中第 r 个参与为 rx 的 k 个秘密多项式如下 + = = + + ⋯ t 1 m t ( ) f x 1 = ( ) f x 2 ∑ ∑ 1 = m 0 a x 1 m a 10 t m 1 = 0 a x 2 m m = a 20 a x 11 + a x 21 x a 1(t 1) + a 2(t 1) + ⋯ t 1 x (6) ⋮ ⋯ ⋯ ⋯ ⋯ ⋯ ⋮ + = = + + ⋯ m t a k 0 a x k 1 ∑ 1 = m 0 a x km ( ) f x k a t 1 x k (t 1)         则 D 发送给他的影子秘密为 f x l r ( ) = ∑ ( t m 1 = 0 m a x 1 m r , ∑ t m 1 = 0 m a x m r 2 ∑⋯ , , t m 1 = 0 m a x km r ) 将式(4)代入式(5)可得 = s ∑ f C r k = 1 r = j ∑ ∑ = 1 r k = 1 l d f x r ( l l ) j = 1, v v r w x v l x r x v = ∑ j = 1 r ( d f x r 1 1 ( ) j = 1, v v r + w x v l x r x v d f x r 2 2 ( j = 1, v v r w 2 x r x v x v + + ⋯ d f x r 1 1 ( ) j = 1, v v r w k x r ) x v x v ) (7) 拉格朗日插值多项式 ( ) f x l = ∑ k = 1 r f x l r ( ) j = 1, v v r x x r x v x v (8) 由式(7)和(8)可知，式(3)与式(7)相等。因此等式(3)和(5)右边相等，即命题 1 正确。 2) 安全性本方案在秘密发送的过程中采用安全的信道进行，以避免内外部敌手。 ① 有攻击者的安全性秘密恢复过程中，如果参与者中包含持有无效密 s 的一个线性关系或者完全得不到 s 的任何信息，即得不到秘密多项式 ( ) lf x ，恢复秘密失败。因此，即使攻击者在获得 1n - 个 rC 密，算法安全。也恢复不了秘 f ② 有欺骗者的安全性接下来分析有任意 1t - 个欺骗者时该算法的安全性。欺骗者试图从他们自己的影子秘密 = ∑ ( t 1 = ) ( m a x f x ) l r km r lf x l = 复秘密。由于在 k 个 1t - 阶多项式 ( )( m a x m r m a x m r 1 , , m m m 2 0 0 0 ∑⋯ , t 1 = t ∑ 1 = 恢 1, 2, , )k⋯ 上秘密 = ∑ k = l 1 者使用他们持有的 ( s d f w l ( l l ) 是一个线性组合。欺骗 k t - 个影子秘密可构造 ( k t - n> - （ kt 是每个 ( 1) t - 阶多项式 = ⋯ 未知系数个数），欺骗者解不出秘 1) 1) kt 1 个方程。因为 , ) k 1, 2, lf x l ( )( 密多项式 ( ) 能通过 1t - 个影子秘密恢复出秘密。 lf x ，秘密恢复失败。因此内部欺骗者不此外，对于任意秘密 s ，针对每对 i 和 j ，秘密 l l l ) ( s k = 1 w w„ 时 D 需要选择 i d f w l = ，对于每对 i 和 j ，敌手在知道 t 个 rC = ∑ = w w w 仍能恢复出秘密。这是因为秘密 s 是一个由 1t - 阶叠加而成的，每个参与者 rP 需要 ( ) d f x =∑ 。如果多项式后 f k j i j l l l 1 使用他自己的影子秘密计算并发送拉格朗日因子 f rC 给每个参与者。敌手可通过每个发送的拉格朗日 f 因子 rC 中恢复出影子秘密叠加 k =∑ l 1 d f x r ( l l ) 。因而，在知道 t 个影子秘密的叠加后，敌手就能恢复 k =∑ l 1 ( ) d f x l l ，从而得到秘密。相反，出多项式的叠加 w w„ 时，敌手得不到秘密 s 。当 i j 4.2.2 扩展算法 1) 正确性影子秘密人员，导致最后恢复的秘密无效。为了验由命题 1 知，改进算法中秘密 s 的计算方法是证该方案安全性，假设攻击者在参与秘密恢复过程正确的，即可通过 = ∑ f C r k = 1 l s 得到秘密。而在扩展 f , , 后 }n 中能获得最多信息，即恢复阶段中有 n 个参与者 P⋯ 且攻击者是最后一个发送其拉格朗日 { , P P 1 2 因子的人，只需验证攻击者在获取了 1n - 个 rC 能否恢复出秘密即可。由式(6)可知，k 个 1t - 阶多 = ⋯ 包含 kt 个系数，它的系数构 , ) k 项式 ( )( lf x l 1, 2, · 矩阵成一个 k 0,1, t t -⋯ f ，且每个 rC , lf x 的线性函数，攻击者得到 1n - 个 rC 后可构建 1n - 个方程。因为 n> - ，由线性方程组解的条件可知，攻击者通 kt 过解这 1n - 个方程得不到唯一解，他只能得到秘是 ( ) k m 1, 2, lma ]( l ⋯ = = = 1) A 1 [ ; , f 算法中共有 h 个秘密，每个秘密均采用相同的方法计算，则可以恢复出 h 个秘密。 2) 安全性 ① 影子秘密安全性因为每个 rU 发送的拉格朗日因子 = ∑ k = 1 = ⋯ 的一个线性组合，因此每个参与是 k 个影子秘密 d f x r w x v x v x r = 1, v r ( ( ) ) v l j l l l 1, 2, , ) k f C r f x l r ( )( l 者发送的拉格朗日因子可以保证影子秘密的安全性。下面考虑给予外部攻击者最多的信息来恢复影 2015083-7 - - - - - - - - - - - - „ - - „ - - „ „ - - - - „ - - - - - „ - -

第 3 期荣辉桂等：基于 Shamir 秘密共享的密钥分发与恢复算法子秘密的情形。首先假设在秘密恢复阶段中敌手是 f j 个参与者中最后一个发送 rC 复最后一个秘密 hs 的影子秘密（前面 1h - 个秘密已经恢复了）。假设用 n 个拉格朗 ( is i -⋯ h 的人并试图得到恢 1, 2, = 1) , MyEclipse 8.6 实现并部署文中算法，在局域网下计算机配置 4 GB 内存及 Win7 操作系统；因局域网下计算机使用不同主频 CPU，因此仿真过程中以 CPU 时间作为衡量指标。实验整体环境贴近真日因子恢复每个秘密（包括当前正在恢复的秘密实随机的秘密共享过程，以反映算法在真实环境 hs ）。由于每个发送的拉格朗日因子和每个秘密是 kt 个系数的 1t - 阶多项式 ( ) lf x 的线性函数，敌手从拉格朗日因子和已恢复秘密的 1n - 个方程中最多能构建 ( 个方程。总地来说，敌手 + n 1) 1) h ( 最多可以得到 ( > kt ( h 1) 1) h - + n 1) ( + n ( - + 1) n > 1) ( h ( h 1) + - ( h n kt n + n 中的有效性。文中提出的改进算法在时间复杂度上与传统经典算法相比较处于同一个数量级上，可假定它们的执行效率基本一致。 4.3.2 实验结果及分析个方程。由于 1) 2 ，不能在实验中，可依据秘密恢复过程中影子秘密数量 n 、秘密多项式的个数 k 、门限 t 这 3 个值来验证算法有效性。图 2 给出秘密分发执行时间随影子秘密数量 n 变化情况，随着影子秘密数目增加，执行时间呈线性增长。图 2 秘密分发计算量随影子秘密 n 变化曲线图 3 给出不同的门限值 t 对计算性能影响情况，结果表明门限值对计算性能影响较小。得出秘密多项式 ( )( lf x l = ⋯ 唯一解。因此， 1, 2, , ) k 敌手不能恢复影子秘密。 ② 门限值安全性接下来分析多个欺骗者获取最多信息时门限值的安全性。假设有 1t - 个欺骗者，他们在 1h - 个秘密 ( is i -⋯ h 已经恢复前提下试图恢复最 1, 2, = 1) , 后一个秘密 hs 。首先，分析是否可以从预先恢复的秘密 is 的一个线性组合恢复出 hs 。对于每对 i 和 j ，每个秘密为 s i ( d i ,1 , d i ,2 ⋯ , , d )( i i k , = = ∑ 1, 2, l k = 1 d f w w w )( ( i l , l l i ) j ，由于 ⋯ 是独立线性矢量，他们 , ) h 不可能从预先恢复秘密的线性组合中得到 ks 。其次，再检验是否能从欺骗者自己影子秘密的组合内 1) 及另容、预先恢复的 1h - 个秘密 ( is i = -⋯ h , 1, 2, 外 1 - + 个 rU 发送的拉格朗日因子中恢复 hs 。假 n t 设有 s 个拉格朗日因子用于恢复每个秘密 is 。因为每个发送的拉格朗日因子和每个秘密是 1t - 阶，且 = ⋯ 的线性函 lf x l 含有 kt 个系数多项式 ( )( - + ( t 1)( h t - 个方程来自于另外 rU 发送 ( （其中 ( 的拉格朗日因子， 1h - 个方程来自于已恢复的秘数，欺骗者能构建 ( 1, 2, , ) k 1)( 1)) 1)) 个方程 1) n h h n ( 1) 密）。此外，这些欺骗者可以使用他们自己拥有的 k t - 个方程。总地来说， h t - 个影子秘密构建 ( ( - + 他们能构造 ( ( 1) 1) t h > + ( h + - + ( + ( k t 1)( 1)) 1) n h 个方程。 1) - + ( h h ( ( kt > 1) k t - ( 出秘密多项式 ( )( lf x l 1)( h k ( t ( h 1) 1)) 1)( n - + n t = ⋯ 而得到最后的秘，这能防止欺骗者解 2) 1) 1, 2, , ) k 密 hs 。因此，未恢复秘密的门限值依然与原有值相同。 4.3 仿真实验图 3 秘密分发计算量随 t 值变化曲线 4.3.1 实验环境设置及指标获取图 4 给出秘密分发阶段计算量随影子秘密数量实验采用和文献 [12] 相似环境，使用变化情况。当秘密多项式个数一定时，其计算性能 2015083-8 - - - - - - ﬁ „ - - - - - - - - - - - - - ﬁ -

分享到：

赞收藏

资料库

SHamir分发密钥机制.pdf

相关推荐

区块链

热门标签

最新资料