CS计算机代考程序代写 algorithm 第六章 密码学

第六章 密码学

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
第7章 加密编码
加密编码的基础知识
数据加密标准DES
国际数据加密算法（IDEA〕
公开密钥加密法
通信网络中的加密
信息安全和确认技术

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.1 加密编码的基础知识
人们希望把重要信息通过某种变换转换成秘密形式的信息。转换方法可以分为两大类：
隐写术，隐蔽信息载体——信号的存在，古代常用。
编码术，将载荷信息的信号进行各种变换使它们不为非授权者所理解。
在利用现代通讯工具的条件下，隐写术受到很大限制，但编码术却以计算机为工具取得了很大的发展。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.1.1 加密编码中的基本概念
真实数据称为明文M
对真实数据施加变化的过程称为加密EK
加密后输出的数据称为密文C
从密文恢复出明文的过程称为解密DK
完成加密和解密的算法称为密码体制。
变换过程中使用的参数叫密钥K。
加密时使用的密钥与解密时使用的密钥可以相同（单密钥），也可以不同（双密钥）

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
安全性
如果求解一个问题需要一定量的计算，但环境所能提供的实际资源却无法实现它，则称这种问题是计算上不可能的；
如果一个密码体制的破译是计算上不可能的，则称该密码体制是计算上安全的。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
保密性
即使截获了一段密文C，甚至知道了与它对应的明文M，破译者要从中系统地求出解密变换仍然是计算上不可能的。
破译者要由截获的密文C系统地求出明文M是计算上不可能的。

保密性只要求对变换DK（解密密钥）加以保密，只要不影响DK的保密，变换EK可以公布于众。
EK DK
M C M

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
真实性
对于给定的C，即使密码分析员知道对应于它的明文M，要系统地求出加密变换EK仍然是计算上不可能的。
密码分析员要系统地找到密文C’，使DK（C’）是明文空间上有意义的明文，这在计算上是不可能的。

EK DK
M C M
真实性只要求变换EK（加密密钥）保密，变换DK可公布于众。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
密码体制（1）
对称（单密钥）体制：加密密钥和解密密钥相同或者很容易相互推导出。

由于我们假定加密方法是众所周知的，所以这就意味着变换EK和DK很容易互相推导。因此，如果对EK和DK都保密，则保密性和真实性就都有了保障。但这种体制中EK和DK只要暴露其中一个，另一个也就暴露了。所以，对称密码体制必须同时满足保密性和真实性的全部要求。用于加密私人文件。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
非对称（双密钥）密码体制：加密密钥和解密密钥中至少有一个在计算上不可能被另一个导出。因此，在变换EK或DK中有一个可公开而不影响另一个的保密。

通过保护两个不同的变换分别获得保密性和真实性。保护DK获得保密性，保护EK获得真实性。公开密钥体制即是这种。接收者通过保密自己的解密密钥来保障他接收信息的保密性，但不能保证真实性，因为任何知道他的加密密钥的人都可以将虚假消息发给他。发送者通过保密自己的解密密钥来保障他发送信息的真实性。但任何知道他的加密密钥的人都可以破译消息，保密性不能保证。用于数字签名。
密码体制（2）

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

EB DB
M C M
保障保密性
保障真实性
M C M
DA EA
DA EB
DB EA
M C’ C C’ M
保密性
真实性
保密性与真实性

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
密码分类
根据加密明文数据时的加密单位的不同，分为分组密码和序列密码两大类。
分组密码：设M为密码消息，将M分成等长的连续区组M1,M2,…，分组的长度一般是几个字符，并且用同一密钥K为各区组加密，即

