（计算机软件与理论专业论文）先应秘密共享方案的研究与实现.pdf

先应秘密共享方案的研究与实现 摘要 随着计算机网络技术的迅速发展和普及，信息成为社会发展的重要战略资源，信 息安全问题己成为世人关注的社会问题。门限秘密共享是实现信息安全和数据保密的 重要手段，先应秘密共享在不改变共享秘密的情况下，通过周期性更新秘密份额来保 证门限秘密共享系统的安全性和鲁棒性。 本文阐述了密码学的相关知识，介绍了门限秘密共享的基本原理，重点分析了可 验证秘密共享方案、无可信中心方案、先应秘密共享等几种典型方案。针对这些方 案中存在的问题和不足，提出了一种新的先应秘密共享方案。该方案具有以下特点： 1 采用无可信中心的秘密共享形式，避免了可信中心的权威欺骗。同时能 够验证成员的秘密份额，发现攻击者和不诚实的成员，提高了系统的安全性； 2 为了防止移动攻击造成的秘密份额的泄漏或损坏，方案定期更新所有成员的 秘密份额，使得攻击者在前一个周期获得的秘密份额完全失效，提高了系统的 鲁棒性； 3 通过部分更新秘密份额删除被腐蚀的成员和增加新的成员，提高了系统 的可用性。 最后在w i n d o w s x p 系统下，利用v c + + 6 0 实现了该方案的原型系统。实验结果表 明：该方案是正确和可行的，且具有良好的安全性和鲁棒性。 关键词：l a g r a n g e 插值；秘密共享；先应秘密共享 t h er e s e a r c ha n dr e a l i z a t i o no fp r o a c t i v es e c r e t s h a r i n g 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 fc o m p u t e rn e t w o r k s ，t h ei n f o r m a t i o nh a sb e c o m ea l l i m p o r t a n ts t r a t e g yr e s o u r c eo fs o c i a ld e v e l o p m e n t ，a n di n f o r m a t i o ns e c u r i t yh a sb e c o m ea s o c i a lp r o b l e mt h a tt h ew o r l dp a y st h ea t t e n t i o nt o t h r e s h o l ds e c r e ts h a r i n gi so n eo ft h e i m p o r t a n tw a yt os a v es e c u r e l yi m p o r t a n ti n f o r m a t i o na n dd a t a ，p r o a c t i v es e c r e ts h a r i n g r e n e w se v e r ys h a r ep e r i o d i c a l l yw i t h o u tc h a n g i n gt h es e c r e t t h i sd i s s e r t a t i o np r e s e n t ss o m ek n o w l e d g et h a tr e f e r st ot h ec r y p t o g r a p h y t h e ni t i n t r o d u c e st h em a i ni d e ao ft h r e s h o l ds e c r e ts h a r i n g ，a n dd e t a i l e d l ya n a l y s e sv e r i f i a b l e s e c r e ts h a r i n gs h c e m e ，s e c r e ts h a r i n gw i t h o u tt h et r u s ta n dp r o a c t i v es e c r e ts h a r i n g t od e a l w i t ht h ep r o b l e m sa n dd e f i c i e n c yo ft h e s es c h e m e s ，w ep r o p o s ean e ws c h e m eo f p r o a c t i v es e c r e ts h a r i n gw h i c hh a st h ef o l l o w i n gf e a t u r e s ： 1 t h es c h e m eh a sn o tt h et r u s t e dc e n t e rw h i c hc a np r e v e n tt h ea u t h o r i t yc h e a t a tt h e s a m et i m e ，t h es c h e m ec a nv 耐母e v e r ys h a r e h o l d e r ss h a r ea n df i n dt h ea t t a c k e r sa n d m i s b e h a v i n gs h a r e h o l d e r s s ot h es c h e m ei m p r o v e ss y s t e m ss e c u r i t y 2 i no r d e rt op r e v e n tt h em o b i l ea d v e r s a r yf r o ml e a r n i n go rd e s t r o y i n gt h es h a r e s ，t h e s c h e m er e n e w st h e mp e r i o d i c a l l y , a n di ns u c haw a yt h a ta n yi n f o r m a t i o nl e a r n e db yt h e a d v e r s a r ya b o u ti n d i v i d u a l s h a r e sb e c o m e so b s o l e t e h e n c et h es c h e m ee n h a n c e s s y s t e m sr o b u s t n e s s 3 s o m eo ft h es h a r e sm u s tb er e n e w e ds oa st od e l e t et h ec o r r u p t e ds h a r e h o l d e ra n d a d dan e ws h a r e h o l d e r , t h e r e f o r et h es c h e m er a i s e ss y s t e m su s a b i l i t y a tl a s t ，w eu s ev c + + 6 0a n ds q ls e r v e r 2 0 0 0t od e s i g nap r o t o t y p es y s t e mi n w i n d o w sx p t h er e s u l ts h o w st h a tt h i ss c h e m ew h i c hh a sg o o ds e c u r i t ya n d r o b u s t n e s s ，i sr i g h ta n df e a s i b l e k e y w o r d s ：l a g r a n g ei n t e r p o l a t i o n ；s e c r e ts h a r i n g ；p r o a c t i v es e c r e ts h a r i n g 插图目录 系统模型3 3 原型系统的运行流程图一3 3 新成员获取秘密份额的过程3 4 获取的公共参数3 5 产生秘密份额的过程3 6 恢复的共享秘密3 8 定期更新秘密份额的过程3 9 添加成员的过程一4 0 删除成员的过程4 2 恢复的共享秘密4 4 1 2 3 4 5 6 7 8 9 1 5 5 5 5 5 5 5 5 5 5 图图图图图图图图图图 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金目垦王些太堂 或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 履履梅签字日期：d 窘年石月，弓日 学位论文版权使用授权书 本学位论文作者完全了解金理王些盔堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金胆 王些盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 再尖f 虱爿辱 导师签名： 彳膨亿 签字日期：d 8 年6 月妒 签字日期：苏石月f 却 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 致谢 本人在硕士研究生学习和撰写学位论文期间，自始至终得到了我的导师侯整风教 授的悉心指导，无论从课程学习，论文选题，还是收集资料，论文成稿，都倾注了侯 老师的心血，由衷地感谢侯老师在学业指导及其他各方面所给予的关心。侯老师兢兢 业业的敬业精神、一丝不苟的治学态度和诲人不倦的高尚师德给我留下了深刻的印 象，让我受益匪浅，所有这一切必将在我今后的工作、学习和生活中激励我继续努力， 鞭策我不断上进。 同时，在此感谢计算机学院的各位老师，他们的教诲为本文的研究提供了理论基 础；感谢实验室的其他同学，在本课题的研究和撰写中，他们在许多问题上都给我提 出了宝贵的意见，感谢他们对我的无私帮助。 感谢所有爱我、关心和帮助过我的人。 作者：殷凤梅 2 0 0 8 年3 月 第一章绪论 随着计算机网络及通信技术的迅猛发展，人类进入了信息社会，利用互联 网获取和交换信息己成为当今信息社会的一个重要特征。在信息社会的发展过 程中，人类必须面对和解决几个关键问题：( 1 ) 如何进行保密的通信；( 2 ) 如何 保证信息不被非法修改；( 3 ) 如何保障计算机及网络系统不被非法访问和攻击。 密码学是研究信息安全的重要学科，主要针对数据加密、数字签名、身份认证、 密钥交换等安全理论和协议进行研究，保障计算机尤其是网络系统中的数据安 全性。 密码体制的设计和研究都是在k e r c k h o f f 的假设前提下进行的。一般情况 下，密码体制由密码算法和密钥组成，k e r c k h o f f 假设要求密码体制的安全性仅 依赖于密钥的保密而不依赖加密和解密算法。因此，密钥的安全是整个密码体 制安全的前提，密钥一旦泄露将直接破坏密码体制的安全性，因此必须解决密 钥管理问题。秘密共享为解决密钥管理问题提供了崭新的思路，在密钥的安全 保存、传输及合法利用中起着非常关键的作用。 1 1 研究目的和意义 门限秘密共享的概念最早是由s h a m i r 1 l 并i i b l a k l e y t 2 】于1 9 7 9 年分别提出的， 其基本思想是将秘密分成行个秘密份额( 也称为份额) ，并安全地分发给以个成员 ( 参与者) ，使得其中t 个或更多的成员联合就可以恢复秘密，而少于t 个成员 就无法恢复。秘密共享具有如下优点： ( 1 ) 有利于防止权力过于集中； ( 2 ) 确保秘密的安全性和完整性； ( 3 ) 提高系统的可靠性。 然而，传统的秘密共享方案对于保护生命周期较长的秘密并不十分有效， 因为入侵者可以利用整个生命周期进行长时间的攻击。当然，我们可以周期性 地更新秘密本身来解决这个问题。但是，对有些周期比较长、机密性比较强的 秘密( 例如各种密钥、企业机密文件、高机密数据等) 来说，更新秘密是不现实 的。先应秘密共享方案( p r o a c t i v es e c r e ts h a r i n g ，简称p s s ) t 3 】为解决这个问题提 供了个崭新的途径。 先应秘密共享方案的基本思想就是“分布+ 更新”，即在秘密共享的基础上 引入秘密共享份额周期更新机制。系统周期性地用新份额替换当前使用的旧份 额，由于新份额与旧份额间无相关性，攻击者在前期获得的秘密份额变得毫无 用处。攻击者欲获得完整的秘密信息，必须在一个周期内获得足够多的秘密份 额。先应秘密共享使得攻击者的有效可利用时间大大缩短，从而保证了秘密的 长期安全性。先应秘密共享已经在认证中心的密钥管理，电子商务中银行电子 货币的签名密钥管理，安全数据库的密钥管理等众多场合有着广泛的应用。 在大多数秘密共享方案中，成员的秘密份额都是由可信中心分发的。实际 应用中，这不仅增加了可信中心的计算、传输和存储复杂度，而且会使得可信 中心成为攻击者的首选目标，影响系统的安全性。此外，被绝对信任的可信中 心并不存在，因此需要探索无可信中心的秘密共享方案。 为了提高秘密共享的安全性，本文提出了一种新的先应秘密共享方案，该 方案无需可信中心。为了提高系统的鲁棒性，共享秘密保持不变的情况下，所 有成员如何定期更新秘密份额是本方案研究的主要目的。另外，没有可信中心 的情况下，如何完成成员变更( 包括成员的添加和删除) 引起的部分秘密份额 的更新是本方案研究的另一目的。 1 2 国内外研究现状 秘密共享最早由s h a m i r 和b l a k l e y 提出。随后，出现许多秘密共享的其它算 法，如基于中国剩余定理的a s m u t h b l o o m 法【4 j 、使用矩阵乘法的 k a m i n g r e e n e h e l l m a n 方法【5 】以及b r i c k e l l 的矢量空间方法【6 】等。 s h a m i r 方案需要一个可信中心，然而出于某种目的，可信中心可能分发给 某个成员假的秘密份额，这样该成员与其他成员合作将不能恢复秘密。为了防 止可信中心的权威欺骗，1 9 8 5 年c h o r 7 】等人首先提出了可验证秘密共享的思想。 随后，f e l d m a n 提出了一种可验证的秘密共享方案【8 】，该方案基于离散对数问题。 为了保留s h a m i r 方案的完备性，p e d e r s o n 提出了一种新的可验证方案 9 】 4 6 1 。1 9 9 4 年h a r n 提出了一种基于e 1 g a m a l 签名的门限群签名方案【l ，该方案不需要可信 中心。然而，在h a m 的方案中，超过门限值的小组成员联合起来，能够恢复某 个成员的私钥。r g e n n a r o 给出了分布式环境下的联合秘密共享协议【1 1 j o i n t s h a m i rr s s 协议) ，分布式密码系统是一个公钥密码系统，其私钥分布在多个 用户中，并且一定数量的用户可以恢复私钥。这样，部分私钥信息的丢失不会 影响整个系统的安全性。 在秘密共享方案中，部分秘密份额可能会泄漏或者损坏。泄漏或损坏的秘 密份额达到门限数目，秘密就会暴露或者丢失。因此在保证共享秘密保持不变 的情况下，成员需要周期性地更新自己的秘密份额，使以前暴露或损坏的秘密 份额不会对秘密的安全产生威胁，这样就出现了先应秘密共享方案( p r o a c t i v e s e c r e ts h a r i n g ，简称p s s ) 。 ro s t r o v s k y 和my u n g 屹】于1 9 9 1 年最早提出先应秘密共享的概念， h e r z b e r g 将先应秘密共享与门限密码学结合，提出了动态r s a 的先应秘密共享 算法【3 】。在h e r z b e r g 方案的基础上，随后出现了多种不同形式的先应式秘密共 享方案 1 孓2 0 1 。为了保证其他成员在不泄漏秘密份额的情况下，新成员可以正确 地获得秘密份额，李琥提出了一个新成员加入协议【2 引。 2 先应秘密共享的思想已经应用到数字签名中，并且出现了各种前向安全签 名方案。其中，a n d e r s o n 2 l 】最先提出前向安全特性的概念，b e l l a r e 和m i n e r 率 先实现了前向安全签名方案【22 1 ，之后出现了各种前向安全签名方案 2 3 2 7 1 。 现有的先应秘密共享方案中都存在可信中心，系统的安全性受到很大的影 响；并且这些方案都主要集中在所有成员定期更新问题的研究上，而对于由于 添加删除成员引起的部分秘密份额的更新问题很少研究。 1 3 研究内容和内容安排 本文主要对先应秘密共享进行研究，通过分析前人的成果与不足，提出一 种新的先应秘密共享方案。研究的主要内容包括： ( 1 ) 深入研究门限秘密共享理论及其典型方案； ( 2 ) 提出了新的先应秘密共享方案； ( 3 ) 实现原型系统，验证了该方案的可行性和安全性。 本论文的组织结构如下： 第一章绪论。阐述了课题的研究的目的和意义、国内外研究现状和研究的 主要内容及内容安排。 第二章密码学概述。介绍了经典密码学和公钥密码学的主要内容以及数字 签名技术。 第三掌门限秘密共享。介绍了门限秘密共享的基本思想和主要类型，重点 分析了门限秘密共享的几种典型方案。 第四章先应秘密共享方案。详细介绍了方案的主要内容，并分析该方案的 可行性、安全性以及方案的特点。 第五章先应秘密共享原型系统的实现。阐述了大数运算的实现，重点介绍 了原型系统的设计和实现过程。 第六章总结与展望。总结本文所做的工作，并对先应秘密共享的研究及应 用前景做出展望。 第二章密码学概述 密码学作为一种保护信息安全的方法，是一门古老又年青的学科，它最早 应用于军事、外交和情报等少数领域，后来随着科技的不断发展而逐渐进入到 人们的生活中，其商用价值和社会价值已经得到充分的认可。 密码学包含两个分支：密码编码学和密码分析学。密码编码学是对信息进 行编码实现信息保密的学科；密码分析学是研究、分析、破译密码的学科。 两者相互对立，又互相促进地共同向前发展。 密码学的发展可以分为经典密码学和公钥密码学。 2 1 经典密码学 经典密码学是基于消息的发送者和接收者运用相同的密钥来达到消 息加密的目的，其具体实现过程是：首先消息的发送者用共享密钥加密消 息，然后消息的接收者用相同的密钥解密消息并获取消息。采用这种方法 的密码学我们又将它称之为单钥密码学或对称密钥密码学。这种密码体制 大体上可分为两类：代替密码和换位密码。 代替密码：基本思想是将明文中的字符替换成密文中的另外一个字 符。在经典密码学中，有四种类型的代替密码：简单代替密码、多名码代 替密码、多字母代替密码和多表代替密码。 换位密码：基本思想是根据某种算法不改变明文的字符形式仅仅改变 字符的位置，将重新排列的信息作为密文。 如果将代替密码和换位密码相结合便形成乘积式密码，它是一种混合 式密码。使用最广泛的混合式密码就是d e s 算法。 对称密钥系统中，消息的发送者和接受者必须在没有第三方知道的情况 一下获取双方都同意的密钥，如果他们处于不同的地理位置，特别是不可能当面 交流的情况下，他们就必须借助一个可靠的第三方或是一个可靠的通信系统来 确定密钥。然而人和通信系统都未必是可靠的，所以密钥的传输和保管是对称 密码学中一个棘手的问题。 2 2 公钥密码学 在对称密钥算法中，算法的安全性很大程度上取决于密钥的安全性， 一旦密钥泄漏出去，那就意味着任何获得密钥的人都可以进行加密和解 密。为了更好地解决密钥的安全性问题，研究人员做了大量新的尝试。19 7 6 年，w h i t f i e l dd i f f i e 和m a r t i nh e l l m a n 2 9 】发表了开创性的论文“密码学的 新方向 ，提出了公钥密码体制的思想，给密码学的发展带来了划时代的 变革。 4 公钥密码体制用到两个不同的密钥：一个是公开的( 公钥) ，另一个是秘密 的( 私钥) 。从公钥很难推导出私钥。公钥用来加密消息，但无法解密，只有私 钥能够解密消息。公钥密码体制对于保密通讯、密钥分配和鉴别等领域都有着 深远的影响。公钥密码体制将加密密钥和解密密钥分开的特点，可以实现多个 用户加密的消息只能由一个用户解密；或者由一个用户加密的消息能由多个用 户解密。前者应用在网络中，实现了保密通信；后者应用在认证系统中，实现 了数字签名。 公开密钥的第一个算法是由r a l p hm e r k l e 和m a r t i nh e l l m a n 联合开 发的背包算法【3 1 】 32 1 。这个算法是基于组合数学中的背包问题而提出的， 该系统又被称为m h 背包公钥密码系统。由于m e r k l e h e l l m a n 变换无法 将超递增序列的特性完全隐藏起来，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 公钥密码算法【”】，它的安全性是依赖于大数的素因子分解困难性。 此后，又出现了r s a 的变形：r a b i n 密码。 此外，还有基于离散对数问题( d l p 问题) 的e 1 g a m a l 算法【3 4j 和基于 椭圆曲线离散对数问题的椭圆曲线密码算法e c c 3 5 1 【36 1 。美国政府的官方 数字签名标准d s a 算法【37 】就是在e 1 g a m a l 的成果基础上稍作修改而成。 尽管还有许多其他公开密钥算法，但是随着计算机硬件的发展和数学 理论上的突破可以在实际中使用的算法所剩无几。经过大量研究和实践， r s a ，e 1 g a m a l 和e c c 等公开密钥系统已经被证明是符合要求的，并且日 渐趋于完善。 2 2 1r s a 算法 r s a 是由r i v e s t ，s h a m i r 和a d l e m a n 联合提出的公钥系统，它的基础 是数论的欧拉定理，其安全性依赖于大数的素因子分解的困难性。 r s a 算法的具体描述如下： ( 1 ) 取两个素数p ，q ( 保密) ； ( 2 ) 计算n = p q ( 公开) ，矽( 以) = ( p - 1 ) ( q - 1 ) ( 保密) ； ( 3 ) 随机选择整数e ( 公开) ，满足g c d ( e ，妒( ，z ) ) = 1 ； ( 4 ) 计算d ( 保密) ，满足d e 毫l ( m o d 0 ( n ) ) 。 加密算法：c = e ( m ) = m 。m o dn 解密算法：m = d ( c ) = c dm o dn 如果n = p q 被因子分解，r s a 算法就被攻破。因为如果获得p , q ，便 可计算出( ，1 ) = ( p 一1 ) ( g - 1 ) ，并从等式d e 兰l ( m o d ( n ) ) 最终能求出解密密钥d 。 因此，r s a 算法的安全性依赖于因子分解的困难性。 随着因子分解算法不断的进步以及计算机硬件技术的飞速发展，为了 保证r s a 算法的安全性，采用了如下措施： ( 1 ) 产生位数更大的大素数。现今r s a 的密钥长度一般采取1 0 2 4 比特，这 能够保证在现有的数学知识基础上，r s a 加密体制是安全的； ( 2 ) 选取恰当的p ，q 。s i m m o n s 和n o r r i s 曾证明，如果p ，q 选取不当，破译 者可以利用公开密钥反复对密文进行多次加密就能还原出明文。r i v e s t 提出， 若选择的p ，q 使p 1 ，q 1 各能被一个大素数p ，q 整除，并使得p 1 ，q 1 分别含 有大素数因子，则上述破译成功的概率很小。 ( 3 ) 选择安全素数因子作为p ，q 。b l a k l a y 提出了安全素数的概念，即若素 数p 形如p = 2 p + l ( p 为另一大素数) ，则称p 为安全的。若p 和q 两个素数因 子均为安全素数，那么将大大提高r s a 体制的安全性。 r s a 算法的优点是密钥空间大，安全性能高，但是加密速度比d e s 算法慢很多。如果通过硬件实现，r s a 比d e s 慢大约10 0 0 倍，即使通过 软件实现也要慢上10 0 倍左右。在实际应用中，r s a 算法常常和d e s 算 法结合使用：d e s 加密明文，r s a 加密d e s 的密钥，这样既解决了长报 文加密的效率问题，又解决了d e s 密钥分配的问题。 2 2 2e l g a m a l 算法 e 1 g a m a l 算法既可用于数字签名又可用于加密，其安全性依赖于有限 域上的离散对数分解的难度。现阶段有限域上离散对数问题仍然无法被破 解，因此用e 1 g a m a l 算法加密后的信息在没有密钥的情况下是无法被恢复 的。 e 1 g a m a l 算法如下： ( 1 ) 随机选择g 、x 和大素数p ，其中g 和x 小于p ； ( 2 ) 计算y = 9 1m o dp ，x 是私钥，y 是公钥，公开g 和p ； ( 3 ) 加密消息m ，选择随机数k ( k 和p 1 互素) ，计算：a = g km o dp 和b = y k m m o d p ( 4 ) 解密时计算：m = b a 1m o dp 因为a 1 = g k x m o dp 以及b a 1 = y k m a 1 = g k x m g h = mr o o dp 都成立，除了y 是 密钥的一部分以及加密是和y l c 相乘而来，它和d i f f e h e l l m a n 密钥交换几乎一 样。每个e 1 g a m a l 签名和加密都需要一个新的k 值，该值必须随机选取。 2 2 3 椭圆曲线( e c c ) 密钥系统 椭圆曲线密码体制3 8 】 3 9 1 来源于对椭圆曲线的研究。椭圆曲线指的是 由韦尔斯特拉斯( w e i e r s t r a s s ) 方程： y 2 + 口l x y + a 3 y = 石3 + 口2 x 2 + 口4 x + a 6 6 所确定的平面曲线，它是由方程的全体解( 毛) ，) 再加上一个无穷远点曰构成 的集合。其中系数a i o = 1 , 2 ，6 ) 定义在某个域上，可以是有理数域、实数 域、复数域、也可以是有限域g f ( p 7 ) 。椭圆曲线密码体制中的椭圆曲线定 义在有限域上。给定椭圆曲线e 上的一个点尸，对任意的点q ，如果存在 整数m 使q = m p ，如何求解m 为椭圆曲线上的离散对数问题，而椭圆曲线 密码体制的安全性就是基于该问题的困难性。将椭圆曲线应用到密码学 上，最初是由n e a lk o b l i t z 3 9 】和v i c t o rm i l l e r t 3 8 】在19 8 5 年分别独立提出的。 椭圆曲线密码体制是目前公钥密码体制中，对每比特提供的加密强度 最高的一种体制。目前求解椭圆曲线上的离散对数问题的最好算法是 p o l l a r d r h o 4o j 方法，其时间复杂度是完全指数时间的。而目前最好的大整 数分解算法的时间复杂度是亚指数时间的。因此，当r s a 的密钥使用2 0 4 8 位时，仅使用2 3 4 位e c c 密钥，就可以获得相同的安全强度，此时它们之 间的密钥长度相差6 倍，且此差距会随着e c c 密钥的增长而变得更大。 2 3 数字签名 从社会的发展来看，随着电子信息时代的来临，人们越来越希望通过 数字通信网进行迅速的、远距离的交易。在这种数字化的信息世界里，传 统的手写签名和印签已经难以发挥作用，因此，人们迫切需要一种具有手 写签名和印签功能的数字化签名方法。这正是数字签名技术产生的背景。 数字签名有助于实现大型网络安全通信中的密钥分配，同时也是实现认证 的重要工具。 数字签名的作用与手写签名类似，应满足如下条件： ( 1 ) 可验证性。接收方能够验证发送方所宣称的身份； ( 2 ) 不可否认性。发送方不能否认已发送的报文； ( 3 ) 不可伪造性。接收方不能伪造报文： ( 4 ) 第三方可以确认收发双方的消息传递，但不能伪造这一过程。 目前已经提出了许多数字签名体制，但大致可以分为两种：一种是对 整体消息的签字，它是消息经过密码变换的被签字消息整体；另一种是对 压缩消息的签字，它是附加在被签字消息之后或某一特定位置上的一段签 字图样。如果按照明密文的对应关系划分，每一种又可分为两种类型：一 类是确定性数字签名，其明文与密文一一对应，它对一特定消息的签字不 变化，如r s a 签名；另一类是随机化的或概率式的数字签名，它对同一消 息的签字是随机变化的，取决于签字算法中的随机参数取值，这时一个明 文可能有多个合法的数字签名，如e l g a m a l 签名。下面分别介绍基于r s a 和e l g a m a l 的数字签名。 7 2 3 1r s a 签名 r s a 签名与r s a 加密不同之处在于r s a 加密是用公开密钥e 进行加 密，用解密密钥d 进行解密，而r s a 签名正好相反，它是用解密密钥d 进行签名，用公开密钥e 进行验证。具体过程描述如下： 假设明文为m 和签名为s z n 。 参数选择：p l 和p 2 是大素数，计算甩= p 。木p ：，随机选择e 并根据 d e 三1 m o d ( p l - 1 ) ( p 2 1 ) 计算d ，公开n 和e ，将p l ，p 2 销毁，秘密保存d 。 签名：对消息m ，计算散列码h ( m ) ，定义s = s i g ( h ( m ) ) = h ( m ) om o d 1 1 验证：对给定消息m ，签名s 可以按以下等式进行验证： v e r k ( h ( m ) ，s ) = 1 h ( m ) = s 。r o o dn 在r s a 实现数字签名的方案中，将要签名的消息作为一个散列函数 的输入，产生一个定长的安全散列码。使用数字签名者的解密密钥对这个 散列码进行加密就形成了签名，然后将签名附在消息后。验证者根据消息 产生一个散列码，同时使用签名者的公开密钥对签名进行解密。 r s a 签名的安全性依赖于分解甩= p ，木p ：的困难性。 2 3 2e 1 g a m a l 签名 e 1 g a m a l 签名的基本过程为：m 为需要签名的消息，选择大素数p 、 随机数x 、g z p ，其中g 是z p 乘法群的一个本原元，x 是用户的私人密 钥。计算y = g xm o dp 得到公开密钥( p ，g ，y ) 。 签名：给定消息m ，发送方进行签名： ( 1 ) 发送方在z 口乘法群中选择随机数k ； ( 2 ) 计算m 的散列码h ( m ) ； ( 3 ) 计算r = g 。m o dp 和s = ( h ( m ) 一x r ) k “m o d ( p 一1 ) ； ( 4 ) 将s i g k ( m ，k ) = ( r l l s ) 作为签名，将m ，( r l i s ) 发送给接收方。 验证：接收方收到m ，( r | | s ) ，计算出h ( m ) ，并按下式进行验证： v e r k ( h ( m ) r ，s ) = 1 铮y r = g h 【m r o o dp 这是因为：y r r 8 = g x r + k s = g h ( m m o dp 在此方案中，对同一个消息m ，由于随机数k 不同会产生不同的签名值。 该体制的安全性依赖于求解离散对数问题的困难性。 2 4 本章小结 本章首先概述了密码学的发展，探讨了几种重要的公钥密码算法，如 r s a 算法、e l g a m a 算法和椭圆曲线( e c c ) 密钥系统等，最后介绍了数字签 名的相关内容。 第三章门限秘密共享 门限秘密共享是信息安全和数据保密中的重要手段，在多方环境中，它 是一个基本协议和工具。其概念最早由s h 锄i r 【1 】和b l a k l e y 2 j 于1 9 7 9 年分别提出 的。这一思想的最初动机在于解决密钥管理的安全性问题。通常，一个密钥 可能决定着多个重要文件的安全性，一旦密钥丢失或者损坏，都可能造成 多个重要文件不能打开，在密钥失窃的情况下，还可能造成多个文件被窃取( 一 个密钥可能加密多个文件) 。为了解决这个问题，一种方法是创建密钥的多 个备份并且将这些备份分发给不同的人保管。但是这种方法并不理想，因 为创建的备份数目多或者少都会影响系统的安全性和鲁棒性。门限秘密共 享在不增加风险的前提下能够很好地解决上述问题。 3 1 门限秘密共享的基本思想 门限秘密共享的基本思想是将所需共享的秘密s 分成n 个份额s f ，分 发给以个成员，并且满足： ( 1 ) 任何f 个以上的s f ，能够重构s ； ( 2 ) 少于t 个s f ，无法重构s 。 下面给出门限秘密共享的正式定义【4 l 】：设p = ，最，只) 为成员集合， s ，s ，s ：，s 。为n + 1 个有限集。一个( t ，n ) 门限方案由两个算法组成，一个是秘 密分配算法，另一个是秘密恢复算法。对于秘密s ，分配中心通过秘密分 配算法生成秘密份额= b ，是，j 。) e s , x s 2 x 最和对应于成员集的公开目录 局= 缸。，x ：，工。 ，一般简单地记2 p = 1 ，2 ，z ) 。对每个a = e ，p , 2 ，气) c p ， i ， k ) 个人能阻止秘密的恢复。 b e u t e l s p a c h e r 给出了实现这一特殊安全要求的秘密共享方案【42 | ，即可阻 止恢复秘密的秘密共享( s e c r e ts h a r i n gw i t hp r e v e n t i o n ) 方案。其基本思想： 每个参与者都有两个分享的秘密份额，一个为“是 ，一个为“否 ，当决定是 否能恢复秘密时，参与者选择并提交自己的秘密份额，如果多于k 个“是而 少于m 个“否”，就可重构秘密，否则就不能重构秘密。 ( b ) 基于多分辨滤波的秘密共享 l o 在现有大多数门限秘密共享方案中，各参与者的权限相同，不适用于 社会中广泛存在的等级关系；另外，任意t 个拥有份额的参与者都可以组 成授权子集，不利于分组控制。为此，s a n t i s 等人【43 提出了多分辨滤波秘 密共享的概念。其基本思想是借用现代信号中经常用到的双通道滤波器 组。一个信号序列经过双通道滤波器组滤波，可以分解成两组序号序列。 将分解后的两组信号继续通过双通道滤波器，由此得到多种“分辨率 层 次的信号表示，用这些信号即可精确恢复原有信号( 秘密) 。 ( c ) 可视秘密共享 在19 9 4 年欧洲密码学会议上，n a o r 和s h a m i r 4 4 】首次提出了可视密码 学( v i s u a lc r y p t o g r a p h y ) 来实现图像的共享。其目标是对二进制黑白图像 进行( t ，n ) f - j 限视觉式处理：将原图像中的每个像素5 。分成m 个子像素j ， 其中m 为一个完全平方数，这些子像素非黑即白地紧邻在一起。在( t , n ) 门限可视秘密共享方案中，将原图像分成n 张投影片，若将数量大于门限 值t 的投影片重叠在一起( 即m 个子像素作或运算) ，则重叠后的图像每一 点色彩均相同，反之，则会表现出各点不同的差异，造成视觉上的区别。 ( d ) 量子秘密共享 近年来，基于物理现象的密码学也得到了研究界的重视。量子密码可 能成为光通信网络中数据保护的有力工具。量子秘密共享是量子密码理论 的重要组成部分，其基本原理是量子纠缠( q u a n t u me n t a n g l e m e n t ) 。量子 秘密共享主要受到量子的“无性( n o c l o n i n g ) 特性 的物理限制。 ( e ) 基于广义自缩序列的秘密共享 基于广义自缩序列的秘密共享【45 】是l a g r a n g e 内插多项式体制的一种 延伸，其基本思想是构造两个l a g r a n g e 多项式，一个用于恢复秘密，一 个则用于检验份额和秘密的有效性。后者的系数来自广义自缩序列，由于 其良好的伪随机性，所以该类秘密共享方案是安全可靠的，并且能简捷地 更新秘密份额。 3 3 门限秘密共享的典型方案研究 3 3 1 经典的门限秘密共享 ( 1 ) s h a m i r 的门限方案 s h a m i r 提出的门限秘密共享方案可以描述如下： 系统参数：1 1 是参与者的数目，t 是门限值，p 是一个大素数，p 挖t 。 同时，要求p 大于秘密的最大值，秘密空间与份额空间相等，均为有限域 g f ( p ) 。x i ，x 2 ，x n 为g f ( p ) 上n 个互不相同的元素。以上这些参数都是公 开的。 秘密分配算法： ( a ) 分发者d 首先随机选择g f ( p ) 上的一个t 一1 次的多项式 f ( x ) = a o + 口1 工+ + a t _ 1 3 c - 1m o d q 其中s = a o 。 ( b ) 分发者d 对于x 1 ，x 2 ，x n 分别计算s i = f ( x i ) ，其中1 f ，z 。 ( c ) 分发者d 将( x i ，s i ) 分配给成员p i ，s i 作为p i 拥有的秘密份额。 秘密恢复算法： 任意t 个秘密份额的持有者都可以将秘密份额放在一起，通过 l a g r a n g e 插值公式恢复出秘密信息s ： tt ， m ) = j 。兀兰m o d p 乍t s = 口。= 们) 1 = 1 j = l ，f “f “ 而少于t 个成员的集合无法计算出秘密s 。 ( 2 ) b l a k l e y 的矢量方案 b l a k l e y 利用多维空间中的点构造门限方案l 2 1 秘密被看成m 维空间 中的一个点，每一个影子是包含该点的( m 1 ) 维超平面的方程，任何m 个 超平面的交点就可以确定该点。 b l a k l e y 的方案比s h a m i r 的方案效率要低，但是它有一个特性：任何两 个影子之间是无关的。而s h a m i r 的方案中足够多的影子是可以计算出其他 影子的。 ( 3 ) a s m u t h b l o o m 的门限方案 a s m u t h b l o o m 的( f ，1 ) 门限方案 4 】是通过素数实现的：选择大素数p ， 使得p 大于消息m ，选择行个小于p 的数d 。，d ：，d 。使得： ( a ) d ，的值按递增顺序排列，即d ， p x d 。一。+ 2x d 。一。+ 3 x d 。 分配秘密份额时，选择一个随机数，计算： m = t + 巾 计算份额k i ： k f = m m o d d f 由中国剩余定理可知：由任意f 个或t 个以上的份额能够恢复m ，少于f 个 份额则不能恢复。 ( 4 ) k a m i n g r e e n e h e l l m a n 的门限方案 k a m i n g r e e n e h e l l m a