经典密码基础及密钥管理

1、计算机网络安全计算机网络安全主讲：周艺华Email:高校信息安全专业系列课程高校信息安全专业系列课程计算机网络安全计算机网络安全 第四章第四章 经典密码基础经典密码基础4.1 概述概述基本概念基本概念密码学：密码学：研究密码技术的学科。密码学包含两个分支：密码编码学和密码分析学。密码编码学：密码编码学：主要研究如何对信息进行编码，实现对信息进行隐藏的技术。密码分析学：密码分析学：主要研究加密消息的破译，在未知密钥的情况下从密文推出明文或密钥的技术。4.1 概述概述2.2.基本术语基本术语明文（明文（Message）：）：加密输入的原始信息，即信息的原始形式。通常用m或p表示。密文（密文（Cry

2、pto Message）：）：明文经加密变换后的结果，即信息被加密处理后的形式，通常用c表示。加密算法（加密算法（ Encryption Algorithm）：）：将明文变换为密文的变换函数，通常用E表示。解密算法（解密算法（ Encryption Algorithm） ：将密文恢复将密文恢复为明文的变换函数，通常用为明文的变换函数，通常用D表示表示。4.1 概述概述加密密钥（加密密钥（Encryption Key）：）：用于在加密过程中使用的密钥，称为加密密钥。常用K表示。解密密钥（解密密钥（Decryption Key）：）：用于在解密过程中使用的密钥，称为解密密钥。常用K表示。私有密钥（