序列密码：若将M分成连续的字符或位m1,m2,…，并用密钥序列K＝K1K2…的第i个元素给mi加密，即
常用分组密码。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.1.2 加密编码中的熵概念
密码学和信息论一样，都是把信源看成是符号（文字、语言等）的集合，并且它按一定的概率产生离散符号序列。在第二章中介绍的多余度的概念也可用在密码学中，用来衡量破译某一种密码体制的难易程度。多余度越小，破译的难度就越大。可见对明文先压缩其多余度，然后再加密，可提高密文的保密度。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
安全性
在截获密文后，明文在多大程度上仍然无法确定。即如果无论截获了多长的密文都得不到任何有关明文的信息，那么就说这种密码体制是绝对安全的。
所有实际密码体制的密文总是会暴露某些有关明文的信息。被截获的密文越长，明文的不确定性就越小，最后会变为零。这时，就有了足够的信息唯一地决定明文，于是这种密码体制也就在理论上可破译了。
理论上可破译，并不能说明这些密码体制不安全，因为把明文计算出来的时空需求也许会超过实际上可供使用的资源。在计算上是安全的。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
熵概念
密码系统的安全问题与噪声信道问题进行类比。噪声相当于加密变换，接收的失真消息相当于密文，破译者则可类比于噪声信道中的计算者。
随机变量的不确定性可以通过给予附加信息而减少。正如前面介绍过条件熵一定小于无条件熵。例如，令X是32位二进制整数并且所有值的出现概率都相等，则X的熵H(X)＝32比特。假设已经知道X是偶数，那么熵就减少了一位，因为X的最低位肯定是零。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
疑义度
对于给定密文，密钥的疑义度可表示为

对于给定密文，明文的疑义度可表示为

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
破译者的任务是从截获的密文中提取有关明文的信息或从密文中提取有关密钥的信息
I(M；C)＝H(M)－H(M/C)
I(K；C)＝H(K)－H(K/C)
H(M/C)和H(K/C)越大，破译者从密文能够提取出有关明文和密钥的信息就越小。
对于合法的接收者，在已知密钥和密文条件下提取明文信息：H(M/C,K)＝0

I(M；CK)＝H(M)－H(M/C,K)＝H(M)
疑义度

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
因为 H(K/C)＋H(M/K,C)
＝H(M/C)＋H(K/M,C)（M和K交换）
 H(M/C) （熵值H(K/M,C)总是大于等于零）
H(M/C,K)＝0，上式得 H(K/C)  H(M/C)
即已知密文后，密钥的疑义度总是大于等于明文的疑义度。我们可以这样来理解，由于可能存在多种密钥把一个明文消息M加密成相同的密文消息C，即满足

的K值不止一个。但用同一个密钥对不同明文加密而得到相同的密文则较困难。

疑义度

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
又因为 H(K)  H(K/C)  H(M/C)，
则
上式说明，保密系统的密钥量越少，密钥熵H(K)就越小，其密文中含有的关于明文的信息量I(M;C)就越大。至于破译者能否有效地提取出来，则是另外的问题了。作为系统设计者，自然要选择有足够多的密钥量才行。

疑义度

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.2 数据加密标准DES
——私密密钥加密法
1977年7月美国国家标准局公布了采纳IBM公司设计的方案作为非机密数据的正式数据加密标准（DESData Encryption Standard）。DES密码是一种采用传统加密方法的区组密码，它的算法是对称的，既可用于加密又可用于解密。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.2.1 换位和替代密码
换位密码：对数据中的字符或更小的单位（如位）重新组织，但并不改变它们本身。
替代密码：改变数据中的字符，但不改变它们之间的相对位置。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
P盒
0 15 15 0
0 14 14 0
0 13 13 0
0 12 12 0
输 0 11 11 0 输
0 10 10 0
入 0 9 9 0 出
0 8 8 0
数 0 7 7 0 数
0 6 6 0
据 0 5 5 1 据
0 4 4 0
0 3 3 0
0 2 2 0
1 1 1 0
换位盒(P盒)

输入
第i位

输出
第j位

15
14
13
12
11
10
9
8
7
6
5
4
3
2
1

7
4
12
10
15
2
11
1
9
14
6
3
8
13
5

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
S盒
n=3 2n=8 2n=8

0 0
0 1 1 1
2 2
1 3 3 1
4 4
1 5 5 1
6 6
7 7
替代盒（S盒）

