Chapter 2 密码学基础

1、第二章 密码学基础,目录,2.1 密码学的基本知识 2.2 对称密码体制 2.3 密码学的数学基础 2.4 公钥密码体制,密码学的基本概念,是经过伪装后的明文c。全体可能出现的密文集合称为密文空间C,密文,未经过加密的原始信息称为明文m，明文的全体称为明文空间 M,明文,由明文空间、密文空间、密码方案和密钥空间组成,密码 系统,密码学的基本概念,密码学的基本概念(2),加密和解密算法的操作在称为密钥（k）的元素控制下进行。密钥的全体称为密钥空间（K）,密钥,确切地描述了加密变换和解密变换的具体规则,密码 方案,加密算法 对明文进行加密时所使用的规则的描述(m),解密算法 对密文进行还原时所使用

2、的规则D(c),保密通信系统的基本模型,有了密钥的概念后，加密的过程：c=EKe(m)，解密的过程:m=DKd(c)，其中mM，cC,被动攻击和主动攻击,密码分析者（Cryptanalyst）又称攻击者，可采用搭线窃听等方式直接获得未经加密的明文或加密后的密文，并分析得知明文。这种对密码系统的攻击手段称为被动攻击（Passive attack），特点：不破坏原始信息 攻击者还可以采用删除、更改、增添、重放、伪造等手段主动向系统注入假信息，这种对密码系统的攻击手段称为主动攻击（Active attack）,被动攻击和主动攻击,密码体制的分类,1. 按照密码的发展历史分类密码可分为古典密码和近现代

3、密码 2.按照需要保密的内容分类 根据密码体制的密码算法是否需要保密，可分为受限制的算法和基于密钥的算法 1883年Kerchoffs第一次明确提出了编码的原则，即加密算法应建立在算法的公开不影响明文和密钥的安全的基础上,密码体制的分类,3. 根据加密和解密所使用的密钥是否相同对称密码体制 公钥密码体制：也称为非对称密码体制,对称密码体制,对称密码体制 Symmetric Key Cryptosystem,加密密钥=解密密钥,密钥必须保密,公钥密码体制,公钥密码体制 Public Key Cryptosystem,加密密钥解密密钥,加密密钥为公钥（Public Key），公钥无需保密 解密密钥

4、为私钥（Private Key）,密码体制的分类,4. 根据对明文的处理方式 分组密码算法和流密码算法 5. 根据是否能进行可逆的加密变换分为单向函数密码体制和双向变换密码体制,密码学的发展历程,密码学的发展历程,古典密码体制,近现代密码体制 Shannon的保密通信的信息理论,密码学的新方向 Diffie和Hellman密码学的新方向,密码分析与密码系统的安全性,密码系统的安全性取决于,(1) 所使用的密码算法的保密强度,(2) 密码算法以外不安全的因素,因此必须同时完善技术与管理上的要求，才能保证整个密码系统的安全,密码分析研究如何分析和破解密码,密码分析的方法,密码分析攻击的类型,假设密

5、码分析者已经知道加密算法，根据密码分析者对明文、密文等资源的掌握程度： 1）唯密文攻击（Ciphtext-only attack） 2）已知明文攻击（Plaintext-known attack） 3）选择明文攻击（Chosen-plaintext attack） 4）选择密文攻击（ChosenCiphtext attack）,现代加密算法的设计目标是要能抵抗住选择明文攻击,密码系统安全性的层次,无条件安全（Unconditionally Secure） 计算上安全（Computationally Secure） 可证明安全（Provable Secure）,一般认为，密码系统只要能达到计算上

6、安全就是安全的,目录,2.1 密码学的基本知识 2.2 对称密码体制 2.3 密码学的数学基础 2.4 公钥密码体制,对称密码体制,对称密码体制，即加密密钥与解密密钥相同的密码体制，这种体制只要知道加（解）密算法，就可以反推解（加）密算法 在1976年公钥密码算法提出以前的所有加密算法都是对称密码体制 对称密码体制可分为分组密码和流密码 本节将介绍的古典密码、分组密码和流密码,古典密码,置换（换位）是对明文中的元素进行 换位排列，可以证明置换是替代的一 种特殊形式,置换,替代是将明文中的每个元素映射为另一个元素，明文元素被其他元素所替代而形成密文,替代,采用的加密思想：替代和置换,对于明文“d

7、og”，使用替代技术加密：结果可能是“eph”，使用置换技术加密：结果可能是“ogd”,讨论下面密码算法的加密思想,Scytale 密码 棋盘密码,几种典型的古典密码,移位密码（又称凯撒密码） 一般单表替代密码 仿射密码 密钥短语密码 维吉尼亚（Vigenere）密码 希尔（Hill）密码 置换密码,移位密码,加密变换：Ek(m)=m+k(mod 26) mM, kK 解密变换：Dk(c)=c-k(mod 26) cC, kK 很容易利用穷举法将密文解密，最多尝试25次，就能找到密文对应的明文信息,将明文每个字母前移三位,移位密码加密示例,密钥产生）Alice与Bob协定编码方式为明文字母后移

