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

无可信中心门限秘密共享的研究 摘要 随着计算机及网络技术的快速发展，信息安全日益得到人们的关注。秘密 共享改变了以往单人加密模式，能够提高系统的安全性、鲁棒性和可用性。因 此，秘密共享研究不仅有重要的理论意义，而且具有广泛的应用价值。 本文介绍了门限秘密共享的产生和发展，详细讨论了几种典型的门限秘密 共享方案，分析了这些方案的优越性和不足之处。针对有可信中心秘密共享方 案中存在的不足，提出了一种基于无可信中心秘密共享的认证方案。本文完成 的主要工作如下： ( 1 ) 提出了一种基于无可信中心秘密共享的认证方案。该方案的c a 由 多台服务器组成，用户的公钥证书由c a 的若干台独立的服务器和用户自身协 同产生，无需可信中心的参与。 ( 2 ) 对所提出方案的安全性和鲁棒性进行了分析。c a 的私钥分散在各个 服务器中，当服务器数目小于门限值，就不能使用c a 的私钥进行签名，这样 能确保系统的安全性。当一定数目的服务器出现故障或受到攻击时，只要服务 器个数不少于门限值，则不会影响系统的正常运行，故而增强了系统的鲁棒性。 ( 3 ) 在w i n d o w sx p 系统下，利用v c + + 6 0 和m i r a c l 库实现了该方案 的原型系统。实验结果表明该方案是可行的和正确的。 最后本文进行了总结和展望。 关键词：秘密共享，无可信中心，l a g r a n g e 插值 r e s e a r c h i n go f s e c r e ts h a r i n gw 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 er a p i dd e v e l o p m e n to f c o m p u t e ra n dn e t w o r kt e c h n o l o g y , p e o p l eh a v e p a i dm o r ea n dm o r ea t t e n t i o nt oi n f o r m a t i o ns e c u r i t y r e c e n ts e c r e ts h a r i n gh a s c h a n g e dt h ep r e v i o u ss i n g l ee n c r y p t i o nm o d e ，a n di tc a ni m p r o v et h es e c u r i t y , r o b u s t n e s sa n da v a i l a b i l i t yo fi t ss y s t e m t h e r e f o r e ，t h er e s e a r c ho ns e c r e t s h a r i n g h a sb o t ht h e o r e t i c a ls i g n if i c a n c ea n de x t e n s i v ea p p l i c a t i o nv a l u e t h i st h e s i sf i r s t l yi n t r o d u c e st h ed e v e l o p m e n to ft h r e s h o l ds e c r e ts h a r i n g ，w i t h s e v e r a l t y p i c a lt h r e s h o l ds e c r e ts h a r i n gs c h e m e si sd i s c u s s e df u r t h e ri nd e t a i l ， f o c u s i n go na n a l y s e so ft h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s i nr e g a r dt ot h e s h o r t c o m i n g se x i s t e di ns e c r e ts h a r i n gs c h e m e sw i t ht r u s t e dp a r t i e s ，ac e r t i f i c a t i o n s c h e m ei sp r o p o s e db a s e do ns e c r e ts h a r i n gw i t h o u tat r u s t e dp a r t y t h i st h e s i sh a s f i n i s h e dt h ef o l l o w i n gw o r k ： ( 1 ) as c h e m ei sp r o p o s e db a s e do ns e c r e ts h a r i n gw i t h o u tat r u s t e dp a r t y a c c o r d i n gt ot h es c h e m e ，t h ec ai sc o m p o s e do fan u m b e ro fs t a n d a l o n es e r v e r s t h eu s e r sp u b l i ck e yc e r t i f i c a t ei sp r o d u c e dc o l l a b o r a t i v e l yb o t hb yt h es t a n d a l o n e s e r v e r so fi t sc aa n dt h eu s e r st h e m s e l v e sw i t h o u tt h ep a r t i c i p a t i o no fa n yt r u s t e d p a r t y ( 2 ) t h e o r e t i c a la n a l y s e so fs e c u r i t ya n dr o b u s t n e s sa r ep r o v i d e df o rt h e s c h e m e c a sp r i v a t ek e yi sd i s t r i b u t e di na l ls e r v e r s w h e nt h en u m b e ro fs e r v e r s i ss m a l l e rt h a nt h et h r e s h o l dv a l u e ，t h e ns i g n a t u r e sc a nn o tb e g i v e no u tb yt h e p r i v a t ek e yo fc a ，t h e r e f o r et h es e c u r i t yo fs y s t e mi se n s u r e d w h e nac e r t a i n n u m b e ro fs e r v e r sf a i lt ow o r ko rg e ta t t a c k e d ，s ol o n ga st h en u m b e ro fs e r v e r si s n ol e s st h a nt h et h r e s h o l dv a l u e ，t h e nt h en o r m a lo p e r a t i o no ft h es y s t e mw i l ln o tb e a f f e c t e d ，f o rt h i sr e a s o nt h er o b u s t n e s so ft h es y s t e mi se n h a n c e d ( 3 ) t h ep r o t o t y p es y s t e mo ft h es c h e m ei sr e a l i z e db yu s i n gv c + + 6 0a n d m i r a c ld a t a b a s ei 1 1w i n d o w sx ps y s t e m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e s c h e m ei sw o r k a b l ea n dc o r r e c t a tl a s t ，as u m m a r ya n da no u t l o o ka r eg i v e na tt h ee n do ft h et h e s i s k e yw 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 ；l a g r a n g ei n t e r p o l a t i o n 插图清单 图4 1p k i 管理模型2 3 图4 2 系统框架图2 4 图5 1 p 产生的数据3 4 图5 2p ，接收到的数据3 4 图5 3p ，对p 。的数据进行验证3 6 图5 4p 的秘密份额3 8 图5 5c a 的公钥y 3 8 图5 6 珐产生的4 0 图5 7p 。产生的签名4 0 图5 8 用户u 。的证书：4 1 图5 - 9 用户u r 验证证书4 2 独创性声明 本人声明所呈交的学位沦文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别j 以标志和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得盒8 曼王些太堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者酶毕题 签字吼年月同 学位论文版权使用授权书 本学位论文作者完全了解金8 曼王些太堂 有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅或借阅。本人授权 金8 里王、业友堂可以将学位论文的全部或部分论文内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 越 导师签名： 签字同期： 电话： 邮编： 澎飞垧21j：月后 名 业签年毕 者 者 作：作： 文期文位址论同论单地位字位作讯学签学工通 致谢 时间飞逝，一转眼，三年的研究生生活即将结束。在研究生阶段，我的知 识水平和专业技能都有了长足的进步。这里面既有自己的不懈努力，更重要的 是来自导师和同学的帮助。 首先我要感谢合肥工业大学计算机与信息学院的各位老师，尤其要感谢我 的导师侯整风教授。感谢侯老师在百忙之中抽出时间指导我完成毕业论文的每 一个环节。侯老师知识渊博、治学严谨、教学经验丰富，对我的人生观和价值 观都有着很大的影响。同时，也督促我在今后的工作和学习中严格要求自己。 其次我要感谢网络与信息安全实验室的同学们。在这三年的学习生活中， 我们互相帮助，共同进步，建立起了深厚的友谊。在课题的研究和撰写中，他 们在很多问题上都给予我极大的启发和帮助。 最后，我还要感谢我的父母、家人以及所有关心我、帮助过我的人。 作者：毕越 2 0 10 年4 月 第一章引言 1 1 研究的背景及意义 随着计算机互联网技术的不断发展，越来越多的人们利用网络进行资源共 享和信息交流。互联网给人们带来了便利，同时也带来了安全性的问题。因此， 人们也更加地重视在网络中出现的安全问题，对信息安全领域的研究也成为了 热门的研究课题。 在信息安全领域中有多种实用的技术，如数字加密技术、数字签名技术和 身份认证技术等，而密钥的安全性则是这些技术是否有效的重要保障。如果密 钥丢失或被窃取，用户便无法获得信息，而且还有可能使非法用户获得信息。 因此，对密钥的管理是信息系统安全性和保密性的关键因素。 门限秘密共享是密码学的一个重要组成部分，在密钥管理中得到了广泛的 应用。其基本思想为：将秘密分割为若干个秘密份额，并将它们分别分发送给 若干个参与者，只要合法的参与者数量大于或等于门限值，就能利用他们的秘 密份额恢复出秘密，否则就无法恢复秘密。把门限秘密共享应用在信息安全领 域，可以有效解决因权力过分集中而遭到滥用的问题，同时也保证了秘密的可 靠性和可用性。1 9 7 9 年，s h a m i r 1 】和b l a k l e y 2 】分别提出了秘密共享思想并给 出了具体的方案。秘密共享的基本思想是指：将共享的秘密分割成若干个秘密 份额，并安全地分发给所有参与者，只要合法的参与者数量大于或等于门限值t 个，就可以进行协同合作来恢复共享的秘密，否则将无法恢复。 自1 9 7 9 年以来，人们已构造了多种不同环境下的秘密共享方案，归纳起来 有两大类：有可信中心秘密共享和无可信中心秘密共享。前者是指秘密份额的 产生和分发、甚至恢复均需要可信中心完成，产生并分发秘密份额。后者是指 无需可信中心的协助，秘密份额的产生以及秘密的恢复均由成员协同完成。而 在实际应用中，有可信中心秘密共享可能存在“权威欺骗 ，并且在现实中需 要成员具有较高的诚信度也是不明智的假设。因此，与有可信中心秘密共享相 比，无可信中心秘密共享的安全性更高，可用性更强。对无可信中心秘密共享 研究的主要目的就是：寻找合适的方案来保证信息能够安全、有效地发布和传 输。此外，无可信中心秘密共享的秘密份额如何进行分发，是人们研究的热点 问题，其发展空间还很大。因此，无可信中心秘密共享不仅存在着重要的理论 研究价值，更在实际应用中存在着广泛的应用前景。 1 2 国内外研究现状 1 9 7 9 年，s h a m i r 1 】和b l a k l e y 2 】分别提出了秘密共享思想并给出了具 体的方案。之后，许多学者对门限秘密共享进行了深入的研究。比较有特点的 有：由k a m i n 等人t 31 提出的基于矩阵方法的门限秘密共享。a s m u t h 和b l o o m 4 】 对中国剩余定理进行了研究，提出了一种基于中国剩余定理的门限秘密共享方 案。同态秘密共享的概念首先是由b e n a l o h 等人【5j 提出的。b l u n d o ”等人从信息 论的角度出发，提出了多秘密共享的理论。b r i c k e l l 和d a v e n p o r t 7 1 提出了理想的 秘密共享方案。但是，上述方案都无法有效的解决可信中心的欺骗行为和参与 者之间的欺骗行为等问题。 为了防止可信中心的欺骗行为和参与者之间的欺骗行为，c h o r 8 】在1 9 8 5 年提出了一种可验证秘密共享方案。f e ld m a n 9 j 在1 9 8 7 年首先提出了一种非 交互式的可验证秘密共享方案。之后，由p e d e r s e n 1 0 】【1 1 】首先提出了一种基 于无条件安全的非交互式的可验证秘密共享方案。可是他们的方案都只能防止 可信中心的欺骗行为和参与者之间的欺骗行为，而对于可信中心的“权威欺骗” 和秘密份额的骗取却无法防止。 i n g e m a r s s o n 和s i m m o n s 1 2 】于1 9 9 1 年提出了一种无可信中心秘密共享方 案，可以有效的防止可信中心的“权威欺骗”。1 9 9 4 年，h a r n 1 3 】提出了一种 无需可信中心的门限群签名方案。1 9 9 5 年，h e r z b e r g 等人【1 4 】提出了先应秘密 共享的概念，成功解决了以往的门限方案中在周期上出现的安全性问题。2 0 0 1 年，为了解决无可信中心模型中共同密钥的产生问题，r o s a r i0 等人【1 5 】在门限 d s s 签名方案中提出了联合秘密共享方案。2 0 0 3 年，p r a m a n i k 和u p a d h y a y a 1 6 j 提出了一种可验证的先应秘密共享方案，在该方案中，秘密份额是可以被可恢 复的。2 0 0 3 年，王斌和李建华i l7 j 提出了一种无可信中心的门限签名方案，指 出了h a r n 1 3j 签名方案的缺点。 1 3 课题研究的主要内容和拟解决的问题 1 3 1 研究内容和主要工作 本文介绍了公开密钥密码体制的相关知识，讨论了几种典型的门限秘密共 享方案，总结了传统门限秘密共享方案的优越性和不足之处。通过分析以往的 门限秘密共享方案中存在的不足，提出了一种基于无可信中心秘密共享的认证 方案。 论文的主要工作如下： ( 1 ) 深入分析门限秘密共享理论及其典型方案，如经典秘密共享方案、可 验证秘密共享方案、动态秘密共享方案和多秘密共享方案等。通过分析研究， 详细阐述了传统门限秘密共享方案中的优点和不足之处； ( 2 ) 提出了一种基于无可信中心秘密共享的认证方案，提高了系统的安全 性、鲁棒性和可用性，并在理论上对该方案进行了分析； ( 3 ) 实现了个网络环境中的无可信中心秘密共享的认证方案原型系统， 结合实验数据，对系统进行了分析。 1 3 2 拟解决的问题 ( 1 )在无可信中心环境下，如何产生、分发秘密份额。 ( 2 )如何实现若干成员的协同合作能够使用但不能暴露原秘密，从而保 证原秘密的可重复使用。 ( 3 )大数运算问题。通过m i r a c l 大数库来实现大数运算。 1 4 本论文的组织结构 本论文的组织结构如下： 第一章引言。概述了课题研究的背景及意义、国内外研究现状、课题研 究的内容和主要工作、拟解决的问题。 第二章公开密钥密码体制。介绍了数论的基础知识、公开密钥密码体制 和数字签名技术。 第三章门限秘密共享方案。概述了门限秘密共享的基本模型，讨论了几 种典型的门限秘密共享方案，并进行了分析和比较。 第四章基于无可信中心秘密共享的认证方案。提出了一个基于无可信中 心秘密共享的认证方案，并对该方案进行了分析。 第五章原型系统的实现。简述了大数运算的实现，详细地介绍了原型系 统的各个组成部分，通过实验数据验证了本方案的正确性和可用性。 第六章总结与展望 第二章公开密钥密码体制 公开密钥密码体制的提出在密码学发展史上具有重要的意义，为密码学的发展 提供了新的思路。目前公开密钥密码体制主要有r s a ，e l g a m a l ，e c c 等。数论是 设计公开密钥密码算法的基础。 2 1 数论的基础知识 在近代密码学中，严密的数学理论是密码协议的基石。因此，数论是设计 公开密钥密码算法的基础。下面就将详细介绍有关数论的基础知识。 2 1 1 有限域 定义2 1 密码学技术的运算都是基于有限域上的算术运算，因此实现有限 域的算术运算是实现密码学的关键。域是由一个集合f 和两种运算构成，这 两种运算分别为加法运算( 用“+ 表示) 和乘法运算( 用“，i c 表示) ，并且满 足以下特点： ( 1 ) f 中的元素均具有一个单位元( 用0 表示) ，并且对于加法运算构 成加法交换群。其中a 的逆元为一口： ( 2 ) f 中的非零元素均具有一个单位元( 用l 表示) ，并且对于乘法运 算构成乘法交换群。其中口的逆元为a 一： ( 3 ) 分配律成立：对于v a ，b ，c f ： ( 口+ 6 ) 幸c = 口幸c + b 木c c 毒( 口+ 6 ) = c 枣a + c 木b 成立。 定义减法：a b = 口+ ( - b ) 。 定义除法：a b = a * b ，b 叫是b 的逆元。 有限域( 伽罗瓦域) 是指集合f 中元素的个数是有限的。反之，则称为 无限域。 有限域的阶是指有限域元素的个数。假设存在一个q 阶有限域f ，p 是 一个素数，也称为域f 的特征当且仅当q = p ”。若整数m = 1 ，则域f 就称为 素域：若整数肋= 2 ，则域f 就称为扩域。任意两个q 阶有限域除了域元素 的表示符号不同外，他们在结构上是相同的。这是因为，对于任意的一个素数 幂q ，实质上有且仅有一个q 阶有限域。故我们可以得出：任意两个q 阶 有限域都是同构的，用c 或者g f ( q ) 表示。 2 1 2 乘法的逆元 定义2 1 我们称函数妒为欧拉函数，当且仅当矽满足下列条件：对于玎1 ， 伊( ，2 ) 表示在区间 1 ，n 内与1 3 互素的整数个数。 4 欧拉函数的性质： ( 1 ) 若p 是素数，则缈( p ) = p - 1 ； ( 2 ) 欧拉函数是乘性的，即若g c d ( m ，n ) = 1 ，则9 ( m n ) = 缈( 垅) 水缈( ，2 ) ； ( 3 ) 若n = 崩e l p 2 e 2 p 2 是f i 的素因子分解，则： 111 c p ( n ) = n ( 1 一二) ( 1 一二) ( 1 一二) ( 2 1 ) p l p 2 p k 定理2 1 欧拉定理若a 和n 互素，则口矿( ”) 兰1 m o d n 。 定义2 2 已知m 1 ，( 口，以) = 1 则存在c 使得c a 三l m o d n ，其中c 为a 对模刀 的逆，记为a 一。通常我们求逆元有以下两种方法： ( 1 ) ：若矽( 聍) 为已知，则由欧拉定理可得： a 幸口伊( ”) 一1 誊1 m o d n j a 一1 苦口伊( ”) 一1 m o d n( 2 2 ) ( 2 ) ：利用扩展的欧几里德算法找到整数x 和y 使得似+ m y = l ，这样 a 一1 兰x m o d n 。 2 1 3 模及同余的运算 定义2 3 模运算若口，b 为整数，存在a 除以b 的整数q ( 商) 和，( 余数) ， 使得： 口= q b + 厂，其中0 ， b 而且g 和，唯一。这里做除法所得的余数记为a r o o d b ( r = a r o o d b ) ，商记为 a d i v b ( q = a d i v b ) ，其中我们把b 称为模，把，= a m o d b 称为模运算。 模运算的性质任意整数口，b ，n ，其中以为模，存在： ( 1 ) ( 口6 ) m o d n = ( a m o d n ) ( 6 m o d n ) r o o d n c 争( a m o d n ) ( 6 m o d 门) m o d n = ( 口b ) m o d n ( 2 ) ( 口幸b ) m o d n = ( 口m o d 玎) 宰( b r o o d n ) m o d n c 亨( 口m o d 聆) 奎( b m o d 门) m o d n ；( 日木b a ) m o d n ( 3 ) ( 口木( 6 + c ) ) r o o d n = ( ( 口木b m o d n ) + ( a 木c m o d n ) ) m o d n c ( ( 口b m o d n ) + ( a 宰c m o d n ) ) m o d n = ( a + ( b + c ) ) m o d n 定义2 4 同余a ，b ，7 1 为整数且押0 ，如果n 能够整除( a 一6 ) ，即a b = k n ， k 为整数，我们称a 与b 是模n 同余的，记为a 兰b m o d n ，其中整数门称为该同余 的模。 同余的性质任意整数a ，b ，c ，d ，我们有： ( 1 ) a 兰b m o d n 当且仅当a 与6 被1 1 除时所得的余数相同； ( 2 ) ( 自反性) a 三a m o d 疗； ( 3 ) ( 对称性) 若a 三bm o d n ，则bf - a m o d 玎； ( 4 ) ( 传递性) 若a 暑b m o d n ，b 暑c m o d n ，则a 三c m o d n ； ( 5 ) 若a 毫b m o d 刀，c = d m o d 疗，贝0a + c 兰( b + d ) m o d 胛，且a c 毫b dm o d n 。 定理2 2 中国剩余定理若，z l ，n 2 ，仇是两两互素的，对于任意的整数 a l ，a 2 ，a k ，则同余方程组： x 誊口lm o d x 暑口2m o d n 2 x 量a km o d n k 对于模玎= 啊他仇有唯一解。 ( 2 3 ) 2 2 公开密钥密码体制 公开密钥密码体制的提出在密码学发展史上具有重要的意义，为密码学的发展 提供了新的思路。 1 9 7 6 年d i f f i e 和h e l i m a n 1 8 】首次提出了公开密钥密码体制的思想，它 是密码学史上的一次伟大革命，为近代密码学的发展提供了新的思路。公开密钥 密码体制克服了对称密码体制的缺点，能够进行数字签名、认证、鉴别，同时 也能够加密和解密。在密码学研究领域中被称为的一项伟大的发现，也为现代 密码学的诞生奠定了基础。 一般来说，公开密钥密码体制使用两个不同的密钥：公钥( 公开的) 和私 钥( 秘密的) 。只有私钥能够解密消息，公钥只是用来加密消息，无法解密。 从公钥很难推导出私钥。 在公开密钥密码体制中，加密密钥和解密密钥是分开的，可以实现一个用 户加密的消息能由多个用户解密，这在认证系统中得到了应用，实现了数字签 名的功能；可以实现多个用户加密的消息只能由一个用户解密，这在网络中得 到了应用，实现了秘密通信的功能。 常用的公开密钥密码算法都是建立在以下某一数学难题基础之上的： ( 1 ) 大整数分解问题：若p q = n ，其中n 为整数，p 和g 为两个大素 数，求解大素数p 和q ； ( 2 ) 离散对数问题：对于g 。皇a m o d p ，其中p 为素数，g 和a 均为整数， 求解x ； ( 3 ) 椭圆曲线离散对数问题：假设椭圆曲线e 上存在一个g 点，对于任意 的点d ，求解出整数m 满足o = m g 。 2 2 1r s a 密码体制 1 9 7 8 年，r i v e s t ，s h a m i r 和a l e m a n 1 9 1 提出了第一个有效的公开密钥密码 体制，称为r s a 密码体制。它是建立在欧拉定理的基础之上的，故该算法的 安全性基于大数分解的难度。 加密和解密： ( 1 ) 产生密钥 首先，任意选择两个大素数p 和g ，并且它们大小相近，求解n = p x q ( 公 开) ，则欧拉函数的值为： 6 缈( 聆) = ( p - 1 ) ( q - 1 ) ( 保密) ( 2 4 ) 然后，随机选取整数e ( 公开) ，满足g c d ( e ，妒( 胛) ) = 1 ，并计算： d = e 1m o d o ( n ) ( 保密)( 2 5 ) 其中( p ，即) 为公钥，d 为私钥。 ( 2 ) 加密算法 假设c 为密文，且0 c ”。将c 按”的比特长度分组，依次对每个分组m 做 一次加密，所有分组的密文构成的序列即为对c 加密的结果。并且明文m 满足 0 m 疗。 加密算法为： c = e ( m 、三m 8m o d n ( 2 6 ) ( 3 ) 解密算法 解密算法为： m = d ( c ) 兰一m o d n ( 2 7 ) 下面对解密过程进行证明： 证明：d ( c ) 暑c d 兰( m 。) d 三m 耐董m m o d n ( 2 。8 ) e d 善1m o d o ( n ) je d = r 缈( 纷) + 1 ( 其中，为整数)( 2 9 ) 若( m ，p ) = 1 ，由f e r m a t 定理可知： m p 一1 暑1 m o d p ( 2 1 0 ) 等式( 2 1 0 ) 两边同时取r ( q 一1 ) 次方，然后两边再乘以所得： m 1 + 7 ( p 一1 x q 一1 ) 暑m m o d p ( 2 11 ) 若( m ，p ) = p ，则等式( 2 1 1 ) 两边模p 均为零，因此等式成立。故： 肌耐毫m m o d p ( 2 1 2 ) 总成立。 同理，m 耐暑m m o d q 成立。 由于p 和口是不同的素数，因此有： 聊耐兰m m o d n 成立。所以有： d ( c ) 兰c 4 兰( m 8 ) 4 兰肌鲥三m m o d n 自从r s a 密码体制诞生以来，在多个领域都得到了广泛的应用，在世界许 多的地方已成事实上的标准。 2 2 2e l g a r e a l 密码体制 1 9 8 5 年，e 1 g a m a l 基于离散对数理论提出了一种新的密码体制，被称为 e 1 g a m a l 密码体制。该密码体制不仅具有加密的功能，而且具有于数字签名的 功能。e i g a m a l 体制的安全性较强，在众多领域中得到了广泛的应用。 产生密钥对：选择一个素数p 与两个随机数g 和x ，其中g ，x p 。计算： y = g 。( m o dp ) ( 2 1 3 ) 公钥为y ，g 和p ，私钥为x 。 ( 1 ) e 1 g a m a l 在数字签名中的应用： 设需要签名的信息为m 。k 与p 一1 互素， 数。求解a ： 口= g ( m o d p ) 用扩展e u c l i d e a n 算法，求解b ： m = x a + k b ( m o d p - 1 ) 则消息m 的数字签名为 ，6 ) 。 验证签名时，验证下式是否成立： y 4 露6 ( m o d p ) = g m ( m o d p ) 同时1 g p 。 ( 2 ) e 1 g a m a l 在加密中的应用： 设需要加密的信息为m 。k 与p l 互素， 数。求解密文对( 口，6 ) ： a = g k ( m o d p ) b = y k m ( m o d p ) 解密时由下式： a 。三g 殷( m o d p ) 要a 暑掣a 毫掣g 兰m m 。d p 一，一u一 j m ，n jx胜 1 求得m ： m ：b m o d p 其中k ( 保密) 为一个随机的整 ( 2 1 4 ) ( 2 1 5 ) ( 2 1 6 ) 其中k ( 保密) 为一个随机的整 ( 2 17 ) ( 2 1 8 ) ( 2 1 9 ) 2 2 3 椭圆曲线密码体制 椭圆曲线密码体制【2 0 】f2 l 】来源于对椭圆曲线的研究。椭圆曲线是指由韦尔 斯特拉斯方程： y 2 + g x y + g ，y2 x 3 + a 2 x 2 + a 4 x + a 6( 2 2 0 ) 所确定的平面曲线。假设p 为一个无穷远点，它和方程( 2 2 0 ) 的全体解( x ，j ，) 构 成了该平面曲线的集合。其中系数q ( f _ 1 ，2 ，6 ) 定义在某个域上，如：有理数 域、实数域、复数域、有限域g f ( p ) 。 椭圆曲线密码体制中的椭圆曲线定义在有限域上。假设椭圆曲线e 上存在 一点尸，对于任意的点q ，若q = m p 成立，则如何求解整数m ，即为椭圆曲线 上的离散对数问题。椭圆曲线密码体制的安全性就是依赖于解决该问题的困难 性。在1 9 8 5 年，v ic t o rm ille r 2 0 $ 1n e a l k o b lit z 2 11 分别独立提出将椭圆曲 线应用到密码学上。 在目前公开密钥体制中，椭圆曲线密码体制是对每比特提供的加密强度最 8 高的一种体制。目前，p o ll a r d r h o 2 21 方法是求解椭圆曲线上的离散对数问题 的最好算法，其时间复杂度是完全指数时间的。而目前最好的大整数分解算法的 时间复杂度是亚指数时间的。因此，仅使用2 3 4 位椭圆曲线密钥，就可以获得与 r s a 使用2 0 4 8 位密钥时同样的安全强度。它们之间的密钥长度相差6 倍，而且 该差距与椭圆曲线密钥的增长成正比。 2 3 数字签名技术 在现实生活和工作中，很多事务都需要当事人签名，过去人们通常采用的 方法是印章、指纹和手写等等。随着计算机科学技术的不断发展，人们对互联 网的应用越来越广泛，希望利用网络的便利进行安全有效的信息传输和交易， 从而诞生了数字签名技术。 数字签名技术具有以下几个特性： ( 1 ) 可验证性。发送方的身份可以被接收方所验证。 ( 2 ) 不可否认性。发送方必须承认已发送的报文。 ( 3 ) 不可伪造性。接收方不能伪造报文。 ( 4 ) 可信第三方可以确认收发双方的信息传输，但该过程无法被伪造。 在很多领域中数字签名都得到了广泛的应用，出现了许多数字签名方案。 应用比较频繁的有群签名、代理签名、指定验证人签名和多重签名等，这些签 名方案大致可分为两类：直接数字签名和仲裁数字签名。 直接数字签名：在通信双方之间进行。我们假设接收方事先已知发送方的 公钥。( 1 ) 产生签名：发送方使用自己的私钥对整个消息或者消息的散列码进 行加密。( 2 ) 验证签名：接收方用发送方的公钥检验签名的真实性。但是，直 接数字签名方案存在一个缺陷：方案的有效性完全取决于发送方私钥的安全性。 如果发送方的私钥被窃取，窃取者就能够发送带有发送方签名的消息，并以盗 用前的任何时刻作为时间戳。如果发送方想否认某个已经发送过的签名消息， 可以声明签名的私钥丢失或者被盗，他的签名被人伪造了。 仲裁数字签名：仲裁数字签名是在签名者、签名接收者和仲裁者之间进行 的，其中仲裁者是可信第三方。( 1 ) 产生签名：签名者对消息进行数字签名， 然后发送给仲裁者。( 2 ) 验证签名：仲裁者收到了签名者发送过来的消息和数 字签名后分别对其进行验证，并加上一个验证日期和一个仲裁说明，然后把验 证过的数字签名和消息发送给签名的接收者。因为有仲裁者的存在，所以签名 者无法否认已经发送过的签名消息。 目前，r s a 签名、e 1 g a m a l 签名和椭圆曲线签名为较常用的签名方案。 2 3 1r s a 数字签名方案 ( 1 ) 生成参数与密钥 9 选取两个大素数p 和g ，计算玎= p q 。随机选取整数c ，欧拉函数为 够( 玎) = ( p 一1 ) ( q 一1 ) ，使得( c ，c o ( n ) ) = 1 成立，再计算d = c 1m o d6 p ( n ) 。其中，d 为私 钥，c 为公钥。 ( 2 ) 签名算法 设待签名的消息m 乙，计算散列码h ( m ) ，对消息m 的签名为 s = s i g ( h ( m ) ) = h ( 俄) dm o d n ( 2 。2 1 ) ( 3 ) 签名的验证算法 当签名的接收者收到签名( s ，m ) 时，按下式验证： v e r k ( h ( m ) ，s ) = l 铮( 朋) = ，m o d n ( 2 2 2 ) 该方案的安全性基于对大数分解的困难性。此方案输入散列函数( 待签名 的消息) ，输出定长的安全散列码。签名者用自己的私钥对该散列码进行加密， 产生签名，并将该签名添加在消息后。验证者收到签名后，利用消息生成散列 码，然后利用签名者的公钥验证该签名。 2 3 2e i g a m a l 数字签名方案 ( 1 ) 生成参数与密钥 选取一个大素数p ，g 是z 。乘法群的本原元，x 是用户的私钥。计算： y = g 。m o d p ( 2 2 3 ) 则公开的密钥为( p ，g ，y ) 。 ( 2 ) 签名算法 假设签名消息为m 。发送方选择随机数e ，其中e z 。，m 的散列码为日( 聊) ， 再计算下式： 1 t = 9 8 m o d p ( 2 2 4 ) s = ( 日( 聊) - x r ) e m o d ( p - 1 ) ( 2 2 5 ) 签名为s i g , ( m ，e ) = ( ，1 ij ) ，并发送( m ，( ，i is ) ) 给接收方。 ( 3 ) 签名的验证算法 接收方收到( m ，( ，| i is ) ) 后，计算出h ( m ) ，并验证下式 y 7 ，5 = g 片”m o dp ( 2 。2 6 ) 当且仅当该等式成立，数字签名有效。 该方案的安全性基于求解离散对数问题的困难性。同一个消息 i v 产生的签 名会随着随机数e 的变化而变化。 2 3 3 椭圆曲线数字签名方案 ( 1 ) 生成参数与密钥 ：有限域 e ：c 上的椭圆曲线 g ：椭圆曲线e 的基点 l o 1 1 ：g 的阶 随机选取d 【1 ，n l 】，计算q = d g 。其中q 是公钥，d 是私钥。 ( 2 ) 签名算法 待签名消息历的散列码为1 t ( m ) 。任意选取个整数c ， c g = ( x ，y ) ，= x m o d n 。计算： s = c - i ( h ( m ) + r d ) m o d n 故可得签名为：( ，s ) 。 ( 3 ) 签名的验证算法 满足1 c 疗，计算 ( 2 2 7 ) 收到( ，s ，m ) 后，接收方计算出忉的散列码h ( 历) 。再计算下式： “= s h ( m ) m o d n ，v = s - 1 r m o d n ( 2 2 8 ) ( 而，乃) = u g + v q ，= 葺m o d n ( 2 2 9 ) 签名有效当且仅当，= r t 。 事实上，若( ，s ) 是对m 的有效签名，则一定存在： c = $ - i ( 日( m ) + ，d ) = s - 1 h ( m ) + s r d = ( “+ v d ) m o d n ( 2 3 0 ) 故：( x ，y ) = c g = u g + v q = ( 而，咒) ，所以，i = 五= x = rm o d n 。 2 4 本章小结 本章首先概述了公开密钥密码体制所需要的基本数论知识，介绍了公开密 钥密码体制的产生与发展。然后深入分析了几种典型的公开密钥密码体制：如 r s a 密码体制、e i g a m a l 密码体制和椭圆曲线密码体制等。最后对几种典型的 数字签名技术进行了分析与总结。 第三章门限秘密共享方案 自从1 9 7 9 年s h a m i r 提出了秘密共享方案之后，许多学者对其进行了深入 的研究，提出了多种秘密共享的方案。本章详细介绍了经典秘密共享方案、可 验证秘密共享方案、动态秘密共享方案和多秘密共享方案。 3 1 门限秘密共享方案的基本模型 设参与者集合w = 只，) ，将秘密s 分解为n 个秘密份额：墨，s 2 ，s n ， 使得只要秘密份额的数目大于或者等于门限值t 时，就能够计算出s ；反之， 则无法计算出s 。 将n 个秘密份额分发给n 个参与者，少于t 个参与者的秘密份额组合 也不会得到关于共享秘密的任何信息，所以泄露m ( m s ) ，门限值为t ，并公布整数薯( 1 f n ) 。 ( 2 ) 秘密的分发 分发者在域f 。上任意选择t - 1 个元素，并利用这些元素来构造t 一1 次多 项式： f ( x ) = s + a l x + a 2 x 2 - i - + 口f 一1 x 卜1m o d p ( 3 1 ) 然后分发者对于五，恐，分别计算秘密份额墨= f ( x , ) m o d p ，最后将分发 给所有参与者只。 ( 3 ) 秘密的恢复 1 2 任意t 个参与者就能恢复共享的秘密，不失一般性，我们设 w = 鼻，b ，只) 为参与者的集合。t 个参与者利用他们的秘密份额构成t 个点 对( 五，而) ，( 恐，屯) ，( 一，墨) ，通过l a g r a n g e 插值运算，恢复出共享的秘密s ： 厂( x ) = 兀兰m o d p ( 3 2 ) i = 1 = l 。j ，“f“ 其中s = f ( o ) 。 由多项式( 3 1 ) 可知，未知系数为q ，a 2 ，q 小s ，因此任意t 个或者t 个以 上的份额就能解出未知系数，即恢复秘密s 。如果份额数少于t 个，则无法恢 复秘密s 。 例如：构造( 3 ，5 ) 门限秘密共享方案，设共享的秘密s = 1 0 ，p = 2 3 。在 域e ，中随机选取一个二次方程： f ( x ) = l o + 8 x + 6 x 2 m o d 2 3 ( 3 3 ) 5 个秘密份额一次如下： s = 厂( 1 ) = 1 0 + 8 + 6 三l ( m o d 2 3 ) = f ( 2 ) = 1 0 + 1 6 + 2 4 兰4 ( r o o d 2 3 ) s 3 = 厂( 3 ) = 1 0 + 2 4 + 5 4 兰1 9 ( m o d 2 3 ) s 4 = f ( 4 ) = 1 0 + 3 2 + 9 6 置o ( m o d 2 3 ) = 厂( 5 ) = 1 0 + 4 0 + 1 5 0 量1 6 ( m o d 2 3 ) 若使用秘密份额是，& ，黾来恢复秘密s ， l a g r a n g e 插值运算，即求解方程组3 5 ： 口1x 2 + a 2x 2 2 + s = 4 ( m o d 2 3 ) a ix 4 + a 2x 4 2 + s = o ( m o d 2 3 ) 口1x5 + a 2x5 2 + s = 1 6 ( m o d2 3 ) ( 3 4 ) 则利用点( 2 ，1 7 ) ，( 4 ，o ) ，( 5 ，1 6 ) 进行 解得：a l = 8 ，a 2 = 6 ，s = 1 0 。则共享的秘密被恢复。 ( 3 5 ) 3 2 2b r i c k e l l 向量空间秘密共享方案 设w = 眉，最，e ) 为r 1 个参与者的集合，r 是w 的子集的集合，我们 把称r 为访问结构当且仅当所有在r 中的子集都可以计算出秘密s 的参 与者的子集，其中，1 1 中的子集称为授权子集。 假设d 萑p 是可信赖的中心机构。d 选取一个大素数q ，k