输入

输出

101
010
100
111
000
110
011
001

000
001
010
011
100
101
110
111

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

0 P s P s P s P 0
0 1
0 0
0 0
输 0 s s s 0 输
0 1
入 0 1 出
0 s s s 1
数 0 1 数
0 0
据 0 s s s 0 据
0 0
0 1
0 s s s 1
1 0
 
P盒和S盒的结合使用

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.2.2 DES密码算法
DES密码就是在上述换位和替代密码的基础上发展的。
将输入明文序列分成区组，每组64比特。
64比特的密钥源循环移位产生16个子密钥

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

图7-7 密码运算

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

密钥表计算

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.2.3 DES密码的安全性
DES的出现在密码学史上是一个创举。以前的任何设计者对于密码体制及其设计细节都是严加保密的。而DES算法则公开发表，任人测试、研究和分析，无须通过许可就可制作DES的芯片和以DES为基础的保密设备。DES的安全性完全依赖于所用的密钥。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
弱密钥
DES算法中每次迭代所用的子密钥都相同，即 K1＝K2＝…＝K16 ，如11…1，此时

DESk(DESk(x))＝x，DESk－1(DESk－1(x))＝x
即以k对x加密两次或解密两次都恢复出明文。其加密运算和解密运算没有区别。
而对一般密钥只满足

DESk－1(DESk(x))＝DESk(DESk－1(x))＝x

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
半弱密钥
给定的密钥k，相应的16个子密钥只有两种图样，且每种都出现8次。如1010…10
半弱密钥的特点是成对地出现，且具有下述性质：若k1和k2为一对互逆的半弱密钥，x为明文组，则有

DESk1(DESk2(x))＝DESk2(DESk1(x))＝x
称k1和k2是互为对合的。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
问题
DES的密钥短了些
选择长的密钥会使成本提高、运行速度降低。
新算法很可能要采用128比特密钥。
实现DES算法的产品有：
设计专用LSI器件或芯片；
用现成的微处理器实现；
只限于实现DES算法；
可运行各种工作模式。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.2.4   DES密码的改进
尽管DES算法十分复杂，但它基本上还是采用64比特字符的单字母表替换密码。当同样的64比特明文块进入编码器后，得到的是同样的64比特的密文块。破译者可利用这个性质来破译DES。
改进方法：密码块链接、密码反馈方式

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
密码块链接
M1 M2 M3 M4 C1 C2 C3 C4

V # # # # 密钥 D D D D
解密箱

加密箱

密钥 E E E E … V # # # # …
异或
 
C1 C2 C3 C4 M1 M2 M3 M4

(a) (b)

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
64位移位寄存器 64位移位寄存器

C2 C3 C4 C5 C6 C7 C8 C9 C2 C3 C4 C5 C6 C7 C8 C9
 
 
64
  8

密钥 E 加密箱 C10 密钥 E 加密箱 C10
 

 
选择最左字节 选择最左字节
 
  8

M10 # C10 C10 # M10
  8
(a) (b)
密码反馈方式

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.3 国际数据加密算法（IDEA）
尽管一次加密的DES仍然广泛应用于保密中，但专家们对DES不安全的原因作了大量的分析，认为这种方法刚被发明时是很适用的，而现在已不再能满足需要。人们开始寻求更安全的块密码，曾提出了许多算法，其中最令人感兴趣最重要的就是IDEA（Intrenational Data Encryption Algorithm），即国际数据加密算法。
IDEA由瑞士的两名科学家于1990年提出，最早称作PES（Proposed Encryption Standard），后改称为IDEA。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.3.1 算法原理
采用下述几种基本运算：

