网络信息安全第四章课件.ppt-淘文阁

资源描述

《网络信息安全第四章课件.ppt》由会员分享，可在线阅读，更多相关《网络信息安全第四章课件.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、网络信息安全课件第四章2022/10/101第1页，此课件共53页哦本章要点l域是一些元素的集合，其上定义了两个算术运算(加法和乘法)，具有常规算术性质，如封闭性、结合律、交换律、分配律、加法逆和乘法逆等。l模算术是一种整数算术，它将所有整数约减为一个固定的集合0,1,n-1，n为某个整数。任何这个集合外的整数通过除以n取余的方式约减到这个范围内。l两个整数的最大公因子是可以整除这两个整数的最大正整数。l一个有限域就是有有限个元素的域。可以证明有限域的阶(元素个数)一定可以写作素数的幂形式pn，n为一个整数，p为素数。l阶为p的有限域可以由模p的算术来定义。l阶为pn，n1的有限域可由多项式算

2、术来定义。2022/10/102第2页，此课件共53页哦4.1群,环和域Groups,Rings,and Fieldsl群G,记作G,定义一个二元运算的集合，G中每一个序偶(a,b)通过运算生成G中元素(ab)，满足下列公理：l(A1)封闭性Closure:如果a和b都属于G,则ab也属于G.l(A2)结合律Associative:对于G中任意元素a,b,c，都有a(bc)=(ab)c成立l(A3)单位元Identity element:G中存在一个元素e，对于G中任意元素a，都有ae=ea=a成立l(A4)逆元Inverse element:对于G中任意元素a,G中都存在一个元素a，使得aa

3、=aa=e成立2022/10/103第3页，此课件共53页哦群、有限群和无限群l用Nn表示n个不同符号的集合，1,2,n.n个不同符号的一个置换是一个Nn到Nn的一一映射。定义Sn为n个不同符号的所有置换组成的集合。Sn中的每一个元素都代表集合1,2,n的一个置换，容易验证Sn是一个群：lA1：如果,Sn，则合成映射根据置换来改变中元素的次序而形成，如，3,2,11,3,2=2,3,1,显然 SnlA2：映射的合成显而易见满足结合律lA3：恒等映射就是不改变n个元素位置的置换，对于Sn，单位元是1,2,nlA4：对于任意Sn，抵消由定义置换的映射就是的逆元，这个逆元总是存在，例如：2,3,13

4、,1,2=1,2,3,l有限群Finite Group和无限群Infinite Group：如果一个群的元素是有限的，则该群称为有限群，且群的阶等于群中元素的个数；否则称为无限群2022/10/104第4页，此课件共53页哦交换群和循环群l交换群Abelian Group：还满足以下条件的群称为交换群(又称阿贝尔群)l(A5)交换律Commutative：对于G中任意的元素a,b，都有ab=ba成立l当群中的运算符是加法时，其单位元是0；a的逆元是-a,并且减法用以下的规则定义：a b=a+(-b)l循环群Cyclic Groupl如果群中的每一个元素都是一个固定的元素a(a G)的幂ak(k

5、为整数)，则称群G为循环群。元素a生成了群G，或者说a是群G的生成元。2022/10/105第5页，此课件共53页哦环(Rings)l环R,由R,+,x表示,是具有加法和乘法两个二元运算的元素的集合，对于环中的所有a,b,c,都服从以下公理：l(A1-A5),单位元是0，a的逆是-a.l(M1),乘法封闭性,如果a和b属于R,则ab也属于Rl(M2),乘法结合律,对于R中任意a,b,c有a(bc)=(ab)c.l(M3),乘法分配律,a(b+c)=ab+ac or(a+b)c=ac+bcl(M4),乘法交换律,ab=ba，交换环 l(M5),乘法单位元,R中存在元素1使得所有a有 a1=1a.

6、l(M6),无零因子,如果R中有a,b且ab=0,则 a=0 or b=0.满足M4的是交换环；满足M5和M6的交换环是整环2022/10/106第6页，此课件共53页哦域(Fields)l域F,可以记为F,+,x,是有加法和乘法的两个二元运算的元素的集合，对于F中的任意元素a,b,c,满足以下公理：l(A1-M6),F是一个整环l(M7),乘法逆元,对于F中的任意元素a(除0以外),F中都存在一个元素a-1,使得aa-1=(a-1)a=1.l域就是一个集合，在其上进行加减乘除而不脱离该集合,除法按以下规则定义:a/b=a(b-1).l有理数集合,实数集合和复数集合都是域；整数集合不是域，因为