3、私有密钥（Private Key）：）：用于个人使用的密钥。常用SK表示。公开密钥（公开密钥（Public Key）：）：其密钥是公开的，无论什么人均可拥有。常用PK表示。)()(21CDMMECKK4.1 概述概述3.3.基本密码通信系统基本密码通信系统加密器)(1MECK解密器)(2CDMK密钥产生1K密钥产生2K非法入侵者密码分析明文M接收者MMC4.1 概述概述说明：说明：合法接收者：可得到攻击者:利用其选定的函数H和密钥 K3对截获的密文进行变换得：一般MM，若M=M则攻击者破译成功。MMEDCDMKKK)()(122)(3CHMK在对称密码体制下，加密和解密用相同的密钥。由于加密和

4、解密密钥相同，所以密钥不能公开，所以又称为秘密密钥密码体制。在非对称密码体制下，加密和解密用不同的密钥，所以又称为双密钥体制，由于加密和解密是用4.密码体制分类密码体制分类 以密钥为标准的划分：对称密码体制和非对称密码体制。以密钥为标准的划分：对称密码体制和非对称密码体制。4.1 概述概述不同的密钥，且加密密钥是公开的，所以又称为公开密钥体制。 对称密码体制的优点：对称密码体制的优点：加解密速度快，易于硬件实现，密钥相对较短 对称密码体制的缺点：对称密码体制的缺点： 1）密钥的秘密分发问题； 2）密钥分发的复杂性非常高； 3）数字签名困难问题。4.1 概述概述非对称密码体制的缺点：非对称密码体

5、制的缺点：加密速度慢，同等安全强度下密钥的位数要多一些。非对称密码体制的优点：非对称密码体制的优点：1）密钥管理简单；2）密钥分发简单；3）可以实现数字签名。 通常在网络中加密普遍采用对称密码体制和非对称密码体制结合在一起使用。4.2 最基本的加密算法最基本的加密算法 1.替代密码替代密码其原理是用一些符号代替明文的一些符号。4.2 最基本的加密算法最基本的加密算法4.2 最基本的加密算法最基本的加密算法2. 置换密码置换密码其原理是按照某一规则重新排列信息中的比特或字符的顺序。例子：假定有一个密钥是TYPE的列换位密码，把明文 can you understand 写成一个如下的44矩阵：按

6、照密钥TYPE所确定的顺序：ynsdnurncodtauea4.2 最基本的加密算法最基本的加密算法 密密 钥钥 T Y P E 顺顺 序序 3 4 2 1 c a n y o u u n d e r s t a n d4.3 对称密码算法对称密码算法4.3.1 4.3.1 数据加密标准数据加密标准DES DES 1.DES 1.DES （data encryption standarddata encryption standard）的历的历史：史：由美国IBM公司研制的数据加密算法，1975年3月17日首次被公布在联邦记录中。1977年1月15日被正式批准并作为美国联邦信息处理标准，即FI

7、PS-46。经1994年1月评估，美国已决定1998年12月以后将不再使用DES。 尽管如此， DES对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值。4.3.1 数据加密标准数据加密标准DES64比特明文DES算法加密64比特密文64比特密钥（含8bit校验位）DES算法基本原理算法基本原理 DES的算法如下图：4.3.1 数据加密标准数据加密标准DES2.DES算法的设计思想算法的设计思想扩散：扩散：是指将密钥和明文的任何一位都影响密文的许是指将密钥和明文的任何一位都影响密文的许多位。通过密钥对密文的影响防止对密钥进行多位。通过密钥对密文的影响防止对密钥进行分段破译，而

8、明文对密文的影响用于隐藏明文分段破译，而明文对密文的影响用于隐藏明文的统计特性。的统计特性。实现方法：重复地使用置换操作。实现方法：重复地使用置换操作。混淆：混淆：是指把密文的统计特性与和密钥之间的依赖关是指把密文的统计特性与和密钥之间的依赖关系尽量复杂化，从而使统计分析攻击不能奏效。系尽量复杂化，从而使统计分析攻击不能奏效。实现方法：采用复杂的替代操作。实现方法：采用复杂的替代操作。4.3.1 数据加密标准数据加密标准DES3.DES算法设计中的基本变换和操作算法设计中的基本变换和操作置换置换(P)：重新排列输入中的比特位置：重新排列输入中的比特位置4.3.1 数据加密标准数据加密标准DES

9、 扩展置换：在置换的同时对输入比特进行扩展扩展置换：在置换的同时对输入比特进行扩展4.3.1 数据加密标准数据加密标准DES选择置换：在置换的同时对输入比特进行压缩。4.3.1 数据加密标准数据加密标准DES循环移位：将输入中的比特进行循环移位循环移位：将输入中的比特进行循环移位作为输出。作为输出。4.3.1 数据加密标准数据加密标准DES交换交换(SW):将输入的左右两部分的比特进行将输入的左右两部分的比特进行互换互换替代：替代：4.3.1 数据加密标准数据加密标准DES4.DES算法的描述算法的描述DES加密算法如下页图所示,由初始置换函数IP，子密钥产生函数Ki，密码函数（完成非线性变换

10、），逆初始置换函数IP-1四部分组成。（1 1）初始置换函数）初始置换函数IPIPDES对64位明文分组进行操作。首先，64位明文分组x经过一个初始置换函数IP，产生64位的输出x0，再将分组x0分成左半部分L0和右半部分R0，即： x0=IP(x)=L0R0 置换表如表2-1所示。此表顺序为从上到下，从左至右。如初始置换把明文的第58位换至第1位，把第50位换至第二位，以此类推。64bit明文输入明文输入IP输出输出32bitL032bitR0L16=R15),(15161516RKFLR),(0101RKFLRL15=R14L1R0),(14151415RKFLRIP-1FFFK1(48b

11、it)K2(48bit)K16(48bit),(11iiiiRKFLR12344.3.1 数据加密标准数据加密标准DES58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7表2-1 IP初始置换4.3.1 数据加密标准数据加密标准DES（2 2）获取子密钥）获取子密钥 DES加密算法的密钥长度为56位

12、，但一般表示为64位，其中，每个第8位用于奇偶校验。在DES加密算法中，将用户提供的64位初始密钥经过一系列的处理得到K1，K2，K16，分别作为116轮运算的16个子密钥。现在来看如何获得这16个子密钥。 首先，将64位密钥去掉8个校验位，用密钥置换PC1置换剩下的56位密钥；再将56位分成前28位C0和后28位D0两部分，即PC1(K56)=C0D0。密钥置换PC-1如表2-2所示。4.3.1 数据加密标准数据加密标准DES表2-2 密钥置换PC157 49 41 33 25 17 91 58 50 42 34 26 1810 2 59 51 43 35 2719 11 3 60 52 4

13、4 3663 55 47 39 31 23 157 62 54 46 38 30 2214 6 61 53 45 37 2921 13 5 28 20 12 4 4.3.1 数据加密标准数据加密标准DES 接下来，根据轮数，这两部分分别循环左移1位或2位。具体每轮移位的位数如表2-3所示。 表2-3 每轮移动的位数 轮次轮次 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 位数位数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1移动后，将两部分合并成56位后通过压缩置换PC2后得到48位子密钥，即Ki=PC-2(CiDi)。压缩置换如表2-4所示。

14、4.3.1 数据加密标准数据加密标准DES表2-4 压缩置换PC2 14 17 11 24 1 53 28 15 6 21 1023 19 12 4 26 816 7 27 20 13 241 52 31 37 47 5530 40 51 45 33 4844 49 39 56 34 5346 42 50 36 29 32图4-4 子密钥产生 56位密钥PC-1C0D0左移左移C1D1PC-2K1左移左移CiDiPC-2Ki左移左移C16D16PC-2K164.3.1 数据加密标准数据加密标准DES（3 3）密码函数）密码函数F F1) 函数F的操作步骤 密码函数F的输入是32比特数据和48比

15、特的子密钥，其操作步骤如图2-5所示。v 扩展置换扩展置换(E)(E)：将数据的右半部分Ri从32位扩展为48位。位选择函数(也称E盒)如表2-5所示。4.3.1 数据加密标准数据加密标准DES图2-5 F(Ri, Ki)计算 Ri1(32比特)E48比特S1S2S3S4S5S6S7S8Ki(48比特)P32比特输出4.3.1 数据加密标准数据加密标准DES表2-5 扩展置换(E) 32 1 2 3 4 54 5 6 7 8 98 9 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 292

16、8 29 30 31 32 14.3.1 数据加密标准数据加密标准DESv异或异或: :扩展后的48位输出E(Ri)与压缩后的48位密钥Ki作异或运算。vS S盒替代盒替代: :将异或得到的48位结果分成八个6位的块，每一块通过对应的一个S盒产生一个4位的输出。八个S盒如表2-6所示。4.3.1 数据加密标准数据加密标准DESS盒的具体置换过程为：某个Si盒的6位输入的第1位和第6位形成一个2位的二进制数(从0-3)，对应表中的某一行；同时，输入的中间4位构成4位二进制数(从0-15)对应表中的某一列(注意：行和列均从0开始计数)。例如，第8个S盒的输入为001011，前后2位形成的二进制数为

17、01，对应第8个S盒的第1行；中间4位为0101，对应同一S盒的第5列。从表2-6中可得S8盒的第1行第5列的数为3，于是就用0011代替原输入001011。4.3.1 数据加密标准数据加密标准DES表 2-6 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 1

18、03 13 4 7 15 2 8 14 12 0 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 94.3.1 数据加密标准数据加密标准DESS3盒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

19、 9 10 1 2 8 5 11 12 4 1513 8 11 5 6 15 0 3 4 7 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 34.3.1 数据加密标准数据

20、加密标准DESS6盒12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 1110 15 4 2 7 12 9 5 6 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

21、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 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 11输入：输入： 001011001011首尾两位01中间四位0101输出结果00114.3.1 数据加密标准数据加密标准DESvP P盒置换：盒置换：将八个S盒的输出连在一起生成一个32位的输出，输出结果再通过置换P产生一个32位的输出即：F(Ri, Ki)。表2-7为P盒置换。至

22、此，密码函数F的操作就完成了。 最后，将P盒置换的结果与最初的64位分组的左半部分异或，然后左、右半部分交换，接着开始下一轮计算。4.3.1 数据加密标准数据加密标准DES 表2-7 P盒置换 16 7 20 2129 12 28 171 15 23 265 18 31 102 8 24 1432 27 3 919 13 30 622 11 4 254.3.1 数据加密标准数据加密标准DES2) 2) 函数函数F F的设计的设计函数F是DES加密的核心，它依赖于S盒的设计。这也适用于其它的对称分组加密算法。v F F的设计准则。的设计准则。非线性：输入和输出之间不存在任何线性关系或近似线性关系

