第二章
信息加密技术基础
引 言
信息加密是网络安全体系中重要机制之
一。信息加密的目的是为了保持信息的机密
性，使用恰当的加密标准将在计算机环境中
增加安全性。信息加密通过使用一种编码而
使存储或传输的信息变为不可读的信息，解
密是一个相反的过程。这些编码就是将明文
变成密文的加密算法或数学方法。
引 言 (续 )
加密编码在 Shannon的信息论中有针对性的阐述，
数论及基础代数是加密算法的理论基础。要将一段
信息加密或解密，你会要用到密钥，它是一个很大
的值。一般来说，密钥越大，加密就越健壮。一般
来说加密体制分为对称密钥加密和公用密钥加密，
对称密钥加密在密钥方面有一定的缺陷，但执行效
率高；公用密钥加密加密执行效率底，但保密性强，
在报文和网络方面对小量信息加密非常有效,
2.1 信息加密理论基础
信息安全的核心技术之一是加密技术，
它涉及信息论、基础数论和算法复杂性等
多方面基础知识。随着计算机网络不断渗
透到各个领域，加密技术的应用也随之扩
大，应用加密基础理论知识，深入探索可
靠可行的加密方法，应用于数字签名、身
份鉴别等新技术中成为网络安全研究重要
的一个方面。
加密的理论依据
密码学问题就是随机性的利用问题,
差不多每台使用加密技术的计算机安全系
统都需要随机数，供密钥、协议中的基础
参量等使用或者用做辅助信息或者初始化
向量。这些系统的安全也经常依赖于这些
随机数的随机性及被保护程度 。
简单的加密举例
中秋日月 编码 密钥 密文编码 诗
月明明日 010101 10 111111
明日月明 101010 000000？
明日明日 101101 000111
日明月明 110010 011000
通过这个例子我们看到一个简单的加密过程，原来的诗
通过与密钥的模二运算实现了加密。
2.1.1 信息编码基础知识
第二次世界大战期间，美国为了提高
信息储存和传递的效率，发明了多种新的
编码方法，奠定了现代信息科学技术的基
础。 Shannon还于 1949年发表了“保密系统
的通信理论”一文，奠定了现代密码学基
础从而对加密过程中信息编码有了明确的
分析。在该文中他从信息论观点，对信息
系统的保密性问题作了全面而深刻的阐述。
1,信 息 熵 基 本 知 识
信息论中最重要的内容，是如何认识和使用
信息熵来表现信息。 这里用 Shannon最喜欢用的
猜谜方法来说明信息熵的基本概念。假如有：
“我们大 __都喜 __使 __计 __机来管 __数 __。”
不用很多努力，就可以猜出完整的句子,“我们大
家都喜欢使用计算机来管理数据。” Shannon在
信息论中指出，能猜出来的字符不运载信息，而
不能猜出来的字符运载信息。
1,信 息 熵 基 本 知 识 (续 )
空格所隐藏的字符属于多余度字符，不
用那些字符也能运载该句子的全部信息，
比如：“我 __大 ________使 ______机来
____数 __。”就很难猜出完整的句子，在
信息传递的时候，也很难做检错和抗错。
因此，保留一定的多余度 (或冗余度 )是非常
重要的。
2,信息量和信息熵基本定义 (1)
信息熵（ information entropy）是对
信息状态“无序”与“不确定”的度量
（从本质上讲，熵不是对信息的度量，但
信息的增加而使产生的熵减小，熵可以用
来度量信息的增益）。
2,信息量和信息熵基本定义 (2)
定义：给定一离散集合 X={xi; i=1,2,…,n}，
令 xi出现的概率是 且 。事件 xi
包含的信息量
通常 =2，此时相应的信息量单位是 bit。
Shannon定义信息的数学期望为信息熵，即
信源的平均信息量。
( ) 0ipx ?
1
( ) 1n i
i
px
?
??
)(l o g)( iai xPxI ?? (2.1)
2,信息量和信息熵基本定义 (3)
定义：将集合 X中事件所包含的信息量统计
平均，则平均值定义为集合 X的熵,信息熵表
征了信源整体的统计特征，集合 X的熵 H（ x）
表示 X中事件所包含的平均信息量，或总体
的平均不确定性的量度。
0)(lo g)()](lo g[)( 2
1
2 ???? ?
?
i
n
i
ii xpxpxPExH
(2.2)
2,信息量和信息熵基本定义 (4)
对某一特定的信源，
其信息熵只有一个，
因统计特性不同，其
熵也不同。例如，两
个信源，其概率空间
分别为：
12[,( ) ]
0, 9 9 0, 0 1i
xx
X P x
??
? ??
??
12[,( ) ]
0, 5 0, 5i
yy
Y P y
??
? ??
??
2,信息量和信息熵基本定义 (5)
则信息熵为：
可见，,说明信源 比信源 的平均不确定
性要大，即在事件发生之前，分析信源,由于事
件 是等概率的，难以猜测哪一个事件会发生,
( ) 0, 9 9 l o g 0, 9 9 0, 0 1 l o g 0, 0 1 0, 0 8 [ ]H X b i t? ? ? ?
( ) 0, 5 l o g 0, 5 0, 5 l o g 0, 5 1 [ ]H Y b i t? ? ? ?
( ) ( )H Y H X? Y X
Y
21,yy
2,信息量和信息熵基本定义 (6)
而信源,虽然也存在不确定性，但大致可以
知道,出现的可能性要大。正如两场比赛，其中
一场，双方势均力敌；而另一场双方实力悬殊很
大。当然,人们希望看第一场，因为胜负难卜，一
旦赛完，人们获得信息量大。也可以这样理解，
信息熵 表征了变量 的随机性。因此，熵反映了变
量的随机性，也是表征随机变量统计特性的一个
特征参数。
X
1x
3,信息熵的基本性质 (1)
I,对称性
当概率空间中 序任意互换时，
熵函数的值不变，例如下面两个信源空
间,
?)(),( 21 xPxP
?
?
?
?
?
?
?
?
?
2
1
6
1
3
1)](,[
321 xxx
xPX
?
?
?
?
?
?
?
?
?
3
1
2
1
6
1)](,[
321 yyy
yPX
3,信息熵的基本性质 (2)
其信息熵,该性质说明，熵
只与随机变量的总体结构有关，与信源总
体的统计特性有关，同时也说明所定义的
熵有其局限性，它不能描述事件本身的主
观意义。
)()( YHXH ?
3,信息熵的基本性质 (3)
II,确定性
如果信源的输出只有一个状态是必然的,
即 则信源的熵,
此性质表明，信源的输出虽有不同形态，但其中
一种是必然的，意味着其他状态不可能出现。
那么，这个信源是一个确知信源，其熵为零。
,0)()(,1)( 321 ???? ?xPxPxP
2
( ) [ 1 l o g 1 0 l o g 0 ] 0
n
i
HX
?
? ? ? ? ? ??
(2.3)
3,信息熵的基本性质 (4)
III,非负性
即 。 因为随机变量 的所有取值的
概率分布为,当取对数的底大
于１时，,而,则得到
的熵是正值，只有当随机变量是一确知
量时，熵才等于零。这种非负性对于离
散信源的熵来说，这一性质并不存在。
0)( ?XH
1)(0 ?? ixP
0)(lo g ?ixP 0)(lo g)( ?? ii xPxP
3,信息熵的基本性质 (5)
IV,可加性
独立信源 和 的联合信源的熵等于它们各自的
熵之和。 如果有两个随机变量 和, 它们彼此是
统计独立的，即 的概率分布为,
而 的分布概率为,则联合信源
的熵,
可加性是熵函数的一个重要特性，正因为有可加性，
所以可以证明熵函数的形式是唯一的。
X Y
X Y
X )](,),(),([ 21 sxPxPxP ?
Y )](,),(),([ 21 zyPyPyP ?
)()()( YHXHXYH ??
1)(
1
??
?
N
i
ixP 1)(1 ???
M
j
iyP
3,信息熵的基本性质 (6)
V,极值性
信源各个状态为零概率分布时，熵值最
大，并且等于信源输出状态数，因为
当 时，
(2.5)
NxPxPxP s /1)()()( 21 ???? ?
N
NN
XH
N
i
l o g1l o g1)(
1
??? ?
?
例 题
例，信源有两种状态时，概率空间
其 与 关系如图所示,，当 =1/2时熵有最大值；
当信源输出是确定的，即,则,此时表
明该信源不提供任何信息；反之，当信源输出为等概
率发生时，即 时信源的熵达到最大值，等于
1bit信息量。
?????? ?? )(1)P ( x)](,[
11
21
xP
xxxPX
i
)(XH )(xP )(xP
1)( 1 ?xP 0)( ?XH
2/1)( 1 ?xP
信息熵函数曲线
P(x)
0 0.5 1
明
文
H(x)
4,信息熵在信息加密编码中的作用 (1)
通过熵和信息量的概念，可计算加密系统中各
部分的熵。令明文熵为,密钥
熵,密文熵 。这里 M、
K和 C分别是明文、密钥和密文空间,m,k、
c分别是它们的字母集,l,r和 v分别是明文、密
钥、和密文的长度。则明文和密文之间的互信
息以及密钥与密文之间的互信息分别是：
)()( lmHMH ?
)()( rkHKH ? )()( vcHCH ?
)()();( vllvl cmHmHcmI ??
)()();( vrrvr ckHkHckI ??
(2.6)
(2.7)
4,信息熵在信息加密编码中的作用 (2)
因为只要密文、密钥确定后，明文也就得到了，所以
,故
定理：对任意加密系统
从该理论我们可以看出，密钥熵越大，密文中所包含的
明文信息量就越小。一个加密系统中，若其密文与明
文之间的互信息,则密码分析者无论截
获多大的密文，均不能得到有关明文的任何信息。这
种加密系统称为完善加密系统，或无条件加密系统。
0)),()( ?rvl kcmH )()),(;( lrvl mHkcmI ?
)()();( KHmHcmI lvl ??
(2.8)
0);( ?vl cmI
4,信息熵在信息加密编码中的作用 (3)
在对密文攻击下，完善加密系统是安全的，但它不能
保证在已知明文或选择性明文攻击下也是安全的。因
此，完善保密系统存在的必要条件是
证明：若,则由前一个定理可
得，,所以 的必要条件是
)()( lmHKH ?
(2.9)
)()( lmHKH ?
0);( ?vl cmI 0);( ?vl cmI
)()( lmHKH ?
2.1.2 数论基本术语
? 数论是研究整数性质的一个数学分支，
同时也是加密技术的基础学科之一。首
先介绍一些数论的基本知识,
1,整 数
定义：设 。如果存在 使得,那么就说 b可
以被 a 整除，记为,且称 b是 a的倍数,a 是 b的因数 (或称约
数、除数、因子 ) 。 b不能被 a整除可以记作 dFa。由定义及乘
法运算的性质，可推出整除关系具有以下性质（注：符号
本身包含了条件 ）：
（ 1） ；
（ 2）如果 且,则 ；
（ 3）设,那么 与 等价 ;
（ 4）如果 且,则对所有的,有 ;
（ 5）设,如果,那么 ;
0,,?? aZba Zq? aqb?
ba
ba
0?a
aa
ba cb ca
0?m ba bmam
ba ca Zyx ?,cybxa ?
0?b ba ba ?
2,素 数
定义,设整数 。如果它除了显然因数 外没有其他的
因数，则 p就称为是素数，也叫不可约数。若, 且 a不
是素数，则 a称为合数。
关于素数，有以下性质：
（ 1）如果 p是素数，且,则 或,即 p至少整除 a与 b中
的一个。
（ 2）任何一个整数,均可以分解成素数幂之积：
（ 3）若不计因数的顺序，这个分解式是唯一的。其中,
是两两互不相同的素数,是正整数。
（ 4）素数有无穷多个。
（ 5）设 表示不大于 的素数的数目，则 。
0?p p??,1
0?a 1?
abp ap bp
2?n kekee pppn ?21 21?
1?k ip )1( ki??
)1( kiei ??
)(x? 1/ln)(lim ?xxx?
3,同 余
设,如果,则称 a和 b模 n同
余，记为,整数 n称为模数。由
于 等价于,所以 与
等价。因此，一般我们总假定 。如
果,我们称 b是 a对模 n的最小非负剩
余，有时也称 b为 a对模 n的余数。
0,,?? nZba )( ban ?
)( m o dnba ?
ban ? ban ?? )(m o dnba ? ))( m o d ( nba ??
1?n
nb ??0
同余式的一些基本性质
（ 1）反身性, ；
（ 2）对称性,如果,那么 ；
（ 3）传递性,如果,,那么 ；
（ 4）如果, 那么； 。
（ 5）如果,, gcd, (两个
不同时为 0的整数 a与 b的最大公约数表示成 gcd(a,b))那
么,存在,当且仅当 gcd 。
)(m o dnaa ?
)(m o dnba ? )(m o dnab ?
)(m o dnba ? )(m o dncb ? )(m o dnca ?
)(m o d1 naa ? )(m o d1 nbb ? )( m o d11 nbaba ???
)( m o d11 nbaba ??? )( m o d11 nbaab ?
)(m o dnbdac ? )(m o dnba ? 1),( ?na
)(m o dndc ? )(m o d1 nac ? 1),( ?na
一些关于同余的基本概念 (1)
同余类 可用其中任一元素
a(经常取 )代替，记作 。于是
从 中分别取一个数作为代表构成
一个集合，称为模 n的一个完全剩余系，
记为,称为模 n的非负最小完
全剩余系。
}0,{ qrZqqnr ????
ra? ][a
]1[]1[]0[ ?? nz ???? )10(][][ ????? njiji ??
(2.11)
]1[,],1[],0[ ?n?
}1,,1,0{ ?n? nZ
一些关于同余的基本概念 (2)
在模 n的完全剩余系中，去掉那些与 n不互素的数，
剩下的部分称为模 n的简化剩余系； 的简化剩余
系记为,读为模 n的非负最小简化剩余系。显
然,中的元便是不超过 n并与 n互素的那些数，
它们的个数等于欧拉函数 的值。 （欧拉函数
的定义为, 小于自然数 N并与 N互质 (除 1以外无其
它公因子 )的自然数的个数用函数 表示,称为欧
拉函数。欧拉函数的具体性质会在后面第 6小节进
行阐述）
nZ
*nZ
*nZ
)(n?
)(n?
4,模 运 算
给定正整数 n，对任意 a，若存在 q，使得
则称 r是 a关于模 n的余数，
记为 。
若 则称整数 a,b同余，记
为
整数集中所有与数 a同余的整数集合称为 a
的同余类，记为 。
)0( nrrqna ????
nar mod?
)m o d()m o d( nbna ?
(m o d )a b n?
??na
模 运 算 的 性 质
（ 1） 当且仅当 。
（ 2） 当且仅当 。
（ 3）如果,,则 。
a模 n的运算给出了 a对模 n的余数。注意：模运算的结果
是从 0到 的一个整数。模运算就像普通的运算一样，
它是可交换，可结合，可分配的。而且，对每一个中间
结果进行模 m运算，其作用与先进行全部运算，然后再
进行模 m运算所得到结果是一样的。
)( m o dnba ? )( ban ?
)(m o dnba ? )(m o dnab ?
)(m o dnba ? )(m o dncb ? )(m o dnca ?
1?n
5,最大公约数与最小公倍数
设, 是两个整数，如果 且,那么就称 b是 和 的公
约数,一般的，设,是 K个整数，如果
那么就称 b是 的公约数。因为对于任意一个不等于零
的整数，它的因数是有限的。所以，任意一对整数,其中一
个不为零时，它们的公约数的个数也必定是有限的；同理，当
中有一个不为零时，它们的公约数是有限的,这样,我们引入最大公
约数的概念。
定义, 设, 是两个整数，我们把 和 的公约数中最大的数
称为 和 的最大公约数，记为 (,)或
当 时，我们称 和 是互素的。 显然
1a 2a 1ab 2ab 1a 2a
kaaa,,,21 ? kababab,,,21 ?
kaaa,,,21 ?
21,aa
kaaa,,,21 ?
1a 2a 1a 2a
1a 2a ),gcd( 21 aa
1),( 21 ?aa 1a 2a 0),( 21 ?aa
1a 2a
最 大 公 约 数 的 性 质
（ 1）
（ 2）若 |,j=2,…,k,则
（ 3）任意的整数 x,有
（ 4）对任意的整数 x,有
（ 5）设,是不都为零的整数，则一定存
在一对整数,，使得：
),(),(),( 211221 aaaaaa ???
1a ja 12121 ),,,(),( aaaaaa k ?? ?
),,(),( 12121 xaaaaa ?
),(),( 12121 xaaaaa ??
1a 2a
1x 2x 221121
),( xaxaaa ??
最 小 公 倍 数 的 概 念
设, 是两个均不等于零的整数，如果
且,那么 1 就称为是 和 的公倍数，
一般地，设 是 k个均不等于零的整数。
如果,则称 l是 的公倍数。
公倍数的集合是无穷集合，但根据自然数的理
论，存在最小的正的公倍数。我们把 和
的正的公倍数中最小的数称为 和 的最小
公倍数，记为 或
1a 2a 11a
12a 1a 2a
kaaa,,,21 ?
1,,1,1 21 kaaa ? kaaa,,,21 ?
1a 2a
1a 2a
],[ 21 aa ),( balcm
6,欧拉 （ Euler） 函数
欧拉（ Euler）函数
设 n≥1,欧拉函数 表示在区间 中与 n互素的
整数的个数。
欧拉函数 具有以下性质：
(1)如果 p是素数，则 ；
(2)如果 p是素数,。那么 ；
(3)对于整数,根据算术基本定理,n可以分解成惟一的形
如 的分解式，则
(4)若 和 互素，则 。
)(n?
?? Zzn,)(? ],1[ n
)(n?
1)( ?? pp?
1?k )1()( 1 ?? ? ppp kk?
2?n
kekee pppn ?21 21? )/11()/11)(/11()( 21 kpppnn ???? ??
1m 2m )()()( 21 mmm ??? ?
2.1.3 算法复杂性基础知识
所谓问题，是指一个要求给出解释的一
般性提问，通常含有若干个未定参数或自由
变量。它由两个要素组成,第一个要素是描
述所有的参数，也就是对所有未定参数的一
般性描述 ;第二个要素是解答必须满足的性质。
一个问题 可以看成是由无穷多个问题实例组
成的一个类。
1,算 法 的 定 义
所谓 算法 是由明确指出操作的规则所组成的
若干语句的集合，只要按照规则一步一步执行一
定数目的语句，便可求出问题的答案。通常的计
算机程序都可以看作是算法的表达形式，在问题
的两要素中，对算法而言，第一个要素就是“输
入”，第二个要素就是“输出”。如果把问题 P的
任意一个实例作为算法 A的输入,A在有限步骤之
内总能输出关于此实例的正确答案，我们就说算
法 A可解问题 P。对于一个问题 P，如果存在一个
算法 A可解问题 P，我们称问题 P是 算法可解 的。
2,算 法 复 杂 性
算法的复杂性表征了算法在实际执行时所需计
算能力方面的信息, 通常它由该算法所要求的最
大时间与存取空间来确定。 由于算法所需的时间
和空间往往取决于问题实例的规模 n (n表示了该
实例的输入数据长度 )，同时，算法在用于相同规
模 n的不同实例时。其时间和空间需求也可能会有
很大差异，因此，实际中我们常常研究的是算法
关于输入规模 的所有实例的时间与空间需求的平
均值。
算 法 复 杂 性 的 构 成
通常情况下，一个算法的计算复杂性由两个变
量度量：时间复杂性 和空间复杂性 。它们
定义如下：
（ 1） 时间复杂性,以某特定的基本步骤为单元，
完成计算过程所需的总单元数称为算法的时间复杂
性，或时间复杂度。 n为输入的规模或尺寸。
（ 2） 空间复杂性,以某特定的基本存储空间为单
元，完成计算过程所用的存储单元数，称为算法的
空间复杂性或空间复杂度。 n是输入的规模或尺寸。
)(nT )(nS
)(nT
)(nS
算法复杂性的基本符号 （ 1）
一个算法的计算复杂性用,O”符号表示其
数量级。,O”的意思是：对于两个任意的
实值函数 f和 g，若记号,则
存在有一个值 a，对充分大的 n，
有 。计算复杂性的数量级就是这
种类型的函数，即当 n变大时增长得最快的
函数，所有常数和较低阶形式的函数可以
忽略不计。
??? nngOnf ) ),(()(
)()( nganf ?
算法复杂性的基本符号 （ 2）
另一个符号是,o”。它的定义是：
当且仅当,这意味着在 时，
比 可以忽略不计。 时间复杂度 有时
也用工作因子 W表示，这时 。如果一个算
法的复杂性不依赖于 n，那么它是常数级的用 表
示之，而 表示复杂性随 n线性增长，因而是线
性型算法。复杂性随 n线性增长的其他一些算法也
称为二次方或三次方等，所有这些算法都是多项
式的，它们的时间复杂性是 。有多项式
时间复杂性的算法称为多项式时间算法或有效算
法。
??? nngonf ) ),(()(
lim ( ) / ( ) 0n f n g n?? ? ??n
)(nf )(ng ))(( ngo
)(ngW ?
)1(o
)(no
)()( lnonT ?
3,问 题 的 复 杂 性
问题的复杂性是问题固有的性质。问题
的复杂性理论利用算法复杂性作为工具，
将大量典型的问题按照求解的代价进行分
类。问题的复杂性由在图灵机上解其最难
实例所需的最小时间与空间决定，还可以
理解为由解该问题的最有效的算法所需的
时间与空间来度量。
N P 问 题
在确定型图灵机上可用多项式时间求解的问
题，称为易处理的问题。易处理的问题的全体称
为确定性多项式时间可解类，记为 P类。在非确定
性图灵机上可用多项式时间求解的问题，称为非
确定性多项式时间可解问题，记为 NP问题 。 NP问
题的全体称为非确定性多项式时间可解类，记为
NP类。显然，,因为在确定型图灵机上多项
式时间可解的任何问题在非确定型图灵机上也是
多项式时间可解的。
NPP ?
N P C 问 题
NP类中还有一类问题称为 NP完全类，记为 NPC。所
有的 NP问题都可以通过多项式时间转换为 NPC中的
问题。 NPC是 NP类中困难程度最大的一类问题,但
NPC中的问题困难程度相当，都可以多项式时间转化
为称为可满足性问题的 NPC问题，此类 NPC具有如下
性质，若其中的任何一个问题属于 P，则所有的 NP问
题都属于 P，且 。现在的密码算法的安全性都
是基于 NPC问题的，破译一个密码相当于求解一个
NPC问题,如果,则破译密码就是一件很容易
的事情,
NPP ?
NPP ?
2.2 信息加密方式与标准
经典的信息加密理论主要用于通信保密，而
现代信息加密技术的应用已深入到信息安全的各
个环节和对象，信息的加密方式和标准也有了深
入广泛的发展，特别是现代加密和信息隐藏技术
的结合，实现信息隐蔽传输使人类对信息的加密
技术有了新的认识和要求，下面介绍信息加密技
术的基本概念、方式和标准。
2.2.1 信息加密基本概念 （ 1）
研究安全信息的加密技术和研究破解安全信息密码的密
码分析技术的学科称为 密码学 。信息加密是通过使用一种编
码而使某些可读的信息 (明文 )变为不可读的信息 (密文 )。这
些编码就是将明文变成密文的加密算法 (也称为密码 )或数学
方法。密码使用隐蔽语言、文字、图象的特种符号，目标是
接收数据作为输入，产生密文作为输出，以便数据的原始意
义得以隐藏。在计算机通讯中，采用密码（密钥为参数）将
信息隐蔽起来，再将隐蔽后的信息传输出去，使信息在传输
过程中即使被窃取或载获，也不能了解信息的内容，从而保
证信息传输的安全。
2.2.1 信息加密基本概念 （ 2）
通信两端将信息编码时，发送端使用简单
的信息加密；接收端收到传来的信息后通过解
密看到编码前的信息，整个过程中加密或解密
是由密钥控制实现的。 密钥 是用户按照一种密
码体制随机选取，它通常是一随机字符串，是
控制明文变换（加密）和密文变换（解密）的
唯一参数。密钥全体称为密钥空间。一般来说，
密钥越大，加密就越健壮。
加密系统的组成部分
如上所述，一个加密系统实际上是某种加密算法在
密钥控制下实现的从明文到密文的映射，它至少包括下
面四个组成部分：
（ 1）加密的报文，也称明文；
（ 2）加密后的报文，也称密文；
（ 3）加密解密设备或算法；
（ 4）加密解密的密钥；
一般情况下，密钥由 K表示，明文由 m表示，加密算法
由 ( ) 表示，解密算法由 ( ) 表示，；
则,( ( m )) =m
1EK
2DK
2DK
1EK
加密系统示意图
一个完整的加密系统如下图所示,
信源 加密 解密 信宿
密文明文
窃听 干扰
明文
密钥 K1 密钥 K2
图 2.2 加密系统示意图
加密系统的安全规则 （ 1）
任何一个加密系统必须基本具备四个安
全规则：
（ 1）机密性 (confidentiality)：加密系统在信
息的传送中提供一个或一系列密钥来把信
息通过密码运算译成密文，使信息不会被
非预期的人员所读取，只有发送者和接收
者应该知晓此信息的内容。
加密系统的安全规则 （ 2）
（ 2）完整性 (integrity)：数据在传送过程中不应被
破坏，收到的信宿数据与信源数据是一致的。应
该选取健壮的密码和加密密钥，以确保入侵者无
法攻破密钥或找出一个相同的加密算法，阻止入
侵者会改变数据后对其重新加密。有时，数据完
整性可以通过适当的方法在信息还未被完全修改
时检测到，如：密码散列函数是单向密码，它为
明文产生惟一的“指纹”，当明文被拦截和读取，
要修改它将改变散列，致使有意向的接收者很容
易看出散列之间的差异。
加密系统的安全规则 （ 3）
（ 3）认证性 (authentication),加密系统应该提供数字签名技术来
使接收信息用户验证是谁发送的信息，确定信息是否被第三者篡
改。只要密钥还未泄露或与别人共享，发送者就不能否认他发送
的数据。实际应用中，假如发送者和接收者都使用一个对称密钥，
对于整体信息加密或计算机网络上的链路级加密，在两个路由器
之间建立一个加密会话，以通过因特网发送加密信息。连接到网
络的计算机发送明文给路由器，明文被转换为密文，然后通过因
特网发送到另一端的路由器。在整个加密数据形成和传递过程中，
加密方网络内部和非加密方的任一节点都能插入信息，并在这一
层次分析，但对于接收者这一节点来说你只能判定信息是否来自
某个特定的网络，而要确认信息的发送节点，这将使验证机制变
得很复杂。
加密系统的安全规则 （ 4）
（ 4）非否定 (non-repudiation)：加密系统除了应该验
证是谁发送的信息外，还要进一步验证收到的信息是
否来自可信的源端，实际上是通过必要的认证确认信
息发送者是否可信。现代健壮的验证方法用加密算法
来比较一些已知的信息段，如 PIN(个人识别号 )判断
源端是否可信。
非否定规则应属于认证性规则中的一部分。一般来说，
前三个规则一起被称为 CIA 。从技术的角度来看，所
有的加密都提供了私有性和完整性，其余的均由此衍
生，这包括非否定和认证性规则。
2.2.2 信息加密方式
1,信息加密方式分类
对存储的文件和网络中传输的数据包实施信息加密，其加
密方式可以根据加密系统不同的特征划分,
（ 1） 按密钥方式划分
对称式加密, 收发双方使用相同密钥。加密和解密使用同一密
钥。加密算法和解密算法在对称式加密中是相同的，加密和解
密使用同一密钥 K表示。
非对称式加密, 也称公用密钥加密，加密和解密使用不同密钥。
它通常有两个密钥，称为“公钥”和“私钥”。它们两个必需
配对使用，否则不能打开加密文件。这里的“公钥”是指可以
对外公布的，“私钥”则不对外公布，只有持有人知道。加密
算法和解密算法在非对称式加密中是不相同的； K1是加密密钥,
是公开的，称为公钥,K2是解密密钥，称为私钥，则须保密。
2种不同方式的加密示意图
明文解密
密钥 K2
明文 加密
密钥 K2
K K
密文传输
图 2.2 对称式 加密示意图
明文 解密
密钥 K2
K1 K2
加密
密钥 K2
明文
图 2.3 非对称式 加密示意图
1,信息加密方式分类
（ 2）按保密程度划分
理论上保密的加密：无论获取多少密文和有多大的计算能力，
对于明文始终不能得到唯一解的加密方法。如：采用客观随机一
次出来的密码就属于这种加密方式。
实际上保密的加密：从理论的角度是可以破解的，但在现有客
观条件下，无法通过计算来确定唯一解。
（ 3）按明文形态划分
模拟信息加密：用来加密模拟信息。如：动态范围之内，连续
变化的语音信号的加密。
数字信息加密：用来加密数字信息。如：两个离散电平构成 0、
1二进制关系的电报信息的加密。
2,数 字 签 名
数字签名是对原信息附上加密信息的过程，是一种身份认
证技术，支持加密系统认证性和非否定；签名者对发布的原信
息的内容负责，不可否认。数字签名采用非对称式加密（也称
公钥加密标准）对信息 m使用私钥 K2加密，运算如下：
S=DK2(m) 其中 S为签名,D为解密算法；接收者收到发送者发
来的 S和 m信息，同时从公开媒体找到了发送者的公钥 K1,发送
者用 K2对 S进行如下运算,E K1 (S)= E K1 (DK2(m))= m,E为加
密算法；收到的 m对应计算出来的 m，结果说明信息确实来源于
发送者，第三方不可能知道私钥 K2，无法篡改 S，发送者无法
否认发送 m信息。在实际工作中，由于解密计算缓慢，为了提
高签名速度,m信息往往要经过压缩或散列处理或尽量取简短
信息，如公钥数据等。
数字签名工作流程图
信息 m
密钥 K2
私钥 K 2
公钥 K1
信息 m
密钥 K2
解密算法
密钥 K2
签名 S
密钥 K2
签名 S
密钥 K2
加密算法
密钥 K2
图 2.4 数字签名工作流程图
3,网 络 信 息 加 密
网络信息加密的目的是保护网内的数据、文件、口令和控制
信息，保护网上传输的数据。网络加密常用的方式有链路加密和
端点加密。
（ 1）链路加密
链路加密对链路层数据单元进行加密保护，其目的是保护网络节
点之间的链路信息安全。这种加密不但对节点之间之间传输的数
据报文加密，还要把路由信息、校验和控制信息包括数据链路层
的帧头、位填充和控制序列等都进行加密；当密文传输到某一节
点时，全部解密获得链信息和明文，然后全部加密后发送往下一
个节点；对于这种加密，加密设备的设计相对复杂，必须理解链
路层协议和必要的协议转换。
链路加密的优缺点
链路加密非常有效，是因为几乎任何有用消息都被加密保护。加密范
围包括用户数据、路由信息和协议信息等。因此，攻击者将不知道通信的
发送和接受者的身份、不知道信息的内容、甚至不知道信息的长度以及通
信持续的时间。而且，系统的安全性将不依赖任何传输管理技术。密钥管
理也相对简单，仅仅是线路的两端需要共同的密钥。线路两端可以独立于
网络的其他部分更换密钥。
链路加密的缺点是：整个连接中的每段连接都需要加密保护。对于包含不
同体系机构子网络的较大型网络，加密设备、策略管理、密钥量等方面的
开销都是巨大的。另外，在每个加密节点，都存在加密的空白段：明文信
息，这是及其危险的，特别是对于跨越不同安全域的网络。后来，为解决
节点中数据是明文的缺点，在节点内增加了加解装置，避免了节点明文，
这种加密方式称为节点加密；但和链－链加密一样，同样依靠公共网络节
点资源的配合，开销依然很大。
端 点 加 密
端点加密的是对源端用户到目的端用户的数据提供加密
保护。既将加密模块置于网络以上的加密方式。端点加密中，
数据从加密的端节点，一直到对应的解密节点，数据在整个
传输过程中都保持密文形式，从而克服了链路加密出现加密
空白段（中间节点明文信息）的问题。由于加密和解密只发
生在两个端节点，因此对中间节点是透明的。这样大大减少
了安装设备的开销（特别是中间节点设备开销），以及复杂
的策略管理和密钥管理所引起的麻烦。由于加密范围往往集
中在高层协议数据，还极易为不同流量提供 QoS服务，实现
按特定流量进行加密和不同强度的加密。从而有利于提高系
统的效能，优化系统的性能。
端点加密的缺点
端点加密的缺点是：由于通信环境往往比较复杂，要
在跨越网络的两个端用户之间成功地完成密钥的建立是需
要付出性能代价的。其次，端点加密不能保护数据传输过
程中的某些信息，如路由信息、协议信息等，一个训练有
素的攻击者可以借助这些信息发动某些流量分析攻击。另
外，端点加密设备（模块）的实现十分复杂，要求设备必
须理解服务的提供层的协议，并且成功调用这些服务，然
后在设备中对对应的数据进行密码处理，并且将处理后的
数据传送给上层协议。如果加密设备不能为上层协议提供
良好的服务接口，则将对通信的性能产生较大的影响。
2.2.3 数据加密标准
1,对称密钥加密 DES
DES(data encryption standard)是 1976年由美国国
家标准局颁布的一种加密算法，属于对称密钥加密算
法体制，早期被公认为较好的加密算法，经过长期严
验证后，被国际标准化组织接受作为国际标准。 DES
自它应用 20多年来，不断经受了许多科学家破译，同
时也成为密码界研究的重点。 DES对称密钥加密算法
广泛的应用在民用密码领域，为全球贸易、金融等非
官方部门提供了可靠的通信安全保障。
DES的相关知识
DES主要采用替换和移位的加密方法用 56位密钥对 64位二进制
数据块进行加密，加密每次可对 64位的输入数据进行 16轮编码，经
过一系列替换和移位后，原始的 64位输入数据转换成了完全不同的
64位输出数据。 DES算法运算速度快，生成密钥容易，适合于在当
前大多数计算机上用软件方法和专用芯片上实现。但 DES密钥太短
（ 56位），密钥健壮性不够好，降低保密强度；同时,DES安全性
完全依赖于对密钥的保护，在网络环境下使用，分发密钥的信道必
须具备有力的可靠性才能保证机密性和完整性。
DES算法还有一些变形，如：三重 DES和广义 DES等。目前，
DES应用领域主要包括：计算机网络通信中的数据保护（只限于民
用敏感信息）；电子资金加密传送；保护用户存储文件，防止了未
授权用户窃密；计算机用户识别等。
2,Clipper加密芯片标准
这种数据加密标准对用户只提供加密芯片（ Clipper）和硬件
设备，它的密码算法不公开，密钥量比 DES多 1000多万倍，是美国
国家保密局（ NSA）在 1993年正式使用的新的商用数据加密标准，
目的是取代 DES，提高密码算法的安全性，主要用于通信交换系统
中电话、传真和计算机通信信息的安全保护。为确保更可靠的安全
性，加密设备的制作方法按照 Clipper芯片由一个公司制造裸片，再
由另一公司编程严格规定来实施。
Clipper芯片主要特点是充分利用高的运算能力的设备资源加大密钥
量，从而用于计算机通信网上的信息加密，如：政府和军事通信网
中数据加密芯片的研究不断换代使它还实现了数字签名标准和保密
的哈希函数标准以及用纯噪声源产生随机数据的算法等。
3,国际数据加密标准
这种算法是在 DES算法的基础上发展的。与
DES相同，国际数据加密算法 IDEA
（ international data encryption algorithm）也是
针对数据块加密；它采用 128位密钥，设计了一系
列加密轮次，每轮加密都使用从完整的加密密钥
中生成的一个子密钥，基于这种算法，采用软件
实现和采用硬件实现同样快速，非常适合于对大
量的明文信息的快速加密。它在 1990年正式公布
并在以后得到了增强。
传统加密方法的缺点
在网络通信中，传统的对称加密方法是发送者加密、接收
者解密使用同样的密钥，这种方法虽然有运算快的特点，随着
用户的增加，大量密钥的分配是一个难以解决的问题。例如，
若系统中有 n个用户，其中每两个用户之间需要建立密码通信，
则系统中每个用户须掌握 (n-1)/2个密钥，而系统中所需的密钥
总数为 n*(n-1)/2 个。对 10个用户，每个用户必须有 9个密钥，
系统中密钥的总数为 45个。对 100个用户，每个用户必须有 99个
密钥，系统中密钥的总数为 4950个。这还仅考虑用户之间的通
信只使用一种会话密钥的情况。如此庞大数量的密钥生成、管
理、分发确实是一个难处理的问题。因此，对称加密方法所带
来的密钥的弱的健壮性和密钥管理的复杂性局限了它的发展。
4,公开密钥加密标准
早在 20世纪 70年代，美国斯坦福大学的两名学者
迪菲和赫尔曼提出了一种加密方法 ―― 公开密钥加密
方法，解决了传统加密体系的密匙分配复杂的缺点。
公开密钥加密方法是非对称加密方式，该技术采用不
同的加密密钥和解密密钥对信息加密和解密，每个用
户有一个对外公开的加密算法 E和对外保密的解密算
法 D，它们须满足条件：
（ 1） D是 E的逆，即 D[E（ X） ]=X。
（ 2） E和 D容易计算。
（ 3）如果由 E出发求解 D十分困难。
公钥及私钥的概念
若加密密钥可对外公开，称为 公钥 ；一个用户向
另一用户传送信息，首先通过开放途径 (如 BBS)的获
得另一用户的公开密钥，对明文加密后发送，而另
一用户唯一保存的解密密钥是保密的，称为 私钥,
另一用户通过安全的方法验证信源可靠后，私钥将
密文复原、解密。理论上解密密钥可由加密密钥推
算出来，但这种算法设计在实际上是不可能的，或
者虽然能够推算出，但要花费很长的时间和代价，
所以，将加密密钥公开不会危害密钥的安全。
RSA 算 法
著名的 RSA正是基于这种理论，算法以发明者的名字命名：
Ron Rivest,Adi Shamir 和 Leonard Adleman.这种算法为公用网络
上信息的加密和鉴别提供了一种基本的方法。为提高保密强度，
RSA密钥至少为 500位长，一般推荐使用 1024位，这就使加密的计
算量很大。同时，为减少计算量，在传送信息时，常采用传统对
称加密方法与 RSA公开密钥加密方法相结合的方式，信息明文加
密采用改进的 DES或 IDEA加密方法，使用 RSA用于加密密钥和信
息摘要。对方收到信息后，用各自相关的密钥解密并可核对信息。
但是 RSA并不能替代 DES等对称算法,RSA的密钥长，加密速度
慢，而采用 DES等对称算法加密速度快，适合加密较长的报文，
弥补了 RSA的缺点。美国的保密增强邮件系统 （ PEM） 就是采用
了 RSA 和 DES结合的方法，目前已成为 E-MAIL保密通信标准。
5,量子加密方法
量子加密与公钥加密标准同期出现，适用于网络上加
密普通宽带数据信道所传送的信息，工作原理是两端用户各自
产生一个私有的随机数字符串，两个用户向对方的接受装置发
送代表数字字符串的单个量子序列（光脉冲），接受装置从两
个字符串中取出相匹配的比特值组成了密钥。实现了会话或交
换密钥的传递。由于这种方法依赖的是量子力学定律，传输的
光量子是无法被窃听的；如果有人进行窃听，就会对通信系统
造成干扰，对通信系统的量子状态造成不可挽回的变化，通信
双方就会得知有人进行窃听，从而结束通信，重新生成密钥。
这种加密技术不久的将来应该有应用和发展，但是如何实现数
字签名有待于研究。
2.3 公钥信息加密算法
随着密码技术的发展,Diffie和 Hellman在
IEEE提出提出了公钥密码系统，即加密密钥和
解密密钥不是同一把密钥。现在公钥密码系统被
广泛的应用，其中 RSA加密算法,Diffie-Hellman
算法,ElGamal加密算法，椭圆曲线加密算法被广
泛研究和应用。
2.3.1 RSA加密算法
RSA的安全性依赖于大数分解。公钥及私钥都是两个大素数（大
于 100个十进制位）的函数，从一个密钥和密文推断出明文的难度等
同于分解两个大素数的积。算法如下：
１,生成密钥
（ 1）秘密的选取两个大数 p,q
（ 2）计算,,这 指的是 Euler函数
（ 3）选取整数 e，满足 且 。
（ 4）计算 d,满足 。即 d是 e关于模 乘的逆元，
（ 乘法逆元, 设,如果存在, 满足,则称 x
是 a的模 n乘法逆元，记为 (mod n) ）由 e的定义,d唯一。
（ 5）输出公钥,私钥 。
qpn ?? )1)(1()( ??? qpn? )(n?
)(1 ne ??? 1)),(gc d( ?en?
))(( m o d1* ned ?? )(n?
naZ? nxZ?
1(m od )ax n?
1a?
},{ ne },{ nd
具体加密解密操作
加密操作
选定,把明文分成长度为 k的组块。对每个
明文分组 M,M在 0到 (n-1)之间。加密操作为：
解密操作
得到密文分组 C，解密操作为：
][lo g )1(2 ?? nk
nMC e m o d?
(2.14)
nCM d m o d?
(2.15)
RSA算法的局限性 （ 1）
（ 1）有限的安全性
RSA是一种分组密码算法，它的安全是基于数论中大的整数 n
分解为两个素数之积的难解性。目前,RSA的一些变种算法已被
证明等价于大数分解。同样，分解 n也是最显然的攻击方法。现在，
人们已能分解 140多个十进制位的大素数。因此，适用具体情况而
定，模数 n必须选尽可能大。同时要注意，如果系统中共享一个模
数，不同的人拥有不同的公钥 e1和 e2，这些公钥共模而且互质，假
如普遍的情况是同一信息用不同的公钥加密，那么该信息无需私
钥就可得到恢复。即设 P为信息明文,C1和 C2为密文，公共模数
是 n，则,C1 = P^e1 mod n ； C2 = P^e2 mod n 密码分析者知道 n、
e1,e2,C1和 C2，就能得到 P。解决办法只有一个，那就是不要共
享模数 n。
RSA算法的局限性 （ 2）
（ 2）运算速度慢
RSA算法进行的都是大数计算，使得其最快的情况也比 DES
慢上 100倍，无论是软件实现还是硬件实现。速度一直是 RSA算
法的缺陷。一般来说 RSA算法只用于少量数据加密。有一种提高
RSA速度的建议是使公钥 e取较小的值，这样会使加密变得易于
实现，速度有所提高。但这样作是不安全的，公钥 e和私钥 d还是
都取较大的值为好。但是,RSA算法是第一个能同时用于加密和
数字签名的算法，也易于理解和操作。经历了各种攻击的考验和
最广泛的研究，从提出到现在已近二十年，逐渐为人们认为是目
前最适用的公钥算法之一。
2.3.2 Diffie-Hellman算法
Diffie和 Hellman在 1976年公开发表的第一
个公钥密码算法定义了公钥密码学。论文中提
出一个密钥交换系统，让网络互不相见的两个
通信体，可以共享一把钥匙，用以证明公开密
钥的概念的可行性。这个算法本身基于计算对
数难度，其目的是实现两个用户之间安全地交
换密钥以便于后续的数据加密。 Diffie-Hellman
密钥交换算法在现在的许多商用产品中使用。
Diffie-Hellman算法描述
算法描述 如下：
给定公开素数 q和 q的本原根 r。即 r∈ {1,2,3,4,…( q-1)},且
{1,2,3,4,…( q-1)}＝ { mod q,mod q,mod q,… mod q}则对
b∈ {1,2,3,4,…( q-1)},可以唯一的指数 i，使得 b= mod q。
用户 A,B交换密钥的方法 如下：
（ 1）用户 A选择一个随机数,计算,A将 秘
密保存而将 公开。
（ 2）用户 B选择一个随机数,计算,B将 秘
密保存而将 公开。
（ 3） A将 送给 B,B将 送给 A,（ A并不知道,B并不知道 ）
（ 4）用户 A计算密钥,；
（ 5）用户 B计算密钥,；
2rr 3r 1qr ?
ir
aAXq? qrY
aXA m o d? aX
AY
bAXq? qrY
bXB m o d? bX
BY
AY BY xb xa
qYK aXB m o d)(1 ?
qYK bXA m o d)(2 ?
2.3.3 ElGamal加密算法
EIGamal体制是 T.EIGamal在 1985年发表的,A
public-key cryptosystem and a signatures scheme based
on discrete logarithms”(一个基于离散对数的共钥密码体
制和数学签名方案 )论文中提出的公开密匙密码体制。
下面给出的 EIGamal体制在论文中用于数据加密的算法。
采用 EIGamal公开密匙密码体制的密码系统中，所有的
用户都共享一个素数 P 以及一个 Z的生成元 g,明文空间
P=Z,密文空间,选定 0<a<p,计算
秘密密钥,a 公开密钥,b
*PZ Z Z?? pgb a m o d?
ElGamal加密解密算法
加密算法,设明文为 m,0≤m<p,随机的选取正整数
k,0≤k<p,gcd(k,p-1)=1,计算密文对 y1,y2：
密文 。
解密算法,
可见,EIGamal体制的密文不是唯一的，这是一种非确
定性加密方式。显然增加了系统的安全性，但是，代价
是密文膨胀了两倍。
)m o d(1 pgy k? )m o d(2 pmby k?
pmgmggmbyym akakakkk m o d/// 12 ????
)2,1( yyc ?
2.3.4 椭圆曲线加密算法定义
定义, 椭圆曲线指的是由韦尔斯特拉斯方程所确
定的平面曲线 。
其中，系数（ i =1,2,…, 6）定义在基域 K上
（ K可以是有理数域、实数域、复数域，还可以是
有限域，椭圆曲线密码体制中用到的椭圆曲线都
定义在有限域上）
2 3 21 3 2 4 6y a x y a y x a x a x a? ? ? ? ? ?
椭圆曲线加密算法相关知识
1985年,Koblitz和 Miller相互独立地开发提出了在密
码学中应用椭圆曲线（ Eliptical Curve）构造公开密钥密
码体制的思想。这一算法一出现便受到关注，由于基于
椭圆曲线的公开密钥密码体制开销小（所需的计算量
小）、安全性高等优点，随着椭圆曲线的公开密钥密码
体制极大的发展，它将替代 RSA成为通用的公钥密码算
法。实践表明，在 32位的 PC机上和 16位微处理器上运行
椭圆曲线密码算法，其中 16位微处理器上的数字签名不
足 500ms。因此，应用椭圆曲线的数字签名可以很容易地
在小的有限资源的设备中使用。
1,有限域上的椭圆曲线算法的提出
设 K表示一个有限域,E是域 K上的椭圆曲线，则 E是一个点的集合：
E/K = { ( x,y ) | y2+ a1xy + a3y = x3 + a2x2 + a4x + a6,a1,a3,a2,a4,a6 x,y
K } { O } 其中 O表示无穷远点。在 E上定义‘ +’运算,P + Q = R,R是过 P、
Q的直线与曲线的另一交点关于 x轴的对称点,当 P = Q时 R是 P点的切线与
曲线的另一交点关于 x轴的对称点。这样,( E,+ )构成可换群 ( Abel群 )，
O是加法单位元 (零元 )。椭圆曲线离散对数问题定义如下：给定定义在 K上
的椭圆曲线 E，一个 n阶的点 PE/K，和点 QE/ K，如果存在 l，确定整数 l,0,
l,n - 1,Q = lP。
我们知道,RSA是基于因子分解，其算法的核心就是如何寻找大数的
因子分解，但大数的因子分解是比因子分解难得多的问题。椭圆曲线上的
加法, P + Q = R 是椭圆曲线上一点的 2倍, P + P = R,基于该难题,1985年
N.Koblitz和 Miller提出将椭圆曲线用于密码算法，分别利用有限域上椭圆
曲线的点构成的群实现了离散对数密码算法。
2,椭圆曲线上的密码算法
椭圆曲线加密系统由很多依赖于椭圆曲线离散对数
算法问题的加密系统组成,
（ 1）知 E(Fn)对点的,?”运算形成一个 Abel群，设
p∈ E(Fn)，若 p的周期很大，即使 p? p ?…… ? p= θ
(共有 t个 p相加 )成立的最小正整数 t，希望 t很大 (t = p的
周期，表示为 ∏(p)=t)，并且对 Q∈ E(Fq)，定有某个正整
数 m使 Q=m?p=p ? …… ? p(共有 m个 p相加 )定义 m=㏒ n
Q (m为以 n为底 Q的对数 )椭圆曲线上的点形成的群 E(Fn)，
相关它的离散对数问题是难处理的。
建立椭圆曲线密码体制
选取基域 Fn,Fn的椭圆曲线具体给定为确定
的形式。 在 E(Fn)中选一个周期很大的点，如选了
一个点 P=(xn,yn)，它的周期为一个大的素数 n，
记 ∏ (P)=n(素数 )。注意：在这个密码体制中，具
体的曲线及点 P和它的 n都 是公开信息。密码体制
的形式采用 EIGamal体制，是完全类比过来。
建立椭圆曲线密码的方法
使用者执行了下列计算：
a) 在区间 [1,n-1]中随机选取一个整数 d；
b) 计算点 Q:=dP (d个 P相 ? ) ；
c) 使用者公开自己的公开密钥 ——(E(Fn),p,n,Q)；
d) 使用者的私钥为整数 d；
发送者要发送消息 m给使用者，执行：
a) 查找使用者的公钥 (E(Fn),p,n,Q),
b) 将 m表示成一个域元素 m∈ Fn，
c) 在区间 [1,n-1]内选取一个随机数 k,
d) 依据使用者的公钥计算点 (x1,y1):=kP (k个 P相 ? )，
e) 计算点 (x2,y2):=kQ,如果 x2 =0,则回到第 c步计算 C:=m?x2；
f) 传送加密数据 (x1,y1,C)给使用者；
使用者收到发送者的密文 (x,y,C)后，执行解密过程：
a)使用私钥 d，计算点 (x2,y2):=d(x1,y1)，再计算 Fn中,
b)通过计算 m:=C?,恢复出明文数据 m。
12x?
12x?
2.4 信息加密产品简介
信息加密产品随着加密技术的应用和
发展出现了良好的商业化趋势，比较常用
的信息加密软件有 PGP和 CryptoAPI，作为
开放的软件工具，它们的使用为深入开展
信息加密技术的研究提供了帮助。下面分
别介绍 PGP和 CryptoAPI。
2.4.1 PGP加密软件简介
PGP(pretty good privacy)是一个对邮件和传
输的文挡进行加密的软件，可以用来对邮件和文
挡保密以防止非授权者阅读，让你可以安全地和
你从未见过的人们通信。 PGP软件综合了目前健
壮的加密方法和加密系统认证性方面的新手段，
功能强大有很快的速度，是一种比较实用和安全
的加密工具。 PGP软件创始人是美国的
Phil Zimmermann，由于许多版本不受密码出口
管制，源代码也是免费的，获取比较方便。
1,PGP采用的加密标准
PGP 用的是公匙加密和传统加密的杂合算法，这种算法创造
性在于他把公匙加密体系的方便和传统加密体系的高速度结合起来，
充分利用多个算法各自的优点应用于明文加密和密匙认证管理机制
中，形成了整个加密系统巧妙的设计。 PGP实际上用来对明文加密
采用了 IDEA的传统加密算法。 IDEA的加（解）密速度比公匙加密
算法如 RSA快得多，但主要缺点就是密匙的传递渠道解决不了安全
性问题，不适合网络环境加密需要。因此,PGP每次加密都可以随
机生成密匙用 IDEA算法对明文加密，然后在用密匙的传递中用公
匙加密算法，一般是使用不适合加密大量数据的 RSA或 Diffie-
Hellman算法对该密匙加密来保证传递渠道的安全性，这样收件人
同样是用 RSA或 Diffie-Hellman解密出这个随机密匙，再用 IDEA解
密出明文。
PGP加密方法示意图
解密
密钥 K2
明文
密钥 K
加密
密钥 K2
明文
加密
密钥 K2
发送者 接收者
IDEA加密密文
接收者的公钥 K1
公钥加密密文
解密
密钥 K2
接收者的私钥 K2
密钥 K
图 4.1PGP加密方法示
意图
2,PGP的密匙管理 （ 1）
在 PGP中如果 IDEA密匙是通过网络传送而不
加密，网络黑客们就会“监听”而获取密匙，整
个传输肯定危险，因此，必须通过必要可靠的密
匙管理来保证信息发送和接收的安全性。一个成
熟的加密系统必然要有一个成熟的密匙管理机制
配套，公匙加密体系可以解决传统加密体系的密
匙分配难保密的缺点,PGP中应用 RSA或 Diffie-
Hellman算法实施密匙分配。
2,PGP的密匙管理 （ 2）
但是，分配过程中首先要获取对方公匙，如果公
匙被篡改，所获得的公匙成了伪造的，密匙分配就会
传递给篡改者，篡改者可以用自己的私匙解密获得密
匙。这可能是公匙密码体系中最大的漏洞和安全性问
题，你必须确信你拿到的公匙属于它看上去属于的那
个人。防止这种情况出现的最好办法是避免让任何其
他人有机会篡改公匙，比如直接从要接收信息的人手
中得到公匙，然而当在千里之外或无法见到时，这是
很困难的。
2,PGP的密匙管理 （ 3）
解决这个问题一般方法是数字签名，直接认证你的信息接收者
的公匙，防止篡改公匙；而 PGP则在此基础上发展了一种公匙介绍
机制来解决这个问题，举例来说：如果你和接收信息的人有一个共
同的朋友，而朋友知道他手中的你的接收信息的人的公匙是正确的，
这样朋友可以用他自己的私匙在你的接收信息的人的公匙上加密，
表示他担保这个公匙属于你的信息接收者，然后你需要用朋友的公
匙解密获取信息接收者给你的公匙，同样朋友也可以向你的信息接
收者认证你的公匙。这样朋友,介绍人”。这样你就可以放心地到
BBS上取朋友签过字的公匙，由于经过朋友认证，没人可能获得朋
友的私匙去伪造和篡改信息接收者给你的公匙，但前提是朋友认证
过你的信息接收者的公匙，这样是从信任的公共渠道传递公匙的安
全手段。
PGP的安全性管理特点
（ 1）审慎的密匙管理
（ 2）灵活选择加密密匙对的位数
（ 3）专门用来签名而不加密，用于声明人用自己的私匙签名
证实自己的身份
（ 4）加密的实际密匙随机数难以分析，如,PGP程序对随机
数的产生是很审慎的，关键的随机数像 RSA密匙的产生
是从用户瞧键盘的时间间隔上取得随机数种子的，这有
效地防止了他人从你的随机数文件中分析出你的加密实
际密匙的规律来
（ 5） PGP内核使用 PKZIP算法来压缩加密前的明文，压缩后
加密再经过 7bits编码使密文比明文更短，节省了网络传
输的时间；另一方面，明文经过压缩，信息更加杂乱无
章，增强了对明文攻击的抵御能力。
2.4.2 CryptoAPI加密软件简介
Microsoft CryptoAPI（ Cryptography API，
加密 API）是微软开发的一系列 API标准加密接口
功能函数，主要提供在 Win32环境下加解密、数字
签名验证等安全服务应用，供给应用程序使用这
些 API 函数生成和交换密钥、加密和解密数据、
实现密钥管理和认证、验证数字签名及散列计算
等操作，增强应用程序的安全性和可控性。
1,CryptoAPI的加密系统结构
Microsoft提供 CryptoAPI接口和 CSP
（ cryptographic service provider）,CSP是真
正实行实现所有加密操作的独立模块，由两部
分组成：一个 DLL（ dynamic linkable library，
动态链接库）文件和一个签名文件。 Microsoft
安装会将该 CSP的各个的文件安放到相应的目
录下，并在注册表中为其注册。
CSP密钥库示意图
签名密钥对
交换密钥对
签名密钥对
交换密钥对
User#1
密钥容器
User#2
密钥容器
密钥库
图 2.4 CSP密钥库
CSP类型和算法
CSP类型 交换算法 签名算法 对称加密算法 Hash算法
PROV_RSA_FULL RSA RSA RC2/RC4 MD5/SHA
PROV_RSA_SIG none RSA none MD5/SHA
PROV_RSA_SCH
ANNEL RSA RSA
RC4/DES/Triple
DES
MD5/SHA
PROV_DSS DSS none DSS MD5/SHA
PROV_DSS_DH DH DSS CYLINK_MEK MD5/SHA
PROV_DH_SCHA
NNEL DH DSS DES/Triple DES
MD5/SHA
PROV_FORTEZZA KEA DSS Skipjack SHA
PROV_MS_EXCH
ANGE RSA RSA CAST MD5
PROV_SSL RSA RSA Varies Varies
2,CryptoAPI函数分类 （ 1）
（ 1） base cryptography functions 基本的加密服务函数
这类函数是用 CSP提供的函数直接编制的 API函数，它主要
完成数据加 /解密、计算 Hash、产生密钥等操作，具体包括
下面函数组：
service provider functions基本的服务提供函数；
key generation and exchange functions密钥生成与交
换函数 cryptencode object/cryptdecode object
functions 对象加 /解密函数；
data encryption/decryption functions 数据加 /解密函数；
hash and digital signature functions Hash算法与数据签
名函数 ；
2,CryptoAPI函数分类 （ 2）
（ 2） certificate and certificate store functions
签名证书存储函数
通常情况下，时间长了计算机上的签名证书数量
会增加，用户有必要管理证书。 certificate store
functions让用户存储、检索、删除、列出和验证
证书，但并不生成证书（生成证书是 CA的任务）
和证书请求。 Certificate Store Functions提供将证
书和要发送的信息附加的功能。
2,CryptoAPI函数分类 （ 3）
（ 3） certificate verification functions 证书验证函数用
来验证证书的有效性。具体包括下面函数组：
functions using CTLs
使用 CTLs(certificate revocation lists，证书恢复列表 )
函数；
certificate chain verification functions证书列表验证
函数；
2,CryptoAPI函数分类 （ 4）
（ 4） message functions 消息传递函数
具体包括两组功能函数：
low-level message functions
低级消息传递函数；
simplified message functions
简化的消息传递函数；
2,CryptoAPI函数分类 （ 5）
（ 5） auxiliary functions 辅助函数
具体包括下面函数组：
data management functions 数据管理函数；
data conversion functions 数据转换函数；
enhaned key usage functions 密钥使用函数；
key identifier functions 密钥标识函数；
certificate store provider callback functions 证书存储提供模块
的回调函数；
OID support functions：微软的对象标识技术的支持函数，提
供对 SDCOM（ security DCOM+）的支持
remote object retrieval functions 远程对象恢复函数；
小 结
本章我们介绍了信息加密的相关基础
知识，主要内容有信息编码基础知识、数
论基础知识、信息加密方式与标准,RSA
加密算法,Diffie-Hellman算法,ElGamal
加密算法，椭圆曲线加密算法以及主流加
密软件的介绍，如果大家对此有兴趣的话
可以自己查阅相关资料，谢谢！
信息加密技术基础
引 言
信息加密是网络安全体系中重要机制之
一。信息加密的目的是为了保持信息的机密
性，使用恰当的加密标准将在计算机环境中
增加安全性。信息加密通过使用一种编码而
使存储或传输的信息变为不可读的信息，解
密是一个相反的过程。这些编码就是将明文
变成密文的加密算法或数学方法。
引 言 (续 )
加密编码在 Shannon的信息论中有针对性的阐述，
数论及基础代数是加密算法的理论基础。要将一段
信息加密或解密，你会要用到密钥，它是一个很大
的值。一般来说，密钥越大，加密就越健壮。一般
来说加密体制分为对称密钥加密和公用密钥加密，
对称密钥加密在密钥方面有一定的缺陷，但执行效
率高；公用密钥加密加密执行效率底，但保密性强，
在报文和网络方面对小量信息加密非常有效,
2.1 信息加密理论基础
信息安全的核心技术之一是加密技术，
它涉及信息论、基础数论和算法复杂性等
多方面基础知识。随着计算机网络不断渗
透到各个领域，加密技术的应用也随之扩
大，应用加密基础理论知识，深入探索可
靠可行的加密方法，应用于数字签名、身
份鉴别等新技术中成为网络安全研究重要
的一个方面。
加密的理论依据
密码学问题就是随机性的利用问题,
差不多每台使用加密技术的计算机安全系
统都需要随机数，供密钥、协议中的基础
参量等使用或者用做辅助信息或者初始化
向量。这些系统的安全也经常依赖于这些
随机数的随机性及被保护程度 。
简单的加密举例
中秋日月 编码 密钥 密文编码 诗
月明明日 010101 10 111111
明日月明 101010 000000？
明日明日 101101 000111
日明月明 110010 011000
通过这个例子我们看到一个简单的加密过程，原来的诗
通过与密钥的模二运算实现了加密。
2.1.1 信息编码基础知识
第二次世界大战期间，美国为了提高
信息储存和传递的效率，发明了多种新的
编码方法，奠定了现代信息科学技术的基
础。 Shannon还于 1949年发表了“保密系统
的通信理论”一文，奠定了现代密码学基
础从而对加密过程中信息编码有了明确的
分析。在该文中他从信息论观点，对信息
系统的保密性问题作了全面而深刻的阐述。
1,信 息 熵 基 本 知 识
信息论中最重要的内容，是如何认识和使用
信息熵来表现信息。 这里用 Shannon最喜欢用的
猜谜方法来说明信息熵的基本概念。假如有：
“我们大 __都喜 __使 __计 __机来管 __数 __。”
不用很多努力，就可以猜出完整的句子,“我们大
家都喜欢使用计算机来管理数据。” Shannon在
信息论中指出，能猜出来的字符不运载信息，而
不能猜出来的字符运载信息。
1,信 息 熵 基 本 知 识 (续 )
空格所隐藏的字符属于多余度字符，不
用那些字符也能运载该句子的全部信息，
比如：“我 __大 ________使 ______机来
____数 __。”就很难猜出完整的句子，在
信息传递的时候，也很难做检错和抗错。
因此，保留一定的多余度 (或冗余度 )是非常
重要的。
2,信息量和信息熵基本定义 (1)
信息熵（ information entropy）是对
信息状态“无序”与“不确定”的度量
（从本质上讲，熵不是对信息的度量，但
信息的增加而使产生的熵减小，熵可以用
来度量信息的增益）。
2,信息量和信息熵基本定义 (2)
定义：给定一离散集合 X={xi; i=1,2,…,n}，
令 xi出现的概率是 且 。事件 xi
包含的信息量
通常 =2，此时相应的信息量单位是 bit。
Shannon定义信息的数学期望为信息熵，即
信源的平均信息量。
( ) 0ipx ?
1
( ) 1n i
i
px
?
??
)(l o g)( iai xPxI ?? (2.1)
2,信息量和信息熵基本定义 (3)
定义：将集合 X中事件所包含的信息量统计
平均，则平均值定义为集合 X的熵,信息熵表
征了信源整体的统计特征，集合 X的熵 H（ x）
表示 X中事件所包含的平均信息量，或总体
的平均不确定性的量度。
0)(lo g)()](lo g[)( 2
1
2 ???? ?
?
i
n
i
ii xpxpxPExH
(2.2)
2,信息量和信息熵基本定义 (4)
对某一特定的信源，
其信息熵只有一个，
因统计特性不同，其
熵也不同。例如，两
个信源，其概率空间
分别为：
12[,( ) ]
0, 9 9 0, 0 1i
xx
X P x
??
? ??
??
12[,( ) ]
0, 5 0, 5i
yy
Y P y
??
? ??
??
2,信息量和信息熵基本定义 (5)
则信息熵为：
可见，,说明信源 比信源 的平均不确定
性要大，即在事件发生之前，分析信源,由于事
件 是等概率的，难以猜测哪一个事件会发生,
( ) 0, 9 9 l o g 0, 9 9 0, 0 1 l o g 0, 0 1 0, 0 8 [ ]H X b i t? ? ? ?
( ) 0, 5 l o g 0, 5 0, 5 l o g 0, 5 1 [ ]H Y b i t? ? ? ?
( ) ( )H Y H X? Y X
Y
21,yy
2,信息量和信息熵基本定义 (6)
而信源,虽然也存在不确定性，但大致可以
知道,出现的可能性要大。正如两场比赛，其中
一场，双方势均力敌；而另一场双方实力悬殊很
大。当然,人们希望看第一场，因为胜负难卜，一
旦赛完，人们获得信息量大。也可以这样理解，
信息熵 表征了变量 的随机性。因此，熵反映了变
量的随机性，也是表征随机变量统计特性的一个
特征参数。
X
1x
3,信息熵的基本性质 (1)
I,对称性
当概率空间中 序任意互换时，
熵函数的值不变，例如下面两个信源空
间,
?)(),( 21 xPxP
?
?
?
?
?
?
?
?
?
2
1
6
1
3
1)](,[
321 xxx
xPX
?
?
?
?
?
?
?
?
?
3
1
2
1
6
1)](,[
321 yyy
yPX
3,信息熵的基本性质 (2)
其信息熵,该性质说明，熵
只与随机变量的总体结构有关，与信源总
体的统计特性有关，同时也说明所定义的
熵有其局限性，它不能描述事件本身的主
观意义。
)()( YHXH ?
3,信息熵的基本性质 (3)
II,确定性
如果信源的输出只有一个状态是必然的,
即 则信源的熵,
此性质表明，信源的输出虽有不同形态，但其中
一种是必然的，意味着其他状态不可能出现。
那么，这个信源是一个确知信源，其熵为零。
,0)()(,1)( 321 ???? ?xPxPxP
2
( ) [ 1 l o g 1 0 l o g 0 ] 0
n
i
HX
?
? ? ? ? ? ??
(2.3)
3,信息熵的基本性质 (4)
III,非负性
即 。 因为随机变量 的所有取值的
概率分布为,当取对数的底大
于１时，,而,则得到
的熵是正值，只有当随机变量是一确知
量时，熵才等于零。这种非负性对于离
散信源的熵来说，这一性质并不存在。
0)( ?XH
1)(0 ?? ixP
0)(lo g ?ixP 0)(lo g)( ?? ii xPxP
3,信息熵的基本性质 (5)
IV,可加性
独立信源 和 的联合信源的熵等于它们各自的
熵之和。 如果有两个随机变量 和, 它们彼此是
统计独立的，即 的概率分布为,
而 的分布概率为,则联合信源
的熵,
可加性是熵函数的一个重要特性，正因为有可加性，
所以可以证明熵函数的形式是唯一的。
X Y
X Y
X )](,),(),([ 21 sxPxPxP ?
Y )](,),(),([ 21 zyPyPyP ?
)()()( YHXHXYH ??
1)(
1
??
?
N
i
ixP 1)(1 ???
M
j
iyP
3,信息熵的基本性质 (6)
V,极值性
信源各个状态为零概率分布时，熵值最
大，并且等于信源输出状态数，因为
当 时，
(2.5)
NxPxPxP s /1)()()( 21 ???? ?
N
NN
XH
N
i
l o g1l o g1)(
1
??? ?
?
例 题
例，信源有两种状态时，概率空间
其 与 关系如图所示,，当 =1/2时熵有最大值；
当信源输出是确定的，即,则,此时表
明该信源不提供任何信息；反之，当信源输出为等概
率发生时，即 时信源的熵达到最大值，等于
1bit信息量。
?????? ?? )(1)P ( x)](,[
11
21
xP
xxxPX
i
)(XH )(xP )(xP
1)( 1 ?xP 0)( ?XH
2/1)( 1 ?xP
信息熵函数曲线
P(x)
0 0.5 1
明
文
H(x)
4,信息熵在信息加密编码中的作用 (1)
通过熵和信息量的概念，可计算加密系统中各
部分的熵。令明文熵为,密钥
熵,密文熵 。这里 M、
K和 C分别是明文、密钥和密文空间,m,k、
c分别是它们的字母集,l,r和 v分别是明文、密
钥、和密文的长度。则明文和密文之间的互信
息以及密钥与密文之间的互信息分别是：
)()( lmHMH ?
)()( rkHKH ? )()( vcHCH ?
)()();( vllvl cmHmHcmI ??
)()();( vrrvr ckHkHckI ??
(2.6)
(2.7)
4,信息熵在信息加密编码中的作用 (2)
因为只要密文、密钥确定后，明文也就得到了，所以
,故
定理：对任意加密系统
从该理论我们可以看出，密钥熵越大，密文中所包含的
明文信息量就越小。一个加密系统中，若其密文与明
文之间的互信息,则密码分析者无论截
获多大的密文，均不能得到有关明文的任何信息。这
种加密系统称为完善加密系统，或无条件加密系统。
0)),()( ?rvl kcmH )()),(;( lrvl mHkcmI ?
)()();( KHmHcmI lvl ??
(2.8)
0);( ?vl cmI
4,信息熵在信息加密编码中的作用 (3)
在对密文攻击下，完善加密系统是安全的，但它不能
保证在已知明文或选择性明文攻击下也是安全的。因
此，完善保密系统存在的必要条件是
证明：若,则由前一个定理可
得，,所以 的必要条件是
)()( lmHKH ?
(2.9)
)()( lmHKH ?
0);( ?vl cmI 0);( ?vl cmI
)()( lmHKH ?
2.1.2 数论基本术语
? 数论是研究整数性质的一个数学分支，
同时也是加密技术的基础学科之一。首
先介绍一些数论的基本知识,
1,整 数
定义：设 。如果存在 使得,那么就说 b可
以被 a 整除，记为,且称 b是 a的倍数,a 是 b的因数 (或称约
数、除数、因子 ) 。 b不能被 a整除可以记作 dFa。由定义及乘
法运算的性质，可推出整除关系具有以下性质（注：符号
本身包含了条件 ）：
（ 1） ；
（ 2）如果 且,则 ；
（ 3）设,那么 与 等价 ;
（ 4）如果 且,则对所有的,有 ;
（ 5）设,如果,那么 ;
0,,?? aZba Zq? aqb?
ba
ba
0?a
aa
ba cb ca
0?m ba bmam
ba ca Zyx ?,cybxa ?
0?b ba ba ?
2,素 数
定义,设整数 。如果它除了显然因数 外没有其他的
因数，则 p就称为是素数，也叫不可约数。若, 且 a不
是素数，则 a称为合数。
关于素数，有以下性质：
（ 1）如果 p是素数，且,则 或,即 p至少整除 a与 b中
的一个。
（ 2）任何一个整数,均可以分解成素数幂之积：
（ 3）若不计因数的顺序，这个分解式是唯一的。其中,
是两两互不相同的素数,是正整数。
（ 4）素数有无穷多个。
（ 5）设 表示不大于 的素数的数目，则 。
0?p p??,1
0?a 1?
abp ap bp
2?n kekee pppn ?21 21?
1?k ip )1( ki??
)1( kiei ??
)(x? 1/ln)(lim ?xxx?
3,同 余
设,如果,则称 a和 b模 n同
余，记为,整数 n称为模数。由
于 等价于,所以 与
等价。因此，一般我们总假定 。如
果,我们称 b是 a对模 n的最小非负剩
余，有时也称 b为 a对模 n的余数。
0,,?? nZba )( ban ?
)( m o dnba ?
ban ? ban ?? )(m o dnba ? ))( m o d ( nba ??
1?n
nb ??0
同余式的一些基本性质
（ 1）反身性, ；
（ 2）对称性,如果,那么 ；
（ 3）传递性,如果,,那么 ；
（ 4）如果, 那么； 。
（ 5）如果,, gcd, (两个
不同时为 0的整数 a与 b的最大公约数表示成 gcd(a,b))那
么,存在,当且仅当 gcd 。
)(m o dnaa ?
)(m o dnba ? )(m o dnab ?
)(m o dnba ? )(m o dncb ? )(m o dnca ?
)(m o d1 naa ? )(m o d1 nbb ? )( m o d11 nbaba ???
)( m o d11 nbaba ??? )( m o d11 nbaab ?
)(m o dnbdac ? )(m o dnba ? 1),( ?na
)(m o dndc ? )(m o d1 nac ? 1),( ?na
一些关于同余的基本概念 (1)
同余类 可用其中任一元素
a(经常取 )代替，记作 。于是
从 中分别取一个数作为代表构成
一个集合，称为模 n的一个完全剩余系，
记为,称为模 n的非负最小完
全剩余系。
}0,{ qrZqqnr ????
ra? ][a
]1[]1[]0[ ?? nz ???? )10(][][ ????? njiji ??
(2.11)
]1[,],1[],0[ ?n?
}1,,1,0{ ?n? nZ
一些关于同余的基本概念 (2)
在模 n的完全剩余系中，去掉那些与 n不互素的数，
剩下的部分称为模 n的简化剩余系； 的简化剩余
系记为,读为模 n的非负最小简化剩余系。显
然,中的元便是不超过 n并与 n互素的那些数，
它们的个数等于欧拉函数 的值。 （欧拉函数
的定义为, 小于自然数 N并与 N互质 (除 1以外无其
它公因子 )的自然数的个数用函数 表示,称为欧
拉函数。欧拉函数的具体性质会在后面第 6小节进
行阐述）
nZ
*nZ
*nZ
)(n?
)(n?
4,模 运 算
给定正整数 n，对任意 a，若存在 q，使得
则称 r是 a关于模 n的余数，
记为 。
若 则称整数 a,b同余，记
为
整数集中所有与数 a同余的整数集合称为 a
的同余类，记为 。
)0( nrrqna ????
nar mod?
)m o d()m o d( nbna ?
(m o d )a b n?
??na
模 运 算 的 性 质
（ 1） 当且仅当 。
（ 2） 当且仅当 。
（ 3）如果,,则 。
a模 n的运算给出了 a对模 n的余数。注意：模运算的结果
是从 0到 的一个整数。模运算就像普通的运算一样，
它是可交换，可结合，可分配的。而且，对每一个中间
结果进行模 m运算，其作用与先进行全部运算，然后再
进行模 m运算所得到结果是一样的。
)( m o dnba ? )( ban ?
)(m o dnba ? )(m o dnab ?
)(m o dnba ? )(m o dncb ? )(m o dnca ?
1?n
5,最大公约数与最小公倍数
设, 是两个整数，如果 且,那么就称 b是 和 的公
约数,一般的，设,是 K个整数，如果
那么就称 b是 的公约数。因为对于任意一个不等于零
的整数，它的因数是有限的。所以，任意一对整数,其中一
个不为零时，它们的公约数的个数也必定是有限的；同理，当
中有一个不为零时，它们的公约数是有限的,这样,我们引入最大公
约数的概念。
定义, 设, 是两个整数，我们把 和 的公约数中最大的数
称为 和 的最大公约数，记为 (,)或
当 时，我们称 和 是互素的。 显然
1a 2a 1ab 2ab 1a 2a
kaaa,,,21 ? kababab,,,21 ?
kaaa,,,21 ?
21,aa
kaaa,,,21 ?
1a 2a 1a 2a
1a 2a ),gcd( 21 aa
1),( 21 ?aa 1a 2a 0),( 21 ?aa
1a 2a
最 大 公 约 数 的 性 质
（ 1）
（ 2）若 |,j=2,…,k,则
（ 3）任意的整数 x,有
（ 4）对任意的整数 x,有
（ 5）设,是不都为零的整数，则一定存
在一对整数,，使得：
),(),(),( 211221 aaaaaa ???
1a ja 12121 ),,,(),( aaaaaa k ?? ?
),,(),( 12121 xaaaaa ?
),(),( 12121 xaaaaa ??
1a 2a
1x 2x 221121
),( xaxaaa ??
最 小 公 倍 数 的 概 念
设, 是两个均不等于零的整数，如果
且,那么 1 就称为是 和 的公倍数，
一般地，设 是 k个均不等于零的整数。
如果,则称 l是 的公倍数。
公倍数的集合是无穷集合，但根据自然数的理
论，存在最小的正的公倍数。我们把 和
的正的公倍数中最小的数称为 和 的最小
公倍数，记为 或
1a 2a 11a
12a 1a 2a
kaaa,,,21 ?
1,,1,1 21 kaaa ? kaaa,,,21 ?
1a 2a
1a 2a
],[ 21 aa ),( balcm
6,欧拉 （ Euler） 函数
欧拉（ Euler）函数
设 n≥1,欧拉函数 表示在区间 中与 n互素的
整数的个数。
欧拉函数 具有以下性质：
(1)如果 p是素数，则 ；
(2)如果 p是素数,。那么 ；
(3)对于整数,根据算术基本定理,n可以分解成惟一的形
如 的分解式，则
(4)若 和 互素，则 。
)(n?
?? Zzn,)(? ],1[ n
)(n?
1)( ?? pp?
1?k )1()( 1 ?? ? ppp kk?
2?n
kekee pppn ?21 21? )/11()/11)(/11()( 21 kpppnn ???? ??
1m 2m )()()( 21 mmm ??? ?
2.1.3 算法复杂性基础知识
所谓问题，是指一个要求给出解释的一
般性提问，通常含有若干个未定参数或自由
变量。它由两个要素组成,第一个要素是描
述所有的参数，也就是对所有未定参数的一
般性描述 ;第二个要素是解答必须满足的性质。
一个问题 可以看成是由无穷多个问题实例组
成的一个类。
1,算 法 的 定 义
所谓 算法 是由明确指出操作的规则所组成的
若干语句的集合，只要按照规则一步一步执行一
定数目的语句，便可求出问题的答案。通常的计
算机程序都可以看作是算法的表达形式，在问题
的两要素中，对算法而言，第一个要素就是“输
入”，第二个要素就是“输出”。如果把问题 P的
任意一个实例作为算法 A的输入,A在有限步骤之
内总能输出关于此实例的正确答案，我们就说算
法 A可解问题 P。对于一个问题 P，如果存在一个
算法 A可解问题 P，我们称问题 P是 算法可解 的。
2,算 法 复 杂 性
算法的复杂性表征了算法在实际执行时所需计
算能力方面的信息, 通常它由该算法所要求的最
大时间与存取空间来确定。 由于算法所需的时间
和空间往往取决于问题实例的规模 n (n表示了该
实例的输入数据长度 )，同时，算法在用于相同规
模 n的不同实例时。其时间和空间需求也可能会有
很大差异，因此，实际中我们常常研究的是算法
关于输入规模 的所有实例的时间与空间需求的平
均值。
算 法 复 杂 性 的 构 成
通常情况下，一个算法的计算复杂性由两个变
量度量：时间复杂性 和空间复杂性 。它们
定义如下：
（ 1） 时间复杂性,以某特定的基本步骤为单元，
完成计算过程所需的总单元数称为算法的时间复杂
性，或时间复杂度。 n为输入的规模或尺寸。
（ 2） 空间复杂性,以某特定的基本存储空间为单
元，完成计算过程所用的存储单元数，称为算法的
空间复杂性或空间复杂度。 n是输入的规模或尺寸。
)(nT )(nS
)(nT
)(nS
算法复杂性的基本符号 （ 1）
一个算法的计算复杂性用,O”符号表示其
数量级。,O”的意思是：对于两个任意的
实值函数 f和 g，若记号,则
存在有一个值 a，对充分大的 n，
有 。计算复杂性的数量级就是这
种类型的函数，即当 n变大时增长得最快的
函数，所有常数和较低阶形式的函数可以
忽略不计。
??? nngOnf ) ),(()(
)()( nganf ?
算法复杂性的基本符号 （ 2）
另一个符号是,o”。它的定义是：
当且仅当,这意味着在 时，
比 可以忽略不计。 时间复杂度 有时
也用工作因子 W表示，这时 。如果一个算
法的复杂性不依赖于 n，那么它是常数级的用 表
示之，而 表示复杂性随 n线性增长，因而是线
性型算法。复杂性随 n线性增长的其他一些算法也
称为二次方或三次方等，所有这些算法都是多项
式的，它们的时间复杂性是 。有多项式
时间复杂性的算法称为多项式时间算法或有效算
法。
??? nngonf ) ),(()(
lim ( ) / ( ) 0n f n g n?? ? ??n
)(nf )(ng ))(( ngo
)(ngW ?
)1(o
)(no
)()( lnonT ?
3,问 题 的 复 杂 性
问题的复杂性是问题固有的性质。问题
的复杂性理论利用算法复杂性作为工具，
将大量典型的问题按照求解的代价进行分
类。问题的复杂性由在图灵机上解其最难
实例所需的最小时间与空间决定，还可以
理解为由解该问题的最有效的算法所需的
时间与空间来度量。
N P 问 题
在确定型图灵机上可用多项式时间求解的问
题，称为易处理的问题。易处理的问题的全体称
为确定性多项式时间可解类，记为 P类。在非确定
性图灵机上可用多项式时间求解的问题，称为非
确定性多项式时间可解问题，记为 NP问题 。 NP问
题的全体称为非确定性多项式时间可解类，记为
NP类。显然，,因为在确定型图灵机上多项
式时间可解的任何问题在非确定型图灵机上也是
多项式时间可解的。
NPP ?
N P C 问 题
NP类中还有一类问题称为 NP完全类，记为 NPC。所
有的 NP问题都可以通过多项式时间转换为 NPC中的
问题。 NPC是 NP类中困难程度最大的一类问题,但
NPC中的问题困难程度相当，都可以多项式时间转化
为称为可满足性问题的 NPC问题，此类 NPC具有如下
性质，若其中的任何一个问题属于 P，则所有的 NP问
题都属于 P，且 。现在的密码算法的安全性都
是基于 NPC问题的，破译一个密码相当于求解一个
NPC问题,如果,则破译密码就是一件很容易
的事情,
NPP ?
NPP ?
2.2 信息加密方式与标准
经典的信息加密理论主要用于通信保密，而
现代信息加密技术的应用已深入到信息安全的各
个环节和对象，信息的加密方式和标准也有了深
入广泛的发展，特别是现代加密和信息隐藏技术
的结合，实现信息隐蔽传输使人类对信息的加密
技术有了新的认识和要求，下面介绍信息加密技
术的基本概念、方式和标准。
2.2.1 信息加密基本概念 （ 1）
研究安全信息的加密技术和研究破解安全信息密码的密
码分析技术的学科称为 密码学 。信息加密是通过使用一种编
码而使某些可读的信息 (明文 )变为不可读的信息 (密文 )。这
些编码就是将明文变成密文的加密算法 (也称为密码 )或数学
方法。密码使用隐蔽语言、文字、图象的特种符号，目标是
接收数据作为输入，产生密文作为输出，以便数据的原始意
义得以隐藏。在计算机通讯中，采用密码（密钥为参数）将
信息隐蔽起来，再将隐蔽后的信息传输出去，使信息在传输
过程中即使被窃取或载获，也不能了解信息的内容，从而保
证信息传输的安全。
2.2.1 信息加密基本概念 （ 2）
通信两端将信息编码时，发送端使用简单
的信息加密；接收端收到传来的信息后通过解
密看到编码前的信息，整个过程中加密或解密
是由密钥控制实现的。 密钥 是用户按照一种密
码体制随机选取，它通常是一随机字符串，是
控制明文变换（加密）和密文变换（解密）的
唯一参数。密钥全体称为密钥空间。一般来说，
密钥越大，加密就越健壮。
加密系统的组成部分
如上所述，一个加密系统实际上是某种加密算法在
密钥控制下实现的从明文到密文的映射，它至少包括下
面四个组成部分：
（ 1）加密的报文，也称明文；
（ 2）加密后的报文，也称密文；
（ 3）加密解密设备或算法；
（ 4）加密解密的密钥；
一般情况下，密钥由 K表示，明文由 m表示，加密算法
由 ( ) 表示，解密算法由 ( ) 表示，；
则,( ( m )) =m
1EK
2DK
2DK
1EK
加密系统示意图
一个完整的加密系统如下图所示,
信源 加密 解密 信宿
密文明文
窃听 干扰
明文
密钥 K1 密钥 K2
图 2.2 加密系统示意图
加密系统的安全规则 （ 1）
任何一个加密系统必须基本具备四个安
全规则：
（ 1）机密性 (confidentiality)：加密系统在信
息的传送中提供一个或一系列密钥来把信
息通过密码运算译成密文，使信息不会被
非预期的人员所读取，只有发送者和接收
者应该知晓此信息的内容。
加密系统的安全规则 （ 2）
（ 2）完整性 (integrity)：数据在传送过程中不应被
破坏，收到的信宿数据与信源数据是一致的。应
该选取健壮的密码和加密密钥，以确保入侵者无
法攻破密钥或找出一个相同的加密算法，阻止入
侵者会改变数据后对其重新加密。有时，数据完
整性可以通过适当的方法在信息还未被完全修改
时检测到，如：密码散列函数是单向密码，它为
明文产生惟一的“指纹”，当明文被拦截和读取，
要修改它将改变散列，致使有意向的接收者很容
易看出散列之间的差异。
加密系统的安全规则 （ 3）
（ 3）认证性 (authentication),加密系统应该提供数字签名技术来
使接收信息用户验证是谁发送的信息，确定信息是否被第三者篡
改。只要密钥还未泄露或与别人共享，发送者就不能否认他发送
的数据。实际应用中，假如发送者和接收者都使用一个对称密钥，
对于整体信息加密或计算机网络上的链路级加密，在两个路由器
之间建立一个加密会话，以通过因特网发送加密信息。连接到网
络的计算机发送明文给路由器，明文被转换为密文，然后通过因
特网发送到另一端的路由器。在整个加密数据形成和传递过程中，
加密方网络内部和非加密方的任一节点都能插入信息，并在这一
层次分析，但对于接收者这一节点来说你只能判定信息是否来自
某个特定的网络，而要确认信息的发送节点，这将使验证机制变
得很复杂。
加密系统的安全规则 （ 4）
（ 4）非否定 (non-repudiation)：加密系统除了应该验
证是谁发送的信息外，还要进一步验证收到的信息是
否来自可信的源端，实际上是通过必要的认证确认信
息发送者是否可信。现代健壮的验证方法用加密算法
来比较一些已知的信息段，如 PIN(个人识别号 )判断
源端是否可信。
非否定规则应属于认证性规则中的一部分。一般来说，
前三个规则一起被称为 CIA 。从技术的角度来看，所
有的加密都提供了私有性和完整性，其余的均由此衍
生，这包括非否定和认证性规则。
2.2.2 信息加密方式
1,信息加密方式分类
对存储的文件和网络中传输的数据包实施信息加密，其加
密方式可以根据加密系统不同的特征划分,
（ 1） 按密钥方式划分
对称式加密, 收发双方使用相同密钥。加密和解密使用同一密
钥。加密算法和解密算法在对称式加密中是相同的，加密和解
密使用同一密钥 K表示。
非对称式加密, 也称公用密钥加密，加密和解密使用不同密钥。
它通常有两个密钥，称为“公钥”和“私钥”。它们两个必需
配对使用，否则不能打开加密文件。这里的“公钥”是指可以
对外公布的，“私钥”则不对外公布，只有持有人知道。加密
算法和解密算法在非对称式加密中是不相同的； K1是加密密钥,
是公开的，称为公钥,K2是解密密钥，称为私钥，则须保密。
2种不同方式的加密示意图
明文解密
密钥 K2
明文 加密
密钥 K2
K K
密文传输
图 2.2 对称式 加密示意图
明文 解密
密钥 K2
K1 K2
加密
密钥 K2
明文
图 2.3 非对称式 加密示意图
1,信息加密方式分类
（ 2）按保密程度划分
理论上保密的加密：无论获取多少密文和有多大的计算能力，
对于明文始终不能得到唯一解的加密方法。如：采用客观随机一
次出来的密码就属于这种加密方式。
实际上保密的加密：从理论的角度是可以破解的，但在现有客
观条件下，无法通过计算来确定唯一解。
（ 3）按明文形态划分
模拟信息加密：用来加密模拟信息。如：动态范围之内，连续
变化的语音信号的加密。
数字信息加密：用来加密数字信息。如：两个离散电平构成 0、
1二进制关系的电报信息的加密。
2,数 字 签 名
数字签名是对原信息附上加密信息的过程，是一种身份认
证技术，支持加密系统认证性和非否定；签名者对发布的原信
息的内容负责，不可否认。数字签名采用非对称式加密（也称
公钥加密标准）对信息 m使用私钥 K2加密，运算如下：
S=DK2(m) 其中 S为签名,D为解密算法；接收者收到发送者发
来的 S和 m信息，同时从公开媒体找到了发送者的公钥 K1,发送
者用 K2对 S进行如下运算,E K1 (S)= E K1 (DK2(m))= m,E为加
密算法；收到的 m对应计算出来的 m，结果说明信息确实来源于
发送者，第三方不可能知道私钥 K2，无法篡改 S，发送者无法
否认发送 m信息。在实际工作中，由于解密计算缓慢，为了提
高签名速度,m信息往往要经过压缩或散列处理或尽量取简短
信息，如公钥数据等。
数字签名工作流程图
信息 m
密钥 K2
私钥 K 2
公钥 K1
信息 m
密钥 K2
解密算法
密钥 K2
签名 S
密钥 K2
签名 S
密钥 K2
加密算法
密钥 K2
图 2.4 数字签名工作流程图
3,网 络 信 息 加 密
网络信息加密的目的是保护网内的数据、文件、口令和控制
信息，保护网上传输的数据。网络加密常用的方式有链路加密和
端点加密。
（ 1）链路加密
链路加密对链路层数据单元进行加密保护，其目的是保护网络节
点之间的链路信息安全。这种加密不但对节点之间之间传输的数
据报文加密，还要把路由信息、校验和控制信息包括数据链路层
的帧头、位填充和控制序列等都进行加密；当密文传输到某一节
点时，全部解密获得链信息和明文，然后全部加密后发送往下一
个节点；对于这种加密，加密设备的设计相对复杂，必须理解链
路层协议和必要的协议转换。
链路加密的优缺点
链路加密非常有效，是因为几乎任何有用消息都被加密保护。加密范
围包括用户数据、路由信息和协议信息等。因此，攻击者将不知道通信的
发送和接受者的身份、不知道信息的内容、甚至不知道信息的长度以及通
信持续的时间。而且，系统的安全性将不依赖任何传输管理技术。密钥管
理也相对简单，仅仅是线路的两端需要共同的密钥。线路两端可以独立于
网络的其他部分更换密钥。
链路加密的缺点是：整个连接中的每段连接都需要加密保护。对于包含不
同体系机构子网络的较大型网络，加密设备、策略管理、密钥量等方面的
开销都是巨大的。另外，在每个加密节点，都存在加密的空白段：明文信
息，这是及其危险的，特别是对于跨越不同安全域的网络。后来，为解决
节点中数据是明文的缺点，在节点内增加了加解装置，避免了节点明文，
这种加密方式称为节点加密；但和链－链加密一样，同样依靠公共网络节
点资源的配合，开销依然很大。
端 点 加 密
端点加密的是对源端用户到目的端用户的数据提供加密
保护。既将加密模块置于网络以上的加密方式。端点加密中，
数据从加密的端节点，一直到对应的解密节点，数据在整个
传输过程中都保持密文形式，从而克服了链路加密出现加密
空白段（中间节点明文信息）的问题。由于加密和解密只发
生在两个端节点，因此对中间节点是透明的。这样大大减少
了安装设备的开销（特别是中间节点设备开销），以及复杂
的策略管理和密钥管理所引起的麻烦。由于加密范围往往集
中在高层协议数据，还极易为不同流量提供 QoS服务，实现
按特定流量进行加密和不同强度的加密。从而有利于提高系
统的效能，优化系统的性能。
端点加密的缺点
端点加密的缺点是：由于通信环境往往比较复杂，要
在跨越网络的两个端用户之间成功地完成密钥的建立是需
要付出性能代价的。其次，端点加密不能保护数据传输过
程中的某些信息，如路由信息、协议信息等，一个训练有
素的攻击者可以借助这些信息发动某些流量分析攻击。另
外，端点加密设备（模块）的实现十分复杂，要求设备必
须理解服务的提供层的协议，并且成功调用这些服务，然
后在设备中对对应的数据进行密码处理，并且将处理后的
数据传送给上层协议。如果加密设备不能为上层协议提供
良好的服务接口，则将对通信的性能产生较大的影响。
2.2.3 数据加密标准
1,对称密钥加密 DES
DES(data encryption standard)是 1976年由美国国
家标准局颁布的一种加密算法，属于对称密钥加密算
法体制，早期被公认为较好的加密算法，经过长期严
验证后，被国际标准化组织接受作为国际标准。 DES
自它应用 20多年来，不断经受了许多科学家破译，同
时也成为密码界研究的重点。 DES对称密钥加密算法
广泛的应用在民用密码领域，为全球贸易、金融等非
官方部门提供了可靠的通信安全保障。
DES的相关知识
DES主要采用替换和移位的加密方法用 56位密钥对 64位二进制
数据块进行加密，加密每次可对 64位的输入数据进行 16轮编码，经
过一系列替换和移位后，原始的 64位输入数据转换成了完全不同的
64位输出数据。 DES算法运算速度快，生成密钥容易，适合于在当
前大多数计算机上用软件方法和专用芯片上实现。但 DES密钥太短
（ 56位），密钥健壮性不够好，降低保密强度；同时,DES安全性
完全依赖于对密钥的保护，在网络环境下使用，分发密钥的信道必
须具备有力的可靠性才能保证机密性和完整性。
DES算法还有一些变形，如：三重 DES和广义 DES等。目前，
DES应用领域主要包括：计算机网络通信中的数据保护（只限于民
用敏感信息）；电子资金加密传送；保护用户存储文件，防止了未
授权用户窃密；计算机用户识别等。
2,Clipper加密芯片标准
这种数据加密标准对用户只提供加密芯片（ Clipper）和硬件
设备，它的密码算法不公开，密钥量比 DES多 1000多万倍，是美国
国家保密局（ NSA）在 1993年正式使用的新的商用数据加密标准，
目的是取代 DES，提高密码算法的安全性，主要用于通信交换系统
中电话、传真和计算机通信信息的安全保护。为确保更可靠的安全
性，加密设备的制作方法按照 Clipper芯片由一个公司制造裸片，再
由另一公司编程严格规定来实施。
Clipper芯片主要特点是充分利用高的运算能力的设备资源加大密钥
量，从而用于计算机通信网上的信息加密，如：政府和军事通信网
中数据加密芯片的研究不断换代使它还实现了数字签名标准和保密
的哈希函数标准以及用纯噪声源产生随机数据的算法等。
3,国际数据加密标准
这种算法是在 DES算法的基础上发展的。与
DES相同，国际数据加密算法 IDEA
（ international data encryption algorithm）也是
针对数据块加密；它采用 128位密钥，设计了一系
列加密轮次，每轮加密都使用从完整的加密密钥
中生成的一个子密钥，基于这种算法，采用软件
实现和采用硬件实现同样快速，非常适合于对大
量的明文信息的快速加密。它在 1990年正式公布
并在以后得到了增强。
传统加密方法的缺点
在网络通信中，传统的对称加密方法是发送者加密、接收
者解密使用同样的密钥，这种方法虽然有运算快的特点，随着
用户的增加，大量密钥的分配是一个难以解决的问题。例如，
若系统中有 n个用户，其中每两个用户之间需要建立密码通信，
则系统中每个用户须掌握 (n-1)/2个密钥，而系统中所需的密钥
总数为 n*(n-1)/2 个。对 10个用户，每个用户必须有 9个密钥，
系统中密钥的总数为 45个。对 100个用户，每个用户必须有 99个
密钥，系统中密钥的总数为 4950个。这还仅考虑用户之间的通
信只使用一种会话密钥的情况。如此庞大数量的密钥生成、管
理、分发确实是一个难处理的问题。因此，对称加密方法所带
来的密钥的弱的健壮性和密钥管理的复杂性局限了它的发展。
4,公开密钥加密标准
早在 20世纪 70年代，美国斯坦福大学的两名学者
迪菲和赫尔曼提出了一种加密方法 ―― 公开密钥加密
方法，解决了传统加密体系的密匙分配复杂的缺点。
公开密钥加密方法是非对称加密方式，该技术采用不
同的加密密钥和解密密钥对信息加密和解密，每个用
户有一个对外公开的加密算法 E和对外保密的解密算
法 D，它们须满足条件：
（ 1） D是 E的逆，即 D[E（ X） ]=X。
（ 2） E和 D容易计算。
（ 3）如果由 E出发求解 D十分困难。
公钥及私钥的概念
若加密密钥可对外公开，称为 公钥 ；一个用户向
另一用户传送信息，首先通过开放途径 (如 BBS)的获
得另一用户的公开密钥，对明文加密后发送，而另
一用户唯一保存的解密密钥是保密的，称为 私钥,
另一用户通过安全的方法验证信源可靠后，私钥将
密文复原、解密。理论上解密密钥可由加密密钥推
算出来，但这种算法设计在实际上是不可能的，或
者虽然能够推算出，但要花费很长的时间和代价，
所以，将加密密钥公开不会危害密钥的安全。
RSA 算 法
著名的 RSA正是基于这种理论，算法以发明者的名字命名：
Ron Rivest,Adi Shamir 和 Leonard Adleman.这种算法为公用网络
上信息的加密和鉴别提供了一种基本的方法。为提高保密强度，
RSA密钥至少为 500位长，一般推荐使用 1024位，这就使加密的计
算量很大。同时，为减少计算量，在传送信息时，常采用传统对
称加密方法与 RSA公开密钥加密方法相结合的方式，信息明文加
密采用改进的 DES或 IDEA加密方法，使用 RSA用于加密密钥和信
息摘要。对方收到信息后，用各自相关的密钥解密并可核对信息。
但是 RSA并不能替代 DES等对称算法,RSA的密钥长，加密速度
慢，而采用 DES等对称算法加密速度快，适合加密较长的报文，
弥补了 RSA的缺点。美国的保密增强邮件系统 （ PEM） 就是采用
了 RSA 和 DES结合的方法，目前已成为 E-MAIL保密通信标准。
5,量子加密方法
量子加密与公钥加密标准同期出现，适用于网络上加
密普通宽带数据信道所传送的信息，工作原理是两端用户各自
产生一个私有的随机数字符串，两个用户向对方的接受装置发
送代表数字字符串的单个量子序列（光脉冲），接受装置从两
个字符串中取出相匹配的比特值组成了密钥。实现了会话或交
换密钥的传递。由于这种方法依赖的是量子力学定律，传输的
光量子是无法被窃听的；如果有人进行窃听，就会对通信系统
造成干扰，对通信系统的量子状态造成不可挽回的变化，通信
双方就会得知有人进行窃听，从而结束通信，重新生成密钥。
这种加密技术不久的将来应该有应用和发展，但是如何实现数
字签名有待于研究。
2.3 公钥信息加密算法
随着密码技术的发展,Diffie和 Hellman在
IEEE提出提出了公钥密码系统，即加密密钥和
解密密钥不是同一把密钥。现在公钥密码系统被
广泛的应用，其中 RSA加密算法,Diffie-Hellman
算法,ElGamal加密算法，椭圆曲线加密算法被广
泛研究和应用。
2.3.1 RSA加密算法
RSA的安全性依赖于大数分解。公钥及私钥都是两个大素数（大
于 100个十进制位）的函数，从一个密钥和密文推断出明文的难度等
同于分解两个大素数的积。算法如下：
１,生成密钥
（ 1）秘密的选取两个大数 p,q
（ 2）计算,,这 指的是 Euler函数
（ 3）选取整数 e，满足 且 。
（ 4）计算 d,满足 。即 d是 e关于模 乘的逆元，
（ 乘法逆元, 设,如果存在, 满足,则称 x
是 a的模 n乘法逆元，记为 (mod n) ）由 e的定义,d唯一。
（ 5）输出公钥,私钥 。
qpn ?? )1)(1()( ??? qpn? )(n?
)(1 ne ??? 1)),(gc d( ?en?
))(( m o d1* ned ?? )(n?
naZ? nxZ?
1(m od )ax n?
1a?
},{ ne },{ nd
具体加密解密操作
加密操作
选定,把明文分成长度为 k的组块。对每个
明文分组 M,M在 0到 (n-1)之间。加密操作为：
解密操作
得到密文分组 C，解密操作为：
][lo g )1(2 ?? nk
nMC e m o d?
(2.14)
nCM d m o d?
(2.15)
RSA算法的局限性 （ 1）
（ 1）有限的安全性
RSA是一种分组密码算法，它的安全是基于数论中大的整数 n
分解为两个素数之积的难解性。目前,RSA的一些变种算法已被
证明等价于大数分解。同样，分解 n也是最显然的攻击方法。现在，
人们已能分解 140多个十进制位的大素数。因此，适用具体情况而
定，模数 n必须选尽可能大。同时要注意，如果系统中共享一个模
数，不同的人拥有不同的公钥 e1和 e2，这些公钥共模而且互质，假
如普遍的情况是同一信息用不同的公钥加密，那么该信息无需私
钥就可得到恢复。即设 P为信息明文,C1和 C2为密文，公共模数
是 n，则,C1 = P^e1 mod n ； C2 = P^e2 mod n 密码分析者知道 n、
e1,e2,C1和 C2，就能得到 P。解决办法只有一个，那就是不要共
享模数 n。
RSA算法的局限性 （ 2）
（ 2）运算速度慢
RSA算法进行的都是大数计算，使得其最快的情况也比 DES
慢上 100倍，无论是软件实现还是硬件实现。速度一直是 RSA算
法的缺陷。一般来说 RSA算法只用于少量数据加密。有一种提高
RSA速度的建议是使公钥 e取较小的值，这样会使加密变得易于
实现，速度有所提高。但这样作是不安全的，公钥 e和私钥 d还是
都取较大的值为好。但是,RSA算法是第一个能同时用于加密和
数字签名的算法，也易于理解和操作。经历了各种攻击的考验和
最广泛的研究，从提出到现在已近二十年，逐渐为人们认为是目
前最适用的公钥算法之一。
2.3.2 Diffie-Hellman算法
Diffie和 Hellman在 1976年公开发表的第一
个公钥密码算法定义了公钥密码学。论文中提
出一个密钥交换系统，让网络互不相见的两个
通信体，可以共享一把钥匙，用以证明公开密
钥的概念的可行性。这个算法本身基于计算对
数难度，其目的是实现两个用户之间安全地交
换密钥以便于后续的数据加密。 Diffie-Hellman
密钥交换算法在现在的许多商用产品中使用。
Diffie-Hellman算法描述
算法描述 如下：
给定公开素数 q和 q的本原根 r。即 r∈ {1,2,3,4,…( q-1)},且
{1,2,3,4,…( q-1)}＝ { mod q,mod q,mod q,… mod q}则对
b∈ {1,2,3,4,…( q-1)},可以唯一的指数 i，使得 b= mod q。
用户 A,B交换密钥的方法 如下：
（ 1）用户 A选择一个随机数,计算,A将 秘
密保存而将 公开。
（ 2）用户 B选择一个随机数,计算,B将 秘
密保存而将 公开。
（ 3） A将 送给 B,B将 送给 A,（ A并不知道,B并不知道 ）
（ 4）用户 A计算密钥,；
（ 5）用户 B计算密钥,；
2rr 3r 1qr ?
ir
aAXq? qrY
aXA m o d? aX
AY
bAXq? qrY
bXB m o d? bX
BY
AY BY xb xa
qYK aXB m o d)(1 ?
qYK bXA m o d)(2 ?
2.3.3 ElGamal加密算法
EIGamal体制是 T.EIGamal在 1985年发表的,A
public-key cryptosystem and a signatures scheme based
on discrete logarithms”(一个基于离散对数的共钥密码体
制和数学签名方案 )论文中提出的公开密匙密码体制。
下面给出的 EIGamal体制在论文中用于数据加密的算法。
采用 EIGamal公开密匙密码体制的密码系统中，所有的
用户都共享一个素数 P 以及一个 Z的生成元 g,明文空间
P=Z,密文空间,选定 0<a<p,计算
秘密密钥,a 公开密钥,b
*PZ Z Z?? pgb a m o d?
ElGamal加密解密算法
加密算法,设明文为 m,0≤m<p,随机的选取正整数
k,0≤k<p,gcd(k,p-1)=1,计算密文对 y1,y2：
密文 。
解密算法,
可见,EIGamal体制的密文不是唯一的，这是一种非确
定性加密方式。显然增加了系统的安全性，但是，代价
是密文膨胀了两倍。
)m o d(1 pgy k? )m o d(2 pmby k?
pmgmggmbyym akakakkk m o d/// 12 ????
)2,1( yyc ?
2.3.4 椭圆曲线加密算法定义
定义, 椭圆曲线指的是由韦尔斯特拉斯方程所确
定的平面曲线 。
其中，系数（ i =1,2,…, 6）定义在基域 K上
（ K可以是有理数域、实数域、复数域，还可以是
有限域，椭圆曲线密码体制中用到的椭圆曲线都
定义在有限域上）
2 3 21 3 2 4 6y a x y a y x a x a x a? ? ? ? ? ?
椭圆曲线加密算法相关知识
1985年,Koblitz和 Miller相互独立地开发提出了在密
码学中应用椭圆曲线（ Eliptical Curve）构造公开密钥密
码体制的思想。这一算法一出现便受到关注，由于基于
椭圆曲线的公开密钥密码体制开销小（所需的计算量
小）、安全性高等优点，随着椭圆曲线的公开密钥密码
体制极大的发展，它将替代 RSA成为通用的公钥密码算
法。实践表明，在 32位的 PC机上和 16位微处理器上运行
椭圆曲线密码算法，其中 16位微处理器上的数字签名不
足 500ms。因此，应用椭圆曲线的数字签名可以很容易地
在小的有限资源的设备中使用。
1,有限域上的椭圆曲线算法的提出
设 K表示一个有限域,E是域 K上的椭圆曲线，则 E是一个点的集合：
E/K = { ( x,y ) | y2+ a1xy + a3y = x3 + a2x2 + a4x + a6,a1,a3,a2,a4,a6 x,y
K } { O } 其中 O表示无穷远点。在 E上定义‘ +’运算,P + Q = R,R是过 P、
Q的直线与曲线的另一交点关于 x轴的对称点,当 P = Q时 R是 P点的切线与
曲线的另一交点关于 x轴的对称点。这样,( E,+ )构成可换群 ( Abel群 )，
O是加法单位元 (零元 )。椭圆曲线离散对数问题定义如下：给定定义在 K上
的椭圆曲线 E，一个 n阶的点 PE/K，和点 QE/ K，如果存在 l，确定整数 l,0,
l,n - 1,Q = lP。
我们知道,RSA是基于因子分解，其算法的核心就是如何寻找大数的
因子分解，但大数的因子分解是比因子分解难得多的问题。椭圆曲线上的
加法, P + Q = R 是椭圆曲线上一点的 2倍, P + P = R,基于该难题,1985年
N.Koblitz和 Miller提出将椭圆曲线用于密码算法，分别利用有限域上椭圆
曲线的点构成的群实现了离散对数密码算法。
2,椭圆曲线上的密码算法
椭圆曲线加密系统由很多依赖于椭圆曲线离散对数
算法问题的加密系统组成,
（ 1）知 E(Fn)对点的,?”运算形成一个 Abel群，设
p∈ E(Fn)，若 p的周期很大，即使 p? p ?…… ? p= θ
(共有 t个 p相加 )成立的最小正整数 t，希望 t很大 (t = p的
周期，表示为 ∏(p)=t)，并且对 Q∈ E(Fq)，定有某个正整
数 m使 Q=m?p=p ? …… ? p(共有 m个 p相加 )定义 m=㏒ n
Q (m为以 n为底 Q的对数 )椭圆曲线上的点形成的群 E(Fn)，
相关它的离散对数问题是难处理的。
建立椭圆曲线密码体制
选取基域 Fn,Fn的椭圆曲线具体给定为确定
的形式。 在 E(Fn)中选一个周期很大的点，如选了
一个点 P=(xn,yn)，它的周期为一个大的素数 n，
记 ∏ (P)=n(素数 )。注意：在这个密码体制中，具
体的曲线及点 P和它的 n都 是公开信息。密码体制
的形式采用 EIGamal体制，是完全类比过来。
建立椭圆曲线密码的方法
使用者执行了下列计算：
a) 在区间 [1,n-1]中随机选取一个整数 d；
b) 计算点 Q:=dP (d个 P相 ? ) ；
c) 使用者公开自己的公开密钥 ——(E(Fn),p,n,Q)；
d) 使用者的私钥为整数 d；
发送者要发送消息 m给使用者，执行：
a) 查找使用者的公钥 (E(Fn),p,n,Q),
b) 将 m表示成一个域元素 m∈ Fn，
c) 在区间 [1,n-1]内选取一个随机数 k,
d) 依据使用者的公钥计算点 (x1,y1):=kP (k个 P相 ? )，
e) 计算点 (x2,y2):=kQ,如果 x2 =0,则回到第 c步计算 C:=m?x2；
f) 传送加密数据 (x1,y1,C)给使用者；
使用者收到发送者的密文 (x,y,C)后，执行解密过程：
a)使用私钥 d，计算点 (x2,y2):=d(x1,y1)，再计算 Fn中,
b)通过计算 m:=C?,恢复出明文数据 m。
12x?
12x?
2.4 信息加密产品简介
信息加密产品随着加密技术的应用和
发展出现了良好的商业化趋势，比较常用
的信息加密软件有 PGP和 CryptoAPI，作为
开放的软件工具，它们的使用为深入开展
信息加密技术的研究提供了帮助。下面分
别介绍 PGP和 CryptoAPI。
2.4.1 PGP加密软件简介
PGP(pretty good privacy)是一个对邮件和传
输的文挡进行加密的软件，可以用来对邮件和文
挡保密以防止非授权者阅读，让你可以安全地和
你从未见过的人们通信。 PGP软件综合了目前健
壮的加密方法和加密系统认证性方面的新手段，
功能强大有很快的速度，是一种比较实用和安全
的加密工具。 PGP软件创始人是美国的
Phil Zimmermann，由于许多版本不受密码出口
管制，源代码也是免费的，获取比较方便。
1,PGP采用的加密标准
PGP 用的是公匙加密和传统加密的杂合算法，这种算法创造
性在于他把公匙加密体系的方便和传统加密体系的高速度结合起来，
充分利用多个算法各自的优点应用于明文加密和密匙认证管理机制
中，形成了整个加密系统巧妙的设计。 PGP实际上用来对明文加密
采用了 IDEA的传统加密算法。 IDEA的加（解）密速度比公匙加密
算法如 RSA快得多，但主要缺点就是密匙的传递渠道解决不了安全
性问题，不适合网络环境加密需要。因此,PGP每次加密都可以随
机生成密匙用 IDEA算法对明文加密，然后在用密匙的传递中用公
匙加密算法，一般是使用不适合加密大量数据的 RSA或 Diffie-
Hellman算法对该密匙加密来保证传递渠道的安全性，这样收件人
同样是用 RSA或 Diffie-Hellman解密出这个随机密匙，再用 IDEA解
密出明文。
PGP加密方法示意图
解密
密钥 K2
明文
密钥 K
加密
密钥 K2
明文
加密
密钥 K2
发送者 接收者
IDEA加密密文
接收者的公钥 K1
公钥加密密文
解密
密钥 K2
接收者的私钥 K2
密钥 K
图 4.1PGP加密方法示
意图
2,PGP的密匙管理 （ 1）
在 PGP中如果 IDEA密匙是通过网络传送而不
加密，网络黑客们就会“监听”而获取密匙，整
个传输肯定危险，因此，必须通过必要可靠的密
匙管理来保证信息发送和接收的安全性。一个成
熟的加密系统必然要有一个成熟的密匙管理机制
配套，公匙加密体系可以解决传统加密体系的密
匙分配难保密的缺点,PGP中应用 RSA或 Diffie-
Hellman算法实施密匙分配。
2,PGP的密匙管理 （ 2）
但是，分配过程中首先要获取对方公匙，如果公
匙被篡改，所获得的公匙成了伪造的，密匙分配就会
传递给篡改者，篡改者可以用自己的私匙解密获得密
匙。这可能是公匙密码体系中最大的漏洞和安全性问
题，你必须确信你拿到的公匙属于它看上去属于的那
个人。防止这种情况出现的最好办法是避免让任何其
他人有机会篡改公匙，比如直接从要接收信息的人手
中得到公匙，然而当在千里之外或无法见到时，这是
很困难的。
2,PGP的密匙管理 （ 3）
解决这个问题一般方法是数字签名，直接认证你的信息接收者
的公匙，防止篡改公匙；而 PGP则在此基础上发展了一种公匙介绍
机制来解决这个问题，举例来说：如果你和接收信息的人有一个共
同的朋友，而朋友知道他手中的你的接收信息的人的公匙是正确的，
这样朋友可以用他自己的私匙在你的接收信息的人的公匙上加密，
表示他担保这个公匙属于你的信息接收者，然后你需要用朋友的公
匙解密获取信息接收者给你的公匙，同样朋友也可以向你的信息接
收者认证你的公匙。这样朋友,介绍人”。这样你就可以放心地到
BBS上取朋友签过字的公匙，由于经过朋友认证，没人可能获得朋
友的私匙去伪造和篡改信息接收者给你的公匙，但前提是朋友认证
过你的信息接收者的公匙，这样是从信任的公共渠道传递公匙的安
全手段。
PGP的安全性管理特点
（ 1）审慎的密匙管理
（ 2）灵活选择加密密匙对的位数
（ 3）专门用来签名而不加密，用于声明人用自己的私匙签名
证实自己的身份
（ 4）加密的实际密匙随机数难以分析，如,PGP程序对随机
数的产生是很审慎的，关键的随机数像 RSA密匙的产生
是从用户瞧键盘的时间间隔上取得随机数种子的，这有
效地防止了他人从你的随机数文件中分析出你的加密实
际密匙的规律来
（ 5） PGP内核使用 PKZIP算法来压缩加密前的明文，压缩后
加密再经过 7bits编码使密文比明文更短，节省了网络传
输的时间；另一方面，明文经过压缩，信息更加杂乱无
章，增强了对明文攻击的抵御能力。
2.4.2 CryptoAPI加密软件简介
Microsoft CryptoAPI（ Cryptography API，
加密 API）是微软开发的一系列 API标准加密接口
功能函数，主要提供在 Win32环境下加解密、数字
签名验证等安全服务应用，供给应用程序使用这
些 API 函数生成和交换密钥、加密和解密数据、
实现密钥管理和认证、验证数字签名及散列计算
等操作，增强应用程序的安全性和可控性。
1,CryptoAPI的加密系统结构
Microsoft提供 CryptoAPI接口和 CSP
（ cryptographic service provider）,CSP是真
正实行实现所有加密操作的独立模块，由两部
分组成：一个 DLL（ dynamic linkable library，
动态链接库）文件和一个签名文件。 Microsoft
安装会将该 CSP的各个的文件安放到相应的目
录下，并在注册表中为其注册。
CSP密钥库示意图
签名密钥对
交换密钥对
签名密钥对
交换密钥对
User#1
密钥容器
User#2
密钥容器
密钥库
图 2.4 CSP密钥库
CSP类型和算法
CSP类型 交换算法 签名算法 对称加密算法 Hash算法
PROV_RSA_FULL RSA RSA RC2/RC4 MD5/SHA
PROV_RSA_SIG none RSA none MD5/SHA
PROV_RSA_SCH
ANNEL RSA RSA
RC4/DES/Triple
DES
MD5/SHA
PROV_DSS DSS none DSS MD5/SHA
PROV_DSS_DH DH DSS CYLINK_MEK MD5/SHA
PROV_DH_SCHA
NNEL DH DSS DES/Triple DES
MD5/SHA
PROV_FORTEZZA KEA DSS Skipjack SHA
PROV_MS_EXCH
ANGE RSA RSA CAST MD5
PROV_SSL RSA RSA Varies Varies
2,CryptoAPI函数分类 （ 1）
（ 1） base cryptography functions 基本的加密服务函数
这类函数是用 CSP提供的函数直接编制的 API函数，它主要
完成数据加 /解密、计算 Hash、产生密钥等操作，具体包括
下面函数组：
service provider functions基本的服务提供函数；
key generation and exchange functions密钥生成与交
换函数 cryptencode object/cryptdecode object
functions 对象加 /解密函数；
data encryption/decryption functions 数据加 /解密函数；
hash and digital signature functions Hash算法与数据签
名函数 ；
2,CryptoAPI函数分类 （ 2）
（ 2） certificate and certificate store functions
签名证书存储函数
通常情况下，时间长了计算机上的签名证书数量
会增加，用户有必要管理证书。 certificate store
functions让用户存储、检索、删除、列出和验证
证书，但并不生成证书（生成证书是 CA的任务）
和证书请求。 Certificate Store Functions提供将证
书和要发送的信息附加的功能。
2,CryptoAPI函数分类 （ 3）
（ 3） certificate verification functions 证书验证函数用
来验证证书的有效性。具体包括下面函数组：
functions using CTLs
使用 CTLs(certificate revocation lists，证书恢复列表 )
函数；
certificate chain verification functions证书列表验证
函数；
2,CryptoAPI函数分类 （ 4）
（ 4） message functions 消息传递函数
具体包括两组功能函数：
low-level message functions
低级消息传递函数；
simplified message functions
简化的消息传递函数；
2,CryptoAPI函数分类 （ 5）
（ 5） auxiliary functions 辅助函数
具体包括下面函数组：
data management functions 数据管理函数；
data conversion functions 数据转换函数；
enhaned key usage functions 密钥使用函数；
key identifier functions 密钥标识函数；
certificate store provider callback functions 证书存储提供模块
的回调函数；
OID support functions：微软的对象标识技术的支持函数，提
供对 SDCOM（ security DCOM+）的支持
remote object retrieval functions 远程对象恢复函数；
小 结
本章我们介绍了信息加密的相关基础
知识，主要内容有信息编码基础知识、数
论基础知识、信息加密方式与标准,RSA
加密算法,Diffie-Hellman算法,ElGamal
加密算法，椭圆曲线加密算法以及主流加
密软件的介绍，如果大家对此有兴趣的话
可以自己查阅相关资料，谢谢！
