第2章密码学基础

1、第第2章章 密码学基础密码学基础密码学基础知识密码学基础知识v密码技术在信息安全中的作用密码技术在信息安全中的作用信息安全的重要和核心部分之一是数据安全信息安全的重要和核心部分之一是数据安全数据安全的目标包括机密性、真实性、完整性、数据安全的目标包括机密性、真实性、完整性、不可否认性、可用性、可控性不可否认性、可用性、可控性实现数据安全目标的重要手段是密码技术实现数据安全目标的重要手段是密码技术密码技术具有几千年的历史密码技术具有几千年的历史v密码学（密码学（Cryptology）是密码技术的基础，）是密码技术的基础，包括：包括：密码编码学（密码编码学（Cryptography）密码分析学（密

2、码分析学（Cryptanalysis）密码学基础知识密码学基础知识v密码编码学：研究如何进行数据加密和解密密码编码学：研究如何进行数据加密和解密（机密性），以及防止和发现数据的伪造、（机密性），以及防止和发现数据的伪造、篡改（真实性、完整性、不可否认性）篡改（真实性、完整性、不可否认性）v密码分析学：分析发现密码算法的弱点、缺密码分析学：分析发现密码算法的弱点、缺陷，破解密码算法或者破译密码数据陷，破解密码算法或者破译密码数据数据加密、解密的基本过程数据加密、解密的基本过程明文明文明文明文密文密文密文密文解密解密加密加密破解破解密钥密钥kc密钥密钥kd明文明文: plaintext密文密文:

3、ciphertext加密加密: encrypt解密解密: decrypt密钥密钥: key密码算法的基本定义密码算法的基本定义设：设：M是可能明文的集合，称为明文空间是可能明文的集合，称为明文空间 C是可能密文的集合，称为密文空间是可能密文的集合，称为密文空间 K是一切可能密钥构成的集合，称为密钥空间是一切可能密钥构成的集合，称为密钥空间 E为加密算法，对密钥空间的任一密钥为加密算法，对密钥空间的任一密钥k都能进行加都能进行加密运算，即密运算，即Ek: MC D为解密算法，对密钥空间的任一密钥都能进行解为解密算法，对密钥空间的任一密钥都能进行解密运算，即密运算，即Dk: CM 则密码算法具有如

4、下性质：则密码算法具有如下性质：（1）Dk(Ek(x)=x，x属于属于M，k属于属于K（2）密码破译者获得密文）密码破译者获得密文c=Ek(x)后无法在有效的时后无法在有效的时间内破解出密钥间内破解出密钥k和和/或明文或明文x密码体制分类密码体制分类v古典密码古典密码(Classic Cryptography)v对称密钥密码对称密钥密码(Symmetric Key Cryptography)v公开密钥密码体系公开密钥密码体系(Public Key Cryptography)古典密码古典密码v代替表代换密码代替表代换密码v移位密码移位密码v乘数密码乘数密码v仿射密码仿射密码对照表代替密码对照表代

5、替密码abcdefghijklmXNYAHPOGZQWBTnopqrstuvwxyzSFLRCVMUEKJDIABCDEFGHIJKLMdlryvohEzxwptNOPQRSTUVWXYZbgfjqnmuskaci加密代替表加密代替表解密代替表解密代替表i am a teacherZ XT X MHXYGHC一些关于模余数的基本知识一些关于模余数的基本知识定义定义1. 设设n为大于为大于1的正整数，的正整数，a为任一整数，为任一整数，a可表可表示为示为a=kn +r，r 0，则记为：，则记为： a mod n = r，称，称r为为a的模的模n余数余数注意：负数的模注意：负数的模n余数是正整数！

6、余数是正整数！例，若例，若 na0，则，则a mod n = n+a定义定义2.设设n为大于为大于1的正整数，的正整数，a、b为任意整数，如果为任意整数，如果a mod n = b mod n，即，即a、b有相同模有相同模n余数，则余数，则称称a、b模模n同余同余表示为表示为 a b (mod n) a、b模模n同余当且仅当同余当且仅当n整除整除a-b一些关于模余数的基本知识一些关于模余数的基本知识注意以下差别：注意以下差别： a = b mod n a b (mod n) 前者表示：前者表示：b的模的模n余数是余数是a；后者表示：；后者表示： a和和b模模n同余，即有相同的模同余，即有相同的

7、模n余数余数在本课中用前一种表示，即在本课中用前一种表示，即mod作为一种算子作为一种算子一些关于模余数的基本知识一些关于模余数的基本知识v定义定义 3. n为大于为大于1的正整数，的正整数，a、b为整数，为整数，则则a+b mod n，a*b mod n，ab mod n分别分别称为整数的模称为整数的模n加法、乘法和乘方加法、乘法和乘方(幂幂)一些关于模余数的基本知识一些关于模余数的基本知识设设n为大于为大于1的正整数，的正整数，a、b为任意整数，则为任意整数，则1) a + b mod n = (a mod n) + (b mod n) mod n2) a b mod n = (a mod

8、 n) + (b mod n) mod n = (a mod n) (b mod n) mod n3) ab mod n = (a mod n)*(b mod n) mod n4) a mod n = a + kn mod n = a kn mod n 5) a + (b mod n) mod n = a+b mod n 一些关于模余数的基本知识一些关于模余数的基本知识6) a*(b mod n) mod n = a*b mod n7) (a mod n)p mod n = ap mod n注意：注意： mod的运算优先级最低的运算优先级最低 结论：结论： 对于同一个模对于同一个模n，只要保存

