《计算机网络安全技术第二章.ppt》由会员分享，可在线阅读，更多相关《计算机网络安全技术第二章.ppt（27页珍藏版）》请在三一办公上搜索。
1、第二章 预备知识,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
2、没有任何其他因数。不是素数的整数称为合数。例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的最大公因数与最大公倍数
3、满足下列等式：lcm(a,b)gcd(a,b)=ab如果对两个整数a,b有gcd(a,b)=1，则称a与b互素。定理 设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)
4、=其中，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因为每进行一次带余数的除法，余数至少减
5、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的系数分别就是定理中的u,v。故最后一个不为零的余数就是a、b的最大公因数。例23 求gcd 1694,917 1694=1917+777 917=1777+140 777=5140+77 140=177+63 7
6、7=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同
7、余，4和1对模3同余，即3 1（mod 2），41（mod 3）定理 同余的性质 设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
8、）来代替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作乘法11131113=143=816+15所以，1113(mod16)=15定义2.1.4 Euler函数是定义在整数上的函数，它在正整数m的值等于1，2，m-1中
9、与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,定理（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)称作模
10、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，若
11、同余式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的二次剩余的乘积
12、或两个模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，则,定义 设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
13、)=(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的熵
14、并用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，)的联合熵
15、。,定义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中
16、不含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+1
17、0，那么，其计算复杂性表示为O(n2)。通常，算法按其事件和空间的复杂性进行分类，如果一个算法的复杂性是不依赖于n：O(1)，那么，它是“常数级的”。如果它的复杂性是随n线性增长的，那么它是“线性的”。O随n增长的其他一些算法也称为“二次方的”，“三次方的”，等等。所有这些算法都是“多项式的”，他们的复杂性是O(nt)，这里t是一个常数。有一个多项式的时间复杂性的算法簇称之为多项式时间算法。复杂性是O(tf(n)的算法，被称为是“指数的”，这里t是一个常数，f(n)是n的多项式函数。,2问题的分类复杂性理论按照解决问题的算法对问题进行分类。能够用多项式时间算法解决的问题称之为易解决的；不能在多
18、项式时间内解决的问题称之为难处理的，难处理的问题有时也称为难解决的。定义 P类问题：在多项式时间内可以解决的问题。NP类问题：多项式时间内可以验证的问题。由于在多项式时间内可以解决的问题，在多项时间内也完全可以验证其正确性，因此一般有P NP，但现在还不知道是否有“P=NP”成立。在NP问题中有些特殊的问题能够被证明与此类问题中的任何问题一样困难，这类问题称之为NP-完全类问题。有人已经编辑了一份NP-完全类问题的目录，下面将列出几个例子。,3几个例子 1）整数分解问题前面介绍了算术基本定理，根据这个定理，任何一个正整数都可以分解成标准形式 m=pi 是常数，ei N当m较小时，这个问题不太困
19、难，例如6=23，100=2252但当m较大时，这个问题就变得非常困难了，例如你能立即指出整数8616460789的标准分解形式吗？特别是当m达到几百位时，根据现有的算法用最快的计算机也不行。但反过来，如果给出一个整数的标准分解时，则可以很快验证这个标准分解式是否是这个整数的标准分解式了。例212 861646079的标准分解式为 861646079=89681 96079我们能立即验证这个分解式的正确性。,2）背包问题背包问题是这样一个问题：已知长度为k的圆形背包及长度分别为a1，a2，an的n个圆形物品。假定这些物品的半径和背包的半径相同，要求从n个物品中选出若干个正好装满这个背包。把背包
20、问题抽象成数学模型，称为子集合问题：设有长度为n的向量A=(a1，a2，an)，若一给定一个整数k，寻找有没有一些ai的和恰好等于k，即求方程=k的解向量x=(x1，x2，xn)，其中xi=0或1。当背包向量A的长度较小是，可以用穷举搜索发求得解向量x=(x1，x2，xn)；但当n比较大时，比如说200，那么用穷举法就不可行了。反过来，如果给定一个向量x=(x1，x2，xn)，可以很容易的验证它是不是背包问题的解，因此背包问题是NP类问题，计算机理论科学已经证明，背包问题是NP-完全问题。,例213 长度为10的背包向量 A=43，129，215，473，903，302，561，1165，67
21、9，1523给定整数k=3231，要求=3231向量解x，需穷举搜索。反过来，如果给定向量x=0，1，0，1，1，0，1，1，0，0，我们可以很容易证明129+473+903+561+1165=3231因此，给定的向量是这个背包问题的解向量。,3）离散对数问题设x，r，n是正整数。已知x，r和n，可以很快地求得 y xr(mod n)反过来，如果已知y，x和n，求r使得 y xr(mod n)成立，这便是离散对数问题。当x，r和n都比较小时，可以用穷举法搜索求得r，如果这些数都比较大时，这就非常困难了。给定一个整数r，那么可以很容易验证它是否为 y xr(mod n)的解。因此离散对数问题是NP类问题。计算机理论科学已经证明，离散对数问题是NP-完全问题。,
