第2章_密码学基础(8课时)

1、 第第2章章 密码学基础密码学基础电子商务安全电子商务安全2021-7-162第2章 密码学基础问题的提出问题的提出国内第一起电子邮件侵权案国内第一起电子邮件侵权案2021-7-163第2章 密码学基础 如果电子邮件的发送附加了数字如果电子邮件的发送附加了数字签名，也许本案就不会发生了。签名，也许本案就不会发生了。 第第2章章 密码学基础密码学基础 2.1 密码学概述密码学概述 2.2 传统对称密码体制传统对称密码体制 2.3 公钥密码体制公钥密码体制 2.4 量子密码体制量子密码体制 电子商务安全电子商务安全2021-7-165第2章 密码学基础2.1 密码学概述密码学概述 2.1.1 密码

2、学起源与发展2.1.2 什么是密码学2.1.3 密码体制分类2.1.4 密码系统设计的基本原则2.1.5 密码系统攻击及分析2021-7-166第2章 密码学基础2.1.1 密码学起源与发展密码学起源与发展密码学的雏形始于古希腊人在战场上加密写有“战争机密”的信件2021-7-167第2章 密码学基础2.1.1 密码学起源与发展密码学起源与发展1.1.古典密码学古典密码学 -1949年之前，密码学是一门艺术2.2.近代密码学近代密码学 -19491975年：密码学成为科学3.3.现代密码学现代密码学 -1976年以后：密码学的新方向公钥密码学2021-7-168第2章 密码学基础隐写术隐写术(

3、steganography): 通过隐藏消息的通过隐藏消息的存在存在来保护消息来保护消息.隐形墨水隐形墨水字符格式的变化字符格式的变化a.图象图像图象图像 2.1.1 密码学起源与发展密码学起源与发展2021-7-169第2章 密码学基础象形文字的修改象形文字的修改(Modified Hieroglyphics) c. 1900 B.C. 密码学的第一个例子是对标准书写符号的修改我去君留十载中 爱无南北与西东 万株松树青山上 洁白孤高生不同 2021-7-1610第2章 密码学基础example-ii2021-7-1611第2章 密码学基础2.1.1 密码学起源与发展密码学起源与发展传说，古时

4、候有一对夫妻，男的名叫李石匠，女的叫张小花。李石匠靠手艺赚钱，张小花在家纺纱织布。一年，李石匠参加修建石桥，因工程紧张，十一个月也没回家一次。张小花独自在家只有纺车做伴。一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带去一封书信。 2021-7-1612第2章 密码学基础公元前公元前400400年斯巴达人使用密码棍年斯巴达人使用密码棍( (scytalescytale) )2021-7-1613第2章 密码学基础2.1.1 密码学起源与发展密码学起源与发展加密加密: 将要传递的信息隐藏将要传递的信息隐藏例如：清末大儒纪晓岚赠送的对联鳳遊禾蔭鳥飛去馬走蘆邊草不生禾下加鳳去掉鳥字得禿字馬置蘆

5、邊去掉草頭得驢字 2021-7-1614第2章 密码学基础Phaistos(Phaistos(范斯特范斯特) )圆盘，一种直径约为圆盘，一种直径约为160mm160mm的粘土的粘土圆盘，始于公元前圆盘，始于公元前1717世纪。表面有明显字间空格的字世纪。表面有明显字间空格的字母，至今还没有破解母，至今还没有破解2021-7-1615第2章 密码学基础转轮密码机ENIGMA，1944年装备德国海军2021-7-1616第2章 密码学基础2020世纪早期密码机世纪早期密码机2021-7-1617第2章 密码学基础2.1.1 密码学起源与发展密码学起源与发展这样的数字毫无意义么？这样的数字毫无意义么

6、？2021-7-1618第2章 密码学基础16世纪意大利数学家卡尔达诺发明的一种保密通信方法，史称“卡尔达诺漏格板”漏格板是一张用硬质材料(如硬纸、羊皮、金属等)做成的板，上面挖了一些长方形的孔，即漏格2.1.1 密码学起源与发展密码学起源与发展2021-7-1619第2章 密码学基础2.1.1 密码学起源与发展密码学起源与发展大约在1793年，当时的美国总统托马斯杰斐逊发明了一种轮子密码机。2021-7-1620第2章 密码学基础2.1.1 密码学起源与发展密码学起源与发展以二战时期以二战时期真实历史为真实历史为背景的，关背景的，关于电报密文于电报密文窃听和密码窃听和密码破解的故事破解的故事

7、2021-7-1621第2章 密码学基础2.1.2 什么是密码学什么是密码学 1.1.密码学概念密码学概念2.2.密码系统构成密码系统构成 3.3.密码系统数学模型密码系统数学模型 2021-7-1622第2章 密码学基础1. 密码学概念密码学概念密码学密码学（CryptologyCryptology） ：是研究是研究如何保护信息安全性如何保护信息安全性的一门的一门科学。它包含两个分支：科学。它包含两个分支：密码编码学和密码分析学密码编码学和密码分析学。密码编码学（密码编码学（CryptographyCryptography） ：主要研究密码方案的设计，主要研究密码方案的设计，即寻找对信息编码