8、有cd，而d是a和b的最大公因子。因此d=gcd(b,r1)。4.3欧几里得算法Euclid Algorithm2022/10/1019第19页，此课件共53页哦a=q1b+r1 0r1r1，可以用r1除b，应用除法有b=q2r1+r2 0r2r1如前所述，如果r2=0，则d=r1.如果r20，则d=gcd(r1,r2)。继续除法过程直到余数为0，比如说在第(n+1)阶段有rn整除r(n-1)。结果为如下的方程系统：4.3欧几里得算法Euclid Algorithm2022/10/1020第20页，此课件共53页哦使d等于gcd(a,b),根据gcd的定义，有d|a和d|b成立。对于任意正整数

10、066+904 gcd(1066,904)1066=1 x 904+162 gcd(904,162)904=5 x 162+94 gcd(162,94)162=1 x 94+68 gcd(94,68)94=1 x 68+26 gcd(68,26)68=2 x 26+16 gcd(26,16)26=1 x 16+10 gcd(16,10)16=1 x 10+6 gcd(10,6)10=1 x 6+4 gcd(6,4)6=1 x 4+2 gcd(4,2)4=2 x 2+0 gcd(2,0)Gcd(1970,1066)=22022/10/1022第22页，此课件共53页哦对于给定的整数a和b，扩展的

11、Euclid算法不仅计算出最大公因子d，而且还有另外的整数x和y，它们满足如下方程：ax+by=d=gcd(a,b)用扩展的Euclid算法计算(x,y,d).假设在每一步骤i都可以找到xi和yi满足ri=axi+byi。4.3扩展的Euclid算法2022/10/1023第23页，此课件共53页哦从原始的Euclid算法知该过程当余数为0时结束，求得a和b的最大公因子为d=gcd(a,b)=rn.我们也决定了4.3扩展的Euclid算法2022/10/1024第24页，此课件共53页哦4.4 有限域GF(p)Galois Fieldsl有限域在密码学中扮演重要角色l有限域的阶(元素个数)必须

12、是一个素数的幂pn,n 为正整数。元素个数是pn的有限域一般记为GF(pn)，即Galois fields,模pn.l关注两种特殊情形，n=1时的有限域和p为2时的有限域，即GF(p)和GF(2n)l最简单的有限域是GF(2)，它的代数运算简述如下：+0 1 x 0 1 w -w w-10 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 1 加乘求逆2022/10/1025第25页，此课件共53页哦Galois Fields GF(p)l阶为p的有限域GF(p)l给定一个素数p，元素个数为p的有限域GF(p)被定义为整数0,1,p-1的集合Zp，其运算为模p的算术运算lZn中的

13、任一整数有乘法逆元当且仅当该整数与n互素，若n为素数，Zn中的所有非零整数都与n互素，因此Zn中所有非零整数都有乘法逆元l对每一个wZp，存在一个z，使得wz1 mod p，则z即为乘法逆元w-1l因为w与p互素，如果用w乘以Zp中的所有数模p，得到的余数将以不同次序涵盖Zp中的所有数，即余数集合是0,1,p-1的置换形，那么至少有一个余数的值为1。因此，在Zp中的某个数与w相乘模p的余数为1,这个数就是w的乘法逆元，w-1。所以，Zp是一个有限域。2022/10/1026第26页，此课件共53页哦2022/10/1027第27页，此课件共53页哦l计算乘法逆元素 Computing mult

14、iplicative inverses ax mod n=1,x=a-1=?给定a0,n-1,gcd(a,n)=1，若能找到唯一整数 x0,n-1，满足：ax mod n=1,则称a和x互逆如 n=10,a=3,x=7,ax mod n=1=3x7 mod 10 n=17,a=5,x=7,ax mod n=1=5x7 mod 17引理4.1:如果gcd(a,n)=1,则对于每个i,j,0ijn,ai mod naj mod n 证明：(略)可以用反证法证明此性质意味着每一个ai mod n(i=0,n-1)都是不同的模n剩余，而 ai mod n i=0,1,n-1是完全剩余集0,1,n-1

15、的置换形式计算乘法逆元素2022/10/1028第28页，此课件共53页哦例如:n=5,a=3,gcd(3,5)=1,0,1,n-1=0,1,2,3,4 3*0 mod 5=0 3*1 mod 5=3 3*2 mod 5=1 3*3 mod 5=4 3*4 mod 5=2 ai mod ni=0,1,n-1=0,3,1,4,2引理4.1说明，当gcd(a,n)=1时，a一定有一个唯一的逆元素。定理4.1 如果gcd(a,n)=1,一定存在整数x,0 xn，满足ax mod n=1可以用Euclids计算最大公约数算法的扩展来求逆。计算乘法逆元素2022/10/1029第29页，此课件共53页哦