（1） 逐位mod 2和，记作⊙；
（2） mod 216（即65536）整数加，记作 ；
（3）mod (216＋1)（即65537）整数乘，记作 ；
（4）三个运算中任意两个运算不满足分配律。例如：a (b c) ≠(a b) (a c)
（5）三个运算中任意两个运算间不满足结合律。例如： a (b⊙c) ≠(a b)⊙c

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
实现时需考虑
（1）基本构件——乘/加单元：实现16比特为字长的非线性S盒，如图所示。它是IDEA实现中的关键非线性构件。通过8轮迭代，能够完成更好的扩散和混淆。研究表明，为实现完善混淆至少需要4轮迭代。
（2）硬件：加密、解密运算相似，差别是密钥时间表，类似于DES，具有对合性，可用同一器件实现。由于采用规则的模块结构，易于设计ASIC实现。
（3）软件：采用子段结构：以16比特为字长进行处理。采用简单运算，三种运算易于编程实现加、移位等。
F1 16 F2 16

K5

K6

 

G1 16 G2 16

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.3.2 加密解密过程
输入和输出字长为64比特，密钥长128比特，8轮迭代体制。最后经过一个输出变换给出密文。IDEA可用于各种标准工作模式。
它由两部分组成：一个是对输入64比特明文组的8轮迭代产生64比特密文输出；另一个是由输入的128比特会话密钥，产生8轮迭代所需的52个子密钥，共52×16比特。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
64比特明文x
x1 x2 x3 x4
K1
迭代1 K6
w11 w12 w13 w14
K7
迭代2 K12
w21 w22 w23 w24
w71 w72 w73 w74
K43
迭代8 K48
w81 w82 w83 w84
K49
输出变换 K52
y11 y12 y13 y14

密文
IDEA算法框图

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
x1 x2 x3 x4

K1 K3
K2 K4
⊙ ⊙
 

乘加
单元
K5 K6
 

⊙ ⊙ ⊙ ⊙
 
w11 w12 w13 w14

图7-15
w1 w2 w3 w4

K49 K51
K50 K52
 

图7-16 IDEA的输出变换

128比特密钥K

子密钥生成器
16 …
K1 K52

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
K(128比特)

 K1  K2  K3  K4  K5  K6  K7  K8 
K15K16K9K10K11K12K13K14K15
K22K23K24K17K18K19K20K21
K28K29K30K31K32K25K26K27K28
K35K36K37K38K39K40K33K34
K41K42K43K44K45K46K47K48
K49K50K51K52
 
图7-17 IDEA的子密钥
 

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.3.3 算法的安全性
如果采用穷搜索破译，要求进行2128≈1038次试探。若每秒可完成100万次加密，需1013年；若用1024个ASIC芯片阵需要一天。有关专家研究表明，IDEA算法没有似DES意义下的弱密钥，8轮迭代使得没有任何捷径破译，在差分和线性攻击下是安全的。当然若将字长由16比特增加到32比特，密钥相应长256比特，采用232模加，232＋1模乘，则可进一步强化IDEA。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.4 公开密钥加密法
前面介绍的秘密密钥加密法，算法公开，密钥是保密的（对称密钥）。
如果要进行通信，必须在这之前把密钥通过非常可靠的方式分配给所有接收者，这在某些场合是很难做到的。
因而提出了公开密钥加密法PKC（Public Key Cryptography）

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
密 钥
使用两个不同密钥（非对称密钥体制）；
一个公开（公钥），另一个为用户专用（私钥）；
通信双方无需事先交换密钥就可进行保密通信；
要从公钥或密文分析出明文或私钥，在计算上是不可能的。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
应 用
保密通信：

多个用户将信息传给某用户，可用该用户的公钥加密，唯有该用户可用自己的私钥解读。
数字签名：

用自己的私钥加密信息，而以公钥作为解密密钥，用来确认发送者。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
PKC算法的关键
——加密函数y＝F(x)的单向性
加密计算容易：对任意给定的x值，容易计算y＝F(x)的值；
破译难：已知F和y，不可能求出对应的x值；
用私钥容易解密：若知道F的某种特殊性质（窍门trapdoor ），就容易计算出x值。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
构造和使用
使用者构造出单向函数F（公钥）和它的逆函数F－1（私钥）。
破译者：已知F和密文不能推导出F－1或明文；
接收者：用窍门信息（解密密钥Kd）简单地求解x＝F－1Kd(y)。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.4.1 公开密钥密码体制
——保密通信

