【1】第二章 密码学基础1

1、目录v2.1 密码学的基本知识密码学的基本知识v2.2 对称密码体制对称密码体制v2.3 密码学的数学基础密码学的数学基础v2.4 公钥密码体制公钥密码体制密码学的基本概念是经过伪装后的明文是经过伪装后的明文c。全体可能。全体可能出现的密文集合称为出现的密文集合称为密文空间密文空间C密文密文未经过加密的原始信息称为明文未经过加密的原始信息称为明文m，明文的全体称为，明文的全体称为明文空间明文空间 M明文明文由明文空间、密文空间、密码方由明文空间、密文空间、密码方案和密钥空间组成案和密钥空间组成密码密码系统系统密码学的基本概念密码学的基本概念密码学的基本概念(2)加密和解密算法的操作在称为密加密

2、和解密算法的操作在称为密钥（钥（k）的元素控制下进行。密）的元素控制下进行。密钥的全体称为钥的全体称为密钥空间（密钥空间（K）密钥密钥确切地描述了加密变换和解密变确切地描述了加密变换和解密变换的具体规则换的具体规则密码密码方案方案加密算法加密算法对明文进行加密时对明文进行加密时所使用的规则的描所使用的规则的描述述(m)解密算法解密算法对密文进行还原时对密文进行还原时所使用的规则所使用的规则D(c)保密通信系统的基本模型加密算法解密算法密码分析者加密密钥Ke解密密钥Kd窃听干扰明文明文m明文明文m密文密文c有了密钥的概念后，加密的过程：有了密钥的概念后，加密的过程：c=EKe(m)，解密的过程，

3、解密的过程:m=DKd(c)，其中，其中mM，cC被动攻击和主动攻击v密码分析者（密码分析者（Cryptanalyst）又称攻击者，可）又称攻击者，可采用搭线窃听等方式直接获得未经加密的明文采用搭线窃听等方式直接获得未经加密的明文或加密后的密文，并分析得知明文。这种对密或加密后的密文，并分析得知明文。这种对密码系统的攻击手段称为码系统的攻击手段称为被动攻击被动攻击（Passive attack），），特点：不破坏原始信息特点：不破坏原始信息 v攻击者还可以采用删除、更改、增添、重放、攻击者还可以采用删除、更改、增添、重放、伪造等手段主动向系统注入假信息，这种对密伪造等手段主动向系统注入假信息，

4、这种对密码系统的攻击手段称为码系统的攻击手段称为主动攻击主动攻击（Active attack） 被动攻击和主动攻击形式形式威胁威胁特点特点被动攻击被动攻击窃听窃听流量分析流量分析机密性机密性不破坏原始不破坏原始信息信息难于发现难于发现主动攻击主动攻击篡改、伪造篡改、伪造重放、否认重放、否认完整性完整性易于探测但易于探测但却难于防范却难于防范 拒绝服务拒绝服务可用性可用性密码体制的分类 v1. 按照密码的发展历史分类按照密码的发展历史分类密码可分为密码可分为古典密码古典密码和和近现代密码近现代密码 v2.按照需要保密的内容分类按照需要保密的内容分类 根据密码体制的密码算法是否需要保密，可分根据密

5、码体制的密码算法是否需要保密，可分为为受限制的算法受限制的算法和和基于密钥的算法基于密钥的算法v1883年年Kerchoffs第一次明确提出了编码的原则，第一次明确提出了编码的原则，即加密算法应建立在即加密算法应建立在算法的公开算法的公开不影响明文和不影响明文和密钥的安全的基础上密钥的安全的基础上 密码体制的分类v3. 根据加密和解密所使用的密钥是否相同根据加密和解密所使用的密钥是否相同对称密码体制对称密码体制 公钥密码体制公钥密码体制：也称为非对称密码体制：也称为非对称密码体制对称密码体制对称密码体制 对称密码体制对称密码体制Symmetric Key Cryptosystem加密密钥加密密

6、钥=解密密钥解密密钥密钥必须保密密钥必须保密公钥密码体制公钥密码体制公钥密码体制公钥密码体制Public Key Cryptosystem加密密钥加密密钥解密密钥解密密钥 加密密钥为公钥（加密密钥为公钥（Public Key），公钥无需保密），公钥无需保密 解密密钥为私钥（解密密钥为私钥（Private Key）密码体制的分类v4. 根据对明文的处理方式根据对明文的处理方式 分组密码分组密码算法和算法和流密码流密码算法算法 v5. 根据是否能进行可逆的加密变换根据是否能进行可逆的加密变换分为单向函数密码体制和双向变换密码体分为单向函数密码体制和双向变换密码体制制 密码学的发展历程密码学的发展历

7、程密码学的发展历程古典密码古典密码体制体制近现代密近现代密码体制码体制Shannon的保密的保密通信的信通信的信息理论息理论 密码学的密码学的新方向新方向Diffie和和Hellman密码学密码学的新方向的新方向 密码分析与密码系统的安全性密码系统的安全性取决于密码系统的安全性取决于(1) 所使用的密码算法的保密强度所使用的密码算法的保密强度(2) 密码算法以外不安全的因素密码算法以外不安全的因素因此必须同时完善技术与管理上的要因此必须同时完善技术与管理上的要求，才能保证整个密码系统的安全求，才能保证整个密码系统的安全密码分析研究如何分析和破解密码密码分析的方法密码分析密码分析的方法的方法数学