8、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，I，T，E，V，X”。,加密：,2.一般单

9、表替代密码,明文消息中的每个字母不是同时移动相同的位数，而是根据一张替代表使用随机替换,一张一般单表替代密码的映射表,c=Ek(m)=(m)m=Dk(c)=-1(c),3. 仿射密码,加密变换为： c=Ek(m)= (k1m+k2) mod 26 相应的解密变换为： m=Dk(c)=k1-1(c-k2) mod 26 注意：k1必须和26互素，如果不互素，例如取k1=2，则明文m=mi和m=mi+13两个字符都将被映射成同一个密文字符,仿射密码示例,例：Alice欲将明文m=“affine”用仿射密码加密，传递给Bob，Bob来解读。,密钥：,Alice与Bob事先协定一把密钥K=(3,8)其

10、中gcd(3,26)=1,加密：,解密：,密钥短语密码,密钥短语密码选用一个英文短语或单词作为密钥，如密钥为university时，先去掉重复字母i，成为universty,总结：单表替代密码的特点,以上几种密码都是单表替代密码，特点如下：,这个特点使其密文中单字母出现的频率分布与明文中的相同，因此任何单表替代密码都经不起统计分析。,明文和密文是一对一的映射关系。Ef (x0,x1,x2,)=(f(x0),f(x1),f(x2),),对单表加密算法的统计分析,另外最常出现的双字母组合为： th(3.15%)，he(2.51%)，an(1.72)，in(1.69%)，er(1.54%)，re(1

11、.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，。,多表替代密码,多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布 同一个明文字母将对应不同的密文字母,Ef (x0,x1,x2,)=(f0(x0),f1(x1),f2(x2),),维吉尼亚（Vigenere）密码,维吉尼亚密码：一种典型的多表替代密码，该密码体制有一个参数n，表示采用n位长度的字

12、符串（例如一个英文单词）作为密钥。 设密钥k=k1k2kn，明文M=m1m2mn，则加密变换为： Ek(m1,m2,mn)=(m1+k1mod 26, m2+k2mod 26 ,mn+knmod 26 ),维吉尼亚密码举例,例2.2 设明文为“killthem”密钥为“gun”，试用维吉尼亚密码对明文进行加密。 加密密钥：k=gun=(6,20,13),因,密文为：hcyrnvwg,破解维吉尼亚密码,密文为：hcyrnvwgcxgtu h n c u c v x y w g r g t,关键是如何确定密钥长度n,希尔密码,希尔密码：利用矩阵变换来对信息实现加密。 数学定义：设m是一个正整数，令

13、M=E=(Z26)m，密钥Kmm=定义在Z26上的mm矩阵，其中K的行列式值必须和26互素，否则不存在K的逆矩阵K-1。 对任意的密钥Kmm，定义加密/解密变换为Ek(x)= Kmmx mod 26Dk(y)= K-1mmy mod 26,希尔（Hill）密码举例,密钥产生：,首先决定所用矩阵的大小，譬如是22,其中E的行列式值detE必须与26互素，否则不存在E的反矩阵。,明文：,m=Hill,矩阵形态,加密过程：,密文,c=pbwz,如何求矩阵的逆矩阵,A*为A的伴随矩阵。,Hill密码解密过程,解密矩阵,计算加密矩阵的逆矩阵，再进行模运算（mod 26）， 得解密矩阵,解密过程,常见的置

14、换密码,置换（Permutation）密码通过改变明文消息中各字符出现的相对位置，但明文消息字符本身的取值不变。置换密码的一个显著特点是它的明文空间和密文空间完全相同 列置换密码 螺旋置换密码,置换密码,置换密码：Ek(dog)=ogd可用如下希尔密码实现,这证明了置换密码可转换为替代密码,古典密码分类汇总图,替代密码,单表替代密码,多表替代密码,移位密码,仿射密码,密钥短语密码,一般单表替代密码,维吉尼亚密码,希尔密码,置换密码,2.2.2 分组密码,分组密码体制是目前商业领域中比较重要而流行的一种加密体制，它广泛地应用于数据的保密传输、加密存储等应用场合。 加密时，先对明文分组，每组长度都

15、相同，然后对分组加密得到等长的密文，分组密码的特点是加密密钥与解密密钥相同。 如果明文不是分组长的倍数，则要填充,分组密码算法的要求,将大的明文分组再分成几个小段，分别完成各个小段的加密置换，最后进行并行操作,强化密码算法的措施,采用乘积密码技术。乘积密码就是以某种方式连续执行两个或多个密码变换,分组长度m足够大,密钥空间足够大,密码变换必须足够复杂,数据加密标准DES,DES是一种分组密码算法，它将明文从算法的一端输入，将密文从另一端输出。 由于采用的是对称密钥，因此加密和解密使用相同的算法和密钥 并且加密和解密算法是公开的，系统的安全性完全依赖于密钥的保密,DES分组的原理,DES对数据进

16、行加密时，首先将数据切分成64位的明文分组 它使用的密钥为64位，但有效密钥长度为56位（另有8位用于奇偶校验）。输出的密钥分组也是64位 解密时的过程和加密时的类似，但密钥的顺序正好相反,DES的加密过程,（1）明文初始置换 （2）密钥初始置换 （3）生成16个48位的子密钥 （4）明文扩展置换 （5）S盒替代 （6）P盒置换 （7）末置换 （8）DES的解密,DES加密过程,明文初始置换,初始置换,M=m1m2,m62m63,m64,M=m58m50,m23m15,m7,IP(M),由于M(64位) =0000 0001 0010 0011 0100 0101 0110 0111 1000

17、 1001 1010 1011 对M运用IP，故有IP(64位) = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010,将明文分成左右两半,IP(64位) = L0(32位) + R0(32位) 故 L0 (32位) = 1100 1100 0000 0000 1100 1100 1111 1111 R0 (32位) = 1111 0000 1010 1010 1111 0000 1010 1010,密钥初始置换,16轮子密钥的生成,第一步：生成16个子钥(48位),从而得到C1D1 C16D16： C1 = 1110000

18、110011001010101011111D1 = 1010101011001100111100011110 C2 = 1100001100110010101010111111D2 = 0101010110011001111000111101 C3 = 0000110011001010101011111111D3 = 0101011001100111100011110101 C4 = 0011001100101010101111111100D4 = 0101100110011110001111010101 C15 = 1111100001100110010101010111D15 = 1010

19、101010110011001111000111 C16 = 1111000011001100101010101111D16 = 0101010101100110011110001111,明文扩展置换,对Ri-1进行扩展置换,与密钥Ki进行异或运算,进行S盒替代,8个S 盒的表,P盒置换,Li = Ri-1 i=1,2,16 Ri = Li-1f ( Ri-1 , Ki ),16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25,对R16L16作末置换,40 8 48 16 5

20、6 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25,DES加密的特点,综合运用了许多次置换和替代技术,从而达到了混淆和扩散的特点 扩散：将明文的统计特性散布到密文中。目的是使明文的每一位影响密文中多位的值 混淆：应使得密钥和明文以及密文之间的依赖关系相当复杂，以至于这种依赖性对密码分析者来说是无法利用的。 采

21、用了乘积密码技术，将R0加密后的所得结果R1再作为L2的输入进行加密,DES算法的变形,利用两个密钥的三重DES 若K1=K2，将可兼容单DES算法,其他分组密码,AES高级加密标准（Advanced Encryption Standard）明文分组的长度为128比特，而密钥长度可以为128、192、256比特 IDEA国际数据加密标准（International Data Encryption Algorithm）是最强大的数据加密标准之一,流密码,流密码采用密钥流生成器，从种子密钥生成一系列密钥流来加密信息，每个明文字母被密钥流中不同的密钥字母加密,流密码的类型,流密码的思想：模拟一次一密

22、 同步流密码 ：密钥流和明文流相互独立； (如密钥流是固定的，明文每次是变化的) 异步流密码： 密钥流和明文流不相互独立，密钥流的产生有密文或者明文的参与，会发生错误传播现象,同步流密码,设维吉尼亚密码的密钥为cipher，则密钥长度d=6，将该密钥作为流密码的种子密钥， 密钥流产生器产生密钥流的规则为：第一次用该密钥加密明文，然后将该密钥每位循环右移一位。例如 设种子密钥 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）,异步流密码,

23、明文： t h i s i s a s a m p l e 密钥： c i p h e r 密钥流：c i p h e r t h i s i s a 密钥与明文有关，若明文在传输中发生错误，则会导致密钥也发生错误，即错误传播现象,目录,2.1 密码学的基本知识 2.2 对称密码体制 2.3 密码学的数学基础 2.4 公钥密码体制,数论的基本概念 整除,1. 整除 设a, b是两个整数，其中b0，如果存在另一整数m使得等式a=mb成立，则称b整除a，记为b | a，并称b是a的除数（或因子），a为b的倍数。 整除具有以下性质： （1）若b | a，c | b，则c | a； （2）若a | 1

24、，则a=1；若a | b且b | a，则a=b； （3）对任一b(b0)，则b | 0； （4）若b | g，b | h，则对任意整数m，n有b | (mg+nh),数论的基本概念素数,2. 素数和合数 一个大于1且只能被1和它本身整除的整数，称为素数（或质数）；否则，称为合数。例如：2、3、5、7、11就是素数。除2之外所有的素数必定都是奇数。 对于素数，有以下定理： 定理1.1 任一正整数a都能分解成素数乘积的形式，并且此表示是唯一的。,gcd,定理1.2 若p是素数，p | ab，则p | a或p | b。 如果整数a能整除整数a1, a2, a3, , an，则称a为这几个整数的公因子

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

26、, 12)= gcd(12, 6) = gcd(6, 0)=6 gcd(11, 10)= gcd(10, 1) = gcd(1, 0)=1,素数的相关定理,定理1.5 任给整数ab0，则存在两个整数m, n，使得： ma+nb=gcd(a, b) 定理1.6 若a是合数，则a有一因数d满足：1d=a1/2。 定理1.7 若a是合数，则a必有一素因数小于或等于a1/2。,例如：若a=3，b=2，则gcd(a, b)=1，存在m=1，n=-1,3. 模运算与同余,设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，即a=qn+r，0rn，则余数r可以用“a mod n”表示，即r=a mo