公开加密密钥 秘密解密密钥
B(e，n) B(d，n)
A(e，n) A(d，n)
B发到A B M fA(e，n) C A
A接收B A C fA(d，n) M
A发到B A M fB(e，n) C B
B接收A B C fB(d，n) M

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.4.1 公开密钥密码体制
——数字签名
公开加密密钥 秘密解密密钥
B(e，n) B(d，n)

A(e，n) A(d，n)
B发到A B M fB(d，n) S fA(e，n) C A
A收到B A C fA(d，n) S fB(e，n) M

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
RSA由来
理论基础
密钥设计
加密解密
实现步骤

7.4.2 RSA密码体制

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
RSA密码体制（1）
RSA由来：RSA体制是根据PKC算法由美国麻省理工学院（MIT）的研究小组提出的，该体制的名称是用了三位作者（Rivest，Shamir和Adleman）英文名字的第一个字母拼合而成。
理论基础：利用数论

正：要求得到两个大素数（如大到100位）的
乘积在计算机上很容易实现。
逆：但要分解两个大素数的乘积在计算上几乎
不可能实现。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
密钥设计：两个密钥：公钥（e，n）

私钥（d，n）
加密解密：

加密时：
解密时：
RSA密码体制（2）

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
实现步骤：
选取两个很大的素数p和q，令模数
求n的欧拉函数

并从2至[(n)－1]中任选一个数作为加密指数e；
解同余方程

求得解密指数d；
(e，n)即为公开密钥，(d，n)即为秘密密钥。

RSA密码体制（3）

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
例题－保密通信
例7-1 在RSA方法中，令p＝3，q＝17，取e＝5，试计算解密密钥d并加密M＝2。
解：n＝p×q＝51
(n)＝(p－1)×(q－1)＝32
(5×d) mod 32＝1，可解得d＝13
加密 y＝xe mod n＝25 mod 51＝32
解密 yd mod n＝3213 mod 51＝2＝x
若需发送的报文内容是用英文或其他文字表示的，则可先将文字转换成等效的数字，再进行加密运算。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
RSA公开密钥体制用于数字签名
发送者A用自己的秘密解密密钥(dA，nA)计算签名；
用接收者B的公开加密密钥(eB，nB)再次加密：
接收者B用自己的秘密解密密钥(dB，nB)解密：
查发送者A的公开密钥(dA，nA)计算，恢复出发送者的签名，认证密文的来源。

(dA，nA) (eB，nB) (dB，nB) (eA，nA)
Mi Si S Si Mi

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
例题－数字签名
例7-2 用户A发送给用户B一份密文，用户A用首字母B＝02来签署密文。用户A知道下列三个密钥：
A B
公开密钥(e，n) (7，123) (13，51)
秘密密钥(d，n) (23，123)
A计算他的签名：

再次加密签名：

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
接收者B必须恢复出02＝B认证他接收的密文。接收者也知道三个密钥：
A B
公开密钥(e，n) (7，123) (13，51)
秘密密钥(d，n) (5，51)
B用户用自己的秘密解密密钥一次解密：

再用A用户的公开密钥解密：

B用户可以确认：该签名是由A发出——用A公钥可解读；
该签名是发给自己的——用了B的公钥。
例题－数字签名（续）

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
安全性和速度
n要大，破译512比特（154位） RSA算法体制与破译64比特的单密钥体制相当；
目前n＝512比特在短期内十分安全，但已有一定威胁，很快可能要采用768比特甚至1024比特；
RSA算法的硬件实现速度很慢，最快也只有DES的1/1000，512比特模下的VLSI硬件实现只达64kb/s；软件实现的RSA的速度只有DES的软件实现的1/100。
在速度上RSA无法与对称密钥体制相比，因而RSA体制多用于密钥交换和认证。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
有时需要确认一段报文的出处，而报文本身不需加密。如用公开密钥算法加密整段报文，则加密时间长，而且报文传输和存储的开销也大。
采用报文摘要(message digest) ，即从一段报文中计算出较短的报文摘要，然后在报文摘要上签名，并将签名的摘要和报文一起发送。

