（计算机应用技术专业论文）可验证多秘密共享的研究及应用.pdf

苏州大学学位论文使用授权声明 i i11 1 1hlui lli fi il y 1 7 3 2 110 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属在 年一月解密后适用本规定。 非涉密论文口 论文作者签名： 重酞 日 期：趁：么1 2 导师签名：差燧日期：丝：乏2 可验证多秘密共享的研究及应用中文摘要 可验证多秘密共享的研究及应用 中文摘要 多秘密共享是密码学技术一个很重要的研究方向，它为重要信息的安全保存和合 法利用提供了一种有效的途径，是信息安全方向的研究热点。利用它保管秘密，不但 能防止权力过分集中而被滥用，而且能够保证秘密的安全性和完整性。 本文介绍了秘密共享的研究背景和现状。从门限方案和一般访问结构两个方面对 多秘密共享进行了深入研究，并将其应用到共享验证签名方案和电子拍卖协议中。首 先，分析y c h 门限多秘密共享方案，指出其在安全性方面存在的严重不足，给出自 己的方案，在该方案中参与者的秘密份额由自己选择产生无需安全信道，同时能够防 止分发者和参与者的主动攻击；其次，提出了一个基于一般访问结构的可验证多秘密 共享方案，。在该方案中，秘密分发者可以动态的增加秘密的数量，各参与者的秘密份 额可以重复使用。与现有的一些方案相比，该方案在防止分发者和参与者之间的各种 欺骗时所需的模指数运算量更小，是一个安全高效的多秘密共享方案；再次，在一般 访问结构的可验证多秘密共享的基础上，提出一个新的共享验证数字签名方案。该方 案有效的克服了已有共享验证签名方案在安全性方面的不足，在验证签名的过程中， 验证组可以防止因某些成员提供假的信息而造成验证的失败。本方案使用的是可验证 多秘密共享，因此能够通过一次秘密共享验证多个签名的有效性，效率有了一定的提 高。最后，研究多秘密共享在电子拍卖协议中的应用，设计并模拟实现了一个安全的 电子拍卖协议。 结果表明，本文的工作使得多秘密共享方案的安全性在一定程度上得到了提高， 同时对于多秘密共享的进一步应用有重要价值。因此，本课题的研究工作对于可验证 多秘密共享走向实用有着重要的意义。 关键词：多秘密共享，v m s s ，一般访问结构，共享验证签名，电子拍卖 作者：王永 指导老师：朱艳琴 t h ed e a l e ro re a c hp a r t i c i p a n tf r o mc h e a t i n g i ti sas e c u r ea n de f f i c i e n tm u l t i - s e c r e ts h a r i n g s c h e m e t h i r d l y , w ep r e s e n t as i g n a t u r ew i t hs h a r e dv e r i f i c a t i o ns c h e m eb a s e do n v e r i f i a b l em u l t i s e c r e ts h a r i n g t h i ss c h e m ee f f e c t i v e l yo v e r c o m et h ed e f i c i e n c i e so ft h e p r e v i o u ss c h e m e si nt e r m so fs e c u r i t y i nt h ep r o c e s so fs i g n a t u r ev e r i f i c a t i o n ，v a l i d a t i o n t h e s t u d y o f v e r i f i a b l e m u l t i - s e c r e ts h a r i n gs c h e m ea n di t sa p p l i c a t i o n a b s t r a e t t h ee x p e r i m e n ts h o w st h a tt h es e c u r i t yo fm u l t i s e c r e ts h a r i n gs c h e m ei si m p r o v e di na c e r t a i ne x t e n tb e c a u s eo ft h ec o n t r i b u t i o no ft h i sp a p e r ，a n di th a sa l li m p o r t a n tv a l u et o f u r t h e r a p p l i c a t i o n o fm u l t i s e c r e t s h a r i n g t h e r e f o r e ，t h e r e s e a r c ho ft h i s p a p e ri s s i g n i f i c a n tt ov e r i f i a b l em u l t i - s e c r e ts h a r i n gc o m i n gi n t ou t i l i t y k e y w o r d s ：m u l t i - s e c r e ts h a r i n g ，v m s s ，g e n e r a la c e s ss t r u c t u r e s i g n a t u r e 埘t hs h a r e d v e r i f i c a t i o n ，e l e c t r o n i ca u c t i o n 1 i i w r i t t e nb yw a n gy o n g s u p e r v i s e db yz h uy a n q i n 1 3 本文的主要研究内容一8 1 4 论文的组织结构- 9 第二章密码学的基础知识l o 2 1 相关的数学知识l o 2 1 1 有限域10 2 1 2 素数的产生和判定1 0 2 1 3 两类数学难解问题1 1 2 1 4h a s h 函数11 2 2 公钥密码算法1 2 2 2 1r s a 密码算法1 3 2 2 2e i g a m a l 密码算法1 4 2 2 3s c h n o r r 数字签名算法15 2 3 基本的秘密共享方案1 6 2 3 1 秘密共享方案的数学模型1 6 2 3 2s h a m i r 的( 毛n ) f - j 限秘密共享方案1 6 2 4 可验证秘密共享方案1 7 2 4 1 可验证秘密共享方案的数学模型1 7 2 4 2f e l d m a n 的可验证秘密共享方案”l8 2 5 本章小结1 9 第三章门限可验证多秘密共享方案 3 1 多秘密共享方案2 0 3 1 1 多秘密共享概念2 0 3 1 2y c h 方案”2 0 3 2 安全的门限可验证多秘密共享方案2 2 3 2 1 多秘密共享方案介绍”2 2 3 2 2 可行性分析2 4 3 2 3 安全性分析”2 4 3 2 4 性能分析2 5 3 3 可动态加入新成员的多秘密共享方案2 5 3 3 1 方案的设计2 5 3 3 2 分发者和参与者的诚实性验证2 7 3 3 3 性能分析2 7 3 4 本章小结2 8 第四章一般访问结构上的可验证多秘密共享 2 9 4 1 一般访问结构上秘密共享的简单描述2 9 4 2 基于一般访问结构的可验证多秘密共享方案3 0 4 2 1 方案介绍3 0 4 2 2 正确性证明3 2 4 2 3 安全性分析3 3 4 2 4 效率分析3 4 4 2 5 系统的安全概率3 4 4 3 本章小结3 6 第五章共享验证的数字签名方案” 3 7 5 1 共享验证的数字签名3 7 5 2 离散对数共享验证签名方案的分析3 8 5 2 1 方案描述”3 8 5 2 2 验证分析3 9 5 2 3 安全性方面的缺陷4 0 5 3 基于可验证多秘密共享的共享验证签名方案4 0 5 3 1 共享验证的签名方案设计4 1 5 3 2 正确性证明4 3 5 3 3 方案的性能优势4 4 5 3 4 安全特性分析4 5 5 3 5 效率分析4 5 5 4 本章小结4 5 第六章基于多秘密共享的电子拍卖协议的设计 6 1 电子拍卖的性质4 6 6 1 1 电子拍卖系统组成4 6 6 1 2 电子拍卖的分类4 7 6 1 - 3 电子拍卖的基本过程4 7 6 1 4 电子拍卖的安全属性4 8 6 2 安全高效的电子拍卖协议4 8 6 2 1 相关知识的介绍4 8 6 2 2 拍卖协议设计4 9 6 2 3 安全性与公平性证明5 0 6 3 电子拍卖协议的设计5 l 6 3 1 拍卖系统功能模块5 2 6 3 2 系统流程设计5 3 6 3 3 实体功能流程设计5 4 6 3 4 电子拍卖协议模拟实现5 6 6 4 本章小结5 9 第七章总结与展望 l 总结6 0 7 2 展望6 1 参考文献“ 攻读硕士学位期间发表的论文 致谢“6 8 来方便的同时也带来了很多安全方面的隐患，如网上信息容易受到窃听、截获、修改、 伪造和重放等各种攻击。如何保证计算机网络中信息的完整性、保密性及其可用性受 到人们的普遍重视，信息安全这门学科应运而生。秘密共享在密钥管理和信息安全方 面有着广泛的应用空间，成为信息安全研究的热点问题。多秘密共享以其特有的优势 引起了许多学者的关注，他们分别提出了自己的多秘密共享方案，对秘密共享体制的 研究与发展做出了很大贡献。 1 1 秘密共享体制研究背景及意义 随着计算机网络和通信技术的飞速发展，人类进入了信息社会。利用互联网进行 信息和资源的共享，从事电子商务以及传递私人信息越来越普遍。与此同时，信息安 全问题日益突出，网络入侵、信息泄密以及网络犯罪等案件也日益上升。如何保护信 息传输、保存、使用等过程中不被攻击，确保信息的保密性、完整性、可用性和不可 否认性，已成为学术界乃至全社会高度关注的问题。 密码学为解决信息安全问题提供了很多实用技术【1 】【2 】【3 1 ，如加密算法、数字签名 技术和身份认证技术等，它们可用来对数据和信息进行加密，对身份进行认证，保证 数据的完整性和不可否认性。但是，要完全保证信息的安全仅仅依靠这些技术还是不 行的。这是因为在使用密码技术的系统中，其安全性主要取决于对密钥的保护，而非 对算法或硬件本身的保护。密码体制可以公开，密码设备可能丢失，同一型号的密码 机仍可以继续使用。然而，一旦密钥丢失或出错，不但合法用户不能提取信息，而且 可能使非法用户窃取信息。因此，密钥是密码体制安全与保密的关键，它的产生和管 理是密码学中一个重要研究问题。另外，由于电子数据的脆弱性，使得它很容易被毁 坏、改变或丢失，即使拥有正确的解密密钥对此也无能为力。由此可见，仅通过加密、 签名、认证等密码技术并不能解决信息安全的所有问题。 在这种情况下，s h a m i r 和b l a k l e y 分别于1 9 7 9 年独立提出了秘密共享的概念并 分别设计了具体的共享方案。秘密共享体制在解决密钥管理和信息安全等问题方面起 第一章绪论 可验证多秘密共享的研究及应用 到了重要的作用。在秘密共享方案中，将所需共享的秘密分成若干子秘密( 也称为份 额) ，并安全地分发给若干参与者保存，同时规定哪些参与者合作可以重构秘密，哪 些参与者恶意的串通不能得到有关该秘密的任何信息。如果攻击者想要重构出所共享 的秘密，他必须首先获得足够多的子秘密，而这往往是非常困难的：当有些子秘密由 于人为因素或自然灾害等而遭到破坏或丢失时，其他一定数量的子秘密持有者联合仍 可恢复出所共享的秘密。利用秘密共享方案保管密钥具有如下优点： ( 1 ) 为密钥合理地创建了备份，克服了以往保存副本的数量越大，安全性泄露的 危险越大，保存副本越小，则副本丢失的风险越大的缺点。 ( 2 ) 有利于防止权力过分集中以导致被滥用的问题。 ( 3 ) 攻击者必须获取足够多的子密钥才能恢复出所共享的密钥，保证了密钥的安 全性和完整性。 ( 4 ) 在不增加风险的情况下，保证了系统的可靠性。 另外，秘密共享体制与密码理论的其它方面也有着紧密的联系，门限数字签名【4 】【5 】 就是一种建立在秘密共享基础上的数字签名方案。在( t ，玎) 门限群签名方案中，利用 秘密共享技术将签名密钥分散给多人管理，使得r 个或更多的参与者( 或签名者) 联合 才能生成有效的群签名，而少于r 个参与者合作不能进行有效签名。 秘密共享体制在现实生活中也有着广泛的应用，如保护国家有关政治、军事、外 交及经济的机密信息的安全性。还有确保日益为广大消费者所接受的网上购物、数字 银行、收费电视、电子钱包等信息系统的正常运行，秘密共享方案在电子商务中的电 子现金、电子拍卖、公平交换等方面也有着重要应用。 总之，对秘密共享体制的研究不但具有重要的理论意义，而且在社会各领域也有 着广泛的实用价值。 1 2 秘密共享体制的研究现状及存在的问题 秘密共享是信息安全和数据保密的重要手段，也是密码学和分布式计算领域的一 个重要的研究内容。第一个秘密共享方案是( f ，甩) 门限秘密共享方案，该方案是 s h a m i r 【6 1 和b l a l d e y 7 1 于1 9 7 9 年独立提出的。s h a m i r 的( ，n ) 门限方案是基于 l a g r a n g e ( 拉格朗日) 插值法来实现的，通过构造一个( ，一1 ) 次多项式，并将需要共享的 秘密作为该多项式的常数项，将秘密分成玎个份额，分别交给刀个人( 也称为参与者) 2 可验证多秘密共享的研究及应用 第一章绪论 保管，使得其中f 个或更多的参与者公开他们的份额就能重构秘密，而o 一1 ) 个或更少 的参与者合作不能得到有关秘密的任何信息。b l a k l e y 独立提出了的另一个( ，聍) 门限 秘密共享方案，该方案的基本思想是利用多维空间中的点来建立门限方案，将共享的 秘密看成，维空间中的一个点，每个子秘密为包含这个点的o 1 ) 维超平面方程，任意 ，个o 1 ) 维超平面刚好确定共享的秘密，而o 1 ) 个子秘密仅仅能确定其交线，因而 得不到共享秘密的任何信息。s h a m i r 方案是一个完备的理想方案，而b l a k l e y 方案是 一个完备方案，但不是一个理想方案。b l a k l e y 方案有一个特殊的性质，任意，个子秘 密除确定交点以外，他们相互之间是无关的，而s h a r n i r 方案却不同，任意t 个子秘密 能够确定整个多项式，并能计算出其余参与者的子秘密。典型的门限方案除s h a m i r 的拉格朗同插值多项式方案和b l a l d e y 提出的几何方法外，还有a s m u t h 等【8 】提出的同 余类方案和k a m i n 等【9 】提出的矩阵法体制。其中，最常用的是s h a m i r 的门限方案， 它实现简单，并且是一个完备的理想方案。使用( f ，聆) 门限秘密共享方案保管秘密有 如下好处：( 1 ) 攻击者必须获得至少r 个份额，才能恢复出所共享的秘密；( 2 ) 即使多达 伽一r ) 个份额因为人为因素或自然灾害等被破坏时，剩下的，个份额仍能重构所共享 的秘密；( 3 ) 将秘密分散保管，有利于避免权利过分集中而被滥用的缺点。 自从( f ，胛) 门限方案被提出以来，秘密共享问题得到了广泛的研究，但也存在以 下几点不足： ( 1 ) 参与者的诚实性问题，即有些参与者在重构秘密时会提供假的份额，而使一 些授权子集的成员不能重构出正确的秘密； ( 2 ) 庄家的诚实性问题，即庄家在分发秘密份额的时候可能会给某些参与者分发 假的份额； ( 3 ) 一次只能共享一个秘密； ( 4 ) 参与者的秘密份额只能使用一次，即秘密重构后需要更换参与者的秘密份额。 基本的秘密共享方案，一般都会假设秘密分发者( 庄家) 和参与者都是诚实的。然 而，这样的假设在现实中是不切实际的。为此，b c h o r 等【阳】提出了可验证秘密共享 ( v e r i f i a b l es e c r e ts h a r i n g ，v s s ) 的概念，它是在通常的秘密共享方案的基础上附加一个 验证算法而构成的。同时，b c h o r 等给出了一个v s s 方案【1 0 】来检测不诚实秘密分发 者的欺骗，每个参与者能够在不重构秘密的情况下证实所得的秘密份额的有效性。但 该方案在验证的过程中需要进行交互，因而效率不是很高。f e l d m a n 1 1 1 1 9 8 7 年提出了 3 第一章绪论可验证多秘密共享的研究及应用 第一个非交互式的可验证秘密共享协议( f e l d m a n v s s ) ，该协议基于s h a m i r 的门限方 案【6 】和离散对数难题的，能够抵抗包括分发者在内的一0 2 个恶意参与者的合谋攻 击。后来，p e d e r s o n 1 2 】提出了一个无条件安全的非交互式可验证秘密共享协议 ( p e d e r s e n v s s ) 。这两个协议都具有较高的效率，是目前应用最多的两个v s s 协议。 根据验证算法是否需要参与者之间或者参与者与分发者之间进行交互，可验证秘密共 享方案被分为两类：交互式的【1 0 1 和非交互式的【l l l 【1 2 】。 由于在可验证秘密共享方案中增加了一个验证协议，即秘密共享者可根据协议验 证秘密分发者分发的秘密份额是否合法、有效以及验证其他参与者在重构秘密时提交 的秘密份额是否合法，因而其安全性得到了一定的保障。但这些验证都只能在参与者 内部进行，有一定的局限性。在此基础上，s a d l e r i ”】于1 9 9 6 年提出了可公开验证的秘 密共享思想( p u b l i c l yv e r i f i a b l es e c r e ts h a r i n g ) ，即除了秘密共享的参与者可以验证秘 密份额的有效性以外，任何其他成员都可以公开验证参与者所得的秘密份额是否有 效，这从根本上避免了庄家与参与者之间的相互勾结。当然这对所给的算法或协议提 出了一定的要求，即算法本身至少是可公开的。 s a d l e r 给出了两个p v s s 方案，允许任何人验证秘密分发者分发给参与者的秘密 份额是否有效而不泄露共享的秘密和参与者持有的秘密份额。p v s s 方案不仅可以防 止秘密分发者的欺骗【14 1 ，还可以防止参与者的欺骗1 5 】【1 6 】【17 1 ，为系统提供了更好的鲁 棒性。但s t a d l e r 的p v s s 方案通信和计算量较大，因而效率不高，于是f u j i s a k i 【l 引 提出了一个效率相对较高的p v s s 方案。后来，s c h o e n m a k e r s v g 对s t a d l e r 和f u j i s a l d 等的方案分别进行了简单的改进。在这些方案中，验证算法依赖于公钥加密、零知识 证明等工具，结构较为复杂而且是交互式的，导致其效率不够理想。除了可验证和可 公开验证的秘密共享方案外，在国内，学者们还提出了许多其它的预防秘密共享中欺 诈的方法和手段，如费如纯和王丽娜【2 0 l 基于r s a 公钥体制和单向函数提出了防欺诈 的门限秘密共享体制，戴元军、马春光和杨义先【2 1 】利用椭圆曲线离散对数问题的难解 性提出了防欺诈的门限秘密共享方案，肖立国、钟诚和陈国良f 2 2 1 基于椭圆曲线提出了 一个动态秘密共享体制，许春香、陈恺和肖国镇【2 3 】提出了安全矢量空间秘密共享方案。 上面介绍的秘密共享方案均为一次性方案，即每个参与者的秘密份额只能使用一 次，而且一次秘密共享过程只能在一组参与者中共享一个秘密。但是在实际的应用中， 有时要求在同一组参与者中共享多个秘密，例如在研究无条件安全的多步计算的通信 4 可验证多秘密共享的研究及应用第章绪论 复杂度等场合。显而易见，最简单的做法是：对每个秘密分别构造一个基本的秘密共 享方案来实现多个秘密的共享。但该方法具有明显的缺陷：每个参与者需要保护的秘 密份额数量太多，秘密分发者需要分发大量的秘密数据。为减少参与者保护的份额数 量和减轻秘密分发者的负担，多秘密共享( m u l t i s e c r e ts h a r i n gm s s ) 方案被提出。众所 周知，共享算法的运行以及将秘密份额分发给参与者都需要花费很大的计算和通信代 价，因此在多秘密共享的研究过程中，大家关注的焦点主要集中在如何使参与者拥有 的秘密份额可以重复使用和在一次秘密共享的过程中，运行次共享算法，可以共享 多个秘密的问题。j a l ( s o n 【2 4 】将多秘密共享分为两种类型：一类是一次性方案，另一类 是多次性方案。它们的主要区别在于：多次使用方案中参与者的秘密份额可以重复多 次使用，而一次性方案中参与者的秘密份额只能使用一次。h e 和d a w s o n l 2 5 】利用单向 函数的概念提出了一个门限多秘密共享方案，它是一个多次性方案，即参与者的秘密 份额可以重用，每个参与者保护一个秘密份额就可以共享多个秘密，但该方案的一个 不足就是多个秘密的重构必须按照一定的顺序来进行。随后，他们利用双变量单向函 数对上述方案进行了一定的改进。c h i e n 掣2 6 】基于系统分组码提出了一种门限多秘密 共享方案，在一次共享过程中可以共享多个秘密，且秘密份额可以重用，该方案对于 一次性共享多个秘密的应用场合非常有效，拓展了秘密共享的应用范围，具有重要的 实用价值。同时国内的很多学者提出了自己的多秘密共享方案，如许春香和肖国镇【2 7 j 基于r s a 公钥体制提出了一个门限多秘密共享方案，庞辽军和王育民1 2 8 】提出了一个 基于几何性质的门限多秘密共享方案。 为了防止分发者( 庄家) 和参与者的主动攻击，h a m t 2 9 】于1 9 9 5 年首次提出了可验 证多秘密共享( v e r i f i a b l em u l t i s e c r e ts h a r i n g ，v m s s ) 方案。该方案能够防止分发者和 参与者的主动攻击，但是它存在以下不足：为了验证秘密份额的有效性，每个参与者 需要执行c次模指数运算，计算量非常大；在秘密重构过程中，验证每个参与者的子。 份额的有效性是交互式的；且秘密分发者不能动态地增加秘密，方案的实用性很差。 c h e n 等【3 0 1 提出了一个v m s s 方案，克服了h a m t 2 9 1 方案的缺点，但是l i n w u 【3 l 】指出 该方案的效率也比较低。因为该方案需要对每一个秘密计算一个，2 维检验向量，秘密 分发者为此需要花费2 玎次的模指数运算，计算代价也很大。针对上面两个方案的不 足，l i n 一、u 【3 l l 提出了一个能够防止庄家和参与者欺骗的，计算量相对较少且不执行 交互式验证协议的多秘密共享方案。但是h e w u l 3 2 1 指出其方案存在参与者欺骗的安 5 第一章绪论可验证多秘密共享的研究及应用 全缺陷。2 0 0 5 年，s h a o 和c a o 3 3 】基于y c h 方案提出了一个高效的可验证门限多秘 密共享方案，但其方案需要一个安全的信道用于秘密份额的分发。2 0 0 6 年，z h a o p 4 1 等人提出一个实用的可验证多秘密共享方案，该方案中，虽然秘密分发者无法通过伪 造各参与者的秘密份额进行欺骗，但可以通过公开无效的函数值使得参与者恢复无效 的秘密，而对秘密分发者的这种恶意行为参与者无法察觉。2 0 0 7 年，m h d e h k o r d i 和s m a s h h a d i 3 5 】提出了一个可验证多秘密共享方案，秘密份额由共享者产生，通信代 价小且不需要安全通道，有一定的实用价值。 前面提到的方案都是门限秘密共享方案，门限方案有一个潜在的约束就是只有在 所有参与者具有完全平等的地位、可靠性和安全性的情况下才是有意义的，然而在现 实世界中，这样的假设往往很难满足。更为一般、更为普遍的是访问结构上的秘密共 享。因此，对访问结构上秘密共享方案的研究具有更广泛的现实意义。i t 0 等1 3 6 1 阐述 了秘密共享的一般方法，并提出了一般访问结构上秘密共享方案。b a n a l o h 等【37 j 提出 了一个比i t o 等的方法更为简单有效的构造方法单调电路构造法，并证明了任何访 问结构都能够通过完备的秘密共享方案加以实现。b a n a l o h 等【3 7 】的方案可以用于构造 计算上安全的一般访问结构上的秘密，他们给出了一个一般访问结构上的秘密共享模 型：秘密分发者将所要共享的秘密s 分成疗个子份额分别分发给，z 个参与者，使得每 一个参与者仅知道自己的子秘密而不知道其他任何参与者的子秘密：同时，秘密分发 者定义一些授权子集，使得这些集合中的参与者联合可以恢复s ，而非授权子集中的 参与者合作不能得到有关s 的任何信息。由所有授权子集组成的集合称为访问结构， 常用r 表示，称b f 是最小授权子集，若a b 且a b ，则a 萑f 。f 的最小授权 子集的集合r o 称为r 的基，r 可以由f 。唯一确定，即f = b c ，b f o ) ，其中c 为 由参与者组成的集合。在国内，张福泰和王育民【3 8 】提出了具有传递性质的访问结构， 并给出了在此类访问结构上的秘密共享方案的构造方法。 除了上面介绍的各种秘密共享方案外，根据不同的应用环境，近些年来学者们还 提出了一些新型的秘密共享方案。 ( 1 ) 在线秘密共享( o n - l i n es e c r e ts h a r i n g ) 针对参与者的动态变化，c a c h i n l 3 9 1 首次提出了在线秘密共享方案，这个方案具有 共享多个秘密的能力，并且可以动态地添加参与者，而不必重新给当前的参与者发送 新的影子。这些功能是通过在一个公开的可访问的区域存储额外的可靠信息而获得 6 可验证多秘密共享的研究及应用第一章绪论 的。 ( 2 ) 能除名的秘密共享( s e c r e ts h a r i n gw i t hd i s e n r o l l m e n t ) b l a k l e y 首先提出了带除名能力的秘密共享的概念，文献 4 0 】研究了当影子泄漏成 为无效影子的处理方法，通过对有效的影子进行修改或变换，使泄漏影子无法恢复出 新的共享秘密，成为无效影子。 ( 3 ) 先应式秘密共享( p r o a c t i v es e c r e ts h a r i n g ) 在基本的秘密共享基础上，人们又提出了先应式秘密共享( p r o a c t i v es e c r e t s h a r i n g ，p s s ) 。基于该思想的秘密共享是针对秘密比较重要、非常敏感或生存期较长 的情况提出的，这时有一个被称作是移动敌手的蓄意破坏者存在，他不时地想窃取秘 密，为此秘密共享者周期性地更换其携带的秘密份额，因而当恶意敌手窃取秘密成功 时，原来的秘密份额已被更新，从而确保秘密的安全性。 ( 4 ) 无仲裁参与的秘密共享方案 大多数秘密共享方案都有一个仲裁( 秘密分发者) ，而在有的安全环境中并不希望 有这样的第三方，i n g e m a r s s o n 等讨论了没有秘密分发者的情况，访问结构中的授 权子集可以生成同一个共享秘密，而合作之前没有人知道他们所共享的秘密。 ( 5 ) 分布式秘密共享方案 在无线通讯的局域网、传感器网络和a dh o c 网络等的应用中，各分散节点上的 用户要实现信息共享或数字保密通信的密钥交换，就要用到分布式秘密共享方案。该 方案无固定庄家或秘密中心，每个参与者都可以做秘密分发者进行秘密的分发，秘密 分发者和参与者之间不需要建立安全信道，参与者之间能有效地检测和识别其他成员 的欺骗行为，具有较高的安全性和实用性。 总而言之，自从s h a m i r 和b l a k l e y 提出秘密共享的思想以来，秘密共享获得了长 足的发展。为了防止分发者和参与者的各种欺骗，可验证性被引入到秘密共享方案中， 出现了很多可验证秘密共享方案，f e l d m a n 提出了第一个非交互式的可验证秘密共享 方案。为了提高秘密共享的效率，许多学者提出了多秘密共享的思想，即在一组参与 者中共享多个秘密。由于门限秘密共享方案的局限性，访问结构上的秘密共享方案引 起了国内外学者的广泛关注。同时，还有一些具有特殊性质的秘密共享方案被提出， 用以满足现实中的各个领域的不同需求。 至今秘密共享还有一些问题没有得到很好的解决。秘密共享最主要的用途是保护 7 第一章绪论 可验证多秘密共享的研究及应用 密钥的安全性，因此，无论什么样的秘密共享方案，安全性永远都是第一位的。但是， 通过分析发现很多方案为了安全性而使得方案的计算量很大，效率非常差，有些方案 甚至在验证秘密份额有效性时需要交互，使得方案的实用性很差。同时秘密共享参与 者的可变性问题也是一个需要着重探讨的课题，因为在实际应用中，构成秘密共享参 与者的成员会经常发生变化。门限方案只有在所有参与者具有完全平等的地位、可靠 性和安全性的情况下才是有意义的，因此一个很重要的问题就是如何将门限秘密共享 推广到一般访问结构上，设计个真正的一般访问结构上的可验证多秘密共享方案。 目前，对秘密共享的研究更多的是在理论上，对秘密共享在数字签名、共享验证签名、 公平交换和电子拍卖中的应用的研究相对较少。 1 3 本文的主要研究内容 上一节讨论了秘密共享的研究现状及存在的问题，由于传统的单秘密共享方案已 经无法满足当今数据量较大的应用需求，人们迫切需要多秘密共享技术来解决这一问 题。门限多秘密共享对能够恢复秘密的参与者集合有一定的限制，随后i t o ，n i s h i z e k i 等提出了更一般的秘密共享体制。本文重点研究了可验证多秘密共享方案的设计以及 可验证多秘密共享技术在共享验证签名和电子拍卖中的应用。本文的主要研究内容概 述如下： ( 1 ) 研究门限多秘密共享技术，分析了y c h 方案在安全方面存在的不足。利用 r s a 密码体制和s c h n o r r 签名算法，对y c h 方案进行改进，得到一个安全的可验证 多秘密共享方案。在该方案中，参与者的秘密份额由自己选择产生无需安全信道，能 够防止分发者和参与者的主动攻击，安全性较好。同时，基于离散对数难题，给出一 个可动态加入新成员的多秘密共享方案。 ( 2 ) 将门限多秘密共享扩展到一般访问结构上，提出了一个一般访问结构上的可 验证多秘密共享方案，一次秘密共享过程可以共享多个秘密，且参与者的秘密份额可 以重复使用。该方案在防止分发者和参与者之间的各种欺骗时所需的运算量更小，具 有广泛的适用性。 ( 3 ) 分析共享验证签名的性质及其与秘密共享的区别，利用可验证多秘密共享技 术，提出一个新的共享验证签名方案。该方案在验证签名的过程中，验证组可以防止 因某些成员提供假的信息而造成验证的失败。多秘密共享技术的应用使得该方案能够 8 存在的问题，在此基础上，提出了本文的研究内容和组织安排。 第二章：介绍了后面章节要用到的一些密码学基础知识。 第三章：分析了y c h 方案在安全方面存在的不足，对其进行改进，得到一个安 全的可验证多秘密共享方案。同时基于离散对数难题，提出一个可动态加入新成员的 多秘密共享方案。介绍了这些方案的设计与实现，并对方案的安全性及性能进行了分 析。 第四章：提出了一个般访问结构上的可验证多秘密共享方案，并将它与现有的 一些方案进行比较，同时分析了该方案在各种入侵情况下的安全概率。 第五章：基于可验证多秘密共享技术，提出一个新的共享验证签名方案，在验证 签名的过程中，验证组可以防止因某些成员提供假的信息而造成验证的失败，通过一 次秘密共享验证多个签名的有效性。 第六章：讨论电子拍卖系统的分类、安全属性和系统的构成，利用可验证多秘密 共享技术设计一个安全的电子拍卖协议，并模拟实现该协议。 第七章：对论文进行总结，并对未来工作进行展望。 9 r 。1 。一 第二章密码学的基础知识 可验证多秘密共享的研究及应用 第二章密码学的基础知识 本章主要介绍本文后面将用到的密码学相关知识，包括有限域、素数的选择判定、 计算复杂性问题及困难性假设、公钥密码算法、哈希函数、数字签名、s h a m i r 门限 秘密共享方案和f e l d m a n 可验证秘密共享方案。 2 1 相关的数学知识 2 1 1 有限域 定义2 1 1 1 一个代数系统 如果它的两个二元运算满足以下条件： ( 1 ) 是a b e l 群，即加法交换群； ( 2 ) 是半群； c 3 ， 满足分配律c a , b , c r ，： 芝：暑二：篇乏； 则我们称代数系统 为环。 定义2 1 1 2 如果一个环 ( 口，b ，f g ) 满足以下条件： ( 1 ) g 至少包含一个以上的元素； ( 2 ) 有单位元e ，即口幸e = e 木口= 口； ( 3 ) 是可交换的，即0 b ) c = a ( b 事c ) ； ( 4 ) 对任意的非零元d ，都存在逆元d ，即d 幸d = d 一d = e ； 则我们称 为域。 定义2 1 1 3 若 的元素为有限个( 记为g ) ，则称为有限域或g a l o i s 域， 记作e 或g f ( q ) 。 最常见的有限域主要有两种类型：素数域卯( g ) 和特征为2 的二进制有限域 g f ( 2 “) 。 2 1 2 素数的产生和判定 素数是一种整数，在整除意义下，它只能被自身( 正负) 和1 整除。素数在密码学中 扮演着重要的角色，许多密码算法的一个重要要求是能够选择一个大的素数，如在后 可验证多秘密共享的研究及应用第一二章密码学的基础知识 面将要介绍的r s a 加密算法和e 1 g a m a l 加密算法都需要大素数。因此下面简单介绍 下素数如何产生以及如何判断一个数是素数。 对于小素数的产生，可以通过简单的算法实现，而密码学中需要的素数非常大。 在现有的技术条件下，真正可以做到随机产生的随机数发生器并不存在，一般都是从 随机源中选取，或是采用伪随机数发生器来产生密码学所需要的大素数。由伪随机数 发生器产生的素数可能是伪素数，它的性质仍有待判断。而由于密码学中所使用的素 数都非常大，利用人工判断显然不合实际，所以需要有效的素数测试法来正确判定素 数的真伪。常用的素数判定法有s o l o v a g s t r a s s e n 素数测试算法、r a b i n m i l l e r 素数测 试算法等，这些方法并不能完全确定出素数，但非素数的概率很小，可忽略不计。 2 1 3 两类数学难解问题 ( 1 ) 大整数分解问题 如果已知两个数p 和g ，求其乘积n = p 勺会非常容易，但如果已知的是乘积， 那么分解这个乘积以解出两个因子将非常困难。当这个乘积是一个大素数( 如超过 1 0 2 4 位) 时，分解它是计算上不可行的，而这也是现代密码学一公钥密码体制提出的 数学理论基础。基于大整数因子分解问题的公钥密码体制最典型的是r s a 公钥密码 体制。 ( 2 ) 有限域的乘法群上的离散对数问题 另一个频繁地用于密码学的数学难解问题是模指数运算，这是一种单向函数。比 如，已知( 口，x ，玎) ，计算a 工m o d ，2 这个表达式很容易。而模指数运算逆问题是找出一 个数的离散对数，这就是一个很困难的问题。比如，己知( 口，b ，刀) ，求解x ，使得 a 。量bm o dn 成立。 这个难解问题使得很多公钥密码算法的安全性有了坚实的数学理论依据。基于有 限域上的离散对数问题的公钥密码体制主要包括e l g a m a l 型的加密体制和数字签名 体制，d i f f i e h e l l m a n 密钥交换方案等。 2 1 4h a s h 函数 密码学上的h a s h 函数( 也称杂凑函数、散列函数) ，是将任意长度的消息压缩到 某一固定长度的消息摘要的函数。例如，输入一长段信息m ，可以得到一小段固定长 第二章密码学的基础知识 可验证多秘密共享的研究及应用 度的信息办( 研) 。由于信息m 的长度任意，而 伽) 的长度固定，因此函数是一个多对 一的函数。对于同一输出，对应有多种输入。h a s h 函数的算法公开，不需密钥，而 且容易计算。 单向h a s h 函数是在一个方向上工作的h a s h 函数：从预映射的值很容易计算其散 列值，但要使其散列值等于一个特殊值却很难。好的h a s h 函数必须具备这样的性质： 单向性、定长性、非线性、伪随机性和抗碰撞性。 将h a s h 函数应用到数字签名中可带来如下一些好处： ( 1 ) 可破坏数字签名方案中的某种数学结构，诸如同态结构。 ( 2 ) 可提高数字签名的速度。当签名人想对消息m 进行签名时，他首先构造一个 消息摘要：z = 办( 聊) ( 厅是一个h a s h 函数) ，然后计算签名y = s i g k ( z ) 。 到现在为止关于h a s h 函数的安全性设计的理论主要有两点：一个是函数的单向 性，二是函数映射的随机性。常用的h a s h 算法是利用某些数学难题而设计的：如r a b i n h a s h 方案、m e r k l eh a s h 方案、m d 4 算法、m d 5 和s h a 1 等。 2 2 公钥密码算法 公钥密码算法又称非对称密钥算法、双密钥密码算法。其思想是由d i f f i e 和 h e l l m a n 在1 9 7 6 年提出的，在密码学的发展史上具有划时代意义。在公钥密码算法中 七p 红，七，可以公开，简称公钥；恕必须保密，简称私钥。公钥密码算法是基于数 学函数而不是基于替换和置换，公钥算法通常是利用下面几个数学难题：( 1 ) 大整数 因式分解问题( r s a 算法采用) ；( 2 ) 有限域的乘法群上的离散对数问题( e 1 g a m a l 算法 采用) ；( 3 ) 椭圆曲线上的离散对数问题(