27、d n；商q可表示为q= ，其中， 表示小于或等于x的最大整数。 同余：如果a mod n=b mod n，则称两整数a和b模n同余，记为ab mod n,模运算与同余,求余运算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 mod n) mod n=(a-b) mod n。 (a mod n)(b mod n) mod n=(ab) mod n。,同余的性质,同余的性质： 若

28、n | (a-b)，则ab mod n； 自反性：如aa mod n； 对称性：若ab(mod m)，则ba(mod m)； 传递性：若ab(mod m)，bc(mod m)，则ac(mod m)。,同余式的运算规则,定理1.8 若ab(mod m)，cd(mod m)，则有： ax+cybx+dy(mod m), 其中x和y为任给整数； acbd(mod m)； anbn(mod m), 其中 n0。例如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)为任给的一

29、个整系数多项式。,同余式的运算规则,1）如果acbd(mod m)，ab(mod m)，gcd(a, m)=1，则cd(mod m) 2）存在c，使得ac1(mod m)，当且仅当gcd(a, m)=1 3）ab(mod m)，如果d是m的因子，则ab(mod d)。,逆变换,1）加法逆元：对每一个a，存在一个b，使得a+b=0 mod n，则称b为a对模n的加法逆元，例如5+3 mod 4=0，我们就称5是3对模4的加法逆元。 2）乘法逆元：若m1，gcd(a,m)=1，则存在c使得ca1(mod m)，我们把满足这样条件的c称为a对模m的乘法逆元，记作a-1 (mod m)。若aZm，则a