7.4.3 报文摘要

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
报文摘要的特点
该方案基于单向散列(Hash)函数的思想；
给出报文P就易于计算出报文摘要MD(P)；
只给出MD(P)，几乎无法找出P；
无法生成两条具有同样报文摘要的报文；
如果有人替换了报文P，当接收者计算MD(P)时就得不到相同的结果。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
添加1~512比特 报文长度K mod 264
L×512比特＝N×32比特
K比特
报文 100…0
 
512比特 512比特 512比特 512比特
Y0 Y1 … Yq … YL-1
 
512 512 512 512
ABCD H MD5 H MD5 H MD5 HMD5
128 128 128 128 128比特
报文摘要
采用MD5算法产生报文摘要

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
MDq 128
Yq
512 A B C D 32
ABCDfF (ABCD，Yq，T[1..16])
  A B C D
ABCDfG (ABCD，Yq，T[17..32])
  A B C D
ABCDfH (ABCD，Yq，T[33..48])
  A B C D
ABCDfI (ABCD，Yq，T[49..64])
 
 
 
＋ ＋ ＋ ＋
MDq+1 128
处理512比特块
的算法HMD5

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

A B C D
 
g
 
＋
  32
＋ X[k]
 
＋ T[i]
 
  CLSs
 
＋
AB＋CLSs{A＋g(BCD)＋X[k]＋T[i]}
16次

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
表7-12 基本函数的逻辑运算关系
轮

基本函数g

g(B,C,D)

fF

F(B,C,D)

fG

G(B,C,D)

fH

H(B,C,D)

fI

I(B,C,D)

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
表7-13 基本函数的真值表
B

C

D

F

G

H

I

0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

0
1
0
1
0
0
1
1

0
0
1
0
0
1
1
1

0
1
1
0
1
0
0
1

1
0
0
1
1
1
0
0

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
MD5的安全性
安全的hash函数在设计时必须满足两个要求：其一是寻找两个输入得到相同的输出值在计算上是不可行的，这就是通常所说的抗碰撞的；其二是找一个输入，能得到给定的输出在计算上是不可行的，即不可从结果推导出它的初始状态。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
MD5是在国内外有着广泛应用的hash函数算法，它曾一度被认为是非常安全的。然而，2004年山东大学的王小云教授在国际密码学会议（Crypto 2004）上公布了MD系列算法的破解结果，可以很快找到MD5的“碰撞”，就是两个文件可以产生相同的报文摘要。
美国国家技术与标准局（NIST）对此发表专门评论，安全性暂时没有问题，但随着技术的发展，需要换用其他更长更安全的算法替代。

MD5的安全性

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.4.4 公开密码体制的优缺点
减少了密钥数量。在n个用户的密码系统中，采用对称密码体制，需要n(n-1)/2个密钥。采用公钥密码体制，只需要n对密钥，而真正需要严加保管的只有用户自己的秘密密钥；
彻底消除了密钥在分送过程中被窃的可能性，大大提高了密码体制的安全性。
便于实现数字签名，完满地解决了对发方和收方的证实问题，彻底解决了发、收双方就传送内容可能发生的争端，为在商业上广泛应用创造了条件。
计算较复杂，加密和解密的工作速率远低于对称密码体制。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.5 通信网络中的加密
分类：模拟加密、数字加密
模拟话音的特性：时间、频率和幅度
模拟加密方法：时间置乱、频率置乱、幅度置乱；一维置乱、二维置乱
数字加密方法：比特置乱、比特掩盖
模拟加密简单，但保密度较差；
数字加密，要求取样率较高。
可结合使用。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
链路加密
  数据 数据
节点
密钥1
密钥1
密钥2
密钥2
节点
节点
明文

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
节点加密
节点 节点 节点
加密数据 加密数据
数据 （密钥1） （密钥2） 数据

