（计算机应用技术专业论文）动态多秘密共享的研究.pdf

动态多秘密共享的研究 摘要 秘密共享是密码学的一个重要组成部分，为密钥管理提供了一个崭新的思 路，在密钥的安全保存、传输以及合法利用中起到了关键的作用。利用秘密共 享来保管秘密信息，一方面有利于防止权利过分集中而遭到滥用，另一方面保 证秘密的安全性和完整性。因此，秘密共享的研究不仅有重要的理论意义，而 且具有广泛的应用前景。 本文首先介绍了门限秘密共享的产生、发展和研究现状，然后详细的讨论 了可验证秘密共享方案、动态秘密共享方案和多秘密共享方案，分析了这些方 案中存在的问题，提出了一个新的动态多秘密共享方案。该方案具有以下特点： ( 1 ) 参与者可以自主选择子密钥，可信中心得到的只是参与者子密钥的影 子，由子密钥的影子得到子密钥在计算上是不可行的。 ( 2 ) 子密钥更新份额由可信中心和参与者共同决定，任一方子密钥更新份额 泄露，都不会影响方案的安全性。更新过程中参与者之间不需要进行交互，减 少了数据的传输量。 ( 3 ) 方案采用了椭圆曲线密码体制，相对于r s a 密码体制和e 1 g a m a l 密码 体制，椭圆曲线密码体制可以使用较短的密钥达到同样的安全性，进一步的提 高了方案的安全性和效率。 本文在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 ho fd y n a m i cm u l t i s e c r e ts h a r i n g a b s t r a c t s e c r e ts h a r i n gi sa ni m p o r t a n tc o m p o n e n to fc r y p t o g r a p h y , i tp r o v i d e san e w i d e af o rs e c r e tm a n a g e m e n t ，a n dp l a y sai m p o r t a n tr o l ea t s e c r e tp r e s e r v a t i o n t r a n s m i s s i o na n du t i l i z i n g l e g a l l y s e c r e ts h a r i n g i su s e df o rs a v i n gs e c r e t i n f o r m a t i o n ，o nt h eo n eh a n d ，i th a sr i g h tt op r e v e n to v e r c o n c e n t r a t i o na n da b u s e ，o n t h eo t h e rh a n d ，i tg u a r a n t e e st h es e c u r i t ya n di n t e g r i t yo fs e c r e t t h e r e f o r e ，r e s e a r c h o fs e c r e ts h a r i n gn o to n l yh a si m p o r t a n tt h e o r e t i c a ls i g n i f i c a n c e ，b u ta l s oh a sb r o a d a p p l i c a t i o np r o s p e c t s f i r s t l y , t h i sd i s s e r t a t i o ni n t r o d u c e se m e r g e n c e ，d e v e l o p m e n t a n dr e s e a r c ho f s e c r e t s h a r i n g ，a n d t h e nd e t a i l e dd i s c u s s i o no ft h ev e r i f i a b l e s e c r e t s h a r i n g s c h e m e ，d y n a m i cs e c r e ts h a r i n ga n dm u l t i - s e c r e ts h a r i n gs c h e m e ，p r o b l e m si sf o u n d i nt h e s es c h e m e i nr e s p o n s et ot h e s ep r o b l e m s ，an e wd y a n m i em u l t i - s e c r e ts h a r i n g i sp r o p o s e d t h e r ea r es o m ef e a t u r e si no u rs c h e m ea sf o l l o w ： ( 1 ) p a r t i c i p a n t c a nc h o o s es u b s e c r e t s ，t r u s tc e n t e rr e c e i v e s as h a d o wo f s u b 。s e c r e t s i ti sn o tf e a s i b l ef r o ms h a d o wo fs u b s e c r e t st o s u b - s e c r e t si n c a l c u l a t i o n ( 2 ) u p d a t i n gs h a r eo fs u b - s e c r e t s i s c o m p o i s e db yp a r t i c i p a n t a n dt r u s t c e n t e r ，e i t h e ro fu p d a t i n gs h a r ei sl e a k e d ，s e c u r i t yo fs c h e m ew i l l n o tb ea f f e c t e d p a r t i c i p a n t sn e e dn o tt oi n t e r a c ta tu p d a t e i n gs t a g e ，v o l u m eo fd a t at r a n s m i s s i o ni s r e d u c e d ( 3 ) t h es c h e m eb a s e so ne l l i p i t ec u r v ec r y p t o s y s t e m ，e c ct h a t i sc o m p a r e d w i t ht h er s aa n de l g a m a lc r y p t o s y s t e m ，w h i c hc a n u s es h o r t e rk e y st oa c h i e v et h e s a m es e c u r i t y , s os e c u r i t ya n de f f i c i e n c yi sf u r t h e re n h a n c e d t h ed i s s e r t a t i o nu s ev c + + 6 0a n dm i r a c ll i b r a r yt od e s i g nap r o t o t y p es y s t e m i nw i n d o w sx p , i ti sd e t a i l e d l yi n t r o d u c e df o rc o m p o n e n to fp r o t o t y p es y s t e ma n d t h ee x p e r i m e n t a lr e s u l t s t h er e s u l ts h o w st h a ts c h e m ei sf e a s i b i l i t ya n dr i g h t k e y w o r d ：m u l t i - s e c r e ts h a r i n g ；l a g r a n g ei n t e r p o l a t i o n ；e c c 插图清单 图5 1 系统模型3 5 图5 2 公告板3 6 图5 3 参与者初始化：3 6 图5 4 秘密共享的设置3 7 图5 5 可信中心选择恢复的秘密和参与者4 0 图5 6 秘密的恢复4 0 图5 7 可信中心定期更新4 1 图5 8 参与者定期更新4 l 图5 9 子密钥更新后秘密的恢复4 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 金目曼至些太堂或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：厢寻肜 签字日期：2 呻，3 ，弓i 学位论文版权使用授权书 本学位论文作者完全了解金a 巴王些太堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金目旦王些太堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名凋伤 签字日期：工们产乡弓) 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 导师签名： 俨移也 辩醐：h ； 致谢 三年的研究生生活即将结束，回首这段时间，有许多人在生活上和学习上 都给我了极大的帮助，自己在能力上和专业知识上都有一定程度的增长。首先 要特别感谢的是我的导师侯整风教授，侯老师在学术上给予了我悉心的指导， 使我对计算机密码学几乎一无所知到掌握了密码学相关的基本方案协议，以及 基本的研究方法和手段。在课题的研究和论文的撰写过程中给我提出了宝贵的 意见。他为人正直、渊博的知识、热爱教育事业、一丝不苟的治学态度和废寝 忘食的工作热情为我树立了榜样，对我产生了深深的影响，不断的激励着我孜 孜不倦的学习和工作。 感谢网络与信息安全实验室的所有同学。在几年的学习和生活中，我们相 互帮助，建立了很好的关系。感谢他们对我无私的帮助。同时，我还要感谢家 人，他们的支持是我前进的动力。 最后感谢所有关心和帮助过我的人。 作者：周伟 2 0 0 9 年3 月 第一章绪论 1 1 研究的背景和意义 在当今高度信息化和数字化的社会里，利用互联网进行信息的交换和资源 的共享成为信息社会的一个重要特征。计算机网络给人们带来便利的同时也带 来了安全性的问题。如何保持信息秘密性、确定信息的完整性和不可否认性， 成为人们关心和重视的问题。因此，信息安全成为信息科学领域的热点研究课 题。 密码学为解决信息安全的问题提供了许多实用技术，如数字加密技术、数 字签名技术和身份证明技术等。然而，这些技术的安全性都是依赖于密钥的安 全性，一旦密钥被窃取、丢失或者损坏，不但合法的用户无法获取信息，而且 非法的用户可能窃取信息。因此，密钥管理是信息安全与保密的关键。 门限秘密共享是密码学的一个重要组成部分，为密钥管理提供了一个崭新 的思路，在密钥的安全保存、传输以及合法利用中起到了关键的作用。门限秘 密共享的基本思想是将秘密信息分解为多个秘密份额，并且将秘密份额分发给 多个参与者，只要合法的参与者数量达到门限值，就可以利用他们的秘密份额 恢复出秘密信息。利用门限秘密共享来保管秘密信息，一方面有利于防止权利 过分集中而遭到滥用，另一方面保证了秘密的安全性和完整性。当有些秘密份 额由于人为因素或者自然灾害而遭到损坏时，其他秘密份额的拥有者仍可以恢 复出秘密信息。因此，利用秘密共享保护秘密信息不仅有重要的理论意义，而 且具有广泛的应用前景。 在实际应用过程中，可能需要一次共享多个秘密。如果按照传统的秘密共 享的方法，各参与者需要保存多个秘密份额，这样做的效率很低。而且当需要 共享一个新的秘密时，需要重新分发，这在时间和资源上都是一个价值相当高 的过程。因此，多秘密共享应运而生，其主要思想是分发中心只需要一次分发 过程和参与者保存一份秘密份额，就可以完成对多个秘密的共享。拓展了秘密 共享的应用，提高了秘密共享的效率。秘密共享虽然得到了大量的研究，但是 仍然有一些有待解决的问题。如移动敌手攻击的问题、防欺骗问题等。 1 2 门限秘密共享研究现状 门限秘密共享的概念最早由s h a m i r 1 】和b l a k l e y 2 】分别提出的，并给出了秘 密共享的原型，s h a m i r 方案的思想是基于拉格朗日插值来实现的，b l a k l e y 方 案是矢量性质建立的。随后许多学者对门限秘密共享进行深入的研究，提出了 多种类型的秘密共享方案。k a m i n 4 】提出了矩阵法构造门限秘密共享方案。 b e n a l o h l 5 于1 9 8 6 年提出了同态秘密共享的概念。a s m u t h 和b l o o m 6 】等对基于 中国剩余定理的门限秘密共享方案进行了研究。c h o r 7 】等人提出了可验证秘密 共享方案，但是该方案在验证阶段需要进行大量的交互，因而效率很低。 f e l d m a n 8 】提出了一个非交互可验证秘密共享方案，该方案基于求解普通离散对 数的困难性。p e d e r s e n 9 】【1 0 】提出了一个无条件安全的非交互可验证秘密共享方 案。这两个方案在验证时不需要交互，提高了方案的效率。文献 3 9 详细的分 析了现有防欺骗秘密共享的缺陷。 h e 3 】等人提出了一个基于单向函数的门限多级秘密共享方案，但是秘密的 恢复必须严格的按照预先规定的顺序进行。后来对方案进行了改进，取消了秘 密的恢复按照预先规定的顺序进行，提出了一个真正意义上的门限多秘密共享 方案【2 7 】( m u l t i s e c r e ts h a r i n g ，m s s ) 。h a m 1 1 】等人提出了一个基于单向函数可 验证多秘密共享方案。c h i e n 1 2 1 等人基于系统分组码提出了一种多秘密共享方 案，在这个体制中多个秘密可以在一次秘密重构过程中并行计算得到。 p a n g w a n g ”】对c h i e n 的方案进行了改进，减少了秘密恢复的计算量。l i n w u p 州 提出了一个可验证的多秘密共享方案，该方案基于大数因子分解和离散对数的 难解性。文献 3 5 对l i n w u 的方案进行了改进，提高了方案的安全性。 o s t r o v s k yr y u n gm 【1 4 】第一次提出了移动敌手的模型和动态安全的 概念。h e r z b e r ga t j 具体化了一个动态秘密共享( p r o a c t i v e ss e c r e ts h a r i n g ) 的概念，给出了一个动态秘密共享方案，该方案的更新过程需要参与者之间的 大量交互才能完成。许春香【2 3 】等人提出了一种定期更新防欺诈的秘密共享方 案，在该方案中参与者的更新份额由分发中心产生，减少了数据的传输量，提 高了效率。v e n t z i s l a v 4 7 】对动态秘密共享进行了详细的研究。 1 3 课题研究的内容，解决的问题 1 3 1 研究内容 本文介绍了经典的门限秘密共享方案，重点研究了动态秘密共享和多秘密 共享。在分析和研究前人研究成果的基础上，提出了一种动态多秘密共享方案。 论文的主要工作如下： ( 1 ) 研究了经典门限秘密共享方案，如s h a m i r 门限秘密共享方案、f e l d m a n 可验证秘密共享方案、h e r z b e r g 动态秘密共享方案和p a n gf - j 限多秘密共享 方案等； ( 2 ) 提出了一个动态多秘密共享方案，有效地防止了更新份额泄露可能出现 的安全性问题，并对方案进行了详细的分析； ( 3 ) 实现动态多秘密共享的原型系统，验证方案的正确性和可行性。 1 3 2 解决的关键问题 ( 1 ) 大数运算问题 通过m i r a c l 大数库来实现大数运算。 2 ( 2 ) 如何防止更新份额泄露可能出现的安全性问题 分析和研究前人的研究成果，提出自己的方案。该方案通过将更新份额由 参与者和可信中心共同决定，有效地防止了更新份额泄露可能出现的安全性问 题，从而提高了方案的安全性。 ( 3 ) 如何验证方案的正确性与可行性 对方案进行理论证明和分析，结合实验来证明方案的正确性与可行性。 1 4 本论文的组织结构 本论文的组织结构如下： 第一章绪论。阐述了课题研究的背景和意义、研究现状、研究的主要内 容、解决的关键问题。 第二章经典密码技术。介绍了经典密码技术的主要内容。 第三章门限秘密共享的研究。介绍了门限秘密共享的基本思想，对现有 典型的门限秘密共享方案进行了详细的阐述和研究。 第四章动态多秘密共享方案。提出了新的动态多秘密共享方案，并对方 案进行了分析。 第五章原型系统的实现。详细的介绍原型系统的各个组成部分，对方案 的可行性和正确性进行了验证。 第六章总结与展望。 3 第二章经典密码技术 目前公钥密码体制主要有r s a 公钥密码体制、e 1 g a m a l 公钥密码体制和椭 圆曲线公钥密码体制。数字签名技术是基于公钥密码体制的，r s a 签名、 e 1 g a m a l 签名和椭圆曲线签名是最常用的数字签名技术。数论是设计公钥密码 体制的基础。 2 1 数论知识 密码学是一门典型的交叉学科，近代密码学中的大部分密码协议都建立在 严密的数学理论基础上。数论是设计公开密钥密码算法的基础。 2 1 1 有限域 定义2 1 有限域f 算术运算的有效实现是实现密码学的重要条件，因为密 码学技术的运算都是基于有限域上的算术运算。域是有一个集合f 和两种运算 组成，这两种运算分别为加法( 用”+ ”表示) 和乘法( 用” 表示) ，并且运算满足 下列特性： ( 1 ) f 中的元素对于加法运算”+ ”构成加法交换群，且具有单位元( 单位元用 0 表示) 。8 的逆元为a ： ( 2 ) f 中的非零元素对于乘法运算” 构成乘法交换群，且具有单位元( 单位 元用1 表示) 。a 的逆元为8 一： ( 3 ) 分配律成立：对于v a ，b ，c f ： ( a4 - b )木c = a 冰c4 - b ，i cc c ，i ：( a + b ) = c 水a + c ，i cb 成立。 定义减法为：8 一b = a4 - ( - b ) 。 定义除法为：8 b = f l ，i cb ，其中b 。1 为b 的逆元。 如果集合f 中元素的个数是有限的，则称为有限域或者伽罗瓦域。反之称 为无限域。 有限域元素的个数称为有限域的阶。存在一个q 阶有限域f ，当且仅当q 是一个素数的幂，即q = p m ，其中p 是一个素数并称为域f 的特征，m 是一个整 数。若m = l ，则域f 就称为素域。若m = 2 ，则域f 就称为扩域。对于任意的一 个素数幂q ，本质上只存在一个q 阶有限域。这意味着，任意两个q 阶有限域 除了域元素的表示符号不同外，在结构上它们是相同的。我们称任意两个q 阶 有限域都同构，用f 口或者g f ( q ) 表示。 4 2 1 2 有限域中的运算 2 1 2 1 整数有限域 整数集合 o ，1 ，2 ，p 1 ) 按照通常的加法( 减法) ，乘法( 除法) 代数运算在模 p 的意义下构成一个整数有限域f p ，即( 减法和除法可以转化为加法和乘法) ： 加法：如果a ，b f p ，则a + b - - - - rr o o dp ，r f p ； 乘法：如果1 3 ，b f p ，则a 木b 量sr o o dp ，s f p 。 令f p + 表示f p 中所有的非零元素集合，可以证明f p 至少存在一个元素g ， 使得f p 中的任意非零元素都可以表示成g 的某次方幂的形势，这样的元素g 称 为f p 的生成元( 或者本原元) 。 2 1 2 2 多项式有限域 域f 。中的元素是次数最多为m 一1 次的多项式( 多项式系数取自f p = 0 ，1 ， 2 ，p - 1 ) ) ： f d 。= a m - 1 工朋- 1 + 口m 一2 z “一2 + + 口l x + 口o ，口f f p 。 f n 。中的加法：多项式a ，b f n 。，且a = a m _ 1 x ”1 + a m _ 2 x ”2 + + a l x + a o ， b = 屯- l 石朋_ 1 + k 一2 z “一2 + + b l x + b o ， c = a + b = c r n _ 1 x “- 1 + c 肘一2 x 脚一2 + + c l x + c o ( 2 1 ) 其中c f = a f + 玩m o d p ，0 i m 一1 。 f n 。中的乘法：多项式a ，b f 口。，a 与b 的乘积与一般多项式的乘积相同， 其差别是，如果积的指数等于或者比m 大，必须用不可约多项式f ( x ) 去除，则 c = a 木bm o d “x ) 。 2 1 3 模及同余的运算 定义2 2 模运算若a ，b 为整数，存在a 除以b 的整数q ( 商) 和r ( 余数) ， 使得： a = q b + r ，其中0 r b 而且q 和r 唯一。这里做除法所得的余数记为ar o o db ( r = ar o o db ) ，商记为ad i v b ( q = ad i vb ) ，b 叫做模，r = am o db 这种运算称为模运算。 模运算的性质对于任意的整数i t , ，b ，n ，其中1 3 为模，有： ( 1 ) ( a b ) m o dn = ( a r o o dn ) ( br o o dn ) r o o d1 1 车争( ar o o dn ) ( b r o o dn ) r o o d1 3 = ( a b ) r o o d1 1 ； ( 2 ) ( a 水b ) m o d1 1 = ( ar o o dr 1 ) 术( br o o dn ) r o o dn ( ar o o d1 1 ) 幸( br o o dn ) r o o dn = ( a ，i cb ) r o o d1 1 ； ( 3 ) ( a 木( b + c ) ) r o o d1 1 = ( ( a 木br o o dn ) + ( a 水cr o o dn ) ) r o o dn ，( ( a 水b r o o dn )+ ( a 冰cm o dn ) ) m o dn=( a 串( b + c ) ) r o o d1 3 , 定义2 3 同余a ，b ，1 1 为整数且n 0 ，则称a 与b 是模1 1 同余的，当且仅 当1 1 整除( a b ) ，既是a b = k n ，其中k 为任意整数。若a 与b 是模n 同余的， 5 我们记为a - br o o dn ，整数n 称此同余的模。 同余的性质对于v 整数a ，b ，c ，d 有： ( 1 ) a 善br o o d1 3 当且仅当a 与b 被n 除时所得的余数相同； ( 2 ) ( 自反性) a 兰ar o o d1 1 ； ( 3 ) ( 对称性) 若a - br o o dn ，则b 羞ar o o dn ； ( 4 ) ( 传递性) 若a - br o o dn ，b - - - - cr o o d1 3 ，则a - - - - - cr o o dn ； ( 5 ) 若a - = br o o dn ，c - dr o o dn ，贝i ja + c 暑( b + d ) m o dn ，且a c - b dr o o d1 1 。 定理2 1 中国剩余定理若，l ，拧：，, 。是两两互素的，对于任意的整数 a l ，a 2 ，a t ，则同余方程组： x 三a lr o o d n l z 兰口2m o d ，1 2 ( 2 2 ) ： z 暑口七r o o d n i 对于模n = 确1 2 n i 有唯一解。 2 1 4 乘法逆元的求法 定义2 4 欧拉函数对于n 1 ，令伊( n ) 表示 1 ，n 内与i i 互素的整数个数。函 数p 称为欧拉函数。 欧拉函数的性质： ( 1 ) 若p 是素数，则缈( p ) = p 一1 ； ( 2 ) 欧拉函数是乘性的，即若g c d ( m ，1 3 ) = 1 ， ( 3 ) 若n = 绅p ；2 p 是n 的素因子分解，则 伊c n ，= n ( ，一吉 ( 一去 ( t 一去 则p = 妒( m ) 木缈( n ) 5 定理2 2 欧拉定理若a 和n 互素，则a 9 ( n ) 富1m o dn 。 定义2 5 已知m 1 ，( a ，n ) = 1 ，则存在c 使得c a - - 1 为a 对模1 3 的逆，记为a 。求逆元常用的有两种方法： 方法一：如果p ( n ) 已知，有欧拉定理可知 a 木a 伊( n ) 1 兰1m o dn j a 1 兰a 妒( n ) 1m o d1 3 ( 2 3 ) m o dn ，我们把c 称 方案二：利用扩展的欧几里德算法找到整数x 和y 使得a x + m y = 1 ， a 三xm o dn 。 ( 2 4 ) 这样 2 2 对称密码体制 对称密码体制是密码学的重要组成部分，是一种加密密钥和解密密钥相同 或者很容易相互推导出的密码体制。该体制的特点是发送者和接收者之间的密 钥必须安全传送，双方所用的通信密钥必须安全的保管，从而确保通信数据的 秘密性，而且运算的速度比较快，效率比较高。其安全性依赖于加密算法的强 6 度和密钥的安全性。目前，最著名的对称密码算法是d e s t 3 7 】【3 8 1 算法和a e s 算 法。 对称密码体制存在的缺点： ( 1 ) 密钥分发问题。即要求分发密钥既是保密的又是保真的。 ( 2 ) 密钥管理问题。使用对称密钥密码体制进行通信时，任意不同的两个用 户都应该使用互不相同的密钥。如果一个网络中有n 个用户，每个用户都必须 保存其它n 1 个用户的密钥，这时网络中一共需要n ( n 1 ) 2 个密钥。在用户 数量不是很大的情况下，对称密码体制是比较有效的，但对于大型网络实体数 量大、分布很广时密钥的分配和存储就会成为很大的困难。 ( 3 ) 消息确认问题。由于两个或者更多的实体共享密钥，所以对称密码体制 不能实现用于不可否认服务的数字签名，这是因为无法区分共享密钥的不同实 体的行为。 2 3 公钥密码体制 1 9 7 6 年d i f f i e 和h e l l m a n 【1 6 】在 密码学新方向一文中首次提出了公开密 钥密码体制( 简称公开密码体制或者公钥体制) 的思想，它是密码学上的一次重 要飞跃，开创了密码学的新纪元。公钥密码体制克服了对称密码体制的缺点， 不仅完成了加密和解密的功能，而且还具有数字签名、认证、鉴别等功能。它 的出现是密码学研究领域中的一项重大突破，为近代密码学的发展指明了方向。 公开密码体制又称为非对称密码体制。公钥密码体制用到两个不同的密钥： 一个是公开的( 公钥) ，另一个是秘密的( 私钥) 。由公钥得到私钥在计算上是不 可行的，用户的公钥是公开的，私钥保密。公钥密码体制可以适用于网络的开 放性要求，与对称密码体制相比，密钥管理要简单的多。由于公钥密码体制在 加密和解密时使用的是不同的密钥，即加密功能和解密功能分开，可以实现由 一个用户加密的消息能由多个用户解密；或者由多个用户加密的消息只能由一 个用户解密。前者应用在认证系统中，实现了数字签名；后者应用在网络中实 现了保密通信。 自从公钥密码体制的思想提出来，已经出现了许多公钥密码体制。如基于 大整数因子分解问题的r s a 体制和r a b i n 体制，基于有限域上的离散对数问题 的d i m e h e l l m a n 体制和e 1 g a m a 体制，基于背包问题的m e r k l e h e l l m a n 体制 和c h o r r i v e s t 体制等等。目前比较流行的公钥密码体制主要有两类：一类是基 于大整数因子分解问题的，其中最典型代表是r s a 公钥密码体制。另一类是基 于离散对数问题的，如e 1 g a m a l 公钥密码体制和影响比较大的椭圆曲线公钥密 码体制。 目前常用的公钥密码算法都是基于以下的数学难题之一的： ( 1 ) 大整数因子分解问题：给定一个大整数n 为两个大素数的乘积，确定这 两个素因子，即求解大素数p 和q 使得：p x q = n 。 ( 2 ) 离散对数问题：p 是素数，给定整数g ，求解x 使得：9 1 - am o dp 。 ( 3 ) 椭圆曲线离散对数问题：给定椭圆曲线e 上的一个点g ，对于任意的 点p ，如果存在整数m 使得p - - r a g ，求解出m 。 2 3 1r s a 密码体制 1 9 7 8 年r i v e s t ，s h a m i r 和a d l e m a n 【1 7 1 提出了第一个有效的公钥密码体制， 称为r s a 公钥密码体制。它是使用最广泛的公钥密码体制，可用来提供数据的 保密性和数字签名。该密码体制的安全性基于大数因子分解问题的困难性，基 础是欧拉定理( 见定理2 2 ) ，体制中的运算在z n ( z n 是一个有n 个元素的有限域， 其中z n = 0 ，l ，2 ，1 1 1 ) ) 中进行。 r s a 密码体制的加密和解密： ( 1 ) 密钥生成 首先随机生成两个不同且大小相近的大素数p 和q ，计算n = p q ( 公开) ，其 欧拉函数值是： 伊( n ) = ( p - 1 ) ( q 1 ) ( 保密) ( 2 5 ) 然后随机选取整数e ( 公开) ，满足g c d ( e ，9 ( n ) ) = 1 ，并计算： d = e o m o d q ，( n ) ( 保密) ( 2 6 ) 则公钥为( e ，n ) ，私钥是d 。 ( 2 ) 加密运算 将要加密的消息按n 的比特长度分组，依次对每个分组m 做一次加密，所 有分组的密文构成的序列既是原始消息的加密结果。明文m 满足0 m n ；则 加密算法为： c = e ( m ) - - m 。m o dn( 2 7 ) c 为密文，且0 c n 。 ( 3 ) 解密运算 解密算法为： m = d ( c ) - - - - c dm o dn ( 2 8 ) 下面证明解密过程是正确的： 证明：d ( c ) - - c d - - - ( m 。) d = m e d - mm o dn ( 2 9 ) 因为 e d - 1 m o d f o ( n )e d = r c p ( n ) + 1 ，( 其中r 为整数) ( 2 1 0 ) 如果( m ，p ) = 1 ，有f e r m a t 定理可知： m ( p - 1 ) 三l m o dp ( 2 “) 等式( 2 1 1 ) 两边同时取r ( q 1 ) 次方，然后两边乘以m 得： m 1 + 。( p 1 ) ( q 1 ) - - mm o dp( 2 1 2 ) 如果( m ，p ) = p ，则等式( 2 1 2 ) 两边模p 都为零，因此等式成立。因此， m e d - - mm o d p ( 2 1 3 ) 总成立。 同理，m 酣- mm o dp 成立。 由于p 和q 是不同的素数，因此， m e d - = mm o dn( 2 1 4 ) 成立。所以有 d ( c ) - - - - c d 暑( m e ) d - m 。d - mr o o d1 1 r s a 密码体制在美国和加拿大都已经申请专利，一些标准组织已经撰写了 或正在撰写标准，标准规范了r s a 密码体制在加密、数字签名和密钥建立中的 使用。 2 3 2e 1 g a m a l 密码体制 e 1 g a m a l 公钥密码体制是由e 1 g a m a l 在1 9 8 5 年提出的，是一种基于离散对 数的公钥密码体制。该密码体制即可用于加密，又可用于数字签名。e 1 g a m a l 体制有较好的安全性，得到了广泛的应用。著名的美国数字签名标准d s s 采用 了e 1 g a m a l 签名方案。 e 1 g a m a l 密码体制的加密和解密： ( 1 ) 密钥生成 首先随机选取一个大素数p ，且要求p 1 有大素数因子。g z p ( z p 是一个 有p 个元素的有限域，z p + 是z p 中的非零元构成的乘法群) 是一个本原元。然后 选择一个随机数k ( 1 - - k 是由g 生成的椭圆曲线的循环子群。 椭圆曲线上的循环子群的运算规则如下： ( 1 ) 对于所有的p e ( f 口) ，p + = o o + p = p ，其中o 。为单位元； ( 2 ) 如果p = ( x ，y ) e ( f p ) 则( x ，y ) + ( x , - y ) = ，记点( x ，一y ) 为- p ，并称其为p 的负，其中p e ( f p ) ； ( 3 ) 如果p = ( 而，y 1 ) e ( f p ) ，q = ( x 2 ，y 2 ) e ( f p ) ，且p q ，则p + q = ( 而，y 3 ) ； 矿( 嚣卜吨m o a p 胪( 嚣卜咄m o a p 铲( 警 2 - 2 侧p 胪( 等卜咄m 。d p ( 2 2 0 ) ( 2 2 1 ) 则2 p = ( x 3y 3 ) 。其中： ( 2 2 2 ) ( 2 2 3 ) 例如：设p = 2 9 ，a = 4 ，b = 2 0 。素域f 2 9 上的上的椭圆曲线： e ：y 2 = x 3 + 4 x + 2 0 ( 2 2 4 ) 由于= 一1 6 ( 4 a 3 + 2 7 b 2 ) = 一1 7 6 8 9 6 考0 r o o d 2 9 ，所以e 为椭圆曲线。椭圆曲 线e ( f p ) 上的点如下： 1 0 ( 2 , 6 ) ( 4 ，1 9 ) ( 8 ，1 0 ) ( 1 3 ，2 3 ) ( 1 6 ，2 ) ( 1 9 ，1 6 ) ( 2 7 ，2 ) ( 0 ，7 ) ( 2 ，2 3 ) ( 5 ，7 ) ( 8 ，1 9 ) ( 1 4 ，6 ) ( 1 6 ，2 7 ) ( 2 0 ，3 ) ( 2 7 ，2 7 ) ( 0 ，2 2 ) ( 3 ，1 ) ( 5 ，2 2 ) ( 1 0 ，4 ) ( 1 4 ，2 3 ) ( 1 7 ，1 0 ) ( 2 0 ，2 6 ) ( 1 ，5 ) ( 3 ，2 8 ) ( 6 ，1 2 ) ( 1 0 ，2 5 ) ( 1 5 ，2 ) ( 1 7 ，1 9 ) ( 2 4 ，7 ) ( 1 ，2 4 ) ( 4 ，1 0 ) ( 6 ，1 7 ) ( 1 3 ，6 ) ( 1 5 ，2 7 ) ( 1 9 ，1 3 ) ( 2 4 ，2 2 ) 设p = ( 5 ，2 2 ) ，q = ( 1 6 ，2 7 ) 。 点加：r = p + q = ( 1 3 ，6 ) 。 点乘：r = 2 p = ( 1 4 ，6 ) 。 椭圆曲线密码体制的加密和解密： ( 1 ) 密钥的生成 首先在区间 1 ，n 1 】随机选择一个正整数d ，然后计算q = d g 。则私钥为d ， 公钥为q 。 ( 2 ) 加密运算 把待加密的明文m 表示成椭圆曲线上的一个点m ， 计算： e l = k g ，c 2 = m + k q 则密文为( c l ，c 2 ) 。 ( 3 ) 解密运算 收到密文( t h e 2 ) 后，计算： 随机选取k e 1 , n - 1 ， ( 2 2 5 ) m - c 2 一d c l ( 2 2 6 ) 并从点m 提取出明文m 。 椭圆曲线密码体制具有安全性是目前公钥密码体制中，对每个比特提供的 加密强度最高的一种体制，具有安全性高、密钥量小、灵活性好等特点。研究 证明，椭圆曲线密码体制使用1 6 0 比特的密钥提供的安全性相当于r s a 和d s a 使用1 0 2 4 比特密钥使用的安全性。而且在签名和解密方面要比d s a 和r s a 快 的多，此差距会随着椭圆曲线密码体制密钥的长度的增加而变得更大。人们对 椭圆曲线密码体制的安全性和实现方法进行了大量的研究，在理论上和实践上 都取得了重大的进展，许多标准化组织已经或正在制定有关椭圆曲线密码标准。 2 4 数字签名技术 在实际的工作和生活中，许多事务的处理都需要当事人签名，传统上都是 采用手写签名。签名起到认证、核准、有效和负责等作用。随着计算机网络技 术的发展，人们越来越希望通过网络进行安全有效的数据传输和交易，数字签 名应运而生。数字签名是电子信息发展的产物，是针对电子文档的一种签名确 认方法，所要达到的目的是对数字对象的合法性、真实性进行标记，并提供签 名者的承诺。 数字签名具有以下特征： ( 1 ) 可验证性：接收方能够验证发送方的签名是否真实有效； ( 2 ) 不可伪造性：除了签名人外，任何人都不能伪造签名人的合法签名； ( 3 ) 不可否认性：发送方不能否认他所签名的消息； ( 4 ) 数据完整性：数字签名能够提供对签名人所签署消息的完整性检验。 目前已经出现了许多数字签名方案，如群签名、代理签名、指定验证人签 名和多重签名等，它们大致可分为两类：直接数字签名和仲裁数字签名。 直接数字签名：直接数字签名在签名者和接收者之间进行的。假设签名的 接收者知道签名者的公钥，签名者用自己的私钥对整个消息或消息的散列码进 行数字签名，签名接收者用签名者的公钥对签名进行验证，从而确认数字签名 和消息的真实性。另外，可以通过对整个消息和数字签名进行加密来实现消息 和数字签名的机密性。加密的密钥可以是接收者的公钥，也可以是双方共享的 密钥。 仲裁数字签名：仲裁数字签名是在签名者、签名接收者和仲裁者之间进行 的。仲裁者是签名者和签名接收者共同信任的，签名者首先对消息进行数字签 名，然后送给仲裁者。仲裁者首先对签名者送来的消息和数字签名进行验证， 并对验证过的消息和数字签名附加一个验证日期和一个仲裁说明，然后把验证 过的数字签名和消息发给签名的接收者。因为有仲裁者的验证，所以签名者无 法否认仲裁者验证过的数字签名。 目前常用的数字签名方案有r s a 签名，e 1 g a m a l 签名，椭圆曲线签名。 2 4 1r s a 数字签名方案 ( 1 ) 参数与密钥生成 选取两个大素数p 和q ，计算n = p q ，其欧拉函数为伊( n ) = ( p - 1 ) ( q 一1 ) 。随 机选取e ，使( e ，伊( n ) ) = 1 ，计算d = e 。m o d9 ( n ) 。d 为私钥，e 为公钥。 ( 2 ) 签名算法 设待签名消息m z n ，对消息m 的签名为 s = s i