30、对模m的逆记作：a-1。例如5*3 mod 7=1，我们就称5是3对模7的乘法逆元。,欧拉函数,定义：设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为(n)。例如小于6且与6互素的数只有1和5，因此(6)=2。 欧拉函数的性质（求法）： 1）若n是素数，则(n)=n-1； 2）若n=p*q，p、q是素数且pq，则(n)=(p-1)*(q-1)；,欧拉函数（2）,3）若np1a1p2a2psas，其中p1, p2, , ps为素数，a1, a2, as为正整数，则有： 例如：(6)= (3-1)*(2-1)=2；(7)=7-1=6；(8)=8*(1-1/2) =4；(20)=

31、20*(1-1/5) *(1-1/2)=8；(49)=49*(1-1/7) =42。,欧拉（Euler）定理：若a和n都是正整数，且gcd (a, n) =1，则有a(n) mod n =1。 欧拉定理的应用：求解3102 mod 11 解：因为gcd (3, 11) =1，则有310 mod 11=1 （因为(11)=10） 所以310*10 mod 11=110=1，3100+2 mod 11=32 mod 11=9 推论：若a与n互素，则a与a (n)-1 互为乘法逆元。,欧拉定理,费马定理,费马（Fermat）定理：设a和p都为正整数，且p是素数，若gcd (a, p) =1，则ap-

32、1 1 mod p。也可写成设p是素数，a是任一正整数，则apa mod p。,当n为素数时，欧拉定理即转化为费马定理，该费马定理又叫做费马小定理,数论的其他重要定理,3. 威尔逊定理：若p为素数，则p可整除(p-1)!+1，该定理给出了判定自然数为素数的充要条件。 4. 中国剩余定理：已知某个数关于一些两两互素的数的同余类集，就可重构这个数。如某个数模3余2、模5余3、模7余2，使用中国剩余定理就可求出该数是23。,中国剩余定理的思想在密钥分割中很有用,欧几里得（Euclid）算法,基本的欧几里德算法可求两个正整数的最大公因子GCD，这时也叫辗转相除法，而扩展的Euclid算法还可用来求出其

33、中一个数关于另一个数的乘法逆元 1. 求最大公因子GCD 对欧几里得算法的具体描述是： 对于整数a，b（ab），如果要求gcd(a, b)，步骤如下： （1）用a mod b 得余数 c （2）将b作为a，c作为b，重复步骤1，2（若c不为0，否则转3） （3）如果c等于0，则退出，返回b则是所求的gcd(a, b),例2.5 求gcd(1970, 1066),解：1970=11066+904,gcd(1066, 904) 1066=1904+162,gcd(904, 162) 904=5162+94,gcd(162, 94) 162=194+68,gcd(94, 68) 94=168+26,