密钥1 密钥1 密钥2
密钥2
（安全模块） （安全模块） （安全模块）
数据 数据

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
端对端加密
节点
密钥1 节点 节点
密钥1
数据
数据

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.6 信息安全和确认技术
信息资源共享的限制
信息资源的保护

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.6.1 信息安全的基本概念
认证业务：提供某种方法来证实某一声明是正确的。例口令
访问控制：控制非授权的访问。例防火墙。
保密业务：对未授权者保护信息，例数据加密
数据完整性业务：对安全威胁所采取的一类防护措施，
不可否认业务：提供无可辩驳的证据来证明曾经发生过的交换。采用数字签名技术。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.6.2 数字签名
伪造：接收方伪造一份来自某一发送方的文件；
篡改：接收方篡改接收到的文件或其中的数据；
冒充：网络中任一用户冒充另一用户作为接收方或发送方；
否认：发送/接收方不承认曾发送/接收过某一文件。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
手迹签名代替方案
接收者可以确认发送者的身份；
发送者以后不能否认文件是他发的；
接收者自己不能伪造该文件。

第一个条件是必须的，比如当一位顾客通过计算机发订货单，向一家银行订购一吨黄金，银行计算机需要证实发出订购要求的计算机确实属于付款的公司。第二个条件用于保护银行不受欺骗。假设银行为该顾客买入了这吨黄金，但金价随后立即暴跌，狡猾的顾客可能会控告这家银行，声称自己从未发出过任何订购黄金的订单。第三个条件用来在下述情况下保护顾客，如金价暴涨，银行伪造一个文件，说顾客只要买一条黄金而不是一吨黄金。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
数字签名的优点
数字签名可以通过计算机网络使地理位置不同的用户实现签名；
数字签名既可有手写签名那样的可见性，又可将签名存储于计算机系统之中；
数字签名与整个文件的每一组成部分都有关，从而保证了不变性，而手写签名的文件则可以改换某一页内容；
数字签名可以对一份文件的一部分进行签署，这是手写签名所不能做到的；手写签名一般要经过专家的鉴定才能确认，而在一个具有良好数字签名方案的网络内，接收方可以立即识别接收的文件中的签名的真伪。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
秘密密钥的数字签名
 
 
A 2. X(A＋D＋P) BB 4. X(A＋D＋P) B

 
3. X(A＋D＋P)

1. KA(P) 5. KB(A＋D＋P)

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
A用户的计算机 传输线 B用户的计算机

P A的私有 B的公开 B的私有 A的公开 P
密钥 DA 密钥 EB 密钥 DB 密钥 EA
 
 

DA(P) EB(DA(P)) DA(P)

公开密钥的数字签名

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
7.6.3 防火墙
所谓防火墙就是一个或一组系统，用来在两个或多个网络间加强访问控制。它是一个网络与其它网络之间的可控网关，通常它置于一个私有的、有确认的网络和公开的Internet之间。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
主要技术
包过滤（Packet Filter），该技术是在网络层中对数据包实施有选择的通过。
应用网关（Application Gateway），这是建立在网络应用层上的协议过滤技术。
代理服务（Proxy Service），这是设置在Internet防火墙网关的专用应用级代码。

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
第7章复习
加密编码的基本知识
加密编码的基本概念：
明文、密文、加密、解密、破译、密钥、密码体制
保密性、真实性
对称密钥体制、非对称密钥体制
分组密码、序列密码
加密编码中的熵概念

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
两种加密体制的比较
私密加密体制中，采用对称密钥算法，加密算法公开，安全性在于对密钥的保护；
公开加密体制中，采用非对称密钥算法，加密算法公开，其中的一个密钥也公开，安全性在于对另一个密钥的保护；

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
数据加密标准DES
换位和替代密码
DES密码算法
DES密码的安全性
DES密码的改进

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
国际数据加密算法IDEA
算法原理
加密解密过程
算法的安全性

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
公开密钥加密法
公开密钥密码体制
RSA密码体制
报文摘要
由P计算MD(P)简单，反之复杂
不同P不能生成相同的MD(P)
相同的P生成相同的MD(P)

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