16、如果a和b互素，则b有模a的乘法逆元。也就是说，如果gcd(a,b)=1,那么b有模a的乘法逆元。即对于正整数ba,存在b-1a使bb-1=1mod a.如果a是素数并且b=0)的表达形式如下l其中ai是某个指定数集S中的元素，该数集称为系数集，且an0，f(x)是定义在系数集S上的多项式l零次多项式称为常数多项式，是系数集里的一个元素，如果an=1，对应的n次多项式就称为首1多项式2022/10/1031第31页，此课件共53页哦普通多项式运算l加或减就是相应系数的加减，乘则要用到所有系数lEx.let f(x)=x3+x2+2 and g(x)=x2 x+1f(x)+g(x)=x3+2x2

17、 x+3f(x)g(x)=x3+x+1f(x)x g(x)=x5+3x2 2x+2f(x)/g(x)=x+2,x2022/10/1032第32页，此课件共53页哦2022/10/1033第33页，此课件共53页哦系数在 Zp中的多项式运算l在计算每个系数的值时需要做模运算l可以模任何素数p，但是我们更感兴趣的是模2的运算l也就是说所有的系数不是0就是1l比如，令 f(x)=x3+x2,g(x)=x2+x+1 则 f(x)+g(x)=x3+x+1 f(x)x g(x)=x5+x22022/10/1034第34页，此课件共53页哦2022/10/1035第35页，此课件共53页哦多项式的模运算l多

