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

1、第二章预备知识，21数论基础数论是古老数学的分支。 一直以来被认为是完全纯粹的数学，但在现实生活中很难找到实际的应用。 自从公钥体制在一九七九年诞生以来，现代的密码学与数学理论有着无数的关系。 因此，首先简单介绍数学论的基本概念。 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=23，6是整数，26，2是第六系数，6是第二倍数。 7=17，除了1和7没有其他系数，因此7是素数。 定理2.1.1 (带馀数除法)为a，b为2个整数，这里设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 )。 如果对于lcm (a，b )

3、gcd (a，b )=ab个整数a，b，gcd (a，b )=1，那么a和b的最大公因子和最小公倍数被认为是素数。 假定定理2.1.2和b N，存在两个整数u和v，使得在ua vb=gcd (a，b )定理2.1.3 (算术基本定理)中的任何一个的正整数m中都存在唯一的因数分解形式m=。 eiN和pi的质数是p1p2p n。 这种分解形式也被称为m的标准分解形式。 当存在示例22=23，20=225，100=2252算术基本定理时，任何整数能够被分解为标准形式并且能够容易地确定两个整数的最大公倍数和最小公倍数。 其中，min x、y表示x、y中的最小；并且max、y表示x、y中的最大。 另外，

4、虽然2Euclid算法能够利用算术基本定理求出原则上任意两个整数的最大公倍数，但是在两个整数大的情况下，求出其标准分解式非常困难，因为当前没有有效的算法，所以也很难求出其最大公倍数。 Euclid算法单方面解决了求两个整数的最大公系数的问题。 Euclid算法被称为反相除法或馀数除法，其中，a=bq1r 10 r1b=r1q2r0r2r1rn-2=rn-1 q rn0rn-1=rn-1 rn1=0，每当进行馀数除法时馀数至少减少1，并且b是有限的。 从而，若进行最大b次频带的馀数的除法，则得到总是一个馀数为0的方程式，即最后的方程式，最后不为0的馀数rn是我们所要求的最大的公共系数gcd(a，

5、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的最大公系数。 例23gcd1694， 9171694=19177917=177140777=51515353525352535253535353535353535353535353535353535353535353535353535353535 35353535353535353535353535353535353

6、执行世代更迭定7=63-414=63-4 (77-63 )=-477=-4775 (140-77 )=5140-9775=5140-9 (777-5140 )=- 其中，u=-59、v=109、3 .联合定义假设a和b是两个整数，m是正整数。 就m b a而言，a和b是m合并的。标记为ab (模型m )。 例24和一对模型2的合并，4和一对模型3的合并，即，将3 1(mod 2)、41(mod 3)定理2.1.4的合并的性质设为a、b、c和m为整数时，如果是i.a(modm)ii.a b(mod m )，则为b(modm )，如果是a b(mod m )，则为b(modm )。 如果是b(mo

7、dm )，则b(modm )的a c(mod m )假定a和b被m除以获得整数商和馀数，并且在0和m-1之间，也就是说，a=q1m r1和b=q2mrr 2，0 r1m 1，0 r2m 1。 可以看出，a b(mod m )只是r1=r2。 我们使用符号a(mod m )表明，当a被m除时，馀数，即，上述r1，如此是a(mod m )，并且只有a(mod m )b(mod m )。 如果我们用a(mod m )代替a，我们就说a已经约定了模型m。 现在，Zm是集合0，1，可以定义模型m的算术。 的双曲正切值。 的双曲正切值。 有m-1、2种运算和。 Zm中的加法和乘法除了用模型m来近似结果以外

8、，正好类似于实数加法和乘法。 例如25Z2种中的加法器0 00(mod 2)、0 11(mod 2)、1 01(mod 2)、1 10(mod 2)一般被称为模式2加法器，有时也被称为二进制位异或，并且用符号来指示。 因为0=0，0=1，1=1，1=0，并且25z16中的乘法器1113=143=816，所以如在1113(mod16)=15中所定义的2.1.4欧拉函数是在整数中定义的函数，其中，正整数m的值为1，2， m-1，并且m和像素的数量为整数例26m=6，1，2，3，4，5中6和素数为1， 因为有两个，所以(m)=(6)=2定理2.1.5如果将正整数的标准分解形式设为m=，则由于(m)=

9、m(1-1/p1)(1-1/p2)(1-1/pn )例27 m=6，其标准分解形式为6=23，所以(6)=6(1-1/2) (1-1) 如果a和m是元素，则a(m) 1(mod m )可以采用f(x )作为多项式： anxn an-1xn-1 a0，其中an 0和ain (I=1，2，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个二

10、元素的整数，并且m=m1m1mk、Mi=m/mi、I=1、2和k。 根据原则联合方程式x b 1、x b 2、x bk在解x=(mim m1m1b2m2m k MK bk ) (modm )中的Mimi 1、I=1、2、 k的定理，mi在之前介绍的Euclid算法中4 )二次馀数设定gcd(a，m)=1，如果对等式x2a(mod m )存在解，则a被称为模块m的二次馀数，否则被称为模块m的非二次馀数。 例如，考虑到以下等式x=1 (模式5 )、x 22 (模式5 )、x=3 (模式5 )和x=4 (模式5 )，x=1，x=4是x=1 (模式5 ) x=2，x=3是满足x=4 (模式5 )的整数

11、x是x2(模式5 )和x=3 (模式5 ) 如果定理2.1.8gcd(a，p)=1，则a是模型p的二次馀数的充分条件，而ap-1/21(mod p) a是模型p的非二次馀数的充分条件，则是ap-1/2-1(mod p )，定理2.1.9两个模型p的二次馀数的乘积或两个模型定义一个模型p的二次馀数和另一个模型p的非二次馀数的2.1.5 Legendre符号()是对于给定的素数p在所有整数a中定义的函数，其值如下规定： 定理2.1.10 legendre符号的性质a)b)ab(modp )，c) d) e，q都是奇数素数，pq，定义2.1.6m=ei0为奇数的正整数，u为m和素的整数，则雅可比符号