9、最外层的，只要保存最外层的mod算子算子，给加、减、乘、乘方运算中的数据加上或去，给加、减、乘、乘方运算中的数据加上或去掉掉mod 算子，不影响结果算子，不影响结果 请尝试证明一下！请尝试证明一下！模余数举例模余数举例例例1. 求求9 mod 6 9 = 6+3，故，故 9 mod 6 =3例例2. 求求7 mod 6 7 = -12+5，故，故 7 mod 6=5而而 2X6 + (7) mod 6 = 5故，故， 7 mod 6 = 2X6 + (7) mod 6 = 5(即即 a mod n = a + kn mod n)模余数举例模余数举例(续续)例例3. 求求9 7 mod 6 9

10、7=2，故，故 9 7 mod 6 =2而而 (9 mod 6) + (7 mod 6) mod 6 = 3+5 mod 6 = 8 mod 6 = 2 (9 mod 6) (7 mod 6) mod 6 = 3 1 mod 6 =2故故 9-7 mod 6 = (9 mod 6) + (7 mod 6) mod 6 = (9 mod 6) (7 mod 6) mod 6(即即a b mod n = (a mod n) + (b mod n) mod n = (a mod n) (b mod n) mod n )模余数举例模余数举例(续续)例例4. 求求 2+(9 mod 6) mod 6 =

11、 2+3 mod 6 =5而而 2+9 mod 6 = 11 mod 6 =5故故 2+(9 mod 6) mod 6 = 2+9 mod 6(即即a + (b mod n) mod n = a+b mod n)例例5. 求求 2*(9 mod 6) mod 6 = 2*3 mod 6 =0 而而 2*9 mod 6 = 18 mod 6 = 0故，故，2*(9 mod 6) mod 6 = 2*9 mod 6(即即a*(b mod n) mod n = a*b mod n)一些关于模余数的基本知识一些关于模余数的基本知识定义定义 4. 设设n为大于为大于1的正整数，的正整数，a、b为任意整数

12、，为任意整数，若若a+b mod n= 0，则，则b称为称为a的模的模n加法逆，记加法逆，记为为-a注意：注意：a的模的模n加法逆不止一个，它们相差加法逆不止一个，它们相差kn定义定义 5. 设设n为大于为大于1的正整数，的正整数，a、b为任意整数，为任意整数，若若 ab mod n= 1，则，则b称为称为a的模的模n乘法逆，记乘法逆，记为为a-1注意：注意：a的模的模n乘法逆不止一个，它们相差乘法逆不止一个，它们相差kn模余数举例模余数举例(续续)例例6. 求求5的模的模6加法和乘法逆加法和乘法逆 5+1 mod 6 = 0故，故，1是是5的模的模6加法逆，加法逆， 5的模的模6加法逆是加法

13、逆是6k+1 5*5 mod 6 = 25 mod 6 =1故，故，5是是5的模的模6乘法逆，乘法逆， 5的模的模6乘法逆是乘法逆是6k+5例例7. 求求3的模的模6加法和乘法逆加法和乘法逆 3+3 mod 6 =0故，故，3是是3的模的模6加法逆，加法逆， 3的模的模6加法逆是加法逆是6k+30,1,.,5都不是都不是3的模的模6乘法逆，故乘法逆，故3无模无模6乘法逆乘法逆一些关于模余数的基本知识一些关于模余数的基本知识定义定义 6. 设设p是大于是大于1的正整数，若的正整数，若p只能分解为只能分解为1和和自己的乘积，则自己的乘积，则p称为素数称为素数定义定义 7. 设设a和和b是大于是大于

14、1的正整数，的正整数， 且且a和和b的最大的最大公因子是公因子是1，即，即 gcd(a,b)=1，则称为，则称为a和和b互素互素定理定理 1. 设设a和和n是大于是大于1的正整数，且的正整数，且a和和n互素，互素，则则a存在模存在模n乘法逆乘法逆a-1推理推理 1. 设设n是素数，则任何非是素数，则任何非kn整数整数a存在模存在模n乘乘法逆法逆a-1移位密码移位密码v加密函数：加密函数：c = Ek(m) = (m+k) mod n，其中，其中0mn，m是待加密的明文数据是待加密的明文数据(当作数当作数)， 1kn， k是密钥是密钥v解密函数：解密函数：m= Dk(c) = (ck) mod

15、nk如何理解？如何理解？v有效性有效性 Dk(c) = (ck) mod n = (m+k) mod n) - k mod n = m + k k mod n = m mod n = m c-k0怎办？怎办？移位密码移位密码v凯撒密码凯撒密码每个字母用后移每个字母用后移3位的字母代换位的字母代换用用0,1,25对应对应26个字母个字母M=C=0,1,25, n=26, k=3明文信息明文信息 M=meet me after the toga party密文信息密文信息 C=phhw ph diwho wkh wrjd sduwb 乘数密码乘数密码v加密函数：加密函数：c = Ek(m) = k