34、gcd(68, 26) 68=226+16,gcd(26, 16) 26=116+10,gcd(16, 10) 16=110+6,gcd(10, 6) 10=16+4,gcd(6, 4) 6=14+2,gcd(4, 2) 4=22+0,c等于0，返回b=2 因此gcd(1970, 1066)=2。,2. 求乘法逆元,扩展的欧几里得算法（extended Euclid） 1）首先定义几个变量X1, X2, X3, Y1, Y2, Y3和Q，令： (X1, X2, X3)等于(1, 0, n)；(Y1, Y2, Y3)等于(0, 1, a)；令Q值为空；将它们写到表格的第一行。 2）然后令Q=，根

35、据得到的Q计算(X1-QY1, X2-QY2, X3-QY3)，将计算结果暂存到T1, T2, T3。 3）重新赋值，将原来(Y1, Y2, Y3)的值赋给新的(X1, X2, X3)，即(X1, X2, X3)(Y1, Y2, Y3)，将(T1, T2, T3)的值赋给新的(Y1, Y2, Y3) 4）重复第2、3步，直到Y3等于1或0，如果Y3=1，返回最大公因子的值为Y3，乘法逆元的值为Y2。如果Y3=0，则表示无乘法逆元，最大公因子为X3的值。,求乘法逆元的例子,用扩展的欧几里得算法计算37-1 mod 98,离散对数,欧拉定理指出如果gcd(a, n)=1，则a(n)1 mod n。

36、现在考虑如下的一般形式： am1 mod n 如果a与n互素，则至少会有一整数m（比如m=(n)）满足这一方程。称满足方程的最小正整数m为模n下a的阶。 例如：a=7，n=19，则易求出717 mod 19，7211 mod 19，731 mod 19，即7在模19下的阶为3。,本原根,定理4.1 设a的阶为m，则ak1 mod n的充要条件是k为m的倍数。 推论：a的阶m整除(n)。 如果a的阶m等于(n)，则称a为n的本原根。 如果a是n的本原根，则a,a2,a(n)在mod n下互不相同且都与n互素。特别地，如果a是素数p的本原根，则a,a2,ap-1在 mod p下都不相同。,本原根举

37、例,例如：n=9，则(n)=6，考虑2在mod 9下的幂21 mod 92，22 mod 94，23 mod 98，24 mod 97，25 mod 95，26 mod 91。即2的阶为6，正好等于(9)，所以2为9的本原根。,离散对数,计算bak mod p 对于任意b1, p-1，都有且仅有唯一的正整数k与b对应，使得bak mod p，也就是说b和k之间是一一对应的关系。称k为模p下以a为底b的离散对数，记为klogab(mod p),离散对数的这一特点保证了任意一个明文（密文）字符都有且仅有唯一的密文（明文）字符与之对应,离散对数难题,当a、k、p已知时，可有快速算法比较容易地求出b的

38、值；但如果已知b、a和p时，要求k的值，对于小心选择的p将至少需要p1/2次以上的运算，如果p足够大，求解离散对数问题是相当困难的，这就是著名的离散对数难题。 由于离散对数问题具有较好的单向性，所以离散对数问题在公钥密码学中得到广泛应用。像EIGamal、Diffie-Hellman、DSA等密码算法都是建立在离散对数问题之上的,目录,2.1 密码学的基本知识 2.2 对称密码体制 2.3 密码学的数学基础 2.4 公钥密码体制,公钥密码体制,公钥密码算法：基于数学函数而不是基于替换和置换 公钥密码体制是不对称的，它有两个密钥，一个为密钥拥有者保管，另一个公开。用两个密钥中任何一个密钥加密内容

39、，都能且只能用对应的另一个密钥解密， 可解决对称密码体制中的密钥管理、分发和数字签名的难题,2.4.1公钥密码体制的基本思想,使用两个不同的密钥进行加密和解密，一个可对外公开，称为公钥Public Key；另一个严格保密，只有所有者才知道，称为私钥Private Key一般用KR或SK表示。 下面两种做法是可行的： 用公钥加密、私钥解密 用私钥加密、公钥解密 而以下两者做法是行不通的： 用公钥加密、公钥解密 用私钥加密、私钥解密,公钥密码体制示意图,保存有其他用户（如B、C、D等）的公钥,公钥密码体制应满足以下要求,1）对任意明文进行加密变换是很容易的，并且若知道解密密钥，那么对密文的解密也是

40、很容易的； 2）信息的发送方对任意明文进行加密变换后，接收方进行解密变换就可以得到明文； 3）若不知道解密密钥，那么即使知道加密密钥，具体的加密与解密算法以及密文，确定明文在计算上也是不可行的。,单向陷门函数的引例,开关防盗门,关门容易，但如果没有钥匙，要打开关着的门非常困难，单向陷门函数是公钥密码体制实现的基础,单向陷门函数的特点,1）正向易算性给出f的定义域中的任意元素x，计算f(x)是很容易的； 2）当给出y=f(x)中的y，要计算x=fk-1(y)时，若知道设计函数f(x)结合进去的某种信息时，则容易计算（陷门依赖性）；否则x=fk-1(y)将是很难计算的（反向不可算性）。,实现单向陷