12、为(u/m)=此处定理2.1.11雅可比编码的性质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)(m-1)(n-1)/4，22信息论的基础假定Shannon信息论是密码学的理论基础，在本节中介绍Shannon信息论的基本概念，关于密码学的概念后述。 1熵的概念熵是信息的测度或不确定性，作为概率分布的函数来计算。 根据概率分布p(x )，假定有按有限集合取值的随机变量x。 从分布p(x )发生的上通告得到的情报是什么一样

13、，如果事件还没有发生，关于其结果的不真实自我是多少？这个量叫x的熵，用H(x )表示。 定义2.2.1离散随机变量x的熵H(x )定义为H(x)=-P(x) Log2P(x )。 在此，P(x )表示随机变量x的概率分布。 例如，假设离散关随机变量字x为0和1这两个值，其中P(x=0)=P(x=1)=1/2，h (x )=-1 p (x=0)-p (x=1)-log2p (x=1)=-1/2 (-1 )=1，并且连通性被设置为定义2.2.2个离散随机变量(x，y )的联合熵被定义为H(xy)=-1P(xy) Log2P(xy )。 在此，P(xy )表示离散随机变量(x，y )的联合概率分布。

14、 同样，可以定义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 )的不真实自我减少。 如定义了具有概率分布P(x )、P(y )和联合概率分布密度P(xy )的2.2.4个离散随机变量x和y，则相互信息可

15、以是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的计算复杂度曲线计算复杂度理论是计算机科学技术理论的分支点，提供了分析不同密码术和算法秘密强度的方法。 比较密码算法和技术，决定保密工作。 现代密码学的很多理论和技术基于某种计算问题的复杂性。 1算法的复杂度算法的计算复杂度用符号“o”表示，计算复杂度的几级是这种类型的函数，n越大则是增长最快的函数(n是输入尺寸)，所有的常数和下

16、位形式的函数都被忽略。 举例来说，如果给定算法的复杂度为5n28到n10，则其计算的复杂度被表示为O (n2 )。 通常，将算法按其上通告和空间的复杂度进行分类，在算法的复杂度不依赖于n :O (1)时为“常数级”。 如果复杂性随着n线性增加，那么它是“线性的”。 随on而增加的其他算法也被称为“平方”“三次方”等。 这些个的算法都是“多项式”，他们的复杂度是O (nt )，其中t是常数。 具有多项式时间复杂度的算法簇称为多项式时间算法。 复杂度在O (tf (n ) )的算法中被称为“指数”，其中t是常数，f(n )是n的多项式函数。 2问题的分类复杂性理论根据解决问题的算法来分类问题。 在多项式时间算法中容易解决的问题这一多项式时间内不能解决的问题称为难