23、，避免攻击者用线性函数来逼进F的设计，从而推导出密钥或明文内容。严格雪崩准则(SAC)：算法具有良好的雪崩效应，输入当中的一个比特发生变化都应当使输出产生尽可能多的比特变化。4.3.1 数据加密标准数据加密标准DES比特独立准则(BIC)：BIC的意思是当单个输入比特位i发生变化时，输出比特位j,k的变化应当互相独立，且对任意的i,j,k均应成立。4.3.1 数据加密标准数据加密标准DES（4 4）逆初始置换函数）逆初始置换函数IPIP-1-1 逆初始置换是初始置换的逆变换。对L0和R0进行16轮完全相同的运算后，将得到的两部分数据合在一起，经过一个逆初始置换函数置换函数就可得到64位的密文c

24、，即： c=IP-1(R16L16) 表2-8列出了该变换。4.3.1 数据加密标准数据加密标准DES表2-8 逆初始置 换IP-140 8 48 16 56 24 64 3239 7 47 15 55 23 63 3138 6 46 14 54 22 62 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 254.3.1 数据加密标准数据加密标准DES5. DES工作模式工作模式 DES密码算法提供一种对明文分组进行加密运算的

25、手段，在实际应用中（如对大块数据进行加密等），DES算法作为一种基本构件，采用不同的操作方式或组合方式才能真正起到保护数据的作用。DES主要有四种工作模式：电子密码本(ECB)、密文分组链接(CBC)、密文反馈(CFB)和输出反馈(OFB)。这四种工作模式同样适用于其它分组密码。 (1) (1) 电子密码本电子密码本ECB(Electronic Codebook)ECB(Electronic Codebook)模式模式 4.3.1 数据加密标准数据加密标准DES最简单的方式最简单的方式 将明文划分为定长分组，用同一密钥分别对各个分将明文划分为定长分组，用同一密钥分别对各个分组加密组加密 解密过

26、程类似解密过程类似P1P2P3C1C2C3DESKDESKDESK图26 电子密码本ECB模式4.3.1 数据加密标准数据加密标准DES特点特点 简单简单缺点：不够安全缺点：不够安全相同的明文分组将产生相同的密文分组相同的明文分组将产生相同的密文分组如果明文结构化很强（如明文分组重复出现），密码如果明文结构化很强（如明文分组重复出现），密码分析员就可以利用这种统计规律进行攻击和篡改分析员就可以利用这种统计规律进行攻击和篡改适用于加密少量的数据适用于加密少量的数据因为明文到密文的映射是固定的，类似于一个大的电因为明文到密文的映射是固定的，类似于一个大的电子密码本（各种可能明文到密文的映射），因此