*
普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著
数字签名
密码密钥的数字签名
公开密钥的数字签名

普通高等教育“十五”国家级规划教材《信息论与编码》 曹雪虹等编著

64

64 64

16次

64 48

64

64
图7-6 DES算法

密钥源

子密钥

输出

逆置换

密码运算

初始置换IP

输入

64

32 32

L0 R0

K1
＋ f

L1＝R0 R1＝L0 ＋ f(R0，K1)
K2
＋ f

L2＝R1 R2＝L1 ＋ f(R1，K2)
Kn
＋ f

L15＝R14 R15＝L14 ＋ f(R14，K15)
K16
＋ f

L16＝R15 R16＝L15 ＋ f(R15，K16)

64

Ri-1(32) 密钥(64)

E 密钥表

48比特 Ki(48)
＋

S1 S2 S3 … S8

P

32比特

图7-8 密码计算函数f(R，K)

密钥 64

置换选择1

28 28

C0 D0

左移 左移

C1 D1 48

置换选择2 K1
左移 左移

Cn Dn 48

置换选择2 Kn
左移 左移

C16 D16 48

置换选择2 K16

12
()()()
kkk
CEMEMEM
==
LL

12
12
()()()
kkk
CEMEmEm
==
LL

2
(/)()(/)log(/)
jijij
ji
HKCpcpkcpkc
=-
åå

2
(/)()(/)log(/)
jijij
ji
HMCpcpmcpmc
=
åå

()
K
CEM
=

(;)()(/)()()
IMCHMHMCHMHK
=-³-

1264
Kkkk
=
L

64

64
64

16
次

64 48

64

64

输入

初始置换
IP

密码运算

逆置换

输出

子密钥

密钥源

图
7
–
6
DES
算法

64

32 32

L
0
R
0

K
1

＋

f

L
1
＝
R
0
R
1
＝
L
0

＋
f
(
R
0
，
K
1
)

K
2

＋

f

L
2
＝
R
1
R
2
＝
L
1

＋
f
(
R
1
，
K
2
)

K
n

＋

f

L
15
＝
R
14
R
15
＝
L
14

＋
f
(
R
14
，
K
15
)

K
16

＋

f

L
1
6
＝
R
15
R
16
＝
L
15

＋
f
(
R
15
，
K
16
)

64

R
i
–
1
(32)
ÃÜÔ¿
(64)

E
ÃÜÔ¿±í

48
±ÈÌØ
K
i
(48)

£«

S
1
S
2
S
3

¡­
S
8

P

32
±ÈÌØ

ͼ
7
–
8
ÃÜÂë¼ÆË㺯Êý
f(R
£¬
K)

ÃÜÔ¿
64

Öû»Ñ¡Ôñ
1

28 28

C
0
D
0

×óÒÆ

×óÒÆ

C
1
D
1 48

Öû»Ñ¡Ôñ
2 K
1

×óÒÆ

×óÒÆ

C
n
D
n
48

Öû»Ñ¡Ôñ
2 K
n

×óÒÆ

×óÒÆ

C
1
6
D
1
6
48

Öû»Ñ¡Ôñ
2 K
1
6

Å

Å

Ä

Ä

Ä

Å

Ä

Å

(mod)
e
yxn
=

(mod)
d
xyn
=

npq
=´

()(1)(1)
npq
F=-´-

()(mod())1
edn
f
´=

23
mod(02)(mod123)8388608(mod123)8
A
d
iiA
SMn
====

13
mod8(mod51)549755813888(mod51)26
B
e
iB
SSn
====

5
mod26(mod51)11881376(mod51)8
B
d
iB
SSn
====

7
mod8(mod123)2097153(mod123)2
A
e
iiA
MSn
====

()()
BCBD
·Ú·

()()
BDCD
·Ú·

BCD
ÅÅ

()
CBD
Å·