41、门函数的数学难题,单向陷门函数一般基于数学上的难解的问题来实现。目前常见的数学难题有： （1）基于大整数分解的数学难题，即已知两个素数，要求它们的乘积是容易的，但已知它们的乘积，要将它们分解成两个素数是很困难的，代表算法是RSA。 （2）基于离散对数的难题，代表算法有EIGamal、Diffie-Hellman、DSA等； （3）基于椭圆曲线的难题，代表算法有椭圆曲线密码体制ECC（Elliptic Curves Cryptography,2.4.2 RSA公钥密码体制,RSA算法是一个公钥密码算法 1978年由R.Rivest, A.Shamir和L.Adleman提出 RSA的安全性基于数

42、论中大整数的素数分解难题， 其密钥对是一对大素数（100200位十进制数或更大），从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。,大整数分解难题的几类,设N是两个大素数的乘积:则存在以下几个难题 (l)分解N (2)给定整数M(明文)和C(密文)寻找d满足Md=C mod N (3)给定整数e和C，寻找M满足c=me mod n (4)给定整数x，判定是否存在整数y满足x=y2 mod N,RSA算法基于第(3)个难题,RSA算法的运算过程,加密 c=me mod n 解密 m=cd mod n 明文分组m为整数且必须小于n,RSA算法的过程：密钥产生,找素数 选取两个大的随

43、机的素数p，q 计算模n和Euler函数(n) npq (n)=(p-1)(q-1) 找ed1 mod (n) 随机取一个数e(与(n)互素)，用扩展Euclid算法求d即可 发布 d保密，(d, n)是私钥 Ks 发布(e,n)，这是公钥Kp 销毁p、q,RSA的简单例子,任选两个素数 p7，q17,npq (n)请练习,任务：对明文 M=19 加密,npq119 (n)(p-1)(q-1)61696,选取整数1e (n)与(n) 互素：e5,求e的逆元d：ed1 mod (n) 请练习,计算 C=Me(mod n)=? 其中M=19 请练习,计算 M=Cd(mod n)=? 请练习,d=7

44、7,c=66,RSA参数的考虑,素数 必须够大，否则对手可能很快分解n 判定是否为素数，采用Miller-Rabin概率测试方法 假素数意味着加解密不能正确进行，故可放弃之 强素数 (p-1)/2和(q-1)/2应是素数 选取较小的e和较大的d e：3、65537,RSA参数的考虑,p和q在长度上应仅差几个数位，即p和q应是1075 到10100 （p-1）和（q-1）都应包含一个较大的素数因子，r-1也有一个大的素因子 gcd(p-1, q-1)应比较小 如果en 且 dn1/4,则d可以很容易确定,证明RSA算法中解密的正确性,证明： 由加密过程知cme mod n，所以 cd mod n

45、med mod nmk(n)+1 mod n 下面分两种情况： m与n互素，则由Euler定理得 m(n)1 mod n,mk(n)1 mod n,mk(n)+1m mod n 即cd mod nm。,证明RSA算法中解密的正确性, m与n不互素，即gcd(m,n)1 先看gcd(m,n)=1的含义，由于n=pq，所以gcd(m,n)=1意味着m不是p的倍数也不是q的倍数。因此gcd(m,n)1意味着m是p的倍数或q的倍数，不妨设m=tp，其中t为一正整数。此时必有gcd(m,q)=1，否则m也是q的倍数，从而是pq的倍数，与mn=pq矛盾。,提示：一个明文m同n不互素的概率小于1/p+1/q

46、，因此，如果p和q的值极其大的话，gcd (m, n)1的概率极小，也可忽略不计,证明RSA算法中解密的正确性,由gcd(m,q)=1及Euler定理得m(q)1 mod q，所以 mk(q)1 mod q,mk(q)(p)1 mod q, mk(n)1 mod q 因此存在一整数r，使得mk(n)=1+rq，两边同乘以m=tp得 mk(n)+1=m+rtpq=m+rtn 即mk(n)+1m mod n，所以cd mod nm。 (证毕),Diffie-Hellman密钥交换,Diffie-Hellman算法 Diffie-Hellman算法是第一个公开密钥算法，发明于1976年1。Diffi

