（计算机软件与理论专业论文）安全协议的研究与设计.pdf

摘要 摘要 随着信息产业的快速发展，信息的交流规模、内容和手段都很大的进 步。大型的计算机网络给人们的生活和工作带来了巨大的便利。然而，同 时也使人们感到其后潜伏着的不安全因素。病毒，黑客，网络犯罪给网络 用户造成的危害也越来越大。网络与信息安全的重要性不言而喻。因此， 保密通信和信息安全越来越受到人们的重视。本文对网络与信息安全的核 心，即密码技术中的公钥密码算法与身份认证协议进行研究，工作如下： 首先，设计了一个新的公钥加密体制，定义为s e e 密码体制，并分析 了该密码体制的安全性。结果表明，该密码体制的安全性基于计算d i f f i e h e l l m a n 问题和判定d i f f i e h e l l m a n 问题的难解性。在随机预言机模型下， 具有抵抗自适应性选择密文攻击的能力。而且，该密码体制具备很好的实 用性。 其次，提出了证明者与验证者共同协商挑战，使认证协议成为完备零 知识协议的方法。并根据这种方法提出了一个3 阶段的基于离散对数的身 份认证协议，该协议定义为3 - z k s c h n o r r 认证协议。并证明了这个协议是 完备零知识协议，其安全性完全等价于离散对数问题的难解性。另外，还 提出了该协议的一个优化的实现方案。该方案效率高，有很好的实用性。 最后，提出了验证者承诺挑战，使认证协议成为完备零知识协议的方 法，并根据这种方法提出了一个4 阶段的基于离散对数的身份认证协议， 该协议定义为4 - z k s c h n o r r 认证协议。并证明了这个协议是完备零知识协 议，其安全性完全等价于离散对数问题的难解性。另外，还提出了该协议 的一个高效实现方案。该方案有较好的实用性。 关键词离散对数；判定d i f f i e h e l l m a n 问题；计算d i f f i e h e l l m a n 问题 公钥加密；认证 燕山大学工学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n f o r m a t i o ni n d u s t r y , m u c ht e c h n i c a l p r o g r e s st a k e sp l a c ei ns c o p ea n dm e a n so fc o m m u n i c a t i o n p e o p l et a k e a d v a n t a g eo fn e t w o r k n e v e r t h e l e s sm o r ea n dm o r ep e o p l ef e e li n s e c u r i t y d u r i n gi n f o r m a t i o nc o m m u n i c a t i o n v i r u s ，i n t r u d e ra n dn e t w o r kc r i m et h r e a t e n t h e ma n dd oc a u s el o td a m a g e i tg o e sw i t h o u ts a y i n gt h ei m p o r t a n c eo f n e t w o r ka n di n f o r m a t i o ns e c u r i t y n o w , a b o u tc o m m u n i c a t i o na n di n f o r m a t i o n s e c u r i t yh a sc o m et op e o p l e sa t t e n t i o n s t u d yc r y p t o g r a p h i ca l g o r i t h m sa n d p r o t o c o l si sav e r yi m p o r t a n tr e s e a r c hs u b j e c t ，w h i c hi st h ec o r et e c h n i q u eo f t h ei n f o r m a t i o ns e c u r i t y c r y p t o g r a p h y t h i sd i s s e r t a t i o nf o c u s e so nt h e f o l l o w i n gr e s e a r c hw o r k ： f i r s t l y , t h ed i s s e r t a t i o nd e s i g n san e wp u b l i ck e ye n c r y p t i o ns c h e m ew h i c h i sd e f m e da ss e e c r y p t o s y s t e ma n da n a l y s i si t ss e c u r i t y i ti sp r o v e dt h a ti t s s e c u r i t yi sb a s e do nt h eh a r d n e s so f t h ec o m p u t a t i o n a ld i f f i e h e l l m a np r o b l e m a n dt h ed e c i s i o n a ld i t t i e h e l l m a np r o b l e m i ti ss e c u r ea g a i n s ta d a p t i v e l y c h o s e n c i p h e r t e x t a t t a c ki nr a n d o mo r a c l e m o d e l f u r t h e r m o r e ，t h i s c r y p t o s y s t e mi sv e r yp r a c t i c a l s e c o n d l y , t h ed i s s e r t a t i o np r o p o s e sam e t h o dt h a tt h ep r o v e ra n dv e r i f i e r n e g o t i a t et h ec h a l l e n g es oa st ot r a n s f e rt h ep r o t o c o lt ob eaz e r o k n o w l e d g e o n e t h e nan e w 3 - p h a s ei d e n t i f i c a t i o np r o t o c o li sp r e s e n t e da c c o r d i n gt ot h e m e t h o d t h i sp r o t o c o li sd e f m e da s3 - z k s c h n o r ri d e n t i f i c a t i o np r o t o c 0 1 i ti s p r o v e dt h a tt h i sp r o t o c o li sap e r f e c tz e r o k n o w l e a g eo n ea n di t ss e c u r i t yi s e q u a lt ot h eh a r d n e s so ft h ed i s c r e t el o g a r i t h mp r o b l e m a d d i t i o n a l l y , o n e i m p r o v e di m p l e m e n t a t i o no ft h ep r o t o c o li sp r o p o s e d ，w h i c hi se f f i c i e n ta n d v e r yp r a c t i c a l f i n a l l y , t h ed i s s e r t a t i o np r o p o s e sam e t h o dt h a tt h ev e r i f i e rp r o m i s e st h e a b s i r a c t c h a l l e n g es oa st ot r a n s f e rt h ep r o t o c o lt ob eaz e r o k n o w l e d g eo d e ，t h e nan e w 4 - p h a s ei d e n t i f i c a t i o np r o l o c o li sp r e s e n t e da c c o r d i n gt ot h em e t h o dw h i c hi s d e f m e da s4 - z k s c h n o r ri d e n t i f i c a t i o np r o t o c 0 1 i ti sp r o v e dt h a tt h ep r o t o c o li s ap e r f e c tz e r o k n o w l e d g eo n ea n di t ss e c u r i t yi se q u a 】t ot h eh a r d n e s so ft h e d i s c r e t el o g a r i t h mp r o b l e m a d d i t i o n a l l y , o n ee f f i c i e n ti m p l e m e n t a t i o no ft h e p r o t o c o li sp r o p o s e dw h i c hi sp r a c t i c a l k e y w o r d sd i s c r e t el o g a r i t h m ；d e c i s i o n a ld i f f i e - h e l l m a np r o b l e m ；c o m p u t a t i o n a ld i f f i e - h e l l m a np r o b l e m ；p u b l i c k e y e n c r y p t i o n ；l d e n t i f i c a t i o n m 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文安全协议的研究与设计， 是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所 取得的成果。据本人所知，论文中除已注明部分外不包含他人己发表或撰 写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在 文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字胡私音 日期：。ub g 年中月 日 燕山大学硕士学位论文使用授权书 安全协议的研究与设计系本人在燕山大学攻读硕士学位期间在导 师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本人 如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕山 大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论 文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可 以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分 内容。 保密口，在 年解密后适用本授权书。 本学位论文属于 不保密刚 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名：杨f 球 日期：年月 日 日期：2 帅6 年年月上7 日 第1 章绪论 1 1引言 第1 章绪论 随着计算机、通信技术和微电子技术的飞速发展，使信息业迅速发展。 信息交流的规模、内容、形式手段和频繁程度都呈现激增的态势。四通八 达的信息网络更是给人们的工作和生活带来了极大的便利。大型信息系统 将众多的计算机和智能化设备连在一个网络中，共享丰富的数据库信息和 计算机资源，存储大量的数据文件，完成异地之间的数据交换和通信。信 息系统的应用，加速了社会自动化的进程，减轻了日常繁杂的重复劳动， 同时也提高了生产效率，创造了经济效益。以此为基础建立起来的各种信 息系统和各种应用给人们的生活和工作带来了极大的方便。但同时也使人 们日益感受到其背后潜伏着的脆弱性和危险性。病毒、黑客、网络犯罪给 网络用户造成的危害越来越大。网络安全的重要性不言而喻。因此，通信 系统的保密和安全越来越受到人们的重视。要在开放的网络上进行数据传 输，就对保密通信提出越来越多，越来越高的要求。 1 2 可证明安全性的公钥密码体制 8 0 年代早期g o l d w a s s e r 和m i c a l i 在文献i 1 1 中提出了一个非同寻常的 方法：在公认的计算复杂度理论假设下，安全性是可以证明的。这一方法 就称为可证明安全性。它不仅是一种证明方法，也是一种设计协议的方法。 随着对可证明安全性的进一步研究，特别是人们对国际密码标准进行大量 分析之后，越来越意识到可证明安全性的重要性，可证明安全性也己成为 任何一个密码协议的基本要求。密码学家发现它对密码学，特别是公钥密 码体制的影响重大，并且对密码学实践也有重要的意义。 在文献 1 】中，g o l d w a s s e r 和m i c a l i 提出了概率加密这一概念，文中提 燕山大学工学硕士学位论文 出了这样的方法。对于具体的方案及其实现，假设数论中的某些问题，如 大整数分解问题或对模一个合数求二次剩余等问题是难解的，则证明一个 问题是难问题就意味着证明该问题与上述某一数论问题等价。换句话说， 对文献【1 】中加密方案安全性的威胁会产生个求解模一个合数的二次剩 余的有效算法。f 当我们认为该问题困难的时候，也就意味着加密方案是安 全的。) 简略地讲，对于一个给定的问题，达到可证明安全性就是要提供： ( 1 ) 安全目标的定义； f 2 ) 使用某些较低水平的原型的协议； ( 3 ) 一个证明( 称为一个“归约”) ，证明如果该原型确实能起到它应有 的功能( 或类似定义的功能) ，则该协议可以达到该安全定义。 可证明安全性使密码学从一门艺术成为一门科学，并且也成为密码学 领域中理论工作的主线。但是，因为可证明安全性是在计算复杂度假设下 建立的，强调的是多项式时间、可忽略概率等概念。所以密码学的实践家 们即使完全懂得可证明安全性的含义，也趋向于认为可证明安全性几乎没 有应用价值。为此，b e l l a r e 和r o g a w a y 等人提出了面向实际的可证明安全 性“1 ，强调的是确切的、具体的安全性，使得可证明安全性中的定义和归 约成为实际分析协议的强大工具，并得到了很多实用的成果，如o a e p ， d h i e s ，p s s ，p s s r 等体制用于支持a n s i ，i e e e ，i s o p k c s ，s e c g 等 标准。 公钥密码体制自1 9 7 6 年提出以来，已经得到了广泛的应用。1 9 8 4 年 g o l d w a s s e r 和m i c a l i 提出了概率加密的概念“1 ，使公钥密码体制有了更广 泛的用途。为了更好地使用和设计好的公钥密码体制，密码学家们对公钥 的安全性进行了大量的研究，他们提出了各种安全性目标( 定义) ，如：语 义安全性( s e m a n t i cs e c u r i t y ：s s ) 、不可区分性( i n d i s t i n g u i s h a b i l i t y ：i n d ) 、 不可展性( n o n - m a l l e a b i l i t y ：n m ) ”1 、明文可意识性( p l a i n t e x t a w a r e n e s s ；p a l 等，以选择明文攻击( c p a ) ，选择密文攻击( c c a l ) ”3 和适应性选择密文攻击 ( c c a 2 ) “1 为攻击类型，得到了很多的安全术语。对这些安全术语之间的关 系目前己经有了很好的研究，并得到了i n d 。c c a 2 确实是公钥密码体制的 2 第1 章绪论 良好的安全性定义的结论”1 。而对选择密文攻击包括( c c a i 和c c a 2 ) 的安 全性又是很多密码学协议中希望达到的安全性，因此人们就要研究达到这 种安全性的公钥体制，但遗憾的是这一安全性很难达到”1 。为此，近年来 很多密码学家致力于研究能够使得现有的体制达到这种安全性的技术”2 ， 试图以最小的代价获得这一安全性。d b l e i c h e n b a c h e r 指出了s s l ( 安全 套接层) 协议的一个缺陷”1 。他的攻击是对被认为是安全的协议和作为基 础的加密系统的直接攻击。如上面提到的，这样的攻击者不只是窃听，他 是主动攻击者，把仔细伪造的密文发送给s s l 服务器，然后观察服务器对 这些密文解密后返回的结果。根据这些结果，攻击者可以解开编码。 组合以上安全目标和攻击模型可以得到多种安全性定义，其安全性各 不相同。公钥密码系统的安全性主要考虑以下三种：在选择明文攻击下的 不可区分安全性，在非适应性选择密文攻击下的不可区分安全性和在适应 性选择密文攻击下的非延展安全性，分别记做i n d c p a ，i n d c c a l 和 n m c c a 2 。其中，i n d c p a 也被g o l d w a s s e r 和m i c a l i 定义为语义安全性。 实际上，公钥密码系统的安全性不仅与安全目标和攻击模型相关，也 和安全证明模型相关。目前，安全证明模型有两种。一种是标准模型，另 外一种是随机预言机模型。 标准模型是指安全证明仅仅依赖于标准代数难题。也就是说，攻击者 只有解开某个数学难题才能够攻破某个密码体制，否则不能。标准模型下 的安全也称为真实世界中安全，因为它们在现实中的安全性也能达到 n m c c a 2 。在标准模型下，i n d c c a 2 和n m c c a 2 安全性等价，而 i n d c p a 安全性次之”1 。有许多密码体制是i n d c p a 的，但却不是 i n d c c a 2 或n m c c a 2 的，如e 1 g a m a l 体制。 随机预言机模型是指安全证明不仅依赖于标准代数难题，而且还依赖 于一种很强的假设：存在给定输入，其输出是均匀的这样一种h a s h 函数”1 。 但是，根据s h a n n o n 的熵理论，一个确定的函数不可能“放大”熵，因此 以上假设的h a s h 函数是不可能存在的。所以，在随机预言机模型下安全 的公钥密码体制在现实中可能根本就不安全。c a n e r i 等人就给出了这样一 个密码体制。1 。该密码方案在随机预言机模型下是安全的，但无论h a s h 函 燕山大学工学硕士学位论文 数如何选择，在现实中根本就不安全。现在还不清楚这意味着什么。但它 至少提醒在现实中的密码方案，最好采用标准模型下安全的公钥密码体制， 而不要采用随机预言机模型下安全的公钥密码体制。 多年以来，没有加密方案在选择密文攻击下是安全的。m n a o r 和m y u n g 提出了第一个在非适应性选择密文攻击下可证明安全的方案“。接 着，d d o l e v , c d w o r k 和m n a o r 提出了一个在选择密文攻击下可证明安 全的方案“。这些方案在标准难题假设下是可证明安全的，但是不实用， 这是因为密码体制为了非交互式零知识证明，需要代价高昂的构造。 i d a m g a r d 提出了一个实用方案“。作者猜想这个方案对非适应性选 择密文攻击是安全的。但是，这个方案没有证明是安全的。实际上，这个 方案在选择密文攻击下被证明是不安全的。 y z h e n g 和j s e b e r r y 提出了一个实用方案”，作者猜想这个方案对选 择密文攻击下是可证明安全的，但是到目前还没有基于标准难题的安全证 明。 c h l i m 和pj l e e 提出了实用的方案“。但是后来被y f r a n k e l 和 m y u n g 攻破“。 r c r a m e r 和v s h o u p 提出来了第一个实用的而且在标准难题假设下可 抵挡选择密文攻击的密码方案“”。这个方案基于e 1 g a m a l 加密方案，生成 了一个扩展的私有密钥和公有密钥。一个信息m ，也叫做明文，用公有密 钥加密成密文t 。只有拥有正确私有密钥的接受者才能解密密文t 。但是在 解密前，有一个密文t 的验证。这个验证可以证明密文t 的合法性。也就 是说，密文t 被检查。如果密文是合法的，则被解密成明文：如果密文t 是不合法的，也就是说，密文t 是无效的，则被拒绝。如果判定d i f f i e h e l l m a n 难解假设和h a s h 函数是无碰撞性假设成立，那么这个加密方案对非适应性 选择密文攻击和适应性选择密文攻击都是安全的。但是该方案的公共密钥 和私有密钥都扩展的较长，效率也较低。 在另外一个不同的方向，m b e l l a r e 和e r o g a w a y 提出了实用的方案“”。 在随机预言机模型下这些方案可证明是安全的。另外，还有一些其它的在 随机预言机模型下可证明安全的方案“8 ”1 。 4 第1 章绪论 d b o n e h 和m f r a n k l m 提出了一个基于身份的加密方案1 ”。这个方案 在随机预言机模型下被证明是适应性选择密文攻击安全的，并在一种很弱 的攻击模型下被证明是标准模型下安全的”“”j 。但实际上，这个方案在现 实中对适应性选择密文攻击并不安全。 d b o n e h 和m f r a n k l i n 提出了另一个基于身份的加密方案”“。这个方 案是标准模型下安全的。但是效率太低，根本就不实用。 b r e n tw a t e r s 提出了另一个基于身份的加密方案”。这个方案是标准模 型下是非适应性选择密文攻击安全的，但没有适应性选择密文攻击的安全 证明。 总的来讲，标准模型下n m c c a 2 公钥密码体制研究进展缓慢，目前 只有c r a m e r - s h o u p 这一项实用研究成果。 证明一个体制是1 n d c c a 2 时，我们使用可证明安全性的方法，即寻 找一个有效的归约，这也正是可证明安全性方法的难点，也是很多体制无 法达到可证明安全的原因。己知的在理论上对选择密文攻击可证明安全的 公钥体制大多数都不实用，而且证明也是构造性的，比较复杂，各种抗选 择密文攻击的技术和研究正是为了解决这一矛后，人们实际采用的一般方 法有采用h a s h 函数构造密文合法性的嵌入式系统。采用单、双钥体制混合 的方法，以及采用非交互式零知识证明构造密文合法性的方案等。其中包 括s h o u p 提出的几个k e m - d e m 方案【2 5 】，f u j i s a k i 和o k a m o t o 提出的f o 方案口“，p o i n t c h e v a l 提出的h d r s a 方案【2 ”，a b d a l l a 、b e l l a r e 和r o g a w a y 提出的d h a e s 方案【2 8 1 ，s h o u p 提出的c r a m e r s h o u p 体制的一个变形1 2 ，i ， 以及o k a m a t o 和p o i n t c h e v a l 提出的r e a c t 方案m 。 1 3 零知识身份认证协议 在现实生活中，我们常将某个自己掌握的知识公之于众，以期让其他 人相信你确实掌握了该知识。但是这个知识有可能是一个不可告人的秘密， 我们不能把它公之于众。如何才能在不向别人泄露任何秘密的前提下，使 别人相信秘密的存在是一个困难的问题。零知识证明为此类问题提供了一 燕山大学工学硕士学位论文 个解决方法。 1 9 8 5 年，g o l d w a s s e r ，m i c a l i 和r a e k o f 首先提出了零知识证明概念”， 证明者可以利用单向函数进行零知识证明。该证明采用了交互式的形式， 验证方向证明方提出系列的问题，如果证明方确实知道其声称掌握的秘 密，则可以正确回答全部问题；如果证明方并不知道该秘密，仍有一半的 机会答对任何一个问题，在很多问答的交互过程后，验证方可以相信证明 方知道该秘密。零知识证明过程是一个规则性很强的多步骤过程，参与证 明的双方( 证明者与验证者) 按照预先约定的规则和步骤进行交互，传送信 息。在每一轮证明中，验证者判断证明是否有误，若无误则继续下一轮证 明。该过程不停地循环，直到验证者察觉到一个错误的产生( 即证明失败1 或者满足于当前证明的可信程度而不再提出下一轮证明。 可以看出零知识证明在形式上是一种交互式协议，我们称之为零知识 证明协议。伴随着零知识证明的提出，不经意传输、不经意签名、盲签名、 保密选举、保密的多方计算和数字现金等一系列具有隐藏目的的交互式协 议活跃在应用密码学的舞台上。简言之，零知识证明的目的就是使人相信 证明而无需细节。这是一个引人入胜的话题。 零知识在密码领域中居于核心地位，可以用来定义和证明各种密码体 制的安全性。特别地，基于零知识可以构造许多关于身份的证明，而证明 身份是电子商务系统的基本部分，同时也可以实现秘密共享协议中对恢复 秘密之前进行验证的有效手段。 1 4 本文研究内容与结构 本文的以下部分组织结构和主要内容如下： 第2 章是理论基础。首先介绍了实现密码系统的有关数学背景，然后 介绍了公钥密码系统的构建基础单向陷门函数的有关理论和作为公钥 密码基础的几个数学难题假设，最后介绍了零知识证明的一些理论基础和 相关知识。 第3 章是s e e 公钥密码体制的研究与设计。设计了s e e 公钥密码体 第1 章绪论 制。该体制的安全性基于d i f f i e h e l l m a n 计算问题和d i f f i e h e l l m a n 判定问 题。在随机预言机模型下，具有抵抗自适应选择密文攻击的能力。此外， 该密码体制效率高，有很好的实用性。 第4 章是3 - z k s c h n o r r 认证协议研究与设计。提出了证明者与验证者 共同协商挑战，使认证协议成为完备零知识协议的方法。并根据这种方法 提出了一个3 阶段的基于离散对数的身份认证协议，该协议定义为 3 - z k s c h n o r r 认证协议。并证明了这个协议是完备零知识协议，其安全性 完全等价于离散对数问题的难解性。另外，还提出了该协议的一个高效实 现方案。该方案具备很好的实用性。 第5 章是4 - z k s c h n o r r 认证协议研究与设计。提出了验证者承诺挑战， 使认证协议成为完备零知识协议的方法，并根据这种方法提出了一个4 阶 段的基于离散对数的身份认证协议，该协议定义为4 - z k s c h n o r r 认证协议。 并证明了这个协议是完备零知识协议，其安全性完全等价于离散对数问题 的难解性。另外，还提出了该协议的一个高效实现方案。该方案具备较好 的实用性。 最后是总结。对本文进行总结和归纳，指出其需进一步完善的地方和 以后的工作方向。 燕山大学工学硕士学位论文 2 1 数学背景 第2 章理论基础 这里介绍一些公钥密码的基本复杂性理论、数论和单向陷门函数概念、 定义、定理等。 2 1 1 复杂性理论 近3 0 年来，计算机科学家和数学家在计算复杂性理论方面做了很多研 究，它是公钥密码的理论基础。 从理论上讨论何种问题可由计算机来完成，何种问题则不能，属于“可 计算性理论”的范畴。理论上可计算的问题在实际上是不是一定能行得通， 属于计算复杂性理论的研究范畴，这就要作时间、空间的复杂性分析。 一般度量问题的复杂性都以问题的规模为标准，在问题的规模玎的多 项式时间内完成的问题称为属于多项式类p 的问题。例如求两个n n 阶矩 阵的乘积可在做 3 乘法的时i n 内完成，则称它为o ( n 3 ，即所需时间不超 过勋3 次运算。 可在n 的多项式时间内完成的问题为存在有效算法的问题。 还有一类目前还未找到有效算法，但解可在多项式时间内给予验证的 问题为n p 类。所有p 类问题的解都可以在多项式时间内给予验证，故： p 三n p 俨类中还有一类问题称为 驴完全类，所有n p 类问题都可以转换为 尸完全类中的问题。可见p 完全类是肝类中困难程度最大的一类问题。 胛完全类中的问题困难程度相当，这一类问题只要有一个问题有多项式 算法，则整个n p 类问题都属于尸。 由于目前不存在有效算法来解决p 完全类问题。因此，若想破译一 密码体制就相当于解一个p 完全问题，很显然该密码体制是安全的。所 第2 章理论基础 以，n p 完全问题十分适合用于构造密码体制。 2 1 2 数论 数论是近代密码学中应用最多的数学理论。这里仅介绍本论文用到的 相关数论知识。 2 1 1 2 1 同余及模运算令三个整数口，b 及订0 ，称口在模”时与b 同余， 当且仅当口与b 的差为 的整数倍。即d b = k n ，其中j i 为任一整数。若口 与b 在模胛中同余，则可写成口；b m o d n 。 由上述定义可知：若d 与b 在模y 中同余，则n 必整除d 与b 的差，即” 整除盯一b ，在符号上写成力i 一b ) 。 利用同余的概念，所有整数在模订中被分成, 个不同的剩余类，以h 整 除余数相同的数为一剩余类，以n 整除余数为1 的数为一类，余2 的数为 一剩余类，依此类推。若将每一剩余类中取一数为代表，形成一集合，则 此集合称为模n 的完全剩余系，以z 。表示。很明显地，集合 o ，l ，2 ，, 一1 为模 的一完全剩余系。 在同余的基本运算中，存在以下的基本定理。 定理2 1 ：口= a r o o d ”。 定理2 2 ：若口= b m o d 胛，贝0 b ea r o o d 。 定理2 3 ：若口b m o d , 且b ic m o d r ，则d ；c r o o d 。 定理2 4 ：若口b r o o d 疗且c ；d r o o d ，则： ( d + c ) i ( 6 + d ) m o d n ， 口一f l ；6 一d ) m o d n ， b c ) i ( b d ) m o d n 定理2 5 ：( a + b ) m o d n = m o d n ) + ( b m o d n ) m o d n ； 0 一b ) m o d n = 盼r o o d n ) 一( b m o d n ) m o d n ； ( a x b ) m o d n = 盼m o d n ) x ( b m o d n ) m o d n 。 定理2 6 ：若b d r o o d 订且c ；d r o o d h 及f 与行互素，则： 口eb r o o d r 在模n 的完全剩余系中，若将所有与n 互素的剩余系形成一集合，则 燕山大学工学硕士学位论文 此集合称为模n 的既约剩余系，以z ：表示。 例如”= 1 0 时， o ，l ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 为模1 0 的完全剩余系；而 l ，3 ，7 ，9 为 模1 0 的既约剩余系。在模”中取既约剩余系的原因为，在模h 的既约剩余 系中取一整数a ，则必存在另一整数b ( 属于此既约剩余系) 使得 a b ；1 m o d ”且此解唯一。 若a b = i m o d n ，则b 为a 在模行的乘法逆元，b 可表示为口。定理2 7 说明上述的叙述为正确。 定理2 7 ：若g c d ( a ， ) = 1 ( g c d ( a ，”) 表示盯与珂的最大公因子) ，则存在 唯一整数b ，0 b 1 ，且g c d ( b ，竹) = 1 ，使得a bz l m o d n 。 定义2 1 ：令庐0 ) 为小于n 的且与n 互素的正整数个数。即( ) 为模h 既约剩余系中所有元素的个数，此庐( 即) 称为欧拉函数。 对于任一素数p ，有：妒0 ) = p 一1 。 对于两个不同的素数p 和g ，则对h = p q ，有： 咖o ) = 咖0 9 ) = 咖0 ) 妒q ) = 0 1 x g 1 ) 定理2 8 ：令乜，吃，( 。) j 为模胛的一既约剩余系，胃g c d ( a ，聆) = 1 ，则 集合 ，a t 2 ，“ 也为模珂的一既约剩余系。 2 1 2 2 欧拉定理欧拉定理是数论中的一个重要定理，也是构建r s a 公 钥密码体制的理论基础。 定理2 9 ：欧拉定理( e u l e r st h e o r e m ) 若g c d ( a ，胛) = 1 ，则：a “je l m o d n 。 欧拉定理的另一种等价形式也很有用： 盯“h 1 口m o d 拧 欧拉定理的这一推论在说明r s a 算法的有效时是很有用的。给定两个 素数p 和g ，以及整数竹= p q 和m ，其中0 0 。限制算法仅考虑了正整数，但是，这是可以接受 的，因为根据最大公因予的有关性质，；有g c d ( a ，6 1 = g c d o a l ，1 0 t ) 。算法的详 细描述如下： e u c l i d 似，f ) ( 1 ) 工一d ；y 一厂 ( 2 ) i fy = 0r e t u r nx = g c d ( d ，f ) ( 3 ) r = x m o d y ( 4 ) x 一】， ( 5 ) 】，一r ( 6 ) g o t o ( 2 ) 如果g c d ( d ，) = 1 ，那么d 有一个模，的乘法逆元。即对小于f 的正整 数d ，存在一个小于，的正整数d ，使得d d 一；l m o d f 。对欧几里德算 法进行扩展使得它不仅能找出g c d ( d ，f ) 。如果g c d p ，) = 1 ，算法还能返回 d 的乘法逆元，算法如下： e x t e n d e d e u c l i d q ，f 1 ( 1 ) ，x ：，工，) 一( 1 ，0 ，f ) ； ( 2 ) 纯，艺，e ) 一( o ，l ，d ) ( 3 ) i fe = 0r e t u r nx 3 = g c d ( d ，f ) ；无逆元 ( 4 ) i f 匕= 1r e t u r n 匕= g c d ( d ，f ) ：e = d 。m o d f ( 5 ) q = l x ，r , j ( 6 ) 旺，疋，乃) 一阮- o r , ，x ：一q e ，x 3 一q y s ) 燕山大学工学硕士学位论文 ( 7 ) 伍，：，局) 一瓴，艺，e ) ( 8 ) 佤，e ，e ) 一亿，疋，五) ( 9 ) g o t o ( 2 ) 2 1 3 单向陷门函数 数据加密解密算法信息系统安全的一个非常重要的手段就是加密技 术。它的方法核心就是既然网络本身并不安全可靠，那么所有重要信息就 全部通过加密处理。通常，我们将源信息称为明文，为了保护明文，可以 将其通过某种方式变换成无法识别的密文，这个变换过程我们称之为加密； 另一方面，密文可以经过相应的逆变换再还原成明文，这个变换过程称之 为解密。保密算法是用于加密解密变换的数学函数，通常使用两个相关的 函数，解密函数是加密函数的反函数，反之亦然。 假设r e ( m e s s a g e ) 代表明文，c ( c i p h e r t e x t ) 代表密文，e ( e n c i p h e r i n g ) 代表 加密变换，d ( d e c i p h e r i n g ) 代表解密变换，则上述加密解密过程可以用数学 形式描述为： 产e ( m ) m = d ( c ) 经过变换后的信息，即使被偷窃，窃取者由于没有解密手段而无法理 解其含义，这样起到了保护源信息的作用。而信息的合法接收者具有解密 手段，从而可以获得明文信息。当然为了使密文信息安全可靠，要经常更 新算法，增加算法的安全强度，这就是密码学研究的中心内容。 加密解密的技术主要分两种： 单匙技术。这种技术无论加密还是解密都是用同一把钥匙( s e c r e tk e y ) 。 这是比较传统的一种加密方法。发信人用某把钥匙将某重要信息加密，通 过网络传给收信人，收信人再用同一把钥匙将加密后的信息解密。这种方 法快捷简便，即使传输信息的网络不安全，被别人截走信息，加密后的信 息也不易泄露。 但这种方法也存在一个问题，即如果收信者和发信者不在同一地理位 置，那么他们必须确保有一个安全渠道来传送加密钥匙。但是如果确实存 第2 苹理论基础 在这样一个安全渠道( 如通过信差、长途电话等等) ，他们也就不需要加密。 后来出现的双匙技术解决了这个难题。 双匙技术。此技术使用两个相关互补的钥匙：一个称为公用钥匙( p u b l i c k e y ) 另一个称为私人钥匙( s e c r e tk e y ) 。公用钥匙是大家被告知的，而私人钥 匙则只有每个人自己知道。发信者需用收信人的公用钥匙将重要信息加密， 然后通过网络传给收信人。收信人再用自己的私人钥匙将其解密。除了私 人钥匙的持有者，没有人一即使是发信者一能够将其解密。公用钥匙是公 开的，可以通过网络告知发信人( 即使网络不安全) 。而只知道公用钥匙是 无法导出私人钥匙的。现有软件如i n t e r n e t 免费提供的p g p ( p r e t t yg o o d p r i v a c y ) 可直接实现这些功能。 加密技术主要有两个用途，一是加密信息，正如上面介绍的：另一个 是信息数字签名，即发信者用自己的私人钥匙将信息加密，这就相当于在 这条消息上署上了名。任何人只有用发信者的公用钥匙，才能解开这条消 息。这一方面可以证明这条信息确实是此发信者发出的，而且事后未经过 他人的改动( 因为只有发信者才知道自己的私人钥匙) ：另方面也确保发 信者对自己发出的消息负责，消息一旦发出并署了名，他就无法再否认这 一事实。 如果既需要保密又希望署名，则可以将上面介绍的两个步骤合并起来。 即发信者先用自己的私人钥匙署名再用收信者的公用钥匙加密，再发给对 方。反过来收信者只需用自己的私人钥匙解密，再用发信者的公用钥匙验 证签名。这个过程说起来有些繁琐，实际上很多软件都可以只用一条命令 实现这些功能，非常简便易行。 1 9 7 6 年d i f f i e 和h e l l m a n 提出公开密钥密码体制的概念时，他们并未 能提出一个真正可以实现的公开密钥密码体制，只是推测公开密钥密码体 制“可能”存在。 为了说明公钥密码体制可能存在，d i f f i e 和h e l l m a n 提出了单向函数 及单向陷门函数的定义。 定义2 2 ：单向函数( o n e - w a yf u n c t i 0 1 1 ) 一函数厂若满足下列二条件，贝, l j f 称为单向函数。 燕山大学工学硕士学位论文 ( 1 ) 对于所有属于厂定义域的任一x ，可以很容易算出“) 叫。 ( 2 ) 对于几乎所有( a l m o s ta 1 1 ) 属于厂值域的任一y ，则在计算上不可能 求出x ，使得d x ) = y 。 单向函数很多，例如因子分解问题。 已给一大的奇数p ，欲判断其是否为素数，现已有许多有效的方法。 以现在的计算机能力而言，应属容易。即使聍为2 5 6 或5 1 2 位，仍可在1 0 m i n 内完成。若已给两个大素数p 及g ，欲求出其乘积n = p q ，则只需要一次 乘法。但若已给胛，欲分解h 求得确实的p 及口，称为因子分解问题f a c ( f a c t o r i z a t i o np r o b l e m ) 。这是几千年来数学界无法突破的问题。也是属于 p 完全类问题。当行很大时，分解n 为计算上不可能。另外，还有许多数 学问题为单向函数，如求离散对数问题，背包问题等。 定义2 3 ：单向陷门函数( o n e w a yt r a p d o o rf u n c t i o n ) 。 一“可逆”函数f 若满足下列二条件，则，称为单向陷门函数。 ( 1 ) 对于所有属于f 定义域的任一石，可以很容易算出f ( x ) = y 。 ( 2 ) 对于几乎所有属于f 值域的任一y ，则在计算上除非获得陷门，否 则不可能求出x ，使得工= f 。( y ) ，f - 1 为f 的反函数。但若有一额外数据 z ( 称为陷门) ，则可以很容易求出x = f 。1 ( y ) 。 由上述定义可知单向函数与单向陷门函数的差异在于可逆与不可逆。 d i 脓和h e l l m a n 当初认为，若单向陷门函数f 存在，则任何单向陷门函 数f 均可用来设计公开密钥密码体制。因为任何人均可将明文x 经f f 公开 密钥) 加密得到密文y ；f ( x ) 。而任何人均无法由密文求得明文。但拥有解 密密钥( 陷门z ) 的接受方，却可以很轻易由密文y 解出明文x 。 公钥密码体制都是基于一些数学难题。以下给出几个基本的数学难题 假设，它们是我们讨论以下章节的基础。这些难题假设也是构建公钥密码 的基础，包括离散对数问题，判定d i f f i e h e l l m a n 问题和计算d i f f i e h e l l m a n 问题。 定义2 4 ：离散对数问题l 问题) ( 在有限域中) 。 输入：有限域f 。的描述； g ef q 0 ) ：n 0 ) 的一个生成元； 1 4 第2 章理论基础 h uf 。 0 。 输出：唯一的整数a q ，满足 = 旷。 著名的e 1 g a m a l 密码体制就是基于离散对数问题。目前，解离散对数 问题的平凡算法有很多 3 1 , 3 2 】，包括s h a n k s 算法【”】、p o h l i g h e u m a n 算法【3 4 】 和指数计算方法l ”i 。 定义2 5 ：判定d i f f i e h