27、叫电子密码本（各种可能明文到密文的映射），因此叫电子密码本方式。子密码本方式。4.3.1 数据加密标准数据加密标准DES(2) (2) 密文分组链接密文分组链接CBC(Ciper Block Chaining)CBC(Ciper Block Chaining)模模式式原理：原理： 将明文分组序列的处理过程连接起来 将前一个分组的处理结果引入到当前分组的计算过程，目的隐藏明文的统计特性方法方法将当前明文分组与前一个密文分组异或后，再进行加密4.3.1 数据加密标准数据加密标准DESC1C2C3P1P2P3DESKDESKKDESIV图27 密文分组链接CBC模式（加密）4.3.1 数据加密标准数

28、据加密标准DESP1P2P3C1C2C3图28 密文分组链接CBC模式（解密）DESKIVDESKDESK特点：特点： 隐藏明文的结构和统计特征 适用于长报文的加密4.3.1 数据加密标准数据加密标准DES(3) (3) 密文反馈密文反馈CFB(Ciper FeedBack)CFB(Ciper FeedBack)模式模式（如图（如图2 29 9）原理：将分组密码用于构成流密码原理：将分组密码用于构成流密码 一次加密一个单位（若干比特或字节）一次加密一个单位（若干比特或字节）(4) (4) 输出反馈输出反馈OFB(Output FeedBack)OFB(Output FeedBack)模式模式（

29、如图（如图2 21010）原理：与原理：与CFBCFB类似，差异在于反馈点不同，类似，差异在于反馈点不同，反馈的内容与输入的明文无关。反馈的内容与输入的明文无关。4.3.1 数据加密标准数据加密标准DES64PB164jjCB1IVj64jj64jj64jj64jjPB2CB2PB3CB3DESKDESKDESKjjjjj64移位寄存器图29 密文反馈CFB模式4.3.1 数据加密标准数据加密标准DES64PB164jjCB1IVj64jj64jj64jj64jjPB2CB2PB3CB3DESKDESKDESKjjjjj64移位寄存器图210 输出反馈OFB模式4.3.1 数据加密标准数据加密

30、标准DES6. 多重多重DES（1 1）二重）二重DESDES二重DES是多重使用DES时最简单的形式，如图211所示。其中明文为P，两个加密密钥为K1和K2，密文为：解密时，以相反顺序使用两个密钥：21 KKCEEP12 KKPDDC4.3.1 数据加密标准数据加密标准DES图图211 二重二重DES4.3.1 数据加密标准数据加密标准DES安全性：安全性：二重及多重二重及多重DESDES的等价问题？的等价问题？213 KKKEEPEP3K1992年证明使用二重DES产生的映射不会等价于单重DES加密。4.3.1 数据加密标准数据加密标准DES中途相遇攻击问题：中途相遇攻击问题：如果有：那么

