1
计算机系统安全
第四讲 密码学
2
一、密码学概述
密码体制,1） 传统密码体制 2） 现代密码体制
传统密码体制：对称密码体制 （ 单钥体制 ）
现代密码体制：非对称密码体制 （ 公钥密码体制, 双
钥体制 ）
按照对明文的处理方式分为：分组密码算法和序列密
码算法 。
分组密码算法：把明文分成等长的组分别加密
序列密码算法：是一个比特一个比特地处理, 用已知
的密钥随机序列与明文按位异或 。
第四章 传统密码学
3
二、加密和解密
第四章 传统密码学
加密 解密明文 M 密文 C 原始明文M
E（ M） =C,D（ C） =M
D（ E（ M）） =M
明文 Plaintext 密文 Cipher text
加密 Encryption 解密 Decryption
密钥 key
4
二、加密和解密
第四章 传统密码学
密码就是一组含有参数 k的变换 E。 设已知信息 m,通
过变换 E得到密文 c。 即 c=Ek(m) 这个过程称之为加密，
参数 k称为密钥。解密算法 D是加密算法 E的逆运算，
解密算法也是含参数 k的变换。
DK（ EK（ M）） =M.
加密 解密明文 M 密文 C 原始明文M
密钥 K 密钥 K
EK（ M） =C DK（ C） =M.
5
二、加密和解密
第四章 传统密码学
DK2 （ EK1（ M）） =M 双钥密码体制
加密 解密明文 M 密文 C 原始明文 M
加密
密钥 K1
解密
密钥 K2
EK1（ M） =C DK2（ C） =M
6
定义, (密码体制）它是一个五元组（ P,C,K,E,D)满足条件：
（ 1） P是可能明文的有限集；（明文空间）
（ 2） C是可能密文的有限集；（密文空间）
（ 3） K是一切可能密钥构成的有限集；（密钥空间）
*（ 4）任意 k∈ K,有一个加密算法 和相应的解密
算法,使得 和
分别为加密解密函数，满足 dk(ek(x))=x,这里 x ∈ P。
二、加密和解密
第四章 传统密码学
Eek?
CPek ?,PCdk ?:Ddk?
7
二、加密和解密
第四章 传统密码学
信源 加密机 解密机 接收者
安全信道
密钥源
窃听者
x y x
k1
加密通信的模型
密钥源
k2不安全信道
密码分析
8
1*.Alice要将明文Ｘ在不安全信道上发给 Bob,设 X=x1
x2… xn,其中 xi ∈ P,Alice用加密算法 ek作 yi=ek(xi) 1≤ i≤
n
结果的密文是 Y=y1y2….y n,在信道上发送，
Bob收到后解密,xi=dk(yi)
得到明文 X=x1 x2… xn,。
2*.加密函数 ek必须是单射函数，就是一对一的函数。
3*.好的密钥算法是唯密钥而保密的。
4*.若 Alice和 Bob在一次通信中使用相同的密钥，那么
这个加密体制为对称的，否则称为非对称的。
二、加密和解密
第四章 传统密码学
9
密码学：对信息进行编码实现隐蔽信息的一门学问。
密码分析学：研究分析破译密码的学问。两者相互对立、促进。
1,常用的密码分析攻击有四类,
加密算法：公开 。 攻击目标：获得密钥 K
? 唯密文攻击 （ ciphertext only attacks） 。
已知：截获部分密文
? 已知明文攻击 （ know plaintext attacks） 。
已知：截获部分密文；若干明文 ——密文对 。
? 选择明文攻击 （ chosen plaintext attacks） 。
已知：截获部分密文；自主选择的明文 ——密文对 。
? 选择密文攻击
暂时接近密码机, 可选择密文串, 并构造出相应的明文 。
三、密码分析
第四章 传统密码学
10
三、密码分析
第四章 传统密码学
2、算法的安全性
密码算法具有不同的安全等级,以下情况可能是安全的
.破译算法的代价大于加密数据的价值
.破译算法所需的时间大于加密数据保密的时间
.用单密钥加密的数据量小于破译算法需要的数据量
Shannon理论：仅当密钥至少和明文一样长时才无条件安全。
如果不论密码分析者有多少密文，都没有足够的信息恢复出
明文，那么这个算法就是无条件保密的，只有一次一密乱码
本，才是无条件安全的 。 所有其它的密码系统在唯密文攻击
中都是可破的 （ 蛮力攻击 ）。
11
三、密码分析
第四章 传统密码学
密码学更关心在计算上不可破译的密码系统。如果一个算法
用（现在或将来）可得到的资源（ 公开数据 ）都不能破译，
这个算法则被认为在计算上是安全的。
可以用不同方式衡量攻击方法的复杂性：
数据复杂性 。 用作攻击输入所需的数据量 。
处理复杂性 。 完成攻击所需要的时间, 这个经常叫做工作因
素 。
存储需求 。 进行攻击所需要的存储量 。
作为一个法则，攻击的复杂性取这三个因数的最小化，有些
攻击包括这三种复杂性的折中：存储需求越大，攻击可能越
快。
12
四、传统密码学
第四章 传统密码学
1、移位法, 将明文字母互相换位，明文的字母不变, 但顺
序被打乱了。 例如,线路加密法
明文以固定的宽度水平写出，密文按垂直方向读出。
明文,COMPUTERSYSTEMSECURITY
COMPU
TERSY
STEMS
ECURI
TY
密文,CTSETOETCYMREUPSMRUYSI
13
四、传统密码学
第四章 传统密码学
2、代替法,代替密码就是明文中每一个字符被替换成密文
中的另外一个字符，代替后的各字母保持原来位置。对密文
进行逆替换就可恢复出明文。有四种类型的代替密码：（ 1）
（ 1）单表（简单）代替密码：就是明文的一个字符用相应
的一个密文字符代替。加密过程中是从明文字母表到密文字
母表的一一映射。例：恺撒（ Caesar)密码。
（ 2）同音代替密码：它与简单代替密码系统相似，唯一的
不同是单个字符明文可以映射成密文的几个字符之一同音代
替的密文并不唯一。
（ 3）多字母组代替密码：字符块被成组加密，例如, ABA”
可能对应, RTQ”,ABB可能对应, SLL”等。例,Playfair密码。
（ 4）多表代替密码：由多个单字母密码构成，每个密钥加
密对应位置的明文。 例：维吉尼亚密码。
14
四、传统密码学
第四章 传统密码学
3、凯撒（ Caesar） 密码
令 26个字母分别对应于 0～ 25,a=1,b=2…… y=25,z=0。
凯撒加密变换实际上是 c≡ (m + k) mod 26
其中 m是明文对应的数据, c是与明文对应的密文数据, k是
加密用的参数, 叫密钥 。 比如明文,data security 对应数据
序列,4,1,20,1,19,5,3,21,18,9,20,25
k=5时, 得密文序列
9,6,25,6,24,10,8,0,23,14,25,4
密文,ifyxjhzwnyd
缺点：容易破解密码 。
15
置换密码：
1*,置换 π的表示：
π＝
2*密钥空间 K很大,|k|=26! ≈ 4× 1026,破译者穷举搜索
是不行的，然而，可由统计的方式破译它。
3*移位密码体制是替换密码体制的一个特例，它仅含 26
个置换做为密钥空间
四、传统密码学
第四章 传统密码学
移位密码：如 凯撒（ Caesar） 密码 。
仿射密码,如果选取 k1,k2两个参数，其中 k1 与 26 互素，
令 c≡(k 1m + k2)mod 26。 这种变换称为仿射变换。
( 0 1 2 3,.23 24 250' 1' 2' 3',.23' 24' 25' )
16
四、传统密码学
第四章 传统密码学
4,Playfair密码（ 英国曾用）
密钥由 25个英文字母（ J与 I相同）组成的 5阶方阵。
每一对明文字母 m1和 m2,都根据下面的 6条规则进行加密 。
（ 1） 明文字母 m1和 m2同行 。 密文是其右边字母 。
（ 2） 明文字母 m1和 m2同列 。 密文是其下边字母 。
（ 3） 明文字母 m1和 m2不同行, 不同列 。 密文是长方形的
另两个顶点 。
（ 4） 明文字母 m1和 m2相同 。 在 m1和 m2之间加一个无效
字母 。
（ 5） 明文有奇数个字母, 末尾加一个无效字母 。
（ 6） I,J看成是相同字母 。
17
四、传统密码学
第四章 传统密码学
例,25个字母组成 5阶方阵如下 （ J与 I相同 ）,
HARPS （ 1） 明文字母 m1和 m2同行 。 密文是其右边字母 。
ICODB （ 3） m1和 m2不同行, 不同列 。 密文是长方形的另两个顶点 。
EFGKL
MNQTU
VWXYZ
例：明文,CO MP UT ER
密文,OD TH MU GH
利用规则,1 3 1 3
18
四、传统密码学
第四章 传统密码学
5,维吉尼亚 （ Vigenere） 密码
典型的多表密码, 即一个明文字母可表示为多个密
文字母 。,
例如：明文为 System,密钥为 dog,加密过程如下：
明文,S y s t e m
密钥,d o g d o g
密文,V m g w r s
在这个例子中, 每三个字母中的第一, 第二, 第三
个字母分别移动 （ mod 26） 3个, 14个和 6个位置 。
19
四、传统密码学
第四章 传统密码学
优点：能抵抗简单的字母频率分析攻击 。
设密钥 k=k1k2… kn,明文 M=m1m2… mn,加密变换
Ek(M)=c1c2… cn。 其中
ci≡( mi + ki) mod 26,i=1,2… n。
多表密码加密算法结果将使得对单表置换用的简单
频率分析方法失效 。
20
四、传统密码学
第四章 传统密码学
6,一次一密密码
一次一密密码, 由 AT&T公司的 Gilbert Vernam在
1917年提出 。 发方和收方各保存一份一次一密乱码
本, 它是一个大的不重复的真随机密钥字母集 。 发
方用乱码本中的某一页密钥加密明文 。 加密方法：
明文字符和乱码本密钥字符的模 26加法 。
每个密钥仅对一个消息使用一次 。 发方对所发的消
息加密, 然后销毁乱码本中用过的一页 。 收方有一
个同样的乱码本, 并依次使用乱码本上的每个密钥
去解密密文的每个字符, 然后销毁乱码本中用过的
一页 。
21
四、传统密码学
第四章 传统密码学
棋盘密码
建立一张表, 使每一个字符对应一数 ξ,η, ξ 是该
字符所在行标号, η 是列标号 。 这样将明文变成形
式为一串数字密文 。 这种密码古代曾广泛利用 。
1 2 3 4 5
1 A B C D E
2 F G H I J K
3 L M N O P
4 Q R S T U
5 V W X Y Z
22
五、密码体制评价
第四章 传统密码学
保密强度,与数据的重要性有关
密钥的长度：安全, 保管, 记忆
算法的复杂度：开销大小
差错的传播性：不应使差错导致通信失败
加密后信息长度的增加程度：
23
六、单表密码分析
第四章 传统密码学
英语 26个字母中, 各字母出现的频率不同而稳
定, 经过大量统计, 可以给出了各字母出现的
频率值 。 英文明文字母按出现概率大小分组表：
1 e >0.1
2 t a o i n s h r 0.05-0.1
3 d l 0.03-0.05
4 c u m w f g y p b 0.01-0.03
5 v k j x q z <0.01
24
六、单表密码分析
第四章 传统密码学
字母, 三字母组合是分析单表密码的有力手段 。
英语单词以 e,s,t,d双结尾的超过一半；以 t,a、
s,w 为起始字母的约为一半 。
某些常用用法也会提供有价值的线索, 如信的开头
写 Dear ； 源程序的某一位置是版权声明；电子资金
传送报头格式 。
单表密码的弱点：明文和密文字母之间的一一代替
关系 。 这使得明文中的一些固有特性和规律 （ 比如
语言的各种统计特性 ） 必然反映到密文中去 。
25
一,DES算法概述
现代与古典密码学采用的基本思想相同：替换与变位 。
古典：算法简单, 长密钥 。
现代：算法复杂 。
P盒和 S盒
数据加密标准
P盒 用 P盒构成的 S盒
P盒 实质上是用硬件实现 变位,改变输入序列
S盒 实质上是用硬件实现若干比特的替换
译
码
器
编
码
器
26
一,DES算法概述
发明人,IBM公司 W,Tuchman 和 C,Meyer 1971-72年研制 。
产生,美国商业部的国家标准局 NBS1973年 5月到 1974年 8月
两次发布通告, 公开征求用于电子计算机的加密算法 。 经评
选从一大批算法中采纳了 IBM的 LUCIFER方案 。
标准化,于 1976年 11月被美国政府采用, DES随后被美国国
家标准局和美国国家标准协会 (American National Standard
Institute,ANSI) 承认 。 1977年 1月以数据加密标准 DES
（ Data Encryption Standard） 的名称正式向社会公布 。 于
1977年 7月 15日生效 。
DES的发展：如衍生出可抗差分分析攻击的变形 DES以及密
钥长度为 128比特的三重 DES等 。
数据加密标准
27
一,DES算法概述
在 1977年, 人们估计要耗资两千万美元才能建成一
个专门计算机用于 DES的解密, 而且需要 12个小时
的破解才能得到结果 。
1997年开始, RSA公司发起了一个称作, 向 DES挑
战, 的竞技赛 。
1997年 1月, 用了 96天时间, 成功地破解了用 DES加
密的一段信息；一年之后, 在第二届赛事上, 这一
记录 41天 ； 1998年 7月,, 第 2-2届 DES挑战赛
（ DES Challenge II-2）, 把破解 DES的时间缩短到了
只需 56个小时；, 第三届 DES 挑战 赛 （ DES
Challenge III）,把破解 DES的时间缩短到了只需 22.5
小时 。
数据加密标准
28
一,DES算法概述
数据加密标准
个人攻
击
小组攻
击
院, 校
网络攻
击
大公司 军事情
报机构
40（ bits） 数周 数日 数小时 数毫秒 数微秒
56 数百年 数十年 数年 数小时 数秒钟
64 数千年 数百年 数十年 数日 数分钟
80 不可能 不可能 不可能 数百年 数百年
128 不可能 不可能 不可能 不可能 数千年
29
一,DES算法概述
数据加密标准
上表中攻击者配有如下计算机资源的攻击能力
攻击者类
型
所配有的计算机资源 每秒处理
的密钥数
个人攻击 1台高性能桌式计算机及
其软件
217-224
小组攻击 16台高性能桌式计算机及
其软件
221-224
院, 校网
络攻击
256台高性能桌式计算机
及其软件
225-228
大公司 配有价值 1百万美元的硬
件
243
军事情报
机构
配有价值 1百万美元的硬
件及先进的攻击技术
255
30
二、数据加密标准 (DES)
数据加密标准
64位码
64位码
初始变换
逆初始变换
乘积变换 16次迭代
明文
密文
输入
输出
IP
IP-1
31
二、数据加密标准 (DES)
数据加密标准
利用传统的换位和置换加密 。 假定信息空间由 {0,1}组成的字
符串, 信息被分成 64比特的块, 密钥是 56比特 。 经过 DES加
密的密文也是 64比特的块 。
明文,m=m1m2… m64 mi = 0,1 i = 1,2,… 64
密钥,k=k1k2… k64 ki = 0,1 i = 1,2,… 64
其中 k8,k16,…, k64是奇偶校验位, 起作用的仅为 56位 。
加密算法, Ek(m) = IP-1·T16·T15…… T1·IP(m)
其中 IP为初始置换, IP-1是 IP的逆, Ti,i = 1,2,… 16是一
系列的变换 。
解密算法, Ek-1 (c) = IP-1·T1·T2…… T16·IP (c)
32
二、数据加密标准 (DES)
数据加密标准
输入（ 64位）
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
输出（ 64位）
初始变换
IP
L0（ 32位） R0（ 32位）
初始变换 IP
33
二、数据加密标准 (DES)
数据加密标准
IP 中各列元素位置号数相差为 8, 相当于将原明文各字节按列写出,
各列比特经过偶采样和奇采样置换后再对各行进行逆序, 将阵中元素
按行读得的结果 。
1 9 17 25 33 41 49 57
2 10 18 26 34 42 50 58
3 11 19 27 35 43 51 59
4 12 20 28 36 44 52 60
5 13 21 29 37 45 53 61
6 14 22 30 38 46 54 62
7 15 23 31 39 47 55 63
8 16 24 32 40 48 56 64
输入 64个二进制位明码文数据区组
m= m1m2… m64
按初始换位表 IP进行换位, 得到区组 B（ 0）,
B（ 0） =b1(0)b2(0)… b64(0)= m58m50… m7记成 L0,R0左右两部分
34
二、数据加密标准 (DES)
数据加密标准
置换码组 输入（ 64位）
40 8 48 16 56 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
输出（ 64位）
逆初始变换
IP-1
逆初始变换
35
二、数据加密标准 (DES)
数据加密标准
逆初始变换。用 IP-1 表示，它和 IP互逆。例
如，第 58位经过初始置换后，处于第 1位，
而通过逆置换，又将第 1位换回到第 58位 。
可见输入组 m和 IP (IP-1 (m)) 是一样的。
36
二、数据加密标准 (DES)
数据加密标准
64位码
64位码
初始变换
逆初始变换
L0
明文
密文
输入
输出
IP
IP-1
R0
37
?中间各级算法说明
?Ki, 每级密钥不同
二、数据加密标准 (DES)
数据加密标准
Li-1
Li
Ri-1
Ri
Li-1 ? f(Ri-1,Ki)
38
二、数据加密标准 (DES)
数据加密标准
加密函数
?(A,Ki)
A(32位 ) 加密时 A=Ri-1
扩展置换 E
48位 结果 48位 Ki
+
选择函数组
(S1~S8)
32位结果
?(A,Ki)
置换运算 P
32位
39
二、数据加密标准 (DES)
数据加密标准
左 32位 右 32位
Li-1 Ri-1
扩展置换 E
48位 (明文 )
64位密钥
作第 i次 迭代的
计算机子密钥 Ki
密钥
程序表48位 (密钥 )
8组 6位码
S1 S2 S8
模 2加
选择函数 Si
输入,6位
输出,4位
+++++…+++++
乘积变换中的一次迭代
40
二、数据加密标准 (DES)
数据加密标准
32位
置换运算 P
32位加密函数输出
32位
Li Ri
左 32位 右 32位
Ri-1
Li-1 模 2加 +++++...++++++
41
二、数据加密标准 (DES)
数据加密标准
扩展置换 E
r1(i)r2(i)r3(i)r4(i)
r5(i)r6(i)r7(i)r8(i)
…
r29(i)r30(i)r31(i)r32(i)
r32(i)r1(i)r2(i)r3(i)r4(i) r5(i)
r4(i)r5(i)r6(i)r7(i)r8(i) r9(i)
…
r28(i)r29(i)r30(i)r31(i)r32(i) r1(i)
把 R（ i） 视为由 8个 4位
二进制的块组成
把它们再扩充为 8个 6
位二进制的块（左右
各增加一列）
用 E(R（ i） )表示这个变
换，称为选择函数 E。
42
二、数据加密标准 (DES)
数据加密标准
A 32位
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
选择运算 E
选择运算 E的结果 48位
扩展置换 E
43
二、数据加密标准 (DES)
数据加密标准
使用密钥
在第 i+1次迭代中，用 48位二进制的密钥（由 56位密
钥生成，下边会介绍）
K（ i+1） =k1(i+1)k2(i+1)…k 48(i+1)
与 E(R（ i） )按位相加（逻辑异或），输出仍是 48位，
共 8行，每行 6位。
Z 1, r32(i)+ k1(i+1) r1(i) +k2(i+1) … r 5(i) +k6(i+1)
Z 2, r4(i)+ k7(i+1) r5(i) +k8(i+1) … r 9(i) +k12(i+1)
…
Z 8, r28(i)+ k43(i+1) r29(i) +k44(i+1) … r 1(i) +k48(i+1)
作为 8个 Si选择函数 的输入
44
二、数据加密标准 (DES)
数据加密标准
S1,S2...S8选择函数
其功能是把 6bit数据变为 4bit数据。 Si(i=1,2......8)的功能表：
S1,14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,
0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,
4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,
S2,15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,
3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,
0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,
45
数据加密标准
S6:
12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
S7:
4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,
13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,
1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,
S8:
13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,
1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,
7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11,
S3:
10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,
13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,
13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,
S4:
7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,
13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,
10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,
S5:
2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,
14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,
4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,
46
数据加密标准
S 盒是 DES 的最敏感部分，其原理至今未公开。人们担
心 S 盒隐藏陷门，使得只有他们才可以破译算法，但研
究中并没有找到弱点。美国国家安全局透露了 S 盒的几
条设计准则：
1 所有的 S 盒都不是它输入的线性仿射函数。就是没有
一个线性方程能将四个输出比特表示成六个比特输入的
函数。
2 改变 S 盒的 1 位输入，输出至少改变 2 位。这意味着 S
盒是经过精心设计的，它最大程度上增大了扩散量。
3 S 盒的任意一位输出保持不变时,0 和 1 个数之差极
小。即如果保持一位不变而改变其它五位，那么其输出
0 和 1 的个数不应相差太多。
47
二、数据加密标准 (DES)
数据加密标准
使用选择函数 S
将以上第 j个 (1≤j≤6)二进制的块 （ 记为 Z j=zj1 zj2 zj3 zj4 zj5
zj6） 输入第 j个选择函数 Sj。 各选择函数 Sj的功能是把 6位数
变换成 4位数, 做法是以 zj1zj6为行号, zj2 zj3 zj4 zj5为列号,
查找 Sj,行列交叉处即是要输出的 4位数 。
在此以 S1为例说明其功能, 我们可以看到：在 S1中, 共有 4行
数据, 命名为 0,1,2,3行；每行有 16列, 命名为 0,1,2、
3,......,14,15列 。 现设输入为,D＝ 101100
令：列＝ 0110
行＝ 10
坐标为（ 2,6），然后在 S1表中查得对应的数为 2，以 4
位二进制表示为 0010，此即选择函数 S1的输出。
48
二、数据加密标准 (DES)
数据加密标准
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S1
1 0 1 1 0 010
2
0 0 1 0
输入 6位
输出 4位
使用选择函数 S的例子
49
二、数据加密标准 (DES)
数据加密标准
8个选择函数的输出 （ 32位）
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
置换 P
加密函数的结果 X （ 32位）
置换 P（ 单
纯换位表）
50
二、数据加密标准 (DES)
数据加密标准
迭代
把 L（ i） 与 X（ i） 按位相加, 形成 R（ i+1）, 且令 R
（ i） 为 L（ i+1）, 即得到经第 i+1次迭代加密后的
输出 L（ i+1） R（ i+1）, 其中
L（ i+1） = R（ i）
R（ i+1） = L（ i） ⊕ f(R（ i）,K（ i+1） ) (*)
(i=0,1,2,…,15)
51
数据加密标准
64位密钥
置换选择 1
C0(28位 ) D0(28位 )
循环左移 循环左移
C1(28位 ) D1(28位 )
置换选择 2 K1
(48位 )(56位 )
循环左移 循环左移
Ci(28位 ) Di(28位 )
置换选择 2 Ki
(48位 )(56位 )
16个子密钥的生成算法
循环左移：
1 1 9 1
2 1 10 2
3 2 11 2
4 2 12 2
5 2 13 2
6 2 14 2
7 2 15 2
8 2 16 1
52
二、数据加密标准 (DES)
数据加密标准
置换选择 1
密钥计算的目的在于产生加密和解密时所需要的 16
个子密钥，记作 K(i)。 初始密钥 Key值为 64位，但
DES算法规定，其中第 8,16,......64位是奇偶校
验位，不参与 DES运算。故 Key 实际可用位数便只
有 56位。即：经过子密钥换位表 PC-1的变换后，
Key 的位数由 64 位变成了 56位，此 56位分为 C0、
D0两部分，各 28位。
53
二、数据加密标准 (DES)
数据加密标准
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 33 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
不考虑各字节第 8位
密钥（ 64位）
C0(28位 ) D0(28位 )
密钥置换选择 1
54
二、数据加密标准 (DES)
数据加密标准
循环移位规则：
轮数,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
密钥置换选择 2
56位分为 C0,D0两部分，然后分别进行第 1次循环左移，得
到 C1,D1,将 C1（ 28位）,D1（ 28位）合并得到 56位，
再经过子密钥换位表 PC-2,便得到了密钥 K1（ 48位）。
子密钥换位表 PC-2给出了选择及选择后的次序，可以看出
去掉了第 9,18,22,25,35,38,43,54位。
55
二、数据加密标准 (DES)
数据加密标准
Ci(28位 ) Di(28位 )
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Ki(48位 )
密钥置换 2
去掉第 9,18，
22,25,35，
38,43,54
位,56位变
成 48位
56
二、数据加密标准 (DES)
数据加密标准
L0R0 ←IP( 明文 )
L1←R 0
R1← L 0??(R0,K1)
L2←R 1
R2← L 1??(R1,K2)
……
L16←R 15
R16← L 15??(R15,K16)
密文 ← IP-1(R16L16)
加密过程,
L0R0 ←IP(<64 位明文 >)
Ln←R n-1
Rn← L n-1??(Rn-1,Kn)
<64位密文 >← IP-1(R16L16)
解密过程,
R16L16 ←IP(<64 位密文 >)
Rn-1←L n
Ln-1←R n??(Ln,Kn)
<64位明文 >← IP-1(L0R0)
57
二、数据加密标准 (DES)
数据加密标准
DES算法
1,处理密钥,
1.1 从用户处获得 64位密钥 Key.(每第 8位为校验位,
为使密钥有正确的奇偶校验,每个密钥要有奇数个, 1”
位,(本文如未特指, 均指二进制位 )
1.2 具体过程,
1.2.1 对密钥实施变换,经过子密钥换位表 PC-1的
变换后, Key 的位数由 64 位变成了 56位 。 (P53 表 4.4)
1.2.2 把变换后的密钥等分成两部分,前 28位记为 C0,
后 28位记为 D0。
58
二、数据加密标准 (DES)
数据加密标准
1.2.3 计算子密钥 (共 16个 ),从 i=1开始 。
1.2.3.1 分别对 Ci-1,Di-1作循环左移来生成 Ci,Di(共 16次 )。
1.2.3.2 串联 Ci,Di,得到一个 56位数, 然后对此数作子密钥
换位表 PC-2变换以产生 48位子密钥 Ki。 (P53 表 4.6)
1.2.3.3 按以上方法计算出 16个子密钥。
2,对 64位数据块的处理：
2,1 把数据分成 64位的数据块, 不够 64位的以适当方式填补 。
2,2对数据块利用 初始变换 IP表作变换 。
2,3 将变换后的数据块等分成前后两部分，前 32位记为 L0,后
32位记为 R0。
59
二、数据加密标准 (DES)
数据加密标准
2,4 用 16个子密钥对数据加密 。
2,4,1 利用 扩展置换 E,扩展 32位的成 48位 （ P54 表 4.7)
2,4,2 用 E{R (i-1)}与子密钥 K(i)作按位 异或运算 。
2,4,3 把所得的 48位数分成 8个 6位数 。 1-6位为 Z 1,7-12位
为 Z 2,…… 43-48位为 Z 8。
2,4,4 用 S密箱里的值替换 Z j。 从 j=1开始 。 S密箱里的值为
4位数, 共 8个 S密箱
2,4,4,1 取出 Z j的第 1和第 6位串联起来成一个 2位数, 记
为 m.。 m即是 Sj密箱里用来替换 Z j的数所在的列数 。
2,4,4,2 取出 Z j的第 2至第 5位串联起来成一个 4位数, 记
为 n。 n即是 Sj密箱里用来替换 Z j的数所在的行数 。
60
二、数据加密标准 (DES)
数据加密标准
2,4,4,3 用 S密箱里坐标 （ n,m） 的值替换 。
2,4,5八个选择函数 Sj(1≤j≤8)的输出拼接为 32位二进制数据
区组, 把它作为 P盒置换 的输入, 得到输出
2,4,6 把得到的结果与 L（ i-1） 作异或运算 。 把计算结果賦给
R（ i） 。
2,4,7 把 R（ i-1） 的值賦给 L（ i）, 完成第 1轮乘积变换 。
2,4,8 从 2,4,1循环执行, 直到 K(16)也被用到 。 2~16轮
2,5 把 R（ 16） 和 L（ 16） 顺序串联起来得到一个 64位数 。 对这
个数实施 2,2变换的 逆变换 IP-1。
61
分组密码运行模式
数据加密标准
ECB（ 电码本）模式：
各明文组独立地以同一密钥加密；传送短数据
62
分组密码运行模式
? CBC（ 密码分组链接）模式：
Cn=Ek[Cn-1⊕ Pn]； 初始向量 V1；
用途：传送数据分组；认证。
63
分组密码运行模式
? CFB（ 密码反馈）模式：利用 CFB,OFB模式，可将
DES转换为流密码。流密码无需填充消息，实时运行。
流密码中明文和密文长度相同。如对字符加密，只要
密钥长度 8bit。
Cn=Pn ⊕S j(E(C n-1))
64
分组密码运行模式
? OFB（ 输出反馈）模式,用分组密码产生一个
随机密钥流，将此密钥流和明文流进行异或可
得密文流。仍然需要一个初始向量（ IV）
65
二、数据加密标准 (DES)
数据加密标准
+ ?
K1
+ ?
K2
+ ?
Kn
DES设计原理
重复交替使用选择函数 S和置换运算 P两种变换
使用 Feistel密码结构 (1967年）
66
混淆 (confusion),使密文与明文的统计独立性
关系复杂化。 使得输出是输入的非线性函数；
用于掩盖明文和密文间的关系。通过代替法
实现，如 S盒。
散布 (diffusion),使每位明文尽可能影响多位
密文。 扩展输出对输入的相关性，尽量使密
文的每一位受明文中多位影响。通过置换法
实现，如 P盒。
单独用一种方法，容易被攻破。
流密码只依赖于混淆；分组密码两者都用。
67
DES算法的脆弱性
DES的半公开性,S盒的原理至今保密，所以不能算作
真正的公开加密算法。
1） 函数构造与作用域：
加密强度取决于函数 f的复杂度 (S,P)和 f的执行次数。
? 64位固定分组，短组模式，易造成密文重复组块
? 有限的函数作用域 ASCII码 0~127
? 子密钥只参与异或简单的运算，有可能损害变换精
度。
2）迭代问题
无法证明迭代 16次最好
迭代在有限的作用域中存在封闭性；迭代次数多不仅
费时，还可能被一次简单的变换所代替。
68
DES算法的脆弱性
3） S盒中的重复因子及密钥多值问题
? S盒设计中利用重复因子，导致 S盒对不同输入
可能产生相同输出，使加密、解密变换的密钥
具有多值性。
? 子密钥长度 48位，只影响 32位输出，因此加密
强度达不到 256，实际只有 232x16=236
? S盒是精心设计的，它有利于设计者破译密码。
? 提高加密强度（如增加密钥长度），系统开销
呈指数增长，除提高硬件、并行处理外，算法
本身和软件技术无法提高加密强度。
69
DES算法存在的问题与挑战
数据加密标准
强力攻击,255次尝试 穷尽搜索 蛮力攻击
差分密码分析法,247次尝试
1991年提出，选择明文攻击。分析明文对
的差值对密文对差值的影响。很有效。
线性密码分析法,243次尝试
1992年提出，已知明文攻击。寻找一个近
似的线性表达式，通过选择充分多的明文 ——
密文对来破解密钥。对 DES更有效。
70
多重 DES及 IDEA
? 二重 DES （ 二个密钥，长度 112位）,
? 加密,C=Ek2[Ek1(P)]
? 解密,P=Dk1[Dk2(C)]
? 要防止中途攻击
? 三重 DES（ 二个密钥）
? 加密,C=Ek1[Dk2 [Ek1(P)]]
? 解密,P=Dk1[Ek2 [Dk1(C)]]
? IDEA加密算法 1992年，瑞士的 Lai和 Massey
128位密钥,8轮，快速，软硬件实现。
71
三、高级加密标准 (AES)
NIST(国家标准技术研究所 )1997年 9月 12日发出征集高
级加密标准的通知 。 1998年 8月首次选出 15个候选者，
1999年 3月遴选出 5个，包括,E2,MARS,RC6、
Rijndael,Twofish。 2000年 10月 2日，美国商务部部长
宣布比利时的 Rijndael算法成为新的 AES。
选择的基本条件：公开；分组单钥，分组长度 128；密
钥可为 128,192,256；可软硬件实现。
优劣标准：安全性；计算效率；内存要求；简便灵活。
此外：适应性；减少专利纠纷；分散目标减少攻击。
AES被开发用于替代 DES,但 NIST预测 Triple DES仍将
在近期作为一种实用的算法，单 DES将逐步退出。
72
一,RSA算法概述
传统密码体制的缺陷,
密钥管理的麻烦,n个用户保存 n*(n-1)/2个密钥 。
不能提供法律证据,不仅要保密还要解决证实问题 。
1976年, 美国学者 Diffie和 Hellman发表了著名论文
,密码学的新方向,, 提出了建立, 公开密钥密码体
制,,若用户 A有加密密钥 ka（ 公开 ）, 不同于解秘
密钥 ka’（ 保密 ）, 要求 ka的公开不影响 ka’的安全 。
若 B要向 A保密送去明文 m,可查 A的公开密钥 ka,若用
ka加密得密文 c,A收到 c后, 用只有 A自己才掌握的解
密密钥 ka’对 x进行解密得到 m。
公开密钥算法
73
一,RSA算法概述
1978年, 美国麻省理工学院 (MIT)的研究小组成员：
李维斯特 ( Rivest),沙米尔 ( Shamir),艾 德 曼
(Adleman)提出了一种基于公钥密码体制的优秀加密
算法 ——RSA算法 。 RSA算法是一种分组密码体制算
法, 它的保密强度是建立在具有大素数因子的合数,
其因子分解是困难的 。 是否是 NP问题尚未确定 。
RSA得到了世界上的最广泛的应用, ISO在 1992年颁
布的国际标准 X.509中,将 RSA算法正式纳入国际标准 。
1999年美国参议院已通过了立法, 规定电子数字签
名与手写签名的文件, 邮件在美国具有同等的法律效
力 。
公开密钥算法
74
数论知识简介
? 互素：若 gcd(a,b)=1,则整数 a和 b互素。
? 定义：若 a?x mod n =1,则称 a与 x对于模 n互
为逆元。
? 用 Euclid算法求乘法逆元
若 a和 n互素，则 a在模 n下有逆元。
? Euler函数,φ(n)=与 n互素的、小于 n的正整数
的个数,n>1。 例：
φ(3)= φ(4) = φ(6) =2,φ(5)=4,φ(7) =6
φ(12)=6
75
数论知识简介
模运算性质,同余
? 模运算满足自反性、对称性、传递性；
a=a mod n；
若 a=b mod n,则 b=a mod n；
若 a=b mod n,b=c mod n,则 a=c mod n
? 若 a mod n=b mod n,则 (a-b)mod n=0；
[(a mod n) +(b mod n)]mod n=(a + b) mod n；
- - ；
* * ；
例,152 mod 12 =(3*3) mod 12=9
76
? 若 n是素数，则 φ(n)=n-1
若 n=p*q,p,q是素数，则 φ(n)=(p-
1)*(q-1)
例,φ(21)= φ(3*7)=2*6=12
? Fermat小定理：若 m是素数，且 a不是 m
的倍数，则 am-1 mod m=1。
或者：若 m是素数，则 am mod m=a
例,46 mod 7=4096 mod 7=1
47 mod 7=16384 mod 7=4
77
? Euler定理,a φ(n) mod n =1
推论：若 a与 n互素，则 a与 a φ(n)-1 互为
逆元。
例,a=4,n=7,φ(7)=6，
a φ(7)-1 =45=1024
所以,4和 1024在模 7下互为逆元。
验证,4x1024 mod7 =1
78
求乘法逆元
Function Euclid(d,f) //求 d在模 f下的逆元
1) (x1,x2,x3)<-(1,0,f);(y1,y2,y3)<-(0,1,d);
2) If y3=1 then print,逆元是, y2 else print
“无逆元, ; End.
3) Q=[x3/y3]
4) (t1,t2,t3)<-(x1-Q*y1,x2-Q*y2,x3-Q*y3)
5) (x1,x2,x3)<-(y1,y2,y3);
6) (y1,y2,y3)<-(t1,t2,t3)
7) Go to 2)
79
高次幂剩余的运算
公开密钥算法
要计算 gn mod p,因 g,n,p都是大数而
不能采用先高次幂再求剩余的方法来处理,
而要采用平方取模的算法, 即每一次平方或
相乘后, 立即取模运算 。
欧几里德算法
欧几里德算法可以迅速地找出给定的两
个整数 a和 b的最大公因数 gcd（ a,b）, 并可
判断 a与 b是否互素, 因此该算法可用来寻找
加密密钥和解密密钥 。
80
X r mod p 的快速算法流程图
A<-x
B<-r
C<-1
B=0
输出 C
B mod 2=0
B<- B/2
A<- A*A mod p
B<- B-1
C<-C*A mod p
Y
N N
Y
81
一,RSA算法概述
公开密钥算法
每个合数都可以唯一地分解出素数因子
6 = 2 ·3
999999 = 3·3·3·7·11·13·37
27641 = 131·121
从 2 开始试验每一个小于等于 √27641 的素数。
素数：只能被 1和它本身整除的自然数；否则为合数。
整数 n的十进制位数 因子分解的运算次数 所需计算时间（每微秒一次）
50 1.4x1010 3.9小时
75 9.0x1012 104天
100 2.3x1015 74年
200 1.2x1023 3.8x109年
300 1.5x1029 4.0x1015年
500 1.3x1039 4.2x1025年
82
素数的检验
素数的产生
目前, 适用于 RSA算法的最实用的办
法是概率测试法 。 该法的思想是随机产
生一个大奇数, 然后测试其是否满足条
件, 如满足, 则该大奇数可能是素数,
否则是合数 。 素数定理说明素数有无穷
多个, 同时也说明通过随机产生一个大
奇数来判断其素性是具有实用性的 。
83
素数的检验
? Wilson定理：
P是素数 ?? (P -1)! Mod P =-1
当 P较大时，很费时间，无实际价值。
? Rabin-Miller方法 概率检验
Witness(a,n)
/* 将 n-1表示为 bk b k-1… b0的形式
n是待检验的数,a是小于 n的整数。若返
回 True,则 n肯定不是素数；若返回 False,则
n有可能是素数。 */
84
Rabin-Miller方法
{
d=1
for i=k down to 0 {
x=d;d= (d? d) mod n;
if d=1 & (x<>1) &(x<>-1) return True;
if bi=1 then d=(d?a) mod n}
if d<>1 then return True ;
return False ;
}
对于 s个不同的 a,重复调用此算法，每次返回 False,则 n
是素数的概率至少为 1-2-s
85
二,RSA算法的实现
公开密钥算法
RSA加密算法的过程
1,取两个随机大素数 p和 q（ 保密 ）
2,计算公开的模数 n=p*q(公开 )
3,计算秘密的欧拉函数 ?(n) =（ p-1)*(q-1)（ 保密 ）, 丢弃
p和 q,不要让任何人知道 。
4,随机选取整数 e,满足 gcd(e,?(n))=1(公开 e加密密钥 )
5,计算 d满足 de≡1(mod ?(n))(保密 d解密密钥 )
6,将明文 x（ 按模为 r自乘 e次幂以完成加密操作, 从而产生
密文 y（ X,Y值在 0到 n-1范围内 ） 。 Y=xe mod n
7,解密：将密文 y按模为 n自乘 d次幂 。 X=Yd mod n
86
二,RSA算法的实现
公开密钥算法
例设 p=43,q=59,r=p?q=43*59=2537,?(r)=(p-1)(q-1) =42*58
=2436,取 e=13,求 e的逆元 d
解方程 d ? e = 1 mod 2436
2436 =13* 187+ 5,13= 2* 5+ 3
5= 3+ 2,3= 2+ 1
所以 1= 3- 2, 2= 5- 3,3 =13- 2* 5
5 =2436- 13* 187
所以,1= 3- 2= 3-（ 5- 3） = 2* 3- 5
=2*（ 13- 2* 5） - 5= 2 *13- 5* 5
=2* 13- 5*（ 2436 -13 *187）
=937* 13- 5* 2346
即 937* 13 ≡ 1 mod 2436
取 e= 13 时 d= 937
87
二,RSA算法的实现
公开密钥算法
若有明文 public key encryptions
先将明文分块为
pu bl ic ke nc ry pt io ns
将明文数字化令 a b z 分别为 00 01 25 得
1520 0111 0802 1004 2404
1302 1724 1519 0814 1418
利用加密可得密文
0095 1648 1410 1299 1365
1379 2333 2132 1751 1289
88
公开密钥算法
关于素数的分布
1 - 100 25
101 - 200 21
201 - 300 16
301 - 400 16
401 - 500 17
501 - 600 14
601 - 700 16
701 - 800 14
801 - 900 15
901 - 1000 14
素数定理：当 X变得很大时，从 2到 X区间
的素数数目 ?(X)与 X/ln(X)的比值趋近于 1
，即
?(X)
X/ln(X) = 1
limx??
X ?(X) X/ln(X) ?(X)X/ln(X)
1000 168 145 1.159
10,000 1,229 1,086 1.132
100,000 9,592 8,686 1.104
1,000,000 78,498 72,382 1.084
10,000,000 664,579 620,421 1.071
100,000,000 5,761,455 5,428,681 1.061
1,000,000,000 50,847,478 48,254,942 1.054
89
二,RSA算法的实现
公开密钥算法
在 2到 X的区间中，随机选择一个值为素数的概率
近似等于 ?(X)/(X-1)。 可以证明，在找到一个素数
之前，平均要进行 (X-1)/ ?(X)≈LN(X)次实验。
大数的运算
上百位大数之间的运算是实现 RSA算法的基础,
因此程序设计语言本身提供的加减乘除及取模算法
都不能使用，否则会产生溢出，必须重新编制算法
。在编程中要注意进位和借位，并定义几百位的大
数组来存放产生的大数。
90
RSA 的安全性
公开密钥算法
依赖于大数分解, 但是否等同于大数分解一直未能
证明 。 不管怎样, 分解 n是最显然的攻击方法 。
1994年 4月 26日, 美国各大媒体报道：由 RSA发明
人在 17年前出的 129位数字已被因子分解, 并破解
了附带的密语：
The magic words are squeamish ossifrage.
目前, 已能分解 140位十进制的大素数 。 因此,
模数 n必须选大一些 。
RSA最快的情况也比 DES慢上 100倍, 无论是软件还
是硬件实现 。 速度一直是 RSA的缺陷 。 一般只用于
少量数据加密 。
91
RSA算法的脆弱性
公开密钥算法
1) 不能证明 RSA密码破译等同于大数因子分解
2) 速度问题 提高 p?q将使开销指数级增长
3) 至少有 9个明文, 加密后不变，即 me mod n=m
4) 普通用户难于选择 p,q。 对 p,q的基本要求：
? p,q不相同，即不要太接近，又不能差别太大
? p-1,q-1都有大素数因子，增加猜测 φ(r) 难度
? Gcd( p-1,q-1)应当小
92
RSA算法的脆弱性
公开密钥算法
5) P,q选择不当，则变换周期性、封闭性而泄密
例,p=17,q=11,e=7,则 n=187。 设 m=123,则
C1=1237 mod 187=183
C2=1837 mod 187=72
C3=727 mod 187=30
C4=307 mod 187=123
明文 m经过 4次加密，恢复成明文。
总之,RSA对用户要求太苛刻，密钥不能常更换。
93
其它公钥密码体制
? 背包体制 1978年提出 5年后被 Shamir破解
? ElGamal 体制 1985年 基于有限域上计算离
散对数难解性，已用于 DSS(数字签名标准）
例,3x mod 17=5,解得,x=6
3x mod 13=7,无解
? 椭圆曲线体制 (ECC) 1985年 基于离散对数
优点：安全性高；密钥短；灵活性好。
同等安全下的密钥长度：
RSA:512 1024 2048 21000
ECC:106 160 211 600
94
ElGamel 加密体制：
选大素数 P及其本源根 g,p,g公开；
随机选一整数 x作为私钥 (保密 )；
计算 y=gx mod p ; 将 y作为公开密钥。
? 加密过程
在公钥数据库中查找获取用户的公钥 y；
在 0 ~ p-1间取整数 k0; 计算下式并发送 C1和 C2:
K=yk0 mod p,C1=gk0 mod p,C2=K?m mod p；
? 解密过程
计算 K=C1x mod p
明文 m=C2 ?K-1 mod p
计算机系统安全
第四讲 密码学
2
一、密码学概述
密码体制,1） 传统密码体制 2） 现代密码体制
传统密码体制：对称密码体制 （ 单钥体制 ）
现代密码体制：非对称密码体制 （ 公钥密码体制, 双
钥体制 ）
按照对明文的处理方式分为：分组密码算法和序列密
码算法 。
分组密码算法：把明文分成等长的组分别加密
序列密码算法：是一个比特一个比特地处理, 用已知
的密钥随机序列与明文按位异或 。
第四章 传统密码学
3
二、加密和解密
第四章 传统密码学
加密 解密明文 M 密文 C 原始明文M
E（ M） =C,D（ C） =M
D（ E（ M）） =M
明文 Plaintext 密文 Cipher text
加密 Encryption 解密 Decryption
密钥 key
4
二、加密和解密
第四章 传统密码学
密码就是一组含有参数 k的变换 E。 设已知信息 m,通
过变换 E得到密文 c。 即 c=Ek(m) 这个过程称之为加密，
参数 k称为密钥。解密算法 D是加密算法 E的逆运算，
解密算法也是含参数 k的变换。
DK（ EK（ M）） =M.
加密 解密明文 M 密文 C 原始明文M
密钥 K 密钥 K
EK（ M） =C DK（ C） =M.
5
二、加密和解密
第四章 传统密码学
DK2 （ EK1（ M）） =M 双钥密码体制
加密 解密明文 M 密文 C 原始明文 M
加密
密钥 K1
解密
密钥 K2
EK1（ M） =C DK2（ C） =M
6
定义, (密码体制）它是一个五元组（ P,C,K,E,D)满足条件：
（ 1） P是可能明文的有限集；（明文空间）
（ 2） C是可能密文的有限集；（密文空间）
（ 3） K是一切可能密钥构成的有限集；（密钥空间）
*（ 4）任意 k∈ K,有一个加密算法 和相应的解密
算法,使得 和
分别为加密解密函数，满足 dk(ek(x))=x,这里 x ∈ P。
二、加密和解密
第四章 传统密码学
Eek?
CPek ?,PCdk ?:Ddk?
7
二、加密和解密
第四章 传统密码学
信源 加密机 解密机 接收者
安全信道
密钥源
窃听者
x y x
k1
加密通信的模型
密钥源
k2不安全信道
密码分析
8
1*.Alice要将明文Ｘ在不安全信道上发给 Bob,设 X=x1
x2… xn,其中 xi ∈ P,Alice用加密算法 ek作 yi=ek(xi) 1≤ i≤
n
结果的密文是 Y=y1y2….y n,在信道上发送，
Bob收到后解密,xi=dk(yi)
得到明文 X=x1 x2… xn,。
2*.加密函数 ek必须是单射函数，就是一对一的函数。
3*.好的密钥算法是唯密钥而保密的。
4*.若 Alice和 Bob在一次通信中使用相同的密钥，那么
这个加密体制为对称的，否则称为非对称的。
二、加密和解密
第四章 传统密码学
9
密码学：对信息进行编码实现隐蔽信息的一门学问。
密码分析学：研究分析破译密码的学问。两者相互对立、促进。
1,常用的密码分析攻击有四类,
加密算法：公开 。 攻击目标：获得密钥 K
? 唯密文攻击 （ ciphertext only attacks） 。
已知：截获部分密文
? 已知明文攻击 （ know plaintext attacks） 。
已知：截获部分密文；若干明文 ——密文对 。
? 选择明文攻击 （ chosen plaintext attacks） 。
已知：截获部分密文；自主选择的明文 ——密文对 。
? 选择密文攻击
暂时接近密码机, 可选择密文串, 并构造出相应的明文 。
三、密码分析
第四章 传统密码学
10
三、密码分析
第四章 传统密码学
2、算法的安全性
密码算法具有不同的安全等级,以下情况可能是安全的
.破译算法的代价大于加密数据的价值
.破译算法所需的时间大于加密数据保密的时间
.用单密钥加密的数据量小于破译算法需要的数据量
Shannon理论：仅当密钥至少和明文一样长时才无条件安全。
如果不论密码分析者有多少密文，都没有足够的信息恢复出
明文，那么这个算法就是无条件保密的，只有一次一密乱码
本，才是无条件安全的 。 所有其它的密码系统在唯密文攻击
中都是可破的 （ 蛮力攻击 ）。
11
三、密码分析
第四章 传统密码学
密码学更关心在计算上不可破译的密码系统。如果一个算法
用（现在或将来）可得到的资源（ 公开数据 ）都不能破译，
这个算法则被认为在计算上是安全的。
可以用不同方式衡量攻击方法的复杂性：
数据复杂性 。 用作攻击输入所需的数据量 。
处理复杂性 。 完成攻击所需要的时间, 这个经常叫做工作因
素 。
存储需求 。 进行攻击所需要的存储量 。
作为一个法则，攻击的复杂性取这三个因数的最小化，有些
攻击包括这三种复杂性的折中：存储需求越大，攻击可能越
快。
12
四、传统密码学
第四章 传统密码学
1、移位法, 将明文字母互相换位，明文的字母不变, 但顺
序被打乱了。 例如,线路加密法
明文以固定的宽度水平写出，密文按垂直方向读出。
明文,COMPUTERSYSTEMSECURITY
COMPU
TERSY
STEMS
ECURI
TY
密文,CTSETOETCYMREUPSMRUYSI
13
四、传统密码学
第四章 传统密码学
2、代替法,代替密码就是明文中每一个字符被替换成密文
中的另外一个字符，代替后的各字母保持原来位置。对密文
进行逆替换就可恢复出明文。有四种类型的代替密码：（ 1）
（ 1）单表（简单）代替密码：就是明文的一个字符用相应
的一个密文字符代替。加密过程中是从明文字母表到密文字
母表的一一映射。例：恺撒（ Caesar)密码。
（ 2）同音代替密码：它与简单代替密码系统相似，唯一的
不同是单个字符明文可以映射成密文的几个字符之一同音代
替的密文并不唯一。
（ 3）多字母组代替密码：字符块被成组加密，例如, ABA”
可能对应, RTQ”,ABB可能对应, SLL”等。例,Playfair密码。
（ 4）多表代替密码：由多个单字母密码构成，每个密钥加
密对应位置的明文。 例：维吉尼亚密码。
14
四、传统密码学
第四章 传统密码学
3、凯撒（ Caesar） 密码
令 26个字母分别对应于 0～ 25,a=1,b=2…… y=25,z=0。
凯撒加密变换实际上是 c≡ (m + k) mod 26
其中 m是明文对应的数据, c是与明文对应的密文数据, k是
加密用的参数, 叫密钥 。 比如明文,data security 对应数据
序列,4,1,20,1,19,5,3,21,18,9,20,25
k=5时, 得密文序列
9,6,25,6,24,10,8,0,23,14,25,4
密文,ifyxjhzwnyd
缺点：容易破解密码 。
15
置换密码：
1*,置换 π的表示：
π＝
2*密钥空间 K很大,|k|=26! ≈ 4× 1026,破译者穷举搜索
是不行的，然而，可由统计的方式破译它。
3*移位密码体制是替换密码体制的一个特例，它仅含 26
个置换做为密钥空间
四、传统密码学
第四章 传统密码学
移位密码：如 凯撒（ Caesar） 密码 。
仿射密码,如果选取 k1,k2两个参数，其中 k1 与 26 互素，
令 c≡(k 1m + k2)mod 26。 这种变换称为仿射变换。
( 0 1 2 3,.23 24 250' 1' 2' 3',.23' 24' 25' )
16
四、传统密码学
第四章 传统密码学
4,Playfair密码（ 英国曾用）
密钥由 25个英文字母（ J与 I相同）组成的 5阶方阵。
每一对明文字母 m1和 m2,都根据下面的 6条规则进行加密 。
（ 1） 明文字母 m1和 m2同行 。 密文是其右边字母 。
（ 2） 明文字母 m1和 m2同列 。 密文是其下边字母 。
（ 3） 明文字母 m1和 m2不同行, 不同列 。 密文是长方形的
另两个顶点 。
（ 4） 明文字母 m1和 m2相同 。 在 m1和 m2之间加一个无效
字母 。
（ 5） 明文有奇数个字母, 末尾加一个无效字母 。
（ 6） I,J看成是相同字母 。
17
四、传统密码学
第四章 传统密码学
例,25个字母组成 5阶方阵如下 （ J与 I相同 ）,
HARPS （ 1） 明文字母 m1和 m2同行 。 密文是其右边字母 。
ICODB （ 3） m1和 m2不同行, 不同列 。 密文是长方形的另两个顶点 。
EFGKL
MNQTU
VWXYZ
例：明文,CO MP UT ER
密文,OD TH MU GH
利用规则,1 3 1 3
18
四、传统密码学
第四章 传统密码学
5,维吉尼亚 （ Vigenere） 密码
典型的多表密码, 即一个明文字母可表示为多个密
文字母 。,
例如：明文为 System,密钥为 dog,加密过程如下：
明文,S y s t e m
密钥,d o g d o g
密文,V m g w r s
在这个例子中, 每三个字母中的第一, 第二, 第三
个字母分别移动 （ mod 26） 3个, 14个和 6个位置 。
19
四、传统密码学
第四章 传统密码学
优点：能抵抗简单的字母频率分析攻击 。
设密钥 k=k1k2… kn,明文 M=m1m2… mn,加密变换
Ek(M)=c1c2… cn。 其中
ci≡( mi + ki) mod 26,i=1,2… n。
多表密码加密算法结果将使得对单表置换用的简单
频率分析方法失效 。
20
四、传统密码学
第四章 传统密码学
6,一次一密密码
一次一密密码, 由 AT&T公司的 Gilbert Vernam在
1917年提出 。 发方和收方各保存一份一次一密乱码
本, 它是一个大的不重复的真随机密钥字母集 。 发
方用乱码本中的某一页密钥加密明文 。 加密方法：
明文字符和乱码本密钥字符的模 26加法 。
每个密钥仅对一个消息使用一次 。 发方对所发的消
息加密, 然后销毁乱码本中用过的一页 。 收方有一
个同样的乱码本, 并依次使用乱码本上的每个密钥
去解密密文的每个字符, 然后销毁乱码本中用过的
一页 。
21
四、传统密码学
第四章 传统密码学
棋盘密码
建立一张表, 使每一个字符对应一数 ξ,η, ξ 是该
字符所在行标号, η 是列标号 。 这样将明文变成形
式为一串数字密文 。 这种密码古代曾广泛利用 。
1 2 3 4 5
1 A B C D E
2 F G H I J K
3 L M N O P
4 Q R S T U
5 V W X Y Z
22
五、密码体制评价
第四章 传统密码学
保密强度,与数据的重要性有关
密钥的长度：安全, 保管, 记忆
算法的复杂度：开销大小
差错的传播性：不应使差错导致通信失败
加密后信息长度的增加程度：
23
六、单表密码分析
第四章 传统密码学
英语 26个字母中, 各字母出现的频率不同而稳
定, 经过大量统计, 可以给出了各字母出现的
频率值 。 英文明文字母按出现概率大小分组表：
1 e >0.1
2 t a o i n s h r 0.05-0.1
3 d l 0.03-0.05
4 c u m w f g y p b 0.01-0.03
5 v k j x q z <0.01
24
六、单表密码分析
第四章 传统密码学
字母, 三字母组合是分析单表密码的有力手段 。
英语单词以 e,s,t,d双结尾的超过一半；以 t,a、
s,w 为起始字母的约为一半 。
某些常用用法也会提供有价值的线索, 如信的开头
写 Dear ； 源程序的某一位置是版权声明；电子资金
传送报头格式 。
单表密码的弱点：明文和密文字母之间的一一代替
关系 。 这使得明文中的一些固有特性和规律 （ 比如
语言的各种统计特性 ） 必然反映到密文中去 。
25
一,DES算法概述
现代与古典密码学采用的基本思想相同：替换与变位 。
古典：算法简单, 长密钥 。
现代：算法复杂 。
P盒和 S盒
数据加密标准
P盒 用 P盒构成的 S盒
P盒 实质上是用硬件实现 变位,改变输入序列
S盒 实质上是用硬件实现若干比特的替换
译
码
器
编
码
器
26
一,DES算法概述
发明人,IBM公司 W,Tuchman 和 C,Meyer 1971-72年研制 。
产生,美国商业部的国家标准局 NBS1973年 5月到 1974年 8月
两次发布通告, 公开征求用于电子计算机的加密算法 。 经评
选从一大批算法中采纳了 IBM的 LUCIFER方案 。
标准化,于 1976年 11月被美国政府采用, DES随后被美国国
家标准局和美国国家标准协会 (American National Standard
Institute,ANSI) 承认 。 1977年 1月以数据加密标准 DES
（ Data Encryption Standard） 的名称正式向社会公布 。 于
1977年 7月 15日生效 。
DES的发展：如衍生出可抗差分分析攻击的变形 DES以及密
钥长度为 128比特的三重 DES等 。
数据加密标准
27
一,DES算法概述
在 1977年, 人们估计要耗资两千万美元才能建成一
个专门计算机用于 DES的解密, 而且需要 12个小时
的破解才能得到结果 。
1997年开始, RSA公司发起了一个称作, 向 DES挑
战, 的竞技赛 。
1997年 1月, 用了 96天时间, 成功地破解了用 DES加
密的一段信息；一年之后, 在第二届赛事上, 这一
记录 41天 ； 1998年 7月,, 第 2-2届 DES挑战赛
（ DES Challenge II-2）, 把破解 DES的时间缩短到了
只需 56个小时；, 第三届 DES 挑战 赛 （ DES
Challenge III）,把破解 DES的时间缩短到了只需 22.5
小时 。
数据加密标准
28
一,DES算法概述
数据加密标准
个人攻
击
小组攻
击
院, 校
网络攻
击
大公司 军事情
报机构
40（ bits） 数周 数日 数小时 数毫秒 数微秒
56 数百年 数十年 数年 数小时 数秒钟
64 数千年 数百年 数十年 数日 数分钟
80 不可能 不可能 不可能 数百年 数百年
128 不可能 不可能 不可能 不可能 数千年
29
一,DES算法概述
数据加密标准
上表中攻击者配有如下计算机资源的攻击能力
攻击者类
型
所配有的计算机资源 每秒处理
的密钥数
个人攻击 1台高性能桌式计算机及
其软件
217-224
小组攻击 16台高性能桌式计算机及
其软件
221-224
院, 校网
络攻击
256台高性能桌式计算机
及其软件
225-228
大公司 配有价值 1百万美元的硬
件
243
军事情报
机构
配有价值 1百万美元的硬
件及先进的攻击技术
255
30
二、数据加密标准 (DES)
数据加密标准
64位码
64位码
初始变换
逆初始变换
乘积变换 16次迭代
明文
密文
输入
输出
IP
IP-1
31
二、数据加密标准 (DES)
数据加密标准
利用传统的换位和置换加密 。 假定信息空间由 {0,1}组成的字
符串, 信息被分成 64比特的块, 密钥是 56比特 。 经过 DES加
密的密文也是 64比特的块 。
明文,m=m1m2… m64 mi = 0,1 i = 1,2,… 64
密钥,k=k1k2… k64 ki = 0,1 i = 1,2,… 64
其中 k8,k16,…, k64是奇偶校验位, 起作用的仅为 56位 。
加密算法, Ek(m) = IP-1·T16·T15…… T1·IP(m)
其中 IP为初始置换, IP-1是 IP的逆, Ti,i = 1,2,… 16是一
系列的变换 。
解密算法, Ek-1 (c) = IP-1·T1·T2…… T16·IP (c)
32
二、数据加密标准 (DES)
数据加密标准
输入（ 64位）
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
输出（ 64位）
初始变换
IP
L0（ 32位） R0（ 32位）
初始变换 IP
33
二、数据加密标准 (DES)
数据加密标准
IP 中各列元素位置号数相差为 8, 相当于将原明文各字节按列写出,
各列比特经过偶采样和奇采样置换后再对各行进行逆序, 将阵中元素
按行读得的结果 。
1 9 17 25 33 41 49 57
2 10 18 26 34 42 50 58
3 11 19 27 35 43 51 59
4 12 20 28 36 44 52 60
5 13 21 29 37 45 53 61
6 14 22 30 38 46 54 62
7 15 23 31 39 47 55 63
8 16 24 32 40 48 56 64
输入 64个二进制位明码文数据区组
m= m1m2… m64
按初始换位表 IP进行换位, 得到区组 B（ 0）,
B（ 0） =b1(0)b2(0)… b64(0)= m58m50… m7记成 L0,R0左右两部分
34
二、数据加密标准 (DES)
数据加密标准
置换码组 输入（ 64位）
40 8 48 16 56 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
输出（ 64位）
逆初始变换
IP-1
逆初始变换
35
二、数据加密标准 (DES)
数据加密标准
逆初始变换。用 IP-1 表示，它和 IP互逆。例
如，第 58位经过初始置换后，处于第 1位，
而通过逆置换，又将第 1位换回到第 58位 。
可见输入组 m和 IP (IP-1 (m)) 是一样的。
36
二、数据加密标准 (DES)
数据加密标准
64位码
64位码
初始变换
逆初始变换
L0
明文
密文
输入
输出
IP
IP-1
R0
37
?中间各级算法说明
?Ki, 每级密钥不同
二、数据加密标准 (DES)
数据加密标准
Li-1
Li
Ri-1
Ri
Li-1 ? f(Ri-1,Ki)
38
二、数据加密标准 (DES)
数据加密标准
加密函数
?(A,Ki)
A(32位 ) 加密时 A=Ri-1
扩展置换 E
48位 结果 48位 Ki
+
选择函数组
(S1~S8)
32位结果
?(A,Ki)
置换运算 P
32位
39
二、数据加密标准 (DES)
数据加密标准
左 32位 右 32位
Li-1 Ri-1
扩展置换 E
48位 (明文 )
64位密钥
作第 i次 迭代的
计算机子密钥 Ki
密钥
程序表48位 (密钥 )
8组 6位码
S1 S2 S8
模 2加
选择函数 Si
输入,6位
输出,4位
+++++…+++++
乘积变换中的一次迭代
40
二、数据加密标准 (DES)
数据加密标准
32位
置换运算 P
32位加密函数输出
32位
Li Ri
左 32位 右 32位
Ri-1
Li-1 模 2加 +++++...++++++
41
二、数据加密标准 (DES)
数据加密标准
扩展置换 E
r1(i)r2(i)r3(i)r4(i)
r5(i)r6(i)r7(i)r8(i)
…
r29(i)r30(i)r31(i)r32(i)
r32(i)r1(i)r2(i)r3(i)r4(i) r5(i)
r4(i)r5(i)r6(i)r7(i)r8(i) r9(i)
…
r28(i)r29(i)r30(i)r31(i)r32(i) r1(i)
把 R（ i） 视为由 8个 4位
二进制的块组成
把它们再扩充为 8个 6
位二进制的块（左右
各增加一列）
用 E(R（ i） )表示这个变
换，称为选择函数 E。
42
二、数据加密标准 (DES)
数据加密标准
A 32位
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
选择运算 E
选择运算 E的结果 48位
扩展置换 E
43
二、数据加密标准 (DES)
数据加密标准
使用密钥
在第 i+1次迭代中，用 48位二进制的密钥（由 56位密
钥生成，下边会介绍）
K（ i+1） =k1(i+1)k2(i+1)…k 48(i+1)
与 E(R（ i） )按位相加（逻辑异或），输出仍是 48位，
共 8行，每行 6位。
Z 1, r32(i)+ k1(i+1) r1(i) +k2(i+1) … r 5(i) +k6(i+1)
Z 2, r4(i)+ k7(i+1) r5(i) +k8(i+1) … r 9(i) +k12(i+1)
…
Z 8, r28(i)+ k43(i+1) r29(i) +k44(i+1) … r 1(i) +k48(i+1)
作为 8个 Si选择函数 的输入
44
二、数据加密标准 (DES)
数据加密标准
S1,S2...S8选择函数
其功能是把 6bit数据变为 4bit数据。 Si(i=1,2......8)的功能表：
S1,14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,
0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,
4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,
S2,15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,
3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,
0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,
45
数据加密标准
S6:
12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
S7:
4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,
13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,
1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,
S8:
13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,
1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,
7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11,
S3:
10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,
13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,
13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,
S4:
7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,
13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,
10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,
S5:
2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,
14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,
4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,
46
数据加密标准
S 盒是 DES 的最敏感部分，其原理至今未公开。人们担
心 S 盒隐藏陷门，使得只有他们才可以破译算法，但研
究中并没有找到弱点。美国国家安全局透露了 S 盒的几
条设计准则：
1 所有的 S 盒都不是它输入的线性仿射函数。就是没有
一个线性方程能将四个输出比特表示成六个比特输入的
函数。
2 改变 S 盒的 1 位输入，输出至少改变 2 位。这意味着 S
盒是经过精心设计的，它最大程度上增大了扩散量。
3 S 盒的任意一位输出保持不变时,0 和 1 个数之差极
小。即如果保持一位不变而改变其它五位，那么其输出
0 和 1 的个数不应相差太多。
47
二、数据加密标准 (DES)
数据加密标准
使用选择函数 S
将以上第 j个 (1≤j≤6)二进制的块 （ 记为 Z j=zj1 zj2 zj3 zj4 zj5
zj6） 输入第 j个选择函数 Sj。 各选择函数 Sj的功能是把 6位数
变换成 4位数, 做法是以 zj1zj6为行号, zj2 zj3 zj4 zj5为列号,
查找 Sj,行列交叉处即是要输出的 4位数 。
在此以 S1为例说明其功能, 我们可以看到：在 S1中, 共有 4行
数据, 命名为 0,1,2,3行；每行有 16列, 命名为 0,1,2、
3,......,14,15列 。 现设输入为,D＝ 101100
令：列＝ 0110
行＝ 10
坐标为（ 2,6），然后在 S1表中查得对应的数为 2，以 4
位二进制表示为 0010，此即选择函数 S1的输出。
48
二、数据加密标准 (DES)
数据加密标准
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S1
1 0 1 1 0 010
2
0 0 1 0
输入 6位
输出 4位
使用选择函数 S的例子
49
二、数据加密标准 (DES)
数据加密标准
8个选择函数的输出 （ 32位）
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
置换 P
加密函数的结果 X （ 32位）
置换 P（ 单
纯换位表）
50
二、数据加密标准 (DES)
数据加密标准
迭代
把 L（ i） 与 X（ i） 按位相加, 形成 R（ i+1）, 且令 R
（ i） 为 L（ i+1）, 即得到经第 i+1次迭代加密后的
输出 L（ i+1） R（ i+1）, 其中
L（ i+1） = R（ i）
R（ i+1） = L（ i） ⊕ f(R（ i）,K（ i+1） ) (*)
(i=0,1,2,…,15)
51
数据加密标准
64位密钥
置换选择 1
C0(28位 ) D0(28位 )
循环左移 循环左移
C1(28位 ) D1(28位 )
置换选择 2 K1
(48位 )(56位 )
循环左移 循环左移
Ci(28位 ) Di(28位 )
置换选择 2 Ki
(48位 )(56位 )
16个子密钥的生成算法
循环左移：
1 1 9 1
2 1 10 2
3 2 11 2
4 2 12 2
5 2 13 2
6 2 14 2
7 2 15 2
8 2 16 1
52
二、数据加密标准 (DES)
数据加密标准
置换选择 1
密钥计算的目的在于产生加密和解密时所需要的 16
个子密钥，记作 K(i)。 初始密钥 Key值为 64位，但
DES算法规定，其中第 8,16,......64位是奇偶校
验位，不参与 DES运算。故 Key 实际可用位数便只
有 56位。即：经过子密钥换位表 PC-1的变换后，
Key 的位数由 64 位变成了 56位，此 56位分为 C0、
D0两部分，各 28位。
53
二、数据加密标准 (DES)
数据加密标准
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 33 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
不考虑各字节第 8位
密钥（ 64位）
C0(28位 ) D0(28位 )
密钥置换选择 1
54
二、数据加密标准 (DES)
数据加密标准
循环移位规则：
轮数,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
密钥置换选择 2
56位分为 C0,D0两部分，然后分别进行第 1次循环左移，得
到 C1,D1,将 C1（ 28位）,D1（ 28位）合并得到 56位，
再经过子密钥换位表 PC-2,便得到了密钥 K1（ 48位）。
子密钥换位表 PC-2给出了选择及选择后的次序，可以看出
去掉了第 9,18,22,25,35,38,43,54位。
55
二、数据加密标准 (DES)
数据加密标准
Ci(28位 ) Di(28位 )
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Ki(48位 )
密钥置换 2
去掉第 9,18，
22,25,35，
38,43,54
位,56位变
成 48位
56
二、数据加密标准 (DES)
数据加密标准
L0R0 ←IP( 明文 )
L1←R 0
R1← L 0??(R0,K1)
L2←R 1
R2← L 1??(R1,K2)
……
L16←R 15
R16← L 15??(R15,K16)
密文 ← IP-1(R16L16)
加密过程,
L0R0 ←IP(<64 位明文 >)
Ln←R n-1
Rn← L n-1??(Rn-1,Kn)
<64位密文 >← IP-1(R16L16)
解密过程,
R16L16 ←IP(<64 位密文 >)
Rn-1←L n
Ln-1←R n??(Ln,Kn)
<64位明文 >← IP-1(L0R0)
57
二、数据加密标准 (DES)
数据加密标准
DES算法
1,处理密钥,
1.1 从用户处获得 64位密钥 Key.(每第 8位为校验位,
为使密钥有正确的奇偶校验,每个密钥要有奇数个, 1”
位,(本文如未特指, 均指二进制位 )
1.2 具体过程,
1.2.1 对密钥实施变换,经过子密钥换位表 PC-1的
变换后, Key 的位数由 64 位变成了 56位 。 (P53 表 4.4)
1.2.2 把变换后的密钥等分成两部分,前 28位记为 C0,
后 28位记为 D0。
58
二、数据加密标准 (DES)
数据加密标准
1.2.3 计算子密钥 (共 16个 ),从 i=1开始 。
1.2.3.1 分别对 Ci-1,Di-1作循环左移来生成 Ci,Di(共 16次 )。
1.2.3.2 串联 Ci,Di,得到一个 56位数, 然后对此数作子密钥
换位表 PC-2变换以产生 48位子密钥 Ki。 (P53 表 4.6)
1.2.3.3 按以上方法计算出 16个子密钥。
2,对 64位数据块的处理：
2,1 把数据分成 64位的数据块, 不够 64位的以适当方式填补 。
2,2对数据块利用 初始变换 IP表作变换 。
2,3 将变换后的数据块等分成前后两部分，前 32位记为 L0,后
32位记为 R0。
59
二、数据加密标准 (DES)
数据加密标准
2,4 用 16个子密钥对数据加密 。
2,4,1 利用 扩展置换 E,扩展 32位的成 48位 （ P54 表 4.7)
2,4,2 用 E{R (i-1)}与子密钥 K(i)作按位 异或运算 。
2,4,3 把所得的 48位数分成 8个 6位数 。 1-6位为 Z 1,7-12位
为 Z 2,…… 43-48位为 Z 8。
2,4,4 用 S密箱里的值替换 Z j。 从 j=1开始 。 S密箱里的值为
4位数, 共 8个 S密箱
2,4,4,1 取出 Z j的第 1和第 6位串联起来成一个 2位数, 记
为 m.。 m即是 Sj密箱里用来替换 Z j的数所在的列数 。
2,4,4,2 取出 Z j的第 2至第 5位串联起来成一个 4位数, 记
为 n。 n即是 Sj密箱里用来替换 Z j的数所在的行数 。
60
二、数据加密标准 (DES)
数据加密标准
2,4,4,3 用 S密箱里坐标 （ n,m） 的值替换 。
2,4,5八个选择函数 Sj(1≤j≤8)的输出拼接为 32位二进制数据
区组, 把它作为 P盒置换 的输入, 得到输出
2,4,6 把得到的结果与 L（ i-1） 作异或运算 。 把计算结果賦给
R（ i） 。
2,4,7 把 R（ i-1） 的值賦给 L（ i）, 完成第 1轮乘积变换 。
2,4,8 从 2,4,1循环执行, 直到 K(16)也被用到 。 2~16轮
2,5 把 R（ 16） 和 L（ 16） 顺序串联起来得到一个 64位数 。 对这
个数实施 2,2变换的 逆变换 IP-1。
61
分组密码运行模式
数据加密标准
ECB（ 电码本）模式：
各明文组独立地以同一密钥加密；传送短数据
62
分组密码运行模式
? CBC（ 密码分组链接）模式：
Cn=Ek[Cn-1⊕ Pn]； 初始向量 V1；
用途：传送数据分组；认证。
63
分组密码运行模式
? CFB（ 密码反馈）模式：利用 CFB,OFB模式，可将
DES转换为流密码。流密码无需填充消息，实时运行。
流密码中明文和密文长度相同。如对字符加密，只要
密钥长度 8bit。
Cn=Pn ⊕S j(E(C n-1))
64
分组密码运行模式
? OFB（ 输出反馈）模式,用分组密码产生一个
随机密钥流，将此密钥流和明文流进行异或可
得密文流。仍然需要一个初始向量（ IV）
65
二、数据加密标准 (DES)
数据加密标准
+ ?
K1
+ ?
K2
+ ?
Kn
DES设计原理
重复交替使用选择函数 S和置换运算 P两种变换
使用 Feistel密码结构 (1967年）
66
混淆 (confusion),使密文与明文的统计独立性
关系复杂化。 使得输出是输入的非线性函数；
用于掩盖明文和密文间的关系。通过代替法
实现，如 S盒。
散布 (diffusion),使每位明文尽可能影响多位
密文。 扩展输出对输入的相关性，尽量使密
文的每一位受明文中多位影响。通过置换法
实现，如 P盒。
单独用一种方法，容易被攻破。
流密码只依赖于混淆；分组密码两者都用。
67
DES算法的脆弱性
DES的半公开性,S盒的原理至今保密，所以不能算作
真正的公开加密算法。
1） 函数构造与作用域：
加密强度取决于函数 f的复杂度 (S,P)和 f的执行次数。
? 64位固定分组，短组模式，易造成密文重复组块
? 有限的函数作用域 ASCII码 0~127
? 子密钥只参与异或简单的运算，有可能损害变换精
度。
2）迭代问题
无法证明迭代 16次最好
迭代在有限的作用域中存在封闭性；迭代次数多不仅
费时，还可能被一次简单的变换所代替。
68
DES算法的脆弱性
3） S盒中的重复因子及密钥多值问题
? S盒设计中利用重复因子，导致 S盒对不同输入
可能产生相同输出，使加密、解密变换的密钥
具有多值性。
? 子密钥长度 48位，只影响 32位输出，因此加密
强度达不到 256，实际只有 232x16=236
? S盒是精心设计的，它有利于设计者破译密码。
? 提高加密强度（如增加密钥长度），系统开销
呈指数增长，除提高硬件、并行处理外，算法
本身和软件技术无法提高加密强度。
69
DES算法存在的问题与挑战
数据加密标准
强力攻击,255次尝试 穷尽搜索 蛮力攻击
差分密码分析法,247次尝试
1991年提出，选择明文攻击。分析明文对
的差值对密文对差值的影响。很有效。
线性密码分析法,243次尝试
1992年提出，已知明文攻击。寻找一个近
似的线性表达式，通过选择充分多的明文 ——
密文对来破解密钥。对 DES更有效。
70
多重 DES及 IDEA
? 二重 DES （ 二个密钥，长度 112位）,
? 加密,C=Ek2[Ek1(P)]
? 解密,P=Dk1[Dk2(C)]
? 要防止中途攻击
? 三重 DES（ 二个密钥）
? 加密,C=Ek1[Dk2 [Ek1(P)]]
? 解密,P=Dk1[Ek2 [Dk1(C)]]
? IDEA加密算法 1992年，瑞士的 Lai和 Massey
128位密钥,8轮，快速，软硬件实现。
71
三、高级加密标准 (AES)
NIST(国家标准技术研究所 )1997年 9月 12日发出征集高
级加密标准的通知 。 1998年 8月首次选出 15个候选者，
1999年 3月遴选出 5个，包括,E2,MARS,RC6、
Rijndael,Twofish。 2000年 10月 2日，美国商务部部长
宣布比利时的 Rijndael算法成为新的 AES。
选择的基本条件：公开；分组单钥，分组长度 128；密
钥可为 128,192,256；可软硬件实现。
优劣标准：安全性；计算效率；内存要求；简便灵活。
此外：适应性；减少专利纠纷；分散目标减少攻击。
AES被开发用于替代 DES,但 NIST预测 Triple DES仍将
在近期作为一种实用的算法，单 DES将逐步退出。
72
一,RSA算法概述
传统密码体制的缺陷,
密钥管理的麻烦,n个用户保存 n*(n-1)/2个密钥 。
不能提供法律证据,不仅要保密还要解决证实问题 。
1976年, 美国学者 Diffie和 Hellman发表了著名论文
,密码学的新方向,, 提出了建立, 公开密钥密码体
制,,若用户 A有加密密钥 ka（ 公开 ）, 不同于解秘
密钥 ka’（ 保密 ）, 要求 ka的公开不影响 ka’的安全 。
若 B要向 A保密送去明文 m,可查 A的公开密钥 ka,若用
ka加密得密文 c,A收到 c后, 用只有 A自己才掌握的解
密密钥 ka’对 x进行解密得到 m。
公开密钥算法
73
一,RSA算法概述
1978年, 美国麻省理工学院 (MIT)的研究小组成员：
李维斯特 ( Rivest),沙米尔 ( Shamir),艾 德 曼
(Adleman)提出了一种基于公钥密码体制的优秀加密
算法 ——RSA算法 。 RSA算法是一种分组密码体制算
法, 它的保密强度是建立在具有大素数因子的合数,
其因子分解是困难的 。 是否是 NP问题尚未确定 。
RSA得到了世界上的最广泛的应用, ISO在 1992年颁
布的国际标准 X.509中,将 RSA算法正式纳入国际标准 。
1999年美国参议院已通过了立法, 规定电子数字签
名与手写签名的文件, 邮件在美国具有同等的法律效
力 。
公开密钥算法
74
数论知识简介
? 互素：若 gcd(a,b)=1,则整数 a和 b互素。
? 定义：若 a?x mod n =1,则称 a与 x对于模 n互
为逆元。
? 用 Euclid算法求乘法逆元
若 a和 n互素，则 a在模 n下有逆元。
? Euler函数,φ(n)=与 n互素的、小于 n的正整数
的个数,n>1。 例：
φ(3)= φ(4) = φ(6) =2,φ(5)=4,φ(7) =6
φ(12)=6
75
数论知识简介
模运算性质,同余
? 模运算满足自反性、对称性、传递性；
a=a mod n；
若 a=b mod n,则 b=a mod n；
若 a=b mod n,b=c mod n,则 a=c mod n
? 若 a mod n=b mod n,则 (a-b)mod n=0；
[(a mod n) +(b mod n)]mod n=(a + b) mod n；
- - ；
* * ；
例,152 mod 12 =(3*3) mod 12=9
76
? 若 n是素数，则 φ(n)=n-1
若 n=p*q,p,q是素数，则 φ(n)=(p-
1)*(q-1)
例,φ(21)= φ(3*7)=2*6=12
? Fermat小定理：若 m是素数，且 a不是 m
的倍数，则 am-1 mod m=1。
或者：若 m是素数，则 am mod m=a
例,46 mod 7=4096 mod 7=1
47 mod 7=16384 mod 7=4
77
? Euler定理,a φ(n) mod n =1
推论：若 a与 n互素，则 a与 a φ(n)-1 互为
逆元。
例,a=4,n=7,φ(7)=6，
a φ(7)-1 =45=1024
所以,4和 1024在模 7下互为逆元。
验证,4x1024 mod7 =1
78
求乘法逆元
Function Euclid(d,f) //求 d在模 f下的逆元
1) (x1,x2,x3)<-(1,0,f);(y1,y2,y3)<-(0,1,d);
2) If y3=1 then print,逆元是, y2 else print
“无逆元, ; End.
3) Q=[x3/y3]
4) (t1,t2,t3)<-(x1-Q*y1,x2-Q*y2,x3-Q*y3)
5) (x1,x2,x3)<-(y1,y2,y3);
6) (y1,y2,y3)<-(t1,t2,t3)
7) Go to 2)
79
高次幂剩余的运算
公开密钥算法
要计算 gn mod p,因 g,n,p都是大数而
不能采用先高次幂再求剩余的方法来处理,
而要采用平方取模的算法, 即每一次平方或
相乘后, 立即取模运算 。
欧几里德算法
欧几里德算法可以迅速地找出给定的两
个整数 a和 b的最大公因数 gcd（ a,b）, 并可
判断 a与 b是否互素, 因此该算法可用来寻找
加密密钥和解密密钥 。
80
X r mod p 的快速算法流程图
A<-x
B<-r
C<-1
B=0
输出 C
B mod 2=0
B<- B/2
A<- A*A mod p
B<- B-1
C<-C*A mod p
Y
N N
Y
81
一,RSA算法概述
公开密钥算法
每个合数都可以唯一地分解出素数因子
6 = 2 ·3
999999 = 3·3·3·7·11·13·37
27641 = 131·121
从 2 开始试验每一个小于等于 √27641 的素数。
素数：只能被 1和它本身整除的自然数；否则为合数。
整数 n的十进制位数 因子分解的运算次数 所需计算时间（每微秒一次）
50 1.4x1010 3.9小时
75 9.0x1012 104天
100 2.3x1015 74年
200 1.2x1023 3.8x109年
300 1.5x1029 4.0x1015年
500 1.3x1039 4.2x1025年
82
素数的检验
素数的产生
目前, 适用于 RSA算法的最实用的办
法是概率测试法 。 该法的思想是随机产
生一个大奇数, 然后测试其是否满足条
件, 如满足, 则该大奇数可能是素数,
否则是合数 。 素数定理说明素数有无穷
多个, 同时也说明通过随机产生一个大
奇数来判断其素性是具有实用性的 。
83
素数的检验
? Wilson定理：
P是素数 ?? (P -1)! Mod P =-1
当 P较大时，很费时间，无实际价值。
? Rabin-Miller方法 概率检验
Witness(a,n)
/* 将 n-1表示为 bk b k-1… b0的形式
n是待检验的数,a是小于 n的整数。若返
回 True,则 n肯定不是素数；若返回 False,则
n有可能是素数。 */
84
Rabin-Miller方法
{
d=1
for i=k down to 0 {
x=d;d= (d? d) mod n;
if d=1 & (x<>1) &(x<>-1) return True;
if bi=1 then d=(d?a) mod n}
if d<>1 then return True ;
return False ;
}
对于 s个不同的 a,重复调用此算法，每次返回 False,则 n
是素数的概率至少为 1-2-s
85
二,RSA算法的实现
公开密钥算法
RSA加密算法的过程
1,取两个随机大素数 p和 q（ 保密 ）
2,计算公开的模数 n=p*q(公开 )
3,计算秘密的欧拉函数 ?(n) =（ p-1)*(q-1)（ 保密 ）, 丢弃
p和 q,不要让任何人知道 。
4,随机选取整数 e,满足 gcd(e,?(n))=1(公开 e加密密钥 )
5,计算 d满足 de≡1(mod ?(n))(保密 d解密密钥 )
6,将明文 x（ 按模为 r自乘 e次幂以完成加密操作, 从而产生
密文 y（ X,Y值在 0到 n-1范围内 ） 。 Y=xe mod n
7,解密：将密文 y按模为 n自乘 d次幂 。 X=Yd mod n
86
二,RSA算法的实现
公开密钥算法
例设 p=43,q=59,r=p?q=43*59=2537,?(r)=(p-1)(q-1) =42*58
=2436,取 e=13,求 e的逆元 d
解方程 d ? e = 1 mod 2436
2436 =13* 187+ 5,13= 2* 5+ 3
5= 3+ 2,3= 2+ 1
所以 1= 3- 2, 2= 5- 3,3 =13- 2* 5
5 =2436- 13* 187
所以,1= 3- 2= 3-（ 5- 3） = 2* 3- 5
=2*（ 13- 2* 5） - 5= 2 *13- 5* 5
=2* 13- 5*（ 2436 -13 *187）
=937* 13- 5* 2346
即 937* 13 ≡ 1 mod 2436
取 e= 13 时 d= 937
87
二,RSA算法的实现
公开密钥算法
若有明文 public key encryptions
先将明文分块为
pu bl ic ke nc ry pt io ns
将明文数字化令 a b z 分别为 00 01 25 得
1520 0111 0802 1004 2404
1302 1724 1519 0814 1418
利用加密可得密文
0095 1648 1410 1299 1365
1379 2333 2132 1751 1289
88
公开密钥算法
关于素数的分布
1 - 100 25
101 - 200 21
201 - 300 16
301 - 400 16
401 - 500 17
501 - 600 14
601 - 700 16
701 - 800 14
801 - 900 15
901 - 1000 14
素数定理：当 X变得很大时，从 2到 X区间
的素数数目 ?(X)与 X/ln(X)的比值趋近于 1
，即
?(X)
X/ln(X) = 1
limx??
X ?(X) X/ln(X) ?(X)X/ln(X)
1000 168 145 1.159
10,000 1,229 1,086 1.132
100,000 9,592 8,686 1.104
1,000,000 78,498 72,382 1.084
10,000,000 664,579 620,421 1.071
100,000,000 5,761,455 5,428,681 1.061
1,000,000,000 50,847,478 48,254,942 1.054
89
二,RSA算法的实现
公开密钥算法
在 2到 X的区间中，随机选择一个值为素数的概率
近似等于 ?(X)/(X-1)。 可以证明，在找到一个素数
之前，平均要进行 (X-1)/ ?(X)≈LN(X)次实验。
大数的运算
上百位大数之间的运算是实现 RSA算法的基础,
因此程序设计语言本身提供的加减乘除及取模算法
都不能使用，否则会产生溢出，必须重新编制算法
。在编程中要注意进位和借位，并定义几百位的大
数组来存放产生的大数。
90
RSA 的安全性
公开密钥算法
依赖于大数分解, 但是否等同于大数分解一直未能
证明 。 不管怎样, 分解 n是最显然的攻击方法 。
1994年 4月 26日, 美国各大媒体报道：由 RSA发明
人在 17年前出的 129位数字已被因子分解, 并破解
了附带的密语：
The magic words are squeamish ossifrage.
目前, 已能分解 140位十进制的大素数 。 因此,
模数 n必须选大一些 。
RSA最快的情况也比 DES慢上 100倍, 无论是软件还
是硬件实现 。 速度一直是 RSA的缺陷 。 一般只用于
少量数据加密 。
91
RSA算法的脆弱性
公开密钥算法
1) 不能证明 RSA密码破译等同于大数因子分解
2) 速度问题 提高 p?q将使开销指数级增长
3) 至少有 9个明文, 加密后不变，即 me mod n=m
4) 普通用户难于选择 p,q。 对 p,q的基本要求：
? p,q不相同，即不要太接近，又不能差别太大
? p-1,q-1都有大素数因子，增加猜测 φ(r) 难度
? Gcd( p-1,q-1)应当小
92
RSA算法的脆弱性
公开密钥算法
5) P,q选择不当，则变换周期性、封闭性而泄密
例,p=17,q=11,e=7,则 n=187。 设 m=123,则
C1=1237 mod 187=183
C2=1837 mod 187=72
C3=727 mod 187=30
C4=307 mod 187=123
明文 m经过 4次加密，恢复成明文。
总之,RSA对用户要求太苛刻，密钥不能常更换。
93
其它公钥密码体制
? 背包体制 1978年提出 5年后被 Shamir破解
? ElGamal 体制 1985年 基于有限域上计算离
散对数难解性，已用于 DSS(数字签名标准）
例,3x mod 17=5,解得,x=6
3x mod 13=7,无解
? 椭圆曲线体制 (ECC) 1985年 基于离散对数
优点：安全性高；密钥短；灵活性好。
同等安全下的密钥长度：
RSA:512 1024 2048 21000
ECC:106 160 211 600
94
ElGamel 加密体制：
选大素数 P及其本源根 g,p,g公开；
随机选一整数 x作为私钥 (保密 )；
计算 y=gx mod p ; 将 y作为公开密钥。
? 加密过程
在公钥数据库中查找获取用户的公钥 y；
在 0 ~ p-1间取整数 k0; 计算下式并发送 C1和 C2:
K=yk0 mod p,C1=gk0 mod p,C2=K?m mod p；
? 解密过程
计算 K=C1x mod p
明文 m=C2 ?K-1 mod p