8、分析攻击（数学分析攻击（Mathe-matical analysis attack）统计分析攻击（统计分析攻击（Statistical analysis attack）穷举分析攻击（穷举分析攻击（Exhaustive attack）密码分析攻击的类型v假设密码分析者已经知道加密算法，根据密码假设密码分析者已经知道加密算法，根据密码分析者对明文、密文等资源的掌握程度：分析者对明文、密文等资源的掌握程度：v1）唯密文攻击（）唯密文攻击（Ciphtext-only attack）v2）已知明文攻击（）已知明文攻击（Plaintext-known attack） v3）选择明文攻击（）选择明文攻击（C

9、hosen-plaintext attack）v4）选择密文攻击（）选择密文攻击（ChosenCiphtext attack） 现代加密算法的设计目标是要能抵抗现代加密算法的设计目标是要能抵抗住选择明文攻击住选择明文攻击 密码系统安全性的层次v无条件安全（无条件安全（Unconditionally Secure）v计算上安全（计算上安全（Computationally Secure）v可证明安全（可证明安全（Provable Secure） 一般认为，密码系统只要能达到计算上安一般认为，密码系统只要能达到计算上安全就是安全的全就是安全的 目录v2.1 密码学的基本知识密码学的基本知识v2.2

10、对称密码体制对称密码体制v2.3 密码学的数学基础密码学的数学基础v2.4 公钥密码体制公钥密码体制对称密码体制v对称密码体制，即对称密码体制，即加密密钥与解密密钥相同加密密钥与解密密钥相同的的密码体制，这种体制只要知道加（解）密算法，密码体制，这种体制只要知道加（解）密算法，就可以反推解（加）密算法就可以反推解（加）密算法 v在在1976年公钥密码算法提出以前的所有加密算年公钥密码算法提出以前的所有加密算法都是对称密码体制法都是对称密码体制 v对称密码体制可分为分组密码和流密码对称密码体制可分为分组密码和流密码 v本节将介绍的古典密码、分组密码和流密码本节将介绍的古典密码、分组密码和流密码古

11、典密码置换（换位）是对明文中的元素进行置换（换位）是对明文中的元素进行换位排列，可以证明置换是替代的一换位排列，可以证明置换是替代的一种特殊形式种特殊形式置换置换替代是将明文中的每个元素映射为另替代是将明文中的每个元素映射为另一个元素，明文元素被其他元素所替一个元素，明文元素被其他元素所替代而形成密文代而形成密文替代替代采用的加密思想：采用的加密思想：替代替代和和置换置换对于明文“dog”，使用替代技术加密：结果可能是“eph”，使用置换技术加密：结果可能是“ogd” 讨论下面密码算法的加密思想vScytale 密码密码v棋盘密码棋盘密码123451abcde2fghijk3lmnop4qrs

12、tu5vwxyz弗纳姆密码弗纳姆密码例：例： Aice欲将明文欲将明文m=OK，借由弗纳姆密码加密，借由弗纳姆密码加密成密文成密文c，传递给，传递给Bob。假设密钥为。假设密钥为k=DA。ASCIImOK(79,75)10011111001011ASCIIkDA(68,65)10001001000001c00010110001010c00010110001010k10001001000001DAm10011111001011OK10011,00110 ci=(mi+ki) mod 2几种典型的古典密码v移位密码（又称凯撒密码）移位密码（又称凯撒密码）v一般单表替代密码一般单表替代密码v仿射密码

13、仿射密码v密钥短语密码密钥短语密码v维吉尼亚（维吉尼亚（Vigenere）密码）密码v希尔（希尔（Hill）密码）密码v置换密码置换密码移位密码 v加密变换：加密变换：Ek(m)=m+k(mod 26) mM, kKv解密变换：解密变换：Dk(c)=c-k(mod 26) cC, kKv很容易利用穷举法将密文解密，最多尝试很容易利用穷举法将密文解密，最多尝试25次，次，就能找到密文对应的明文信息就能找到密文对应的明文信息 明文明文：youth密文：密文：brxwk将明文每个字母前移三位将明文每个字母前移三位 移位密码加密示例移位密码加密示例密钥产生）Alice与Bob协定编码方式为明文字母后移

14、4位，即加密密钥及解密密钥同为K=4。Alice将明文将明文“gaul is divided into three part”转为数字代码：转为数字代码：（6，0，20，11，8，18，3，8，21，8，3，4，3，8，13，19，14，19，7，17，4，4，15，0，17，19）。）。使用使用加密函数加密函数E（m） m+k=m+4（mod 26）计算得：（计算得：（10，4，24，15，12，22，7，12，25，12，7，8，7，12，17，23，17，23，11，21，8，8，19，4，21，23）即即密文密文“K，E，Y，P，M，Z，M，H，I，H，M，R，X，R，X，L，V，I，

