信息安全数学基础 第二章 同余

巫玲Wuling751,第二章同余modulus,学习目标掌握同余、剩余类（系）、欧拉函数、费马定理、孙子定理了解同余理论和孙子定理在计算机和密码学的应用课程内容的设置同余的基本概念、性质和应用剩余类、完全剩余系、简化剩余系及应用欧拉函数、费马定理及应用孙子定理同余式,2.0问题的提出,50天后星期几？234567天后呢？计算机中的溢出问题循环队列的的实现？,数学中的同余整除中：a=qb+r0r=3,证明(2)模m的最小正简化剩余系的各数之和等于m(m)/2证明：若(m,a)=1,则(m,m-a)=1所以，设ai是在1m/2和m互素的整数所以，ai和m-ai组成了m的最小正简化剩余系共(m)/2对，和为m(m)/2思考：为什么没有考虑m/2,2.3剩余类（系）Residue,例：将1(mod5)写成模15的剩余类的和例：写出模9的完系，要求全是奇数对于10呢？作业(5):p58第9题,2.3剩余类（系）Residue,定理,(m,n)=1,(1)Ca,Cb为2个不同的剩余类nCa,nCb为2个不同的剩余类(2)为模m的一个完系为模m的一个完系为模m的一个缩系为模m的一个缩系(3)为模m的一个完系为模m的一个缩系(4)为模m的一个完系为模m的一个缩系(5)则x遍历m的一个完系，则nx+b也遍历如m=10,n=7,b=6,则13,20,27,34,41,48,55,62,69,76为一个完系,2.3剩余类（系）Residue,定理2-2有所以,2.3剩余类（系）Residue,定理2-3,2.3剩余类（系）Residue,2.3剩余类（系）Residue,2.3剩余类（系）Residue,定理2-4若（m,n）=1那么呢？,2.3剩余类（系）Residue,关键m=pn时，其缩系的元素？排除与其最大公约数大于1的,也就是该数为xp(0,m-1)中，非缩系元素最小为0,最大pn-p,x取值0到pn-11，共pn-1个所以，如=22-2=2,2.3剩余类（系）Residue,作业(6)：用上面的方法计算24的欧拉函数,定理2-5欧拉函数的计算p素,2.3剩余类（系）Residue,定理2-6设m是1,2,n中的任一数，可以按照(m,n)的不同对1,2,n分类,则n的正因子的个数即为类的个数（因为mn）,各类中正整数个数之和为n。设d为n的一个正因子，若(x,n)=d，则(x/d,n/d)=1，由于x/dn/d,所以1,2,n中满足x的个数等于1,2,n/d中，满足(y,n/d)=1的y的个数，故有(n/d)个。因此，记d=n/d，得证,2.3剩余类（系）Residue,2.3剩余类（系）Residue,2.3剩余类（系）Residue,例2-14设m=1,m|n,证n-(n)=m-(m)等号当且仅当m=n时成立,证明：n-(n)表示n个整数中与n不互质的整数个数m|n,所以m-(m)=n/m(m-(m)=n-n(m)/m(n)=(m).(n/m)=(m).n/m所以m-(m)=2则(ab-1)!-1(modab)，则(ab-1)!-1(moda),(ab-1)!-1(modb)因为aab-1,所以a|(ab-1)!所以(ab-1)!0(moda)矛盾,2.3剩余类（系）Residue,例2-17设p为奇素，求证k2(-1)(p+1)/2(modp)其中1kp-2,k1(mod2)考虑-1(modp)是与(n-1)!同余，所以凑k-(p-k)(modp)而k是奇，p-k就是偶所以k2k-(p-k)(p-1)!*(-1)(p-1)/2作业(6):p58第17题,2.3剩余类（系）Residue,例2-18设ao,a1,ap-1和bo,b1,bp-1是模p的两组完全剩余系，p奇素，证aobo,a1b1,ap-1bp-1一定不是模p的完全剩余系,反证：设aobo,a1b1,ap-1bp-1是模p的完全剩余系不妨设p|aobo,p|aibi,1=i=p-1,因此设p|ao,p|bo,p|ai,p|bi,1=i=p-1,所以a1,ap-1和b1,bp-1是模p的两组简化剩余系但a1ap-1-1(modp)b1bp-1-1(modp)a1b1ap-1bp-1-1(modp)矛盾,2.4剩余类（系）的应用,Hash(散列)函数就是把任意长的输入字符串（预映射，Pre-image）变换成固定长（一般更短）的输出字符串单向：多到一=碰撞（collision）必然存在也叫压缩函数、缩短函数、消息摘要、指纹、密码校验和、信息完整性检验（DIC）、操作检验码（MDC）著名的：MD5，SHA-1MOD可以实现,2.4剩余类（系）的应用,Hash函数是公开的，对处理过程不用保密安全性是它的单向性：输出不依赖于输入预映射单个比特的改变，平均而言，将引起hash值中一半的比特改变。已知一个hash值，要找到预映射的值，使它的hash值等于已知的hash值在计算上是不可行的。优良hash函数的条件：已知输出，求输入困难:单向性。已知输入计算输出容易的:快速性。已知x，构造y使Hash（x）=hash(y)困难:抗碰撞性。输出的每一比特都与输入的每一比特有关，输入每改变一比特，都将对输出产生明显影响：雪崩性。,2.4剩余类（系）的应用,应用领域密码学：特别是数字签名密码保存下载软件：emule：校验和标示微支付：例如基于冲突的micromint和基于hash链的支付payword文件系统：物理组织,2.4剩余类（系）的应用,文件系统：物理组织文件的组织形式：逻辑组织：用户看到的文件组织形式物理组织：逻辑组织到磁盘块的映射=地址映像物理组织：顺序、链式、索引、hash结构Hash结构hash(key)=addr(在磁盘或文件中的存放位置)问题：冲突,.,.,文件空间,Hash(key)=addr,起始位置,计算addr=hash(key),对应冲突记数加1,本记录空闲,顺取下一个,标记为占用填记录内容,保存记录：,T,F,查找记录：,计算addr=hash(key),取addr对应记录的冲突记数count,count=0,无此记录,本记录空闲,顺取下一记录,key相等,找到,hash(key)相等,count:=count-1,count=0,无此记录,顺取下一记录,T,F,F,T,T,F,T,F,T,F,删除记录：,调用查找过程(key),找到,错误返回,置空闲标志(找到记录)冲突记数-1对应hash(key),特点：按关键字检索速度非常快。用途：常用于目录检索。注意：文件可循环使用，满时保存失败。,2.5欧拉定理与费马小定理,2.5欧拉定理与费马小定理,2.5欧拉定理与费马小定理,需要指出：261(mod7)，6并不是满足条件的最小数,231(mod7),2.5欧拉定理与费马小定理,例：115x15+278x3+12(mod7)，x=10,原式3x15-2x3-2(mod7)3x3-2x3-2(mod7)x3-2(mod7)25(mod7)4(mod7),2.5欧拉定理与费马小定理,推论:(a,n)=1,axb(modn)解为xba(n)-1(modn)例:求解7x13(mod19)x13*717(mod19)因为72(-8)(mod19)x13*7*224-4*26-4*710(mod19),2.5欧拉定理与费马小定理,计算31000000(mod7)1000000(mod6)4原式34(mod7)6作业(7)：计算245678(mod13),p58第19题(1),2.5欧拉定理与费马小定理,2.5欧拉定理与费马小定理,求证：3n5+5n3+7n0(mod15)3n505n32n7nn(mod3)3n53n5n307n2n(mod5),2.5欧拉定理与费马小定理,例：证97104-1能被105整除,就是要证971041（mod105）因为(97,105)=1105=3*5*7，所以(105)=2*4*6=48971049748*2+8978(mod105)9781(mod3)，9781(mod5)，978972(-1)2(mod7)所以9781(mod105)成立作业(8):p58第24(4)题,2.6RSA公钥密码机制,麻省理工学院的Rivest、Shamir和Adleman三人研究小组于1978年提出机制：(1)选择两个大素数p和q；(2)计算n=pq,则(n)=(p-1)(q-1)；(3)随机选择一整数e，0eMi*xMibi(modmi)=xMibiMi-1(modmi)所以求出：462*31(mod5)变成x462*1*3(mod5)同理：x385*5*1(mod6);x330*4*1(mod7);x210*10*1(mod11),2.3孙子定理,第4步：求出解考虑x462*3(mod5)：此时的x0(mod6)(mod7)(mod11)所以，对于其他方程组，这个x同余于0，可以直接加其实xMibiMi-1(modmi)其他mj都|Mi因此下面的解满足各方程x462*3+385*5*1+330*4*1+210*10*1(mod2310)67312111(mod2310),2.3孙子定理,解方程组：7x5(mod18);13x2(mod15),首先7x5(mod18)化为：7x5(mod2)和7x5(mod9)即：x1(mod2)和7x5(mod9)13x2(mod15)化为:13x2(mod5)和13x2(mod3)即：3x2(mod5)和x2(mod3),对于7x5(mod9)可以推出7x5(mod3)即x2(mod3)所以只有3个：3x2(mod5)，x1(mod2)和7x5(mod9),解：x4*2*2*9+1*1*5*9+2*1*5*220929(mod90)作业：P59第34题,系数都化为1:x4(mod5)，x1(mod2)和x2(mod9),2.3孙子定理,北大ACM网络热身赛,青蛙的约会两只青蛙在网上相识了，觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。青蛙A和青蛙B，规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，青蛙A的出发点坐标是x，一次能跳m米;青蛙B的出发点坐标是y。一次能跳n米。两只青蛙跳一次所花费的时间相同。纬度线总长L米。,福大ACM网络热身赛,猪的安家Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈，很多猪只能够在一个猪圈安家。举个例子，假如有16头猪，Andy建了3个猪圈，为了保证公平，剩下1头猪就没有地方安家了。Mary生气了，骂Andy没有脑子，并让他重新建立猪圈。这回Andy建造了5个猪圈，但是仍然有1头猪没有地方去，然后Andy又建造了7个猪圈，但是还有2头没有地方去。Andy都快疯了。你对这个事情感兴趣起来，你想通过Andy建造猪圈的过程，知道Andy家至少养了多少头猪。,2.5加速RSA的实现速度,p=23,q=47,e=3,加密字母A，并解密,首先A的ASCII码为65，n=pq=1081,(n)=1012，d=675加密：c65351(mod1081)变成“3”解密：m51675(mod1081)m51675(46+5)22*30+155155*2575*2720*32-4(mod23)m51675(47+4)46*14+3126221621218(mod47),直接使用孙子定理m-4*47*1+18*23*(-2)-101665(mod1081),2.5加速RSA的实现速度,JavaDocumentC#RSAParameters,2.5加速RSA的实现速度,分析对N求模，现在变成了对P和Q求模,余数的大小是P和Q的剩余系里的数了。按位数来算，现在的乘数的二进制位数是原来乘数的二进制位数的一半根据理论分析，用了中国剩余定理后，RSA的速度又提高了约50%,2.5加速RSA的实现速度,可能受到出错攻击设备可能出错此时如果Cp计算错误，而Cq计算正确，则可以分解n若Cp被计算成Cp，最终计算的C变成C,=M(modn)则M-M0(modq)M-M0(modp)所以gcd(M-M),n)=q其中,2.6群签名方案,中国剩余定理最主要的价值在于将单个方程式和一个方程组等价起来若干用户组成一个群体，使用相关的签名方案群中心负责为群管理员和群成员分配秘钥，群管理员则在必要的时候打开签名确定签名者的身份。可用在电子投票、电子拍卖等领域一个基本的群签名应具有匿名性即同一个群中的成员不能识别其他群成员的签名;不相关性即决定两个不同的签名是否来自于同一个人计算上是不可行的;不可伪造性即任何多个群成员不能伪造其他成员的签名。,2.6群签名方案,签名机制秘钥生成群中心随机地生成两个大素数p，q，计算n=pq，选择公开hash函数h(x)选择，并求d，使随机选择,使选择素数,且,将()送给用户做密钥验证，以确信消息是群中心送来的群中心将()送给群管理员，其中是群成员的身份。设系统有k个成员，群中心利用中国剩余定理，可求同余方程组：的解C群中心将（n,e,c）作为公钥，（d,p,q）为群中心的私钥,2.6群签名方案,签名机制成员的加入和撤销在有成员加入或撤销时，群中心只需重新求解c的值并公布出去，而不必改变其他群成员的秘钥。签名群成员要对消息m签名,首先计算h(m),再计算则即为的签名。验证若Alice要对的签名进行验证，Alice利用群公钥e计算：，得到，然后验证：是否成立。若成立，签名合法，否则不接受签名。群管理员通过对应的IDi确定签名者的身份。,2.6群签名方案,可能遭受的攻击群中心伪造群成员的签名显然该方案中群中心知道所有的群成员的签名秘钥，因此一个不诚实的群中心可以伪造其他群成员的合法签名而不被发现联合攻击假设群成员联合对方案攻击，他们分别掌握可知为和为的公因子联合人越多成功的可能越大也可以自己通过多次加入群实现,2.4同余方程的一般理论,2.4同余方程的一般理论,2.4同余方程的一般理论,2.4同余方程的一般理论,2.4同余方程的一般理论,法二：直接删除x4化为：3x2+4x+2x3+x+x2+x3+2x2+x3x3+x2+x(mod5),总结,同余：余数相同，关注余数，离不开除数一定是模m的意义下同余ab(modm)m|a-ba=b+km非常类似于=：左右可以同时加减乘除同一个数，但不能除以0:同一个m，左右可以同时加减乘除同余的数但不能除以与0同余的数如1428(mod7)不能=24(mod7)除了以后仍然得为整数:a,b不变，m变m可以变成其一个因子，等式仍然成立M可分解成n个不同的素数：方程与方程组的互化逆元,练习,一般技巧同时减去同余于0的数的倍数，即模m的倍数将几个乘数凑成1，约去，一般使用逆元例：115x15+278x3+12(mod7)，x=15,原式(7*16+3)x15+(7*40-2)x3+14-2(mod7)3x15-2x3-2(mod7)X=153*1515-2*153-2(mod7)3*115-2*13-2(mod7)-1(mod7)类似：求解123456789(mod7),练习,例：求证(mn-1,m3)=1,证：若(mn-1,m3)=p,则m30(modp)mn-10(modp),则n*m30(modp)m2(mn-1)0(modp),则m20(modp)又因m(mn-1)0(modp),则m0(modp),则mn0(modp)又因mn-10(modp),则10(modp),所以p=1,练习,例：a,b,c,d4个整数，求证12|(a-b)(a-c)(a-d)(b-c)(b-d)(c-d),只需证明3|,4|因为a,b,c,d有4个数，则至少2个数模3同余，不妨设为a,b，则3|a-b对于模2，分别2个数模2余1和0，不妨设为a,b和c,d,则2|a-b,2|c-d,则4|(a-b)(c-d)3个数模2同余，不妨设为a,b,c则4|(a-b)(a-c),练习,7*8*9*10*11*12(mod13),(-6)*(-5)*(-4)*(-3)*(-2)*(-1)6!,扩推12!(mod13)(6!)2,总结,模m的剩余类：同余的归一类：2类或者完全一样，或者完全不同完全不同的最多m个：完全剩余类模m的剩余系每个剩余类中找出一个代表元，组成一个系完全剩余类完系，0，1，,m-1紧缩剩余类缩系,(m)缩系最大的价值：每个元素都有逆元m为素的价值：完系-0就是缩系,总结,关于缩系与完系的定理模m都可统一到0到m-1之间，简化x遍历缩（完）系，则ax+b也遍历，其中（a,m）=1结合右图扩展：a也是缩系中的一员，若b=0，如对于72*122*242*362*412*532*65(mod7)可形成分离的循环1*222*244*21；2*362*652*53,总结,技巧不规则的数简化为0，1，m的形式要证完系，分别证有m个，两两不同余要证缩系，先证完系，在证与m互质,练习,证明：当m2时，02,12,(m-1)2一定不是模m的完全剩余系。m个,所以只需证存在两个同余(m-1)2=m2+m+11(modm)类似：m个整数，都不属于剩余类0(modm)则其中必有2个数属于同一剩余类,练习,求证：模m简化剩余系每个元素的和模m与0同余若r为模m的简化剩余，则m-r也是所以，可以两两凑对求和，每对和与0同于,总结,欧拉函数的计算公式：更常用两个：(m,n)=1时和,总结,Wilson定理(p-1)!-1(modp)p是素数判断素数的方法之三之一：用不大于sqrt(n)的质数试除（3,i+=2）之二：爱托拉斯散筛法,总结,欧拉定理费马小定理技巧：指数化简，指数中减去欧拉函数的倍数模若为合数，先分离成多个模互质的方程,练习,证明：n整数，a7a(mod63),首先63=7*9，所以分解：先证a7a(mod7)，直接根据费马定理再由于(9)=9-3=6，所以若(a,9)=1或9时，a7a(mod9)若(a,9)=3，a2k0(mod9)所以(a,9)=3时是不成立注意：欧拉定理与费马小定理的不同之处,总结,应用：判断素数的方法之四首先计算2n，若模n是否同余于2注意：此时的判断方法与费马小定理的推理正好相