1
第十四章 通信安全
14.1 概述
通信安全的基础 － 密码学
密码编码学
密码分析学
通信不安全因素
被破译
被攻击 － 被伪造和篡改
认证 － 防止被攻击的手段
认证的目的：
验证信息发送者真伪
验证接收信息的完整性 ― 是否被篡改了？是否被重复接收了？是否被拖延了？
认证技术：包括消息认证、身份验证和数字签字。
2
密码编码学内容：
将消息加密的方法
将已加密的消息解密的方法
密码分析学内容：如何破译密文和伪造密文。
密码学的基本术语
明文 － 待加密的消息
密文 － 加密后的消息
密码 － 用于加密的数据变换集合
密钥 － 用于表示加密变换的参数
密码种类：
单密钥密码
公共密钥密码：也称为双密钥密码
3
14.2 单密钥加密通信系统
例：
密钥 Z － m序列
加密算法 － 模 2加法
解密算法 － 仍是模 2加法
一般算法：
令 F为产生密文 Y 的可逆变换，即有
Y = F(X,Z) = FZ(X)
在接收端，密文 Y 用逆变换 F-1恢复成原来的明文 X,即
X = F-1(Y,Z) = FZ-1(Y) = FZ-1[FZ(X)]
密钥 安全信道信源 加密 解密信道X Y
Z
X
敌方发送端 信道 接收端
4
14.3 分组密码和流密码
分组密码
加密过程
原理
连续的分组用相同的密钥加密。
若有一个特定的分组明文和以前的一个分组相同，则加密后两者的密文也相同。
目标是使明文的任 1比特都不会直接出现在密文中。
串行 -分组变换器密码加密逻辑分组 -串行变换器密钥串行明文串行明文
5
流密码
原理：对明文的逐个比特进行不同的变换。
例：二进制加性流密码
令 xn,yn和 zn分别表示在 n时刻明文比特、密文比特和密钥流比特，则有式中,N是密钥流的长度。
因为在模 2运算中加法和减法是一样的，所以上式也可以写为因此，同样的装置既可以用于加密，也可以用于解密。
密钥流产生器明文 xn 密文 yn
密钥流 zn
密钥
(a)加密装置密钥流产生器密文 yn 明文 xn
密钥流 zn
密钥
(b)解密装置
Nnzxy nnn,,2,1,
Nnzyx nnn,,2,1,
6
密钥流应当尽可能地近似于一个完全随机的序列。
若密钥流是一个 m序列，则图中的密钥流产生器就是一个 m序列产生器；密钥则是控制此 m序列的生成多项式和同步信息等。
二进制加性流密码没有错误传播；在密文中一个错误比特解密后只影响输出中的相应比特。
（分组密码可能有错误传播，使明文分组中很少几个比特的改变在密文输出中产生很多比特的变化。分组密码的这种错误传播性质在认证中很有价值，因为它使敌方的破译人员不可能修改加密后的数据，除非知道密钥。）
流密码通常较适用于通过易出错的通信信道传输数据，
用于要求高数据率的应用中，例如视频保密通信，或者用于要求传输延迟很小的场合。
7
对通信安全的基本要求
假设：敌方破译人员知道所用加密法的全部机理，只是不知道密钥。
密码分析性攻击的形式：
仅对密文的攻击
对已知明文的攻击
对选定的明文的攻击
对选定的密文的攻击
实际中常发生的是仅对密文的攻击：
例：使用语言的统计结构知识（例如，英文字母 e的出现概率是 13%，以及字母 q的后面总跟随着 u）和关于某些可能的字的知识（例如，一封信的开头中可能有“先生”或“女士”两字）。
仅对密文的攻击是一个密码系统受到的最轻的威胁。因此，任何系统若不能战胜这种攻击，则被认为是完全不安全的系统。
8
14.4用信息论研究密码的方法
香农模型的假定：
敌方破译人员具有无限的时间和无限的计算能力；
敌方仅限于对密文攻击。
香农的密码分析定义：给定密文以及各种明文和密钥的先验概率，搜寻密钥的过程。当敌方破译人员获得密文的唯一解时，就成功地解密了。
香农对安全性的基本度量 － 互信息量 I(X; Y)
令 X = (X1,X2,…,XN)表示一个 N 比特的明文消息 ;
Y = (Y1,Y2,…,YN)表示相应的 N 比特密文。
假定：
密钥 Z服从某种概率分布
H(X) － X的不确定性
H(X/Y) － 给定 Y后 X的不确定性
I (X; Y) = H(X) – H(X/Y) － X和 Y之间的互信息量。
9
14.4.1 完善安全性
完善安全性定义假定：破译人员只能够看到密文 Y，则一个保密系统的完善安全性定义为：明文 X和密文 Y之间是统计独立的，即有
I(X; Y) = 0
于是，由 I (X; Y) = H(X) – H(X/Y)，可以求出
H(X/Y) = H(X)
上式表明，敌方破译人员最多只能，按照所有可能消息的概率分布，从给定的密文 Y，去猜测明文消息 X。
10
香农基本界给定密钥 Z后，有
H(X/Y)? H(X,Z/Y) = H(Z/Y) + H(X/Y,Z)
当且仅当 Y 和 Z 共同唯一地决定 X 时，
H(X/Y,Z) = 0；
当使用已知密钥 Z 解密时，这是一个很有价值的假定。
因此，我们可以将式
H(X/Y)? H(X,Z/Y) = H(Z/Y) + H(X/Y,Z)
简化如下：
H(X/Y)? H(Z/Y)? H(Z)
将上式代入式
H(X/Y) = H(X)
得知：为使一个保密系统给出完善的安全性，必须满足条件
H(Z)? H(X)
它表明为了达到完善安全性，密钥 Z的不确定性必须不小于被此密钥所隐蔽的明文 X的不确定性。
11
一次一密密码
原理方框图：一种流密码，其密钥和密钥流相同，并且密钥只使用一次。
密文 yn = xn? zn,n = 1,2,…
式中,xn － 消息比特序列；
zn － 统计独立和均匀分布的密钥比特序列。
一次一密密码是完善安全的，因为消息和密文之间的互信息量为 0；所以它是完全不可解密的。
消息
xn
密文
yn
密钥
zn
密文
yn
消息
xn
密钥
zn
(a) 加密 (b) 解密
12
14.4.2 唯一解距离
对于一个用非完善密码加密的密文，可以预期，当截获的文件量随时间增大到某一点时，破译人员用无限的时间和无限的计算能力，将能够找到密钥并从而破译了密文。
在香农的模型中，破译人员能破译此密文的临界点称为唯一解距离。
唯一解距离的定义：
使条件熵 H(Z/Y1,Y2,…,YN)近似为 0的最小 N。
对于一类特殊的“随机密文”，唯一解距离近似由下式给出：
式中,H(Z) － 密钥 Z的熵，
Ly － 密文字符集的大小，
r － N比特密文中所含信息的冗余度百分比，即式中,H(X)为明文 X的熵。
yLr
HN
2
0 l o g
)( Z?
yLN
Hr
2l o g
)(1 X
13
在大多数保密系统中，密文字符集的大小 Ly和明文字符集的大小 Lx一样。在这种情况下,r就是明文本身的冗余度百分比。
求 H(Z)
令 K = 密钥 Z中的数字数目，这些数字是从大小为 Lz的字符集中选用的；则可以将密钥 Z 的熵表示如下：
当且仅当密钥是完全随机的时，上式等号成立。
令 Lz = Ly，并完全随机地选择密钥以使唯一解距离最大。
然后，将 H(Z) = K log2 Lz代入得到,N0? K / r
yLN
Hr
2l o g
)(1 X
zKz LKLH 22 l o gl o g)(Z
yLr
HN
2
0 l o g
)( Z?
14
N0? K / r
例：考察一个 Lx = Ly = Lz保密系统，它用于对英文文本加密典型英文文本的 r 大约等于 75％。因此，按照上式，一个破译人员在仅截获约 1.333K比特的密文数据后，就能破译此密码，其中 K是密钥长度。
值得注意，非完善密码仍然有实用价值。
15
14.4.3 数据压缩在密码编码中的作用
数据压缩能除去冗余度，因此增大了唯一解距离。
14.4.4 扩散与混淆
扩散：将明文中一个比特的影响扩散到密文中很多比特，从而将明文的统计结构隐藏起来。
混淆：采用数据变换，使密文的统计特性与明文的统计特性之间的关系更为复杂。
乘积密码：由一些简单的密码分量相继加密构成；这些较简单的密码分量分别能使最终的密码有适度的扩散和混淆。
例：乘积密码用“替代密码”和“置换密码”作为基本分量。
16
替代密码：明文的每个字符用一种固定的替代所代替；代替的字符仍为同一字符表中的字符；特定的替代规则由密钥决定。
若明文为
X = (x1,x2,x3,x4,…)
式中,x1,x2,x3,x4,… 为相继的字符，则变换后的密文为
Y = (y1,y2,y3,y4,…) = [ f(x1),f(x2),f(x3),f(x4),…]
式中,f (? )是一个可逆函数。
例：密文的字符表从此表中可以看到，第一个字符 U替代 A，第二个字符 H
替代 B，等等。 使用替代密码可以得到混淆。
明文字符 ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字符 UHNACSVYDXEKQJRWGOZITPFMBL
17
置换密码：明文被分为具有固定周期 d 的组，对每组作同样的交换。特定的交换规则是由密钥决定的。
若周期 d＝ 4，交换规则为则明文中的字符 x 将从位置 1 移至密文中的位置 4。
一般而言，明文
X = (x1,x2,x3,x4,x5,x6,x7,x8,…)
将变换成密文
Y = (x3,x4,x2,x1,x7,x8,x6,x5,…)
虽然密文 Y 中单个字符的统计特性和明文 X 中的一样，但是高阶统计特性却改变了。
使用置换密码可以得到扩散。
明文字符 x1 x2 x3 x4
密文字符 x3 x4 x2 x1
18
将替代和置换作交织，并将交织过程重复多次，就能得到具有良好扩散和混淆性能的保密性极强的密码。
例：
设明文消息为
THE APPLES ARE GOOD
使用交换字符表作为替代密码，则此明文将变换为如下密文：
IYC UWWKCZ UOC VRRA
下一步我们将交换规则用于置换密码，则从替代密码得到的密文将进一步变换成
UCI YCKWWC OZU ARVR
这样，上面的密文和原来的明文相比，毫无共同之处。
明文字符 ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字符 UHNACSVYDXEKQJRWGOZITPFMBL
明文字符 x1 x2 x3x
4
密文字符 x3 x4 x2 x1
19
14.5 数据加密标准 －美国政府标准算法 DES
DES采用扩散和混淆算法，是一种保密性很强的密码。
它对 64 b长的明文数据分组运算，所用的密钥长度为 56 b。
DES算法中：
总变换 = P -1{F[P(X)]}，
其中 X － 明文，
P － 某种交换，
F － 包括替代和置换；由某些函数 f 的级连构成。
20
DES算法流程图
第 1次初始交换后,64 b的明文分为左半部 L0和右半部 R0，每半部长 32 b。
完成 16轮交换，其中第 i 轮交换：
Li = Ri－ 1,i = 1,2,…,16
Ri = Li-1? f(Ri-1,Zi),i = 1,2,…,16
式中,Zi － 在第 i 轮中使用的密钥；
此密钥的长度为 48 b。
第 16轮运算的结果，经过颠倒后，
得到 R16L16。
再经过最后一次交换 P -1，
就产生出 64 b的密文。
为了解密，函数 f(?,?)不必须是可逆的，
因为 (Li-1,Ri-1)能够从 (Li,Ri)直接恢复：
Ri-1 = Li i = 1,2,…,16
Li-1 = Ri? f(Li,Zi) i = 1,2,…,16
64 b密文
f(R0,Z1)
R16L16
最后一次交换
Z1
64 b 明文初始交换
32 b L0 32 b R0
f(R0,Z1)
R1L1
f(R0,Z1)
R2L2
R15L15
Z2
Z16
21
计算 f(?,?)的流程图
扩展,R(32b)? R?(48b)
方法：重复每个相继的 4
比特字的两端比特。
若
R = r1r2r3r4 r5r6r7r8 … r29r30r31r32
则扩展后
R?＝ r32r1r2r3r4r5 r4r5r6r7r8r9 …
… r28r29r30r31r32r1
R?和 Zi 模 2相加，再将相加结果分成 8个 6 b的字,B1B2 … B8 = R? Zi
32 b的 R
扩 展
48 b的 R?
48 b的
Zi
S2 S8S1 …
交换 P[?]
32 b f(R,Zi)
第 1个
4 b的字第 2个
4 b的字第 8个
4 b的字第 1个
6 b的字 第 2个6 b的字第 8个
6 b的字
22
每个 6 b的字 Bi 输入到一个替代方框 Si；后者用查表的方法产生出一个 4 b的输出 Si(Bi)。 Si(Bi)是 6 b字 Bi的布尔函数。
8个输出 Si 输入到交换方框 P[? ]。
交换所得就是所要求的
32 b的函数 f(R,Zi),
f(R,Zi) ＝ P[S1(B1)S2(B2)… S8(B8)]
32 b的 R
扩 展
48 b的 R?
48 b的
Zi
S2 S8S1 …
交换 P[?]
32 b f(R,Zi)
23
密钥进程计算 － 决定每个 Zi所用的过程
流程图
各 Zi使用密钥 Z0的不同子集。
密钥 Z0在位置 8,16,
…,64 上有 8个监督比特，用于在对应的 8 b字节中进行错误检测。
,交换选择 1”丢掉 Z0
的监督比特。
然后存入两个 28 b的移存器中。
64 b密钥交换选择 1
56 b密钥
28 b C0 28 b D0
左 移 左 移
C1 D1
左 移 左 移交换选择 2
C2 D2
左 移 左 移交换选择 2
C16 D16
交换选择 2
移存器
Z1
Z2
Z16
…
24
作 16次迭代运算，每次迭代包括一次或两次循环左移，然后进行“交换选择 2”。
输出就是第 1次至第
16次迭代用的不同的
48 b密钥分组 Z1,Z2,
…,Z16。
64 b密钥交换选择 1
56 b密钥
28 b C0 28 b D0
左 移 左 移
C1 D1
左 移 左 移交换选择 2
C2 D2
左 移 左 移交换选择 2
C16 D16
交换选择 2
移存器
Z1
Z2
Z16
…
25
14.6 公共密钥密码编码方法
14.6.1 基本原理
公共密钥系统中，用两种算法去计算两个不可逆函数（变换）。令这两种算法用 {Ez}和 {Dz}表示：
Ez,fz(x) = y － 公共密钥（公钥）
Dz,fz-1(y) = x － 秘密密钥（私钥）
式中,x － 在某个函数 fz的域中的一个输入消息，
y － 在 fz取值范围内相应的密文。
基本要求：函数 fz必须是一个单向函数。
公钥和私钥的两个基本性质：
消息被这对密钥之一加密后，能够用另一个密钥解密。
知道公钥后，不可能计算出私钥。
将此系统的用户姓名、地址和公钥列于一本“电话簿”中。
当一个用户需要向另一个用户发送保密消息时，查此“电话簿”，用对方的公钥对消息加密。加密的消息只能由持有对应私钥的用户阅读。
26
14.6.2 Diffie-Hellman 公共密钥分配系统
基本原理：令离散指数函数为
Y =?X mod p 1? X? p – 1
式中,? － 一个整数，并且是一个本原元。
因此,X是 Y的以?为底的模 p离散对数：
X = log?Y mod p 1? Y? p – 1
使用“平方的乘积”法，很容易从 X计算 Y。
例如，对于 X = 16，有
Y =?16 = {[(?2)2]2}2
另一方面，从 Y计算 X则难得多。
应用方法：假定所有用户都知道?和 p。
若有一用户 i，从一组整数 {1,2,…,p}中，均匀地选择一个独立随机数 Xi，作为私钥；并将离散指数
Yi =?Xi mod p
和用户姓名及地址一起放在“公共电话簿”中。其他用户也如此做。
27
假设用户 i 和 j 希望进行保密通信。为此，用户 i 从“公共电话簿”中取出 Yj，并用私钥 Xi计算用户 j 用同样方法计算 Kij。因为
Kji = Kij
所以，用户 i和 j可将 Kji 看作是普通保密系统中的密钥。
敌方若想得到 Kji，必须用从“公共电话簿”中得到的 Yi和
Yj，按照下列公式去计算 Kji：
上式因为包含离散对数故难于计算。
pppYK ijiji XXXXXjji m o dm o dm o d
pYK iYjji m o dl o g
28
14.7 RSA算法
14.7.1 RSA公共密钥密码系统
基本原理,RSA算法是一种分组密码，其理论基础是，求出一个随机的大素数不难，但是将两个这种数的乘积分解因子目前认为是不可能的。
算法：
随机选择两个很大的素数 p和 q,p? q；
将 p和 q相乘，得到乘积
pq = n
使用下式求出欧拉函数?(n):
(n) = (p – 1)(q – 1)
从欧拉函数 φ(n)的定义可知，上式给出小于 n的正整数 i的数目，且 i和 n的最大公因子等于 1，即 i和 n互为素数。
例：设 p＝ 3,q＝ 5，则 n＝ 15,?(n) = (3-1)(5-1) = 8。它表示小于 15
且和 15互素的正整数 i共有 8个；它们是,1,2,4,7,8,11,13，
14。
29
令 e是一个小于 φ(n)的正整数，它使 e和 φ(n)的最大公因子等于 1。
这样，求出一个小于 φ(n)的正整数 d，它使
de ＝ 1 modφ(n)
RSA的单向函数由计算下式中的离散指数定义：
fz(x) = xe = y mod n
将 n和 e值组成公共密钥 －公布计算函数 fz的算法 Ez（它很容易找到）就相当于公布 n和 e的值。
素数 p和 q组成秘密密钥。
知道素数 p和 q后，就容易求出逆函数 fz-1。 fz-1的定义是
fz-1(y) = yd mod n
使用式 de ＝ 1 modφ(n)，能求出解密指数 d,即
de ＝ φ(n)Q + 1
式中,Q是某个整数。
∵ y = xe,∴
利用欧拉的一个著名定理，即对于任何正整数 x和 n,x < n，
有,将其代入 de＝ φ(n)Q + 1，得到
yd = x
它表明：知道素数 p和 q后，就容易求出逆函数 fz-1。
xxxxy QnQnded )(1)(
nx n m o d1)(
30
RSA密码算法的安全性依赖于如下前提：求 fz的逆函数的任何方法等效于求分解 n = pq的方法。这样就产生了一个问题：用分解 n的方法进行攻击可能吗？答案是不可能的。若素数 p和 q
分别由 100位以上十进制数字组成，目前尚无分解因子的算法。
31
14.7.2 RSA算法在数字签字中的应用
数字签字必须具有的性质：
一个电子消息的接收设备必须能够验证发送者的签字。
签字不可能伪造。
已签字的电子消息的发送者不能否认它。
用 RSA算法实现数字签字的方法：
一个拥有私钥 d的用户可以对给定的消息分组 m签字为
s = md mod n
若不知道私钥 d，则很难计算出 s。 故此签字很难伪造。
消息 m的发送者不能否认此消息是他发送的，因为其他人不能造出此签字 s。
接收设备使用公钥 e进行如下计算：
se = (md)e mod n = mde mod n = m mod n
接收设备计算 se，若得到和解密的消息 m相同的结果，就证明了发送者的签字是真的。
32
14.8 小结
第十四章 通信安全
14.1 概述
通信安全的基础 － 密码学
密码编码学
密码分析学
通信不安全因素
被破译
被攻击 － 被伪造和篡改
认证 － 防止被攻击的手段
认证的目的：
验证信息发送者真伪
验证接收信息的完整性 ― 是否被篡改了？是否被重复接收了？是否被拖延了？
认证技术：包括消息认证、身份验证和数字签字。
2
密码编码学内容：
将消息加密的方法
将已加密的消息解密的方法
密码分析学内容：如何破译密文和伪造密文。
密码学的基本术语
明文 － 待加密的消息
密文 － 加密后的消息
密码 － 用于加密的数据变换集合
密钥 － 用于表示加密变换的参数
密码种类：
单密钥密码
公共密钥密码：也称为双密钥密码
3
14.2 单密钥加密通信系统
例：
密钥 Z － m序列
加密算法 － 模 2加法
解密算法 － 仍是模 2加法
一般算法：
令 F为产生密文 Y 的可逆变换，即有
Y = F(X,Z) = FZ(X)
在接收端，密文 Y 用逆变换 F-1恢复成原来的明文 X,即
X = F-1(Y,Z) = FZ-1(Y) = FZ-1[FZ(X)]
密钥 安全信道信源 加密 解密信道X Y
Z
X
敌方发送端 信道 接收端
4
14.3 分组密码和流密码
分组密码
加密过程
原理
连续的分组用相同的密钥加密。
若有一个特定的分组明文和以前的一个分组相同，则加密后两者的密文也相同。
目标是使明文的任 1比特都不会直接出现在密文中。
串行 -分组变换器密码加密逻辑分组 -串行变换器密钥串行明文串行明文
5
流密码
原理：对明文的逐个比特进行不同的变换。
例：二进制加性流密码
令 xn,yn和 zn分别表示在 n时刻明文比特、密文比特和密钥流比特，则有式中,N是密钥流的长度。
因为在模 2运算中加法和减法是一样的，所以上式也可以写为因此，同样的装置既可以用于加密，也可以用于解密。
密钥流产生器明文 xn 密文 yn
密钥流 zn
密钥
(a)加密装置密钥流产生器密文 yn 明文 xn
密钥流 zn
密钥
(b)解密装置
Nnzxy nnn,,2,1,
Nnzyx nnn,,2,1,
6
密钥流应当尽可能地近似于一个完全随机的序列。
若密钥流是一个 m序列，则图中的密钥流产生器就是一个 m序列产生器；密钥则是控制此 m序列的生成多项式和同步信息等。
二进制加性流密码没有错误传播；在密文中一个错误比特解密后只影响输出中的相应比特。
（分组密码可能有错误传播，使明文分组中很少几个比特的改变在密文输出中产生很多比特的变化。分组密码的这种错误传播性质在认证中很有价值，因为它使敌方的破译人员不可能修改加密后的数据，除非知道密钥。）
流密码通常较适用于通过易出错的通信信道传输数据，
用于要求高数据率的应用中，例如视频保密通信，或者用于要求传输延迟很小的场合。
7
对通信安全的基本要求
假设：敌方破译人员知道所用加密法的全部机理，只是不知道密钥。
密码分析性攻击的形式：
仅对密文的攻击
对已知明文的攻击
对选定的明文的攻击
对选定的密文的攻击
实际中常发生的是仅对密文的攻击：
例：使用语言的统计结构知识（例如，英文字母 e的出现概率是 13%，以及字母 q的后面总跟随着 u）和关于某些可能的字的知识（例如，一封信的开头中可能有“先生”或“女士”两字）。
仅对密文的攻击是一个密码系统受到的最轻的威胁。因此，任何系统若不能战胜这种攻击，则被认为是完全不安全的系统。
8
14.4用信息论研究密码的方法
香农模型的假定：
敌方破译人员具有无限的时间和无限的计算能力；
敌方仅限于对密文攻击。
香农的密码分析定义：给定密文以及各种明文和密钥的先验概率，搜寻密钥的过程。当敌方破译人员获得密文的唯一解时，就成功地解密了。
香农对安全性的基本度量 － 互信息量 I(X; Y)
令 X = (X1,X2,…,XN)表示一个 N 比特的明文消息 ;
Y = (Y1,Y2,…,YN)表示相应的 N 比特密文。
假定：
密钥 Z服从某种概率分布
H(X) － X的不确定性
H(X/Y) － 给定 Y后 X的不确定性
I (X; Y) = H(X) – H(X/Y) － X和 Y之间的互信息量。
9
14.4.1 完善安全性
完善安全性定义假定：破译人员只能够看到密文 Y，则一个保密系统的完善安全性定义为：明文 X和密文 Y之间是统计独立的，即有
I(X; Y) = 0
于是，由 I (X; Y) = H(X) – H(X/Y)，可以求出
H(X/Y) = H(X)
上式表明，敌方破译人员最多只能，按照所有可能消息的概率分布，从给定的密文 Y，去猜测明文消息 X。
10
香农基本界给定密钥 Z后，有
H(X/Y)? H(X,Z/Y) = H(Z/Y) + H(X/Y,Z)
当且仅当 Y 和 Z 共同唯一地决定 X 时，
H(X/Y,Z) = 0；
当使用已知密钥 Z 解密时，这是一个很有价值的假定。
因此，我们可以将式
H(X/Y)? H(X,Z/Y) = H(Z/Y) + H(X/Y,Z)
简化如下：
H(X/Y)? H(Z/Y)? H(Z)
将上式代入式
H(X/Y) = H(X)
得知：为使一个保密系统给出完善的安全性，必须满足条件
H(Z)? H(X)
它表明为了达到完善安全性，密钥 Z的不确定性必须不小于被此密钥所隐蔽的明文 X的不确定性。
11
一次一密密码
原理方框图：一种流密码，其密钥和密钥流相同，并且密钥只使用一次。
密文 yn = xn? zn,n = 1,2,…
式中,xn － 消息比特序列；
zn － 统计独立和均匀分布的密钥比特序列。
一次一密密码是完善安全的，因为消息和密文之间的互信息量为 0；所以它是完全不可解密的。
消息
xn
密文
yn
密钥
zn
密文
yn
消息
xn
密钥
zn
(a) 加密 (b) 解密
12
14.4.2 唯一解距离
对于一个用非完善密码加密的密文，可以预期，当截获的文件量随时间增大到某一点时，破译人员用无限的时间和无限的计算能力，将能够找到密钥并从而破译了密文。
在香农的模型中，破译人员能破译此密文的临界点称为唯一解距离。
唯一解距离的定义：
使条件熵 H(Z/Y1,Y2,…,YN)近似为 0的最小 N。
对于一类特殊的“随机密文”，唯一解距离近似由下式给出：
式中,H(Z) － 密钥 Z的熵，
Ly － 密文字符集的大小，
r － N比特密文中所含信息的冗余度百分比，即式中,H(X)为明文 X的熵。
yLr
HN
2
0 l o g
)( Z?
yLN
Hr
2l o g
)(1 X
13
在大多数保密系统中，密文字符集的大小 Ly和明文字符集的大小 Lx一样。在这种情况下,r就是明文本身的冗余度百分比。
求 H(Z)
令 K = 密钥 Z中的数字数目，这些数字是从大小为 Lz的字符集中选用的；则可以将密钥 Z 的熵表示如下：
当且仅当密钥是完全随机的时，上式等号成立。
令 Lz = Ly，并完全随机地选择密钥以使唯一解距离最大。
然后，将 H(Z) = K log2 Lz代入得到,N0? K / r
yLN
Hr
2l o g
)(1 X
zKz LKLH 22 l o gl o g)(Z
yLr
HN
2
0 l o g
)( Z?
14
N0? K / r
例：考察一个 Lx = Ly = Lz保密系统，它用于对英文文本加密典型英文文本的 r 大约等于 75％。因此，按照上式，一个破译人员在仅截获约 1.333K比特的密文数据后，就能破译此密码，其中 K是密钥长度。
值得注意，非完善密码仍然有实用价值。
15
14.4.3 数据压缩在密码编码中的作用
数据压缩能除去冗余度，因此增大了唯一解距离。
14.4.4 扩散与混淆
扩散：将明文中一个比特的影响扩散到密文中很多比特，从而将明文的统计结构隐藏起来。
混淆：采用数据变换，使密文的统计特性与明文的统计特性之间的关系更为复杂。
乘积密码：由一些简单的密码分量相继加密构成；这些较简单的密码分量分别能使最终的密码有适度的扩散和混淆。
例：乘积密码用“替代密码”和“置换密码”作为基本分量。
16
替代密码：明文的每个字符用一种固定的替代所代替；代替的字符仍为同一字符表中的字符；特定的替代规则由密钥决定。
若明文为
X = (x1,x2,x3,x4,…)
式中,x1,x2,x3,x4,… 为相继的字符，则变换后的密文为
Y = (y1,y2,y3,y4,…) = [ f(x1),f(x2),f(x3),f(x4),…]
式中,f (? )是一个可逆函数。
例：密文的字符表从此表中可以看到，第一个字符 U替代 A，第二个字符 H
替代 B，等等。 使用替代密码可以得到混淆。
明文字符 ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字符 UHNACSVYDXEKQJRWGOZITPFMBL
17
置换密码：明文被分为具有固定周期 d 的组，对每组作同样的交换。特定的交换规则是由密钥决定的。
若周期 d＝ 4，交换规则为则明文中的字符 x 将从位置 1 移至密文中的位置 4。
一般而言，明文
X = (x1,x2,x3,x4,x5,x6,x7,x8,…)
将变换成密文
Y = (x3,x4,x2,x1,x7,x8,x6,x5,…)
虽然密文 Y 中单个字符的统计特性和明文 X 中的一样，但是高阶统计特性却改变了。
使用置换密码可以得到扩散。
明文字符 x1 x2 x3 x4
密文字符 x3 x4 x2 x1
18
将替代和置换作交织，并将交织过程重复多次，就能得到具有良好扩散和混淆性能的保密性极强的密码。
例：
设明文消息为
THE APPLES ARE GOOD
使用交换字符表作为替代密码，则此明文将变换为如下密文：
IYC UWWKCZ UOC VRRA
下一步我们将交换规则用于置换密码，则从替代密码得到的密文将进一步变换成
UCI YCKWWC OZU ARVR
这样，上面的密文和原来的明文相比，毫无共同之处。
明文字符 ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字符 UHNACSVYDXEKQJRWGOZITPFMBL
明文字符 x1 x2 x3x
4
密文字符 x3 x4 x2 x1
19
14.5 数据加密标准 －美国政府标准算法 DES
DES采用扩散和混淆算法，是一种保密性很强的密码。
它对 64 b长的明文数据分组运算，所用的密钥长度为 56 b。
DES算法中：
总变换 = P -1{F[P(X)]}，
其中 X － 明文，
P － 某种交换，
F － 包括替代和置换；由某些函数 f 的级连构成。
20
DES算法流程图
第 1次初始交换后,64 b的明文分为左半部 L0和右半部 R0，每半部长 32 b。
完成 16轮交换，其中第 i 轮交换：
Li = Ri－ 1,i = 1,2,…,16
Ri = Li-1? f(Ri-1,Zi),i = 1,2,…,16
式中,Zi － 在第 i 轮中使用的密钥；
此密钥的长度为 48 b。
第 16轮运算的结果，经过颠倒后，
得到 R16L16。
再经过最后一次交换 P -1，
就产生出 64 b的密文。
为了解密，函数 f(?,?)不必须是可逆的，
因为 (Li-1,Ri-1)能够从 (Li,Ri)直接恢复：
Ri-1 = Li i = 1,2,…,16
Li-1 = Ri? f(Li,Zi) i = 1,2,…,16
64 b密文
f(R0,Z1)
R16L16
最后一次交换
Z1
64 b 明文初始交换
32 b L0 32 b R0
f(R0,Z1)
R1L1
f(R0,Z1)
R2L2
R15L15
Z2
Z16
21
计算 f(?,?)的流程图
扩展,R(32b)? R?(48b)
方法：重复每个相继的 4
比特字的两端比特。
若
R = r1r2r3r4 r5r6r7r8 … r29r30r31r32
则扩展后
R?＝ r32r1r2r3r4r5 r4r5r6r7r8r9 …
… r28r29r30r31r32r1
R?和 Zi 模 2相加，再将相加结果分成 8个 6 b的字,B1B2 … B8 = R? Zi
32 b的 R
扩 展
48 b的 R?
48 b的
Zi
S2 S8S1 …
交换 P[?]
32 b f(R,Zi)
第 1个
4 b的字第 2个
4 b的字第 8个
4 b的字第 1个
6 b的字 第 2个6 b的字第 8个
6 b的字
22
每个 6 b的字 Bi 输入到一个替代方框 Si；后者用查表的方法产生出一个 4 b的输出 Si(Bi)。 Si(Bi)是 6 b字 Bi的布尔函数。
8个输出 Si 输入到交换方框 P[? ]。
交换所得就是所要求的
32 b的函数 f(R,Zi),
f(R,Zi) ＝ P[S1(B1)S2(B2)… S8(B8)]
32 b的 R
扩 展
48 b的 R?
48 b的
Zi
S2 S8S1 …
交换 P[?]
32 b f(R,Zi)
23
密钥进程计算 － 决定每个 Zi所用的过程
流程图
各 Zi使用密钥 Z0的不同子集。
密钥 Z0在位置 8,16,
…,64 上有 8个监督比特，用于在对应的 8 b字节中进行错误检测。
,交换选择 1”丢掉 Z0
的监督比特。
然后存入两个 28 b的移存器中。
64 b密钥交换选择 1
56 b密钥
28 b C0 28 b D0
左 移 左 移
C1 D1
左 移 左 移交换选择 2
C2 D2
左 移 左 移交换选择 2
C16 D16
交换选择 2
移存器
Z1
Z2
Z16
…
24
作 16次迭代运算，每次迭代包括一次或两次循环左移，然后进行“交换选择 2”。
输出就是第 1次至第
16次迭代用的不同的
48 b密钥分组 Z1,Z2,
…,Z16。
64 b密钥交换选择 1
56 b密钥
28 b C0 28 b D0
左 移 左 移
C1 D1
左 移 左 移交换选择 2
C2 D2
左 移 左 移交换选择 2
C16 D16
交换选择 2
移存器
Z1
Z2
Z16
…
25
14.6 公共密钥密码编码方法
14.6.1 基本原理
公共密钥系统中，用两种算法去计算两个不可逆函数（变换）。令这两种算法用 {Ez}和 {Dz}表示：
Ez,fz(x) = y － 公共密钥（公钥）
Dz,fz-1(y) = x － 秘密密钥（私钥）
式中,x － 在某个函数 fz的域中的一个输入消息，
y － 在 fz取值范围内相应的密文。
基本要求：函数 fz必须是一个单向函数。
公钥和私钥的两个基本性质：
消息被这对密钥之一加密后，能够用另一个密钥解密。
知道公钥后，不可能计算出私钥。
将此系统的用户姓名、地址和公钥列于一本“电话簿”中。
当一个用户需要向另一个用户发送保密消息时，查此“电话簿”，用对方的公钥对消息加密。加密的消息只能由持有对应私钥的用户阅读。
26
14.6.2 Diffie-Hellman 公共密钥分配系统
基本原理：令离散指数函数为
Y =?X mod p 1? X? p – 1
式中,? － 一个整数，并且是一个本原元。
因此,X是 Y的以?为底的模 p离散对数：
X = log?Y mod p 1? Y? p – 1
使用“平方的乘积”法，很容易从 X计算 Y。
例如，对于 X = 16，有
Y =?16 = {[(?2)2]2}2
另一方面，从 Y计算 X则难得多。
应用方法：假定所有用户都知道?和 p。
若有一用户 i，从一组整数 {1,2,…,p}中，均匀地选择一个独立随机数 Xi，作为私钥；并将离散指数
Yi =?Xi mod p
和用户姓名及地址一起放在“公共电话簿”中。其他用户也如此做。
27
假设用户 i 和 j 希望进行保密通信。为此，用户 i 从“公共电话簿”中取出 Yj，并用私钥 Xi计算用户 j 用同样方法计算 Kij。因为
Kji = Kij
所以，用户 i和 j可将 Kji 看作是普通保密系统中的密钥。
敌方若想得到 Kji，必须用从“公共电话簿”中得到的 Yi和
Yj，按照下列公式去计算 Kji：
上式因为包含离散对数故难于计算。
pppYK ijiji XXXXXjji m o dm o dm o d
pYK iYjji m o dl o g
28
14.7 RSA算法
14.7.1 RSA公共密钥密码系统
基本原理,RSA算法是一种分组密码，其理论基础是，求出一个随机的大素数不难，但是将两个这种数的乘积分解因子目前认为是不可能的。
算法：
随机选择两个很大的素数 p和 q,p? q；
将 p和 q相乘，得到乘积
pq = n
使用下式求出欧拉函数?(n):
(n) = (p – 1)(q – 1)
从欧拉函数 φ(n)的定义可知，上式给出小于 n的正整数 i的数目，且 i和 n的最大公因子等于 1，即 i和 n互为素数。
例：设 p＝ 3,q＝ 5，则 n＝ 15,?(n) = (3-1)(5-1) = 8。它表示小于 15
且和 15互素的正整数 i共有 8个；它们是,1,2,4,7,8,11,13，
14。
29
令 e是一个小于 φ(n)的正整数，它使 e和 φ(n)的最大公因子等于 1。
这样，求出一个小于 φ(n)的正整数 d，它使
de ＝ 1 modφ(n)
RSA的单向函数由计算下式中的离散指数定义：
fz(x) = xe = y mod n
将 n和 e值组成公共密钥 －公布计算函数 fz的算法 Ez（它很容易找到）就相当于公布 n和 e的值。
素数 p和 q组成秘密密钥。
知道素数 p和 q后，就容易求出逆函数 fz-1。 fz-1的定义是
fz-1(y) = yd mod n
使用式 de ＝ 1 modφ(n)，能求出解密指数 d,即
de ＝ φ(n)Q + 1
式中,Q是某个整数。
∵ y = xe,∴
利用欧拉的一个著名定理，即对于任何正整数 x和 n,x < n，
有,将其代入 de＝ φ(n)Q + 1，得到
yd = x
它表明：知道素数 p和 q后，就容易求出逆函数 fz-1。
xxxxy QnQnded )(1)(
nx n m o d1)(
30
RSA密码算法的安全性依赖于如下前提：求 fz的逆函数的任何方法等效于求分解 n = pq的方法。这样就产生了一个问题：用分解 n的方法进行攻击可能吗？答案是不可能的。若素数 p和 q
分别由 100位以上十进制数字组成，目前尚无分解因子的算法。
31
14.7.2 RSA算法在数字签字中的应用
数字签字必须具有的性质：
一个电子消息的接收设备必须能够验证发送者的签字。
签字不可能伪造。
已签字的电子消息的发送者不能否认它。
用 RSA算法实现数字签字的方法：
一个拥有私钥 d的用户可以对给定的消息分组 m签字为
s = md mod n
若不知道私钥 d，则很难计算出 s。 故此签字很难伪造。
消息 m的发送者不能否认此消息是他发送的，因为其他人不能造出此签字 s。
接收设备使用公钥 e进行如下计算：
se = (md)e mod n = mde mod n = m mod n
接收设备计算 se，若得到和解密的消息 m相同的结果，就证明了发送者的签字是真的。
32
14.8 小结