8、的方法从而实现即寻找对信息编码的方法从而实现隐藏信息隐藏信息的一门学问。的一门学问。密码分析学密码分析学（CryptanalyticsCryptanalytics），）， ：主要是从攻击者的角度主要是从攻击者的角度来看问题，研究如何来看问题，研究如何破解被隐藏信息破解被隐藏信息的一门学问。的一门学问。 两个分支：两个分支：是既相互对立，又相互依存的科学。是既相互对立，又相互依存的科学。2021-7-1623第2章 密码学基础2. 密码系统构成密码系统构成 密码系统主要包括以下几个基本要素：密码系统主要包括以下几个基本要素：明文明文（Plain Text），），指的是希望得到保密的原始信息。指的

9、是希望得到保密的原始信息。通通常用常用P或或M表示。表示。用某种方法伪装信息以隐藏它的内容的过程称为用某种方法伪装信息以隐藏它的内容的过程称为加密加密(Encryption)经过加密处理后得到的隐藏信息称为经过加密处理后得到的隐藏信息称为密文密文(Cipher Text)，通常用通常用C表示。表示。 而把密文转变为明文的过程称为而把密文转变为明文的过程称为解密解密(Decryption)。2021-7-1624第2章 密码学基础2021-7-1625第2章 密码学基础加密算法加密算法(Encryption Algorithm)。通常用。通常用E表示表示。是指通过一系列的变换、替代或其他各种方式

10、是指通过一系列的变换、替代或其他各种方式将明文信息转化为密文的方法。将明文信息转化为密文的方法。解密算法解密算法(Decryption Algorithm)。通常用。通常用D表示表示。指通过一系列的变换、替代或其他各种方法将指通过一系列的变换、替代或其他各种方法将密文恢复为明文的方法。密文恢复为明文的方法。2021-7-1626第2章 密码学基础举例说明上述概念举例说明上述概念商人贾某要给他儿子发一份密码电报，电文四个字：商人贾某要给他儿子发一份密码电报，电文四个字：“抛售布匹抛售布匹”（原文）。（原文）。按照电报码手册，这四个汉字对应：按照电报码手册，这四个汉字对应：2141 0786 15

11、80 0572，然后把每个四位数都加上，然后把每个四位数都加上100（加密密钥），四（加密密钥），四个四位数就变成了：个四位数就变成了：2241 0886 1680 0672，此刻这四，此刻这四个电报码对应变为：个电报码对应变为：“抡噌庙叵抡噌庙叵”（密文）。（密文）。儿子收到电报儿子收到电报“抡噌庙叵抡噌庙叵”后，根据相应的电报码手册后，根据相应的电报码手册得到：得到： 2241 0886 1680 0672，按照事先的约定，分别，按照事先的约定，分别减去减去100（解密密钥），就得到（解密密钥），就得到“抛售布匹抛售布匹”的信息。的信息。2021-7-1627第2章 密码学基础2. 密码系

12、统构成密码系统构成 加解密算法通常都是在一组密钥的控制下进行的，分别称为加密密钥和解密密钥。加密和解密过程如下图所示。明文明文密文加密算法解密算法加密密钥解密密钥2021-7-1628第2章 密码学基础3. 密码系统数学模型密码系统数学模型 以五元组（M，C，K，E，D）表示密码系统，其中M是明文信息空间，C是密文信息空间，K是密钥信息空间，E是加密算法，D是解密算法。各元素之间有如下的关系：E：M K - C，表示E是M与K 到C的一个映射；D：C K - M，表示D是C与K到 M的一个映射。2021-7-1629第2章 密码学基础3. 密码系统数学模型密码系统数学模型 在最早的恺撒密码体制

13、中明文信息空间是26个英文字母集合，即M = a,b,c,d z, A,BZ；密文信息空间也是26个英文字母集合，即C= a,b,c,d .z, A,B.Z密钥信息空间是正整数集合，即 K= N | N=1,2.；因此Ek = (M+K) mod 26；与之对应的解密算法是Dk ，Dk =（C-K）mod 26。2021-7-1630第2章 密码学基础3. 密码系统数学模型密码系统数学模型 例如：恺撒密码体制加密算法：(M+K) mod 26A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 10 11

14、 12 13 14 15 16 17 18 19 20 21 22 23 24 25明文 hello world密钥：K=5密文 mjqqt btwqi解密算法：(C-K) mod 262021-7-1631第2章 密码学基础3. 密码系统数学模型密码系统数学模型 发送信息的一方使用密钥K加密明文M，通过加密算法得到密文C，即C = EK（M）；接收信息的一方使用密钥K解密密文C，通过解密算法得到明文M，即M = DK ( C )；。K与K可能相等，也可能不等，具体取决于所采用的密码体制。 2021-7-1632第2章 密码学基础3. 密码系统数学模型密码系统数学模型 明文m加密算法：密文c=