15、I，T，E，V，X”。 2.一般单表替代密码v明文消息中的每个字母不是同时移动相同的位明文消息中的每个字母不是同时移动相同的位数，而是根据一张替代表使用随机替换数，而是根据一张替代表使用随机替换 一张一般单表替代密码的映射一张一般单表替代密码的映射表表明文 abcdefghijklm密文 qwertyuiopasd明文 nopqrstuvwxyz密文 fghjklzxcvbnmc=Ek(m)=(m)m=Dk(c)=-1(c)3. 仿射密码v加密变换为：加密变换为：vc=Ek(m)= (k1m+k2) mod 26v相应的解密变换为：相应的解密变换为：vm=Dk(c)=k1-1(c-k2) mo

16、d 26v注意：注意：k1必须和必须和26互素互素，如果不互素，例如取，如果不互素，例如取k1=2，则明文，则明文m=mi和和m=mi+13两个字符都将被两个字符都将被映射成同一个密文字符映射成同一个密文字符仿射密码示例Alice与Bob事先协定一把密钥K=(3,8)其中gcd(3,26)=1E(.)maffine(0,5,5,8,13,4)(8,23,23,6,21,20)IXXGVUc E(m)3m8 (mod26)1D(c)3 (c8)9(c8) (mod26)D(.)cIXXGVU(8,23,23,6,21,20)(0,5,5,8,13,4)affinem 密钥短语密码v密钥短语密码选

17、用一个英文短语或单词作密钥短语密码选用一个英文短语或单词作为密钥，如密钥为为密钥，如密钥为university时，先去掉时，先去掉重复字母重复字母i，成为，成为universty明文字母a 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密钥字母u n i v e r s t y a b c d f g h j k l m o p q w x z总结：单表替代密码的特点v以上几种密码都是单表替代密码，特点如下：以上几种密码都是单表替代密码，特点如下：这个特点使其密文中单字母出现的频率分布这个特点使其密文中单字母出现的频率分布与明文中的相同，因此

18、任何单表替代密码都与明文中的相同，因此任何单表替代密码都经不起统计分析。经不起统计分析。明文和密文是明文和密文是一对一的映射关系一对一的映射关系。Ef (x0,x1,x2,)=(f(x0),f(x1),f(x2),) 对单表加密算法的统计分析字母百分比字母百分比a8.2n6.8b1.5o7.5c2.8p1.9d4.2q0.1e12.7r6.0f2.2s6.3g2.0t9.0h6.1u2.8i7.0v1.0j0.1w2.4k0.8x2.0l4.0y0.1m2.4z0.1另外最常出现的双字母组合为：另外最常出现的双字母组合为： th(3.15%)，he(2.51%)，an(1.72)，in(1.6

19、9%)，er(1.54%)，re(1.48%)，es(1.45%)，on(1.45%)，ea(1.31%)，ti(1.28)，at(1.24%)，st(a.21%)，en(1.20%)，nd(1.18%)等。等。最常出现的三字母组合最常出现的三字母组合（Trigram）为：）为：the，ing，and，her，ere ，ent，tha，。多表替代密码v多表替代密码使用从明文字母到密文字母的多多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布个映射来隐藏单字母出现的频率分布 v同一个明文字母将对应不同的密文字母同一个明文字母将对应不同的密文字母 Ef (x0,x1,x2,)

20、=(f0(x0),f1(x1),f2(x2),) 维吉尼亚（Vigenere）密码v维吉尼亚密码：一种典型的维吉尼亚密码：一种典型的多表替代密码多表替代密码，该，该密码体制有一个参数密码体制有一个参数n，表示采用，表示采用n位长度的字位长度的字符串（例如一个英文单词）作为密钥。符串（例如一个英文单词）作为密钥。 v设密钥设密钥k=k1k2kn，明文，明文M=m1m2mn，则加密，则加密变换为：变换为：vEk(m1,m2,mn)=(m1+k1mod 26, m2+k2mod 26 ,mn+knmod 26 ) 维吉尼亚密码举例v例例2.2 设明文为设明文为“killthem”密钥为密钥为“gun

21、”，试，试用维吉尼亚密码对明文进行加密。用维吉尼亚密码对明文进行加密。v加密密钥：加密密钥：k=gun=(6,20,13)明文对应的数字为明文对应的数字为 1081111197412密钥对应的数字密钥对应的数字6201362013620相加取余变换后：相加取余变换后： 16224171320106对应的密文是：对应的密文是：hcyrnvwg因 密文为：密文为：hcyrnvwg破解维吉尼亚密码v密文为：密文为：hcyrnvwgcxgtu h n c u c v x y w g r g t关键是如何确定密钥长度关键是如何确定密钥长度n希尔密码v希尔密码：利用矩阵变换来对信息实现加密。希尔密码：利用