16、*m mod n，其中，其中0mn，gcd(k,n)=1，1knv解密函数：解密函数：m= Dk(c) = k-1 *c mod n，其，其k-1是是k的模的模n乘法逆乘法逆有效性有效性 Dk(c) = k-1 *c mod n = k-1*(k*m mod n) mod n = (k-1 * k*m) mod n = (k-1 * k) mod n) * (m mod n) mod n = 1*m mod n = m仿射密码仿射密码v加密函数：加密函数：c = Ek(m) = k*m +h mod n 其中，其中，0mn, gcd(k,n)=1, 0kn，0 hn (k=1, h=0除外除外

17、)v解密函数：解密函数：m = Dk(c) = k-1 *(ch) mod n，其，其中，中，k-1是是k的模的模n乘法逆乘法逆仿射密码仿射密码v对英文字母的密码运算如下：对英文字母的密码运算如下：M=C=0,1,25, hM模模n=26k1,3,5,7,9,11,15,17,19,21,23,25， k-1是是k的的模模26乘法逆乘法逆 k=1, h=0组合除外，故有组合除外，故有26X12-1=311可能可能仿射密码仿射密码例例 设设k=5, h=3, 5的模的模26乘法逆是乘法逆是21，故，故， Ek(m) = 5m+3 mod 26 Dk(c) = 21*(c3) mod 26 =21

18、c11 mod 26yesEk=254185+333=192315=txptxpDk=19231521 -111111=25418=yesmod 26移位、乘数、仿射密码适用性问题移位、乘数、仿射密码适用性问题v适用于有限的明文空间适用于有限的明文空间MvM中的每个元素对应一个非负整数中的每个元素对应一个非负整数v模数模数n大于大于M中的元素对应的最大整数，且中的元素对应的最大整数，且n大于等大于等于于2v密文空间是密文空间是0,1,2,n-1移位、乘数、仿射密码安全性移位、乘数、仿射密码安全性v不但不但k、h要保密，要保密， n也要保密，否则，可以也要保密，否则，可以采用简单的选择明文攻击，

19、比如采用简单的选择明文攻击，比如移位密码移位密码 k = c m mod n 乘数密码乘数密码k= c*m-1 mod n, 选择选择gcd(m,n)=1仿射密码仿射密码k= (c1 c2)*(m1 m2)-1 mod n, 选择选择gcd(m1 m2,n)=1vn必须非常大，否则，用蛮力攻击就可破解必须非常大，否则，用蛮力攻击就可破解对古典代换密码的攻击对古典代换密码的攻击v针对古典代换密码针对古典代换密码 (包括替换表、移位、乘数包括替换表、移位、乘数、仿射密码、仿射密码)可采用统计分析攻击可采用统计分析攻击v蛮力攻击蛮力攻击v对移位、乘数、仿射密码，选择明文攻击对移位、乘数、仿射密码，选

20、择明文攻击英文字母相对使用频度分布英文字母相对使用频度分布英文字母相对使用频度分布英文字母相对使用频度分布多表代换密码多表代换密码v用多个代替表依次对明文消息的字母进行代用多个代替表依次对明文消息的字母进行代换的加密方法换的加密方法v隐藏字母出现的频度隐藏字母出现的频度对称密钥密码对称密钥密码vSymmetric Key Cryptographyv加密和解密使用同一个密钥加密和解密使用同一个密钥v对称密钥数字加密分为流加密和分组加密对称密钥数字加密分为流加密和分组加密非非公共公共网络网络Key安全信道安全信道This is a secret letter明文明文密文密文加密加密密文密文解密解密

21、This is a secret letter明文明文AliceBob流加密流加密(stream cipher)v用一个伪随机密钥流用一个伪随机密钥流(pseudorandom keystream)与数据流与数据流 (按位或按字节按位或按字节)进行异或进行异或(XOR)操作操作发送方，用一个伪随机密钥流对明文数据进行异或发送方，用一个伪随机密钥流对明文数据进行异或(XOR)操作操作(加密加密)接收方，用同一个伪随机密钥流对密文数据进行异接收方，用同一个伪随机密钥流对密文数据进行异或或(XOR)操作操作(解密解密)v根据伪随机密钥流生成方式的不同分为根据伪随机密钥流生成方式的不同分为同步流加密同

22、步流加密(synchronous stream cipher)自同步流加密自同步流加密(self-synchronous stream cipher)或异步流加密或异步流加密(asynchronous stream cipher)同步流加密同步流加密v密钥流的生成与密文流独立密钥流的生成与密文流独立(无依赖关系无依赖关系)i+1 = f(i,k)zi = g(i,k)ciii+1+fgmizikci = zi mi加密加密移位移位ii+1+fgcimizikmi = zi ci解密解密移位移位mi = zi (zi mi)i是一位或多位的内部状态是一位或多位的内部状态zi 是伪随机密钥流是伪随

23、机密钥流同步流加密的特点同步流加密的特点v发送和接收方要求严格密钥流和数据同步，如果发送和接收方要求严格密钥流和数据同步，如果密码数据流出现丢失或插入，则后续的整个解密密码数据流出现丢失或插入，则后续的整个解密解密失败（密钥流与密文流失步）解密失败（密钥流与密文流失步）v无错误传递，如果传输过程中一位密文出现错误无错误传递，如果传输过程中一位密文出现错误（非丢失或插入），不会影响后续密文的解密（非丢失或插入），不会影响后续密文的解密v易于遭受攻击：（易于遭受攻击：（1）攻击者通过删除、插入或）攻击者通过删除、插入或重播密文位导致无法正确解密；（重播密文位导致无法正确解密；（2）攻击者可）攻击者

