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

第二章 预备知识,21 数论基础 数论是一门古老的数学分支。以前人们都认为它是完全纯粹的数学，在现实生活中很难找到它的实际应用。自从1976年公开密钥体制诞生以来，现代密码学就和数论有着千丝万缕的联系。因此，我们先简单介绍一下有关的数论基本概念。 1 引言 我们约定：字母N表示全体自然数集合，Z表示全体整数集合，即 N = 0,1,2, Z = ,-2,-1,0,1,2,定义2.1.1 如果存在一个整数kZ使得n = kd，则称d整除n，记作dn ，其中d称作n的因数，n称作d的倍数。如果不存在这样一个整数kZ使得n = kd，则称d不整除n，记作d + n 。 定义2.1.2 整数p（ 1）,称为素数，如果除了1和其本身外，p没有任何其他因数。不是素数的整数称为合数。 例21 6 = 23 ，6是合数，26 ，2是6的因数，6是2的倍数。7 = 17，除了1和7之外，没有其他因数，因此7是素数。 定理2.1.1 （带余数除法）设a，b是两个整数，其中b 0 。则存在两个整数q，r使得 a = bq + r 0 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 = 其中，eiN，pi是素数且p1p2p n。 这个分解形式也称为m的标准分解形式。,例22 6 =23， 20=225， 100 =2252 有了算术基本定理后，就可以把任意整数分解为标准形式，从而可以方便地求出两个整数的最大公因数和最小公倍数。设a，b是两个整整数，且有标准分解形式：,a = ， b = ， ei ，fiN,则 gcd (a，b) = lcd (a，b) = 其中，min x ,y 表示x，y中最小者，max x ，y 表示x，y中最大者。,2Euclid算法 利用算术基本定理，原则上可以求得任何两个整数的最大公因数，但当两个整数比较大时求他们的标准分解式就非常困难，目前还没有有效的算法，因此求他们的最大公因数也变得非常困难。Euclid算法从另一方面解决了求两个整数的最大公因数的问题。 Euclid算法由称为辗转相除法，即带余数除法，有下列不等式： a = bq1 + r1 0 r1 b b = r1q2 + r2 0 r2 r1 rn-2 = rn-1 q n+rn 0 rn rn-1 rn-1 = rnqn+1 +rn+1 rn+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的最大公因数。 例23 求gcd 1694,917 1694=1917+777 917=1777+140 777=5140+77 140=177+63 77=163+14 63=414+7 14=27+0 所以 gcd (1694，917) = 7,进行回代 7=63-414 =63-4（77-63） = -477+563 =-477+5（140-77） =5140-977 =5140-9（777-5140） =-9777+50140 =-9777+50（917-777） =50917-59777 =50917-59（1694-917） -591694+109917 即 7= u1694+v917 其中 u =-59， v = 109,3. 同余 定义2.1.3 假设a 和b是两个整数，m是一个正整数，如果m b a ，则称a 和b对模m同余。记作 a b (mod m )。 例24 3和1对模2同余，4和1对模3同余，即3 1（mod 2），41（mod 3） 定理2.1.4 同余的性质 设a，b，c和m是整数，则有： i. a a（mod m） ii. 若a b（mod m），则b a（mod m） . 若a b（mod m），b c（mod m）， 则a c（mod m）,假设a和b被m除，获得整数商和余数，这个余数在0和m-1之间，即a = q1m +r1和b = q2m +r2 ，0r1m-1 ，0r2m-1 。不难看出，a b（mod m），当且仅当r1 = r2 。我们使用符号a（mod m）来表示a 被m除时的余数，即上面的r1 ，这样a b（mod m），当且仅当a（mod m ）b（mod m）。如果我们用a（mod m）来代替a ，我们说a是被模m约简的。 现在我们能够定义模m的算术：Zm是一个集合0，1，。，m-1，它有两种运算+和 。在Zm中的加法和乘法，除了将结果被模m约减外，恰好象实数加法和乘法。 例 25 在Z2种作加法 0+00（mod 2 ）,0+11(mod 2 ) ,1+01(mod 2 ) , 1+10(mod 2 ) 一般地，在Z2种的加法称为模2加，有时也称为比特异或，用记号表示。 0 0 =0 ， 0 1 = 1 ， 1 0 = 1 ， 1 1 = 1,例25 在Z16作乘法1113 1113=143 =816+15 所以， 1113(mod16)=15 定义2.1.4 Euler函数是定义在整数上的函数，它在正整数m的值等于1，2， ，m-1中与m互素的数的个数，记作（m）。 例26 m = 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） 例27 m=6 ，其标准分解形式为 6 = 23 所以， （6）= 6（1-1/2）（1-1/3）=2,定理2.1.6（Euler定理） 若a和m互素，则 a(m) 1(mod m) 推论 （fermat定理）若p是素数，则 ap a (mod p) 设f(x)表示多项式：anxn + an-1xn-1 + +a0 ,其中an 0 ，aiN(i=1,2,n)。设n是一个正整数，则 f(x)= 0(mod m) 称作模m的同余式，n称作同余式的次数，n = 1称为一次同余式， n = 2称为二次同余式。 若a是使f(a)0(mod m)成立的一个整数，则x a (mod m) 叫做同余式的一个解。,定理2.1.7 （中国剩余定理） 设m1，m2，mk，是k个两两互素的整数，m= m1m1mk，Mi =m/mi ，i=1,2,k 。则同余方程组 x b1(mod m1) , x b2(mod m2) , x bk(mod mk) 有解 x =(M1M1b1+ M2M2b2+MkMkbk)(mod mk) 其中 MiMi 1(mod mi) ,i=1,2,k 由此定理可以看出，Mi可以利用前面介绍的Euclid算法求出。,4）二次剩余 设gcd(a,m)=1，若同余式x2a(mod m)有解，则a称作模m的二次剩余，否则称作模m的非二次剩余。 例29 考虑下列同余式 x21(mod 5)，x22(mod 5)，x23(mod 5)，x24(mod 5) 不难发现：x=1, x=4满足x21(mod 5) x=2, x=3满足x24(mod 5) 不存在整数x满足 x22(mod 5)，x23(mod 5) 所以1，4是模5的二次剩余，而2，3是模5的非二次剩余。 定理2.1.8 若gcd(a,p)=1，则a是模p的二次剩余的充要条件为 ap-1/21(mod p) a是模p的非二次剩余的充要条件为 ap-1/2-1(mod p),定理2.1.9 两个模p的二次剩余的乘积或两个模p的非二次剩余的乘积，还是模p的二次剩余，一个模p的二次剩余与另一个模p的非二次剩余的乘积是非二次剩余。 定义2.1.5 Legendre符号（）是一个对于给定素数p定义在一切整数a上的函数，它的值规定如下：,例210 ， ，,定理2.1.10 legendre符号的性质 a ) b ) 如果a b(mod p )，则 c) d) e) 设p，q均为奇素数，pq，则,定义2.1.6 设m = ei0是一个奇正整数，u是与m互素的整数，则Jacobi符号定义为 （u/m）= 其中（）是Legendre符号。 定理2.1.11 Jacobi符号的性质 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(mod 4) 5) (2/m) = 1 当且仅当m = +1，-1(mod 8) 6) 设m，n都是奇数，且gcd(m,n) = 1则=（-1）(m-1)(n-1)/4,22信息论基础 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的概率分布。,例211 设离散随机变量x取0，1两个值，其中P(x=0)=P(x=1)=1/2，则 H(x) = -1 P(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(xy) = - P(xy)Log2P(xy) 其中，P(xy)表示离散随机变量（x，y）的联合概率分布，P(xy)表示两离散随机变量的条件分布。 利用联合熵与条件熵的定义，容易证明 定理2.2.1 H(xy) = H(x) + H(yx) 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.2 I (x ；y) = H(x) - H(yx) = H(y) - H(xy) = I(y ；x),23 3 计算复杂度简介 计算复杂度理论是计算机科学理论的一个分支，它提供了一种分析不同密码技术和算法保密强度的方法。它对密码算法和技术进行比较，然后确定它们的安全性。现代密码学的许多理论和技术是建立在某些计算问题的复杂性基础之上的。,1算法复杂度 一个算法的计算复杂度用符号“O”来表示，计算复杂度的数量级是这种类型的函数，即当n变大时，增长最快的函数（n是输入尺寸），所有常数和较低阶形式的函数忽略不计。例如，一个所给的算法复杂度是5n2+8n+10 ，那么，其计算复杂性表示为O (n2)。 通常，算法按其事件和空间的复杂性进行分类，如果一个算法的复杂性是不依赖于n ：O (1) ，那么，它是“常数级的”。如果它的复杂性是随n线性增长的，那么它是“线性的”。O随n增长的其他一些算法也称为“二次方的”，“三次方的”，等等。所有这些算法都是“多项式的”，他们的复杂性是O (nt )，这里t是一个常数。有一个多项式的时间复杂性的算法簇称之为多项式时间算法。 复杂性是O (tf(n) 的算法，被称为是“指数的”，这里t是一个常数，f (n)是n的多项式函数。,2问题的分类 复杂性理论按照解决问题的算法对问题进行分类。能够用多项式时间算法解决的问题称之为易解决的；不能在多项式时间内解决的问题称之为难处理的，难处理的问题有时也称为难解决的。 定义2.3.1 P类问题：在多项式时间内可以解决的问题。 NP类问题：多项式时间内可以验证的问题。 由于在多项式时间内可以解决的问题，在多项时间内也完全可以验证其正确性，因此一般有P NP，但现在还不知道是否有“P = NP”成立。 在NP问题中有些特殊的问题能够被证明与此类问题中的任何问题一样困难，这类问题称之为NP-完全类问题。有人已经编辑了一份NP-完全类问题的目录，下面将列出几个例子。,3几个例子 1）整数分解问题 前面介绍了算术基本定理，根据这个定理，任何一个正整数都可以分解成标准形式 m = pi 是常数，ei N 当m较小时，这个问题不太困难，例如 6=23 ， 100=2252 但当m较大时，这个问题就变得非常困难了，例如你能立即指出整数8616460789的标准分解形式吗？特别是当m达到几百位时，根据现有的算法用最快的计算机也不行。但反过来，如果给出一个整数的标准分解时，则可以很快验证这个标准分解式是否是这个整数的标准分解式了。 例212 861646079的标准分解式为 861646079 = 89681 96079 我们能立即验证这个分解式的正确性。,2）背包问题 背包问题是这样一个问题：已知长度为k的圆形背包及长度分别为a1，a2，an的n个圆形物品。假定这些物品的半径和背包的半径相同，要求从n个物品中选出若干个正好装