




已阅读5页,还剩188页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
2020/6/4,1,.,第2章密码学基础,电子商务安全,2020/6/4,2,.,问题的提出,1996年7月9日,北京市海淀区法院审理国内第一起电子邮件侵权案。此案的原、被告均系北京大学心理学系93级女研究生。4月9日,原告薛燕戈收到美国密执安大学发给她的电子邮件,内容是该校将给她提供1.8万美元奖学金的就学机会,此后久等正式通知却杳无音讯,4月27日薛了解到密执安大学在4月12日收到一封署名薛燕戈的电子邮件,表示拒绝该校的邀请。因此密执安大学已将奖学金机会转给他人。经过调查,证实以薛名义发电子邮件的是其同学张男。,2020/6/4,3,.,如果电子邮件的发送附加了数字签名,也许本案就不会发生了。,2020/6/4,4,.,第2章密码学基础2.1密码学概述2.2传统对称密码体制2.3公钥密码体制2.4量子密码体制,电子商务安全,2020/6/4,5,.,2.1密码学概述,2.1.1密码学起源与发展2.1.2什么是密码学2.1.3密码体制分类2.1.4密码系统设计的基本原则2.1.5密码系统攻击及分析,使用加密技术是保护信息的最基本的方法,密码学技术是信息安全技术的核心,已被广泛应用到各类交互的信息中。实质上,密码学不是现代社会才出现的概念,它的起源与发展要追溯到几千年前。,2020/6/4,6,.,2.1.1密码学起源与发展,密码学的雏形始于古希腊人,他们与敌人作战时,在战场上需要与同伴传递书写有“战争机密”的信件,为了防止信件会落到敌人手中从而泄漏了战略机密,聪明的古希腊战士采取了将信中的内容“加密”的手段,这样信中所显示的内容就不是真实的要表达的战略内容。这种情况下,即使战争信件被敌人获取,敌人也很难得到信件中所包含的军事机密。,2020/6/4,7,.,2.1.1密码学起源与发展,加密:将要传递的信息隐藏例如:清末大儒纪晓岚赠送的对联鳳遊禾蔭鳥飛去馬走蘆邊草不生,禾下加鳳去掉鳥字得禿字馬置蘆邊去掉草頭得驢字,2020/6/4,8,.,2.1.1密码学起源与发展,这样的数字毫无意义么?,2020/6/4,9,.,2.1.1密码学起源与发展,1.古典密码学1949年之前,密码学是一门艺术2.近代密码学19491975年:密码学成为科学3.现代密码学1976年以后:密码学的新方向公钥密码学,2020/6/4,10,.,2.1.2什么是密码学,1.密码学概念2.密码系统构成3.密码系统数学模型,2020/6/4,11,.,1.密码学概念,密码学:是研究如何保护信息安全性的一门科学。它包含两个分支:密码编码学和密码分析学。密码编码学:主要研究密码方案的设计,即寻找对信息编码的方法从而实现隐藏信息的一门学问。密码分析学:主要是从攻击者的角度来看问题,研究如何破解被隐藏信息的一门学问。两个分支:是既相互对立,又相互依存的科学。,2020/6/4,12,.,2.密码系统构成,密码系统主要包括以下几个基本要素:明文指的是希望得到保密的原始信息。用某种方法伪装信息以隐藏它的内容的过程称为加密,经过加密处理后得到的隐藏信息称为密文。而把密文转变为明文的过程称为解密。加密算法是指通过一系列的变换、替代或其他各种方式将明文信息转化为密文的方法。解密算法指通过一系列的变换、替代或其他各种方法将密文恢复为明文的方法。,2020/6/4,13,.,2.密码系统构成,加解密算法通常都是在一组密钥的控制下进行的,分别称为加密密钥和解密密钥。加密和解密过程如下图所示。,明文,明文,密文,加密算法,解密算法,加密密钥,解密密钥,2020/6/4,14,.,2.密码系统构成,比如我们想加密“HelloWorld”这个信息,“helloworld”就是明文;过某种加密机制,上述的“HelloWorld”信息变为“mjqqtbtwqi”,则“mjqqtbtwqi”就是密文信息;“helloworld”隐藏为“mjqqtbtwqi”的过程就是由加密算法完成的;解密算法则完成由“mjqqtbtwqi”恢复为“helloworld”的过程。,2020/6/4,15,.,3.密码系统数学模型,以五元组(M,C,K,E,D)表示密码系统,其中M是明文信息空间,C是密文信息空间,K是密钥信息空间,E是加密算法,D是解密算法。各元素之间有如下的关系:E:MK-C,表示E是M与K到C的一个映射;D:CK-M,表示D是C与K到M的一个映射。,2020/6/4,16,.,3.密码系统数学模型,例如:恺撒密码体制,解密算法:(C-K)mod26,2020/6/4,17,.,3.密码系统数学模型,例如在最早的恺撒密码体制中,明文信息空间是26个英文字母集合,即M=a,b,c,dz,A,BZ;密文信息空间也是26个英文字母集合,即C=a,b,c,d.z,A,B.Z;密钥信息空间是正整数集合,即K=N|N=1,2.;为了计算方便,将26个英文字母集合对应为从0到25的整数,加密算法则是明文与密钥相加之和,然后模26,因此Ek=(M+K)mod26;与之对应的解密算法是Dk,Dk=(C-K)mod26。例如M为“helloworld”,在密钥k=5的条件下,此时对应的密文就是“mjqqtbtwqi”。,2020/6/4,18,.,3.密码系统数学模型,发送信息的一方使用密钥K加密明文M,通过加密算法得到密文C,即C=EK(M);接收信息的一方使用密钥K解密密文C,通过解密算法得到明文M,即M=DK(C);。K与K可能相等,也可能不等,具体取决于所采用的密码体制。,2020/6/4,19,.,3.密码系统数学模型,明文m,加密算法:密文c=Ek1(m),加密密钥源,解密密钥源,解密算法:m=Dk2(c),明文m,m,m,k1,k2,c,c,2020/6/4,20,.,2.1.3密码体制分类,按不同的划分标准或者方式,密码体制可以分为多种形式。在此,我们主要从加密方式、所采用的密钥方式以及保密程度来划分。,2020/6/4,21,.,1.按加密方式划分,(1)流密码体制。也称为序列密码,它是将明文信息一次加密一个比特形成密文字符串,典型的流密码体制是一次一密密码体制,其密钥长度与明文长度相等。(2)分组密码体制。也称为块密码体制,分组密码则是将明文信息分成各组或者说各块,每组具有固定的长度,然后将一个分组作为整体通过加密算法产生对应密文的处理方式。,2020/6/4,22,.,1.按加密方式划分,流密码在流密码中,将明文m写成连续的符号m=m1m2,利用密钥流k=k1k2中的第i个元素ki对明文中的第i个元素mi进行加密,若加密算法为E,则加密后的密文c=Ek(m)=Ek1(m1)Ek2(m2)Eki(mi)。设与加密算法E对应的解密算法为D,则通过解密运算可译得明文为:m=Dk(c)=Dk1(Ek1(m1)Dk2(Ek2(m2)=m1m2,从而完成一次密码通信。,2020/6/4,23,.,1.按加密方式划分,流密码,2020/6/4,24,.,2.按使用的密钥方式划分,(1)单密钥体制。也称为对称密码机制,在该体制下,密码系统只有一个密钥,加密算法和解密算法使用统一的一个密钥,拥有密钥的用户既可以加密信息也可以解密信息。(2)双密钥体制。也称为非对称密码体制或者公钥密码体制,在该体制下,密码系统有两个密钥,分别是公开密钥和私有密钥,公开密钥是对外公开的,即所有的人都可知,私有密钥是只有特定的用户方能拥有。,2020/6/4,25,.,3.按保密程度划分,(1)实际上保密的密码体制。是指在理论上可破解,但是在现有的客观条件下以及有限的时间内,无法通过计算从密文破译出明文或者密钥的密码体制。(2)绝对保密的密码体制。是指无论在理论上还是实际上,都不可破解的密码体制。,2020/6/4,26,.,2.1.4密码系统设计的基本原则,(1)简单实用原则。在已知密钥的情况下,容易通过加密算法和解密算法计算密文和明文;但是在未知密钥的情况下,无法从加密算法或者解密算法推导出明文或者密文。(2)抗攻击性原则。在现有的计算环境下,能够抵抗各种密码分析攻击,例如:已知密文,如果不知道密钥,则无法从其中推出密钥和明文(3)算法公开化原则。,2020/6/4,27,.,2.1.5密码系统攻击及分析,对密码系统的攻击分为被动攻击和主动攻击被动攻击是指通过窃取密文试图了解明文或者密钥的内容;主动攻击是指篡改和伪造密文,以达到修改或者伪造明文的目的。被动攻击的主要方法有:通过窃听通信信道上传输的密文,对其进行分析破译出明文为或者密钥;主动攻击的主要方法有:攻击者截取通信信道上传输的密文,然后对其篡改(如添加、删除某些内容)再发送,2020/6/4,28,.,2.2传统对称密码体制,在公钥密码体制出现以前,无论是古典密码还是近现代密码都属于对称密码体制,也就是说加密和解密使用同一个密钥,我们在实际中常用的分组密码体制如DES、IDEA都属于对称密码体制。多年来,对称密码体制一直被广泛应用于各类信息的加密和解密。2.2.1加解密的基本原理2.2.2数据加密标准DES2.2.3高级加密标准AES,2020/6/4,29,.,2.2.1加解密的基本原理,无论是采用手工或者机械的方式完成的古典密码体制,还是采用计算机程序软件方式或者电子电路的硬件方式完成的现代密码体制,尽管使用的操作方法不一样,但是其加密和解密的基本原理是一致的:都是基于对明文信息的“置换”和“替代”完成的,或者是通过对两者的组合运用即乘积的方式完成。,2020/6/4,30,.,1.置换,置换又称“换位”方法,是指变换明文中各元素的相对位置,但保持其内容不变的方法,即通过对明文元素重新排列组合来达到隐藏明文原始内容所表达含义的加密方法。最典型的置换密码体制是栅栏密码技术。,2020/6/4,31,.,1.置换,栅栏加密算法步骤如下:将明文的元素按照两行的方式书写,并按照从上到下,从左到右的方式排列;按从上到下的顺序依次读出每一行的元素所得到的组合就是密文。,2020/6/4,32,.,1.置换,栅栏解密算法步骤如下:将接收到的密文按照从左到右的顺序写为两行,如果密文元素的个数为偶数n,则每一行写n/2个元素;如果密文元素个数为奇数,则第一行排列n+1/2个元素,第二行排列n-1/2个元素;按照加密算法的规则,依次从上到下,从左到右的规则读取各元素,所得到的字母序列即获得所需要的明文。,2020/6/4,33,.,1.置换,2020/6/4,34,.,1.置换,一种改进的方案是将明文元素以矩阵的方式排列,假设明文可以写成nm的n行m阶的矩阵,矩阵法:按照nm的矩阵格式从左到右依次写出明文元素;根据密钥的内容指示,读出相应各列的明文元素;所有读出的元素按一行的顺序排列,得到的结果即为密文。,2020/6/4,35,.,1.置换,例如:,2020/6/4,36,.,1.置换,矩阵法解密算法是:根据密钥长度将密文写成矩阵形式,但书写的格式是按照逐列写,各列之间的排列顺序参照密钥内容的编号;依次读取排列好的矩阵逐行元素,得到的结果就是明文。,2020/6/4,37,.,1.置换,2020/6/4,38,.,1.置换,置换法破译:通过字母的使用频率破译,2020/6/4,39,.,2.替代,替代方法是将明文各元素的内容用新的符号或者符号组合代替,替换之后形成的新的元素符合集合便是密文。公元前50年,古罗马的凯撒大帝在高卢战争中采用的加密方法。凯撒密码算法就是把每个英文字母向后推移K位。用各自后面对应的第k个字符代替。,ABCDEFGHVWXYZFGHIJKLMABCDE,2020/6/4,40,.,2.替代密码分析,给定加密信息:PHHWPHDIWHUWKHSDUWB由于:加密算法已知可能尝试的密钥只有26个通过强力攻击得到明文:Meetmeaftertheparty替代法容易受到攻击!,2020/6/4,41,.,2.2.1加解密的基本原理,为了提高安全性,自然会想到能不能将置换和替代两种方法结合起来使用,这样得到的结果从密码编码的角度来看比使用一种方式安全性要高很多,我们将置换和替换两者交替使用的密码编码方法称为乘积密码,Feistel提出的Feistel密码结构就是乘积密码,它是在密钥的控制下按照一定的规则经过多轮循环的置换与替代操作达到隐藏信息的目的。现在普遍使用的分组密码体制设计原理几乎都遵循Feistel密码结构,如经典的数据加密标准DES。,2020/6/4,42,.,2.2.2数据加密标准DES,2020/6/4,43,.,1.DES的产生,1972年,美国标准局NBS(现在的NIST)公开征求用于计算机通信数据保密的方案,其要求为:算法必须提供高度的安全性;算法必须有详细的说明,并易于理解;算法的安全性取决于密钥,不依赖于算法;算法适用于所有用户;算法适用于不同应用场合;算法必须高效、经济;算法必须能被证实有效;算法必须可出口。,2020/6/4,44,.,1.DES的产生,IBM公司的W.Tuchman和C.Meyers等研究人员提交了一个数据加密算法Lucifer该算法被美国标准局采用,在经过一系列的研究讨论和简单的修改于1977年正式批为数据加密标准DES。,2020/6/4,45,.,2.DES算法基本原理,DES属于典型的分组密码体制。DES将明文信息按64比特大小分组,密钥长度也是64比特,但是实际使用过程中密钥长度是56比特,另外8比特用作奇偶校验位(即每个字节的最后一位用作奇偶校验)。64比特的明文分组在密钥的作用下经过多次的置换和替代组合操作,最终形成攻击者难以破译的64比特密文。,2020/6/4,46,.,2.DES算法基本原理,DES算法的基本原理是上一节所讲的置换和替代操作,根据前面我们对置换和替代算法的分析,无论是单一的置换还是单一的替代,其安全系数都很低,攻击者通过统计分析等方法很容易的攻破密码系统。因此,DES的设计者在加密过程中,使用了置换和替代的多次组合过程,并且使用多轮循环加密来扰乱和扩散明文信息。,2020/6/4,47,.,2.DES算法基本原理,DES算法加密的基本原理:加密过程中输入64比特的明文,首先经过初始矩阵IP置换;在56比特的输入密钥控制下,进行16轮迭代加密处理过程;通过简单的换位和逆置换算法,得到64比特的输出密文。,2020/6/4,48,.,2.DES算法基本原理,DES算法加密的基本原理:,2020/6/4,49,.,2.DES算法基本原理,DES算法解密的基本原理:具体的解密处理过程与加密处理过程顺序完全一样,只是控制每一轮迭代的密钥K与加密过程中的密钥K正好相反,即加密过程的第1轮控制密钥K1是解密过程的第16轮密钥K16,K1=K16,而解密处理过程的第1轮控制密钥K是加密处理过程的第16轮密钥,即K1=K16。,2020/6/4,50,.,3.算法加密具体过程,DES加密算法主要由4个元素组成:初始置换矩阵IP、加密函数F、S-盒子、逆初始置换矩阵IP-1。,2020/6/4,51,.,3.算法加密具体过程,初始置换:初始置换矩阵IP,2020/6/4,52,.,3.算法加密具体过程,初始置换:由置换矩阵可知置换规则:将原先处在第58位置的比特置换后放在第1个位置,第50位置的比特置换后放在第2个位置,第7个位置的比特置换后放在第64个位置。如果明文M分组是序列m1m2m3.m64,则经过IP置换后变成序列m58m50m42.m7。,2020/6/4,53,.,3.算法加密具体过程,初始置换:举例,假设64比特明文M是:,按照初始置换矩阵IP的变换规则,将M变换为M1,M1序列是:,2020/6/4,54,.,3.算法加密具体过程,M写成88的矩阵,如表2-7所示。初始置换后如表2-8所示,2020/6/4,55,.,3.算法加密具体过程,通过比较表2-7与表2-8,可以发现,M由置换矩阵IP变换到M1遵循一定的规律:矩阵M1的第1行是矩阵M的第2列的倒置,第2行是矩阵M的第4列倒置,第5行是矩阵M的第1列的倒置。概括的说,置换后的矩阵M1前4行是明文矩阵M各偶数列的倒置,后4行是明文矩阵M各奇数列的倒置。,2020/6/4,56,.,3.算法加密具体过程,再次对照逆初始矩阵IP-1(如表2-6所示)可发现,将M1前4行各行的倒置作为新矩阵M2的偶数列,后4行各行的倒置作为新矩阵M2的奇数列,会得到结果M=M2。也就是说将任何明文M经过初始矩阵IP置换,然后再经过逆初始矩阵IP-1的置换,M的值保持不变,2020/6/4,57,.,3.算法加密具体过程,每轮迭代加密处理过程:DES算法加密过程需要16轮迭代处理,每一轮迭代的处理步骤是一样的,只是输入的信息和控制密钥不同,第i轮加密处理过程如图2-3所示。,2020/6/4,58,.,3.算法加密具体过程,2020/6/4,59,.,3.算法加密具体过程,F函数是DES算法的精髓,它是多个置换函数和替代函数的组合函数,该函数以密钥和上一轮加密得到的部分结果作为输入,通过多次扩展、置换和替代达到真正“扰乱”明文信息的目的。F函数分为扩展、异或运算、S盒替代以及置换四个步骤。,2020/6/4,60,.,3.算法加密具体过程,扩展F函数首先将32比特的数据Ri-1预扩展为48比特,其方法是:将Ri-1从左到右分成8块,每块4比特,然后将每块从4比特扩展到6比特。扩展的规则是:每一块向左扩展一位,同时向右扩展一位,也就是说,第n块向左扩展一位,与第n-1块未扩展前的最后一位相同,同时向右扩展一位,与第n+1块未扩展前的最后一位相同;,2020/6/4,61,.,3.算法加密具体过程,例如由表2-8所知的序列M1,得到加密时的L0和R0分别是:,首先将R0分为8块,得到数据:1001011101010110101110011100000,如图2-4所示,,2020/6/4,62,.,3.算法加密具体过程,2020/6/4,63,.,3.算法加密具体过程,异或运算:由图2-3所示,经过扩展后的48比特Ri-1将与第i轮加密密钥Ki进行异或运算,密钥Ki也是48位,由原始密钥经过循环左移以及置换排列的方式产生,具体的生成过程后面将详细描述。48位的Ki同Ri-1一样,也分成8块,每块6比特,然后与扩展后的Ri-1对应的各块做异或运算后,同样生成8个6位比特块,其输出是S盒子的输入。,2020/6/4,64,.,3.算法加密具体过程,假设密钥Ki的第1块6比特数据为:110111,图2-4所示的第一块扩展比特是010010,则两者异或的结果是100101,2020/6/4,65,.,3.算法加密具体过程,S盒替代DES算法中的S盒子由8个子盒S1、S2、S3、S4、S5、S6、S7、S8组成,每个盒子构成4行16阶的416矩阵,表2-9列出了其中一个子盒S1的定义。,2020/6/4,66,.,3.算法加密具体过程,2020/6/4,67,.,3.算法加密具体过程,S盒子的输入是上述所讲的由Ri-1与Ki两者异或运算得到的结果,其中第j个子盒Sj的输入是第j块异或运算的结果,输出是根据Sj盒子定义得到的4比特数据。,2020/6/4,68,.,3.算法加密具体过程,对于每个盒子Sj(j=1,2.8)其输入与输出之间的映射关系是:将Sj输入的第一位与最后一位两个二进制组合起来,得到某个十进制数m,m用来选择矩阵Sj的行;Sj输入的中间四比特数据组合,得到十进制数n,n用来选择矩阵Sj的列。已知行m与列n,查找已经定义好的矩阵Sj的m行n列对应的值,该值就是Sj的输出。,2020/6/4,69,.,3.算法加密具体过程,对应前面叙述的例子,S1盒子的输入是F函数第二步异或运算所得结果,为数据100101,S1盒子的输出通过表2-9确定,具体的方法是:将输入的第1位“1”与第6位“1”构成二进制数“11”,“11”表示十进制数3,即要选择矩阵S1的第3行,输入的中间四位二进制数“0010”,表示十进制数2,即要选择矩阵S1的第2列,在表2-4中,第3行第2列对应的二进制数是1000,2020/6/4,70,.,3.算法加密具体过程,置换F函数的最后一步是对S盒子输出的32比特数据进行置换,目的是使得S盒的输出对下一轮多个Si子盒产生影响,以增强DES的安全性。F函数的输出结果与上一轮加密处理的左半部分数据Li-1异或,得到第i轮加密处理的右半部分32位数据Ri。然后Li与Ri又作为第i+1轮加密处理时的输入数据,这样,经过16轮迭代加密处理之后,得到L16与R16。,2020/6/4,71,.,3.算法加密具体过程,将R16与L16左右换位,即将R16的32比特数据移到左边,L16的32比特数据移到右边。换位之后,再次经过逆初始矩阵IP-1置换,最终得到的结果就是密文。,2020/6/4,72,.,4.DES算法解密过程,DES的解密算法与加密算法除了在每一轮循环迭代时所使用的控制密钥不同之外,其他的完全一样。并且,输出的64比特密文经过解密处理过程,所得结果就是所需的明文。,2020/6/4,73,.,5.密钥的生成,DES算法定义的分组长度是64比特,其主密钥长度与明文分组长度一样,也是64比特,不过在实际使用中,只用到56比特,还有8比特用作奇偶校验位。每轮迭代所使用的密钥Ki(i=1,2.16)都是从主密钥生成的,Ki的长度是48比特。密钥的具体生成方法如图2-5所示:,2020/6/4,74,.,5.密钥的生成,2020/6/4,75,.,6.DES算法安全性分析,关于DES算法的安全性,在最初公布的时候,曾受到很多人的置疑。比如有人认为算法中实际使用的密钥只有56位,过短,难以抵抗穷举式攻击,攻击者会很容易的破译DES算法密钥;更多的人担心保密设计的S盒子的安全性,他们猜测S盒之所以不公开设计标准,是否意味着公布该算法的政府机构隐藏了“后门”。但是随着DES算法在实践中的广泛使用以及密码分析技术的突破,上述大多数问题都有了答案。,2020/6/4,76,.,6.DES算法安全性分析,在DES刚开始公布的时候,曾经有很多用户担心S盒子存在隐藏的弱点,利用这种弱点,公布该算法的美国国家安全局NSA能够在不知道密钥的情况下解密DES加密的报文信息。但是通过多年来对DES算法在实践中的使用分析,以及90年代初差分密码分析技术的公布都证实了DES的S盒子具有很强的防范攻击的能力,这种担心S盒子有弱点的想法是多余的。,2020/6/4,77,.,6.DES算法安全性分析,DES算法为什么需要16次循环迭代?而不是15次或者更多的20次呢?从一定程度上来说,迭代的次数越多,密码分析的难度就会越大,但是相应的加解密所需的时间与代价也会随之增大,算法的效率与性能将会受到影响,所以一方面不能一味的为了防止攻击者破译密码,不断增加循环迭代次数,另一方面,较少的迭代次数又会导致攻击者容易分析密码算法,从而破译出密钥。,2020/6/4,78,.,6.DES算法安全性分析,关于DES算法使用56位密钥是否安全问题。56比特密钥,其密钥空间是256,大约有7.21016个密钥,如果使用最简单的穷举式攻击方法,一台每微妙完成一次DES加密的机器将要花费255us,即要1142年时间才能完成密钥的搜索,这个代价在上世纪70年代DES密钥提出的时候,几乎是计算不可行的,所以很长一段时间以来,DES被广泛使用在安全级别要求不高的场合。但是20世纪90年代以来,随着计算能力的提高以及分布式计算的使用,56位的DES算法安全强度越来越低,1997年3月,美国程序员verser利用因特网成功找到DES密钥,就表明破解56位的DES密钥已经成为事实,显然,从计算上讲,56位密钥的DES不能再认为是安全的。,2020/6/4,79,.,2.2.3高级加密标准AES,1.AES的起源2.AES的设计原则,2020/6/4,80,.,1.AES的起源,1997年9月,NIST征集AES方案,以替代DES。1999年8月,以下5个方案成为最终候选方案:MARS,RC6,Rijndael,Serpent,Twofish。2000年10月,由比利时的JoanDaemen和VincentRijmen提出的算法最终胜出。(Rijndael读成RainDoll。)2000年12月,美国国家标准局NIST正式确认新一代数据加密标准是高级加密标准AES(AdvancedEncryptionStandard)。,2020/6/4,81,.,2.AES的设计原则,能抵抗所有已知的攻击;在各种平台上易于实现,速度快;设计简单,是一种分组密码体制,加密和解密使用相同的密钥,属于对称密码体制;与DES分组密码体制不同的是,AES中明文或密文分组长度以及密钥长度不是固定的,而是可变的,它们可以是128比特、192比特、256比特。,2020/6/4,82,.,2.3公钥密码体制,2.3.1公钥密码体制的基本原理2.3.2RSA算法2.3.3有限域上椭圆曲线密码算法ECC2.3.4公钥密码体制的应用,2020/6/4,83,.,2.3.1公钥密码体制的基本原理,是密码学一次伟大的革命1976年,Diffie和Hellman在“密码学新方向”一文中提出使用两个密钥:公密钥、私密钥加解密的非对称性利用数论与其他数学难题的方法是对对称密码的重要补充,2020/6/4,84,.,2.3.1公钥密码体制的基本原理,重要特点仅根据加密算法和加密密钥来确定解密密钥在计算上不可行两个密钥中的任何一个都可用来加密,另一个用来解密。六个组成部分:明文、密文;公钥、私钥;加密、解密算法,2020/6/4,85,.,2.3.1公钥密码体制的基本原理,1.公钥密码体制依赖的基础2.公钥密码系统的特征3.公钥密码体制加解密过程,2020/6/4,86,.,1.公钥密码体制依赖的基础,经典的公钥密码算法RSA、椭圆曲线密码算法ECC等都是依赖某类数学问题的,它们共同的特点是基于某个单向陷门函数。单向陷门函数y=fk(x)是指同时满足下列条件的一类可逆函数:函数是一一映射关系,也就是说,对于每个函数值y,只有唯一的一个原象x与之对应;给定x与关键参数k,函数y=fk(x)很容易计算;,2020/6/4,87,.,1.公钥密码体制依赖的基础,给定y,存在某个关键参数k,在未知k时,由y计算出x非常困难,即在未知k的条件下,逆函数x=f-1(y)的计算相当复杂,实际上是不可行的;在已知k时,对给定的任何y,若其对应的x存在,则逆函数x=f-1k(y)很容易计算;给定y和参数k,无法从函数y=fk(x)推导出影响其逆函数f-1的关键参数k。,2020/6/4,88,.,2.公钥密码系统的特征,根据密码系统的组成以及公钥密码体制自身的特点,一个公钥密码系统可以表示为:加密算法E、解密算法D、公钥/私钥(PK/SK)对、明文M、密文C六个元素,且各元素必须要满足以下条件:,2020/6/4,89,.,2.公钥密码系统的特征,密钥。要满足三点要求:公钥/私钥(PK/SK)对容易产生,且私钥除了生成密钥的用户自己知道之外,其他任何人都不可知;PK和SK中的任何一个都可以用于加密,相应的另一个用于解密;已知公钥PK,无法计算出私钥SK,即公钥密码系统所要满足的基本条件之一是从公开密钥无法通过计算得到私有密钥。,2020/6/4,90,.,2.公钥密码系统的特征,加密算法E。要满足两点要求:已知公钥PK,对任何明文M,由E计算出密文C非常容易,即C=EPK(M)易计算,或者已知私钥SK,对任何信息M,由E计算数字签名也非常容易,即C=ESK(M)易计算。,2020/6/4,91,.,2.公钥密码系统的特征,解密算法D。要满足两点要求:已知私钥SK,对任何密文C,由D容易计算出明文M,或者已知公钥PK,对任何用SK所做的数字签名C,容易通过D计算,得到签名前的信息;但是已知公钥PK、密文C,以及解密算法D,无法由三者推导出明文M或者私钥SK。即仅知道解密算法以及加密密钥,推导明文和解密密钥都是计算不可行的。,2020/6/4,92,.,3.公钥密码体制加解密过程,假设网络上的两个用户Alice和Bob需要进行秘密通信,为了防止攻击者Eve窃听信息,Alice和Bob选择使用公钥密码体制加密传输的信息。Alice是信息的发送方;Bob是信息的接收方。Alice与Bob产生公钥/私钥对:PKA/SKA,PKB/SKB。,2020/6/4,93,.,3.公钥密码体制加解密过程,Alice与Bob通过某种机制公布各自的公钥PKA与PKB,例如将公钥放到一个公共的服务器,供其他用户查询。,2020/6/4,94,.,3.公钥密码体制加解密过程,Alice通过查询公共服务器获得Bob的公钥PKB。如果Alice欲给Bob发送报文M,他就用Bob的公钥PKB加密报文。已知待加密的明文M以及Bob的公钥PKB,Alice很容易通过加密算法E计算出密文,即C=EPKB(M)。,2020/6/4,95,.,3.公钥密码体制加解密过程,接收方Bob收到Alice发送的信息之后,使用自己的私钥SKB解密报文。已知密文C私钥SKB,Bob很容易通过解密算法计算出明文M,即M=DSKB(C)。,2020/6/4,96,.,2.3.2RSA算法,1.RSA算法依赖的数学问题2.RSA算法密钥产生过程3.RSA算法加解密过程4.RSA算法安全性及性能分析,2020/6/4,97,.,1.RSA算法依赖的数学问题,模运算的性质:正整数n是素数,集合Zn=0,1,2.,(n-1)表示小于n的所有非负整数集合,则对于集合Zn中的每一个整数wZn,均存在一个z,满足公式wz=1modn,我们称z是w的乘法逆元,且n是它们的模。,2020/6/4,98,.,1.RSA算法依赖的数学问题,费马定理:如果p是素数,a是不能整除p的正整数,则:ap-11modp例如:P=7,a=2,则27-1=26=64,64mod7=1,2020/6/4,99,.,1.RSA算法依赖的数学问题,欧拉函数:正整数n的欧拉函数是指小于n且与n互素的正整数个数,通常记为(n)。对于任一素数p,显然有:(p)p1,例如:设p=3,小于3且与3互素的正整数为1,2,因此(3)=2;类似地,当p=7时,小于7且与7互素的正整数为1,2,3,4,5,6,因此(7)=6,2020/6/4,100,.,1.RSA算法依赖的数学问题,假定有两个不同的素数p和q,n是p与q之积,即n=pq,则有如下公式关系:(n)=(pq)=(p)(q)=(p-1)(q-1)例如:取n=21,(21)=(3)(7)=(3-1)(7-1)=26=12,其中这12个整数是1,2,4,5,8,10,11,13,16,17,19,20,2020/6/4,101,.,1.RSA算法依赖的数学问题,欧拉定理:任何两个互素的整数a和n,有如下关系:a(n)=1modn例如:a=3;n=8;由(3)欧拉函数的定义,(8)=4;则a(n)=34=81=108+11mod81modn,2020/6/4,102,.,1.RSA算法依赖的数学问题,欧几里德(Elucid)算法:该算法主要的思想是:用一个简单的方法确定两个正整数的最大公因子,并且如果这两个整数互素,通过扩展该算法能确定它们各自的逆元,2020/6/4,103,.,2.RSA算法密钥产生过程,随机选择两个大素数p与q,且pq=n。为了增强算法的安全性,避免攻击者通过数学攻击的方法找到n的欧拉函数(n),从而攻破RSA密码方案,RSA算法的设计者建议p与q长度应该只差几个数字,且p与q应该位于区间1075.10100内。计算n的欧拉函数值:(n)=(p-1)(q-1)。,2020/6/4,104,.,2.RSA算法密钥产生过程,随机选择一个大的正整数e,e满足小于n且与(n)互素的条件,即e与(n)的最大公因子是1根据e,(n),计算另外一个值d,d是e的乘法逆元,且(n)是它们的模,由模运算的及乘法逆元的性质,de=1mod(n)则两个二元组(e,n)、(d,n)构成RSA的密钥对,选择其中任意一个二元组作为公钥,则另外一个就为私钥,在此,我们定义(e,n)为公钥,(d,n)为私钥。,2020/6/4,105,.,2.RSA算法密钥产生过程,例如:1)令p=7,q=11,则n=77;2)计算n的欧拉函数值(n)=(7-1)(11-1)=60;3)选择e=17,e符合小于77,且于欧拉函数值(n)((n)=60)的最大公因子是1的条件;4)计算e的逆元d,因为5317=1560+11mod60,所以当e=17时,d=53。因此(17,77)/(53,77)构成一个RSA的公钥/私钥对。,2020/6/4,106,.,3.RSA算法加解密过程,RSA算法属于分组加密方案,也就是说明文以分组为单位加密,分组的大小取决于所选的模n的值,明文块每个分组的长度可以相同也可以不同,但是,各分组大小必须小于或等于log2(n)的值。已知明文的某块分组报文M,公钥(e,n),私钥(d,n),则加密过程如下:对M的e次方幂指数运算结果再做模n运算,所得结果即为密文C,即由M计算C用公式表示为:C=EpK(M)=Memodn(公式21),2020/6/4,107,.,3.RSA算法加解密过程,RSA算法加密和解密过程是等价的,解密过程如下:对C的d次方幂运算结果再做模n运算,所得结果即为明文M,即由C推导M可用公式表示为:M=DSK(M)=Cdmodn(公式22),2020/6/4,108,.,3.RSA算法加解密过程,2020/6/4,109,.,3.RSA算法加解密过程,2020/6/4,110,.,4.RSA算法安全性及性能分析,RSA算法的安全性基于大整数因子分解的困难性,即给定大整数n,将n分解为两个素数因子p与q,在数学上已证明是难题,至今没有有效的方法予以解决。RSA密码方案的优点在于原理简单,易于使用,2020/6/4,111,.,4.RSA算法安全性及性能分析,缺点:RSA的性能比较低。因为算法中使用的模数n以及p与q都是大整数,因此无论是用硬件实现还是软件实现效率都比较低,其中硬件实现的效率是DES的1/1000,软件实现的效率是DES的1/100,由此可见,RSA不适用于对长的明文信息加密,它常常与对称密码体制结合使用,RSA用来加密通信双方的会话密钥,对称密码体制如DES用来加密传输的报文。,2020/6/4,112,.,4.RSA算法安全性及性能分析,为了安全起见,RSA方案中要求模数n越来越大。当前,RSA密钥长度要求大于1024比特才有安全保障,在安全要求比较高的政府等部门,需要采用2048比特长的密钥。密钥长度的增加提高了安全性,但是进一步影响了算法的性能,RSA算法加解密的速度会越来越慢,对系统的要求较高,因此,在选择RSA密钥时,不能只考虑安全性,单纯的扩大RSA密钥长度,在系统的安全性和性能之间需要找到一个平衡点。,2020/6/4,113,.,2.3.3有限域上椭圆曲线密码算法ECC,1985年NealKobiltz和Victormiller提出椭圆曲线密码算法ECC(EllipticCurveCryptosystem)1.ECC算法依赖的数学问题2.ECC算法密钥的选择3.ECC算法的加解密过程4.ECC算法的安全性分析,2020/6/4,114,.,1.ECC算法依赖的数学问题,椭圆曲线定义:设K表示一个域,椭圆曲线E(K)用二元方程表示:y2+axy+by=x3+cx2+dx+e其中a,b,c,d,e均属于K域。在实际的密码学研究中,主要应用的是基于有限域上的椭圆曲线。具有q个元素的有限域上的椭圆曲线满足下列方程关系:y2=x3+ax+b,2020/6/4,115,.,1.ECC算法依赖的数学问题,椭圆曲线上的点加运算:设P、Q是E上任意两点,R是连接P,Q的直线L与E相交点,R关于X轴的对称节点是R,如图2-6所示。根据椭圆曲线的对称性,R必定在椭圆曲线E上定义:R=P+Q,R就是P与Q点加的和,2020/6/4,116,.,1.ECC算法依赖的数学问题,2020/6/4,117,.,1.ECC算法依赖的数学问题,如果P和Q相同,即P与Q是椭圆曲线的某一点,如图2-7所示,则过P做椭圆的切线,该切线同E相交点为M,M关于X轴的对称点M就是P+P的点加和,即M=P+P,我们将P+P记做M=2P,以此类推,n个P相加P+P+P.+P记做nP,nP也称为倍乘。根据椭圆曲线的性质,2P、3P.nP都是E上的点。,2020/6/4,118,.,1.ECC算法依赖的数学问题,2020/6/4,119,.,1.ECC算法依赖的数学问题,椭圆曲线离散对数问题给定椭圆曲线E及该椭圆曲线上的一点P,kP表示k个P相加,k为某整数,如果椭圆曲线上存在一点Q,能够满足方程Q=kP,那么椭圆曲线离散对数问题就是给定点P和点Q,求解k的问题,在数学上该问题是同时涉及整数因式分解和离散对数的难题。,2020/6/4,120,.,1.ECC算法依赖的数学问题,ECC算法就是基于“椭圆曲线离散对数问题”难以求解而设计的,给定P和k容易通过方程Q=kP计算Q;但是反过来,给定Q和P,求k在计算上是不可行的,因此我们可以设定k为私钥。,2020/6/4,121,.,2.ECC算法密钥的选择,基于椭圆曲线密码体制的ECC算法在加解密之前,首先要给出椭圆曲线域的一些参数,如基点P,阶n,以确定具体的椭圆曲线。ECC算法密钥的产生是都是建立在某个有限域的椭圆曲线上,设给定一个具有q个元素有限域的椭圆曲线E,E的基点是P,P的阶为n。,2020/6/4,122,.,2.ECC算法密钥的选择,(1)密钥的产生者在区间2,n-1随机选取某整数k;(2)计算Q=kP。则Q就是公钥,私钥是k。,2020/6/4,123,.,3.ECC算法的加解密过程,假设网络上的用户Alice和Bob要进行保密通信,它们选择ECC算法加密通信的报文。Alice与Bob知道同一条椭圆曲线E,并已分别产生公钥/私钥对kA/QA,kB/QB,Alice欲发送明文m送给Bob,并且已获知Bob的公钥QB。,2020/6/4,124,.,3.ECC算法的加解密过程,Alice加密过程如下:(1)首先要将明文m编码成椭圆曲线上的点Pm,Pm为(Xm,Ym);(2)Alice随机选择整数k2,n-1;(3)计算kP=R1(X1,Y1),(kQB=R2(X2,Y2);如果X2=0;则返回到(2);则密文C由R1,Pm+R2组成;,2020/6/4,125,.,3.ECC算法的加解密过程,Bob收到密文C后,解密过程如下:(1)计算kBR1=kBkP=kkBP=kQB(2)Bob利用密文C的第二点的值R2+Pm减去由(1)计算得到的结果kQB,即Pm+R2kQB=Pm+kQBkQB=Pm;(3)Bob得到椭圆曲线上点Pm,然后按照某种解码方法从点Pm获取明文m。,2020/6/4,126,.,4.ECC算法的安全性分析,ECC算法的安全性依赖于椭圆曲线离散对数问题计算的困难性,如果离散对数问题容易计算,从用户的公钥能够推导出私钥,那么整个密码体制就会坍塌。,2020/6/4,127,.,4.ECC算法的安全性分析,相对于RSA,ECC具有一定的优势:安全性高解决椭圆曲线上的离散对数问题,其时间复杂度是完全指数阶的,而RSA所依赖的大整数因子分解问题,其时间复杂度是子指数阶的,因此攻击ECC的复杂度比RSA要高得多;,2020/6/4,128,.,4.ECC算法的安全性分析,相对于RSA,ECC具有一定的优势:密钥短ECC算法中所使用的密钥长度比RSA中要短很多,一般加解密时使用160位长度密钥,据统计,160位密钥ECC与1024位RSA安全强度相同性能高ECC算法的性能比RSA算法要高,其加解密速度比RSA要快得多。,2020/6/4,129,.,4.ECC算法的安全性分析,2020/6/4,130,.,4.ECC算法的安全性分析,随着计算能力的提高,从安全性角度考虑,对密钥长度的要求越来越高。相对于其他公钥密码算法,ECC逐渐体现出其优越性。但是自从使用公钥密码体制以来,实际应用中,RSA算法因为原理简单被广泛使用,ECC算法在实际应用中相对比较少。但是随着时间的推移,ECC算法理论不断完善,相信它逐渐会被应用到实际系统中。,2020/6/4,131,.,2.3.4公钥密码体制的应用,1.用于加解密信息2.用于数字签名,2020/6/4,132,.,2.4量子密码体制,2.4.1概述2.4.2量子密码原理2.4.3量子密钥分配2.4.4量子密钥分配协议BB842.4.5量子密码体制的发展与现状2.4.6三大密码体制的比较,2020/6/4,133,.,2.4.1概述,对称密码体制与公钥密码体制绝大部分算法都是实际上保密的密码体制,理论上并不保密。理论上唯一能确保不可破译的密码体制是一次一密密码1918年由美国数学家vernam设计,也称vernam密码,vernam密码是一种对称密码体制,它要求密钥的长度与所需加密的明文具有相同的长度,而且每个密钥使用且只能使用一次,即一次一密密码体制,用过的密钥不能再用来加密其他任何信息。该体制需要通信双方共享与待加密的明文长度一样长的密钥,2020/6/4,134,.,2.4.1概述,对称密码体制与公钥密码体制绝大部分算法都是实际上保密的密码体制,理论上并不保密。理论上唯一能确保不可破译的密码体制是一次一密密码。该体制在实际应用中是不可行的。,2020/6/4,135,.,2.4.1概述,随着计算能力的不断增强,从安全角度考虑,基于数学问题求解困难的密码体制,逐渐需要通过扩充密钥长度来提高安全性,例如RSA算法密钥长度由原来的768位扩充到现在的1024位。1994年,AT&T试验室的PeterShor提出一种量子计算的方法,采用该方法能够在有限时间内分解大的质因数,该结论引起密码学届的普遍关注,因为这就意味着采用量子计算机将可以轻而易举地破译RSA算法,RSA公钥算法将不能再使用。,2020/6/4,136,.,2.4.1概述,1996年,Bell试验室的LovGrover发现了一种量子搜索算法,该算法可以对现有的DES算法中的密钥进行快速穷举,从而破译出密钥。因此不论是对称密码体制还是公钥密码体制,在量子计算环境下,安全性受到极大的威胁。,2020/6/4,137,.,2.4.1概述,1996年,Bell试验室的LovGrover发现了一种量子搜索算法,该算法可以对现有的DES算法中的密钥进行快速穷举,从而破译出密钥。因此不论是对称密码体制还是公钥密码体制,在量子计算环境下,安全
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 酒店审计厨房考试题及答案
- 精益知识考试题及答案
- 京东销售岗考试题及答案
- 难点详解人教版八年级上册物理声现象《声音的产生与传播》专题测评试题
- 难点解析-人教版八年级上册物理《机械运动》综合练习练习题
- 港股通知识培训课件
- 港城大BIS课件教学课件
- 苏州岗前培训考试题及答案解析
- 证券从业考试 淘宝及答案解析
- 中频炉冶炼安全培训试题及答案解析
- 雅莹(EP)品牌二次增长战略研究报告
- 50MW-100MWh储能电站项目分项造价概算表
- 2025年秋期人教版3年级上册数学核心素养教案(第2单元)(教学反思有内容+二次备课版)
- 曹冲称象的故事练习卷(进阶)小学数学三年级上册 人教新版同步单元分层作业(含解析)
- 马克思主义政治经济学练习题题
- 2025至2030中国无水葡萄糖行业产业运行态势及投资规划深度研究报告
- 《运输实务》项目5课件 水路运输操作
- 2025年水务公司竞聘部门负责人笔试试题及答案
- 实例要素式暂时解除乘坐飞机、高铁限制措施申请书(申请单次解禁用)
- 旅游英语视听说教学课件
- 患者沟通与心理护理
评论
0/150
提交评论