24、可能可通过改变密文的某些位导致出现他预期的结能可通过改变密文的某些位导致出现他预期的结果，比如，修改某些密文位导致订单数量的改变果，比如，修改某些密文位导致订单数量的改变自同步流加密自同步流加密v密钥流的生成与密文流的密钥流的生成与密文流的1位或多位相关位或多位相关i = (ci-t, , ci-2, ci-1)zi = g(i,k)i =有个初始值有个初始值(初始化向量初始化向量)i+gmicizikci = zi mi加密加密ci-t ci-2 ci-1mikmi = zi ci解密解密+gciziici-t ci-2 ci-1i是状态向量是状态向量zi 是伪随机密钥流是伪随机密钥流自同步

25、流加密的特点自同步流加密的特点v接收方能自同步：如果密文的某些位被删除或插入，接收方能自同步：如果密文的某些位被删除或插入，接收方能够自同步，因为接收方的解密仅依赖于前面接收方能够自同步，因为接收方的解密仅依赖于前面固定数量的密文位固定数量的密文位v有限的错误传递：如果密文的某位出现修改、删除或有限的错误传递：如果密文的某位出现修改、删除或插入，最多导致后续有限位的数据解密错误，因为解插入，最多导致后续有限位的数据解密错误，因为解密只依赖于前面的固定数量的密文位密只依赖于前面的固定数量的密文位v对密文修改攻击防护能力增加：对一个密文位的修改对密文修改攻击防护能力增加：对一个密文位的修改，导致多

26、个密文位解密不正确，因此，更易于发现对，导致多个密文位解密不正确，因此，更易于发现对密文的修改密文的修改v发散对明文的统计分析：因为之前的明文影响了对后发散对明文的统计分析：因为之前的明文影响了对后面明文加密的结果，使得攻击者难于通过统计分析找面明文加密的结果，使得攻击者难于通过统计分析找到明文和密文的关系到明文和密文的关系分组加密分组加密L bitL bitL bitL bitBLOCK1BLOCK2BLOCK3BLOCKn明文分组明文分组加密加密E加密加密E加密加密E加密加密EM bitM bitM bitM bit密文分组密文分组解密解密D解密解密D解密解密D解密解密DL bitL bi

27、tL bitL bit明文分组明文分组BLOCK1BLOCK2BLOCK3BLOCKnBLOCK1BLOCK2BLOCK3BLOCKnKeyKeyKeyKey分组加密算法分组加密算法vDES(Data Encryption Standard)v3DES(Triple DES)vRC5vIDEA(International Data Encryption Algorithm)vAES(Advanced Encryption Standard)DES算法算法v曾经使用非常广泛的著名分组密码算法曾经使用非常广泛的著名分组密码算法(已不安全已不安全)v其产生过程是：其产生过程是：1973美国国家标准局

28、美国国家标准局(National Bureau of Standard, NBS)征集国家密码标准方案征集国家密码标准方案1974年年NBS第二次征集时，第二次征集时，IBM公司提出他们的方案公司提出他们的方案LUCIFER1975年年NBS公开了公开了IBM算法并安排两个小组进行评价算法并安排两个小组进行评价1976年年NBS在征询了美国国家安全局在征询了美国国家安全局(National Security Agency，NSA)的意见，并由的意见，并由NSA对对IBM算算法中的法中的S-Box(替换表，替换表，substitution table)进行微小进行微小变化、降低了密钥长度后发表，

29、命名为变化、降低了密钥长度后发表，命名为DES(曾引起密曾引起密码界的广泛怀疑码界的广泛怀疑)DES算法算法v64位的分组加密算法位的分组加密算法v密钥密钥64位，但实际密钥长度是位，但实际密钥长度是56位，其他位，其他8位是奇偶校验位位是奇偶校验位v通过移位通过移位(shift)、排列、排列(permutation)、代换、代换(substitution)、异或、异或(Exclusive OR)操作实操作实现密码运算现密码运算v加密、解密过程是对称的加密、解密过程是对称的DES算法的安全性算法的安全性vDES最大的安全问题是它的密钥长度才最大的安全问题是它的密钥长度才56位位v1990年年S

30、. Biham和和A. Shamir用差分攻击方法，用差分攻击方法，采用选择明文攻击，最终破解了密钥采用选择明文攻击，最终破解了密钥v1994年的世界密码大会上，年的世界密码大会上，M. Matsui采用线性分采用线性分析方法，利用析方法，利用243个已知明文成功地破译了个已知明文成功地破译了DES算算法法v1997年年RSA公司发起了首届公司发起了首届“向向DES挑战挑战”的竞的竞赛，罗克赛，罗克.维瑟用维瑟用96天破解了用天破解了用DES加密的一段信加密的一段信息息v1999年年12月，月，RSA公司发起第三届公司发起第三届DES挑战赛，挑战赛，2000年年1月电子前沿基金会研制的月电子前

31、沿基金会研制的DES解密机以解密机以22.5小时成功破解了小时成功破解了DES加密加密3DESv随着计算技术的发展，随着计算技术的发展，DES越来越不能满足安全要求，越来越不能满足安全要求，特别是其密钥长度特别是其密钥长度56位太短，使得可以通过蛮力攻击位太短，使得可以通过蛮力攻击(brutal force attack)破解密码破解密码v通过应用三重通过应用三重DES算法、使用超过算法、使用超过56位的密钥提高位的密钥提高DES的安全的安全v3DES的四种模式的四种模式DES-EEE3，使用三个不同的，使用三个不同的DES密钥顺序进行三次加密变换，解密密钥顺序进行三次加密变换，解密是逆过程，

