计算机网络安全技术第二章

第二章预备知识2．1数论基础数论是一门古老的数学分支。以前人们都认为它是完全纯粹的数学，在现实生活中很难找到它的实际应用。自从1976年公开密钥体制诞生以来，现代密码学就和数论有着千丝万缕的联系。因此，我们先简单介绍一下有关的数论基本概念。1．引言我们约定：字母N表示全体自然数集合，Z表示全体整数集合，即N={0,1,2,……}Z={……,-2,-1,0,1,2,……}定义2.1.1如果存在一个整数k∈Z使得n=kd，则称d整除n，记作d∣n，其中d称作n的因数，n称作d的倍数。如果不存在这样一个整数k∈Z使得n=kd，则称d不整除n，记作d+n。定义2.1.2整数p（1）,称为素数，如果除了1和其本身外，p没有任何其他因数。不是素数的整数称为合数。例2．16=23，6是合数，26，2是6的因数，6是2的倍数。7=17，除了1和7之外，没有其他因数，因此7是素数。定理2.1.1（带余数除法）设a，b是两个整数，其中b0。则存在两个整数q，r使得a=bq+r0rb成立，其中q和r是唯一确定的。设a，b是两个整数。既是a的因数又是b的因数的数称为a，b的公因数，a和b的所有公因数中最大者，称为a和b的最大公因数，记作gcd(a,b)。既是a的倍数又是b的倍数的数称为a和b的公倍数，a和b的所有公倍数中最小者称为a和b的最小公倍数，记作lcm(a,b)。显然a和b的最大公因数与最大公倍数满足下列等式：lcm(a,b)gcd(a,b)=ab如果对两个整数a,b有gcd(a,b)=1，则称a与b互素。定理2.1.2设a，bN，则存在两个整数u和v使得ua+vb=gcd(a，b)定理2.1.3（算术基本定理）任何一个正整数m都存在唯一的因数分解形式m=其中，eiN，pi是素数且p1p2pn。这个分解形式也称为m的标准分解形式。neneeppp2121例2．26=23，20=225，100=2252有了算术基本定理后，就可以把任意整数分解为标准形式，从而可以方便地求出两个整数的最大公因数和最小公倍数。设a，b是两个整整数，且有标准分解形式：a=，b=，ei，fiNneneeppp2121nfnffppp2121则gcd(a，b)=lcd(a，b)=其中，min{x,y}表示x，y中最小者，max{x，y}表示x，y中最大者。),min{1iifeinip),max{1iifeinip2．Euclid算法利用算术基本定理，原则上可以求得任何两个整数的最大公因数，但当两个整数比较大时求他们的标准分解式就非常困难，目前还没有有效的算法，因此求他们的最大公因数也变得非常困难。Euclid算法从另一方面解决了求两个整数的最大公因数的问题。Euclid算法由称为辗转相除法，即带余数除法，有下列不等式：a=bq1+r10r1bb=r1q2+r20r2r1rn-2=rn-1qn+rn0rnrn-1rn-1=rnqn+1+rn+1rn+1=0因为每进行一次带余数的除法，余数至少减1，而b是有限的。所以，最多进行b次带余数的除法，总可以得到一个余数是0的等式，即最后一个等式，而最后一个不为0的余数rn就是我们要求的最大公因数gcd(a，b)。从上面的Euclid算法中可以看出，将r1=a–bq1代入第二个等式中，，将r2=b–r1q2代入到第三个等式中，…，将rn-1=rn-3–rn-2qn-1代入倒数第二个等式中，就可得到rn关于a,b的一个表示式，其中a,b的系数分别就是定理2.1.2中的u,v。故最后一个不为零的余数就是a、b的最大公因数。例2．3求gcd{1694,917}1694=1917+777917=1777+140777=5140+77140=177+6377=163+1463=414+714=27+0所以gcd(1694，917)=7进行回代7=63-414=63-4（77-63）=-477+563=-477+5（140-77）=5140-977=5140-9（777-5140）=-9777+50140=-9777+50（917-777）=50917-59777=50917-59（1694-917）-591694+109917即7=u1694+v917其中u=-59，v=1093.同余定义2.1.3假设a和b是两个整数，m是一个正整数，如果mba，则称a和b对模m同余。记作a≡b(modm)。例2．43和1对模2同余，4和1对模3同余，即3≡1（mod2），4≡1（mod3）定理2.1.4同余的性质设a，b，c和m是整数，则有：i.a≡a（modm）ii.若a≡b（modm），则b≡a（modm）ⅲ.若a≡b（modm），b≡c（modm），则a≡c（modm）假设a和b被m除，获得整数商和余数，这个余数在0和m-1之间，即a=q1m+r1和b=q2m+r2，0≤r1≤m-1，0≤r2≤m-1。不难看出，a≡b（modm），当且仅当r1=r2。我们使用符号a（modm）来表示a被m除时的余数，即上面的r1，这样a≡b（modm），当且仅当a（modm）≡b（modm）。如果我们用a（modm）来代替a，我们说a是被模m约简的。现在我们能够定义模m的算术：Zm是一个集合{0，1，。。。，m-1}，它有两种运算+和。在Zm中的加法和乘法，除了将结果被模m约减外，恰好象实数加法和乘法。例2．5在Z2种作加法0+0≡0（mod2）,0+1≡1(mod2),1+0≡1(mod2),1+1≡0(mod2)一般地，在Z2种的加法称为模2加，有时也称为比特异或，用记号表示。00=0，01=1，10=1，11=1例2．5在Z16作乘法11131113=143=816+15所以，1113(mod16)=15定义2.1.4Euler函数是定义在整数上的函数，它在正整数m的值等于1，2，……，m-1中与m互素的数的个数，记作（m）。例2．6m=6,{1,2,3,4,5}中与6互素的数为{1，5}，共有两个，所以，（m）=（6）=2定理2.1.5设正整数的标准分解形式为m=，则（m）=m（1-1/p1）（1-1/p2）…（1-1/pn）例2．7m=6，其标准分解形式为6=23所以，（6）=6（1-1/2）（1-1/3）=2neneeppp2121定理2.1.6（Euler定理）若a和m互素，则a(m)≡1(modm)推论（fermat定理）若p是素数，则ap≡a(modp)设f(x)表示多项式：anxn+an-1xn-1+…+a0,其中an≠0，ai∈N(i=1,2,…,n)。设n是一个正整数，则f(x)=0(modm)称作模m的同余式，n称作同余式的次数，n=1称为一次同余式，n=2称为二次同余式。若a是使f(a)≡0(modm)成立的一个整数，则x≡a(modm)叫做同余式的一个解。定理2.1.7（中国剩余定理）设m1，m2，…mk，是k个两两互素的整数，m=m1m1…mk，Mi=m/mi，i=1,2,…k。则同余方程组x≡b1(modm1),x≡b2(modm2),…,x≡bk(modmk)有解x=(M’1M1b1+M’2M2b2+…M’kMkbk)(modmk)其中M’iMi≡1(modmi),i=1,2,…,k由此定理可以看出，M’i可以利用前面介绍的Euclid算法求出。4）二次剩余设gcd(a,m)=1，若同余式x2≡a(modm)有解，则a称作模m的二次剩余，否则称作模m的非二次剩余。例2．9考虑下列同余式x2≡1(mod5)，x2≡2(mod5)，x2≡3(mod5)，x2≡4(mod5)不难发现：x=1,x=4满足x2≡1(mod5)x=2,x=3满足x2≡4(mod5)不存在整数x满足x2≡2(mod5)，x2≡3(mod5)所以1，4是模5的二次剩余，而2，3是模5的非二次剩余。定理2.1.8若gcd(a,p)=1，则a是模p的二次剩余的充要条件为ap-1/2≡1(modp)a是模p的非二次剩余的充要条件为ap-1/2≡-1(modp)定理2.1.9两个模p的二次剩余的乘积或两个模p的非二次剩余的乘积，还是模p的二次剩余，一个模p的二次剩余与另一个模p的非二次剩余的乘积是非二次剩余。定义2.1.5Legendre符号（）是一个对于给定素数p定义在一切整数a上的函数，它的值规定如下：appapapa的非二次剩余是模的二次剩余是模011例2．10，，1545115352055定理2.1.10legendre符号的性质a)b)如果ab(modp)，则c)d)e)设p，q均为奇素数，p≠q，则112pqppbpapa)(mod2/)1(pappbpapab4/)1)(1(1qpqppq定义2.1.6设m=ei≥0是一个奇正整数，u是与m互素的整数，则Jacobi符号定义为（u/m）=其中（）是Legendre符号。定理2.1.11Jacobi符号的性质1）（u/m）=((u-m)/m)2)(uv/m)=(u/m)(v/m)3)(u/mn)=(u/n)(u/m)4)(-1/m)=1当且仅当m=1(mod4)5)(2/m)=1当且仅当m=+1，-1(mod8)6)设m，n都是奇数，且gcd(m,n)=1则=（-1）(m-1)(n-1)/4ieniipu12．2信息论基础Shannon信息论是密码学的理论基础，本节介绍Shannon信息论的基本概念，与密码学有关的概念将在后面介绍。1．熵的概念熵是信息的测度或不确定性，它是作为概率分布的一个函数来计算的。假设又一个随机变量x，它根据概率分布p(x)在一个有限集合上取值。根据分布p(x)发生的事件来获得的信息是什么？等价地，如果一个事件还没有发生，有关这个结果的不确定性是多少？这个量称为x的熵并用H(x)表示。定义2.2.1离散随机变量x的熵H(x)定义为H(x)=-P(x)Log2P(x)其中，P(x)表示随机变量x的概率分布。例2．11设离散随机变量x取{0，1}两个值，其中P(x=0)=P(x=1)=1/2，则H(x)=-1P(x=0)Log2P(x=0)-P(x=1)Log2P(x=1)=-1/2(-1)–1/2(-1)=1下面我们来定义联合熵和条件熵。定义2.2.2两个离散随机变量（x,y）的联合熵定义为H(xy)=-1P(xy)Log2P(xy)其中，P(xy)表示离散随机变量(x，y)的联合概率分布。类似地，可以定义n个离散随机变量(x1，x2，…xn，)的联合熵。定义2.2.3两个离散随机变量(x，y)的条件熵定义为H(x∣y)=-P(xy)Log2P(x∣y)其中，P(xy)表示离散随机变量（x，y）的联合概率分布，P(x∣y)表示两离散随机变量的条件分布。利用联合熵与条件熵的定义，容易证明定理2.2.1H(xy)=H(x)+H(y∣x)2．互信息互信息是一个事件含有另一个事件的信息的度量；或者是已知另外一个事件（称作B）的情况下，事件（称作A）不确定性的减少。定义2.2.4两个离散随机变量x和y，它具有概率分布P(x)和P(y)和联合概率分布密度P(xy)，则互信息定义为I(x；y)=从互信息的定义可以看出，如果随机变量x和y统计独立，即y中不含x的任何信息，则I(x；y)=0。互信息具有对称性，这就是定理2.2.2I(x；y)=H(x)-H(y∣x)=H(y)-H(x∣y)=I(y；x)XxYy)()()(log)(2ypxpxypxyp2．33计算复杂度简介计算复杂度理论是计算机科学理论的一个分支，它