9.1 对称加密体制-DES
• • • 教材5.3 密码学基本原理 6.3 加密技术 p134 DES简介 – 第一个也是最重要的现代对称加密算法。 1977.1 美国国家标准局，非国家安全级保 密数据，用于银行保护资金转帐安全。 5 年+3*5使用期 – 分组密码 每一分组称为一个消息 – M=C={0,1}64 K={0,1}56
9.2 公钥密码体制
• 公钥密码体制是密码 史上一次革命。
– 编码系统基于数学中的单向陷门函数 – 采用了两个不同的密钥，对在公开网络上进 行保密通信、密钥分配、数字签名和认证有 深远影响。
内容 – 公钥密码体制的基本原理 – RSA算法 重点
9.2 .1 公钥密码体制基本原理
• 对称密码体制的一个缺点：双双如何建立会密 钥话；密钥分配成本高。尤其是对公开网络的 电子商务安全应用。 • 1976年，Diffie 和Hellman提出：密码学利用 NP复杂性理论；陷门单向函数 – 单向函数：一个函数f 对定义域上任意一个x, f(x)容易计算；但对f值域上的任意y, f-1(y)都 在计算上不可行。 – 陷门单向函数：单向函数f(x)，如果进一步 给定某些辅助信息（如解密密钥），计算 f-1(y)又变得容易。
• • • • •
9.1.2 DES的核心
• S盒的非线性对DES的安全非常重要
– – – 代换密码是非线性的，移位密码仿射密码线性 线性密码减小密钥空间，对差分分析的脆弱 例差分分析攻击仿射密码
•
• • •
DES的安全性
密钥长度较短： 穷举（强力）测试 利用已知明文和密文消息对 解决方法：不同密钥加密-解密-加密三重DES方案 DES的短密钥弱点90 年代变明显： – 1998.7.15 250,000 $,构造DES解密高手，56个小时成 功找到密码。
9.2.1 公钥密码体制基本原理
• 可信单向函数举例： – 假设n是两个大素数p和q 的乘积，分解n 是 一个非常困难的问题（NP-完全问题）。 – 设b是一个正整数，定义函数f: ZnZn, f(x)=x b mod n , f是一个单向函数。但知道n 的因子是p或q时，计算f-1是容易，因而f是 陷门单向函数。 – 秘密的陷门被嵌在单向函数求逆问题中。这 个陷门信息就是私人密钥。
9.1.1 数据加密标准-DES
DES算法总描述：
1. 2. 对输入分组进行固定的初始置换IP 将下面的运算迭代16轮 Li= R i-1 R i= L i-1 f(R i-1, Ki ) 16轮迭代结果输入到IP的逆置换。 Fesitel密码
ki
3.
9.1.1 数据加密标准DES
• DES-2（核心）：16轮迭代，一轮迭代过程如下图： L i –1(32比特) R i –1(32比特) 扩展运算E 48比特寄存器 子密钥Ki异或
9.2.2 RSA算法
• 1978年，Rivest Shamir和Adleman 三人最早 实现Diffie和 Hellman的想法。 • RSA算法安全： 利用陷门单向函数的一种可逆 模指数运算，安全性基于大整数分解因子的困 难性。
9.2.2 RSA算法-描述
• 建立RSA密码体制的过程 1. 选择两个大素数p ,q 2. 计算乘积n=pq 和(n) = (p-1)(q-1) 3. 选择大于1小于(n) 的随机数e,使得gcd(e, (n) )=1 4. 计算d 使得 de=1 mod((n) ) 5. 对每一个密钥k=(n,p,q,d,e),定义加密变换为： Ek(x)=xe mod n, 解密变换为：Dk(x)=yd mod n, 这里x,yZn; 6. 以{e,n}为公开密钥， {p,q,d}为私有密钥 。
E盒扩展运算
E
32 4 12 16 20 24 28
1 5 13 17 21 25 29
2 6 14 18 22 26 30
3 7 15 19 23 27 31
4 8 16 20 24 28 32
5 9 17 21 25 29 1
S1 ，S2…S8盒选择函数
行/列
0
14
1
4
2
13
3
1
4
2
5
15
6
9.1.1 数据加密标准DES
• F函数-1:扩展运算E: P28 E表， – 标出比特位的读出顺序，其中16位被读了两次（32-48） • F函数-2：与子密钥（Ki 48位）的异或运算 • F函数-3：选择压缩运算(S), P29 8个S盒（4*16） – 48位被分成8组,每组6位 ，每组对应一个S盒， – 1，6 位确定在S盒中的行数，2,3,4,5确定列数，根据 行列位置在S盒中选取给该位置对应的数字（0-15）， 得到4位的二元组.例子 • F函数-4：置换表P
11
7
8
8
3
9
10
10
6
11
12
12
5
13
9
14
0
15
7
0
s1
1
2 3
0
4 5
15
1 12
7
14 8
4
8 2
14
13 4
2
6 9
13
2 1
1
11 7
10
15 56Βιβλιοθήκη 12 11129 3
11
7 14
9
3 10
5
10 0
3
5 6
8
0 13
S盒运算举例
假设r i-1经过扩展运算，并与Ki异或得到48位二进制数 ， 分为八组：011011 110110 111000 010010 000011 010101 110011 110110输入8个S盒。 第一组011011 对应S 盒S1 1、6位组成二进制数：01 -1 确定在S1中行数1 2 3 4 5位 1101-13 确定列数13 在S1盒1行13列的数字是5，换为二进制4位：0101。 注意：所有S盒中的数字都小于等于15，相当于4位二 进制数（15-1111），实现6位（位置：行 列）向4位内 容的转换

F 48比特寄存器 选择压缩运算S 32比特寄存器 置换运算P
(48比特)
R i = Li-1 F(Ri-1, Ki )
轮函数
L i = Ri-1
L i(32比特)

R i (32比特)
9.1.1 数据加密标准-DES
DES的核心：消息的随机非线性分布
• 第i轮, f(R i-1, Ki )做下面两个子运算 – Ri-1（32b）扩展置换运算(48b) 异或 ki（56b）收缩置换运算（48b） – 8个代换盒（S盒）， S盒非线性置换函数 • 8个S盒 （8*6b 8*4b） – 6b地址（1 6b 行 2 3 4 5b 列 ） S盒该位置数 字数字4b 。例 第一组011011 对应：S 盒S1第一行 13列的数字 – S盒 4行*16列 每行是0-15的一个排列 • S盒的非线性对DES的安全非常重要