第2章信息加密技术基础

第二章信息加密技术基础引言信息加密是网络安全体系中重要机制之一。信息加密的目的是为了保持信息的机密性，使用恰当的加密标准将在计算机环境中增加安全性。信息加密通过使用一种编码而使存储或传输的信息变为不可读的信息，解密是一个相反的过程。这些编码就是将明文变成密文的加密算法或数学方法。引言(续)加密编码在Shannon的信息论中有针对性的阐述，数论及基础代数是加密算法的理论基础。要将一段信息加密或解密，你会要用到密钥，它是一个很大的值。一般来说，密钥越大，加密就越健壮。一般来说加密体制分为对称密钥加密和公用密钥加密，对称密钥加密在密钥方面有一定的缺陷，但执行效率高；公用密钥加密加密执行效率底，但保密性强，在报文和网络方面对小量信息加密非常有效.2.1信息加密理论基础信息安全的核心技术之一是加密技术，它涉及信息论、基础数论和算法复杂性等多方面基础知识。随着计算机网络不断渗透到各个领域，加密技术的应用也随之扩大，应用加密基础理论知识，深入探索可靠可行的加密方法，应用于数字签名、身份鉴别等新技术中成为网络安全研究重要的一个方面。加密的理论依据密码学问题就是随机性的利用问题.差不多每台使用加密技术的计算机安全系统都需要随机数，供密钥、协议中的基础参量等使用或者用做辅助信息或者初始化向量。这些系统的安全也经常依赖于这些随机数的随机性及被保护程度。简单的加密举例中秋日月编码密钥密文编码诗月明明日01010110111111明日月明101010000000？明日明日101101000111日明月明110010011000通过这个例子我们看到一个简单的加密过程，原来的诗通过与密钥的模二运算实现了加密。2.1.1信息编码基础知识第二次世界大战期间，美国为了提高信息储存和传递的效率，发明了多种新的编码方法，奠定了现代信息科学技术的基础。Shannon还于1949年发表了“保密系统的通信理论”一文，奠定了现代密码学基础从而对加密过程中信息编码有了明确的分析。在该文中他从信息论观点，对信息系统的保密性问题作了全面而深刻的阐述。1.信息熵基本知识信息论中最重要的内容，是如何认识和使用信息熵来表现信息。这里用Shannon最喜欢用的猜谜方法来说明信息熵的基本概念。假如有：“我们大__都喜__使__计__机来管__数__。”不用很多努力，就可以猜出完整的句子:“我们大家都喜欢使用计算机来管理数据。”Shannon在信息论中指出，能猜出来的字符不运载信息，而不能猜出来的字符运载信息。1.信息熵基本知识(续)空格所隐藏的字符属于多余度字符，不用那些字符也能运载该句子的全部信息，比如：“我__大________使______机来____数__。”就很难猜出完整的句子，在信息传递的时候，也很难做检错和抗错。因此，保留一定的多余度(或冗余度)是非常重要的。2.信息量和信息熵基本定义(1)信息熵（informationentropy）是对信息状态“无序”与“不确定”的度量（从本质上讲，熵不是对信息的度量，但信息的增加而使产生的熵减小，熵可以用来度量信息的增益）。2.信息量和信息熵基本定义(2)定义：给定一离散集合X={xi;i=1,2,…,n}，令xi出现的概率是且。事件xi包含的信息量通常=2，此时相应的信息量单位是bit。Shannon定义信息的数学期望为信息熵，即信源的平均信息量。()0ipx1()1niipx)(log)(iaixPxI(2.1)2.信息量和信息熵基本定义(3)定义：将集合X中事件所包含的信息量统计平均，则平均值定义为集合X的熵.信息熵表征了信源整体的统计特征，集合X的熵H（x）表示X中事件所包含的平均信息量，或总体的平均不确定性的量度。0)(log)()](log[)(212iniiixpxpxPExH(2.2)2.信息量和信息熵基本定义(4)对某一特定的信源，其信息熵只有一个，因统计特性不同，其熵也不同。例如，两个信源，其概率空间分别为：12[,()]0.990.01ixxXPx12[,()]0.50.5iyyYPy2.信息量和信息熵基本定义(5)则信息熵为：可见，,说明信源比信源的平均不确定性要大，即在事件发生之前，分析信源，由于事件是等概率的，难以猜测哪一个事件会发生.()0.99log0.990.01log0.010.08[]HXbit()0.5log0.50.5log0.51[]HYbit()()HYHXYXY21,yy2.信息量和信息熵基本定义(6)而信源，虽然也存在不确定性，但大致可以知道,出现的可能性要大。正如两场比赛，其中一场，双方势均力敌；而另一场双方实力悬殊很大。当然,人们希望看第一场，因为胜负难卜，一旦赛完，人们获得信息量大。也可以这样理解，信息熵表征了变量的随机性。因此，熵反映了变量的随机性，也是表征随机变量统计特性的一个特征参数。X1x3.信息熵的基本性质(1)I.对称性当概率空间中序任意互换时，熵函数的值不变，例如下面两个信源空间:)(),(21xPxP216131)](,[321xxxxPX312161)](,[321yyyyPX3.信息熵的基本性质(2)其信息熵.该性质说明，熵只与随机变量的总体结构有关，与信源总体的统计特性有关，同时也说明所定义的熵有其局限性，它不能描述事件本身的主观意义。)()(YHXH3.信息熵的基本性质(3)II.确定性如果信源的输出只有一个状态是必然的,即则信源的熵:此性质表明，信源的输出虽有不同形态，但其中一种是必然的，意味着其他状态不可能出现。那么，这个信源是一个确知信源，其熵为零。,0)()(,1)(321xPxPxP2()[1log10log0]0niHX(2.3)3.信息熵的基本性质(4)III.非负性即。因为随机变量的所有取值的概率分布为，当取对数的底大于１时，,而,则得到的熵是正值，只有当随机变量是一确知量时，熵才等于零。这种非负性对于离散信源的熵来说，这一性质并不存在。0)(XH1)(0ixP0)(logixP0)(log)(iixPxP3.信息熵的基本性质(5)IV.可加性独立信源和的联合信源的熵等于它们各自的熵之和。如果有两个随机变量和，它们彼此是统计独立的，即的概率分布为,而的分布概率为,则联合信源的熵:可加性是熵函数的一个重要特性，正因为有可加性，所以可以证明熵函数的形式是唯一的。XYXYX)](,),(),([21sxPxPxPY)](,),(),([21zyPyPyP)()()(YHXHXYH1)(1NiixP1)(1MjiyP3.信息熵的基本性质(6)V.极值性信源各个状态为零概率分布时，熵值最大，并且等于信源输出状态数，因为当时，(2.5)NxPxPxPs/1)()()(21NNNXHNilog1log1)(1例题例，信源有两种状态时，概率空间其与关系如图所示,，当=1/2时熵有最大值；当信源输出是确定的，即，则，此时表明该信源不提供任何信息；反之，当信源输出为等概率发生时，即时信源的熵达到最大值，等于1bit信息量。)(1)P(x)](,[1121xPxxxPXi)(XH)(xP)(xP1)(1xP0)(XH2/1)(1xP信息熵函数曲线P(x)00.51明文H(x)4.信息熵在信息加密编码中的作用(1)通过熵和信息量的概念，可计算加密系统中各部分的熵。令明文熵为，密钥熵，密文熵。这里M、K和C分别是明文、密钥和密文空间，m、k、c分别是它们的字母集，l,r和v分别是明文、密钥、和密文的长度。则明文和密文之间的互信息以及密钥与密文之间的互信息分别是：)()(lmHMH)()(rkHKH)()(vcHCH)()();(vllvlcmHmHcmI)()();(vrrvrckHkHckI(2.6)(2.7)4.信息熵在信息加密编码中的作用(2)因为只要密文、密钥确定后，明文也就得到了，所以,故定理：对任意加密系统从该理论我们可以看出，密钥熵越大，密文中所包含的明文信息量就越小。一个加密系统中，若其密文与明文之间的互信息，则密码分析者无论截获多大的密文，均不能得到有关明文的任何信息。这种加密系统称为完善加密系统，或无条件加密系统。0)),()(rvlkcmH)()),(;(lrvlmHkcmI)()();(KHmHcmIlvl(2.8)0);(vlcmI4.信息熵在信息加密编码中的作用(3)在对密文攻击下，完善加密系统是安全的，但它不能保证在已知明文或选择性明文攻击下也是安全的。因此，完善保密系统存在的必要条件是证明：若，则由前一个定理可得，，所以的必要条件是)()(lmHKH(2.9))()(lmHKH0);(vlcmI0);(vlcmI)()(lmHKH2.1.2数论基本术语•数论是研究整数性质的一个数学分支，同时也是加密技术的基础学科之一。首先介绍一些数论的基本知识.1.整数定义：设。如果存在使得，那么就说b可以被a整除，记为，且称b是a的倍数,a是b的因数(或称约数、除数、因子)。b不能被a整除可以记作dFa。由定义及乘法运算的性质，可推出整除关系具有以下性质（注：符号本身包含了条件）：（1）；（2）如果且，则；（3）设,那么与等价;（4）如果且,则对所有的,有;（5）设,如果,那么;0,,aZbaZqaqbbaba0aaabacbca0mbabmambacaZyx,cybxa0bbaba2.素数定义:设整数。如果它除了显然因数外没有其他的因数，则p就称为是素数，也叫不可约数。若，且a不是素数，则a称为合数。关于素数，有以下性质：（1）如果p是素数，且，则或，即p至少整除a与b中的一个。（2）任何一个整数，均可以分解成素数幂之积：（3）若不计因数的顺序，这个分解式是唯一的。其中,是两两互不相同的素数，是正整数。（4）素数有无穷多个。（5）设表示不大于的素数的数目，则。0pp,10a1abpapbp2nkekeepppn21211kip)1(ki)1(kiei)(x1/ln)(limxxx3.同余设，如果，则称a和b模n同余，记为，整数n称为模数。由于等价于，所以与等价。因此，一般我们总假定。如果，我们称b是a对模n的最小非负剩余，有时也称b为a对模n的余数。0,,nZba)(ban)(modnbabanban)(modnba))(mod(nba1nnb0同余式的一些基本性质（1）反身性:；（2）对称性:如果，那么；（3）传递性:如果，,那么；（4）如果，那么；。（5）如果，，gcd，(两个不同时为0的整数a与b的最大公约数表示成gcd(a,b))那么，存在,当且仅当gcd。)(modnaa)(modnba)(modnab)(modnba)(modncb)(modnca)(mod1naa)(mod1nbb)(mod11nbaba)(mod11nbaba)(mod11nbaab)(modnbdac)(modnba1),(na)(modndc)(mod1nac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互