22、矩阵变换来对信息实现加密。v数学定义：设数学定义：设m是一个正整数，令是一个正整数，令M=E=(Z26)m，密钥密钥Kmm=定义在定义在Z26上的上的mm矩阵矩阵，其中，其中K的行列式值必须和的行列式值必须和26互素互素，否则不存在，否则不存在K的逆矩的逆矩阵阵K-1。v对任意的密钥对任意的密钥Kmm，定义加密，定义加密/解密变换为解密变换为Ek(x)= Kmmx mod 26Dk(y)= K-1mmy mod 26希尔（希尔（HillHill）密码举例）密码举例首先决定所用矩阵的大小，譬如是2211E34其中E的行列式值detE必须与26互素，否则不存在E的反矩阵。m=Hillhl711Mi

23、l81111711EM3 481115 2253 7715 22(mod 26)12515 22pwC125bzc=pbwz如何求矩阵的逆矩阵vA*为为A的伴随矩阵。的伴随矩阵。*|11AAA代数余子式代数余子式Hill密码解密过程密码解密过程计算加密矩阵的逆矩阵，再进行模运算（计算加密矩阵的逆矩阵，再进行模运算（mod 26），），得解密矩阵得解密矩阵41D(mod 26)314115 22EM3112559534441711(mod 26)811hlil Hill密码的特点：vHill密码完全隐藏了单字母的频率密码完全隐藏了单字母的频率v能比较好地抵抗频率法的分析，对抗仅有能比较好地抵抗频

24、率法的分析，对抗仅有密文的攻击强度较高密文的攻击强度较高v易受选择明文攻击易受选择明文攻击威胁替代密码的因素威胁替代密码的因素v频率分析频率分析v考虑最可能出现的字母及单词考虑最可能出现的字母及单词v重复结构分析（针对多表替代密码）重复结构分析（针对多表替代密码）va a a a a a a a a avg u n g u n g u n g置换密码v置换（置换（Permutation）密码通过改变明文消息中密码通过改变明文消息中各字符出现的相对位置，但明文消息字符本身各字符出现的相对位置，但明文消息字符本身的取值不变。置换密码的一个显著特点是它的的取值不变。置换密码的一个显著特点是它的明文集

25、合和密文集合完全相同明文集合和密文集合完全相同 列置换密码列置换密码 螺旋置换密码螺旋置换密码ScytalePermutation of characters400 BCSPARTA【例例】明文为明文为cryptography is an applied science。密钥是密钥是creny密钥中字母在字母表中的出现次序密钥中字母在字母表中的出现次序14235密文为：密文为： cohnii yripdn paspsc rgyaee tpalce。密钥 14235cryptographyisanappliedscience列置换密码实例列置换密码实例螺旋置换密码v明文：明文：This is a

26、n examplev密文：密文：xxxeasilnthpexamxxxeAsilnthpexam置换密码v置换密码：置换密码：Ek(dog)=ogd可用如下希尔密码实现可用如下希尔密码实现 dgogodxKxEmmk001100010这证明了置换密码可转换为替代密码这证明了置换密码可转换为替代密码古典密码分类汇总图 替代密码替代密码单表替代密码单表替代密码多表替代密码多表替代密码移位密码仿射密码密钥短语密码一般单表替代密码维吉尼亚密码希尔密码置换密码置换密码2.2.2 分组密码v分组密码体制是目前商业领域中比较重要而流分组密码体制是目前商业领域中比较重要而流行的一种加密体制，它广泛地应用于数据

27、的保行的一种加密体制，它广泛地应用于数据的保密传输、加密存储等应用场合。密传输、加密存储等应用场合。 v加密时，先对明文分组，每组长度都相同，然加密时，先对明文分组，每组长度都相同，然后对分组加密得到等长的密文，分组密码的特后对分组加密得到等长的密文，分组密码的特点是加密密钥与解密密钥相同。点是加密密钥与解密密钥相同。 v如果明文不是分组长的倍数，则要填充如果明文不是分组长的倍数，则要填充分组密码算法的要求将将大的明文分组再分成几个小段大的明文分组再分成几个小段，分别完，分别完成各个小段的加密置换，最后进行并行操作成各个小段的加密置换，最后进行并行操作强化密码算法的措施强化密码算法的措施采用采

28、用乘积密码乘积密码技术。乘积密码就是以某种技术。乘积密码就是以某种方式连续执行两个或多个密码变换方式连续执行两个或多个密码变换分组长度分组长度m足够大足够大 密钥空间足够大密钥空间足够大密码变换必须足够复杂密码变换必须足够复杂Feistel网络示意图网络示意图111,iiiiiiLRRLF RKvDES的历史的历史v1971 IBM，由由Horst Feistel 领导的密码研领导的密码研究项目组研究出究项目组研究出LUCIFER算法。并应用于算法。并应用于商业领域。商业领域。v1973美国标准局征求标准，美国标准局征求标准，IBM提交结果，提交结果，v在在1977年，被选为数据加密标准。年，