32、密钥长度是逆过程，密钥长度168位位DES-EDE3，加密时使用三个不同的，加密时使用三个不同的DES密钥依次进行加密密钥依次进行加密-解密解密-加加密变换，解密是逆过程，密钥长度密变换，解密是逆过程，密钥长度168位位DES-EEE2，进行三次加密变换，其中第一次、第三次变换的密钥相，进行三次加密变换，其中第一次、第三次变换的密钥相同，解密是逆过程，密钥长度同，解密是逆过程，密钥长度112位位DES-EDE2，加密时依次进行加密，加密时依次进行加密-解密解密-加密变换，其中第一次、第加密变换，其中第一次、第三次变换的密钥相同，解密是逆过程，密钥长度三次变换的密钥相同，解密是逆过程，密钥长度1

33、12位位RC5v由由RSA公司的首席科学家公司的首席科学家Ron Rivest于于1994年设计、年设计、1995年正式公开的一种加密算法年正式公开的一种加密算法v一种分组长度一种分组长度w、密钥长度、密钥长度b和迭代轮数和迭代轮数r都都可变的分组迭代式密码，简记可变的分组迭代式密码，简记RC5-w/r/bv采用了三种运算：异或、加和循环移位采用了三种运算：异或、加和循环移位RC5的特点的特点v形式简单易于软件或硬件实现，运算速度快形式简单易于软件或硬件实现，运算速度快v能适用于不同字长的系统，不同字长派生出相能适用于不同字长的系统，不同字长派生出相异的算法异的算法v加密的轮数可变，这个参数用

34、来调整加密速度加密的轮数可变，这个参数用来调整加密速度和安全性的程度和安全性的程度v密钥长度可变，加密强度可调节密钥长度可变，加密强度可调节v对存储要求不高，可在对存储要求不高，可在Smart Card内存有限的内存有限的系统中使用系统中使用v具有高保密性具有高保密性v对数据实行位循环位移，增强抗抵赖能力对数据实行位循环位移，增强抗抵赖能力RC5的安全性的安全性v到目前为止尚未发现有效的攻击手段到目前为止尚未发现有效的攻击手段v分析表明，分析表明，r为为12的的RC5可抵抗差分分析和线可抵抗差分分析和线性分析攻击性分析攻击IDEAv1990年由瑞士联邦技术学院的来学嘉年由瑞士联邦技术学院的来学

35、嘉(X. J. Lai)和和Massey提出提出v64位分组密码算法，密钥长度位分组密码算法，密钥长度128位位v使用了异或、模使用了异或、模216加法、模加法、模216+1乘法乘法v1992年命名为年命名为IDEA(International Data Encryption Algorithm，国际数据加密算法，国际数据加密算法)IDEA的安全性的安全性v到目前为止尚未发现算法的明显弱点到目前为止尚未发现算法的明显弱点v减少密码运算的轮次，可导致算法被攻破减少密码运算的轮次，可导致算法被攻破v存在一些弱密钥需要避免存在一些弱密钥需要避免AESv为了替代为了替代DES和和3DES，1997年年

36、4月美国国家标月美国国家标准和技术研究院准和技术研究院(National Institute of Standards and Technology，NIST)发布征集发布征集AES (Advanced Encryption Standard)的活动的活动v1997年年9月月NIST公布公布AES要求的通告，要求要求的通告，要求AES比比3DES快，至少同快，至少同3DES一样安全，分组一样安全，分组长度长度128位，密钥长度位，密钥长度128/192/256位位v经过反复的评选、论证最后两个比利时密码学经过反复的评选、论证最后两个比利时密码学家家Joan Daemen和和Vincent Ri

37、jmen提出的提出的Rijndael密码算法胜出，密码算法胜出，AES规范发布规范发布AES的安全性的安全性v到目前为止，到目前为止，AES是安全的，尚未有有效的是安全的，尚未有有效的攻击攻击分组加密的工作模式分组加密的工作模式v电子编码本电子编码本(Electronic Code Book, ECB)v密码分组链接密码分组链接(Cipher Block Chaining, CBC)v密码反馈密码反馈(Cipher Feedback, CFB)v输出反馈输出反馈(Output Feedback, OFB)电子编码本电子编码本(ECB)明文分组明文分组1加密加密密文分组密文分组1密文分组密文分组

38、1解密解密明文分组明文分组1明文分组明文分组2加密加密密文分组密文分组2密文分组密文分组2解密解密明文分组明文分组2明文分组明文分组n加密加密密文分组密文分组n密文分组密文分组n解密解密明文分组明文分组n时间时间ECB的特点的特点v简单和有效简单和有效v可实现并行加密可实现并行加密v不能隐藏明文的模式信息，即相同明文对应不能隐藏明文的模式信息，即相同明文对应相同密文，同样的信息多次出现造成泄露相同密文，同样的信息多次出现造成泄露v错误传递小：加密、传输或解密时，一块密错误传递小：加密、传输或解密时，一块密文出错、修改、损坏仅对对应的明文造成影文出错、修改、损坏仅对对应的明文造成影响响v对明文的

