02信息安全概论--第二章-密码学信息保密技术

2020/6/7,1,第二章信息保密技术密码学,国际关系学院信科系王标,2,参考书,密码学理论与实践D.R.斯廷森密码分析学冯登国清华大学出版社现代密码学杨波编著清华大学出版社数论讲义柯召，孙琦近世代数刘绍学近世代数基础小说破译者TheBreaker小说隐私的终结？数字时代密码大战,3,教学目的,了解密码学及其发展掌握通信安全、信息安全核心技术了解数据加密标准（DESAES）掌握常见公钥密码体制、数字签名方案及其在电子商务、政务、诚信建设等方面的应用了解密码发展趋势、新热点出论文,4,一、密码学基本概念,5,密码学的基本概念,密码学(Cryptology)：研究密码系统或通信安全的一门科学。它包含：密码编码学(Cryptography)，目的是寻求保证信息保密性和可认证性的方法；密码分析学(Cryptanalytics)，目的是研究加密信息的破译和伪造。古典应用例子,6,通信安全,Eav,7,通信中的角色,Alice：传递信息者即加密者，将明文（Plaintext）加密成密文（Ciphertext）。Bob：接收信息者即解密者，将密文解密成明文。Oscar：敌对的第三者，它在传递信息的过程中截收密文。,8,信息安全管理的发展,历史发展阶段管人管密码管密钥管口令管配置管产品测评管产品采购管系统安全管等级划分,9,保密通信系统模型,10,攻击者可能的目的,阅读密文。找出密钥攻破该体制，解读其他密文。篡改或修改Alice传给Bob的信息。假扮成Alice，与Bob传递信息，让Bob误认为他还是与Alice通信。,11,密码系统的安全概念,定义1无条件安全（UnconditionallySecure）是指即使接收到无限密文，也无法确定密钥。定义2计算安全（ComputationallySecure）就是指该密码系统满足破解密文的花费远大于所加密信息的价值且破解密文所花费的时间远多于该信息的有效期。定义3可证明安全（ProvableSecure）就是指该密码安全性问题可转化成某个公认的难题。,12,密码可能经受的攻击,13,Kerckhoffs原理,Kerckhoffs原理在现代密码学中是针对信息保密的一个非常重要的假设。,应该假设敌人已经知道所使用的密码系统的保密方法。,14,密码体制的数学描述,一个五元组(P，C，K，E，D)满足：P是可能明文的有限集；C是可能密文的有限集；密钥空间K是可能密钥的有限集；对每一个k，有一个加密规则ek和解密规则dk，对任一明文x有：dk(ek(x)=x,15,基本概念,明文(消息)(Plaintext)：要保密的原文密文(Ciphertext)：明文经密码变换成的一种隐蔽形式。加密(Encryption)：将明文变换为密文的过程。解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程。加密员或密码员(Cryptographer)：对明文进行加密操作的人员。,16,基本概念,加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。接收者(Receiver)：传送消息的预定对象。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。,17,基本概念,密码分析(Cryptanalysis)：截收者通过分析从截获的密文推断出原来的明文或密钥。密码分析员(Cryptanalyst)：从事密码分析的人被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。主动攻击(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。,18,二、数论基础,内容,模运算与辗转相除法,20,模,假设今天是星期五，请问10000天后是星期几？,（即5+10000除以7的余数）,即：10000天后是星期二,21,辗转相除法,例：,求7812及6084的最大公因子,被除数=商除数+余数，gcd（被除数，除数）=gcd（除数，余数）辗转相除法就是利用此性质，反复以（除数/余数）取代（被除数/除数）,其中：,所以gcd(7812,6084)=36,22,23,同余,定义（同余，Congruence）：令，为两整数，称a同余b模n，记为，当n整除b-a。而所有与a同余的整数所组成的集合，即称为a的同余类。所有同余类所形成的集合,24,同余类,25,交换群,定义（交换群）:考虑(G,*)，其中G为集合，*为运算。若*运算满足：,（1）封闭性：则；（2）交换律：则；（3）结合律：则；（4）存在单位元：，使得（5）存在逆元：，使得,若1、3、4、5成立，称为群(Group)；若以上15都成立，称为交换群。,26,交换环,此时除了为交换群以外，另外针对乘法.运算也满足封闭性、交换律、结合律以及存在乘法单位素（即）等性质，但并非所有非零元素都有乘法反元素，另外乘法对加法有分配律，即：若则此时，称为交换环（CommutativeRing）。,考虑,27,中国剩余定理（ChineseRemainderTheorem）,定理：,令为两两互质的正整数，令则同余联立方程组在集合有惟一解，其解为其中，而,28,子群与循环群,令G为任一乘法群，为任一元素，则为G中的子群（封闭性与逆元的存在性自然成立）。此子群称为由元素g所生成的子群。,定义：子群,定义：循环群（CyclicGroup）,若存在使得，则称G为循环群（CyclicGroup），而g为原根或生成元（Generator）。,29,费马小定理,30,原根,31,二次剩余QuadraticResidue,定义：,同余式,a与n互质,若有整数解，称a为（modn）的二次剩余（QuadraticResidue）若无解则称a为（modn）的非二次剩余（QuadraticNonresidue）。,32,二次剩余的性质,性质,令p为奇质数，可定义函数,33,Legendre符号,定义：,令p为质数，定义Legendre符号如下：,定理（Euler判别）,令p为质数，a与p互质。则：,34,Legendre符号性质,性质,令p为奇质数，a、b为与p互质的整数，则,（2）,（3）,（4）,（5）,定理QuadraticReciprocity,令p、q为奇质数，则,35,Jacobi符号,定义：,令a为整数，n0为奇整数，其质因数分解为,定义Jacobi符号：,性质：,当n0为奇整数，Jacobi符号才可能有意义,（5）,（3）,（4）,（2）,（6）,注：a、b为整数，m、n为奇整数,36,质数理论,定义:,令p为不为1的正整数，p为质数（Prime）若某正整数d整除p（记为），则d=1或d=p。,Eratosthenes筛法,37,欧拉函数(n),(n)表示n的一个完全剩余系,即0,1,2,3,n-1与n互素的整数的个数。定理设m,nN，(m,n)=1，则(mn)=(m)(n)。定理设n是正整数，p1,p2,pk是它的全部素因数，则(n)=,38,欧拉函数举例,(2)=1，(3)=2，(4)=2，(7)=6(12)=(34)=(3)(4)=412=223(12)=(223)=12(1-1/2)(1-1/3)=4,39,密码安全伪随机数生成器,BlumBlumShub()dop=RandomPrime();while(p%4!=3);doq=RandomPrime();while(p%4!=3);/p,q为随机质数且=3mod4n=p*q;dos=RandomInteger(1,n);while(gcd(s,n)!=1);/gcd(s,n)=1且s为随机数种子x0=s;for(i=1;i0)可能依赖于k，0，x0，x1，xi-1等参数。,2020/6/7,70,同步流密码,根据加密器中记忆元件的存储状态i是否依赖于输入的明文字符，流密码可进一步分成同步和自同步两种。i独立于明文字符的叫做同步流密码，否则叫做自同步流密码。由于自同步流密码的密钥流的产生与明文有关，因而较难从理论上进行分析。目前大多数研究成果都是关于同步流密码的。,2020/6/7,71,2020/6/7,72,在同步流密码中，由于zi=f(k,i)与明文字符无关，因此密文不依赖于此前的明文。可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。如果与上述加密变换对应的解密变换为xi=Dzi(yi)，则可给出同步流密码体制的模型如图所示。同步流密码体制模型,2020/6/7,73,同步流密码的加密变换Ezi可以有多种选择，只要保证变换是可逆的即可。实际使用的数字保密通信系统一般都是二元系统，因而在有限域F2上讨论的二元加法流密码是目前最为常用的流密码体制。其加密变换可表示为yi=zixi。,一次一密密码是加法流密码的原型。事实上，如果（即密钥用作滚动密钥流），则加法流密码就退化成一次一密密码。实际使用中，密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期良好的统计特性抗线性分析抗统计分析。,2020/6/7,74,密钥流生成器的分解,2020/6/7,75,目前最为流行和实用的密钥流产生器其驱动部分是一个或多个线性反馈移位寄存器：,2020/6/7,76,反馈移位寄存器,移位寄存器是流密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,an)组成，如图所示。,2020/6/7,77,每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列a1,a2,an或n维向量(a1,a2,an)表示，其中ai是第i级存储器的内容。,2020/6/7,78,2020/6/7,79,例：下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表求出。,2020/6/7,80,输出序列为10111011101110周期为4。如果移位寄存器的反馈函数f(a1,a2,an)是线性函数，则称之为线性反馈移位寄存器LFSR（linearfeedbackshiftregister）。此时f可写为f(a1,a2,an)=cna1cn-1a2c1an其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如图所示。,2020/6/7,81,GF(2)上的n级线性反馈移位寄存器,2020/6/7,82,输出序列at满足an+t=cnatcn-1at+1c1an+t-1其中t为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。,2020/6/7,83,2020/6/7,84,例：一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为1001101001000010101110110001111100110,注意：,在线性反馈移位寄存器中总是假定c1,c2,cn中至少有一个不为0，否则f(a1,a2,an)0这样的话，在n个脉冲后状态必然是000，且这个状态必将一直持续下去。若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定cn=1。,2020/6/7,85,2020/6/7,86,习题一,2020/6/7,87,习题二：一5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,1,0,1,1)，求出输出序列,m序列密码的破译*,上面说过，有限域上的二元加法流密码是目前最为常用的流密码体制，设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是序列。又设和是序列中两个连续的长向量，其中：,2020/6/7,88,2020/6/7,89,设序列ai满足线性递推关系：可表示为,2020/6/7,90,或Sh+1=MSh，其中又设敌手知道一段长为2n的明密文对，即已知,2020/6/7,91,于是可求出一段长为2n的密钥序列其中由此可推出线性反馈移位寄存器连续的n+1个状态：,2020/6/7,92,做矩阵而若X可逆，则,2020/6/7,93,下面证明X的确是可逆的。因为X是由S1,S2,Sn作为列向量，要证X可逆，只要证明这n个向量线性无关。由序列递推关系：可推出向量的递推关系：,2020/6/7,94,设m(mn+1)是使S1,S2,Sm线性相关的最小整数，即存在不全为0的系数l1,l2,lm，其中不妨设l1=1，使得即对于任一整数i有,2020/6/7,95,由此又推出密钥流的递推关系：即密钥流的级数小于m。若mn，则得出密钥流的级数小于n，矛盾。所以m=n+1，从而矩阵X必是可逆的。,例：,设敌手得到密文串101101011110010，相应的明文串011001111111001，可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程,2020/6/7,96,2020/6/7,97,即而,2020/6/7,98,从而得到所以密钥流的递推关系为,非线性组合子系统,密钥流生成器可分解为驱动子系统和非线性组合子系统，驱动子系统常用一个或多个线性反馈移位寄存器来实现，非线性组合子系统用非线性组合函数F来实现。,2020/6/7,99,Geffe序列生成器图,2020/6/7,100,多路复合器表示的Geffe序列生成器,2020/6/7,101,J-K触发器,102,利用J-K触发器的非线性序列生成器,2020/6/7,103,Pless生成器,2020/6/7,104,最简单的钟控序列生成器,2020/6/7,105,一个钟控序列的线性等价生成器,2020/6/7,106,2020/6/7,107,设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则：长周期。高线性复杂度。统计性能良好。足够的“混乱”。足够的“扩散”。抵抗不同形式的攻击。,108,2020/6/7,109,六分组密码体制,分组密码概述数据加密标准DES分组密码的运行模式IDEA（了解）AES算法Rijndael习题,分组密码概述,分组密码是指将待处理的明文按照固定长度分组加密解密。在许多密码系统中，单钥分组密码是系统安全的一个重要组成部分。易于构造其他安全组件。与流密码不同之处在于输出不只与相应时刻输入的明文有关，还与组长n有关。,2020/6/7,110,分组密码框图,2020/6/7,111,设计的算法应满足下述要求,分组长度n要足够大，使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效。密钥量要足够大（即置换子集中的元素足够多），尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆。,2020/6/7,112,加密和解密运算简单，易于软件和硬件高速实现。数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。差错传播尽可能地小。,2020/6/7,113,设计分组密码时的一些常用方法,扩散和混淆是由Shannon提出的设计密码系统的两个基本方法。目的是抗击敌手对密码系统的统计分析。,2020/6/7,114,2020/6/7,115,扩散，就是将明文的统计特性散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，等价于说密文中每一位均受明文中多位影响。例如对英文消息M=m1m2m3的加密操作其中ord(mi)是求字母mi对应的序号，chr(i)是求序号i对应的字母。混淆是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。,Feistel密码结构,很多分组密码的结构从本质上说都是基于一个称为Feistel网络的结构。Feistel提出利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果。Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。,2020/6/7,116,2020/6/7,117,Feistel加密结构,Feistel加密结构,加密算法的输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。其第i轮迭代的输入为前一轮输出的函数：其中Ki是第i轮用的子密钥，由加密密钥K得到。一般地，各轮子密钥彼此不同而且与K也不同。,2020/6/7,118,Feistel网络的实现与以下参数和特性有关,分组大小密钥大小轮数子密钥产生轮函数还有以下两个方面需要考虑：快速的软件实现：算法的执行速度是考虑的关键。算法容易分析：就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。,2020/6/7,119,Feistel解密结构,Feistel解密过程本质上和加密过程是一样的，算法使用密文作为输入。使用子密钥Ki的次序与加密过程相反，即第1轮使用Kn，第2轮使用Kn-1，最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。,2020/6/7,120,2020/6/7,121,2020/6/7,122,在加密过程中：在解密过程中,2020/6/7,123,所以解密过程第1轮的输出为LE15RE15，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第i轮有因此,数据加密标准,数据加密标准（dataencryptionstandard,DES）是上世纪最为广泛使用和流行的一种分组密码算法。DES的分组长度为64比特，密钥长度为56比特，是由美国IBM公司研制的，是早期的称作Lucifer密码的一种发展和修改。,2020/6/7,124,DES描述,图3.5是DES加密算法的框图，其中明文分组长为64比特，密钥长为56比特。明文的处理过程，有3个阶段，首先是一个初始置换IP，用于重排明文分组的64比特数据。然后是具有相同功能的16轮变换，每轮中都有置换和代换运算，第16轮变换的输出分为左右两半，并被交换次序。最后再经过一个逆初始置换IP-1（为IP的逆）从而产生64比特的密文。除初始置换和逆初始置换外，DES的结构和Feistel密码结构完全相同。,2020/6/7,125,DES加密算法框图,2020/6/7,126,1.初始置换,DES的初始置换表见下表。表(a)和表(b)分别给出了初始置换和逆初始置换的定义，为了显示这两个置换的确是彼此互逆的，考虑下面64比特的输入M：,2020/6/7,127,消息M,M1M2M3M4M5M6M7M8M9M10M11M12M13M14M15M16M17M18M19M20M21M22M23M24M25M26M27M28M29M30M31M32M33M34M35M36M37M38M39M40M41M42M43M44M45M46M47M48M49M50M51M52M53M54M55M56M57M58M59M60M61M62M63M64,2020/6/7,128,表(a),其中Mi是二元数字。X=IP(M)为：M58M50M42M34M26M18M10M2M60M52M44M36M28M20M12M4M62M54M46M38M30M22M14M6M64M56M48M40M32M24M16M8M57M49M41M33M25M17M9M1M59M51M43M35M27M19M11M3M61M53M45M37M29M21M13M5M63M55M47M39M31M23M15M7,2020/6/7,129,如果再取逆初始置换Y=IP-1(X)=IP-1(IP(M)，可以看出，M各位的初始顺序将被恢复。,2020/6/7,130,DES加密算法的轮结构,2020/6/7,131,函数F(R,K)的计算过程,2020/6/7,132,S盒,对每个盒Si，其6比特输入中，第1个和第6个比特形成一个2位二进制数，用来选择Si的4个代换中的一个（行）。6比特输入中，中间4位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表示为4位二进制数即得这一S盒的输出。例如，S1的输入为011001，行选为01（即第1行），列选为1100（即第12列），行列交叉位置的数为9，其4位二进制表示为1001，所以S1的输出为1001。,2020/6/7,133,解密,和Feistel密码一样，DES的解密和加密使用同一算法，但子密钥使用的顺序相反。,2020/6/7,134,二重DES,2020/6/7,135,两个密钥的三重DES,此方案已在密钥管理标准ANSX.917和ISO8732中被采用。,2020/6/7,136,密码分析,差分密码分析是迄今已知的攻击迭代密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。线性密码分析是对迭代密码的一种已知明文攻击，它利用的是密码算法中的“不平衡（有效）的线性逼近”。,2020/6/7,137,IDEA,瑞士联邦技术学院来学嘉（X.J.Lai）和J.L.Massey提出的第1版IDEA（internationaldataencryptionalgorithm，国际数据加密算法）于1990年公布，当时称为PES（proposedencryptionstandard，建议加密标准）。1991年，在Biham和Shamir提出差分密码分析之后，设计者推出了改进算法IPES，即改进型建议加密标准。1992年，设计者又将IPES改名为IDEA。这是近年来提出的各种分组密码中一个很成功的方案，已在PGP中采用。,2020/6/7,138,IDEA的加密框图,2020/6/7,139,IDEA第1轮的轮结构,2020/6/7,140,IDEA的输出变换,2020/6/7,141,2020/6/7,142,AES算法Rijndael,1997年4月15日，美国ANSI发起征集AES（advancedencryptionstandard）的活动，并为此成立了AES工作小组。目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。,2020/6/7,143,设计思想,Rijndael密码的设计力求满足以下3条标准：抵抗所有已知的攻击。在多个平台上速度快，编码紧凑。设计简单。,2020/6/7,144,当前的大多数分组密码，其轮函数是Feistel结构，即将中间状态的部分比特不加改变地简单放置到其他位置。Rijndael没有这种结构，其轮函数是由3个不同的可逆均匀变换组成的，称它们为3个“层”。,2020/6/7,145,所谓“均匀变换”是指状态的每个比特都是用类似的方法进行处理的。不同层的特定选择大部分是建立在“宽轨迹策略”的应用基础上的。简单地说，“宽轨迹策略”就是提供抗线性密码分析和差分密码分析能力的一种设计。,2020/6/7,146,2020/6/7,147,Rijndael是一个迭代型分组密码，其分组长度和密钥长度都可变，各自可以独立地指定为128比特、192比特、256比特。,算法说明,字节代换行移变换列混合变换行移变换字节代换,若干轮变换,字节代换示意图,2020/6/7,148,行移位示意图,2020/6/7,149,列混合运算示意图,2020/6/7,150,密钥加运算示意图,2020/6/7,151,Nb=6且Nk=4时的密钥扩展与轮密钥选取,2020/6/7,152,153,154,七、公钥加密技术,155,公匙密码系统,将一已加密的信息m解密，即可还原m；加密及解密函数必须是容易计算的；公开加密函数并不会提供任何简易计算解密函数的方法；在实际应用中，这意味着只有Bob能将任何经加密函数加密的信息有效地解密，也只有Bob知道“陷门”(Trapdoor)，从而能有效计算解密函数；若将任何信息m先用解密函数运算，再用加密函数运算，亦可还原信息m。,156,单向陷门函数,单向函数：是指函数f，如果对任意给定的x，计算y=f(x)是容易的，但对于任意给定的y，计算x=f-1(x)是难解的，即求f的逆函数是困难的。单向陷门函数：是指函数f，t是函数f的一个参数，如果对任意给定的x，计算y=f(x)是容易的；不知参数t时，求f的逆函数是困难的，但当已知参数t时，求f的逆函数是容易的。,157,RSA的建立,1.Bob产生两个大素数p、q2.Bob计算n=pq和(n)=(p-1)(q-1)3.Bob选择一随机数e,满足gcd(e,(n)=14.Bob用欧几里德算法计算d=e-1mod(n)5.Bob在目录中公开n和e作为公开密钥。其中p、q、d和(n)保密；n、e公开。,158,RSA算法系统建立,系统建立：（Bob）取互异的大素数p、q（保密）计算RSA模数n=pq选取e为加密密钥，其中gcd(e,(n)=1求得解密密钥d，满足d=e-1mod(n)公开(n,e)，保密(p,q,d)以及(n)。,159,RSA算法加密解密,加密：（Alice）取互异的大素数p、q（保密）计算RSA模数n=pq选取e为加密密钥，其中gcd(e,(n)=1求得解密密钥d，满足d=e-1mod(n)公开(n,e)，保密(p,q,d)以及(n)。,160,RSA加密解密过程,加密：对消息m加密（Alice）取得Bob的公开密钥(n,e)，加密计算：E(m):=me(modn)=c解密：接收到密文c（Bob）用解密密钥d计算：D(c):=cd(modn)=m还原成明文。,161,RSA举例1电子邮件加密,1.选素数p=47和q71，得n=3337,(n)=467032202.选择e=79，求得私钥d=e-11019(mod3220）3.公开n=3337和e=794.现要发送明文688，计算：68879(mod3337)=15705.收到密文1570后，用私钥d1019进行解密：15701019（mod3337)=688,162,RSA算法举例2,加密：,Alice的明文（令a=0、b=1、z=25），取得Bob的公开密钥为，加密得密文,163,RSA算法举例2,解密：,所以,164,RSA加密解密函数,令p、q为相异质数，令n=pq，令e为与(p-1)(q-1)互质的整数，令d满足：,令加密函数：,解密函数：,则对所有整数m皆满足：,且,165,质数分解的记录,166,利用RSA私钥因数分解,假设Alice的RSA密钥为,Alice自行因数分解n如下：,1.随机找一个整数,很正常地,2.计算,计算,167,168,小加密指数攻击,169,小解密指数攻击Wiener低幂次d攻击,定理,令（且）为实数x的某项连分数的收敛值,定理Wiener攻击,令RSA密码系统中各参数满足下列条件：,则存在多项式时间算法可因数分解RSA模数n。,170,循环攻击,171,RSA密码系统使用的注意事项,不可泄漏RSA密码系统的任何参数。不要使用相同的RSA模数。加密密钥的长度不少于模数长度的1/4。另外因为数论家在因数分解上的进展，为防止n被质因数分解，也应考虑以下建议：,1）p、q的大小，长度应有数字之差。2）p、q建议采用“强质数”（不少专家仍有不同意见）。3）n的长度至少应为1024-bit以上，上个世纪曾建议的512-bit的长度，如RSA-155也于世纪交替前被破解）。4）的值越小越好。,172,Rabin密码,173,RSA硬件实现速度,上世纪最有效的RSA硬件实现的加密速度是600bit/s（模n为512bit时），而DES大约是1Gbit/s：15001因此一般公钥密码算法用来加密对称密钥。一般的信息加密实际过程如下：,174,信息加密模型,175,ElGamal公钥加密方案,Diffie-Hellman密钥交换方案的变形能够用于安全交换密钥publishedin1985byElGamal:T