29、被选为数据加密标准。v1994年，美国决定年，美国决定1998年年12月以后不再使月以后不再使用用DES算法算法 数据加密标准（数据加密标准（DES)DES)数据加密标准DES vDES是一种分组密码算法，它将明文从算法的是一种分组密码算法，它将明文从算法的一端输入，将密文从另一端输出。一端输入，将密文从另一端输出。v由于采用的是对称密钥，因此加密和解密使用由于采用的是对称密钥，因此加密和解密使用相同的算法和密钥相同的算法和密钥v并且加密和解密算法是公开的，系统的安全性并且加密和解密算法是公开的，系统的安全性完全依赖于密钥的保密完全依赖于密钥的保密 DES分组的原理vDES对数据进行加密时，首

30、先将数据切分成对数据进行加密时，首先将数据切分成64位的明文分组位的明文分组v它使用的密钥为它使用的密钥为64位，但有效密钥长度为位，但有效密钥长度为56位位（另有（另有8位用于奇偶校验）。输出的密钥分组也位用于奇偶校验）。输出的密钥分组也是是64位位v解密时的过程和加密时的类似，但密钥的顺序解密时的过程和加密时的类似，但密钥的顺序正好相反正好相反 DES的加密过程v（1）明文初始置换）明文初始置换 v（2）密钥初始置换）密钥初始置换 v（3）生成）生成16个个48位的子密钥位的子密钥 v（4）明文扩展置换）明文扩展置换 v（5）S盒替代盒替代 v（6）P盒置换盒置换 v（7）末置换）末置换

31、v（8）DES的解密的解密 vDES加密过程加密过程64位明文IP初始置换L0R0fK1L1R1fK2L15R15fK16左右交换R16L16逆初始置换IP164位密文LiRi1，RiLi1 f(Ri1，Ki)明文初始置换初始置换初始置换M=m1m2,m62m63,m64M=m58m50,m23m15,m7IP(M)由于由于M(64位位) =0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 对对M运用运用IP，故有，故有IP(64位位) = 1100 1100 0000 0000 1100 1100 1111 1111 11

32、11 0000 1010 1010将明文分成左右两半vIP(64位位) = L0(32位位) + R0(32位位)v故故vL0 (32位位) = 1100 1100 0000 0000 1100 1100 1111 1111 R0 (32位位) = 1111 0000 1010 1010 1111 0000 1010 1010 密钥初始置换 k1 （56 位） (48 位) ki （56 位） （48 位） 64 位密钥置换选择 1 C0（28 位） D0（28 位） 循环左移循环左移 C1（28 位） D1（28 位） 循环左移循环左移 Ci（28 位） Di（28 位）置换选择 2置换选择

33、 2密钥表的计算逻辑循环左移：1 1 9 12 1 10 23 2 11 24 2 12 25 2 13 26 2 14 27 2 15 28 2 16 116轮轮子密钥的生成子密钥的生成第一步：生成16个子钥(48位)v从而得到C1D1 C16D16：v C1 = 1110000110011001010101011111D1 = 1010101011001100111100011110 v C2 = 1100001100110010101010111111D2 = 0101010110011001111000111101 v C3 = 0000110011001010101011111111

34、D3 = 0101011001100111100011110101 v C4 = 0011001100101010101111111100D4 = 0101100110011110001111010101 v v C15 = 1111100001100110010101010111D15 = 1010101010110011001111000111 v C16 = 1111000011001100101010101111D16 = 0101010101100110011110001111 明文扩展置换Li-1（32位位）Ri-1（32位位）Li（32位位）48位位扩展置换扩展置换E48位位子密

35、钥子密钥Ki（48位位）32位位S盒替代盒替代P盒置换盒置换Ri（32位位）Li=Ri-1对Ri-1进行扩展置换与密钥Ki进行异或运算进行S盒替代8个个S 盒的表盒的表 S1盒14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 70 15 7 4 14 2 13 1 10 6 12 11 9 5 3 84 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13S2盒15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 103 13 4 7 15 2 8 14 12 0

36、1 10 6 9 11 50 14 7 11 10 4 13 1 5 8 12 6 9 3 2 1513 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9S3盒10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 813 7 0 9 3 4 6 10 2 8 5 14 12 11 15 113 6 4 9 8 15 3 0 11 1 2 12 5 10 14 71 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12S4盒7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 1513 8 11 5 6 15 0 3 4 7

37、 2 12 1 10 14 910 6 9 0 12 11 7 13 15 1 3 14 5 2 8 43 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14S5盒2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 914 11 2 12 4 7 13 1 5 0 15 10 3 9 8 64 2 1 11 10 13 7 8 15 9 12 5 6 3 0 1411 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3S6盒12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 1110 15 4 2 7 12 9 5 6

38、 1 13 14 0 11 3 89 14 15 5 2 8 12 3 7 0 4 10 1 13 11 64 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13S7盒4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 113 0 11 7 4 9 1 10 14 3 5 12 2 15 8 61 4 11 13 12 3 7 14 10 15 6 8 0 5 9 26 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12S8盒13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 71 15 13 8 10 3 7 4