39、主动攻击是可能的：信息块可被替对明文的主动攻击是可能的：信息块可被替换、重排、删除、重放换、重排、删除、重放密码分组链接密码分组链接(CBC)明文分组明文分组1加密加密密文分组密文分组1密文分组密文分组1解密解密明文分组明文分组1IVIV明文分组明文分组2加密加密密文分组密文分组2密文分组密文分组2解密解密明文分组明文分组2明文分组明文分组n加密加密密文分组密文分组n密文分组密文分组n解密解密明文分组明文分组n时间时间CBC的特点的特点v没有已知的并行实现算法没有已知的并行实现算法v能隐藏明文的模式信息，相同明文对应不同密文能隐藏明文的模式信息，相同明文对应不同密文v错误传递较大：错误传递较大

40、：加密时一块密文出错、损坏导致后续所有密文出加密时一块密文出错、损坏导致后续所有密文出错错传输时一块密文损坏、删除、插入导致最多两块传输时一块密文损坏、删除、插入导致最多两块明文块无法解密还原明文块无法解密还原v对明文的主动攻击是不易的：一块密文被替换、对明文的主动攻击是不易的：一块密文被替换、重排、删除、重放，解密会出现错误重排、删除、重放，解密会出现错误v安全性好于安全性好于ECB密码反馈密码反馈(CFB)明文分组明文分组n密文分组密文分组iIV明文分组明文分组2明文分组明文分组1移位寄存器移位寄存器加密加密选择选择S位位 丢弃丢弃S明文分组明文分组1IV明文分组明文分组2明文分组明文分组

41、n移位寄存器移位寄存器加密加密选择选择S位位 丢弃丢弃LS S加密加密解密解密SSLS S L LCFB的特点的特点v适用于分组密码和流密码适用于分组密码和流密码v没有已知的并行实现算法没有已知的并行实现算法v能够隐藏明文模式，相同明文对应不同密文能够隐藏明文模式，相同明文对应不同密文v需要共同的移位寄存器初始值需要共同的移位寄存器初始值v误差传递较大：误差传递较大：加密时一块密文出错、损坏使得所有后续密文出加密时一块密文出错、损坏使得所有后续密文出错错传递时一块密文修改、损坏、插入、删除可能使传递时一块密文修改、损坏、插入、删除可能使得得1+(L+S-1)/S块明文块无法解密还原块明文块无法

42、解密还原输出反馈输出反馈(OFB)明文分组明文分组n密文分组密文分组iIV明文分组明文分组2明文分组明文分组1移位寄存器移位寄存器加密加密选择选择S位位 丢弃丢弃LS SS位位明文分组明文分组1IV明文分组明文分组2明文分组明文分组n移位寄存器移位寄存器加密加密选择选择S位位 丢弃丢弃LS S加密加密解密解密SS L LOFB的特点的特点v适用于分组密码和流密码适用于分组密码和流密码v没有已知的并行实现算法没有已知的并行实现算法v能够隐藏明文模式，相同明文对应不同密文能够隐藏明文模式，相同明文对应不同密文v需要共同的移位寄存器初始值需要共同的移位寄存器初始值v误差传递小误差传递小加密或传输时一

43、个密文块损坏只影响对应的明文加密或传输时一个密文块损坏只影响对应的明文块块v安全性较安全性较CFB差差(伪随机密钥序列的周期短伪随机密钥序列的周期短)分组加密的填充分组加密的填充(padding)v数据长度不一定就是分组的倍数，在数据尾部填充适当数据长度不一定就是分组的倍数，在数据尾部填充适当的数据使得最后一块数据的长度等于分组长度的数据使得最后一块数据的长度等于分组长度要求：要求：(1)满足分组长度要求；满足分组长度要求；(2)解密者知道哪些是原始解密者知道哪些是原始数据哪些是填充数据数据哪些是填充数据vANSI X.923尾部填充字节尾部填充字节0，最后一个字节表示填充个数，最后一个字节表

44、示填充个数 | 3A C3 4B 78 25 8B CD 7D | 3A C3 4B 78 00 00 00 04vPKCS7填充的字节内容就是填充的字节数填充的字节内容就是填充的字节数 | 3A C3 4B 78 25 8B CD 7D | 3A C3 4B 78 04 04 04 04vISO/IEC 7816-4填充的第一个字节内容是填充的第一个字节内容是80，后面填充，后面填充00 | 3A C3 4B 78 25 8B CD 7D | 3A C3 4B 78 80 00 00 00对称密钥加密的特点对称密钥加密的特点v算法实现简单算法实现简单v速度快速度快v密钥短密钥短v密钥分发难密

45、钥分发难作业作业v问题问题1：将移位、乘数、仿射密码用于英文：将移位、乘数、仿射密码用于英文26个字母的密码变换时，个字母的密码变换时， n不是不是26行吗？行吗？ 26个字母不按个字母不按025连续编号行吗？为什么？连续编号行吗？为什么？v问题问题2：如果被加密的数据的长度正好是分组：如果被加密的数据的长度正好是分组长度的整数倍，是否还需要填充？如果不需长度的整数倍，是否还需要填充？如果不需要，说明理由；如果需要，说明如何填充。要，说明理由；如果需要，说明如何填充。假设分组长度是假设分组长度是8字节，采用的填充方案是填字节，采用的填充方案是填充字节的内容是填充字节数。充字节的内容是填充字节数

