1、第二章第二章信息加密技术基础信息加密技术基础 引引 言言 信息加密是网络安全体系中重要机制之信息加密是网络安全体系中重要机制之一。信息加密的目的是为了保持信息的机密一。信息加密的目的是为了保持信息的机密性，使用恰当的加密标准将在计算机环境中性，使用恰当的加密标准将在计算机环境中增加安全性。信息加密通过使用一种编码而增加安全性。信息加密通过使用一种编码而使存储或传输的信息变为不可读的信息，解使存储或传输的信息变为不可读的信息，解密是一个相反的过程。这些编码就是将明文密是一个相反的过程。这些编码就是将明文变成密文的加密算法或数学方法。变成密文的加密算法或数学方法。引引 言言 (续续)加密编码在加密
2、编码在Shannon的信息论中有针对性的阐述，的信息论中有针对性的阐述，数论及基础代数是加密算法的理论基础。要将一段数论及基础代数是加密算法的理论基础。要将一段信息加密或解密，你会要用到密钥，它是一个很大信息加密或解密，你会要用到密钥，它是一个很大的值。一般来说，密钥越大，加密就越健壮。一般的值。一般来说，密钥越大，加密就越健壮。一般来说加密体制分为对称密钥加密和公用密钥加密，来说加密体制分为对称密钥加密和公用密钥加密，对称密钥加密在密钥方面有一定的缺陷，但执行效对称密钥加密在密钥方面有一定的缺陷，但执行效率高；公用密钥加密加密执行效率底，但保密性强，率高；公用密钥加密加密执行效率底，但保密性
3、强，在报文和网络方面对小量信息加密非常有效在报文和网络方面对小量信息加密非常有效.2.1 信息加密理论基础信息加密理论基础 信息安全的核心技术之一是加密技术，信息安全的核心技术之一是加密技术，它涉及信息论、基础数论和算法复杂性等它涉及信息论、基础数论和算法复杂性等多方面基础知识。随着计算机网络不断渗多方面基础知识。随着计算机网络不断渗透到各个领域，加密技术的应用也随之扩透到各个领域，加密技术的应用也随之扩大，应用加密基础理论知识，深入探索可大，应用加密基础理论知识，深入探索可靠可行的加密方法，应用于数字签名、身靠可行的加密方法，应用于数字签名、身份鉴别等新技术中成为网络安全研究重要份鉴别等新技
4、术中成为网络安全研究重要的一个方面。的一个方面。加密的理论依据加密的理论依据 密码学问题就是随机性的利用问题密码学问题就是随机性的利用问题.差不多每台使用加密技术的计算机安全系差不多每台使用加密技术的计算机安全系统都需要随机数，供密钥、协议中的基础统都需要随机数，供密钥、协议中的基础参量等使用或者用做辅助信息或者初始化参量等使用或者用做辅助信息或者初始化向量。这些系统的安全也经常依赖于这些向量。这些系统的安全也经常依赖于这些随机数的随机性及被保护程度随机数的随机性及被保护程度。简单的加密举例简单的加密举例 中秋日月中秋日月 编码编码 密钥密钥 密文编码密文编码 诗诗 月明明日月明明日 0101
5、01 10 111111010101 10 111111 明日月明明日月明 101010 000000 101010 000000？明日明日明日明日 101101 000111101101 000111 日明月明日明月明 110010 011000110010 011000 通过这个例子我们看到一个简单的加密过程，原来的诗通过这个例子我们看到一个简单的加密过程，原来的诗通过与密钥的模二运算实现了加密。通过与密钥的模二运算实现了加密。2.1.1 信息编码基础知识信息编码基础知识 第二次世界大战期间，美国为了提高第二次世界大战期间，美国为了提高信息储存和传递的效率，发明了多种新的信息储存和传递的效
6、率，发明了多种新的编码方法，奠定了现代信息科学技术的基编码方法，奠定了现代信息科学技术的基础。础。Shannon还于还于1949年发表了年发表了“保密系统保密系统的通信理论的通信理论”一文，奠定了现代密码学基一文，奠定了现代密码学基础从而对加密过程中信息编码有了明确的础从而对加密过程中信息编码有了明确的分析。在该文中他从信息论观点，对信息分析。在该文中他从信息论观点，对信息系统的保密性问题作了全面而深刻的阐述。系统的保密性问题作了全面而深刻的阐述。1.信信 息息 熵熵 基基 本本 知知 识识 信息论中最重要的内容，是如何认识和使用信息论中最重要的内容，是如何认识和使用信息熵来表现信息。信息熵来
7、表现信息。这里用这里用Shannon最喜欢用的最喜欢用的猜谜方法来说明信息熵的基本概念。假如有：猜谜方法来说明信息熵的基本概念。假如有：“我们大我们大_都喜都喜_使使_计计_机来管机来管_数数_。”不用很多努力，就可以猜出完整的句子不用很多努力，就可以猜出完整的句子:“我们大我们大家都喜欢使用计算机来管理数据。家都喜欢使用计算机来管理数据。”Shannon在在信息论中指出，能猜出来的字符不运载信息，而信息论中指出，能猜出来的字符不运载信息，而不能猜出来的字符运载信息。不能猜出来的字符运载信息。1.信信 息息 熵熵 基基 本本 知知 识识(续续)空格所隐藏的字符属于多余度字符，不空格所隐藏的字符
8、属于多余度字符，不用那些字符也能运载该句子的全部信息，用那些字符也能运载该句子的全部信息，比如：比如：“我我_大大_使使_机来机来_数数_。”就很难猜出完整的句子，在就很难猜出完整的句子，在信息传递的时候，也很难做检错和抗错。信息传递的时候，也很难做检错和抗错。因此，保留一定的多余度因此，保留一定的多余度(或冗余度或冗余度)是非常是非常重要的。重要的。2.信息量和信息熵基本定义信息量和信息熵基本定义(1)信息熵（信息熵（information entropy）是对）是对信息状态信息状态“无序无序”与与“不确定不确定”的度量的度量（从本质上讲，熵不是对信息的度量，但（从本质上讲，熵不是对信息的度
9、量，但信息的增加而使产生的熵减小，熵可以用信息的增加而使产生的熵减小，熵可以用来度量信息的增益）。来度量信息的增益）。2.信息量和信息熵基本定义信息量和信息熵基本定义(2)定义：给定一离散集合定义：给定一离散集合X=xi;i=1,2,n，令令xi出现的概率是出现的概率是 且且 。事件。事件xi包含的信息量包含的信息量 通常通常=2，此时相应的信息量单位是，此时相应的信息量单位是bit。Shannon定义信息的数学期望为信息熵，即定义信息的数学期望为信息熵，即信源的平均信息量。信源的平均信息量。()0ip x1()1niip x)(log)(iaixPxI(2.1)2.信息量和信息熵基本定义信息
10、量和信息熵基本定义(3)定义：将集合定义：将集合X中事件所包含的信息量统计中事件所包含的信息量统计平均，则平均值定义为集合平均，则平均值定义为集合X的熵的熵.信息熵表信息熵表征了信源整体的统计特征，集合征了信源整体的统计特征，集合X的熵的熵H（x）表示）表示X中事件所包含的平均信息量，中事件所包含的平均信息量，或总体的平均不确定性的量度。或总体的平均不确定性的量度。0)(log)()(log)(212iniiixpxpxPExH(2.2)2.信息量和信息熵基本定义信息量和信息熵基本定义(4)对某一特定的信源，对某一特定的信源，其信息熵只有一个，其信息熵只有一个，因统计特性不同，其因统计特性不同
11、，其熵也不同。例如，两熵也不同。例如，两个信源，其概率空间个信源，其概率空间分别为：分别为：12,()0.990.01ixxX P x12,()0.50.5iyyY P y2.信息量和信息熵基本定义信息量和信息熵基本定义(5)则信息熵为：则信息熵为：可见，可见，,说明信源说明信源 比信源比信源 的平均不确定的平均不确定性要大，即在事件发生之前，分析信源性要大，即在事件发生之前，分析信源 ，由于事，由于事件件 是等概率的，难以猜测哪一个事件会发生是等概率的，难以猜测哪一个事件会发生.()0.99log0.990.01log0.010.08H Xbit()0.5log0.50.5log0.51H
12、Ybit()()HYH XYXY21,yy2.信息量和信息熵基本定义信息量和信息熵基本定义(6)而信源而信源 ，虽然也存在不确定性，但大致可以，虽然也存在不确定性，但大致可以知道知道,出现的可能性要大。正如两场比赛，其中出现的可能性要大。正如两场比赛，其中一场，双方势均力敌；而另一场双方实力悬殊很一场，双方势均力敌；而另一场双方实力悬殊很大。当然大。当然,人们希望看第一场，因为胜负难卜，一人们希望看第一场，因为胜负难卜，一旦赛完，人们获得信息量大。也可以这样理解，旦赛完，人们获得信息量大。也可以这样理解，信息熵信息熵 表征了变量表征了变量 的随机性。因此，熵反映了变的随机性。因此，熵反映了变量
13、的随机性，也是表征随机变量统计特性的一个量的随机性，也是表征随机变量统计特性的一个特征参数。特征参数。X1x3.信息熵的基本性质信息熵的基本性质(1)对称性对称性 当概率空间中当概率空间中 序任意互换时，序任意互换时，熵函数的值不变，例如下面两个信源空熵函数的值不变，例如下面两个信源空间间:)(),(21xPxP216131)(,321xxxxPX312161)(,321yyyyPX3.信息熵的基本性质信息熵的基本性质(2)其信息熵其信息熵 .该性质说明，熵该性质说明，熵只与随机变量的总体结构有关，与信源总只与随机变量的总体结构有关，与信源总体的统计特性有关，同时也说明所定义的体的统计特性有关
14、，同时也说明所定义的熵有其局限性，它不能描述事件本身的主熵有其局限性，它不能描述事件本身的主观意义。观意义。)()(YHXH3.信息熵的基本性质信息熵的基本性质(3)确定性确定性 如果信源的输出只有一个状态是必然的如果信源的输出只有一个状态是必然的,即即 则信源的熵则信源的熵:此性质表明，信源的输出虽有不同形态，但其中此性质表明，信源的输出虽有不同形态，但其中一种是必然的，意味着其他状态不可能出现。一种是必然的，意味着其他状态不可能出现。那么，这个信源是一个确知信源，其熵为零。那么，这个信源是一个确知信源，其熵为零。,0)()(,1)(321xPxPxP2()1 log10 log00niH
15、X (2.3)3.信息熵的基本性质信息熵的基本性质(4)非负性非负性 即即 。因为随机变量因为随机变量 的所有取值的的所有取值的概率分布为概率分布为 ，当取对数的底大，当取对数的底大于时，于时，,而而 ,则得到则得到的熵是正值，只有当随机变量是一确知的熵是正值，只有当随机变量是一确知量时，熵才等于零。这种非负性对于离量时，熵才等于零。这种非负性对于离散信源的熵来说，这一性质并不存在。散信源的熵来说，这一性质并不存在。0)(XH1)(0ixP0)(logixP0)(log)(iixPxP3.信息熵的基本性质信息熵的基本性质(5)可加性可加性 独立信源独立信源 和和 的联合信源的熵等于它们各自的的
16、联合信源的熵等于它们各自的熵之和。熵之和。如果有两个随机变量如果有两个随机变量 和和 ，它们彼此是它们彼此是统计独立的，即统计独立的，即 的概率分布为的概率分布为 ,而而 的分布概率为的分布概率为 ,则联合信源则联合信源的熵的熵:可加性是熵函数的一个重要特性，正因为有可加性，可加性是熵函数的一个重要特性，正因为有可加性，所以可以证明熵函数的形式是唯一的。所以可以证明熵函数的形式是唯一的。XYXYX)(,),(),(21sxPxPxPY)(,),(),(21zyPyPyP)()()(YHXHXYH1)(1NiixP1)(1MjiyP3.信息熵的基本性质信息熵的基本性质(6)极值性极值性 信源各个
17、状态为零概率分布时，熵值最信源各个状态为零概率分布时，熵值最大，并且等于信源输出状态数，因为大，并且等于信源输出状态数，因为 当当 时，时，(2.5)NxPxPxPs/1)()()(21NNNXHNilog1log1)(1例例 题题 例，信源有两种状态时，概率空间例，信源有两种状态时，概率空间 其其 与与 关系如图所示关系如图所示,，当，当 =1/2时熵有最大值；时熵有最大值；当信源输出是确定的，即当信源输出是确定的，即 ，则，则 ，此时表，此时表明该信源不提供任何信息；反之，当信源输出为等概明该信源不提供任何信息；反之，当信源输出为等概率发生时，即率发生时，即 时信源的熵达到最大值，等于时信
18、源的熵达到最大值，等于1bit信息量。信息量。)(1)P(x)(,1121xPxxxPXi)(XH)(xP)(xP1)(1xP0)(XH2/1)(1xP 信息熵函数曲线P(x)00.51明文H(x)4.信息熵在信息加密编码中的作用信息熵在信息加密编码中的作用(1)通过熵和信息量的概念，可计算加密系统中各通过熵和信息量的概念，可计算加密系统中各部分的熵。令明文熵为部分的熵。令明文熵为 ，密钥，密钥熵熵 ，密文熵，密文熵 。这里。这里M、K和和C分别是明文、密钥和密文空间，分别是明文、密钥和密文空间，m、k、c分别是它们的字母集，分别是它们的字母集，l,r和和v分别是明文、密分别是明文、密钥、和密
19、文的长度。则明文和密文之间的互信钥、和密文的长度。则明文和密文之间的互信息以及密钥与密文之间的互信息分别是：息以及密钥与密文之间的互信息分别是：)()(lmHMH)()(rkHKH)()(vcHCH)()();(vllvlcmHmHcmI)()();(vrrvrckHkHckI(2.6)(2.7)4.信息熵在信息加密编码中的作用信息熵在信息加密编码中的作用(2)因为只要密文、密钥确定后，明文也就得到了，所以因为只要密文、密钥确定后，明文也就得到了，所以 ,故故 定理：对任意加密系统定理：对任意加密系统 从该理论我们可以看出，密钥熵越大，密文中所包含的从该理论我们可以看出，密钥熵越大，密文中所包
20、含的明文信息量就越小。一个加密系统中，若其密文与明明文信息量就越小。一个加密系统中，若其密文与明文之间的互信息文之间的互信息 ，则密码分析者无论截，则密码分析者无论截获多大的密文，均不能得到有关明文的任何信息。这获多大的密文，均不能得到有关明文的任何信息。这种加密系统称为完善加密系统，或无条件加密系统。种加密系统称为完善加密系统，或无条件加密系统。0),()(rvlkcmH)(),(;(lrvlmHkcmI)()();(KHmHcmIlvl(2.8)0);(vlcmI4.信息熵在信息加密编码中的作用信息熵在信息加密编码中的作用(3)在对密文攻击下，完善加密系统是安全的，但它不能在对密文攻击下，
21、完善加密系统是安全的，但它不能保证在已知明文或选择性明文攻击下也是安全的。因保证在已知明文或选择性明文攻击下也是安全的。因此，完善保密系统存在的必要条件是此，完善保密系统存在的必要条件是 证明：若证明：若 ，则由前一个定理可，则由前一个定理可得，得，所以，所以 的必要条件是的必要条件是)()(lmHKH(2.9)()(lmHKH0);(vlcmI0);(vlcmI)()(lmHKH2.1.2 数论基本术语数论基本术语数论是研究整数性质的一个数学分支，数论是研究整数性质的一个数学分支，同时也是加密技术的基础学科之一。首同时也是加密技术的基础学科之一。首先介绍一些数论的基本知识先介绍一些数论的基本
22、知识.1.整整 数数定义：设定义：设 。如果存在。如果存在 使得使得 ，那么就说，那么就说b 可可以被以被a 整除，记为整除，记为 ，且称，且称b是是a的倍数的倍数,a 是是b的因数的因数(或称约或称约数、除数、因子数、除数、因子)。b不能被不能被a整除可以记作整除可以记作dFa。由定义及乘法。由定义及乘法运算的性质，可推出整除关系具有以下性质（注：符号运算的性质，可推出整除关系具有以下性质（注：符号 本本身包含了条件身包含了条件 ）：）：（1）；（2）如果）如果 且且 ，则，则 ；（3）设）设 ,那么那么 与与 等价等价;（4）如果）如果 且且 ,则对所有的则对所有的 ,有有 ;（5）设）设
23、 ,如果如果 ,那么那么 ;0,aZbaZqaqb baba0aaabacbca0mbabmambacaZyx,cybxa0bbaba 2.素素 数数 定义定义:设整数设整数 。如果它除了显然因数。如果它除了显然因数 外没有其他的外没有其他的因数，则因数，则p就称为是素数，也叫不可约数。若就称为是素数，也叫不可约数。若 ，且且a不不是素数，则是素数，则a称为合数。称为合数。关于素数，有以下性质：关于素数，有以下性质：（1）如果）如果p是素数，且是素数，且 ，则，则 或或 ，即，即p至少整除至少整除a与与b中中的一个。的一个。（2）任何一个整数）任何一个整数 ，均可以分解成素数幂之积：，均可以分
24、解成素数幂之积：（3）若不计因数的顺序，这个分解式是唯一的。其中）若不计因数的顺序，这个分解式是唯一的。其中 ,是两两互不相同的素数，是两两互不相同的素数，是正整数。是正整数。（4）素数有无穷多个。）素数有无穷多个。（5）设）设 表示不大于表示不大于 的素数的数目，则的素数的数目，则 。0pp,10a1abpapbp2nkekeepppn21211kip)1(ki)1(kiei)(x1/ln)(limxxx3.同同 余余 设设 ，如果，如果 ，则称，则称a和和b模模n同同余，记为余，记为 ，整数，整数n称为模数。由称为模数。由 于于 等价于等价于 ，所以，所以 与与 等价。因此，一般我们总假定
25、等价。因此，一般我们总假定 。如。如果果 ，我们称，我们称b是是a对模对模n的最小非负剩的最小非负剩余，有时也称余，有时也称b为为a对模对模n的余数。的余数。0,nZba)(ban)(modnba banban)(mod nba)(mod(nba1nnb 0同余式的一些基本性质同余式的一些基本性质（1）反身性）反身性:；（2）对称性）对称性:如果如果 ，那么，那么 ；（3）传递性）传递性:如果如果 ，,那么那么 ；（4）如果）如果 ，那么那么 ；。（5）如果）如果 ，gcd ，(两个两个不同时为不同时为0的整数的整数a与与b的最大公约数表示成的最大公约数表示成gcd(a,b)那那么么 ，存在，
26、存在 ,当且仅当当且仅当gcd 。)(modnaa)(modnba)(modnab)(modnba)(modncb)(modnca)(mod1naa)(mod1nbb)(mod11nbaba)(mod11nbaba)(mod11nbaab)(modnbdac)(modnba 1),(na)(modndc)(mod1nac 1),(na一些关于同余的基本概念(1)同余类同余类 可用其中任一元素可用其中任一元素a(经常取经常取 )代替，记作代替，记作 。于是。于是 从从 中分别取一个数作为代表构成中分别取一个数作为代表构成一个集合，称为模一个集合，称为模n的一个完全剩余系，的一个完全剩余系，记为记
27、为 ，称为模，称为模n的非负最小完的非负最小完全剩余系。全剩余系。0,qrZqqnrra a 1 1 0nz )10(njiji(2.11)1,1,0n1,1,0nnZ一些关于同余的基本概念(2)在模在模n的完全剩余系中，去掉那些与的完全剩余系中，去掉那些与n不互素的数，不互素的数，剩下的部分称为模剩下的部分称为模n的简化剩余系；的简化剩余系；的简化剩余的简化剩余系记为系记为 ，读为模，读为模n的非负最小简化剩余系。显的非负最小简化剩余系。显然然,中的元便是不超过中的元便是不超过n并与并与n互素的那些数，互素的那些数，它们的个数等于欧拉函数它们的个数等于欧拉函数 的值。的值。（欧拉函数（欧拉函
28、数的定义为的定义为:小于自然数小于自然数N并与并与N互质互质(除除1以外无其以外无其它公因子它公因子)的自然数的个数用函数的自然数的个数用函数 表示表示,称为欧称为欧拉函数。欧拉函数的具体性质会在后面第拉函数。欧拉函数的具体性质会在后面第6小节进小节进行阐述）行阐述）nZ*nZ*nZ)(n)(n4.模模 运运 算算 给定正整数给定正整数n，对任意，对任意a，若存在，若存在q，使得，使得 则称则称r是是a关于模关于模n的余数，的余数，记为记为 。若若 则称整数则称整数a，b同余，记同余，记为为 整数集中所有与数整数集中所有与数a同余的整数集合称为同余的整数集合称为a的同余类，记为的同余类，记为
29、。)0(nrrqnanarmod)mod()mod(nbna(mod)abn na模模 运运 算算 的的 性性 质质（1）当且仅当当且仅当 。（2）当且仅当当且仅当 。（3）如果）如果 ，则，则 。a模模n的运算给出了的运算给出了a对模对模n的余数。注意：模运算的结果的余数。注意：模运算的结果是从是从0到到 的一个整数。模运算就像普通的运算一样，的一个整数。模运算就像普通的运算一样，它是可交换，可结合，可分配的。而且，对每一个中间它是可交换，可结合，可分配的。而且，对每一个中间结果进行模结果进行模m运算，其作用与先进行全部运算，然后再运算，其作用与先进行全部运算，然后再进行模进行模m运算所得到
30、结果是一样的。运算所得到结果是一样的。)(modnba)(ban)(modnba)(modnab)(modnba)(modncb)(modnca 1n5.最大公约数与最小公倍数最大公约数与最小公倍数 设设 ，是两个整数，如果是两个整数，如果 且且 ，那么就称，那么就称b是是 和和 的公约的公约数数.一般的，设一般的，设 ，是，是K个整数，如果个整数，如果 那么就称那么就称b是是 的公约数。因为对于任意一个不等于零的公约数。因为对于任意一个不等于零的整数，它的因数是有限的。所以，任意一对整数的整数，它的因数是有限的。所以，任意一对整数 ，其中一，其中一个不为零时，它们的公约数的个数也必定是有限的
31、；同理，当个不为零时，它们的公约数的个数也必定是有限的；同理，当 中有一个不为零时，它们的公约数是有限的中有一个不为零时，它们的公约数是有限的.这样这样,我们引入最大公我们引入最大公约数的概念。约数的概念。定义定义:设设 ，是两个整数，我们把是两个整数，我们把 和和 的公约数中最大的数的公约数中最大的数称为称为 和和 的最大公约数，记为的最大公约数，记为(,)或或 当当 时，我们称时，我们称 和和 是互素的。是互素的。显然显然1a2a1ab2ab1a2akaaa,21kababab,21kaaa,2121,aakaaa,211a2a1a2a1a2a),gcd(21aa1),(21aa1a2a0
32、),(21aa1a2a最最 大大 公公 约约 数数 的的 性性 质质（1）（2）若）若|,j=2,k，则，则（3）任意的整数）任意的整数x,有有（4）对任意的整数）对任意的整数x,有有 （5）设）设 ,是不都为零的整数，则一定存是不都为零的整数，则一定存在一对整数在一对整数 ,，使得：，使得：),(),(),(211221aaaaaa1aja12121),(),(aaaaaak),(),(12121xaaaaa),(),(12121xaaaaa1a2a1x2x221121),(xaxaaa最最 小小 公公 倍倍 数数 的的 概概 念念 设设 ，是两个均不等于零的整数，如果是两个均不等于零的整数
33、，如果 且且 ，那么，那么 1 就称为是就称为是 和和 的公倍数，的公倍数，一般地，设一般地，设 是是k个均不等于零的整数。个均不等于零的整数。如果如果 ，则称，则称 l是是 的公倍数。的公倍数。公倍数的集合是无穷集合，但根据自然数的理公倍数的集合是无穷集合，但根据自然数的理论，存在最小的正的公倍数。我们把论，存在最小的正的公倍数。我们把 和和 的正的公倍数中最小的数称为的正的公倍数中最小的数称为 和和 的最小的最小公倍数，记为公倍数，记为 或或1a2a11a12a1a2akaaa,211,1,121kaaakaaa,211a2a1a2a,21aa),(balcm6.欧拉欧拉（Euler）函数
34、函数 欧拉（欧拉（Euler）函数）函数 设设n1,欧拉函数欧拉函数 表示在区间表示在区间 中与中与n互素的互素的整数的个数。整数的个数。欧拉函数欧拉函数 具有以下性质：具有以下性质：(1)如果如果p是素数，则是素数，则 ；(2)如果如果p是素数，是素数，。那么。那么 ；(3)对于整数对于整数 ,根据算术基本定理，根据算术基本定理，n可以分解成惟一的形可以分解成惟一的形如如 的分解式，则的分解式，则 (4)若若 和和 互素，则互素，则 。)(n Zzn:)(,1 n)(n1)(pp1k)1()(1pppkk2nkekeepppn2121)/11()/11)(/11()(21kpppnn1m2m
35、)()()(21mmm2.1.3 算法复杂性基础知识算法复杂性基础知识 所谓问题，是指一个要求给出解释的一所谓问题，是指一个要求给出解释的一般性提问，通常含有若干个未定参数或自由般性提问，通常含有若干个未定参数或自由变量。它由两个要素组成变量。它由两个要素组成，第一个要素是描，第一个要素是描述所有的参数，也就是对所有未定参数的一述所有的参数，也就是对所有未定参数的一般性描述般性描述;第二个要素是解答必须满足的性质。第二个要素是解答必须满足的性质。一个问题一个问题 可以看成是由无穷多个问题实例组可以看成是由无穷多个问题实例组成的一个类。成的一个类。1.算算 法法 的的 定定 义义 所谓所谓算法算
36、法是由明确指出操作的规则所组成的是由明确指出操作的规则所组成的若干语句的集合，只要按照规则一步一步执行一若干语句的集合，只要按照规则一步一步执行一定数目的语句，便可求出问题的答案。通常的计定数目的语句，便可求出问题的答案。通常的计算机程序都可以看作是算法的表达形式，在问题算机程序都可以看作是算法的表达形式，在问题的两要素中，对算法而言，第一个要素就是的两要素中，对算法而言，第一个要素就是“输输入入”，第二个要素就是，第二个要素就是“输出输出”。如果把问题。如果把问题P的的任意一个实例作为算法任意一个实例作为算法A的输入，的输入，A在有限步骤之在有限步骤之内总能输出关于此实例的正确答案，我们就说
37、算内总能输出关于此实例的正确答案，我们就说算法法A可解问题可解问题P。对于一个问题。对于一个问题P，如果存在一个，如果存在一个算法算法A可解问题可解问题P，我们称问题，我们称问题P是是算法可解算法可解的。的。2.算算 法法 复复 杂杂 性性 算法的复杂性表征了算法在实际执行时所需计算法的复杂性表征了算法在实际执行时所需计算能力方面的信息算能力方面的信息，通常它由该算法所要求的最通常它由该算法所要求的最大时间与存取空间来确定。大时间与存取空间来确定。由于算法所需的时间由于算法所需的时间和空间往往取决于问题实例的规模和空间往往取决于问题实例的规模n (n表示了该表示了该实例的输入数据长度实例的输入
38、数据长度)，同时，算法在用于相同规，同时，算法在用于相同规模模n的不同实例时。其时间和空间需求也可能会有的不同实例时。其时间和空间需求也可能会有很大差异，因此，实际中我们常常研究的是算法很大差异，因此，实际中我们常常研究的是算法关于输入规模关于输入规模 的所有实例的时间与空间需求的平的所有实例的时间与空间需求的平均值。均值。算算 法法 复复 杂杂 性性 的的 构构 成成 通常情况下，一个算法的计算复杂性由两个变通常情况下，一个算法的计算复杂性由两个变量度量：时间复杂性量度量：时间复杂性 和空间复杂性和空间复杂性 。它们。它们定义如下：定义如下：（1）时间复杂性时间复杂性 ：以某特定的基本步骤为
39、单元，：以某特定的基本步骤为单元，完成计算过程所需的总单元数称为算法的时间复杂完成计算过程所需的总单元数称为算法的时间复杂性，或时间复杂度。性，或时间复杂度。n为输入的规模或尺寸。为输入的规模或尺寸。（2）空间复杂性空间复杂性 :以某特定的基本存储空间为单以某特定的基本存储空间为单元，完成计算过程所用的存储单元数，称为算法的元，完成计算过程所用的存储单元数，称为算法的空间复杂性或空间复杂度。空间复杂性或空间复杂度。n是输入的规模或尺寸。是输入的规模或尺寸。)(nT)(nS)(nT)(nS算法复杂性的基本符号算法复杂性的基本符号（1）一个算法的计算复杂性用一个算法的计算复杂性用“O”符号表示其符
40、号表示其数量级。数量级。“O”的意思是：对于两个任意的的意思是：对于两个任意的实值函数实值函数f和和g，若记号，若记号 ，则，则存在有一个值存在有一个值a，对充分大的，对充分大的n，有有 。计算复杂性的数量级就是这。计算复杂性的数量级就是这种类型的函数，即当种类型的函数，即当n变大时增长得最快的变大时增长得最快的函数，所有常数和较低阶形式的函数可以函数，所有常数和较低阶形式的函数可以忽略不计。忽略不计。nngOnf),()()()(nganf算法复杂性的基本符号算法复杂性的基本符号（2）另一个符号是另一个符号是“o”。它的定义是：。它的定义是：当且仅当当且仅当 ，这意味着在，这意味着在 时，时
41、，比比 可以忽略不计。可以忽略不计。时间复杂度时间复杂度 有时有时也用工作因子也用工作因子W表示，这时表示，这时 。如果一个算。如果一个算法的复杂性不依赖于法的复杂性不依赖于n，那么它是常数级的用，那么它是常数级的用 表表示之，而示之，而 表示复杂性随表示复杂性随n线性增长，因而是线线性增长，因而是线性型算法。复杂性随性型算法。复杂性随n线性增长的其他一些算法也线性增长的其他一些算法也称为二次方或三次方等，所有这些算法都是多项称为二次方或三次方等，所有这些算法都是多项式的，它们的时间复杂性是式的，它们的时间复杂性是 。有多项式。有多项式时间复杂性的算法称为多项式时间算法或有效算时间复杂性的算法
42、称为多项式时间算法或有效算法。法。nngonf),()(lim()/()0nf ng nn)(nf)(ng)(ngo)(ngW)1(o)(no)()(lnonT3.问问 题题 的的 复复 杂杂 性性 问题的复杂性是问题固有的性质。问题问题的复杂性是问题固有的性质。问题的复杂性理论利用算法复杂性作为工具，的复杂性理论利用算法复杂性作为工具，将大量典型的问题按照求解的代价进行分将大量典型的问题按照求解的代价进行分类。问题的复杂性由在图灵机上解其最难类。问题的复杂性由在图灵机上解其最难实例所需的最小时间与空间决定，还可以实例所需的最小时间与空间决定，还可以理解为由解该问题的最有效的算法所需的理解为由
43、解该问题的最有效的算法所需的时间与空间来度量。时间与空间来度量。N P 问问 题题 在确定型图灵机上可用多项式时间求解的问在确定型图灵机上可用多项式时间求解的问题，称为易处理的问题。易处理的问题的全体称题，称为易处理的问题。易处理的问题的全体称为确定性多项式时间可解类，记为为确定性多项式时间可解类，记为P类。在非确定类。在非确定性图灵机上可用多项式时间求解的问题，称为非性图灵机上可用多项式时间求解的问题，称为非确定性多项式时间可解问题，记为确定性多项式时间可解问题，记为NP问题问题。NP问问题的全体称为非确定性多项式时间可解类，记为题的全体称为非确定性多项式时间可解类，记为NP类。显然，类。显
44、然，因为在确定型图灵机上多项，因为在确定型图灵机上多项式时间可解的任何问题在非确定型图灵机上也是式时间可解的任何问题在非确定型图灵机上也是多项式时间可解的。多项式时间可解的。NPP N P C 问问 题题 NP类中还有一类问题称为类中还有一类问题称为NP完全类，记为完全类，记为NPC。所。所有的有的NP问题都可以通过多项式时间转换为问题都可以通过多项式时间转换为NPC中的中的问题。问题。NPC是是NP类中困难程度最大的一类问题类中困难程度最大的一类问题,但但NPC中的问题困难程度相当，都可以多项式时间转化中的问题困难程度相当，都可以多项式时间转化为称为可满足性问题的为称为可满足性问题的NPC问
45、题，此类问题，此类NPC具有如下具有如下性质，若其中的任何一个问题属于性质，若其中的任何一个问题属于P，则所有的，则所有的NP问问题都属于题都属于P，且，且 。现在的密码算法的安全性都。现在的密码算法的安全性都是基于是基于NPC问题的，破译一个密码相当于求解一个问题的，破译一个密码相当于求解一个NPC问题问题,如果如果 ，则破译密码就是一件很容易，则破译密码就是一件很容易的事情的事情.NPP NPP 2.2 信息加密方式与标准信息加密方式与标准 经典的信息加密理论主要用于通信保密，而经典的信息加密理论主要用于通信保密，而现代信息加密技术的应用已深入到信息安全的各现代信息加密技术的应用已深入到信
46、息安全的各个环节和对象，信息的加密方式和标准也有了深个环节和对象，信息的加密方式和标准也有了深入广泛的发展，特别是现代加密和信息隐藏技术入广泛的发展，特别是现代加密和信息隐藏技术的结合，实现信息隐蔽传输使人类对信息的加密的结合，实现信息隐蔽传输使人类对信息的加密技术有了新的认识和要求，下面介绍信息加密技技术有了新的认识和要求，下面介绍信息加密技术的基本概念、方式和标准。术的基本概念、方式和标准。2.2.1 信息加密基本概念信息加密基本概念（1）研究安全信息的加密技术和研究破解安全信息密码的密研究安全信息的加密技术和研究破解安全信息密码的密码分析技术的学科称为码分析技术的学科称为密码学密码学。信
47、息加密是通过使用一种编。信息加密是通过使用一种编码而使某些可读的信息码而使某些可读的信息(明文明文)变为不可读的信息变为不可读的信息(密文密文)。这。这些编码就是将明文变成密文的加密算法些编码就是将明文变成密文的加密算法(也称为密码也称为密码)或数学或数学方法。密码使用隐蔽语言、文字、图象的特种符号，目标是方法。密码使用隐蔽语言、文字、图象的特种符号，目标是接收数据作为输入，产生密文作为输出，以便数据的原始意接收数据作为输入，产生密文作为输出，以便数据的原始意义得以隐藏。在计算机通讯中，采用密码（密钥为参数）将义得以隐藏。在计算机通讯中，采用密码（密钥为参数）将信息隐蔽起来，再将隐蔽后的信息传
48、输出去，使信息在传输信息隐蔽起来，再将隐蔽后的信息传输出去，使信息在传输过程中即使被窃取或载获，也不能了解信息的内容，从而保过程中即使被窃取或载获，也不能了解信息的内容，从而保证信息传输的安全。证信息传输的安全。2.2.1 信息加密基本概念信息加密基本概念（2）通信两端将信息编码时，发送端使用简单通信两端将信息编码时，发送端使用简单的信息加密；接收端收到传来的信息后通过解的信息加密；接收端收到传来的信息后通过解密看到编码前的信息，整个过程中加密或解密密看到编码前的信息，整个过程中加密或解密是由密钥控制实现的。是由密钥控制实现的。密钥密钥是用户按照一种密是用户按照一种密码体制随机选取，它通常是一
49、随机字符串，是码体制随机选取，它通常是一随机字符串，是控制明文变换（加密）和密文变换（解密）的控制明文变换（加密）和密文变换（解密）的唯一参数。密钥全体称为密钥空间。一般来说，唯一参数。密钥全体称为密钥空间。一般来说，密钥越大，加密就越健壮。密钥越大，加密就越健壮。加密系统的组成部分加密系统的组成部分 如上所述，一个加密系统实际上是某种加密算法在如上所述，一个加密系统实际上是某种加密算法在密钥控制下实现的从明文到密文的映射，它至少包括下密钥控制下实现的从明文到密文的映射，它至少包括下面四个组成部分：面四个组成部分：（1）加密的报文，也称明文；）加密的报文，也称明文；（2）加密后的报文，也称密文
50、；）加密后的报文，也称密文；（3）加密解密设备或算法；）加密解密设备或算法；（4）加密解密的密钥；）加密解密的密钥；一般情况下，密钥由一般情况下，密钥由K表示，明文由表示，明文由m表示，加密算法表示，加密算法由由 ()表示，解密算法由表示，解密算法由 ()表示，；表示，；则，则，(m)=m 1EK2DK2DK1EK加密系统示意图加密系统示意图一个完整的加密系统如下图所示一个完整的加密系统如下图所示:信源信源加密加密解密解密信宿信宿密文密文明文明文窃听窃听干扰干扰明文明文密钥密钥K1密钥密钥K2图图2.2 加密系统示意图加密系统示意图加密系统的安全规则加密系统的安全规则（1）任何一个加密系统必须