39、 12 5 6 11 0 14 9 27 11 4 1 9 12 14 2 0 6 10 13 15 3 5 82 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11P盒置换vLi = Ri-1 i=1,2,16vRi = Li-1 f ( Ri-1 , Ki )16 7 20 21 29 12 28 171 15 23 26 5 18 31 102 8 24 14 32 27 3 919 13 30 6 22 11 4 25对R16L16作末置换40 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62

40、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 25DES加密的特点v综合运用了许多次置换和替代技术综合运用了许多次置换和替代技术,从而达到了从而达到了混淆混淆和和扩散扩散的特点的特点 v扩散扩散：将明文的统计特性散布到密文中。目的：将明文的统计特性散布到密文中。目的是使明文的每一位影响密文中多位的值是使明文的每一位影响密文中多位的值v混淆混淆：应使得密钥和明文以及密文之间的依赖：应使得密钥和明文以及密文之间的依赖关系相当复杂

41、，以至于这种依赖性对密码分析关系相当复杂，以至于这种依赖性对密码分析者来说是无法利用的。者来说是无法利用的。v采用了乘积密码技术，将采用了乘积密码技术，将R0加密后的所得结果加密后的所得结果R1再作为再作为L2的输入进行加密的输入进行加密 DES算法的变形v利用两个密钥的三重利用两个密钥的三重DESv若若K1=K2，将可兼容单，将可兼容单DES算法算法K1K2K1原始明文密文1密文2最终密文加密加密解密其他分组密码其他分组密码 vAES高级加密标准高级加密标准（Advanced Encryption Standard）明文分组的长度为明文分组的长度为128比特，而密钥长度可以为比特，而密钥长度

42、可以为128、192、256比特比特vIDEA国际数据加密标准国际数据加密标准（International Data Encryption Algorithm）是最强大的数据）是最强大的数据加密标准之一加密标准之一 流密码 v流密码采用密钥流生成器，从种子密钥生成一流密码采用密钥流生成器，从种子密钥生成一系列密钥流来加密信息，每个明文字母被密钥系列密钥流来加密信息，每个明文字母被密钥流中不同的密钥字母加密流中不同的密钥字母加密 安全信道安全信道种子密钥种子密钥z密钥流产生器密钥流产生器KGEki(mi)Dki(mi)密钥流产生器密钥流产生器KG种子密钥种子密钥z密文流密文流ci明文流明文流mi

43、明文流明文流mi密钥密钥ki密钥密钥ki流密码的类型v流密码的思想：模拟一次一密流密码的思想：模拟一次一密v同步流密码同步流密码 ：密钥流和明文流相互独立；：密钥流和明文流相互独立； (如密钥流是固定的，明文每次是变化的如密钥流是固定的，明文每次是变化的)v异步流密码异步流密码： 密钥流和明文流不相互独立，密密钥流和明文流不相互独立，密钥流的产生有密文或者明文的参与，会发生错钥流的产生有密文或者明文的参与，会发生错误传播现象误传播现象同步流密码v设维吉尼亚密码的密钥为设维吉尼亚密码的密钥为cipher，则密钥长度，则密钥长度d=6，将该密钥作为流密码的种子密钥，将该密钥作为流密码的种子密钥，v

44、密钥流产生器产生密钥流的规则为：第一次用密钥流产生器产生密钥流的规则为：第一次用该密钥加密明文，然后将该密钥每位循环右移该密钥加密明文，然后将该密钥每位循环右移一位。例如一位。例如v设种子密钥设种子密钥 z=cipher（2, 8, 15, 7, 4, 17），则），则在种子密钥控制下产生的密钥流在种子密钥控制下产生的密钥流Ki=（2,8,15,7,4,17,8,15,7,4,17,2,15,7,4,17,2,8,7,4,17,2,8,15）异步流密码 v明文明文： t h i s i s a s a m p l ev密钥：密钥： c i p h e rv密钥流：密钥流：c i p h e r

45、 t h i s i s av密钥与明文有关，若明文在传输中发生错误，密钥与明文有关，若明文在传输中发生错误，则会导致密钥也发生错误，即错误传播现象则会导致密钥也发生错误，即错误传播现象目录v2.1 密码学的基本知识密码学的基本知识v2.2 对称密码体制对称密码体制v2.3 密码学的数学基础密码学的数学基础v2.4 公钥密码体制公钥密码体制数论的基本概念 整除1. 整除整除v 设设a, b是两个整数，其中是两个整数，其中b0，如果存在另一整数，如果存在另一整数m使得等式使得等式a=mb成立，则称成立，则称b整除整除a，记为，记为b | a，并称并称b是是a的除数（或因子），的除数（或因子），a

46、为为b的倍数。的倍数。v 整除具有以下性质：整除具有以下性质：（1）若）若b | a，c | b，则，则c | a；（2）若）若a | 1，则，则a=1；若；若a | b且且b | a，则，则a=b；（3）对任一）对任一b(b0)，则，则b | 0；（4）若）若b | g，b | h，则对任意整数，则对任意整数m，n有有b | (mg+nh) 整除实例Q: 下面哪个是对的下面哪个是对的?1.77 | 72.7 | 773.24 | 244.0 | 245.24 | 0对对对数论的基本概念素数v2. 素数和合数素数和合数v一个大于一个大于1且只能被且只能被1和它本身整除的整数，称和它本身整除的整