46、。公开密钥密码体系公开密钥密码体系vPublic Key Cryptographyv也称非对称密钥密码体系，也称非对称密钥密码体系，Asymmetric Key Cryptography公开密钥密码算法思想的来源公开密钥密码算法思想的来源v1976年年Whitefield Diffie和和Martin Hellman在其在其密码学新方向密码学新方向中提出了公开密钥密中提出了公开密钥密码算法的思想码算法的思想v首次提出了单向陷门首次提出了单向陷门(trapdoor)函数的概念函数的概念，并提出了，并提出了Diffie-Hellman密钥交换算法密钥交换算法(加加上使用密钥进行加密部分上使用密钥进

47、行加密部分，它实质上也是一它实质上也是一个公开密钥加密算法！个公开密钥加密算法！)单向陷门函数单向陷门函数v一个单向陷门函数一个单向陷门函数f(x)满足如下三个条件满足如下三个条件给定给定x，计算，计算y=f(x)是容易的是容易的给定给定y，计算，计算x使得使得y=f(x)是困难的是困难的存在存在，已知，已知时对给定的任何时对给定的任何y，若相应的，若相应的x存在存在，则计算，则计算x使得使得y=f(x)是容易的是容易的Diffie-Hellman算法数学基础算法数学基础v素数的原根素数的原根(Primitive Root)素数素数p的一个原根是一个正整数的一个原根是一个正整数g，g mod

48、p、g2 mod p，gp-1 mod p不同，且包含了不同，且包含了1到到p-1的所有整数；的所有整数；若若g是素数是素数p的一个原根，则（的一个原根，则（1）g，g mod p、g2 mod p，gp-1 mod p生成了生成了1,2,p-1；（2）对应任意整数）对应任意整数1 b p-1，存在一个唯一，存在一个唯一的的1 i p-1，使得，使得b=gi mod pv定理定理. 对于任意素数对于任意素数p存在原根存在原根(一个或多个一个或多个)Diffie-Hellman算法数学基础算法数学基础v离散对数离散对数若若n为大于为大于1的正整数，的正整数，m为整数，若为整数，若b = mi m

49、od n，则，则b称为称为m的模的模n下的下的 i次幂，次幂，i称为称为b的以的以m为为基数的模基数的模n下的幂指数，即下的幂指数，即b的离散对数的离散对数v离散对数难题离散对数难题对于函数对于函数y=mx mod n，已知，已知m、n、x计算计算y是容是容易的，反之，已知易的，反之，已知m、n、y计算计算x是困难的是困难的Diffie-Hellman密钥交换算法描述密钥交换算法描述Alice和和Bob共享一个公开的大素数共享一个公开的大素数p和大整数和大整数g，1gp，g是是p的原根的原根Alice随机选取大的随机选取大的随机整数随机整数1xp，并计算并计算W=gx mod pBob随机选取

50、大的随机选取大的随机整数随机整数1yp，并计算并计算Z=gy mod pAlice将将W发送给发送给BobBob将将Z发送给发送给AliceAlice计算计算K1= Zx mod p = gxy mod pBob计算计算K2= Wy mod p = gxy mod pK1= K2=KAlice和和Bob用密钥用密钥K进行数据加密、解密进行数据加密、解密This is a secret letterThis is a secret letterBobAlice(y, p, g)是是Bob的私的私钥，钥，(Z, p, g)是是Bob的公钥的公钥(x, p, g)是是Alice的私的私钥，钥，(W,

51、 p, g)是是Alice的公钥的公钥BobAlice易于遭受中间人攻击易于遭受中间人攻击BobAlice我是我是Bob我是我是AliceEveRSA公开密钥算法公开密钥算法v目前应用最广泛、也是最早能同时用于加密目前应用最广泛、也是最早能同时用于加密和签名的公开密钥算法和签名的公开密钥算法v由美国的由美国的Ron Rivest、Adi Shamir、 Leonard Adleman三人于三人于1978年提出年提出v数学基础：数论中的欧拉数学基础：数论中的欧拉(Euler)定理或费马定理或费马小定理小定理(Fermats little theorem)和大整数的和大整数的因子分解问题因子分解问

52、题RSA公开密钥算法的数学基础公开密钥算法的数学基础1）Fermats little theorem若若p为素数，则对于任意整数为素数，则对于任意整数a，有，有 ap mod p = a mod p若进一步地，如若进一步地，如p不能除不能除a(即即a kp)，则有，则有 ap-1 mod p = 12）欧拉定理）欧拉定理如果如果a和和n是互素的正整数，则是互素的正整数，则a(n) mod n = 1 (n)是是Eulers totient function 若若n是素数，则是素数，则(n)=n-1 若若n=pq，p、q是互异的素数，则是互异的素数，则(n)=(p-1)(q-1)RSA公开密钥算

53、法的数学基础公开密钥算法的数学基础3）若）若p、q是两个互异的素数，是两个互异的素数，n=pq，0mn，则对于任意正整数则对于任意正整数k，根据欧拉定理或，根据欧拉定理或Fermats little theorem可导出如下结果：可导出如下结果： mk(n)+1 mod n = m, 其中其中, (n)=(p-1)(q-1)4）已知两个互异的大素数）已知两个互异的大素数p、q，计算，计算n=pq是容是容易的；反之，若已知易的；反之，若已知n是两个素数是两个素数p、q的乘积，的乘积，分解出分解出p、q却是很困难的，目前无有效办法却是很困难的，目前无有效办法RSA公开密钥算法描述公开密钥算法描述1

