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

无可信中心的可验证秘密共享的研究 摘要 随着计算机网络技术的发展，对重要或敏感信息的安全保护问题日益严峻。 秘密共享是信息安全和数据保密中的重要手段之一，它能够将责任分散，从而 提高了系统的安全性。 本文首先阐述了密码学的相关知识，然后对门限秘密共享的研究进行了综 述，探讨了几种典型的门限秘密共享方案。针对这些问题，提出了一种无可信 中心的可验证秘密共享方案。该方案具有如下特点： 1 方案采用了无可信中心的秘密共享模型。由于不再需要可信中心，每个 成员既是秘密的分发者，又是秘密恢复的参与者，从而彻底地消除了可信中心 “权威欺骗 的安全隐患。 2 方案采用双生成元和零知识证明的验证方法，提高了公正性和安全性。 采用双生成元的验证方法，既能验证成员的子秘密份额是否正确，又可有效地 防止恶意成员的欺骗。采用零知识证明的验证方法，不但验证了成员是否拥有 正确的秘密份额，而且不会暴露任何该秘密份额的相关有用信息，从而避免了 不诚实成员的恶意欺骗。 本文在w i n d o w sx p 系统下，使用v c + + 6 0 实现了无可信中心的可验证秘 密共享的原型系统。实验结果表明：本方案是正确可行的，并且具有良好的公 正性和安全性。最后本文对该方案进行了总结和展望。 关键词：秘密共享；可信中心；双生成元；零知识证明 t h er e s e a r c ho fv e r i f i a b l es e c r e ts h a r i n g w i t h o u tat r u s t e dp a r t y a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g y ，t h e s e c u r i t ya n d p r o t e c t i o np r o b l e mo ft h ei m p o r t a n to rs e n s i t i v ei n f o r m a t i o nb e c o m ei n c r e a s i n g l y s e v e r e s e c r e ts h a r i n gi sa n i m p o r t a n tm e a n si ni n f o r m a t i o ns e c u r i t ya n dd a t a s e c r e c y i tc a nd e c e n t r a l i z er e s p o n s i b i l i t ya n di m p r o v e ss y s t e m ss e c u r i t y i nt h i st h e s i s ，w e f i r s t l ye x p a t i a t eo nc r y p t o l o g yk n o w l e d g e ，a n dt h e nw e i n t r o d u c et h em a i ni d e ao ft h r e s h o l ds e c r e t s h a r i n g ，a n dd i s c u s ss o m et y p i c a l t h r e s h o l ds e c r e ts h a r i n gs c h e m e s t or e s o l v et h e s es c h e m e s p r o b l e m s ：w e p r o p o s e av e r i f i a b l es e c r e ts h a r i n gs c h e m ew i t h o u tat r u s t e dp a r t a n dt h i ss c h e m eh a st h e f o l l o w i n gf e a t u r e s ： 1 u s i n gs e c r e ts h a r i n gm o d e lw i t h o u tat r u s t e dp a r ti nt h i ss e h e m e s i n c e w i t h o u tat r u s t e dp a r t ，e a c hm e m b e ri st h ed e a l e ro fs e c r e td i s t r i b u t i o na n d a l s ot h e p a r t i c i p a n to fs e c r e tr e c o n s t r u c t i o n t h e r e f o r e ，i tc a ne l i m i n a t ea u t h o r i t yc h e a t i n g t h o r o u g h l y 2 u s i n gt w og e n e r a t o r sa n dz e r o - k n o w l e d g ep r o o fv e r i f i a b l em e t h o d si nt h i s s c h e m e t h e r e f o r e ，i ti m p r o v e ss c h e m e sj u s t n e s sa n ds e c u r i t y b y u s i n gt w o g e n e r a t o r sv e r i f i a b l em e t h o d ，i tc a nv e r i f yt h a tw h e t h e rt h es u bs h a r ei sc o r r e c ta n d p r e v e n t st h ed i s h o n e s tm e m b e rf r o mc h e a t i n g b yu s i n gz e r o k n o w l e d g ep r o o f v e r i f i a b l em e t h o d ，i tc a nv e r i f yt h a tw h e t h e rt h em e m b e rh a sc o r r e c ts h a r ea n d d o e s n o tr e v e a l a n yu s e f u li n f o r m a t i o na b o u tt h es h a r ea n dp r e v e n t st h ed i s h o n e s t m e m b e rf r o mc h e a t i n g w eu s ev c + + 6 0t o d e s i g nap r o t o t y p es y s t e mb a s e do nt h i ss c h e m ei n w i n d o w sx p t h er e s u l ts h o w st h a to u rs c h e m ei s r i g h ta n df e a s i b l e ，a n dh a sg o o d j u s t n e s sa n ds e c u r i t y a tl a s t ，w es u m m a r i z eo u rd i s s e r t a t i o na n de x p e c tt h ef u t u r e o fs e c r e ts h a r i n g k e y w o r d s ：s e c r e ts h a r i n g ；t r u s t e dp a r t y ；t w og e n e r a t o r s ；z e r o k n o w l e d g ep r o o f 插图清单 5 1 系统模型3 l 5 2 组公钥产生的运行流程3 2 5 3 秘密恢复的运行流程3 3 5 4 初始化过程3 4 5 5 成员1 产生子秘密份额和验证参数3 5 5 - 6 成员l 产生秘密份额3 7 5 7 成员l 计算子组公钥和相关参数3 8 5 8 成员1 验证子组公钥3 9 5 - 9 成员l 计算组公钥3 9 5 1 0 成员1 产生部分签名4 2 5 1 l 签名合成者合成门限签名及验证4 2 5 1 2 成员l 产生参数4 3 5 一1 3 成员1 重构自己的秘密份额4 3 图图图图图图图图图图图图图 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得金壁王些太堂或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：上旋雩是签字日期：玉。8 年6 月f - 日 学位论文版权使用授权书 本学位论文作者完全了解 金胆王些太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金目巴王些太堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：上矽冬彰冬 签字日期：2 d d 亨年6 月 学位论文作者毕业后去向： 工作单位： 通讯地址： t 7 日 导师签名： 签字日期： 电话： 邮编： i i 缈 非6 月夕日 致谢 在三年的硕士研究生学习期间，得到了我的导师侯整风教授的悉心指导， 无论是课程学习、论文选题，还是收集资料、论文成稿，侯老师都给予了我大 量的帮助，使我在完成学业的同时还学会了如何进行学术研究，在此由衷地感 谢侯老师在学业指导以及其他方面给予我的关心。侯老师广博的学识、严谨的 学风、诲人不倦韵情怀必定使我终身受益，并激励我勇往直前。 同时，在此感谢计算机学院的各位老师，他们在课堂上的教诲为本文的研 究提供了理论基础；感谢网络与信息安全实验室的全体同学，他们在平时课程 学习、课题研究及论文撰写过程中给予了我很大的帮助。 最后再次感谢所有关心，帮助过我的人。 作者：王玲玲 2 0 0 8 年5 月 第一章绪论 1 1 课题背景和意义 随着计算机技术的发展和网络的普及，信息由过去的人工和书信传递转变 为通过网络进行发布和传输。网络在带给人们便利的同时也带来了一系列安全 隐患问题，对重要或敏感信息的安全保护问题日益严峻。对信息进行加密是保 障信息安全的重要途径之一，而加密的核心是密钥的安全问题。一旦密钥丢失 或出错，将会造成非常严重后果。 秘密共享为解决密钥的安全问题提供了崭新的思路，在其安全保存、传输 及合法利用中起着关键的作用。它的基本思想是可信中心将共享的秘密( 即密 钥) 分成多个秘密份额分发给多个成员，在恢复秘密时，即使秘密份额存在部 分丢失或损坏，只要参与秘密恢复过程的成员共享的秘密份额的数目不少于门 限值，秘密就能够恢复。这种方法不但依赖于可信中心，还依赖于所有成员的 诚实性，但是可信中心可能存在“权威欺骗”，并且成员较高的诚实性在现实中 也很难成立。因此，传统的秘密共享在公正性和安全性方面并不理想，需要寻 求一种改进的方法。 1 9 9 1 年，i n g e m a r s s o n 和s i m m o n s 1 】提出了不需要可信中心的秘密共享方 案。由于不再需要可信中心，从而彻底地消除了可信中心“权威欺骗 的安全 隐患。所有成员通过某种算法协商产生共同的密钥，通过秘密共享由所有成员 共同管理该密钥。因此，与需要可信中心的秘密共享相比，无可信中心的秘密 共享更加安全，同时更具有实际应用价值。对无可信中心的秘密共享研究的主 要目的就是为了实现它而寻找合适的方案，从而保证无可信中心模型中信息发 布和传输地安全、有效；此外，无可信中心模型中秘密份额的验证是新的研究 方向，其现有理论和方案都不够完善。因此，进行无可信中心秘密共享的理论 和应用研究有着重要的现实意义。 1 2 国内外研究状况 最早的门限秘密共享是由s h a m i r 2 】和b l a k l e y 3 1 于1 9 7 9 年分别提出的。随 后，许多学者对门限秘密共享进行了深入的研究。k a m i n 等人【2 9 j 提出了矩阵法 构造的门限秘密共享。a s m u t h 和b l o o m 3 0 】对基于中国剩余定理的门限秘密共 享进行了研究。b e n a l o h 等人】提出了同态秘密共享的概念。k a m i n 等人p 2 j 将 信息论方法引入秘密共享，更为清晰地刻画了秘密共享的实质。b r i c k e l l 和 d a v e n p o r t t 3 3 1 揭示了理想的秘密共享。曹珍富【3 4 】提出了2 次密钥秘密共享。他 们的方案都不能防止可信中心的欺骗和成员之间的欺骗。 为了解决可信中心和成员之间的欺骗问题，19 8 5 年，c h o r d 提出了可验证 秘密共享的概念，19 8 7 年，f e l d m a n t5 j 提出了第一个非交互式的可验证秘密共 享方案，之后，p e d e r s e n 6 7 】提出了第一个无条件安全的非交互式的可验证秘密 共享方案，他们的方案能够识别可信中心的欺骗和成员之间的欺骗，但是都不 能阻止可信中心的“权威欺骗”，都不能阻止正确的秘密份额被不诚实成员骗取。 1 9 9 1 年，i n g e m a r s s o n 和s i m m o n s q 提出了不需要可信中心的秘密共享方案，可 以彻底地消除可信中心“权威欺骗”的安全隐患。19 9 4 年，h a r n t8 】提出了一种 不需要可信中心的门限群签名方案。1 9 9 5 年，h e r z b e r g 等人【9 】提出了先应秘密 共享的概念，解决了传统门限方案中忽略的周期上的安全性问题。2 0 0 1 年， r o s a r i o 等人【1 0 1 在门限d s s 签名方案中提出了联合秘密共享技术，能够解决无 可信中心模型中共同密钥的产生问题。2 0 0 3 年，p r a m a n i k 和u p a d h y a y a t j 提出 了一种秘密份额可恢复的可验证的先应秘密共享方案，进一步推进了h e r z b e r g 等人的研究。2 0 0 3 年，王斌和李建华i l2 j 提出了一种无可信中心的门限签名方案， 指出了h a r n 签名方案的不足，但是不能防止成员之间秘密份额的欺骗。2 0 0 6 年，沈忠华和于秀源【l3 j 提出了一种无可信中心的有向门限签名方案，但是不能 防止成员之间秘密份额的欺骗。2 0 0 7 年，庞辽军等人【1 4 】提出了一种不需要可信 中心分发秘密份额的可验证的秘密共享方案，但是仍然需要可信中心帮助选择 秘密参数和计算公开信息，因此并不是一种真正意义上的无可信中心的秘密共 享方案。 1 3 本文的研究内容及拟解决的问题 1 3 1 研究内容 本文对门限秘密共享的理论和方案进行了深入研究，重点分析了无可信中 心的秘密共享和可验证的秘密共享的优越性和不足之处。通过认真研究与分析， 总结前人的成果与不足，本文提出了一种无可信中心的可验证秘密共享方案。 本文研究的主要内容是在不安全的网络环境中如何建立无可信中心的秘密 共享方案，以及防止成员之间的欺骗，同时实现无可信中心的可验证秘密共享 的原型系统，验证该方案的可行性、公正性和安全性。 1 3 2 拟解决的问题 ( 1 ) 建立无可信中心模型，设定无可信中心模型中的参数。 ( 2 ) 结合双生成元和零知识证明的验证方法设计无可信中心的秘密共享方 案。 ( 3 ) 实现网络环境中的无可信中心的可验证秘密共享的原型系统。 ( 4 ) 结合实验数据，进行系统和方案分析。 1 4 论文的组织结构 2 论文的组织结构如下： 第一章绪论。阐述了课题背景和意义、国内外研究状况、研究内容、拟 解决的问题。 第二章密码学概述。介绍了密码学的相关知识。 第三章门限秘密共享研究。概述了门限秘密共享，探讨了几种典型的门 限秘密共享方案。 第四章无可信中心的可验证秘密共享方案。介绍了无可信中心的可验证 秘密共享方案的建立。 第五章原型系统的实现。介绍了原型系统的设计及实现过程。 第六章总结与展望。总结本文所做的工作，并且对门限秘密共享的研究 做出展望。 第二章密码学概述 目前的网络中存在着各种各样的安全漏洞和威胁，如何进行保密通信、保 证信息不被非法修改、保障计算机网络系统不被非法访问和攻击，已经成为信 息社会发展过程中必须面对的重要问题。密码学正是为了满足对信息安全和保 密的需求而产生并且发展起来的交叉学科。由于计算机网络的不断发展，密码 学也越发体现出它的重要价值。 密码学( c r y p t o l o g y ) 作为数学的一个分支，包括密码编码学和密码分析学。 密码编码学( c r y p t o g r a p h y ) 是对信息进行编码实现信息保密的科学和技术；密码 分析学( c r y p t a n a l y s i s ) 是研究、分析、破译密码的科学和技术。 2 1 密码体制 采用密码技术可以隐藏和保护需要保密的信息，使未授权者不能提取信息。 需要加密的信息( m e s s a g e ) 称为明文( p l a i n t e x t ) ，加密后的信息称为密文 ( c i p h e r t e x t ) 。明文变换成密文的过程称为加密( e n c r y p t i o n ) ，密文恢复出原明文 的过程称为解密( d e c r y p t i o n ) 。对明文进行加密时所采用的编码规则称为加密算 法( e n c r y p t i o na l g o r i t h m ) ，对密文进行解密时所采用的编码规则称为解密算法 ( d e c r y p t i o na l g o r i t h m ) 。加密算法和解密算法的操作通常在一对密钥( k e y ) 控制下 进行，分别称为加密密钥( e n c r y p t i o nk e y ) 和解密密钥( d e c r y p t i o nk e y ) 。 根据密钥的特点，密码体制分为对称和非对称两种。对称密码体制 ( s y m m e t r i cc r y p t o s y s t e m ) 又称单密钥( o n e k e y ) 、私人密钥体制( p r i v a t e k e y c r y p t o s y s t e m ) 、传统( c l a s s i c a lc r y p t o s y s t e m ) 密码体制，加密和解密使用相同的 密钥，发送方使用密钥和加密算法加密数据，接收方使用相同的密钥和对应的 解密算法来解密。非对称密码体制( a s y m m e t r i cc r y p t o s y s t e m ) 又称双密钥 ( t w o k e y ) 、公开密钥体制( p u b l i c - k e yc r y p t o s y s t e m ) ，加密和解密使用两个不同 的密钥，发送方使用加密密钥对数据进行加密，接收方只能使用对应的解密密 钥才能解密：如果需要认证，发送方使用解密密钥对数据进行加密，接收方只 能使用对应的加密密钥才能解密，而成功的解密可以保证只有发送方才能发送 该信息。 2 2 密码分析 通常假设攻击者知道正在使用的密码体制。根据攻击者破译时已经具备的 前提条件，通常将攻击类型分为四种：唯密文攻击、已知明文攻击、选择明文 攻击和选择密文攻击。 ( 1 ) 唯密文攻击( c i p h e r t e x t o n l ya t t a c k ) ：攻击者有一个或更多的用同一加密 4 算法加密的信息的密文。攻击者的任务是恢复尽可能多的明文、或者推出密钥， 以便使用相同的密钥解出其他被加密的信息。 ( 2 ) 已知明文攻击( k n o w n p l a i n t e x ta t t a c k ) ：攻击者可以得到一些信息的密 文，并且知道这些信息对应的明文。攻击者的任务是推出密钥、或者导出一个 算法，此算法可以对用同一密钥加密的任何新的信息进行解密。 ( 3 ) 选择明文攻击( c h o s e n p l a i n t e x ta t t a c k ) ：攻击者可以得到一些信息的密 文和对应的明文，并且也可以选择被加密的明文。攻击者的任务是推出密钥、 或者导出一个算法，此算法可以对用同一密钥加密的任何新的信息进行解密。 ( 4 ) 选择密文攻击( c h o s e n c i p h e r t e x ta t t a c k ) ：攻击者可以选择不同的被加密 的密文，并且得到对应的解密的明文。攻击者的任务是推出密钥。 上述几种攻击方式是以强度递增排列的，唯密文攻击是最容易防护的攻击。 在每种情况下，攻击者的目标都是获得正在使用的密钥、或者待破译密文所对 应的明文。 2 3 公钥密码算法 为了解决信息公开传送和密钥管理问题，美国著名密码学家d i 伍e 和 h e l l m a n 于1 9 7 6 年提出了公钥密码学的概念【1 5 , 1 6 l 。公钥密码学的提出是整个密 码学发展史上的一次伟大革命。与对称密码算法不同，公钥密码算法基于单向 函数而不是基于替换和置换，使用两个独立的密钥：加密密钥( 又称公开密钥， 简称公钥) 和解密密钥( 又称私人密钥，简称私钥) ，其中，加密密钥公开，解 密密钥保密。使用公钥密码算法在保密通信、密钥分配和认证等领域有着极为 重要的意义。 公钥密码算法的第一个算法是由m e r k l e 和h e l l m a n 1 7 ，1 8 l 联合开发的背包算 法，该算法基于组合数学中的背包问题，又称m h 背包算法。在m e r k e l 和 h e l l m a n 之后，r i v e s t 、s h a m i r 和a d l e m a n 联合提出了r s a 公钥密码算法【1 9 l ， 该算法基于大数的素因子分解问题。此外，还有以基于离散对数问题( d l p ) 为 基础的e l g a m a l 算法【20 1 、以基于椭圆曲线离散对数问题为基础的椭圆曲线密 码算法e c c 2 1 , 2 2 】。美国政府的官方数字签名标准d s s 算法【2 3 】是在e l g a m a l 算法的成果基础上稍作修改而成的。 2 3 1 背包算法 背包算法最初只能适用于加密，后来被s h a m i r 改进，使之可以适用于数字 签名【2 4 1 。背包算法的安全性依赖于求解背包问题的困难性，即给定一个由互不 相同的数组成的集合及和，要找出一个子集之和等于给定的和。背包问题是一 个n p 完全问题。 m h 背包算法描述如下： 给定：n 个值m ，m 2 “，m 。及一个和s 。 计算匆，使之满足： s = 岛m l + b 2 m 2 + + 厶 其中参的值为o 或l ，l 表示在背包中，0 表示不在。该算法将信息编码为 背包问题的解。 将背包问题应用于公钥密码学是因为有两类不同的背包问题，一类在线性 时间内较易求解，另一类在线性时间内较难求解。私钥使用较易求解的背包问 题，公钥使用较难求解的背包问题。由于m e r k l e h e l l m a n 变换无法将超递增序 列的特性完全隐藏起来，因此m h 背包算法被证明是不安全的。 2 3 2r s a 算法 r s a 的安全性依赖于大数的素因子分解的困难性，即给定一个整数为两个 大素数的乘积，要确定这两个素因子。从公钥和密文中恢复明文的难度等价于 分解两个大素数之积。 r s a 算法描述如下： ( 1 ) 随机选择两个大素数p 和q ( 保密) 。 ( 2 ) 计算，2 = p q ( 公开) 和( 刀) = ( p 一1 ) ( g 一1 ) ( 保密) 。 ( 3 ) 随机选择一个加密密钥e ( 公开) ，满足g c d ( e ，) ) = l 。 ( 4 ) 计算解密密钥d ( 保密) ，满足d e 三l m o d 中( 珂) 。 ( 5 ) 得出公钥p k = p ，刀 ，私钥s k = d ，刀) 。两个素数p 和g 不再需要，应 该被舍弃，不可泄漏。 ( 6 ) 加密变换：对明文m 乙，先将它分成比n 小的数据分组( 采用二进 制数) ，再选择长度小于l o g ，甩位的数字作明文块，密文为： c = e ( m ) = m 8 m o d n ( 7 ) 解密变换：对密文c 乙，明文为： m = d ( c ) = c d m o d n r s a 算法利用了数学中存在的一种单向性，即许多运算本身并不难，但是 把它倒回去作逆运算很难。对于r s a 来说，这个困难性就表现在对r 的因子分 解上。若n = p q 被因子分解，( 玎) = ( p 1 ) ( g 一1 ) 就可以被算出，进而根据 d e 兰l m o d 中( 玎) 求得解密密钥d ，从而破译r s a 。 由于因子分解算法的不断进步以及计算机硬件技术的飞速发展，为了保证 r s a 的安全性，又采用了如下措施： ( 1 ) 产生更多位数的大素数。目前，r s a 密钥长度一般最低采用1 0 2 4 位， 这能够保证在现有数学理论基础上，r s a 密码体制是安全可靠的。 ( 2 ) 选择合适的p ，q 。如果p ，q 选择不当，则攻击者可以利用公钥反复对密 文进行多次加密就能还原出明文。但是，如果选择的p ，g 使得p - 1 ，q - 1 各能被 6 一个大素数p ，q 整除，并且使得尸一l ，q 1 分别含有大素数因子，则上述破译成 功的概率很小。 2 3 3e l g a m a l 算法 e l g a m a l 算法既可以用于数字签名又可以用于数据加密，其安全性依赖 于有限域上求解离散对数问题的困难性，即p 是素数，g 和m 是整数，要找出工 使得g 。兰mm o d p 成立。求解离散对数问题不会比因子分解容易，现阶段有限 域上的离散对数问题仍然无法被破解。 要产生一对密钥，首先选择一个素数p 与两个随机数g 和x ，其中g 和x 都小于p ，然后计算： y = g m o d p 公钥是y 、g 和p ( g 和p 可以由一组用户共享) ，私钥是x 。 ( 1 ) e l g a m a l 数字签名 设签名信息为m 。选择一个随机数k ，k 与p 一1 互素。计算a ： a = g m o d p 利用扩展欧几里德算法从下式中求解6 ： m = ( x a + k b ) m o d ( p - 1 ) 得到信息m 的数字签名为( 口，6 ) 。随机数k 必须保密。 验证签名时，只要验证下面等式是否成立： y 4 a 6 m o d p = g 肘m o d p ( 2 ) e l g a m a l 数据加密 e l g a m a l 方案的一种修改版可以对信息进行加密。设加密信息为m 。选 择一个随机数k ，k 与p 一1 互素。 计算密文对( a ，6 ) ： a = g m o d p b = y k m m o d p 解密时，计算： m = b a 。( m o d p ) 2 3 4 椭圆曲线密码算法 椭圆曲线密码体匍 ( e l l i p t i ec u r v ec r y p t o s y s t e m ，e c c ) 来源于对椭圆曲线的 研究。椭圆曲线指的是由韦尔斯特拉斯( w e i e r s t r a s s ) 方程 y 2 + a x y + 砂= x 3 + 珏2 + d x + e 所确定的平面曲线，它是由方程的全体解( x ，y ) 再加上一个无穷远点或零点口构 成的集合，其中口、b 、c 、d 和e 是满足一些简单条件的实数。椭圆曲线密码体制 中的椭圆曲线定义在有限域上，其安全性依赖于求解椭圆曲线上的离散对数问 7 题的困难性，即给定椭圆曲线e 上的一个点p ，对任意的点q ，要存在整数k 使得 q = 舻成立。将椭圆曲线应用于公钥密码体制，最早是由k o b l i t z l 2 1 】和m i l l e r t 2 2 】 于19 8 5 年分别提出的。 椭圆曲线密码算法描述如下： 首先选择一个点g 和一个椭圆群e 。( 口，6 ) 作为参数。某成员a 选择一个私钥 甩。并且产生一个公钥只= n。发送者要加密并且发送一个报文只给彳，可以选,4g 择一个随机数k ，并且产生由如下点对组成的密文q = ( 施，己 - i - 圮) 。 要解密这个报文只，么用这个点对的第一个点乘以a 的私人密钥，再从第 二个点中减去这个值： 己+ 尼巴一b a ( k 6 ) = 圪+ 七( 甩_ g ) 一n a ( k g ) = 乞 发送者通过对己加上圮来保护己，除了发送者之外没有人知道k 的值。因 此，即使只是公钥也没有人能去掉圮，当然只有知道刀。的人才可以去掉圮。 椭圆曲线密码体制是目前公钥密码体制中，对每比特提供的加密强度最高 的一种体制。目前求解椭圆曲线上的离散对数问题的最好算法是p o l l a r d r h o t 2 5 1 方法，其时间复杂度是完全指数时间的，而目前最好的大整数分解算法的时间 复杂度是亚指数时间的。例如：当r s a 的密钥使用2 0 4 8 位时，仅仅使用2 3 4 位 e c c 的密钥，就可以获得相同的安全强度，此时它们之间的密钥长度相差6 倍， 并且这个差距会随着e c c 密钥的增长而变得更大。 2 4 数字签名 在政治、军事、外交、商业中的文件以及个人书信中，传统上采用手写签 名或者印章形式来进行签名，以便在法律上能认证、核准、生效。随着网络技 术的不断发展，人们希望能够利用计算机来实现文件、书信的快速传递以及进 行远距离交易。正是这些要求促进了数字签名技术的诞生，它有助于实现大型 网络安全通信中密钥分配、以及实现认证。 数字签名与手写签名类似，具有以下几个特性： ( 1 ) 接收方能够验证发送方的签名。 ( 2 ) 发送方不能否认已发出签名的信息。 ( 3 ) 接收方不能伪造已收到的签名信息。 ( 4 ) 第三方可以确认收发双方的信息传递，但是不能伪造这一过程。 数字签名可以分为两类：直接数字签名和仲裁数字签名。 直接数字签名：只涉及通信双方。假定接收方知道发送方的公钥，则发送 方通过使用自己的私钥对整个信息或者信息的散列值加密来产生数字签名，接 收方使用发送方的公钥验证签名的真实性。所有的直接数字签名方案都有一个 共同的弱点，即方法的有效性依赖于发送方私钥的安全性。如果发送方的私钥 被盗用，则攻击者可以使用该发送方的签名签发一条信息，并且加盖盗用前的 8 任何时刻作为时间戳。同理，如果发送方想否认已发送过的某签名信息，那么， 他可以声称其私钥已丢失或者被盗用，有人伪造了他的签名。 仲裁数字签名：为了解决直接数字签名中存在的问题而引入仲裁者。从发 送方到接收方的每条已签名的信息都先发送给仲裁者，仲裁者对信息及签名验 证后，加上日期连同一个证明发送给接收方。在仲裁数字签名中，发送方无法 否认自己已经发送的信息，但是仲裁者必须得到所有用户的信任。 目前已经提出了许多数字签名方案，例如：r s a 签名、e l g a m a l 签名、 d s a 签名等。 2 5 零知识证明 零知识证明( z e r o k n o w l e d g ep r o o f ) 理论主要用于密码协议、密钥分配方案 和公钥密码体制的设计和分析，它为所设计的方案的安全性提供了有利的证据。 零知识证明最早由g o l d w a s s e r 等人【2 6 l 于8 0 年代初提出。一方( 证明者) 试图向另一方( 验证者) 证明他拥有某秘密，同时要求在证明过程中不向验证 者提供任何该秘密的相关有用信息。 零知识证明可以分为两种：一种称为交互式零知识证明；另一种称为非交 互式零知识证明。 交互式零知识证明是指在证明方和验证方之间通常采用“呼叫一应答 方 式的一种零知识协议，即验证方质询证明方，证明方则回答验证方提出的问题， 最后验证方以接受或拒绝的方式回应证明方。g o l d w a s s e r 等人提出的零知识证 明就是交互式的。 非交互式零知识证明是由b l u m 等人【2 7 , 2 8 】于8 0 年代末提出的，它是指验证 方无需向证明方提出质询，通过利用一个称为参考串的短随机串代替交互实现 零知识证明。非交互式零知识证明可以大大节省信息交互花费的时间，从而使 得非交互式零知识证明比交互式零知识证明有更好地适用范围。 零知识证明的安全性主要包括以下三个方面： ( 1 ) 完备性：如果证明方的确拥有某秘密，并且证明方和验证方都是诚实 的，则验证方总会接受证明方的零知识证明，相信证明方拥有该秘密。 ( 2 ) 合理性：如果证明方并不知道某秘密，则他要利用零知识证明使得验 证方相信他拥有该秘密几乎是不可能的，即如果证明方不知道秘密，则验证方 总是拒绝他的证明。 ( 3 ) 零知识性：即使验证方确信证明方知道某秘密，但是验证方并没有获 得任何该秘密的相关有用信息，从而也就不能向别人证明他知道该秘密。 2 6 本章小结 本章首先概述了密码体制和密码分析，然后探讨了几种重要的公钥密码算 9 法，例如：背包算法、r s a 算法、e l g a m a 算法和椭圆曲线密码算法，最后 介绍了数字签名和零知识证明。 1 0 第三章门限秘密共享研究 门限秘密共享最初的出发点在于解决密钥的安全问题。在大多数情况下， 密钥由可信中心专门管理，一个密钥控制多个重要文件。一旦密钥丢失，就可 能造成多个重要文件不能打开。在密钥失窃的情况下，还可能造成多个重要文 件被窃取。为了解决这个问题，常用的方法是为密钥创建多个备份并且将这些 备份分发给多人保管或者保存在不同的地方。但是这种方法并不理想，因为创 建的备份数目越多，密钥泄漏的可能性越大。门限秘密共享则为解决上述问题 提供了新的方法。 3 1 门限秘密共享 3 1 1 门限秘密共享的基本思想 门限秘密共享最早由s h a m i r 2 】和b l a k l e y t 3 】于1 9 7 9 年分别提出，其基本思 想是可信中心将共享的秘密( 即密钥) 分成多个秘密份额分发给多个成员( 又 称密钥共享者) ，在恢复秘密时，即使秘密份额存在部分丢失或损坏，只要参与 秘密恢复过程的成员共享的秘密份额的数目不少于门限值，秘密就可以恢复。 门限秘密共享的基本模型描述如下： 将秘密d 按下述方式分成n 个秘密份额4 ，以，吨： ( 1 ) 己知任意k 个4 可以计算出d ： ( 2 ) 己知任意k 一1 个或更少个z ，无法计算出d 。 基于这种模型的方案称为( 尼，n ) 门限方案，简称门限方案，k 称为门限值。 3 1 2 门限秘密共享的欺骗问题 门限秘密共享可能存在的欺骗方式有两类：外部欺骗和内部欺骗。 ( 1 ) 外部欺骗是指非法成员伪装成合法成员去骗取正确的秘密份额。如果 非法成员骗取数目达到门限值的秘密份额，就可以恢复秘密。 ( 2 ) 内部欺骗： 1 ) 可信中心的“权威欺骗 ：可信中心在分发秘密份额时，可能会给某成 员分发一个假的秘密份额，使得包含这个成员的一组合法成员都不能恢复正确 的秘密。 2 ) 不诚实成员的欺骗：当数目达到门限值的合法成员使用他们各自的秘密 份额来恢复秘密时，不诚实成员提供一个假的秘密份额，来骗取其他成员正确 的秘密份额，独自恢复该秘密，而其他成员都无法恢复该秘密。 3 1 3 门限秘密共享的应用 门限秘密共享主要应用于密钥管理。此外，还可以应用于其他方面： ( 1 ) 等级系统中的访问控制：在等级系统中，合法成员及其拥有的信息被 严格分成若干个安全等级，前趋安全类的成员可以利用门限秘密共享计算所有 后继安全类成员的密钥，可以访问后继安全类成员的信息，反之不行。 ( 2 ) 门限数字签名：有时一份文件或者一份协议需要多人或多部门同意才 有效，那么就需要多人在同一份文件上签名，数目达到门限值的签名者联合产 生有效地签名，而数目少于门限值则不能产生有效地签名。 ( 3 ) 数据库保护：对重要或者机密的信息，数目达到门限值的管理者联合 掌握该信息，对其进行查看、添加、审核等操作，而数目少于门限值则不能掌 握该信息。 ( 4 ) 电子选举：在网上进行投票选举，通常采用计票中心来计票，将一个 计票中心的权力分散给多个计票中心，只要数目达到门限值的计票中心不被攻 破，就可以在一定程度上保证选举方案的完备性和安全性。 3 2 几种典型的门限秘密共享方案 3 2 1 b l a k l e y 门限秘密共享方案 b l a k l e y 采用的是矢量方案，其基本思想是利用多维空间中的点来共享秘 密。秘密被定义成k 维空间中的一个点，每个秘密份额都是包含此点的一个k l 维的超平面，任意k 个这种超平面的交点可以唯一确定该秘密，而k 1 个仅能 确定其交线，因此得不到任何该秘密的相关有用信息。 例如：设门限值为3 ，那么原秘密就是三维空间中的一个点，每个秘密份 额都是一个不同的二维超平面。如果有三个秘密份额，则恰好能确定该点在这 三个超平面的交点；如果少于三个秘密份额，则不能确定。 3 2 2s h a m i rf - j 限秘密共享方案 s h a m i r 采用的是l a g r a n g e 插值多项式方案，描述如下： 方案参数：k 是门限值，玎是成员的总数，p 是一个大素数( p 以r ) ，秘密 空间与秘密份额空间相等，均为有限域g f ( p ) ，x ix 2 ，毛是g f ( p ) 上疗个互不 相同的元素。以上这些参数都是公开的。s 是共享的秘密。 秘密分发： ( 1 ) 可信中心随机选择g f ( p ) 上一个k - 1 次多项式： 厂( x ) = a o + 口l x + + a t , 一l x - 1m o d p 显然s = a o 。 ( 2 ) 可信中心对x l ，x 2 ，矗分别计算墨- - - 厂( 葺) ，f 1 ，珂。 ( 3 ) 可信中心将( 玉，s ) 分发给成员只，扛l ，甩，墨作为f 的秘密份额。 秘密恢复： 1 2 任何k 个拥有秘密份额的成员都可以将秘密份额放在一起，通过l a g r a n g e 插值公式计算，恢复秘密s ： kt o ( x ) = s 兀导m o d p ，。l j - i j 刮“ “ 其中s = f ( o ) ，而任何少于k 个成员则无法恢复秘密s 。 s h a m i rf - 1 限秘密共享方案具有以下优点： ( 1 ) 在原有成员的秘密份额保持不变的情况下，可以增加新成员，只要总 数不超过p 。 ( 2 ) 通过选用常数项仍为s 的另一个k 1 次多项式，可以将某些成员的秘 密份额作废。 ( 3 ) 可以根据成员不同的重要性，分发给成员不等数目的秘密份额，从而 实现分级方案。 但是，在s h a m i r 门限秘密共享方案中，假设“所有成员都是诚实的”，这 可能会出现两个问题： ( 1 ) 不能有效地防止可信中心的欺骗； ( 2 ) 不能防止成员之间的欺骗。 因此，“所有成员都是诚实的 的假设在现实中很难成立，这也是s h a m i r 门限秘密共享方案难以直接应用于实际系统中的重要原因。 3 2 3 可验证的秘密共享方案 可验证的秘密共享方案是指可以验证可信中心分发的秘密份额是否正确， 从而有效地识别可信中心的分发欺骗，甚至阻止可信中心的“权威欺骗”。 为了解决在s h a m i r 门限秘密共享方案中存在的问题，c h o r 等人【4 】提出了可 验证秘密共享( v e r i f i a b l es e c r e ts h a r i n g ，v s s ) 的概念。c h a n g 和c h a n 3 5j 提出了 验证可信中心分发的秘密份额的方法。f e l d m a n t 5 】和p e d e r s e n 6 7 】分别提出了不 同的可验证秘密共享方案。i b r a h i t 3 6 】提出了判断共享的秘密是否为大素数的可 验证秘密共享方案。s t a d l e r u7 j 提出了公开可验证秘密共享( p u b l i c l yv e r i f i a b l e s e c r e ts h a r i n g ，简称p v s s ) 的概念，不仅合法成员而且其他人也可以对秘密份 额的正确性进行验证，从而使得该方案能够应用于实际系统中。下面介绍最具 有代表性的f e l d m a n 和p e d e r s e n 可验证秘密共享方案。 ( 1 ) f e l d m a n 可验证秘密共享方案 f e l d m a n 通过使用一个公开的验证函数来改进s h a m i rf - i 限秘密共享方案， 可以抵抗包括可信中心在内的一1 ) 2 个攻击者的攻击。该方案描述如下： 方案参数：p 是一个大素数，q 为p - 1 的素因子，g 为z ：上的q 阶元。三元 组( p ，q ，g ) 是公开的。k 是门限值，n 是成员的总数，s 是共享的秘密。 秘密分发： 1 ) 可信中心随机选择一个k - 1 次多项式f ( x ) ez q 【x 】： f ( x ) = a o + a l x + + a k l x - 1 显然f ( o ) = a o = s