47、数，称为为素数素数(prime number)；否则，称为；否则，称为合数合数(composite)。例如：。例如：2、3、5、7、11就是素就是素数。除数。除2之外所有的素数必定都是奇数。之外所有的素数必定都是奇数。 v对于素数，有以下定理：对于素数，有以下定理：v定理定理1.1 任一正整数任一正整数a都能分解成素数乘积的形都能分解成素数乘积的形式，并且此表示是唯一的。式，并且此表示是唯一的。ttpppa2121gcdv定理定理1.2 若若p是素数，是素数，p | ab，则，则p | a或或p | b。v如果整数如果整数a能整除整数能整除整数a1, a2, a3, , an，则称，则称a为为

48、这几个整数的公因子。这几个整数可能有多个这几个整数的公因子。这几个整数可能有多个公因子，其中最大的公因子叫公因子，其中最大的公因子叫最大公因子最大公因子（GCD，Greatest Common Divisor），记做），记做gcd(a1, a2, a3, , an)或或(a1, a2, a3, , an) v 若若p是素数，是素数，a是任意整数，则有是任意整数，则有p | a或或gcd(p, a)=1，即素数与任意数之间只可能是整除或互，即素数与任意数之间只可能是整除或互素的关系素的关系 gcd的性质和求法v定理定理1.4 设设a，b，c是任意不全为是任意不全为0的整数，且的整数，且a=qb+

49、c，其中，其中q是整数，则有：是整数，则有：gcd(a, b)= gcd(b, c)或写成或写成gcd (a, b)=gcd (b, a mod b)。v即被除数和除数的最大公因子与除数和余数的即被除数和除数的最大公因子与除数和余数的最大公因子相同。例如：最大公因子相同。例如：gcd(18, 12)= gcd(12, 6) = gcd(6, 0)=6gcd(11, 10)= gcd(10, 1) = gcd(1, 0)=1素数的相关定理v定理定理1.5 任给整数任给整数ab0，则存在两个整数，则存在两个整数m, n，使得：使得：ma+nb=gcd(a, b)gcd(a,b)记为记为c，则有，则

50、有c|a,且且c|b,从而从而c|ma+nb 若若 a | b且且a|c,则对任意的则对任意的 m,n,有有 a|(bm+cn).证明证明 因为因为a|b且且a|c, 故故b=aq1和和c=aq2. 于是于是, bm+cn=a(q1m+q2n), 所以所以, a|(bm+cn).例如：若例如：若a=3，b=2，则，则gcd(a, b)=1，存在，存在m=1，n=-1合数的定理v定理定理1.6 若若a是合数，则是合数，则a有一因数有一因数d满足：满足：1d=a1/2。v定理定理1.7 若若a是合数，则是合数，则a必有一素因数小于或等必有一素因数小于或等于于a1/2。3. 模运算与同余v设设n是一

51、正整数，是一正整数，a是整数，如果用是整数，如果用n除除a，得商，得商为为q，余数为，余数为r，即，即a=qn+r，0rn，则余数，则余数r可可以用以用“a mod n”表示，即表示，即r=a mod n；商；商q可表示可表示为为q= ，其中，其中， 表示小于或等于表示小于或等于x的最大的最大整数。整数。 v同余同余：如果：如果a mod n=b mod n，则称两整数则称两整数a和和b模模n同余，记为同余，记为ab mod nna/ x注意：同余符注意：同余符“”和等号和等号“=”的区别的区别ab (mod m) m|(a-b)同余的性质v同余的性质：同余的性质：v 自反性：如自反性：如aa

52、 mod n；v 对称性：若对称性：若a b(mod m)，则，则b a(mod m)；v 传递性：若传递性：若a b(mod m)，b c(mod m)，则，则a c(mod m)。模运算与同余v求余运算求余运算a mod n将整数映射到非负整数的集合将整数映射到非负整数的集合Zn=0,1, , n-1，称为求余运算，在这个集合上，称为求余运算，在这个集合上的运算称为的运算称为模运算模运算。称称Zn为模为模n的的同余类集合同余类集合。其。其上的模运算有以下性质：上的模运算有以下性质： (a mod n)+(b mod n) mod n=(a+b) mod n。 (a mod n)-(b mo

53、d n) mod n=(a-b) mod n。 (a mod n)(b mod n) mod n=(ab) mod n。 同余式的运算规则v定理定理1.8 若若ab(mod m)，cd(mod m)，则有：，则有： ax+cybx+dy(mod m), 其中其中x和和y为任给整数；为任给整数；证明：证明：因为因为m|(a-b), m|(c-d), 故有故有m|x(a-b)+y(c-d) = (ax+cy)-(bx+dy). acbd(mod m)；证明：由证明：由 m|c(a-b)+b(c-d)=ac-bd立即可得立即可得.同余式的运算规则 anbn(mod m), 其中其中 n0。例如。例如