31、：21 KKCEEP12 KKXEPDC在实施中途相遇攻击时，如果已知两个明文密文对，则找到正确密钥的概率为1-2-16。中途相遇攻击中途相遇攻击. .12 KKXEPDC)(1PEK1K2K)(2CDK4.3.1 数据加密标准数据加密标准DES(2)(2)两个密钥的三重两个密钥的三重DESDES抵抗中途相遇攻击的一种方法是使用3个不同的密钥做3次加密，从而可使已知明文攻击的代价增加到2112。但密钥长度增加到563=168比特。一种实用的方法是仅使用两个密钥做3次加密，实现方式为加密解密加密，简记为EDE( encryptdecryptencrypt)，见图212，即：此方案已在密钥管理标准

32、ANS X.917和ISO 8732中被采用。121 KKKCEDEP4.3.1 数据加密标准数据加密标准DES图图2-12 2-12 两个密钥的三重两个密钥的三重DESDES4.3.1 数据加密标准数据加密标准DES三个密钥的三重DES密钥长度为168比特，加密方式为三个密钥的三重DES已在因特网的许多应用（如PGP和S/MIME）中被采用。(3) (3) 三个密钥的三重三个密钥的三重DESDES321 KKKCEDEP4.4 非对称密码算法非对称密码算法4.4.1 4.4.1 概述概述 非对称密钥体制的概念是由Stanford大学的研究人员Diffie与Hellman于1976年在其密码学

33、的新方向中提出的。在这种体制中，采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为公开密钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为私有密钥，用于解密。因为加密是公开的，又称公开密钥体制。 4.4.1 4.4.1 概述概述1.非对称密码体制（公开密钥体制）产生的原因密钥管理问题密钥管理问题 怎样得到通信密钥？ N个人相互保密通信，需要保管大量的密钥：网络中共有密钥N(N-1)/24.4.1 4.4.1 概述概述2.公开密钥体制的特点公钥密码算法的基本工具是数学函数，而不是替代和置换。加密与解密两个密钥是不同的。仅知道加密算法和加密密钥的情况下，要推断解密密钥在计算上是

34、不可行的。数字签名问题考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。4.4.1 4.4.1 概述概述3.公开密钥体制的基本应用（1）基于公开密钥的保密通信Alice的公钥Joy明文输入 加密算法，如RSA传输密文解密算法明文输出Alice的私钥Bob的公钥环TedAliceMike4.4.1 4.4.1 概述概述（2）基于公开密钥的鉴别/认证Bob的公钥Joy明文输入 加密算法，如RSA传输密文解密算法明文输出Bob的私钥Alice的公钥环TedBobMike4.4.2 RSA算法算法Whitefield Diffie和Martin Hellman 于1976年提出了

35、公钥密码系统的思想，然而他们并没有给出一个实用的公钥密码系统。Diffie-Hellman的文章发表两年后，MIT的Ronald Rivist、Adi Shamir和Len Adlemar开发出了第一个公钥密码体制。RSA密码算法的思想：基于大整数因子分解的困难性，即求一对大素数的乘积很容易，但要对这个乘积进行因式分解则是几千年来数论专家的一道难题。4.4.2 RSA算法算法1.算法描述算法描述（1 1）密钥的产生）密钥的产生 生成两个保密的大素数p和q。 (不能公开） 计算这两个素数的乘积n=pq。（可以公开）计算小于n并且与n互素的整数的个数，即欧拉函数(n)=(p-1)(q-1) 。选取

36、一个随机数e，且1e(n)，并且e和(n)互素，即gcd(e,(n)=1。 （可以公开）计算d，满足de1 mod (n),即d是e在模(n)下的乘法逆元，因e与(n)互素，由模运算可知，它的乘法逆元一定存在。 （不能公开）保密d、p和q，PKe,n,SKd,n。4.4.2 RSA算法算法（2 2）加密）加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n。然后对每个明文分组m，作加密运算： c=me mod n（3 3）解密）解密对密文分组的解密运算为： m=cd mod n4.4.2 RSA算法算法2.RSA的安全性的安全性RSA的安全性是基于分解大整

37、数的困难性假定。如果RSA的模数n被成功地分解为pq，则立即获得(n)=(p-1)(q-1)，从而能够确定e模(n)的乘法逆元d，即de-1 mod (n)，因此攻击成功。在对大数进行因数分解所花的时间上。一个b位的二进制的数n的因数分解大约需要机器周期数为： expln(n)ln(ln(n)1/2 若机器周期为1s,则b为不同的数值时分解n=2b所需的时间为： b(bit)100200300500750100030秒秒3天天9年年1兆年兆年2*109年年6*1015年年4.4.2 RSA算法算法随着人类计算能力和分解算法的不断提高，原来被认为是不可能分解的大数已被成功分解。例如RSA-129

38、（即n为129位十进制数，大约428个比特）已在网络上通过分布式计算历时8个月于1994年4月被成功分解，RSA-130 已于1996年4月被成功分解。因此，在使用RSA算法时对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。4.4.2 RSA算法算法2.RSA的性能的性能软件实现：比DES慢1000倍硬件实现：比DES慢100倍安全强度：DES密钥长度（密钥长度（bit)RSA密钥长度（密钥长度（bit）56384645121121792表211 同等强度的DES与RSA比较2.2.算法密钥生成算法密钥生成选取一个素数p计

39、算一个 的一个随机乘法生成元g随机选取一个xp计算4.4.3 离散（离散（DL）对数算法）对数算法1.ElGamal1.ElGamal公钥算法概述公钥算法概述1985年，由ElGamal提出可用于加密和数字签名设计上的安全性基础依赖于计算有限域上离散对数的困难性*pZpgyxmod4.4.3 离散（离散（DL）对数算法）对数算法p,g,y作为算法的加密密钥（公钥）x作为算法的解密密钥（私钥）pgckmod1pmyckmod2pccmxmod/123.3.加密加密对明文m进行以下计算：选择一个随机整数k其结果c1,c2就是m对应的密文c，密文c的长度比明文增加了一倍4.4.解密解密对密文c1,c

40、2计算4.4.3 离散（离散（DL）对数算法）对数算法验证如下（mod p）)(mod/)()/(/12pmgmggmycckxkxxkkx4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法1.椭圆曲线密码体制概述椭圆曲线密码体制概述ECCElliptic Curve Cryptography1985年Koblitz, Miller分别提出对RSA的地位提出了挑战采用更小的密钥长度取得与RSA相同的安全性更小的处理开销数学描述复杂、深奥4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法ECC密钥长度（bit)RSA密钥长度（bit)破解时间（MIPS年）RSA/ECC密钥尺寸比例1

41、065121045：1160102410117：12102048102010：160021000107835：1表表212 RSA/ECC等价强度的密钥尺寸大小比较等价强度的密钥尺寸大小比较4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法2.椭圆曲线的概念及分类椭圆曲线的概念及分类椭圆曲线不是椭圆，而是一个平面上的三次曲线， 是人们在研究如何计算椭圆的弧长时遇到的，因为这些曲线方程类似于计算一个椭圆周长的方程 ，所以称为椭圆曲线。 通常，椭圆曲线是一个具有两个变元x和y的三次方程，它是满足：的所有点（x，y）的集合，外加一个无穷元点O(认为其y坐标无穷大)。其形状如图216所示edxc

42、xxbyaxyy2324.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法图216 椭圆曲线的两个例子4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法（1 1）实数域上的椭圆曲线）实数域上的椭圆曲线实数域上的椭圆曲线是对于固定的a,b值，满足形如方程：的所有点（x，y）的集合，外加一个无穷远点O。其中a，b是实数，且满足(确保曲线是光滑的，即所有的点都没有两个或两个以上的切线)，x和y在实数域取值。027432babaxxy324.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法（2 2）有限域）有限域F Fp p上的椭圆曲线上的椭圆曲线 有限域F Fp p上的椭圆曲线是对于固

43、定的a,b值，满足形如方程：的所有点（x，y）的集合，外加一个无穷远点O。其中a，b，x，y均在有限域Fp，即0,p-1上取值，且满足 ，p是素数（大于3）。这类椭圆曲线常用Ep（a，b）表示。 很显然，此类椭圆曲线只有有限个点N（称为椭圆曲线的阶，包括无穷远点），N越大，安全性越高。 此类椭圆曲线一般适宜用软件实现。 027432ba)(mod32pbaxxy4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法y2=x3+x+1 (mod 23)的图像4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法（3 3）有限域）有限域上的椭圆曲线上的椭圆曲线 有限域 上的椭圆曲线是对于固定的

44、a,b值，满足形如方程：的所有点（x，y）的集合，外加一个无穷远点O。其中a，b，x，y均在有限域 上取值，且满足 ，这类椭圆曲线常用 表示。 此类椭圆曲线只有有限个点。 域 上的元素是m位的二进制串，因此，此类椭圆曲线一般适宜用硬件实现。 027432babaxxxyy32mF2mF2mF2),(2baEmmF24.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法3.椭圆曲线的加法规则椭圆曲线的加法规则（椭圆曲线上点与点之间的关系）只要非负整数a和b，满足椭圆曲线上的点（x，y）与一个称为无穷远点的O组成的群具有重要的“加法规则”属性，即对于椭圆曲线上的任意两个点：P1=(x1,y1)和

45、P2(x2,y2),存在第三个点P3=(x3,y3)=P1+P2也在该椭圆曲线上。0)(mod27432pba加法规则： O是加法单位元（additive identity)，即O= -O；对于一个在椭圆曲线上任何的点P，有P+O=P。三点共线：如果一个椭圆曲线上的三个点处于一条直线上，那么它们的和为O ,如下页左图。4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法加法逆元：它们与曲线在无穷远点（即O点）相交，即),(1yxP 和),(2yxP的加法逆元是因此：有12122121PPPPOPPOOPPP1P24.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法两个不同且不互逆的点相

46、加：如图，显然:yxR (x3, y3)P (x1, y1)Q (x2, y2)ORRRQPORQP即：4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法两个相同的点相加：即沿P点作切线。显然：yxR( x3, y3)P( x1, y1)OPPPRPPP232同里可计算：4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法4.椭圆曲线密码体制椭圆曲线密码体制（1 1）椭圆曲线离散对数问题）椭圆曲线离散对数问题已知椭圆曲线E和基点G，随即选择一个整数k，容易计算Q=kG，但给定Q和G计算k相当困难。（2 2）系统建立和密钥生成）系统建立和密钥生成系统建立（参数生成）系统建立（参数生成）

47、选取一个基域Fp和定义在该域上的椭圆曲线Ep(a,b)及其上的一个拥有素数阶n的点G（xG,yG）,其中有限域Fp，椭圆曲线参数a,b,点G和阶n均是公开参数。4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法密钥的生成密钥的生成 在区间在区间1,n-11,n-1中随机选取一个整数中随机选取一个整数k k作为私钥作为私钥 计算计算Q=kG,Q=kG,即由私钥计算出公钥即由私钥计算出公钥 实体的公开密钥为点实体的公开密钥为点Q,Q,私钥是整数私钥是整数k k。离散对数的难。离散对数的难解性保证了在已知公钥的情况下不能计算出私钥解性保证了在已知公钥的情况下不能计算出私钥k k（3 3）椭圆曲

48、线加）椭圆曲线加/ /解密解密4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法用户用户A A选选n nA A作为私钥，并以作为私钥，并以P PA A=n=nA AG G作为公开钥。作为公开钥。加密：加密：任一用户任一用户B B若想向若想向A A发送消息发送消息m m，应先将，应先将m m编码为椭圆曲线编码为椭圆曲线上的一个点上的一个点P Pm m，然后将，然后将P Pm m看作明文加密成密文消息看作明文加密成密文消息C Cm m。可选取一随机正整数可选取一随机正整数k k，产生以下点对作为密文：，产生以下点对作为密文： ,2121CCCkPPCkGCmAmmAAmAAmAPkGnGkn

49、PkGnkPPCnC12解密：解密：A A解密时解密时, ,以密文点对中的第二个点减去用自己的秘密钥与以密文点对中的第二个点减去用自己的秘密钥与第一个点的倍乘，即：第一个点的倍乘，即：4.4.3 椭圆曲线（椭圆曲线（EC）加密算法）加密算法安全性保证：安全性保证：攻击者若想由攻击者若想由C Cm m得到得到P Pm m，就必须知道，就必须知道n nA A。而要。而要得到得到n nA A，只有通过椭圆曲线上的两个已知点，只有通过椭圆曲线上的两个已知点G G和和P PA A ，这意，这意味着必须求椭圆曲线上的离散对数，因此不可行。味着必须求椭圆曲线上的离散对数，因此不可行。4.4.3 椭圆曲线（椭

50、圆曲线（EC）加密算法）加密算法（4 4）椭圆曲线密码体制的应用：密钥分发）椭圆曲线密码体制的应用：密钥分发例：（略）分发问题体制中难以解决的密钥很好的解决了对称密钥）（因为和钥为各自分别产生的共享密和公开做为私钥，公钥的随机数选择一个小于公开做为私钥，公钥的随机数选择一个小于通信：想与假设ABABBABAABBABBBAAAPnGnnGnnPnPnKPnKBAGnPnnBGnPnnABA)(,:4.5 密钥管理密钥管理1.密钥管理的必要性密钥管理的必要性(1)密钥管理是信息系统安全性的重要因素密钥管理是信息系统安全性的重要因素 信息加密系统的安全性取决于：信息加密系统的安全性取决于： 算法的

51、安全性算法的安全性 密钥使用和管理的安全性。密钥使用和管理的安全性。 算法确定的条件下，保密系统的安全性取决于算法确定的条件下，保密系统的安全性取决于密钥使用和管理的安全性密钥使用和管理的安全性。(2)保护好密钥比保护好算法要容易得多。保护好密钥比保护好算法要容易得多。 算法是公开的，密钥是保密的。算法是公开的，密钥是保密的。(3)可以使用不同的密钥保护不同的秘密。可以使用不同的密钥保护不同的秘密。一个秘密信息的密钥被攻击，不会影响到其他的一个秘密信息的密钥被攻击，不会影响到其他的秘密信息。秘密信息。 4.5.1 密钥管理概述密钥管理概述包括密钥的生成、存储、分配、使用、备份包括密钥的生成、存

52、储、分配、使用、备份/恢恢复、更新、撤销、销毁等。其中复、更新、撤销、销毁等。其中分配分配和和存储存储是最棘是最棘手的问题。手的问题。2.密钥管理的含义密钥管理的含义密钥管理处理从密钥产生到最终销毁的整个过程密钥管理处理从密钥产生到最终销毁的整个过程的有关问题。的有关问题。(1)密钥的生成密钥的生成 好的密钥：好的密钥：应当具有良好的随机性和密码特性，避免应当具有良好的随机性和密码特性，避免弱密钥的出现。弱密钥的出现。 4.5.1 密钥管理概述密钥管理概述 怎样产生好的密钥？怎样产生好的密钥？ 真正随机、等概：如掷硬币、掷骰子、从随机表中真正随机、等概：如掷硬币、掷骰子、从随机表中选取等。选取

53、等。 通过密钥生成器借助某种噪声源（光标或鼠标的位通过密钥生成器借助某种噪声源（光标或鼠标的位置、内存的状态、上次按下的键、声音大小）产生置、内存的状态、上次按下的键、声音大小）产生具有较好统计分布特性的序列，然后再对这些序列具有较好统计分布特性的序列，然后再对这些序列进行各种随机性检验。进行各种随机性检验。 采用密钥揉搓或杂凑技术，将易记的长句子，经单采用密钥揉搓或杂凑技术，将易记的长句子，经单向函数变换成伪随机数串。向函数变换成伪随机数串。4.5.1 密钥管理概述密钥管理概述(2)密钥的安全存储密钥的安全存储（对静态密钥的保护）（对静态密钥的保护） 基于口令的软保护基于口令的软保护基于用户

54、口令，使用对称密钥算法来加密密钥。基于用户口令，使用对称密钥算法来加密密钥。一般步骤为一般步骤为 输入口令输入口令 用用RNG或或PRNG生成一个生成一个“盐值盐值”SALT 用一个混合算法将用一个混合算法将SALT和口令混合在一起，大多数情和口令混合在一起，大多数情况下混合算法的处理结果是一个消息摘要。况下混合算法的处理结果是一个消息摘要。 从上一步的随机输出的结果中选取一定的位数作为密从上一步的随机输出的结果中选取一定的位数作为密钥加密密钥，加密其他密钥。钥加密密钥，加密其他密钥。 扔掉生成的密钥，保护好口令和扔掉生成的密钥，保护好口令和SALT以备解密。以备解密。 引入引入SALT的目的

55、：防止预计算。的目的：防止预计算。4.5.1 密钥管理概述密钥管理概述口令口令混合器混合器密钥加密密钥密钥加密密钥SALTPRNGKEK4.5.1 密钥管理概述密钥管理概述 基于硬件的物理保护基于硬件的物理保护 将密钥存储于与计算机相分离的某种物理设备中，将密钥存储于与计算机相分离的某种物理设备中，以实现密钥的物理隔离保护。以实现密钥的物理隔离保护。实现方式：实现方式：将密钥存储于磁条卡中。将密钥存储于磁条卡中。将密钥存储于带将密钥存储于带ROM芯片的智能卡中。芯片的智能卡中。将密钥存储于专用将密钥存储于专用USB磁盘中。磁盘中。 将密钥分成两部分，一半存入终端，一半存入将密钥分成两部分，一半

56、存入终端，一半存入ROM密钥卡上。密钥卡上。 优点：优点：平常攻击者不能访问到他们，因为他们并不与因特网平常攻击者不能访问到他们，因为他们并不与因特网连接，可以防止远程攻击。连接，可以防止远程攻击。4.5.1 密钥管理概述密钥管理概述这些物理设备本身还可受到口令或这些物理设备本身还可受到口令或PIN的保护，具有的保护，具有防御功能。防御功能。如果有人试图物理地访问其存储空间，设备将自动如果有人试图物理地访问其存储空间，设备将自动销毁。销毁。即使这些物理设备最终也要连接到计算机，并最终即使这些物理设备最终也要连接到计算机，并最终连接到网络，但连接时间较短，不容易收到攻击。连接到网络，但连接时间较

57、短，不容易收到攻击。(3)密钥的更换密钥的更换 密钥的使用时间越长，泄漏的机会越大；一旦泄密钥的使用时间越长，泄漏的机会越大；一旦泄漏，密钥使用越久，损失越大，因此，密钥要定期更漏，密钥使用越久，损失越大，因此，密钥要定期更换。换。4.5.1 密钥管理概述密钥管理概述密钥更换的频率依赖于：密钥更换的频率依赖于： 被保护数据的敏感性；安全性越高，密钥更换越频繁。被保护数据的敏感性；安全性越高，密钥更换越频繁。 被保护数据的有效期：如，密钥加密密钥就无需频繁被保护数据的有效期：如，密钥加密密钥就无需频繁更换，因为他们只是偶尔用作密钥交换。更换，因为他们只是偶尔用作密钥交换。 密钥算法的力量：用密钥

58、算法的力量：用DES算法的系统与用算法的系统与用AES算法的算法的系统相比，密钥应该更换的更频繁。系统相比，密钥应该更换的更频繁。(4)密钥的销毁密钥的销毁 销毁的原因：销毁的原因： 别人可用他来读原来曾用他加密的文件。别人可用他来读原来曾用他加密的文件。 旧密钥有利于分析密码体制旧密钥有利于分析密码体制 销毁的方法销毁的方法4.5.1 密钥管理概述密钥管理概述(5)密钥的吊销密钥的吊销 如果密钥丢失或因其他原因在密钥未过期之前，需如果密钥丢失或因其他原因在密钥未过期之前，需要将它从正常运行使用的集合中除去，称为密钥吊销。要将它从正常运行使用的集合中除去，称为密钥吊销。 采用证书的公钥可以通过

59、公布一个公钥撤销列表来采用证书的公钥可以通过公布一个公钥撤销列表来实现。实现。 用高质量碎纸机粉碎记录密钥的纸张。用高质量碎纸机粉碎记录密钥的纸张。对于硬盘、对于硬盘、EEPROM要进行多次冲写等。要进行多次冲写等。4.5.2 密钥的协商与分发密钥的协商与分发密钥协商密钥协商 1.密钥协商与分发的基本概念密钥协商与分发的基本概念AB协商的结果：参与双方（或多方）都可得到相同的协商的结果：参与双方（或多方）都可得到相同的密钥，任何其他非参与方都不能得到密钥。密钥，任何其他非参与方都不能得到密钥。 是指保密双方（或多方）通过公开信道的通信来共同是指保密双方（或多方）通过公开信道的通信来共同形成秘密

60、密钥的过程。一个密钥协商方案中，密钥的形成秘密密钥的过程。一个密钥协商方案中，密钥的值是某个函数值，其输入是两个（或多个）成员提供。值是某个函数值，其输入是两个（或多个）成员提供。4.5.2 密钥的协商与分发密钥的协商与分发密钥分发密钥分发 ABC是指保密通信中的一方或可信第三方生成并选择秘是指保密通信中的一方或可信第三方生成并选择秘密密钥，然后把该密钥发送给通信参与的其他一方密密钥，然后把该密钥发送给通信参与的其他一方或多方的机制。或多方的机制。4.5.2 密钥的协商与分发密钥的协商与分发 秘密密钥的分发秘密密钥的分发 公开密钥的分发公开密钥的分发2.密钥分发的方式密钥分发的方式3.秘密密钥