47、e-Hellman算法只能够用于密钥分配，但不能用于加密或解密信息。,算法的安全性基于求离散对数的困难性,如果Alice和Bob想在不安全的信道上交换密钥，他们可以采用如下步骤： (1) Alice和Bob协商一个大素数p及p的本原根a，a和p可以公开； (2) Alice秘密产生一个随机数x，计算X=ax mod p，然后把X发送给Bob； (3) Bob秘密产生一个随机数y，计算Y= ay mod p，然后把Y发送给Alice；,(4) Alice计算k=Yx mod p； (5) Bob计算k=Xy mod p。 k和k是恒等的，因为 k= Yx mod p=(ay)x mod p=(a

48、x)y mod p= Xy mod p= k 线路上的搭线窃听者只能得到a、p、X和Y的值，除非能计算离散对数，恢复出x和y，否则就无法得到k，因此，k为Alice和Bob独立计算的秘密密钥。,下面用一个例子来说明上述过程。Alice和Bob需进行密钥交换，则： 两人协商后决定采用素数p=353及其本原根a=3。 Alice选择随机数x=97，计算X=397 mod 35340，并发送给Bob。 Bob选择随机数y=233，计算Y=3233 mod 353248，并发送给Alice。 Alice计算k=Yx mod p24897 mod 353=160。 Bob计算k=Xy mod p4023

49、3 mod 353=160。k和k(160)即为秘密密钥。,Diffie-Hellman密钥交换,Bob和Alice都不关心最终的密钥到底是什么 Bob和Alice相互之间都不分享他们各自的保密数 攻击者能够得到g、p以及值ga mod p和gb mod p，而得到k的唯一办法是计算出a和b，这等价于求解离散对数问题,Diffie-Hellman的参数选择,(1) 素数p必须要非常大(多于300个十进制数位)。 (2) 素数p的选择必须要使得p1具有至少一个大的素因子(多于60个十进制数位)。 (3) 生成元必须要从群中选择。 (4) Alice和Bob算出对称密钥后，必须立即销毁x 和 y。

50、x 和 y的值只能使用一次,2 中间人攻击 Diffie-Hellman密钥交换容易遭受中间人攻击： (1) Alice发送公开值(a和p)给Bob，攻击者Carol截获这些值并把自己产生的公开值发送给Bob。 (2) Bob发送公开值给Alice，Carol截获它然后把自己的公开值发送给Alice。 (3) Alice和Carol计算出二人之间的共享密钥k1。,(4) Bob和Carol计算出另外一对共享密钥k2。 造成中间人攻击的原因是Diffie-Hellman密钥交换不认证对方，没有对公钥的合法性进行验证，利用数字签名可以挫败中间人攻击。,3 认证的Diffie-Hellman密钥交换

51、 密钥交换双方通过数字签名和公钥证书相互认证可以挫败中间人攻击。在密钥交换之前，密钥交换的双方Alice和Bob各自拥有公钥/私钥对和公开密钥证书。下面是Alice和Bob产生共享秘密密钥的过程： (1) Alice产生随机数x并发送给Bob。,(2) Bob产生随机数y并根据Diffie-Hellman协议计算出 共享秘密密钥k，然后Bob对x、y签名并用k加密签名，最后把加密的签名和y一起发送给Alice。 (3) Alice计算出k，用k解密Bob发送给他的消息并验证Bob的签名。验证后对x、y签名并用k加密签名后发送给Bob。 (4) Bob解密消息并验证Alice的签名。,公钥密码算

52、法解决的问题,为什么需要公钥密码算法呢，它可解决以下问题 密钥分配 密码系统密钥管理问题 数字签名问题,Thank You !,第二章 密码学基础,目录,2.5公钥密码体制解决的问题 2.6 混合密码体制（数字签名） 2.7 不可逆加密体制（散列函数） 2.8 数字签名,2.5 公钥密码体制解决的问题,对称密码体制已经能够对信息进行加密，为什么还需要公钥密码体制呢？,公钥密码体制仅仅比对称密钥密码体制多用了一个密钥而已吗，两个密钥好在哪里呢？,思考,本节提纲,密钥分配 密码系统密钥管理问题 数字签名问题,2.5.1 密钥分配,用密钥K加密的密文,生成密钥K,攻击者,接收方B,发送方A,明文可能

53、被窃听,信息的明文,信息是否安全了呢,密文加密后可防止被窃听,发送方生成密钥加密明文,问题：密钥K可能被窃取,用密钥K加密的密文,密钥K（明文形式）,生成密钥K,攻击者,接收方B,发送方A,问题：密钥可能被窃取,改进第一步：接收方生成密钥,改进传递加密信息的过程（第一步）,用密钥K加密的密文,密钥K（明文形式）,生成密钥K,攻击者,接收方B,发送方A,窃取密钥为了解密,使发送方和攻击者获取密钥的目的不同。,获得密钥为了加密,改进第二步：接收方生成公钥,用公钥KUB加密的密文,公钥KUB:明文形式,生成公钥KUB和私钥KRB,攻击者,接收方B,发送方A,公钥被窃取也不能解密,总结,解决密钥分配问