54、）选择两个互异的大素数）选择两个互异的大素数p和和q，计算，计算n=pq，计，计算算(n)=(p-1)(q-1)2）选择整数）选择整数 1e(n)使得使得gcd(e, (n)=1 (互素互素)3）计算得到）计算得到e的模的模(n)乘法逆元乘法逆元d，即，即 e*d mod (n) =1，其中，其中， 1d (n)4）公开密钥是）公开密钥是P=(e,n)，私钥是，私钥是S=(d,n,p,q)以上（以上（1）到（）到（4）由私钥拥有者完成）由私钥拥有者完成5）对于明文）对于明文m加密运算：加密运算：c=me mod n (使用公钥使用公钥)解密运算：解密运算：m=cd mod n (使用私钥使用私

55、钥)RSA公开密钥算法描述公开密钥算法描述算法有效性：算法有效性： d是是e的模的模(n)乘法逆元，乘法逆元，e*d mod (n)=1，故，故存在一个正整数存在一个正整数k使得使得e*d=k(n)+1cd mod n = (me mod n)d mod n = med mod n = mk(n)+1 mod n = m6）将使用）将使用e、d的顺序换一下，结果同样正确（用的顺序换一下，结果同样正确（用于数字签名）于数字签名）加密运算：加密运算：c=md mod n (使用私钥使用私钥d)解密运算：解密运算：m=ce mod n (使用公钥使用公钥e)RSA公开密钥算法的应用公开密钥算法的应用

56、BobAlice公钥公钥私钥私钥This is a secret letterThis is a secret letter公钥发布给公钥发布给BobAlice公钥公钥用用Alice公钥加密公钥加密用私钥解密用私钥解密RSA公开密钥算法的中间人攻击公开密钥算法的中间人攻击BobAlice这是这是Bob公钥公钥这是这是Alice公钥公钥Eve需采用其他方案如需采用其他方案如PKI解决公钥的发布问题解决公钥的发布问题Eve的密钥对的密钥对RSA公开密钥密码算法的安全性公开密钥密码算法的安全性v算法的安全性算法的安全性1） 加密函数加密函数c= me mod n是单向门限函数：已知是单向门限函数：已

57、知m求求c是容易的，是容易的， 反之已知反之已知c求求m是困难的；若已知是困难的；若已知p、q(陷门信息陷门信息)，则由，则由c可计算出可计算出m2）安全性依赖大数）安全性依赖大数n=pq的因子分解难题，及解密函的因子分解难题，及解密函数数m= cd mod n的离散对数难题的离散对数难题v算法的安全性被认为等同于大数分解的难度，但算法的安全性被认为等同于大数分解的难度，但缺乏理论证明缺乏理论证明(也许除了分解之外，还有其他破也许除了分解之外，还有其他破解方案？解方案？)v要保证安全，要保证安全，p和和q必须是足够大的素数，目前必须是足够大的素数，目前n=pq是是1024位的二进制数已不很安全

58、位的二进制数已不很安全RSA公开密钥算法的特性公开密钥算法的特性v首个既可以用于加密，又可以用于签名的公开首个既可以用于加密，又可以用于签名的公开密钥密码算法密钥密码算法v密钥长度密钥长度(模模n)要足够长要足够长vRSA的加密、解密采用了大整数的指数运算，的加密、解密采用了大整数的指数运算，故速度比采用移位、排列、代换、异或操作的故速度比采用移位、排列、代换、异或操作的对称密钥密码算法要慢很多对称密钥密码算法要慢很多v为了提高加密速度通常将整数为了提高加密速度通常将整数e取为固定的小取为固定的小整数，如整数，如EDI国际标准中规定国际标准中规定e=216+1，ISO/IEC9796中规定允许

59、中规定允许e=3，但，但d很大，故加很大，故加密和验签速度比解密和签名速度快很多密和验签速度比解密和签名速度快很多Rabin公开密钥密码算法公开密钥密码算法vMichael O. Rabin提出提出v基于大数分解难题基于大数分解难题v随机选两个大的素数随机选两个大的素数p和和q，计算，计算n=pq，n是是公钥，公钥，p和和q是私钥是私钥v加密：加密：c = m2 mod n, 0 mn是明文是明文v解密：求解密：求c的的0,1,n-1内的模内的模n平方根平方根v经证明其安全性等同于大数分解难题经证明其安全性等同于大数分解难题ElGamal公开密钥密码算法公开密钥密码算法v由由Taher ElG

60、amal提出提出v基于基于Diffie-Hellman密钥交换算法和循环群密钥交换算法和循环群上的离散对数难题上的离散对数难题v包括加密算法和签名算法包括加密算法和签名算法ElGamal加密算法加密算法vElGamal加密算法，基于循环群加密算法，基于循环群(Cyclic group)，可，可用于任何循环群，包括椭圆曲线上的点构成的循环群用于任何循环群，包括椭圆曲线上的点构成的循环群(ECC密码算法密码算法)，故其方案被广泛用于其他公开密钥，故其方案被广泛用于其他公开密钥加密算法加密算法v群一个定义了乘法群一个定义了乘法(或加法或加法)，包含，包含”1”(或或”0”)元素的元素的集合，集合中的