15、Ek1(m)加密密钥源解密密钥源解密算法：m=Dk2(c) 明文mmmk1k2cc2021-7-1633第2章 密码学基础2.1.3 2.1.3 密码体制分类密码体制分类 按不同的划分标准或者方式，密码体制可以分为多种形式。我们主要从加密方式、所采用的密钥方式以及保密程度来划分。 2021-7-1634第2章 密码学基础1. 按加密方式划分按加密方式划分 （1）流密码体制。- 也称为序列密码，它是将明文信息一次加密一个比特形成密文字符串，典型的流密码体制是一次一密密码体制，其密钥长度与明文长度相等。 （2）分组密码体制。 - 也称为块密码体制，分组密码则是将明文信息分成各组或者说各块，每组具有

16、固定的长度，然后将一个分组作为整体通过加密算法产生对应密文的处理方式。2021-7-1635第2章 密码学基础1. 按加密方式划分按加密方式划分 流密码 明文m写成连续的符号m=m1m2， 密钥流k=k1k2 第i个元素ki对明文中的第i个元素mi进行加密， 加密后的密文c=Ek(m)= Ek1(m1) Ek2(m2)Eki(mi)。 解密后：m=Dk(c)=Dk1(Ek1(m1)Dk2(Ek2(m2)=m1m2。2021-7-1636第2章 密码学基础1. 按加密方式划分按加密方式划分 流密码加密算法E解密算法D明文mi密文ci=Eki(mi)明文mi=Dki(ci )密钥ki密钥ki202

17、1-7-1637第2章 密码学基础 分组密码2021-7-1638第2章 密码学基础2. 按使用的密钥方式划分按使用的密钥方式划分 （1）单密钥体制。- 也称为对称密码机制，在该体制下，密码系统只有一个密钥，加密算法和解密算法使用统一的一个密钥，拥有密钥的用户既可以加密信息也可以解密信息。（2）双密钥体制。- 也称为非对称密码体制或者公钥密码体制，在该体制下，密码系统有两个密钥，分别是公开密钥和私有密钥，公开密钥是对外公开的，即所有的人都可知，私有密钥是只有特定的用户方能拥有。2021-7-1639第2章 密码学基础3. 按保密程度划分按保密程度划分 （1）实际上保密的密码体制。- 是指在理论

18、上可破解，但是在现有的客观条件下以及有限的时间内，无法通过计算从密文破译出明文或者密钥的密码体制。（2）绝对保密的密码体制。- 是指无论在理论上还是实际上，都不可破解的密码体制。 2021-7-1640第2章 密码学基础2.1.4 密码系统设计的基本原则密码系统设计的基本原则 （1）简单实用原则。（2）抗攻击性原则 。（3）算法公开化原则 。2021-7-1641第2章 密码学基础2.1.5 密码系统攻击及分析密码系统攻击及分析 对密码系统的攻击分为被动攻击和主动攻击- 被动攻击是指通过窃取密文试图了解明文或者密钥的内容；主动攻击是指篡改和伪造密文，以达到修改或者伪造明文的目的。- 被动攻击的

19、主要方法有：通过窃听通信信道上传输的密文，对其进行分析破译出明文为或者密钥； - 主动攻击的主要方法有：攻击者截取通信信道上传输的密文，然后对其篡改（如添加、删除某些内容）再发送2021-7-1642第2章 密码学基础2.2 传统对称密码体制传统对称密码体制 在公钥密码体制出现以前，无论是古典密码还是近现代密码都属于对称密码体制，也就是说加密和解密使用同一个密钥。2.2.1 加解密的基本原理 2.2.2 数据加密标准DES 2.2.3 高级加密标准AES 2021-7-1643第2章 密码学基础2.2.1 加解密的基本原理加解密的基本原理基于对明文信息的“置换”和“替代”完成的，或者是通过对两

20、者的组合运用即乘积的方式完成。 2021-7-1644第2章 密码学基础1. 置置 换换 置换又称“换位”方法，是指变换明文中各元素的相对位置，但保持其内容不变的方法，即通过对明文元素重新排列组合来达到隐藏明文原始内容所表达含义的加密方法。最典型的置换密码体制是栅栏密码技术。2021-7-1645第2章 密码学基础1. 置置 换换 栅栏加密算法步骤如下：将明文的元素按照两行的方式书写，并按照从上到下，从左到右的方式排列；按从上到下的顺序依次读出每一行的元素所得到的组合就是密文。 明文信息economic business栅栏密码表示e o o i b s n s c n m c u i e s

21、eooibsnscnmcuies密文2021-7-1646第2章 密码学基础1. 置置 换换 栅栏解密算法步骤如下：将接收到的密文按照从左到右的顺序写为两行，如果密文元素的个数为偶数n，则每一行写n/2个元素；如果密文元素个数为奇数，则第一行排列n+1/2个元素，第二行排列n-1/2个元素；按照加密算法的规则，依次从上到下，从左到右的规则读取各元素，所得到的字母序列即获得所需要的明文。2021-7-1647第2章 密码学基础1. 置置 换换 明文信息economic businesse o o i b s n s c n m c u i e seooibsnscnmcuies密文2021-7-

22、1648第2章 密码学基础1. 置置 换换 一种改进的方案是将明文元素以矩阵的方式排列，假设明文可以写成nm的n行m阶的矩阵，矩阵法:按照nm的矩阵格式从左到右依次写出明文元素；根据密钥的内容指示，读出相应各列的明文元素；所有读出的元素按一行的顺序排列，得到的结果即为密文。 2021-7-1649第2章 密码学基础1. 置置 换换 electronical business明文45矩阵 e l e c t r o n i c a l b u s i n e s s密钥3 2 4 5 1enbelolnciustcsserai密文例如：2021-7-1650第2章 密码学基础1. 置置 换换 矩

23、阵法解密算法是：根据密钥长度将密文写成矩阵形式，但书写的格式是按照逐列写，各列之间的排列顺序参照密钥内容的编号；依次读取排列好的矩阵逐行元素，得到的结果就是明文。 2021-7-1651第2章 密码学基础1. 置置 换换 electornical business e l e c t r o n i c a l b u s i n e s senbelolnciustcsserai密钥3 2 4 5 1明文密文45 e l c t e n o i c r b l u s a e n s s i2021-7-1652第2章 密码学基础1. 置置 换换置换法破译: 通过字母的使用频率破译2021-

24、7-1653第2章 密码学基础2. 替替 代代 替代方法是将明文各元素的内容用新的符号或者符号组合代替，替换之后形成的新的元素符号集合便是密文。 A B C D E F G H V W X Y ZF G H I J K L M A B C D E hello worldmjqqt btwqi 明文密文密钥k=52021-7-1654第2章 密码学基础2. 替代替代密码分析密码分析给定加密信息：PHHW PH DIWHU WKH SDUWB由于：加密算法已知 可能尝试的密钥只有26个通过强力攻击得到明文：Meet me after the party替代法容易受到攻击!2021-7-1655第2

25、章 密码学基础2.2.1 加解密的基本原理加解密的基本原理将置换和替换两者交替使用的密码编码方法称为乘积密码Feistel密码结构就是乘积密码Feistel密码结构经过多轮循环的置换与替代操作现在普遍使用的分组密码体制设计原理几乎都遵循Feistel密码结构，如经典的数据加密标准DES。 2021-7-1656第2章 密码学基础2.2.2 数据加密标准数据加密标准DES DES 2021-7-1657第2章 密码学基础1. DES的产生的产生 1972年，美国标准局NBS（现在的NIST）公开征求用于计算机通信数据保密的方案，其要求为：算法必须提供高度的安全性；算法必须有详细的说明，并易于理解

26、；算法的安全性取决于密钥，不依赖于算法；算法适用于所有用户；算法适用于不同应用场合；算法必须高效、经济；算法必须能被证实有效；算法必须可出口。2021-7-1658第2章 密码学基础1. DES的产生的产生IBM公司的W.Tuchman和C.Meyers等研究人员提交了一个数据加密算法Lucifer该算法被美国标准局采用，在经过一系列的研究讨论和简单的修改于1977年正式批为数据加密标准DES。2021-7-1659第2章 密码学基础2. DES算法基本原理算法基本原理 DES属于典型的分组密码体制。DES将明文信息按64比特大小分组，密钥长度也是64比特，但是实际使用过程中密钥长度是56比特

27、，另外8比特用作奇偶校验位（即每个字节的最后一位用作奇偶校验）。64比特的明文分组在密钥的作用下经过多次的置换和替代组合操作，最终形成攻击者难以破译的64比特密文。 2021-7-1660第2章 密码学基础2. DES算法基本原理算法基本原理 置换和替代的多次组合过程置换和替代的多次组合过程多轮循环加密来扰乱和扩散明文信息多轮循环加密来扰乱和扩散明文信息 2021-7-1661第2章 密码学基础2. DES算法基本原理算法基本原理 DES算法加密的基本原理： 加密过程中输入加密过程中输入6464比特的明文，首先经过初始矩比特的明文，首先经过初始矩阵阵IPIP置换；置换； 在在5656比特的输入

28、密钥控制下，进行比特的输入密钥控制下，进行1616轮迭代加密轮迭代加密处理过程处理过程； 通过简单的换位和逆置换算法，得到通过简单的换位和逆置换算法，得到6464比特的输比特的输出密文。出密文。2021-7-1662第2章 密码学基础2. DES算法基本原理算法基本原理 DES算法加密的基本原理：2021-7-1663第2章 密码学基础2. DES算法基本原理算法基本原理 DESDES算法解密的基本原理：算法解密的基本原理：解密处理过程与加密处理过程顺序完全一样解密处理过程与加密处理过程顺序完全一样加密过程：加密过程：K K1 1 = K = K1616解密过程：解密过程：K K1 1 = K

29、 = K16 16 2021-7-1664第2章 密码学基础3. 算法加密具体过程算法加密具体过程DES加密算法主要由加密算法主要由4个元素组成：个元素组成：初始置换矩阵初始置换矩阵IP、加密函数加密函数F、 S-盒子、逆初始置盒子、逆初始置换矩阵换矩阵IP-1。 2021-7-1665第2章 密码学基础3. 算法加密具体过程算法加密具体过程初始置换初始置换：初始置换矩阵：初始置换矩阵IPIP 58 60 62 64 57 59 61 63 5052 54 56 49 51 53 55 42 44 46 48 41 43 45 47 61 34 36 38 40 33 35 37 39 2 4

30、 6 8 1 3 5 7 10 12 14 16 9 11 13 15 26 28 30 32 25 27 29 31 18 20 22 24 17 19 21 23 表 2-5 初始置换矩阵 IP 40 39 38 37 36 35 34 33 8 7 6 5 4 3 2 1 48 47 46 45 44 43 42 41 61 16 15 14 13 12 11 10 9 32 32 30 29 28 27 26 25 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 24 23 22 21 20 19 18 17 表 2-6 逆初始置换矩阵

31、IP-1 2021-7-1666第2章 密码学基础3. 算法加密具体过程算法加密具体过程初始置换初始置换：由置换矩阵可知置换规则：由置换矩阵可知置换规则：将原先处在第58位置的比特置换后放在第1个位置，第50位置的比特置换后放在第2个位置，第7个位置的比特置换后放在第64个位置。如果明文M分组是序列m1 m2 m3 .m64，则经过IP置换后变成序列m58 m50 m42 .m7。 2021-7-1667第2章 密码学基础3. 算法加密具体过程算法加密具体过程初始置换：举例，假设64比特明文M是： 10010000 10110001 11100000 01011100 11111000 000

32、01111 01110111 11001011按照初始置换矩阵IP的变换规则，将M变换为M1，M1序列是： 11011100 01011011 01101000 11100010 10010111 01010110 10111000 111000002021-7-1668第2章 密码学基础3. 算法加密具体过程算法加密具体过程 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 1

33、 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 表 2-7 置换前矩阵 M 表 2-8 置换后矩阵 M1 M写成88的矩阵，如表2-7所示。初始置换后如表2-8所示 2021-7-1669第2章 密码学基础3. 算法加密具体过程算法加密具体过程通过比较表2-7与表2-8，可以发现，M由置换矩阵IP变换到M1遵循一定的规律：矩阵M1的第1行是矩阵M的第2列的倒置，第2行是矩阵M的第4列倒置，第5行是矩阵M

34、的第1列的倒置。概括的说，置换后的矩阵M1前4行是明文矩阵M各偶数列的倒置，后4行是明文矩阵M各奇数列的倒置。2021-7-1670第2章 密码学基础3. 算法加密具体过程算法加密具体过程再次对照逆初始矩阵IP-1（如表2-6所示）可发现，将M1前4行各行的倒置作为新矩阵M2的偶数列，后4行各行的倒置作为新矩阵M2的奇数列，会得到结果M=M2。也就是说将任何明文M经过初始矩阵IP置换，然后再经过逆初始矩阵IP-1的置换，M的值保持不变 2021-7-1671第2章 密码学基础3. 算法加密具体过程算法加密具体过程每轮迭代加密处理过程： DES算法加密过程需要16轮迭代处理，每一轮迭代的处理步骤

35、是一样的，只是输入的信息和控制密钥不同，第i轮加密处理过程如图2-3所示。 2021-7-1672第2章 密码学基础3. 算法加密具体过程算法加密具体过程 F 函函 数数 Li-1 （ 32 比 特 ） Ri-1 （ 32 比 特 ） 扩 展 置 换 S 盒 子 置 换 异 或 第 i 轮 加 密 密 钥Ki（ 48 比 特 ） Ri（ 32 比 特 ） Li（ 32 比 特 ） 异 或 图 2-3 第 i 轮 加 密 处 理 过 程 2021-7-1673第2章 密码学基础3. 算法加密具体过程算法加密具体过程F函数是DES算法的精髓，它是多个置换函数和替代函数的组合函数，该函数以密钥和上一

36、轮加密得到的部分结果作为输入，通过多次扩展、置换和替代达到真正“扰乱”明文信息的目的。F函数分为扩展、异或运算、S盒替代以及置换四个步骤。 2021-7-1674第2章 密码学基础3. 算法加密具体过程算法加密具体过程 扩展 F函数首先将32比特的数据Ri-1 预扩展为48比特，其方法是：将Ri-1 从左到右分成8块，每块4比特，然后将每块从4比特扩展到6比特。扩展的规则是：每一块向左扩展一位，同时向右扩展一位，也就是说，第n块向左扩展一位，与第n-1块未扩展前的最后一位相同，同时向右扩展一位，与第n+1块未扩展前的最后一位相同；2021-7-1675第2章 密码学基础3. 算法加密具体过程算

37、法加密具体过程例如由表2-8 所知的序列M1，得到加密时的L0和R0 分别是： L0 = 11011100 01011011 01101000 11100010R 0 =10010111 01010110 10111000 11100000首先将R0 分为8块，得到数据：1001 0111 0101 0110 1011 100 1110 0000，如图2-4所示， 2021-7-1676第2章 密码学基础3. 算法加密具体过程算法加密具体过程 0 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1

38、0 1 0 1 0 0 0 0 1 0 图 2-4 DES 加密函数 F 的预扩展示例 2021-7-1677第2章 密码学基础3. 算法加密具体过程算法加密具体过程异或运算：由图2-3所示，经过扩展后的48比特Ri-1 将与第i轮加密密钥Ki 进行异或运算，密钥Ki 也是48位，由原始密钥经过循环左移以及置换排列的方式产生，具体的生成过程后面将详细描述。 48位的Ki 同Ri-1 一样，也分成8块，每块6比特，然后与扩展后的Ri-1 对应的各块做异或运算后，同样生成8个6位比特块，其输出是S盒子的输入。 2021-7-1678第2章 密码学基础3. 算法加密具体过程算法加密具体过程假设密钥K

39、i的第1块6比特数据为：110111，图2-4所示的第一块扩展比特是010010，则两者异或的结果是100101 2021-7-1679第2章 密码学基础3. 算法加密具体过程算法加密具体过程 S盒替代 DES算法中的S盒子由8个子盒S1、S2 、S3 、S4 、S5 、S6 、S7 、S8 组成，每个盒子构成4行16阶的4 16 矩阵，表2-9列出了其中一个子盒S1的定义。 2021-7-1680第2章 密码学基础3. 算法加密具体过程算法加密具体过程 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001

40、0000 0111 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000 1111 1011 1000 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0010 0110 1101 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 表

41、2-9 S1 盒子定义 2021-7-1681第2章 密码学基础3. 算法加密具体过程算法加密具体过程S盒子的输入是上述所讲的由Ri-1与Ki 两者异或运算得到的结果，其中第j个子盒Sj的输入是第j块异或运算的结果，输出是根据Sj盒子定义得到的4比特数据。 2021-7-1682第2章 密码学基础3. 算法加密具体过程算法加密具体过程对于每个盒子Sj （j=1,2.8）其输入与输出之间的映射关系是：将Sj输入的第一位与最后一位两个二进制组合起来，得到某个十进制数m，m用来选择矩阵Sj的行；Sj输入的中间四比特数据组合，得到十进制数n，n用来选择矩阵Sj的列。已知行m与列n，查找已经定义好的矩阵

42、Sj 的m行n列对应的值，该值就是Sj的输出。 2021-7-1683第2章 密码学基础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 2021-7-1684第2章 密码学基础3. 算法加密具体过程算法加密具体过程 置换 F函数的最后一步是

43、对S盒子输出的32比特数据进行置换，目的是使得S盒的输出对下一轮多个Si子盒产生影响，以增强DES的安全性。F函数的输出结果与上一轮加密处理的左半部分数据Li-1异或，得到第i轮加密处理的右半部分32位数据Ri。然后Li与Ri又作为第i+1轮加密处理时的输入数据，这样，经过16轮迭代加密处理之后，得到L16 与R16。 2021-7-1685第2章 密码学基础3. 算法加密具体过程算法加密具体过程将R16 与L16 左右换位，即将R16的32比特数据移到左边，L16的32比特数据移到右边。换位之后，再次经过逆初始矩阵IP-1置换，最终得到的结果就是密文。2021-7-1686第2章 密码学基础

44、4. DESDES算法解密过程算法解密过程 DES的解密算法与加密算法除了在每一轮循环迭代时所使用的控制密钥不同之外，其他的完全一样。并且，输出的64比特密文经过解密处理过程，所得结果就是所需的明文。 2021-7-1687第2章 密码学基础5. 密钥的生成密钥的生成 DES算法定义的分组长度是64比特，其主密钥长度与明文分组长度一样，也是64比特，不过在实际使用中，只用到56比特，还有8比特用作奇偶校验位。 每轮迭代所使用的密钥Ki （i=1,2 .16）都是从主密钥生成的，Ki 的长度是48比特。密钥的具体生成方法如图2-5所示：2021-7-1688第2章 密码学基础5. 密钥的生成密钥

45、的生成 去除奇偶校验位 置换排列 PC-1 C0（28 比特） D0（28 比特） 循环左移位 循环左移位 主密钥 K （64 比特） 实际密钥（56 比特） C1（28 比特） D1（28 比特） 置换排列 PC-2 K1 循环左移位 循环左移位 置换排列 PC-2 K16 图 2-5 DES 算法密钥 Ki的生成 2021-7-1689第2章 密码学基础6. DESDES算法安全性分析算法安全性分析 关于DES算法的安全性，在最初公布的时候，曾受到很多人的置疑。攻击者会很容易的破译DES算法密钥更多的人担心保密设计的S盒子的安全性很多用户担心S盒子存在隐藏的弱点2021-7-1690第2章

46、 密码学基础6. DESDES算法安全性分析算法安全性分析 DES算法为什么需要16次循环迭代？而不是15次或者更多的20次呢？不能一味的为了防止攻击者破译密码，不断增加循环迭代次数，否则算法的效率与性能将会受到影响较少的迭代次数又会导致攻击者容易分析密码算法，从而破译出密钥。2021-7-1691第2章 密码学基础6. DESDES算法安全性分析算法安全性分析 DES算法使用56位密钥是否安全?上世纪70年代,DES被广泛使用在安全级别要求不高的场合。但是20世纪90年代以来，从计算上讲，56位密钥的DES不能再认为是安全的。 2021-7-1692第2章 密码学基础2.2.3 高级加密标准

47、高级加密标准AES AES 1. AES的起源2. AES的设计原则2021-7-1693第2章 密码学基础1. AES AES的起源的起源1997年9月，NIST征集AES方案，以替代DES。1999年8月，以下5个方案成为最终候选方案：MARS, RC6, Rijndael, Serpent, Twofish。2000年10月，由比利时的Joan Daemen和Vincent Rijmen提出的算法最终胜出。（ Rijndael 读成Rain Doll。）2000年12月，美国国家标准局NIST正式确认新一代数据加密标准是高级加密标准AES(Advanced Encryption Stan

48、dard) 。2021-7-1694第2章 密码学基础2. AES AES的设计原则的设计原则能抵抗所有已知的攻击；在各种平台上易于实现，速度快；设计简单，是一种分组密码体制，加密和解密使用相同的密钥，属于对称密码体制；与DES分组密码体制不同的是，AES中明文或密文分组长度以及密钥长度不是固定的，而是可变的，它们可以是128比特、192比特、256比特。2021-7-1695第2章 密码学基础2.3 公钥密码体制公钥密码体制 2.3.1 公钥密码体制的基本原理2.3.2 RSA算法2.3.3 有限域上椭圆曲线密码算法ECC 2.3.4 公钥密码体制的应用 2021-7-1696第2章 密码学

49、基础古老的密码学问题 很久以前，分别有两个国家的公主和王子，公主要通过一很久以前，分别有两个国家的公主和王子，公主要通过一位信使送给王子一样不愿被别人看见的信物，所以公主用加锁位信使送给王子一样不愿被别人看见的信物，所以公主用加锁的箱子放信物。这位信使只愿意跑一趟，而且在这段路程中，的箱子放信物。这位信使只愿意跑一趟，而且在这段路程中，只要一有机会（钥匙）就会偷看信物。只要一有机会（钥匙）就会偷看信物。 问题：公主如何才能把信物安全的送到王子的手中？问题：公主如何才能把信物安全的送到王子的手中？2021-7-1697第2章 密码学基础解决办法：解决办法：让两个国家的每一个人都具有两副锁和钥匙，

50、每幅各有让两个国家的每一个人都具有两副锁和钥匙，每幅各有一把锁和一把钥匙。一把锁和一把钥匙。每一把锁和它不配套的钥匙放在一起，这样每个人就有每一把锁和它不配套的钥匙放在一起，这样每个人就有两副不配套的钥匙和锁了。两副不配套的钥匙和锁了。将其中的一幅秘密留在家里（秘密锁钥）；另一幅拿到将其中的一幅秘密留在家里（秘密锁钥）；另一幅拿到锁厂，复制锁厂，复制60亿副，让国家人人都能从市场上买到它（亿副，让国家人人都能从市场上买到它（公开锁钥）。公开锁钥）。2021-7-1698第2章 密码学基础首先假设：首先假设：公主的秘密锁钥（公主的秘密锁钥（Ab）,公开锁钥（公开锁钥（Ba） 王子的秘密锁钥（王子

51、的秘密锁钥（Cd）,公开锁钥（公开锁钥（Dc）公主：送的箱子上共锁着两把锁（公主：送的箱子上共锁着两把锁（DA）王子：（王子：（ Ba ）（A） （ Cd ）（D）2021-7-1699第2章 密码学基础2.3.1 公钥密码体制的基本原理公钥密码体制的基本原理1976年，狄菲和海尔曼提出了密码体制的新概年，狄菲和海尔曼提出了密码体制的新概念念公钥密码。公钥密码。使用两个密钥：公密钥、私密钥使用两个密钥：公密钥、私密钥加解密的非对称性，是对对称密码的重要补充加解密的非对称性，是对对称密码的重要补充利用数论与其他数学难题的方法利用数论与其他数学难题的方法2021-7-16100第2章 密码学基础2

52、.3.1 公钥密码体制的基本原理公钥密码体制的基本原理重要特点重要特点- 仅根据加密算法加密算法和加密密钥加密密钥来确定解密密钥在计算上不可行- 两个密钥中的任何一个都可用来加密，另一个用来解密。六个组成部分六个组成部分：- 明文、密文；公钥、私钥；- 加密、解密算法2021-7-16101第2章 密码学基础序号序号对称密码对称密码公钥密码公钥密码1 加密和解密使用相同的密钥 加密和解密使用不同密钥2 密钥必须保密存放 私钥保密存放，公钥公开存放3 通信前，收发双方必须实现密钥共享 通信前，收发双方无需实现密钥共享 4 应用于数据加解密、可以实现数据保密性、认证等安全服务 应用于数据加解密、数

53、字签名、密钥交换等方面，实现数据保密、认证、数据完整性、不可否认性等安全服务 2021-7-16102第2章 密码学基础2.3.1 公钥密码体制的基本原理公钥密码体制的基本原理1.公钥密码体制依赖的基础2.公钥密码系统的特征 3.公钥密码体制加解密过程 2021-7-16103第2章 密码学基础1. 公钥密码体制依赖的基础公钥密码体制依赖的基础经典的公钥密码算法RSA、椭圆曲线密码算法ECC等都是依赖某类数学问题的，它们共同的特点是基于某个单向陷门函数。2021-7-16104第2章 密码学基础单向陷门函数单向陷门函数 y=fy=fk k(x) (x) 是指同时满足下列条是指同时满足下列条件的

54、一类可逆函数件的一类可逆函数： 函数是一一映射关系，一个y对应唯一的一个x； 给定x与关键参数k,函数y=fk(x)很容易计算；2021-7-16105第2章 密码学基础1. 公钥密码体制依赖的基础公钥密码体制依赖的基础 给定y，存在某个关键参数k，在未知k时，逆函数x=f-1(y) 的计算相当复杂，实际上是不可行的；在已知k时，则逆函数x=f-1k(y)很容易计算； 给定y和参数k，无法从函数y=fk(x)推导出影响其逆函数f-1的关键参数k。2021-7-16106第2章 密码学基础2. 公钥密码系统的特征公钥密码系统的特征 根据密码系统的组成以及公钥密码体制自身的特点，一个公钥密码系统可

55、以表示为：加密算法E、解密算法D、公钥/私钥(PK/SK)对、明文M、密文C六个元素，且各元素必须要满足以下条件： 2021-7-16107第2章 密码学基础2. 公钥密码系统的特征公钥密码系统的特征 密钥要满足三点要求：公钥/私钥(PK/SK)对容易产生，且私钥除了生成密钥的用户自己知道之外，其他任何人都不可知；PK和SK中的任何一个都可以用于加密，相应的另一个用于解密；从公开密钥PK无法通过计算得到私有密钥SK 。 2021-7-16108第2章 密码学基础2. 公钥密码系统的特征公钥密码系统的特征 加密算法加密算法E E要满足两点要求：要满足两点要求：已知公钥PK，对任何明文M，由E计算

56、出密文C非常容易，即C = EPK(M) 易计算已知私钥SK，对任何信息M，由E计算数字签名也非常容易，即C = ESK(M) 易计算。2021-7-16109第2章 密码学基础2. 公钥密码系统的特征公钥密码系统的特征 解密算法解密算法D D要求：要求： 仅知道解密算法以及加密密钥，推导明文和解密 密钥都是计算不可行的。 2021-7-16110第2章 密码学基础3. 公钥密码体制加解密过程公钥密码体制加解密过程 假设网络上的两个用户Alice和Bob需要进行秘密通信，为了防止攻击者Eve窃听信息，Alice和Bob选择使用公钥密码体制加密传输的信息。Alice是信息的发送方；Bob是信息的

57、接收方。 Alice与Bob产生公钥/私钥对：PKA/SKA，PKB/SKB。2021-7-16111第2章 密码学基础3. 公钥密码体制加解密过程公钥密码体制加解密过程 Alice与Bob通过某种机制公布各自的公钥PKA与PKB，例如将公钥放到一个公共的服务器，供其他用户查询。2021-7-16112第2章 密码学基础3. 公钥密码体制加解密过程公钥密码体制加解密过程 Alice通过查询公共服务器获得Bob的公钥PKB。如果Alice欲给Bob发送报文M，他就用Bob的公钥PKB加密报文。已知待加密的明文M以及Bob的公钥PKB，Alice很容易通过加密算法E计算出密文，即 C = EPKB

58、(M)。2021-7-16113第2章 密码学基础3. 公钥密码体制加解密过程公钥密码体制加解密过程 接收方Bob收到Alice发送的信息之后，使用自己的私钥SKB解密报文。已知密文C私钥SKB，Bob很容易通过解密算法计算出明文M，即 M=DSKB(C)。2021-7-16114第2章 密码学基础如果反过来呢？Bob发送给Alice信息该如何加密信息呢？2021-7-16115第2章 密码学基础用公钥进行加密用公钥进行加密2 Alice产生一对密钥，用于加密和解密产生一对密钥，用于加密和解密3 Alice将一个密钥公开，另一个密钥私有将一个密钥公开，另一个密钥私有BobAlice1 Bob要

59、发送消息给要发送消息给Alice4 Bob用用Alice的公钥对消息加密，发送给的公钥对消息加密，发送给Alice。只有。只有Alice能解密能解密2021-7-16116第2章 密码学基础2.3.2 RSARSA算法算法 1.RSA算法依赖的数学问题2.RSA算法密钥产生过程3.RSA算法加解密过程 4.RSA算法安全性及性能分析 2021-7-16117第2章 密码学基础RSA算法算法由MIT的 Rivest, Shamir & Adleman 在 1977 提出最著名的且被广泛应用的公钥加密体制 明文、密文是0到n-1之间的整数，通常n的大小为1024位二进制或309位十进制数2

60、021-7-16118第2章 密码学基础2021-7-16119第2章 密码学基础1. RSARSA算法依赖的数学问题算法依赖的数学问题 模运算的性质：-正整数n是素数，集合Zn = 0，1，2.，(n-1) 表示小于n的所有非负整数集合，则对于集合Zn 中的每一个整数wZn，均存在一个z，满足公式w z = 1 mod n，我们称z是w的乘法逆元，且n是它们的模。 2021-7-16120第2章 密码学基础1. RSARSA算法依赖的数学问题算法依赖的数学问题 费马定理：-如果p是素数，a是不能整除p的正整数，则： ap-1 1 mod p例如：-P=7， a=2，-则27-1=26 =64，64m