54、题的关键有两点： 第一，线路上传输的必须是公钥； 第二，这个公钥必须是接收方的。 提示：如果A、B双方需要使用公钥加密算法相互发送加密的信息给对方，则需要两对公/私钥，即A用B的公钥加密信息发送给B，B用A的公钥加密信息发送给A。,这样，发送方用接收方的公钥加密信息，接收方用该公钥对应的私钥解密信息，攻击者即使截获公钥也不能解密信息，这样就初步解决了密钥在分发过程中可能被窃取的问题。 但要防止接收方的公钥被假冒 即攻击者也生成一对公私钥，然后把自己的公钥Ku冒充接收方B的公钥Ku发给发送方，发送方没有察觉，于是用该假冒的公钥Ku加密信息，攻击者就能用其对应的私钥Kr解密该信息了。,要防止攻击者

55、假冒公钥,攻击者假冒公钥,用公钥KUB加密的密文,假冒的公钥KUB,生成公钥KUB和私钥KRB,攻击者,接收方B,发送方A,生成公钥KUB和私钥KRB,窃取KUB加密的密文,本节提纲,密钥分配 密码系统密钥管理问题 数字签名问题,对称密码系统需要的密钥数,思考：在一个密码系统中，用户通常不止A和B两个人，有时候有几千人之间要相互发送加密信息，能否使用对称密钥进行操作呢？ 假设A要与两个人（B和C）安全通信，A能否用同一个密钥处理与B和与C的消息？ 当然，这是不行的，否则怎么保证B不会打开A给C的信，C不会打开A给B的信？,对称密码系统需要的密钥数,因此，A为了和两个人安全通信，必须使用两个密钥

56、（A-B与A-C），如果B要与C通信，则要另一个密钥（B-C），因此三方通信的话需要3个密钥。 对称密码系统有n人需要安全通信时，这n人中两两之间需要一个密钥，需要的密钥数是： 密钥数与参与通信人数的平方成正比,公钥密码系统需要的密钥数,采用公钥密码系统，假设A要与n个人进行安全通信，他只需把他的公钥发布出去，让这n人知道就可以了。 也就是说，A与n人之间安全通信，只需要一对密钥，同样，B与n人之间安全通信，也只需要一对密钥。 对于公钥密码系统，有n人之间需要相互安全通信时，只需要n对密钥即可，密钥量大大减少。 这n对密钥中的私钥由用户自己保存，公钥由专门的公钥管理机构保管和分发。,两种系统密

57、钥管理的比较,公钥密码系统所需管理的密钥数（n对）比对称密码系统所需的密钥数（n2个）大大减少 对称密码系统和公钥密码系统都需要一个密钥分配中心（KDC）。因此，不要误认为公钥密码技术使得密钥管理非常简单，事实上，仍需要一个代理中心。只是它需要管理的密钥可以大大减少,本节提纲,密钥分配 密码系统密钥管理问题 数字签名问题,2.5.3 数字签名问题,对于公钥密码算法来说，一般的加密机制是： 下面考虑另外一种机制： 这个机制有什么用呢？因为A的公钥是公开的，任何人都可以访问，因此任何人都可以用其解密A加密的信息，从而无法实现保密性。,如果A是发送方，B是接收方，则A用B的公钥加密信息，并将其发送给

58、B,如果A是发送方，B是接收方，则A用A的私钥加密信息，并将其发送给B,数字签名的基本原理,实现消息认证,A用自己的私钥加密信息，不是为了保密消息的内容，而是另有用途。因为接收方B（可能是多方）收到用A的私钥加密的信息，就可以用A的公钥解密，从而访问明文。如果解密成功，则B可以断定这个消息是A发来的。 因为，用A的私钥加密的信息只能用A的公钥解密，反过来说，用A的公钥能解密成功就证明消息一定是用A的私钥加密的。而A的私钥只有A自己知道，别人不可能冒充A用A的私钥加密信息，所以，这个消息一定是A发来的。,实现不可抵赖性,另外，如果今后发生争议，A也无法否认自己发了消息，因为B可以拿出加密信息，用

59、A 的公钥解密，从而证明这个消息是A发来的。这就是数字签名，它可以实现不可抵赖性的安全需求。,总结：数字签名的作用,消息认证：证实某个消息确实是某用户发出的。 实现不可抵赖性：消息的发送方不能否认他曾经发过该消息。 完整性保证：如果消息能够用公钥解密成功，还可确信消息在传输过程中没有被篡改过。,2.5公钥密码体制解决的问题 2.6 混合密码体制（数字信封） 2.7 不可逆加密体制（散列函数） 2.8 数字签名,目录,公钥密码体制的优缺点,虽然公钥密码体制与对称密码体制相比有很多优点，比如解决了对称密码体制中的很多问题，但它并不能取代对称密码体制，因为公钥密码体制存在一个严重的缺点，就是加、解密速度很慢,例如：512比特模数的RSA算法与DES算法相比，用软件实现的话RSA大约比DES慢1000倍，用硬件实现的话RSA大约比DES慢1500倍,对称密钥加密与公钥加密比较,数字信封（混合密码体制）,数字信封用对称密码体制的密钥加密明文，而用公钥密码