54、25 mod 3，则则2*25*2 mod 3。 anbn(mod m), 其中其中 n0。例如。例如25 mod 3，则则2252 mod 3。 f(a)f(b)(mod m), 其中其中f(x)为任给的一个整为任给的一个整系数多项式。系数多项式。同余式的运算规则v1）如果）如果acbd(mod m)，ab(mod m)，gcd(a, m)=1，则，则cd(mod m)v2）存在）存在c，使得，使得ac1(mod m)，当且仅，当且仅当当gcd(a, m)=1v3）ab(mod m)，如果，如果d是是m的因子，则的因子，则ab(mod d)。 逆变换v1）加法逆元加法逆元：对每一个：对每一个

55、a，存在一个，存在一个b，使得，使得a+b=0 mod n，则称，则称b为为a对模对模n的加法逆元，例的加法逆元，例如如5+3 mod 4=0，我们就称，我们就称5是是3对模对模4的加法逆的加法逆元。元。v2）乘法逆元乘法逆元：若若m1，gcd(a,m)=1，则存在，则存在c使使得得ca1(mod m)，我们把满足这样条件的，我们把满足这样条件的c称为称为a对模对模m的乘法逆元，记作的乘法逆元，记作a-1 (mod m)。若。若aZm，则则a对模对模m的逆记作：的逆记作：a-1。例如例如5*3 mod 7=1。 欧拉函数 v定义：设定义：设n是一正整数，是一正整数，小于小于n且与且与n互素互素

56、的正整数的个数的正整数的个数称为称为n的欧拉函数，记为的欧拉函数，记为(n)。v欧拉函数的性质（求法）：欧拉函数的性质（求法）：1）若）若n是素数，则是素数，则(n)=n-1；2）若）若n=p*q，p、q是素数且是素数且pq，则，则(n)=(p-1)*(q-1)；欧拉函数（2）v3）若）若np1a1p2a2psas，其中，其中p1, p2, , ps为素数，为素数，a1, a2, as为正整数，则有：为正整数，则有：v例如：例如：(6)= (3-1)*(2-1)=2；(7)=7-1=6；(8)=8*(1-1/2) =4；(20)=20*(1-1/5) *(1-1/2)=8；(49)=49*(1

57、-1/7) =42。 spppnn111111)(21v欧拉（欧拉（Euler）定理：若）定理：若a和和n都是正整数，且都是正整数，且gcd (a, n) =1，则有，则有a(n) mod n =1。v欧拉定理的应用：求解欧拉定理的应用：求解3102 mod 11v解：因为解：因为gcd (3, 11) =1，则有，则有310 mod 11=1 （因为（因为(11)=10）v所以所以310*10 mod 11=110=1，3100+2 mod 11=32 mod 11=9v推论：若推论：若a与与n互素，则互素，则a与与a (n)-1 互为乘法逆互为乘法逆元。元。 欧拉定理例题eg: 求求780

58、3的后三位数字的后三位数字 解：解： 7803（mod 1000）的结果）的结果 ?(1000) = 1000(1-1/2)(1-1/5) = 400， 有有7803 (7400)273 343 (mod 1000)例如：例如： 求求 253 (mod 11) = ? 由由Fermat小定理小定理: 210 = 1024 1 (mod 11) 253 = (210)523 1523 8 (mod 11) 费马定理v费马（费马（Fermat）定理：设）定理：设a和和p都为正整数，且都为正整数，且p是素数，若是素数，若gcd (a, p) =1，则，则ap-1 1 mod p。也可。也可写成设写成

59、设p是素数，是素数，a是任一正整数，则是任一正整数，则apa mod p。当当n为素数时，欧拉定理即转化为费马定为素数时，欧拉定理即转化为费马定理，该费马定理又叫做费马小定理理，该费马定理又叫做费马小定理（1）通常情况下，如果）通常情况下，如果2n-1 1 (mod n),n为素数为素数,然而然而,也有例外也有例外: 561 = 3 11 17是合数是合数,但但2560 1 (mod 561)。因此，如果。因此，如果2n-1 1 (mod n),那么那么n可可能为素数。能为素数。 （2）但）但2n-1 模模n 不等于不等于 1,那么那么n不可能为素数不可能为素数 这为我们提供一种寻找素数的方法

60、，给定一个这为我们提供一种寻找素数的方法，给定一个n, 计算计算2n-1 模模n 是否等于是否等于 1，如果不等于，如果不等于1， n为非为非素数，如果等于素数，如果等于1，还需用更复杂的方法来判断，还需用更复杂的方法来判断是否为素数，是否为素数，数论的其他重要定理v3. 威尔逊定理：若威尔逊定理：若p为素数，则为素数，则p可整除可整除(p-1)!+1，该定理给出了判定自然数为素数的充要条件。该定理给出了判定自然数为素数的充要条件。v4. 中国剩余定理：已知某个数关于一些两两互中国剩余定理：已知某个数关于一些两两互素的数的同余类集，就可重构这个数。如某个素的数的同余类集，就可重构这个数。如某个