《信息安全技术.ppt》由会员分享，可在线阅读，更多相关《信息安全技术.ppt（90页珍藏版）》请在课桌文档上搜索。
1、信息安全技术,密码技术,提纲,密码技术概述对称密码技术非对称密码技术密钥分配与管理技术数字签名技术信息隐藏技术,提纲,密码技术概述对称密码技术非对称密码技术密钥分配与管理技术数字签名技术信息隐藏技术,知识点,密码学的基本概念密码学的发展历程密码学的应用密码学的技术基础,什么是密码学,密码学研究通信安全保密的学科密码编码学研究将明文转换成密文的技术寻找生成高强度密码的有效算法密码分析学研究分析破译密码的方法破译密码、伪造密码，窃取机密信息,盾,矛,密码体制的组成,密码体制的组成全体明文的集合M明文空间全体密文的集合C密文空间全体密钥的集合K密钥空间加密算法E，由加密密钥控制的加密变换的集合解密算
2、法D，由解密密钥控制的解密变换的集合,密码技术的发展历程,古典密码技术阶段1949年现代密码技术阶段1949,古典密码技术阶段,古典密码技术阶段早在四千年前，埃及人就开始使用密码技术思路”看“的到，但”看“不懂”看“的懂，但”看“不到”看“不到，也”看“不懂技术暗语、文字游戏以及其他信息隐藏方法1918年，William F.Friedman“The Index of Coincidence and Its Applications in Crytography”(重合指数及其在密码学中的应用）特点基本依靠人工或借助器械小范围应用，少数人掌握加密/解密更多的是依靠经验和直觉艺术的成分 科学的成
3、分,现代密码技术阶段（1/10）,香农（C.E.Shannon)1949在贝尔系统技术杂志上发表了“The Communication Theory of Secrecy System”（保密系统的通信理论）奠定了密码学的理论基础艺术科学（但仍不失艺术性的一面）,现代密码技术阶段（2/10）,戴维.卡恩 1967整理一战和二战的历史资料，出版了破译者(The Codebreakers)为密码技术公开化、大众化奠定了基础20世纪70年代，随着IBM等公司陆续发表的关于密码技术的报告，使密码技术为更多的人所了解,现代密码技术阶段（3/10）,W.E.Diffie&M.E.Hellman 1976发
4、表“New Direction in Cryptography(密码学新方向）”，提出了一种全新的密码设计思想（非对称加密），首次证明了在发送端和接收端之间不需要传送密钥的保密通信是可能的开创了公钥密码技术的新纪元使科学高效的密钥管理体制的建立成为可能,现代密码技术阶段（4/10）,美国国家标准局NBS（现在的NIST）1977正式公布了数据加密标准DES(Data Encryption Standard)DES算法公开，使密码技术的研究进入一个崭新的时代DES在相当长的时间内成为事实上的国际标准由于安全性原因，1998年正式退役,现代密码技术阶段（5/10）,李维斯特（R.L.Rivest）
5、,沙米尔（A.Shamir）,艾德曼（L.Adleman）1978提出RSA公钥密码技术杰出的公钥密码技术,现代密码技术阶段（6/10）,Bennett.Charles H&Brassard.Gill 1984提出量子密码技术BB84协议基于量子定律的密码技术可以抗击具有无限计算能力的攻击量子计算机诞生后，量子密码技术有可能成为唯一真正安全的密码技术,现代密码技术阶段（7/10）,N.Koblitz&V.Miller 1985将椭圆曲线理论引入公钥密码技术椭圆曲线密码体制公钥密码技术研究的新亮点较之RSA相同的安全级别下，具有更短的密钥长度实现速度快,现代密码技术阶段（8/10）,R.Math
6、ews&D.Wheeler etc.1989将混沌理论应用到序列密码及保密通信理论中为序列密码技术的研究开辟了新的途径混沌理论的应用主要用于密钥的生成*序列密码利用少量的密钥（制乱元素，保密的）通过某种复杂的运算（密码算法，公开的）产生大量的伪随机位流，用于对明文位流的加密。解密是指用同样的密钥和密码算法及与加密相同的伪随机位流，用以还原明文位流。,现代密码技术阶段（9/10）,Joan Daemen&Vincent Rijmen 2000Rijndael密码算法AES算法（Advanced Encryption Standard)新一代数据加密标准,现代密码技术阶段（10/10）,欧盟 20
7、00启动欧洲数据加密、数字签名、数据完整性计划NESSIE目的：提出一套高鲁棒性的密码体制包括分组密码、序列密码、散列函数、消息认证码（MAC）、数字签名和公钥加密密码标准,密码技术的作用,密码技术作用基本功能提供保密性，使非授权用户无法知道信息的真实内容其他功能鉴别：信息的接收者应能够确认信息的真实来源完整性：信息的接收者应能验证信息在传输过程中有没有发生改变不可否认性：信息的发送方不能否认已发送过的信息,密码技术的应用,密码技术的应用所有需要信息保密的领域军事政治企/事/工/商业个人信息时代尤为重要,知识点,密码学的基本概念密码学的发展历程密码学的应用密码学的技术基础技术基础密码技术分类密
8、码分析计算复杂性理论,密码学的技术基础,Kerckhoff 假设对于所有的密钥，加密和解密算法迅速有效；密码体制的安全性不依赖于算法的保密，而是依赖于密钥的保密当前和今后较长的时间内，密钥仍然是密码体制安全性的关键；密钥的产生、分配和管理是密码技术中重要的研究方向现代密码技术普遍依赖于数学无论是加密/解密技术，还是密码分析技术,密码技术的分类,密码技术的可破译分析,密码技术的可破译分析根据密文可以推算出明文或密钥，或者能够根据明文和相应的密文推算出密钥，则该密码技术是可破译的；否则是不可破译的；根据kerckhoff假设只要密钥是保密的、安全的，则密码技术就是安全的,密码分析的主要方法（1/3
9、）,穷举法通过试遍所有的明文或密钥来进行破译穷举明文将可能的明文进行加密，将得到的密文同截获的密文进行比对，从而确定正确的明文；穷举密钥用可能的密钥解密密文，直到得到有意义的明文，从而确定正确的明文和密钥对抗手段在明文和密文中增加随机冗余信息增加密钥长度，提高生成密钥的随机性,密码分析的主要方法（2/3）,统计分析法通过分析密文、明文和密钥的统计规律来达到破译密码技术的方法；对抗手段设法使明文的统计特性与密文的统计特性不一样,密码分析的主要方法（3/3）,密码技术分析法根据所掌握的明文、密文的有关信息，通过数学求解的方法找到相应的加解密算法原则上，受密码技术分析破译的密码技术已经不能使用对抗手
10、段选用具有坚实数学基础和足够复杂的加解密算法,对密码技术进行攻击的4种情况,惟密文攻击密码分析者仅知道一些密文，并试图恢复尽可能多的明文，并进一步推导出加密信息的密钥已知明文攻击分析者不仅知道一些信息的密文，而且还知道与之对应的明文，根据明文和密文试图推导出加密密钥或加密算法选择明文攻击分析者可以选择一些明文，并得到相应的密文，而且可以选择被加密的明文，并试图推导出加密密钥的酸法。选择密文攻击分析者可以选择不同的密文，并能得到相应的明文，并试图推导出加密密钥。其他自适应选择明文攻击、自适应选择密文攻击，,攻击方案的选择取决于能够掌握的可靠信息和所具有的技术手段,计算复杂性理论,密码技术的安全性
11、在密码技术领域，安全性是相对的，而不是绝对的可证明安全性从理论上证明破译某个密码系统的代价不低于求解某个已知的数学难题计算安全性用已知的最好算法和利用现有的最大计算资源，仍然不可能在合理的时间内完成破译该系统所需要的计算可证明安全性和计算安全性统称实际安全性,密码安全性理论的基础,密码安全性理论的基础计算复杂性理论给出问题求解困难性的数量指标，并确定其安全性密码分析所需的计算量是密码体制安全性的生命指标如果破译一个密码体制所需要的时间为指数阶的，则它在计算上是安全的实际上也是安全的Diffie和Hellman通过证明指出，NPC问题更适合构造密码体制,提纲,密码技术概述对称密码技术非对称密码技
12、术密钥分配与管理技术数字签名技术信息隐藏技术,知识点,对称密码技术概述古典密码技术数据加密标准DES国际数据加密算法IDEA高级加密标准AES,对称密码技术概述,对称密码技术加密密钥和解密密钥相同解密算法是加密算法的逆算法特点密钥必须安全传送和妥善保管典型代表古典密码技术序列密码技术分组密码技术（如DES，IDEA，AES等）,对称密码技术的安全性,对称密码技术的安全性依赖两个因素加密算法必须足够强，仅基于密文本身去解密在实践是不可能的加密方法的安全性依赖于密钥的安全性，而不是算法的秘密性,对称密码技术的应用,对称密码技术的应用优势实现速度快，算法公开，应用广泛，固化成本低存在的问题密钥的分发
13、与管理非常复杂，代价高N个用户的网络，需要N（N-1）/2个密钥不能实现数字签名,知识点,对称密码技术概述古典密码技术数据加密标准DES国际数据加密算法IDEA高级加密标准AES,DES产生的历史背景,DES产生的历史背景美国国家标准巨为了满足计算机通信网络的发展对安全保密的需求，实现系统同一水平的安全性和兼容性，降低数据加密产品的生产成本，推广使用密码算法，而公开征集一种用于政府部门及民间进行计算机数据加密的密码算法1973年5月13日向社会首次公开征集不理想1974年8月27日向社会再次公开征集IBM公司的方案1976年11月23日被采纳，并授权在非密级的政府通信中使用1977年1月15日
14、公布DES正式文本,DES的使用,DES的使用存在疑问，但仍被迅速推广使用最主要质疑：密钥长度不足（56位）在最初的使用中，DES没有受到实质性威胁顺利通过1983、1987、1992、1994年的安全性评估到1998年以后不再使用近年来，DES的问题逐渐暴露出来1991年，RSA数据安全公司宣布该公司发起的对56位DES的攻击已经由一个称为电子边境基金会的组织在22小时15分钟内完成（通过互联网上100000计算机合作完成）有必要以新的对称加密技术取代DES,64位码,64位码,初始变换,逆初始变换,乘积变换,明文,密文,输入,输出,IP,IP-1,DES实现过程,DES设计原理,重复交替使
15、用选择函数S和置换运算P两种变换（confusion+diffusion)使用Feistel方法16次迭代变换每一次迭代变换都是以前一次迭代变换的结果（第一次以x0=L0R0作为输入）和用户密钥扩展得到的子密钥Ki作为输入；每一次迭代变换只变换一半数据，将输入数据的右半部分经过函数f后，将其输出与输入数据的左半部分进行异或运算，并将得到的结果作为新的右半部分，而原来的右半部分变成新的左半部分。）在最后一轮，左、右半部分并围变换，而直接将R16L16并在一起作为末置换的输入。,f函数,f函数非线性函数，DES算法 安全性的关键以长度为32位的比特串作为输入，产生的中间结果为48位，并在最终产生长
16、度为32位的比特串作为输出F以前一轮迭代的结果Ri-1作为输入，首先根据一个固定的扩展函数E“扩展”为48位。与子密钥异或：f将置换得到得到48位输出与子密钥Ki（48位）进行异或S盒替代：以6比特为单位将与子密钥异或得到的结果分为8个小组，并将它们送入替代函数（S盒）中进行替代运算S盒是函数f的核心，是非线性的。48位比特串经过8个S盒后，得到8个4位的分组，重新组合后形成一个32位的比特串。P盒置换：将S盒输出的32位比特串根据固定的置换P盒置换到相应的位置。P盒置换后得到的输出就是函数f(Ri-1,ki)的结果,输入（64位）,58 50 42 34 26 18 10 260 52 44
17、 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7,输出（64位）,初始变换IP,L0（32位）,R0（32位）,加密函数(A,Ki),A(32位),加密时A=Ri;解密时A=Li;,48位结果,Ki,+,选择函数组(S1S8),32位结果,f(A,Ki),置换运算P,32位,左32位,右32位,Li-1,Ri-1,48位(明文),64位密钥,作第i次迭代的
18、计算机子密钥Ki,密钥程序表,48位(密钥),8组6位码,模2加,S盒输入：6位输出：4位,+,32位,置换,32位,32位,Li,Ri,左32位,右32位,Ri-1,Li-1,模2加,+.+,乘积变换中的一次迭代,A,32位,32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 1,选择运算E,选择运算E的结果,48位,选择运算E,扩展函数E的第一分组的工作过程,0 1 2 3 4 5 6 7 8 9
19、10 11 12 13 14 150 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 71 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 82 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 03 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13,S1,1 0 1 1 0 0,102,0 0 1 0,输入6位,输出4位,使用选择函数S1的例子,64位码,64位码,初始变换,逆初始变换,L0,明文,密文,输入,输出,IP,IP-1,R0,选择函数的输出,（32位）,16 7 20 2129 12
20、28 17 1 15 23 26 5 18 31 10 2 8 24 1432 27 3 919 13 30 622 11 4 25,置换P,加密函数的结果,（32位）,置换码组 输入（64位）,40 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 25,输出（64位）,逆初始变换IP-1,64位密钥,C0
21、(28位),D0(28位),循环左移,循环左移,C1(28位),D1(28位),K1,(48位),(56位),循环左移,循环左移,Ci(28位),Di(28位),Ki,(48位),(56位),密钥表的计算逻辑,循环左移：1 1 9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 1,57 49 41 33 25 17 9 1 58 50 42 34 26 1810 2 59 51 43 35 2719 11 3 60 52 44 36,63 55 47 39 31 33 15 7 62 54 46 38 30 2214 6 61
22、53 45 37 2921 13 5 28 20 12 4,置换选择1,密钥（64位）,C0(28位),D0(28位),Ci(28位),Di(28位),14 17 11 24 1 5 3 28 15 6 21 1023 19 12 4 26 816 7 27 20 13 241 52 31 37 47 5530 40 51 45 33 4844 49 39 56 34 5346 42 50 36 29 32,Ki(48位),置换选择2,L0R0 IP(明文)L1R0 R1 L0(R0,K1)L2R1 R2 L1(R1,K2)L16R15 R16 L15(R15,K16)密文 IP-1(R16L
23、16),加密方程：L0R0 IP()LnRn-1Rn Ln-1(Rn-1,Kn)IP-1(R16L16),解密方程：R16L16 IP()Rn-1LnLn-1 Rn(Ln,Kn)IP-1(L0R0),DES算法的脆弱性,DES的半公开性：S盒的原理至今保密，所以不能算作真正的公开加密算法。1）函数构造与作用域：加密强度取决于函数f的复杂度(S、P)和f的执行次数。64位固定分组，短组模式，易造成密文重复组块有限的函数作用域 ASCII码 0127子密钥只参与异或简单的运算，有可能损害变换精度。2）迭代问题无法证明迭代16次最好 迭代在有限的作用域中存在封闭性；迭代次数多不仅费时，还可能被一次简
24、单的变换所代替。,DES算法的脆弱性,3）S盒中的重复因子及密钥多值问题S盒设计中利用重复因子，导致S盒对不同输入可能产生相同输出，使加密、解密变换的密钥具有多值性。子密钥长度48位，只影响32位输出，因此加密强度达不到256，实际只有232x16=236S盒是精心设计的，它有利于设计者破译密码。提高加密强度（如增加密钥长度），系统开销呈指数增长，除提高硬件、并行处理外，算法本身和软件技术无法提高加密强度。,DES算法存在的问题与挑战,数据加密标准,强力攻击：255次尝试 穷尽搜索 蛮力攻击差分密码分析法：247次尝试 1991年提出，选择明文攻击。分析明文对的差值对密文对差值的影响。很有效。
25、线性密码分析法：243次尝试 1992年提出，已知明文攻击。寻找一个近似的线性表达式，通过选择充分多的明文密文对来破解密钥。对DES更有效。,多重DES及IDEA,二重DES（二个密钥，长度112位）：加密：C=Ek2Ek1(P)解密：P=Dk1Dk2(C)要防止中途攻击三重DES（二个密钥）加密：C=Ek1Dk2 Ek1(P)解密：P=Dk1Ek2 Dk1(C)IDEA加密算法 1992年，瑞士的Lai和Massey 128位密钥，8轮，快速，软硬件实现。,高级加密标准(AES),NIST(国家标准技术研究所)1997年9月12日发出征集高级加密标准的通知。1998年8月首次选出15个候选者
26、，1999年3月遴选出5个，包括：E2、MARS、RC6、Rijndael、Twofish。2000年10月2日，美国商务部部长宣布比利时的Rijndael算法成为新的AES。选择的基本条件：公开；分组单钥，分组长度128；密钥可为128，192，256；可软硬件实现。优劣标准：安全性；计算效率；内存要求；简便灵活。此外：适应性；减少专利纠纷；分散目标减少攻击。AES被开发用于替代DES，但NIST预测Triple DES仍将在近期作为一种实用的算法，单DES将逐步退出。,提纲,密码技术概述对称密码技术非对称密码技术密钥分配与管理技术数字签名技术信息隐藏技术,知识点,非对称密码技术概述RSA算
27、法其他非对称密码技术简介,传统密码体制的缺陷,传统密码体制的缺陷密钥管理的麻烦n个用户保存n*(n-1)/2个密钥不能提供法律证据 不仅要保密还要解决证实问题,非对称密码技术的提出,1976年，美国学者Diffie和Hellman发表了著名论文密码学的新方向，提出了建立“公开密钥密码体制”若用户A有加密密钥ka（公开），不同于解秘密钥ka（保密），要求ka的公开不影响ka的安全。若B要向A保密送去明文m,可查A的公开密钥ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密钥ka对x进行解密得到m。,公钥体制的理论基础,从本质上讲，设计一个公开密码体制就是构造一个陷门单向函数。设X
28、为明文，Y为密文。满足以下两条件的f则称为陷门单向函数。算Y=f(X)容易，而已知Y，反求X则很难，即求X=f(Y)很难若陷门（参数）已知，则容易由Y求X保证从已知的Y，X和公钥难以推出秘密密钥的这种安全性，往往建立在著名的数学难题基础上，即要破译某种公钥密码，相当于要解一个公认的数学难题。目前世界上用得最多的公钥密码算法是RSA、离散对数和ECC。其中，RSA是基于大整数分解难题的基础上，而ECC是基于求椭圆曲线离散对数的难题基础上。,公钥密码体制的特点,公钥密码体制有以下特点密钥分发简单由于加密密钥与解密密钥不能互推，使得加密密钥表可以像电话号码本一样由主管部门发给各个用户。需要秘密保存的
29、密钥量少网络中每个成员只需秘密保存自己的解密密钥，N个成员只需产生N对密钥互不相识的人之间也能进行保密对话一方只要用对方的公开密钥加密发出，收方即用自己密藏的私钥解密，而任何第三方即使知道加密密钥也无法对密文进行解密。可以进行数字签名发信者用他的秘密密钥进行签名，收信者可用发信者的公钥进行验证。,公钥密码体制的意义（1/2）,解决大规模网络应用中密钥的分发和管理问题 需要管理的秘密密钥数量大大减少采用公钥密码体制，N个用户只需要产生N对密钥。以100万个用户为例，只需100万对密钥，需要秘密保存的仅100万个私钥。而利用传统密码体制，为保证不被第三方窃听，需要N（N1）/2=4950万个密钥！
30、分发简单，安全性好公钥密码加密密钥通常是公开的，而解密密钥是秘密的，由用户自己保存，不需要往返交换和传递减少了密钥泄露的危险性,公钥密码体制的意义（2/2）,实现网络中的数字签名机制 数字签名的数据需要有惟一性、私有性，而对称密钥技术中的密钥至少需要在交互双方之间共享，因此，不满足惟一性、私有性，无法用做网络中的数字签名。公钥密码技术由于存在一对公钥和私钥，私钥可以表征惟一性和私有性，而且经私钥加密的数据只能用与之对应的公钥来验证，其他人无法仿冒，所以，可以用做网络中的数字签名服务。,知识点,非对称密码技术概述RSA算法其他非对称密码技术简介,RSA算法的提出与发展,1978年，美国麻省理工学
31、院(MIT)的研究小组成员：李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提出了一种基于公钥密码体制的优秀加密算法RSA算法。RSA算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数，其因子分解是困难的。RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中，将RSA算法正式纳入国际标准。1999年美国参议院已通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。,公开密钥算法,数论知识简介,互素：若gcd(a,b)=1，则整数a和b互素。定义：若ax mod n=1，则称a与x对于模n互为逆元。用欧几
32、里得Euclid算法求乘法逆元 若a和n互素，则a在模n下有逆元欧拉Euler函数(n)=与n互素的、小于n的正整数的个数，n1。例：(3)=(4)=(6)=2，(5)=4，(7)=6(12)=6,数论知识简介,模运算性质：同余模运算满足自反性、对称性、传递性；a=a mod n；若a=b mod n，则b=a mod n；若a=b mod n，b=c mod n，则a=c mod n若a mod n=b mod n，则(a-b)mod n=0；(a mod n)+(b mod n)mod n=(a+b)mod n；-；*；例：152 mod 12=(3*3)mod 12=9,若n是素数，则(
33、n)=n-1 若n=p*q，p、q是素数，则(n)=(p-1)*(q-1)例：(21)=(3*7)=2*6=12费尔玛Fermat小定理：若m是素数，且a不是m的倍数，则am-1 mod m=1。或者：若m是素数，则am mod m=a例：47-1 mod 7=4096 mod 7=1 47 mod 7=16384 mod 7=4,欧拉Euler定理：a(n)mod n=1推论：若a与n互素，则a与a(n)-1 互为逆元。例：a=4，n=7，(7)=6，a(7)-1=45=1024 所以，4和1024在模7下互为逆元。验证：4x1024 mod7=1,求乘法逆元,Function Euclid
34、(d,f)/求d在模f下的逆元(x1,x2,x3)-(1,0,f);(y1,y2,y3)-(0,1,d);If y3=1 then print“逆元是”y2 else print“无逆元”;End.Q=x3/y3(t1,t2,t3)-(x1-Q*y1,x2-Q*y2,x3-Q*y3)(x1,x2,x3)-(y1,y2,y3);(y1,y2,y3)-(t1,t2,t3)Go to 2),高次幂剩余的运算,公开密钥算法,要计算 gn mod p，因g、n、p都是大数而不能采用先高次幂再求剩余的方法来处理，而要采用平方取模的算法，即每一次平方或相乘后，立即取模运算。欧几里德算法欧几里德算法可以迅速地
35、找出给定的两个整数a和b的最大公因数 gcd（a，b），并可判断a与b是否互素，因此该算法可用来寻找加密密钥和解密密钥。,Xr mod p 的快速算法流程图,RSA算法概述,公开密钥算法,每个合数都可以唯一地分解出素数因子6=2 3999999=333711133727641=131121从2 开始试验每一个小于等于27641 的素数。,素数：只能被1和它本身整除的自然数；否则为合数。,整数n的十进制位数 因子分解的运算次数 所需计算时间（每微秒一次）501.4x10103.9小时759.0 x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10
36、294.0 x1015年5001.3x10394.2x1025年,素数的检验,素数的检验Wilson定理：P是素数(P-1)!Mod P=-1 当P较大时，很费时间，无实际价值。Rabin-Miller方法：概率检验适用于RSA算法的最实用的办法是概率测试法。该法的思想是随机产生一个大奇数，然后测试其是否满足条件，如满足，则该大奇数可能是素数，否则是合数。,Witness(a,n)/*将n-1表示为 bk b k-1b0的形式 n是待检验的数，a是小于n的整数。若返回True，则n肯定不是素数；若返回False，则n有可能是素数。*/d=1 for i=k down to 0 x=d;d=(d
37、 d)mod n;if d=1 对于s个不同的a，重复调用此算法，每次返回False，则n是素数的概率至少为1-2-s,Rabin-Miller方法,RSA算法的实现,公开密钥算法,RSA加密算法的过程 1取两个随机大素数p和q（保密）2计算公开的模数n=p*q(公开)3计算秘密的欧拉函数(n)=（p-1)*(q-1)（保密），丢弃p和q，不要让任何人知道。4随机选取整数e,满足 gcd(e,(n)=1(公开e加密密钥)5计算d满足de1(mod(n)(保密d解密密钥)6将明文x（按模为r自乘e次幂以完成加密操作，从而产生密文y（X、Y值在0到n-1范围内）。Y=xe mod n7解密：将密文
38、y按模为n自乘d次幂。X=Yd mod n,举例,公开密钥算法,例设p=43,q=59,r=pq=43*59=2537,(r)=(p-1)(q-1)=42*58=2436,取e=13,求e的逆元d解方程 d e=1 mod 24362436=13*187+5,13=2*5+35=3+2,3=2+1所以1=3-2，2=5-3，3=13-2*55=2436-13*187所以，1=3-2=3-（5-3）=2*3-5=2*（13-2*5）-5=2*13-5*5=2*13-5*（2436-13*187）=937*13-5*2346即937*13 1 mod 2436取e=13 时d=937,RSA算法的
39、实现,公开密钥算法,若有明文public key encryptions先将明文分块为pu bl ic ke nc ry pt io ns将明文数字化令a b z 分别为00 01 25 得1520 0111 0802 1004 24041302 1724 1519 0814 1418利用加密可得密文0095 1648 1410 1299 13651379 2333 2132 1751 1289,公开密钥算法,关于素数的分布 1-100 25 101-200 21 201-300 16 301-400 16 401-500 17 501-600 14 601-700 16 701-800 14
40、 801-900 15 901-1000 14,素数定理：当X变得很大时，从2到X区间的素数数目(X)与X/ln(X)的比值趋近于1，即,(X),X/ln(X),=1,limx,X(X)X/ln(X),(X)X/ln(X),1000 168 145 1.159 10,000 1,229 1,086 1.132 100,000 9,592 8,686 1.1041,000,000 78,498 72,382 1.084,10,000,000 664,579 620,421 1.071 100,000,000 5,761,455 5,428,681 1.0611,000,000,000 50,84
41、7,478 48,254,942 1.054,RSA算法的实现,公开密钥算法,在 2到X的区间中，随机选择一个值为素数的概率近似等于(X)/(X-1)。可以证明，在找到一个素数之前，平均要进行(X-1)/(X)LN(X)次实验。大数的运算上百位大数之间的运算是实现RSA算法的基础,因此程序设计语言本身提供的加减乘除及取模算法都不能使用，否则会产生溢出，必须重新编制算法。在编程中要注意进位和借位，并定义几百位的大数组来存放产生的大数。,RSA 的安全性,公开密钥算法,依赖于大数分解，但是否等同于大数分解一直未能证明。不管怎样，分解n是最显然的攻击方法。1994年4月26日，美国各大媒体报道：由R
42、SA发明人在17年前出的129位数字已被因子分解，并破解了附带的密语：The magic words are squeamish ossifrage.目前，已能分解140位十进制的大素数。因此，模数n必须选大一些。RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般只用于少量数据加密。,RSA算法的脆弱性,公开密钥算法,不能证明RSA密码破译等同于大数因子分解速度问题 提高pq将使开销指数级增长至少有9个明文，加密后不变，即me mod n=m普通用户难于选择p、q。对p、q的基本要求：p、q不相同，即不要太接近，又不能差别太大p-1、q-1都有大素数因
43、子，增加猜测(r)难度Gcd(p-1,q-1)应当小,RSA算法的脆弱性,公开密钥算法,P、q选择不当，则变换周期性、封闭性而泄密 例：p=17，q=11，e=7，则n=187。设m=123，则 C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文m经过4次加密，恢复成明文。总之，RSA对用户要求太苛刻，密钥不能常更换。,其它公钥密码体制,背包体制 1978年提出 5年后被 Shamir破解ElGamal 体制 1985年 基于有限域上计算离散对数难解性，已用于DSS(数字签名标准）例：3x
44、 mod 17=5，解得：x=6 3x mod 13=7，无解椭圆曲线体制(ECC)1985年 基于离散对数优点：安全性高；密钥短；灵活性好。同等安全下的密钥长度：RSA:512 1024 2048 21000ECC:106 160 211 600,ElGamel 加密体制：选大素数P及其本源根g，p、g公开；随机选一整数x作为私钥(保密)；计算y=gx mod p;将y作为公开密钥。加密过程在公钥数据库中查找获取用户的公钥y；在0 p-1间取整数k0;计算下式并发送C1和C2:K=yk0 mod p，C1=gk0 mod p，C2=Km mod p；解密过程 计算K=C1x mod p 明文m=C2 K-1 mod p,