18、项式可以写成如下形式:lf(x)=q(x)g(x)+r(x)l其中，r(x)就可被看作是余数lr(x)=f(x)mod g(x)l如果没有余数，就称g(x)可以整除f(x)l如果g(x)除了1和它自身以外没有其他公因式，就称它是不可约多项式或素多项式irreducible or prime2022/10/1036第36页，此课件共53页哦求多项式的最大公因式l可以为多项式求解最大公因式l如果c(x)是可以整除a(x)和b(x)最大公因式，则c(x)=GCD(a(x),b(x)l可以用Euclids Algorithm 来求解多项式最大公因式:gcda(x),b(x)=gcdb(x),a(x)m

19、od b(x)=gcdr1(x),b(x)mod r1(x)=gcdr2(x),r1(x)mod r2(x)2022/10/1037第37页，此课件共53页哦求多项式的最大公因式2022/10/1038第38页，此课件共53页哦求多项式的最大公因式2022/10/1039第39页，此课件共53页哦求多项式的最大公因式2022/10/1040第40页，此课件共53页哦4.6 有限域GF(2n)l所有加密算法都涉及到整数集上的算术运算，如果用到除法，必须使用定义在域上的运算。l整数集里的数与给定的二进制位数所能表达的信息一一对应，即整数集的范围从0到2n-1，正好对应一个n位的字。l将一个整数集不

20、平均地映射到自身的算法用于加密时可能要弱于一个提供一一映射的算法，因此，有限域GF(2n)对加密算法是很有吸引力的。所以要寻找一个包含2n个元素的集合，其上定义了加法和乘法使之成为一个域，给集合的每个元素赋值为0到2n-1之间的唯一整数，用多项式算术来构造所需的域。l可以使用扩展的欧几里德算法来为集合中的元素找到逆元。2022/10/1041第41页，此课件共53页哦2022/10/1042第42页，此课件共53页哦多项式模运算l设集合S由域Zp上次数小于等于n-1的所有多项式组成，每个多项式具有如下形式：l其中，ai在集合0,1,p-1上取值，S共有pn个不同的多项式l当p=3,n=2时，集

21、合中共有32=9个多项式，分别是 0 x2x 1x+12x+1 2x+22x+2l当p=2,n=3时，集合中共有23=8个多项式，分别是0 x+1x2+x 1x2x2+x+1 xx2+12022/10/1043第43页，此课件共53页哦多项式模运算l如果定义了合适的运算，那么每个这样的集合S都是一个有限域，定义由如下几条组成：l该运算遵循基本代数规则中的普通多项式运算规则l系数运算以p为模，即遵循有限域Zp上的运算规则l如果乘法运算的结果是次数大于n-1的多项式，那么必须将其除以某个次数为n的既约多项式m(x)并取余式。对于多项式f(x)，这个余数可表示为r(x)=f(x)mod m(x)l和

22、简单模运算类似，多项式模运算也有剩余类集合的概念。设m(x)为n次多项式，则模m(x)剩余类集合有pn个元素，每个元素都可以表示成一个m次多项式(mn)以m(x)为模的剩余类x+1由所有满足a(x)(x+1)(mod(x)的多项式a(x)组成。也就是说，剩余类x+1中的所有多项式a(x)满足等式a(x)mod m(x)=x+1。2022/10/1044第44页，此课件共53页哦多项式模运算l以n次既约多项式m(x)为模的所有多项式组成的集合满足图4.1的所有公理，于是可以形成一个有限域。l为构造有限域GF(23)，需要选择一个3次既约多项式：x3+x2+1或x3+x+1,选择后者则结果如表4.

23、6所示。2022/10/1045第45页，此课件共53页哦l加法运算，例如 100+010=110，这等价于 x2+x。2022/10/1046第46页，此课件共53页哦多项式模运算对于乘法运算，例如：100 010=011，这等价于x2 x=x3，约减后为x+1。2022/10/1047第47页，此课件共53页哦求乘法逆元l扩展的欧几里德算法可以用来求一个多项式的乘法逆元。如果多项式b(x)的次数小于m(x)且gcdm(x),b(x)=1，那么可以求出b(x)以m(x)为模的乘法逆元。扩展的EUCLIDm(x),b(x)1.A1(x),A2(x),A3(x)1,0,m(x);B1(x),B2

24、(x),B3(x)1,0,b(x)2.if B3(x)=0 return A3(x)=gcdm(x),b(x);no inverse3.if B3(x)=1 return B3(x)=gcdm(x),b(x);B2(x)=b(x)-1 mod m(x)4.Q(x)=quotient of A3(x)/B3(x)5.T1(x),T2(x),T3(x)A1(x),A2(x)-Q(x)B1(x),A2(x)-Q(x)B2(x),A3(x)-Q(x)B3(x)6.A1(x),A2(x),A3(x)B1(x),B2(x),B3(x)7.B1(x),B2(x),B3(x)T1(x),T2(x),T3(x)

25、8.goto 22022/10/1048第48页，此课件共53页哦Extended Euclid2022/10/1049第49页，此课件共53页哦计算上的考虑l因为系数不是0就是1,因此GF(2n)中的每个多项式都可以表示成一个n位的二进制整数l加法其实就是异或运算XOR,两个多项式加法等同于按位异或运算l乘法通过左移一位后按位异或来实现l模运算也是通过左移和异或来实现2022/10/1050第50页，此课件共53页哦Computing in Galois Fields Computing in Galois Fields 在伽罗瓦域中的计算（1）伽罗瓦域 GF(p)当模数是素数p，每个整数a

26、1,p-1与p互素，因而都有唯一的模p的逆。这一组模p的整数，加上算术运算，被称为有限域伽罗瓦域Galois Fields。（2）伽罗瓦域 GF(2n)多项式系数是二进制0和1，一个元素a可被表示成一个位矢量，长度为n,(an-1,a1,a0),每一个长度为n的可能的2n位的矢量都对应着GF(2n)中的不同元素。例如二进制数11001在GF(25)中可以记作x4+x3+1。2022/10/1051第51页，此课件共53页哦l在GF(2n)中的运算（模2运算是基础）加、减运算是异或，加无进位，减无借位，乘法运算是“与”，除法运算只要位数够长即可进行。例：计算d=a2，p(x)=x3x1，在GF(

27、23)中，a=101 aa=101101=10001 模p(x)：a2/p(x)=10001/1011=111，即d。例：a=111，b=100，p(x)=1011，计算d=ab，in GF(23).ab=111100=11100ab模p(x)：11100/1011=001即111100 mod 1011=001，在模1011时a与b互逆。l在GF(2n)中求逆，f(x)-1=f(x)2n-2 mod p(x)Computing in Galois Fields2022/10/1052第52页，此课件共53页哦使用生成元l定义有限域的另一种等价方式有时更方便，它使用相同的不可约多项式。l阶为q的有限域F的生成元是一个元素，记为g，该元素的前q-1个幂构成了F的所有非零元素，即域F的元素为0,g0,g1,gq-2.l考虑由多项式f(x)定义的域F，如果F内的一个元素b满足f(b)=0，则称b为多项式f(x)的根，可以证明一个不可约的多项式的根g是这个不可约多项式定义的有限域的生成元。2022/10/1053第53页，此课件共53页哦

展开阅读全文