（计算机软件与理论专业论文）前向安全签名的一些研究.pdf

山东大学碰。l 。学位论文 摘要： 计算机技术和通信技术促使了互联网络的迅速发展，基于网络的信息服务、 应用服务在短时白j 内迅速发展，充分利用网络通信功能极大的提高了信息资源的 剃用率。但是互联网络本身却并不是安全的场所，暴力攻击、黑客入侵、病毒、 非法窃取信息等网络攻击层出不穷，这些对于基于网络的应用服务都是严峻的挑 i i j ，信息的安全性更是直接影响到基于网络韵应用服务的实现。密码学是研究信 i 。 息安全的学科，采用信息细密、数字签名、身份鉴别、密钥交换等方式保障网络 通信中锖恩的安全性。 密码体制由算法和密钥组成，根据k e r c k h o f f 假设密码，密码体制的算法总 是要公开的，于是密码体制的安全性就完全依赖于密钥的安全性。密钥丢失对于 一个密码体制的安全性来说是致命的，因为整个体制立刻变的不再安全，损失无 法估计。 解决密钥泄露的直接方法是提高密钥的安全性。秘密共享方案、门限签 名方案、p r o a c t i v e 密码体制都是直接加强对密钥的保护来提高密钥的安全性，秘 密共享方案使用分布式的存储实现私钥的安全存储，门限签名方案可以认为是使 用分靠式计算来加强私钥安全性，p r o a c t i v e 密码体制则是同频繁的更换公私钥来 降低私钥泄露的机会。但是这些解决方案中还存在一些不足的地方，比如新的解 决方案中带来新的问题，如门限中的共谋攻击：方案的实现的费用较高。和能够 获得的安全性能相比不能令人满意；这几个方案中如果私钥泄露，损失和普通方 案相同不能降低损失。此外。还有一些其他的解决方式，比如设计安全性更高 的硬件存储设备等。 解决密钥泄露的另种技术是前向安全密码体制，本文主要对前向安全签名 体制进行研究。前向安全的目标是降低密钥泄露所带来的损失，实现的方式是采 用“私钥演化”使敌人不能从所获得的私钥计算出之前所使用的私钥，这样敌人 就无法伪造更多的签名，减少了由私钥泄露所带来的损失。前向安全签名体制改 变了普通签名体制的原有模式，引入公钥的“生存周期”的概念，并将整个“生 存周期”划分为多个时间段，公钥生存在整个“尘存周期”有效且保持不变，两 在不同的时间段里使用不同的私钥，每个阶段之恻的私钥保持单向性，即从某个 阶段的私钥计算目矿一阶段的私钥是不可行的。这样在某阶段泄露密钥以后，由于 山东人学硕i ：学位论文 计算前一阶段的密钥是困难的，敌人无法伪造之 ； 阶段的签名，减少了出私钥泄 露所引起的损失。 本文重点分析了几个典型的前向安全签名体制，比较了几个方案的优点和缺 点，并分析了前向安全签名体制的研究方向。结合基于身份的签名体制，本文设 计了一个基于身份的前向安全签名体制，由于在基于身份的签名体制中，公钥被 规定为使用者的身份上d ，如果私钥泄露必须作废公钥时，使用者的身份d 要被 吊销。而在前向安全签名体制中，则不需要吊销使用者的身份国，作废对应阶 段的所有签名，然后继续进入后面的阶段。本文还对一个前向安全群签名进行改 进，增加了观察者的角色实现群成员删除的功能，在一定程度上增强了群成员管 理的灵活性和群签名方案的可用性。 关键词：网络信息安全私钥密码体制公钥密码体制信息加密数字签 名前向安全私钥演化基于身份的签名体制群签名 v 山东大学碳i 擘位论文 a b s t r a c t ： w i t ht h ea d v a n c eo fc o m p u t e rt e c h n i q u ea n dt h ec o m m u n i c a t i o nt e c h n i q u e ，t h e d e v e l o p m e n to fi n t e m e ti si m p e l l e dq u i c k l y b a s e do i ln e t w o r k ，t h em e s s a g es e r v i c e a n da p p l i c a t i o ns e r v i c ed e v e l o p e ds w i f t l y t h ei n f o r m a t i o nr e s o u r c eu t i l i z a t i o nr a t i o s u f f i c i e n t l yu t i l i z e dt h en e t w o r kc o m m u n i c a t i o ns e r v i c ee x t r e m e l yg r e a tr a i s eo f c a p a c i t y y e tt h ei n t e m e ti ni t s e l fy e ti sn o tas e c u r i t ya r e n aa ta l l ，a n dt h ef o r c e a g a c k 、h a c k e ri n t r u d e s 、v i r u sa n di l l e g a l l yg r a b s ，s om u c hn e t w o r ka t t a c k s e m e r g ei na ne n d l e s ss t r e a m ，a n dt h e s ea r es e r v e dc h a l l e n g ew h ow h o l l yi ss e v e r ea s 1 0t h ea p p l i c a t i o n sb a s e d i n go nt h en e t w o r k ，a n ds e c u r eq u a l i t yo fm e s s a g es t i l lm o r e i sd i r e c t l ya f f e c i n gt ob a s e do nn e t w o r ka p p l i c a t i o ns e r v i c er e a l i z a t i o n t h e c r y p t o l o g yi st h eb r a n c ho fl e a r n i n gt or e s e a r c hi n f o r m a t i o ns e c u r i t y ，a n da d o p t st h e m e a n ss u c ha st h em e s s a g ee n c i p h e r ，f i g u r es i g n a t u r ea n di d e n t i t ya u t h o r i t ya n dk e y e x c h a n g ea n ds oo nt os a f e g r a r ds e c u r eq u a l i t yo fm e s s a g ei nt h en e t w o r k c o m m u n i c a t i o n c r y p t o s y s t e ms c h e m ei sc o m p r i s e do fa l g o r i t h ma n dk e y a c c o r d i n gt o k e r c k h o f fp r i n c i p l e ，t h ea l g o r i t h mi s p u b l i s h e dt op u b l i c s ot h es e c u r i t yo f c r y p t o s y s t e ms c h e m ef u l l yd e p e n d so nt h es e c u r i t yo fk e y k e ye x p o s u r ei sf a t a lt oa c r y p t o s y s t e ms c h e m ea n dt h ed a m g ei su n a b l et oe s t i m a t e d o n es o l u t i o nt ot h ek e y e x p o s u r ep r o b l e mi st oi m p r o v et h es e c u r i t yo f t h es e c r e t k e y ，f o re x a m p l es e c r e ts h a r i n gs c h e m e 、t h r e s h o l dc r y p t o s y s t e m 、p r o a e t i v es e c r e t s h a r i n gs c h e m e s e c r e ts h a r i n gs c h e m eu s e sd i s t r i b u t e ds t o r a g et op r o t e c ts e c r e tk e y t h r e s h o l d e r y p t o s y s t e me n h a n c e st h es e c u r i t yo fs e c r e tk e yw i t hd i s t r i b u t e d c o m p u t a t i o n a n dp r o a c f i v es e c r e ts h a r i n gs c h e m eu p d a t e sk e yf r e q u e n t l y t h e r es r e s o m ep r o b l e mi nt h e r es o l u t i o n s ，f o re x a m p l e ，n e wd i f f i c u l t yw a si nt h es o l u t i o n ，t h e c o s to fi m p l e m e n t a t i o ni sh i g h ，o n c es e c r e tk e yw a sl o s tt h ed a m a g es t i l lc a nn o tb e a v o i d e d t h e r ea r ea l s os o m eo t h e rw a y sw i t hh a r d w a r e a n o t h e rw a yi sf o r w a r d s e c u r es c h e m e ，w h i c hw ew i l ld i s c u s si nt h i sp a p e r 。t o r e d u c et h ed a m a g ec a u s e db yk e y e x p o s u r ei st h eg o a lo ff o r w a r d - s e c u r es c h e m e t h es c h e m em a k ee n e m yd i s a b l et o f o r g es i g n a t u r eb e f o r e ，t h e nt h ed a m a g ew a s v 山东人学顶l ：学位论文 r e d u c e d f o r w a r d - s e c u r es i g n a t u r es c h e m em o d i f i e dp r i m a r ym o d e li nc o m m o n s i g n a t u r es c h e m e t h en o t i o n “l i f ec y c l e w a si n t r o d u c e di n t on e w s c h e m ea n di t i s d i v i d e di n t os e v e r a lp e r i o d s t h ep u b l i ck e yi sk e p tu n c h a n g e di n l i f ec y c l e ”，w h i l e t h es e c r e tk e yw a sc h a n g e di ne v e r yp e r i o d t h es c h e m ec o m p u t en e x ts e c r e tk e y w i t ha no n e w a yf u n c t i o n ，w h i c hm e a n st h a ti t i sd i f f i c u l tt og e tp r e v i o u ss e c r e tk e y w i t ht h a to fa n yp e r i o d s ot h ee n e m yc a nn o tf o r g et h es i g n a t u r eb e f o r ea n dt h e d a m a g ew a sr e d u c e d t h i sp a p e ra n a l y s e ss e v e r a lf o r w a r d - s e c u r es i g n a t u r es c h e m e s ，a n dg i v e st h e i r m e r i t sa n dd e f e c t s ，a l s ot h es e a r c hd i r e c t i o n so ff o r w a r d - s e c u r es i g n a t u r es c h e m e w ep r e s e n tai d e n t i t yb a s e df o r w a r d s e c u r es i g n a t u r es c h e m e i nai d e n t i t yb a s e d s i g n a t u r es c h e m e t h eu s e r si di sd e f i n e da sp u b ；i tk e y o n c et h es e c r e tk e yw a s l o s t ，w eh a v et or e v o k et h ep u b l i ck e y i tm e a n st h a tt h eu s e r si dc a nb en o tu s e d a n ym o r e b u tw en e e dn o tr e v o k et h eu s e r si di no u rn e ws c h e m eb e c a u s eo ft h e “f o r w a r d s e c u r e ”p r o p e r t y i nt h i sp a p e rw ea l s om a d eai m p r o v ei nag r o u ps i g n a t u r e s c h e m e w ea d da n “o b s e r v e r ”t ot h es c h e m et oe r a s eam e m b e rf r o mt h eg r o u p t h e n e ws c h e m ei sm o r ep r a c t i c a l k e y w o r d s ：n e t w o r ki n f o r m a t i o ns e c u r i t y 、 c r y p t o s y s t e m 、e n c r y p t i o ns c h e m e 、d i g i t a l e v o l u t i o n 、i d e n t i t yb a s e ds i g n a t u r es c h e m e 、 v s e c r e tk e yc r y p t o s y s t e m 、p u b l i ck e y s i g n a t u r e 、 f o r w a r ds e c u r i t y 、k e y g r o u ps i g n a t u r e s c h e m e 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体己经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：皇l 乞讽、)日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅：本人 授权】i 东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丝笙璺! ! 导师签名 劲0 4 摹；舟、痈 期：垫笪望三生生盟 山东人学颂i 。学位论文 1 绪论 1 。1 背景介绍 随着电子计算机和互联网络的迅速发展，极大的提高了信息资源的利用 率，给人们的生活和工作带来极大的便利。尤其是互联网的不断普及，使得网络 通信已经逐渐成为人们生活中同益重要的通信手段，但是随之而来的是信息安全 的问题。密码学是研究信息安全的重要学科，主要针对数据加密、数字签名、身 份认证、密钥交换等安全解决方案进行研究，保障计算机尤其是网络传输中的数 据安全性。 密码体制的设计和研究都是在k e r c k h o f f 的假设前提下进行的。一般情况下， 密码体制由密码算法和密钥组成，k e r c k h o f f 假设要求密码体制的研究不能以敌 人不清楚密码算法为前提，在这样的假设前提下密码算法的安全性完全依赖于密 钥的安全性。密钥的安全是整个密码体制安全的前提，密钥一旦泄露将直接破坏 密码体制的安全性，损失也将是无法估计的。很多的研究者在进行者密钥安全存 储的研究工作，提高密钥的安全性，降低风险。 前向安全的提出从另一个角度来解决密钥泄露的阀题，密钥泄露所产生后果 不仅仅是敌人会伪造签名，更重要的是影响到原来合法的签名的合法性，这样将 导致整个体制所有的签名都不再可靠。前向安全签名体制把目光转移到如何降低 密钥泄露后的损失这一方面，前向安全签名体制改变了普通签名体制的原有模 式，引入公钥的“生存周期”的概念，并将整个“生存周期”划分为多个时州段， 公钥生存在整个“生存周期”有效且保持不变丽在不同的时间段罩使用不i 刊的 私钥。每个阶段之间的私钥保持单向性，即从某个阶段的私钥计算前一阶段的私 钥是不可行的。这样在某阶段泄露密钥以后，由于计算前一阶段的密钥是困难的， 敌人无法伪造之前阶段的签名，减少了由私钥泄露所引起的损失。 设计前向安全签名体制的主要工作是设计私钥演化体制，私钥进行单向的演 化，保证了之前阶段晕的签名的可靠性，目前私钥演化的主要方式有模平方、伪 随机数函数。配合私钥演化函数，再选择适合的签名方案，形成完整的前向安全 签名体制。 山东大掌使1 ：学位论文 1 2 本文结果 本文对前向安全签名体制的概念和定义进行详细描述，并主要分析了三个典 型的前向安全签名体制，并讨论这几个方案的优缺点。b e l l a r e m i n e r 文献 5 的方案是第一个存储长度与时段数7 无关的前向安全签名方案，但其密钥过长的 弱点无法避免，难以用于实际。d b d a l l a - r e y z i n 文献 4 的方案针对b e l l a r e 、 一m i n e r 文献 5 的方案弱点给出了公私钥长度、签名长度均与普通签名方案相 同的前向安全方案。而且该方案还具有基于离散对数难解问题的安全性证明，安 全性得到充分保证。但该方案的私钥更新算法、签名与验证算法计算量仍然较大， 降低了实用性。k r a w c z y k 文献 9 的方案在不关心签名方案的情况下实现了前向 安全，具有一定的实用价值，其弱点是增加了签名的长度，降低了验证算法的效 率，另外还需要构造符合要求的伪随机函数并改造原有的密钥生成算法。 本文重点分析以上几个前向安全签名体制的优点及缺陷，并分析了阿向安全 签名体制的研究方向。结合基于身份的签名体制，本文设计了一个基于身份的前 向安全签名体制，由于在基于身份的签名体制中，公钥被规定为使用者的身份 加如果私钥泄露必须作废公钥时，使用者的身份旧要被吊销。而在前向安全 签名体制中，则不需要吊销使用者的身份，作废对应阶段的所有签名，然后 继续进入后面的阶段。本文还对一个前向安全群签名进行改进，增加了观察者的 角色实现了“向后”的安全，同时实现群成员删除的功能在一定程度上增强了 群成员管理的灵活性和群签名方案的可用性。 本文在第2 、3 部分介绍密码体制的基本知识和常见的密码体制。笫4 部分 将对前向安全签名体制进行介绍和研究，笫5 部分是本文的一个成果：一个基于 他的前向安全签名体制，本文的另一个成果是对个前向安全群签名进行改进， 在第6 部分给出。 2 现代密码体制 密码学是研究秘密书写的原理和破译密码的方法的一门科学。包合两个相关 的内容：密码编码学和密码分析学。密码编码学的主要目的是寻求保证消息保密 性或认证性的方法，密码分析学的主要目的是研究加密消扈、的破译或消息的伪 造。 山东大学砸卜学位论文 密码学是一门古老又年青的学科，人类在几千年以前就在军事和外交通信方 面使用密码学的手段。而现在密码学的应用的领域要更为广泛，其商用价值和社 会价值已经得到充分的认可。 密码学的历史发展大致分为三个阶段： 古典密码时期，时间范围大约为1 9 4 9 年以前，密码学家多是凭知觉和经验 来进行设计和分析。 1 9 4 9 年s h a n n o n 发表了“保密系统的信息理论”，揭丌现代密码学的序幕， 为私钥密码系统建立了理论基础，并真正的成为一门科学。 1 9 7 6 年d f i e 和h e l l m a n 的“密码学新方向”则导致了密码学的一次新的革 命，他们证明了在发送端和接收端无密钥传输的保密通讯的可能佳，从而丌创了 公钥密码学的新纪元。 密码分析学的工作恰恰相反总是试图从可能截获到的密文推导出明文。攻 击的类型有唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击，其攻击 的强度依次递增。通常我们假定密码分析者或敌人知道所使用的密码系统，被称 作为k e r c k h o f f 假设。当然如果密码分析者或敌人不知道所使用的密码系统，破 译工作将更困难，但是我们不能把密码系统的安全性建立在敌人不知道所使用的 密码系统这个前提下，因此设计一个安全的密码系统的目标是在k e r c k h o f f 假设 下实现安全性目标。 定义2 1 一个密码体制是一个五元组( p ，c ，k ，e ，d ) ，其中p 是可能明 文的有限集合，c 是可能密文的有限集合，k 是可能密钥的有限集合即密钥空间。 而且满足： 对每一个k k ，有一个加密规则e k e 和一个解密规则d k d ，每个 ：尸一c 和d k ：c 斗j d 是一个函数，它满足以( p ( 工) ) = x ，对每一个x p 。 根据密钥的不同，密码体制主要分为单钥密码体制和公钥密码体制。 2 1 单钥密码体制 单钥密码体制根据对明文消息的加密方式的不同分为流密码和分组密码。 流密码体制的关键在于如何进行密钥同步。流密码的优点是加密速度快，可 山东人学坝。i ：学位论文 以隐蔽数据模式。缺点是实现密钥同步比较麻烦，容易出现错误的传播。本文对 流密码体制不做太多的介绍。 分组密码由于其编码方式和目前的i n t e r n e t 网络的传输模式相类似，逐渐被 广泛的接受和使用。分组密码有着自身的优势，一是比较容易标准化，正是因为 刚才所说在目前的网络传输通常也是以块为单位。其次分组密码容易实现同步，、 某个密文的传输错误不会被传播。与其优点相比，分组密码的确定也很明显，一 是不能隐蔽数据模式，即相同密文对应相同明文：二是分组加密不能抵抗重放、 嵌入、删除等攻击。 2 1 1 分组密码体制及其设计原则 分组密码模型： 密钥k = - ( k l ，也，k )密钥扣( h ，也，。，) 图2 1 定义2 2 私钥分组密码体制 一个私钥分组密码体制是一个满足下列条件的映射：e ：霉s k 斗芝”对 每个k s k ，e ( ，) 是从口到譬的一个置换。我们将一个分组密码简记为 y = e 陇为。 我们知道哆上的簧换共有2 “! 个，d a v y 2 2 可知，一个分组密码是霉上 全体置换所构成的集合的一个子集合。设计一个分组密码的问题在于找到一种算 法，能在密钥控制下从一个足够大的且足够“好”的置换子集合中简单而迅速的 选出一个置换，用来对当前输入的明文数字组进行加密变换。一个好的分组密码 应该是既难破译又容易实现的，加密函数e ( ，曲，和解密函数d ( ，k ) 有 必须是容易计算的，但是要从方程y = e ( x ，舫和x = d ( y ，曲中求出密钥k 应该是一 个困难的问题。 山东人学l i j i ：l ：学位论文 影响密码体制安全性的问题很多，诸如分组长度肌和密钥长度，等，有关私 钥密码的一般性原则是有s h a n n o n 提出的混乱原则和扩散原则： 混乱原则：人们所设计的密码应使得密钥和明文以及密文之问的依赖关系相 当复杂以至于这种依赖性对密码分析者来说是无法利用的， 扩散原则：人们所设计的密码应使得密钥的每一位数字影口向密文的许多位数 字，以防止对密钥进行逐段破译，而且明文的每一位数字也应该影响密文的许多 位数字以便隐蔽明文的数字统计特性。 乘积密码是实现s h a n n o n 提出的混乱原则和扩散原则的一种有效的方法，所 谓乘积密码就是将两个或更多的简单密码逐次应用，有合理选择的多个子密码所 构成的乘积密码可以同时实现良好的混乱和扩散，包括d e s 在内的许多常见私 钥密码体制都属于乘积密码。 2 1 2 几个分组密码体制 计算机通信网络的发展对信息的安全保密的要求只益增长，未来的数据传输 和存储都要求有加密的保护。为了实现同一水平上的安全性和兼容性，提出了数 据加密标准化的问题，标准化有利于加密手段的推广和应用的普及。 数据加密标准( d e s ) ： 美国商业部所属国家标准局n b s 在1 9 7 2 年丌始了一项数据保护标准的发展 规划并于1 9 7 3 年5 月1 3r 颁布了征求在传输和存储数据中保护计算机数据的 密码算法的建议在一措施最终导致了数据加密标准( d e s ) 的出现。d e s 是目 前使用最广泛的分组密码算法，出i b m 公司研制，在1 9 7 5 年3 月1 7 闩首次被 公布在联邦记录中，在大量的公开讨论以后，于1 9 7 7 年1 月1 5r 被正式批准为 美国联邦信息处理标准。每隔大约5 年由联邦国家保密局n s a 作出评估，并决 定是否继续使用d e s 作为数据加密标准。d e s 的最后一次评审是在1 9 9 9 年1 月， 决定不再使用d e s ，而使用新征集到的高级加密标准a e s 候选的优胜者。 d e s 使用5 6 比特长度的密钥，加密和解密的分组长度为6 4 比特。d e s 算法 的基本流程是先代替后置换。d e s 算法包括j 6 轮变换，在每一轮使用从弱比特 完整密钥变换而来的4 8 位子密钥，在6 4 比特的分组上进行相同的变换操作。 d e s 加密算法对明文首先通过初始簧换，p ，将明文块分成左右两个部分，各 山裹夫学埘j ：学位论文 3 2 比特。然后进行1 6 轮变换，在每一轮变换，所使用的密钥为4 8 比特是从 5 6 比特密钥变换而来，明文分组经过1 6 轮迭代形成密文。 在每一轮迭代中，6 4 比特的输入被分为左、右两部分。各3 2 比特。其中右 边3 2 比特经过扩展算法e 扩展为4 8 比特，再与4 8 比特密钥进行异或运算，所 得到的结果经过8 个p 盒的替代运算和置换p ，最终输出3 2 比特。与左半部分 进行异或运算之后成为新的右半部分，而原来的右半部分成为新的左半部分，至 此完成了一轮迭代。 经过1 6 轮迭代之后的输出为6 4 比特，使用初始置换胪的逆置换进行操作 最后得到密文y 。 解密算法过程和加密算法过程相同，不同的是将密钥进行反排。 d e s 的安全性完全依赖于所使用的密钥。d e s 的密钥集合中存在有互补密 钥、弱密钥和半弱密钥，不过所占比例极小，在随机选择密钥的情况基本何以忽 略这些密钥的存在。明文和密文之间的相关性一直是对私钥密码体制分析的重要 指标有研究显示在经过8 轮迭代之后明文和输出就可以认为是不相关的了。虽 然d e s 的安全性在实际中还没有真正的威胁，但是长期以来对d e s 的安全性一 直存在着激烈的争论。d e s 的密钥为5 6 比特，被认为太短，随着计算技术的迅 速发展穷举密钥已经不再是不可能的事情。对j 盒怀疑始终存在，出于s 盒是固 定的，虽然在1 9 7 6 年n s a 公布了s 盒的几个设计原则，但仍没有足够理由漉明 为什么设计成这样，很多人担心s 盒中存在不为人知的陷门信息。对d e s 的攻 击方法主要有差分分析、线性分析、相关密钥攻击等方法，其中线性攻击是最有 效的一种方法。 国际数据加密标准肋歪m 1 9 9 0 年xzl a i 和，l m a s s e y 公椎了i d e a 的第一版，算法经过抵抗差分 密码分析攻击的改进，于1 9 9 2 年公稚。e z 的明文和密文的分组长度是6 4 比 特密钥的长度是1 2 8 比特，该算法所依据的设计思路是“混合使用来自于代数 群的中的运算”。该算法所需要的混乱可通过连续使用三个“不相容”的群运算 于两个1 6 比特字块获得，并且该算法所选择使用的密码结构可提供必要的“扩 散。 山东人学坝i 。学位论义 i d e a 的描述： 1 d e a 由8 轮变换和随后的一个输出变换组成，使用了三个不同的群运算： 加法一为模2 ”加法、异或一1 6 比特异或、乘法一模2 “+ 1 相乘( 1 6 比特全0 字 块处理为2 ”) 。 6 4 比特明文块被分成4 个1 6 比特子块即x = x z 岱幽，经过加密变换输出4 个 1 6 比特密文子块形成密文，即y 7 y 龇) 加密变换是在5 2 个1 6 比特的密钥子 块控制下进行的，这些密钥子块是从1 2 8 比特密钥经过密钥编排获得。对于每一 轮，= l ，2 ，8 ，需要6 个密钥子块，表示为z n z 孑1 ，z 妒。每一轮执行的 变换如下： ( 1 ) x 和z ( ，) 相乘： ( 2 ) 施和z 妒) 相加： ( 3 ) 溉和z l r ) 相加： ( 4 ) 孔和z 0 ) 相乘： ( 5 ) 将( i ) 和( 3 ) 的结果进行异或： ( 6 ) 将( 2 ) 和( 4 ) 的结果进行异或； ( 7 ) 将( 5 ) 的结果同z p ) 相乘： ( 8 ) 将( 6 ) 和( 7 ) 的结果相加： ( 9 ) 将的( 8 ) 结果和z 矿相乘： ( 1 0 )将( 7 ) 和( 9 ) 的结果相加： ( 1 1 )将( 1 ) 和( 9 ) 的结果进行异或： ( 1 2 )将( 3 ) 和( 9 ) 的结果进行异或： ( 1 3 )将( 2 ) 和( 10 ) 的结果进行异或； ( 1 4 )将( 4 ) 和( 1 0 ) 的结果进行异或： 将( 1 1 ) 一( 1 4 ) 的四个子块的中间两个交换就形成下一轮的输入。 经过8 轮的运算之后，进行下面的交换： ( 1 ) x i 和z 9 相乘； ( 2 ) 溉和z 1 9 ) 相加； 山东人学硕f ：学位论文 ( 3 ) x a 和z ，相加： ( 4 ) 知和z 妒) 相乘； 将以上4 步产生的结果连接起来成为加密算法的输出。z 的解密和加密 过程相同，唯一不同的密钥子块的编排算法不同。 ，d e 爿的密钥长度为1 2 8 比特，应付穷举攻击没有问题。i d e a 经证明是抵抗 差分分析的，同时还具有很强的抵抗线性攻击的能力。在伪j e 的密钥集合中， 发现了一些不好的密钥，但如果随机选择密钥，这些密钥不会带来危险。 高级加密标准a e s 1 9 9 7 年9 月1 2r ，n i s t 发抑了征集d e s 的替代者一高级加密标准a e s 的 公告，要求算法具有i 2 8 比特分组长度，支持1 2 8 、1 9 2 、2 5 6 比特长度的密钥， 并能在全世界范围内免费使用。2 0 0 0 年l o 月2 同r i j n d a e l 被选中成为高级加密 标准，2 0 0 1 年1 1 月2 6 日，爿e s 被采纳成为一个标准。a e s 的整个征集过程以 公丌性和国际性闻名，算法的评判标准是安全性、代价和算法与实现特征，最后 r 咖d a e l 被公认为是集安全性、性能、效率、可实现性及灵活性于一身而胜出。 r i j n d a e l 密码是由比利时的j o a nd a e m e n 和v i n c e n tr i j m e n 设计的，是一种 可变分组和可变密钥长度的迭代分组密码。r i j n d a e l 是一个迭代型密码包括i 种可选的密钥长度：1 2 8 、1 9 2 、2 5 6 比特，迭代的轮数与密钥长度相关。密钥 长度为1 2 8 比特时，迭代轮数为1 0 轮，密钥长度为1 9 2 比特时，迭代轮数为1 2 轮，密钥长度为2 5 6 比特时，迭代轮数为1 4 轮。 r i j n d a e t 的描述： r i j n d a e l 是面向字节的密码方案，用一个1 2 8 比特的明文分组作为初始状念。 算法将一个状态看成是一个4 4 的字节矩阵，r 咖d a e l 算法使用以下4 种运算进 行状态的交换： ( 1 ) 字节替换- - s u b b y t e s ：字节替换运算是一个非线性置换，独立的 作用于状态种的每一个字节。这个运算相当于一个8 8 的矩阵乘 以一个单独的字节，再加上一个8 i 的列向量。 ( 2 ) 移位行运算册i f t r o w s ：这是状态种字节的循环移位运算，这个 运算可以表示为b i ，= a i ，( ，+ ) m o d 4 ，即第一行的字节是不移动 山东人学麒f ：掌位论文 的，第二行的字节移动1 列位黄，第三行的字节移动2 列位置。 ( 3 )混合列运算- - m i x c o l u m n s ：由一个线性变换对状态a 的每一列 实藏变换这个变换相当于一个4 x 4 的矩阵这个状念种单个列的 字节。 ( 4 ) 轮密钥加法- - a d d r o u n d k e y ：每一轮的轮密钥都是使用密毛日编排 函数出密钥获得，轮密钥长度和加密分组的长度是相同的。在轮 密钥加法中，轮密钥与状念进行异或，产生新的输出状态。 r i n d a e t 算法的总体流程是： ( 1 ) 给定明文x ，将初始状态s t a t e 初始化为x ，进行a d d r o u n d k e y 操作： ( 2 ) 对于前胪1 轮中的每一轮用s 盒对状念s t a t e 进行一次 s u b 毋f e s 操作再对状态s t a t e 进行一次s h i # r o 岱操作，然后 对状念s t a t e 进行一次m i x c o l u m n s 操作，最后对状态s t a t e 进行 一次a d d r o u n d k e y 操作； ( 3 ) 最后一轮依次进行s u b b y t e s 操作、s h i f t r o w s 操作、a d d r o u n d k e y 操作： ( 4 ) 最后将s t a t e 定义为密文y 。 解密算法需要将所有的操作按逆序进行，同时密钥编排方案也按逆序进行， 经过同样的迭代即可获得明文。 对于目前已知的攻击方法而言，彳e s 算法是安全的。它的设计在各个方面进 行了融合，为抵抗各种攻击提供了安全性。例如，s 盒中有限域逆操作的使用导 致了线性逼近盒差分分布表中的各项统计趋向于均匀分布，这样为抵御差分分析 和线性攻击提供了安全性。类似的，“宽轨道策略“即线性混合列变换m i x c o l u m n s 使找到包含“较少”活动s 盒的差分盒线性攻击成为不可能。目i 对a e s 还不 存在快于穷尽密钥搜索的攻击方法。 2 2 公钥密码体制 私钥密码体制的严重缺路是在任何密文传输之前，发送者和接收者必须使用 一个安全的通道预先交换通信密钥。在现实中，做到这点可能是有困难的，例 如通信双方的地理距离很远，只能使用电子邮件或电话通信，这种情况下，通信 山东人学顽 ：学位论文 双方没有合理的安全信道。公钥密码体制的提出正是针对这个致命的缺陷，通信 双方无须事先交换密钥就可以建立保密通信信道，从而实现了在没有安全通信信 道的情况下的保密通信。 2 2 1 公钥密码体制的提出 公钥密码系统的观点是由d 泓和h e l l m a n 在1 9 7 6 年首次提出的，它使 密码学发生了一场变革。1 9 7 7 年出r i v e s t 、s h a m i r 和a d l e m a n 提出了第一个比 较完善的公钥密码算法，这就是著名的r s a 算法。之后又出现了些基于其他 算法的公钥密码体制，如m e r k e h e l l m a n 背包算法、m c e l i e c e 算法、e l g a m a l 算 法、椭圆曲线算法等。 d 0 犯和h e l l m a n 在提出公钥密码体制的同时指出，密码学可以借助n p 计算复杂性理论，来设计密码算法。将秘密的“陷门”信息嵌入在一个涉及单向 函数求逆计算上困难的问题中这样的函数被称为陷门单向函数( o n e h ，叫 d o o r ) ，而其中的陷门信息既是秘密的解密密钥，这是设计公钥密码体制的基本 原理。 公钥密码体制的安全性是计算上安全性，而不是无条件安全性。单向函数在 这里起到核心的作用，但是目前还没有一个函数被证明是单向的，我们现在使用 的都是被认为或被相信是单向的函数。 本章先介绍公钥加密体制，后面一章将主要介绍公钥签名体制。 2 2 2r s a 密码体制 r s a 算法是最早出现的公钥密码体制之一，它的理论基础是可逆的模指数运 算，安全性基于大整数分解的困难性。 大整数分解问题的描述： 已知刀= p q ，p 、q 为素数，求解p 和q 。 r s a 密码体制： 设n 是两个不同的素数p 和q 的乘积，即 胛= p 口 妒( 仃) = ( p 一1 ) ( g 1 ) r s a 密码体制被描述为： 0 山东人学预f 学位论文 k = f ( 雎，p ，仍口，6 ) l 打= p q ，只g 为素数，a b i t r a o d 妒( n ) ) p = c = z 。 加密算法为： e k ( x ) = 工扫m o d n ，z z 月 解密算法为： d k ( y ) = y 。m o d n ，y z 其中( ”，6 ) 为公钥，如，q ，口) 为私钥。 r s a 算法的专利已经过期，我们可以免费在任何场合使用该算法。 r s a 的安全性依赖于大整数分解的困难性。r s a 方案具有比特安全性，即如 果能从密文中获得一个最低位比特的明文信息，则可以从密文中得到全部的明文 信息。攻击r s a 最直接的方法就是尝试分解公开的模数n ，目前分解大整数的几 个有效算法是二次筛法、椭圆曲线分解算法和数域筛法，对r s a 体制的攻击方 法还有选择明文攻击、共模指数攻击等攻击方法。 2 2 3e i g m a l 密码体制 e l g a m a l 算法是在密码协议中有大量应用的一类公钥加密算法，它的安全性 是基于离散对数的困难性。在一个有限域z 。( p 为素数) 上的离散对数问题是 指给定一个素数p 和z p 的一个本原元d ，对卢z ；，找一个整数口 ( 0 d s p 一2 ) 使得口。；f l r o o d p 。目前尚还没有计算离敞对数的多项式算法 为了抵抗已知的攻击，p 应该至少是1 5 0 位十进制整数，而且矿l 至少有个大 的因子。 e l g a m a l 算法是非确定性的，因为密文受加密者所选的随机数k 影响，所以 同样的明文可能被加密成不同的密文。 e i g a m a l 密码体制： 设p 是一个素数而且离散对数在2 p 上是难解的，口z ；是一个本原元 p = z ：，c = z p z + p 。 e l g a m a l 密码体制被描述为： 山东大学颟f ：学位论文 k = ( p ，g ，口，) 5 口4 r o o d p 其中( p ，口，) 为公钥，口为私钥。 加密算法为： e k ( x ，) = ( y 1 ，y 2 ) ，y l = c t 。m o d p ，y 2 = z 矿m o d p ，随机数t e z p - 1 解密算法为： 一l d k ( y l ，y 2 ) = y 2 ( y 1 a ) m o d p e l g a m a l 密码体制的安全性是基于离散对数问题，在离散对数问题是难解的 假设下，e l g a m a l 密码体制是安全的。 3 数字签名体制 数字签名的出现是由于信息技术的迅速发展，人们希望用这利- 通过数字通信 网络所进行的快速的、远距离的电子签名代替f | 常生活中的手写签名。数字签名 同传统的手写签名相比有很大区别，数字签名是与所签文件物理上分离、可拷贝 的信息集合，一个数字签名方案至少应满足下面的三个条件： 1 、签名者事后不能否认自己的签名，即不可否认性； 2 、接收者能够验证签名，其他人不能伪造签名，即不可伪造性； 3 、 当双方对签名的真伪出现争执时，可以出第三方仲裁： 基于公钥密码体制和私钥密码体制都可以获得数字签名，特别是公钥密码体 制的产生为数字签名的研究和应用开辟了条广阔的道路，日前的数字签名