第二章-同余-信安数学课件.ppt

《第二章-同余-信安数学课件.ppt》由会员分享，可在线阅读，更多相关《第二章-同余-信安数学课件.ppt（131页珍藏版）》请在三一办公上搜索。

1、,学习目标掌握同余、剩余类（系）、欧拉函数、费马定理、孙子定理了解同余理论和孙子定理在计算机和密码学的应用课程内容的设置同余的基本概念、性质和应用剩余类、完全剩余系、简化剩余系及应用欧拉函数、费马定理及应用孙子定理同余式,2.0 问题的提出,50天后星期几？234567天后呢？计算机中的溢出问题循环队列的的实现？%,数学中的同余整除中：a=qb+r 0 r b：同余就是余相等如：19=12*1+7 7=12*0+7,2.0 问题的解决同余理论,2.1 同余的基本概念与性质,定义2.1.1,若r1=r2,则称a，b模m同余：也记为：或,2.1 同余的基本概念与性质,例：27?(mod 7)253

2、天后星期几？,同时：a r(mod 7)0r r 是一个满射,因此：可以按不同的余数对整数分类，也就是每一类余数相同，也就是同余,23=81(mod 7)所以25323*17+2 4(mod 7),2.1 同余的基本概念与性质,定理 2.1.1 同余关系是一种等价关系：自反性：对称性：则 传递性：则,2.1 同余的基本概念与性质,例:证明(mn-1,m3)=1,证：设（mn-1,m3）=p所以mn-10(modp),m3 0(modp)所以m2 mn.m2=n.m3 0(modp),所以m mn.m=n.m2 0(modp),所以1 mn=m.n 0(modp),所以p=1,2.1 同余的基本

3、概念与性质,性质2.2 设（1）特别的：（2)特别的：以及：（6）,且 则有,2.1 同余的基本概念与性质,性质2.2（3）特别的：,若（m,n）=1 则 扩大：扩大：若，d|(a,b,m)则（4）d|m，则 特别的：若,2.1 同余的基本概念与性质,性质2.2（7）若（8）（补充）若，则(a,m)=(b,m)例作业(1):p57 第1题,2.1 同余的基本概念与性质,作业(2):p57 第5题,2.1 同余的基本概念与性质,问题：一个十进制数，什么时候能被3整除结论：当各位和为3的倍数时如：248901why？,2.1 同余的基本概念与性质,关键：10=33+1，100=33 3+1，所以：

4、若n=am10m+am-110m-1+a110+a0 3|n 3|am+am-1+a1+a0,2.1 同余的基本概念与性质,例：快速判断某个数整除7的余数？,103(mod7),100302(mod7),100020-1(mod7)10002k+1-1(mod7),10002k1(mod7)若n=am1000m+am-11000m-1+a11000+a0 对于637692692-637=55=6(mod7),2.1 同余的基本概念与性质,扩展：怎样快速判断一个数可以被19整除？提示：凑成19的倍数2位数字？多于2位时？作业(3)：怎样快速判断一个数可以被31整除？,p57 第3题,2.1 同余

5、的基本概念与性质,补充，性质2.2（7）的特殊情况（1）若P,q不同素数，,2.1 同余的基本概念与性质,例：p,p+10,p+14均是素数？求p,因为10=2*5，14=2*7，所以p2,5,7对于p=3，若p1(mod3)，则p+140(mod3)，排除若p2(mod3)，则p+100(mod3)，排除所以p0(mod3)因为p素，所以p=3,2.1 同余的基本概念与性质,（补充），则存在唯一 使 因为存在ax+my=1 即 ax-1=my 若存在x1和x2两个逆元，则x1*a*x2x1x2(mod m)如若(a,m)1，则a-1不存在,2.1 同余的基本概念与性质,求5模11的逆元,11

6、=5*2+1 5*2-1(mod 11)5*(-2)1(mod 11)5模11的逆元为-2（但更常写为9）求233模1211的逆元,1211=233*5+46 233=46*5+3 46=3*15+11=46-3*15=46-(233-46*5)*15=46*76-233*15=(1211-233*5)*76-233*15=1211*76-233*395所以 395为所求,2.1 同余的基本概念与性质,求解方程 17x 4(mod 19),19=17+2 17=8*2+1 所以 17*9-19*8=1所以 17*91(mod 19)因为(4,9)=1所以 17*364(mod 19)，所以x3

7、6-2(mod 19)作业(4):p59 第25题(1)(3),2.2 同余的应用,主要应用 补码、随机数、文件系统、hash、密码、检错码等,编程时求余的主要实现mod excel、vb、asp、delphi、vfp等%c、c+、c#、java等,2.2 同余的应用,补码 Twos complement为什么会有补码如何计算口诀原理：异或：模2加,2.2 同余的应用,循环队列数组 queuemax_size队首指针 front，指向队首元素的前一个位置队尾指针 rear，指向队尾元素初始化 front=rear=0插入元素 rear=(rear+1)%max_size删除元素 front=(

8、front+1)%max_size什么时候为空？什么时候为满元素数量最多为 max_size-1,2.2 同余的应用,随机数（Random Number）什么是随机数有什么用：仿真、游戏、协议、密码srand(seed)int rand(viod)产生方法：利用随机过程事先定制好的随机数表利用数学递推公式模拟 伪随机数（Pseudo-Random Number),随机数（Random Number）伪随机数产生方法迭代取中法：代表性为平方取中乘同余线性乘同余，也叫混合同余改进：,2.2 同余的应用,1961年由IBM提出,2.2 同余的应用,仿射密码 Affine Cipheryax+b(mo

9、d26)尝试解密：casear 考虑编程的解法LXWPAJCDUJCRXWB,yx+3(mod 26),凯撒密码 Caesar Cipher移位密码、加法密码,2.2 同余的应用,2.3 剩余类（系）Residue,同余是一种等价关系=可以借助同余实现划分 令Ca=c|定理2-1(1)任意整数都包含于一个Cr中，0rm-1(2)Ca=Cb(3)要么 Ca=Cb，要么CaCb=(4)两两不同的Cr最多m个,2.3 剩余类（系）Residue,定义2.2.1Ca叫模m的一个剩余类，Ca中的任一数叫该类的代表元（），若 为m个整数，并且其中任两个数都不在同一个剩余类中，叫模m的一个完全剩余系，若（r

10、,m）=1,则这样的剩余类叫做模m的简化（紧缩/既约）剩余系,缩系元素的个数叫做欧拉函数(m),2.3 剩余类（系）Residue,2.3 剩余类（系）Residue,2.3 剩余类（系）Residue,例:a1,a2，an是一个模n的完系，则 ak 0(mod n)n=2k+1 n/2(mod n)n=2k,ak 1+2+n n(1+n)/2（mod n）若n=2k+1 则，akn*(k+1)0(mod n)若n=2k 则，akk*(n+1)k(mod n),2.3 剩余类（系）Residue,例2-10:a1,a2，an，b1,b2，bn是两个模n的完系，证明：当m是偶数时，a1+b1,a

11、2+b2，an+bn一定不是模n的完系,2.3 剩余类（系）Residue,例2-11 设m=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(mod 5)写成模15的剩余类的和例：写出模9的完系，要求全是奇数对于10呢？作业(5):p58 第9题,2.3 剩余类（系）Residue,定理,(m,n)=1,(1)Ca,Cb为2个不同的剩余类 nCa,n

12、Cb为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 剩余类（系）Re

13、sidue,关键n=pn时，其缩系的元素？排除与其最大公约数大于1的,也就是该数为xp(0,n-1)中，非缩系元素最小为0,最大pn-p,x取值0到pn-1 1，共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中

14、满足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)=n-(n)当且仅当m=n式成立,2.3 剩余类（系）Residue,2.3 剩余类（系）Residue,推论：如果(p-1)!-1(

15、mod p)，则p是素数反证：如果p=ab，a,b=2则(ab-1)!-1(mod ab)，则(ab-1)!-1(mod a),(ab-1)!-1(mod b)因为 aab-1,所以a|(ab-1)!所以(ab-1)!0(mod a)矛盾,2.3 剩余类（系）Residue,例2-17 设p为奇素，求证k2(-1)(p+1)/2(mod p)其中 1k p-2,k1(mod 2)考虑-1(mod p)是与(n-1)!同余，所以凑k-(p-k)(mod p)而k是奇，p-k就是偶所以k2k-(p-k)(p-1)!*(-1)(p-1)/2作业(6):p58 第17题,2.3 剩余类（系）Resid

16、ue,例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-ima

17、ge）变换成固定长（一般更短）的输出字符串单向：多到一=碰撞（collision）必然存在也叫压缩函数、缩短函数、消息摘要、指纹、密码校验和、信息完整性检验（DIC）、操作检验码（MDC）著名的：MD5，SHA-1MOD可以实现,2.4 剩余类（系）的应用,Hash函数是公开的，对处理过程不用保密安全性是它的单向性：输出不依赖于输入预映射单个比特的改变，平均而言，将引起hash值中一半的比特改变。已知一个hash值，要找到预映射的值，使它的hash值等于已知的hash值在计算上是不可行的。优良hash函数的条件：已知输出，求输入困难:单向性。已知输入计算输出容易的:快速性。已知x，构造y使Ha

18、sh（x）=hash(y)困难:抗碰撞性。输出的每一比特都与输入的每一比特有关，输入每改变一比特，都将对输出产生明显影响：雪崩性。,2.4 剩余类（系）的应用,应用领域密码学：特别是数字签名密码保存下载软件：emule：校验和标示微支付：例如基于冲突的micromint和基于hash链的支付payword文件系统：物理组织,2.4 剩余类（系）的应用,文件系统：物理组织文件的组织形式：逻辑组织：用户看到的文件组织形式物理组织：逻辑组织到磁盘块的映射=地址映像物理组织：顺序、链式、索引、hash结构Hash结构hash(key)=addr(在磁盘或文件中的存放位置)问题：冲突,.,.,文件空间,

19、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),特点：按关键字检索速度非常快。用途：常用于

20、目录检索。注意：文件可循环使用，满时保存失败。,2.5 欧拉定理与费马小定理,2.5 欧拉定理与费马小定理,2.5 欧拉定理与费马小定理,需要指出：26 1(mod 7)，6并不是满足条件的最小数,23 1(mod 7),2.5 欧拉定理与费马小定理,例：115x15+278x3+12(mod 7)，x=10,原式3x15-2x3-2(mod 7)3x3-2x3-2(mod 7)x3-2(mod 7)25(mod 7)4(mod 7),2.5 欧拉定理与费马小定理,推论:(a,n)=1,axb(mod n)解为 x ba(n)-1(mod n)例:求解 7x 13(mod 19)x13*717

21、(mod 19)因为72(-8)(mod 19)x13*7*224-4*36-4*7 10(mod 19),2.5 欧拉定理与费马小定理,计算31000000(mod 47)1000000(mod 46)6 原式36-13*9-117 24(mod 47)作业(7)：计算 245678(mod 13),p58第19题(1),2.5 欧拉定理与费马小定理,2.5 欧拉定理与费马小定理,求证：3n5+5n3+7n 0(mod 15)3n50 5n32n 7nn(mod 3)3n53n 5n30 7n2n(mod 5),2.5 欧拉定理与费马小定理,例：证97104-1能被105整除,就是要证971

22、04 1（mod 105）因为(97,105)=1105=3*5*7，所以(105)=2*4*6=48971049748*2+8 978(mod 105)9781(mod 3)，9781(mod 5)，978 972(-1)2(mod 7)所以9781(mod 105)成立作业(8):p58 第24(4)题,2.6 RSA公钥密码机制,麻省理工学院的Rivest、Shamir和Adleman三人研究小组于1978年提出机制：(1)选择两个大素数p和q；(2)计算n=pq,则(n)=(p-1)(q-1)；(3)随机选择一整数e，0e(n),满足(n)，e)=1；(4)计算d，满足de1(mod(

23、n)(5)d保密，(d,n)是私钥；发布(e,n)是公钥；销毁p,q(6)若m表示明文，用c表示密文(m和c均小于n)，则加密：；解密：,2.6 RSA公钥密码机制,实现中的问题（1）如何计算ab mod n（2）如何判定一个给定的整数是素数？（3）如何找到足够大的素数p和q?,2.6 RSA公钥密码机制,如何计算ab mod n1）计算a*a*a*a*a*a，需要计算n-1次乘法，时间复杂度O(n)2）考虑实例a4，计算b=a*a，再算c=b*b，则c=a4，但是只用了两次乘法，效率提高。比如a9=a*(a4)*(a4)，只需用4次乘法，一般的，an时间复杂度为O(logn),2.6 RSA

24、公钥密码机制,第二种算法与二进制的关系9=(1001)2，a9=(12*a)2)2)2*a10=(1010)2，a10=(12)*a)2)2*a)2从二进制第一位开始，遇到1就先平方乘以a，遇到0就直接平方,2.6 RSA公钥密码机制,如何计算ab mod nBR算法 Binary Representation中国剩余定理能提高速度，下节内容作业(9):p58 第20题,d 1for i k down to 0 d(d*d)mod n if bi=1then d(d*a)mod nreturn d,2.6 RSA公钥密码机制,公钥发布当要通信时向对方索要其公钥可能假冒，因此仍需要额外的可信保障

25、扩散通过可信的朋友之间的辗转交换，如PGP(Pretty Good Privacy)公开的目录服务目录的维护得由信得过的机构执行每个用户在目录里有一项身份信息，其公钥 证书中心CA(Certificate Authentication)PKI的核心,2.6 RSA公钥密码机制,RSA可能受到的攻击枚举枚举所有可能明文m，用e加密和c比较枚举所有可能的私钥d数学方法分解n=pq，就可以计算(n)，就可从e求得d不分解n，而直接求(n)，再求d 不求(n)，直接求d,2.6 RSA公钥密码机制,从攻击对象：对RSA的定点攻击对RSA的共模攻击对RSA的选择密文攻击对RSA的小加密指数攻击对RSA的

26、小解密指数攻击时间性攻击：取决于解密算法的运算时间,2.6 RSA公钥密码机制,定点攻击第三者截获密文C后，反复计算e次幂 ce me2 ce2 me3（mod n）一旦 cet c me（mod n）=m cet-1（mod n）t不是很大时这种攻击可行如何避免？如何让t很大？今后分解,2.6 RSA公钥密码机制,选择密文攻击利用同态：Ek(x1x2)=Ek(x1)Ek(x2)例1：m3 m1m2(mod n),让A给其中两个签名就能够得到其对第3个的签名例2：收集到用A公钥加密的密文C，想要得到明文M 他首先选择随机数r,使rn.然后用A的公开密钥e计算 x re mod n y xc m

27、od n 让A对y签名，得到u yd mod n r-1yd mod n r-1xdcd mod n cd mod n m不要用RSA对陌生人的随机文件签名，签名前先使用一个散列函数,2.6 RSA公钥密码机制,共模攻击如果相同的消息曾用两个不同的指数加密，而这两个指数是互素、加密的用户共模，则明文可以不用任何一个解密密钥来恢复。设用户的公开密钥分别为e1,e2,且e1,e2互素，明文消息为m,密文为C1 me1 mod nC2 me2 mod n 因为（e1,e2)=1,r*e1+s*e2=1假定r为负数 则：(C1-1)r*C2s=m mod n所以：不要共模,2.6 RSA公钥密码机制,

28、总结加/解密、密钥交换、数字签名使用最广泛注：实际使用时RSA加密的一般不是直接的明文，而是会话密钥，然后用对称算法加解密公钥算法加密解密速度慢误区:公开密钥密码算法更安全公开密钥密码使对称密钥密码过时了公钥的分发是简单和一目了然的,2.5 同余方程的一般理论,2.5 同余方程的一般理论,2.5 同余方程的一般理论,2.5 同余方程的一般理论,2.5 同余方程的一般理论,法二：直接删除x4化为：3x2+4x+2x3+x+x2+x3+2x2+x 3x3+x2+x(mod 5),问题的提出,代数的主要问题就是解方程隋朝之前有部孙子算经提出“物不知数”问题：今有物不知数，三三数之有二，五五数之有三，

29、七七数之有二，问物有几何韩信点兵有兵一队，若列成五行，末行一人，若列成六行，末行五人，列成七行，末行四人，列成十一行，末行十人，求兵数解决：大衍求一术，鬼谷算天文、历法的需要,中国剩余定理 Chinese Remainder Theorem Let n be a positive integer such that it leaves the remainders 2,3,2 when it is divided by 3,5,7 respectively.Find n.最简单直接的方法：Since n=3k+2 will leave remainder 2 when it is divide

30、d by 3,n=2,5,8,11,14,17,20.We found that n=8 can satisfy the first two conditions but not the third one.As the L.C.M.of 3,5 is 15,we add the number 8 by 15 each time until we get our solutions.n=23 Any other solutions?General Solutions?,2.7 孙子定理,2.3 孙子定理,明朝程大位算数统筹：三人同行七十稀，五树梅花甘一枝，七子团圆整半月，除百零五便得知。,2.

31、3 孙子定理,利用算式表示：再把233+105n均是答案,三人同行七十稀五树梅花甘一枝七子团圆整半月 除百零五便得知,2.3 孙子定理,把问题一般化如何找70、21、15,2.3 孙子定理,找出A,B,C分别满足以下条件而答案则为,2.3 孙子定理,定理2-11 孙子定理 设 两两互素，k=2,，则同余方程组 解为,2.3 孙子定理,2.3 孙子定理,第1步：最后的模M=5*6*7*11=2310第2步：各方程模变为M需要乘以的数Mi M1=2310/5=6*7*11=462;M2=2310/6=5*7*11=385 M3=2310/7=5*6*11=330;M4=2310/11=5*6*7=

32、210第3步：求出逆元Mi-1考虑 Mi*xMibi(mod M)xMi-1Mibi(mod M)但上面Mi-1是不存在的，因为（M,Mi）=M/mi，但（mi,Mi）=1Mi*xMibi(modM)=Mi*xMibi(mod mi)=xMibiMi-1(mod mi)所以求出：462*31(mod 5)变成x462*1*3(mod 5)同理：x385*5*1(mod 6);x330*4*1(mod 7);x210*10*1(mod 11),2.3 孙子定理,第4步：求出解考虑 x462*3(mod 5)：此时的x0(mod6)(mod 7)(mod 11)所以，对于其他方程组，这个x同余于0

33、，可以直接加其实 xMibiMi-1(mod mi)其他mj都|Mi因此 下面的解满足各方程 x462*3+385*5*1+330*4*1+210*10*1(mod 2310)6731 2111(mod 2310),2.3 孙子定理,练习解方程组：7x5(mod 18);13x2(mod 15),首先7x5(mod 18)化为：7x5(mod 2)和7x5(mod 9)即：x1(mod 2)和7x5(mod 9)13x2(mod 15)化为:13x2(mod 5)和13x2(mod 3)即：3x2(mod 5)和x2(mod 3),对于7x5(mod 9)可以推出7x5(mod 3)即x2(m

34、od 3)所以只有3个：3x2(mod 5)，x1(mod 2)和7x5(mod 9),解：x4*2*2*9+1*1*5*9+2*1*5*220929(mod 90)作业：P59第34题,系数都化为1:x4(mod 5)，x1(mod 2)和 x2(mod 9),2.3 孙子定理,北大ACM网络热身赛,青蛙的约会 两只青蛙在网上相识了，觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙

35、，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。青蛙A和青蛙B，规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，青蛙A的出发点坐标是x，一次能跳m米;青蛙B的出发点坐标是y。一次能跳n米。两只青蛙跳一次所花费的时间相同。纬度线总长L米。,福大ACM网络热身赛,猪的安家 Andy和Mary养了很多猪。他们想要给猪安家。但是Andy没有足够的猪圈，很多猪只能够在一个猪圈安家。举个例子，假如有16头猪，Andy建了3个猪圈，为了保证公平，剩下1头猪就没有地方安家了。Mary生气了，骂Andy没有脑子，并让他重新建立猪圈。这回Andy建造了5个猪圈，但是仍然有1头猪没

36、有地方去，然后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(mod 1081)变成“3”解密：m51675(mod 1081)m51675(46+5)22*30+155155*2575*2720*32-4(mod23)m51675(47+4)46*14+3126221621218(mod47),直接使用孙子定理

37、m-4*47*1+18*23*(-2)-1016 65(mod 1081),2.5 加速RSA的实现速度,Java DocumentC#RSAParameters,2.5 加速RSA的实现速度,分析对N求模，现在变成了对P和Q求模,余数的大小是P和Q的剩余系里的数了。按位数来算，现在的乘数的二进制位数是原来乘数的二进制位数的一半根据理论分析，用了中国剩余定理后，RSA 的速度又提高了约50%,2.5 加速RSA的实现速度,可能受到出错攻击设备可能出错此时如果Cp计算错误，而Cq计算正确，则可以分解n若Cp被计算成Cp，最终计算的C变成C,=M(mod n)则 M-M 0(mod q)M-M 0

38、(mod p)所以gcd(M-M),n)=q其中,2.6 群签名方案,中国剩余定理最主要的价值在于将单个方程式和一个方程组等价起来若干用户组成一个群体，使用相关的签名方案群中心负责为群管理员和群成员分配秘钥，群管理员则在必要的时候打开签名确定签名者的身份。可用在电子投票、电子拍卖等领域一个基本的群签名应具有匿名性即同一个群中的成员不能识别其他群成员的签名;不相关性即决定两个不同的签名是否来自于同一个人计算上是不可行的;不可伪造性即任何多个群成员不能伪造其他成员的签名。,2.6 群签名方案,签名机制秘钥生成群中心随机地生成两个大素数 p，q，计算n=pq，选择公开hash函数h(x)选择，并求d

39、，使随机选择,使 选择素数,且,将()送给用户 做密钥 验证，以确信消息是群中心送来的群中心将()送给群管理员，其中 是群成员的身份。设系统有k个成员，群中心利用中国剩余定理，可求同余方程组：的解C 群中心将（n,e,c）作为公钥，（d,p,q）为群中心的私钥,2.6 群签名方案,签名机制成员的加入和撤销 在有成员加入或撤销时，群中心只需重新求解c 的值并公布出去，而不必改变其他群成员的秘钥。签名 群成员 要对消息m签名,首先计算h(m),再计算 则 即为 的签名。验证 若Alice 要对 的签名 进行验证，Alice利用群公钥e 计算：，得到，然后验证：是否成立。若成立，签名合法，否则不接受

40、签名。群管理员通过 对应的IDi确定签名者的身份。,2.6 群签名方案,可能遭受的攻击群中心伪造群成员的签名 显然该方案中群中心知道所有的群成员的签名秘钥，因此一个不诚实的群中心可以伪造其他群成员的合法签名而不被发现联合攻击假设群成员 联合对方案攻击，他们分别掌握 可知 为 和 为的公因子联合人越多成功的可能越大 也可以自己通过多次加入群实现,总结,同余：余数相同，关注余数，离不开除数一定是模m的意义下同余ab(mod m)m|a-ba=b+km非常类似于=：左右可以同时加减乘除同一个数，但不能除以0:同一个m，左右可以同时加减乘除同余的数但不能除以与0同余的数 如1428(mod7)不能=2

41、4(mod7)除了以后仍然得为整数:a,b不变，m变m可以变成其一个因子，等式仍然成立M可分解成n个不同的素数：方程与方程组的互化逆元,练习,一般技巧同时减去同余于0的数的倍数，即模m的倍数将几个乘数凑成1，约去，一般使用逆元例：115x15+278x3+12(mod 7)，x=15,原式(7*16+3)x15+(7*40-2)x3+14-2(mod 7)3x15-2x3-2(mod 7)X=15 3*1515-2*153-2(mod 7)3*115-2*13-2(mod 7)-1(mod 7)类似：求解123456789(mod 7),练习,例：a,b,c,d4个整数，求证 12|(a-b)

42、(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(mod 13),(-6)*(-5)*(-4)*(-3)*(-2)*(-1)6!,扩推 12!(mod 13)(6!)2,总结,模m的剩余类：同余的归一类：2类或者完全一样，或者完全不同完全不同的最多m个：完全剩余类模m的剩余系每个剩余类中找

43、出一个代表元，组成一个系完全剩余类 完系，0，1，,m-1紧缩剩余类 缩系,(m)缩系最大的价值：每个元素都有逆元m为素的价值：完系-0就是缩系,总结,关于缩系与完系的定理 模m都可统一到0到m-1之间，简化x遍历缩（完）系，则ax+b也遍历，其中（a,m）=1结合右图扩展：a也是缩系中的一员，若b=0，如对于72*12 2*24 2*36 2*41 2*53 2*65(mod7)可形成分离的循环1*22 2*24 4*21；2*36 2*65 2*53,总结,技巧不规则的数简化为0，1，m的形式要证完系，分别证有m个，两两不同余要证缩系，先证完系，在证与m互质,练习,证明：当m2时，02,1

44、2,(m-1)2一定不是模m的完全剩余系。m个,所以只需证存在两个同余(m-1)2=m2-2m+11(mod m)类似：m个整数，都不属于剩余类0(mod m)则其中必有2个数属于同一剩余类,练习,求证：模m简化剩余系每个元素的和模m与0同余若r为模m的简化剩余，则m-r也是所以，可以两两凑对求和，每对和与0同于,总结,欧拉函数的计算公式：更常用两个：(m,n)=1时 和,总结,Wilson定理(p-1)!-1(mod p)p是素数判断素数的方法之三之一：用不大于sqrt(n)的质数试除（3,i+=2）之二：爱托拉斯散筛法,总结,欧拉定理费马小定理技巧：指数化简，指数中减去欧拉函数的倍数模若为

45、合数，先分离成多个模互质的方程,练习,证明：n整数，a7 a(mod 63),首先63=7*9，所以分解：先证 a7a(mod 7)，直接根据费马定理再由于(9)=9-3=6，所以若(a,9)=1或9时，a7a(mod 9)若(a,9)=3，a2k0(mod 9)所以(a,9)=3时是不成立注意：欧拉定理与费马小定理的不同之处,总结,应用：判断素数的方法之四首先计算2n，若模n是否同余于2注意：此时的判断方法与费马小定理的推理正好相反。如果p质数则成立 vs.如果成立，则p是质数所以只能排除合数，并不能肯定素数伪素数,总结,应用：RSA(1)选择两个大素数p和q；(2)计算n=pq,则(n)=

46、(p-1)(q-1)；(3)任选整数e，0e(n),满足(n)，e)=1；(4)计算d，满足de1(mod(n)(5)(d,n)是私钥；发布(e,n)是公钥；销毁p,q(6)m表示明文，用c表示密文(m和c均小于n)，则加密：；解密：,练习,p=23,q=47,e=3,加密字母A，并解密,首先A的ASCII码为65，n=pq=1081,(n)=(p-1)(q-1)=1012，因为1012=3*337+1,所以d=-337675所以：公钥(1081,3)，私钥(1081,675)加密：c65351(mod 1081)变成“3”解密：m51675(mod 1081)m51675(46+5)22*3

47、0+155155*2575*2720*32-4(mod23)m51675(47+4)46*14+3126221621218(mod47)所以m=23s-4=47t+18 若t=1,m=65,s=3，还原出明文“A”其实可以直接使用孙子定理,总结,孙子定理解一次同余方程组观察：注意三点x的系数为1，意味着如不为1就要先化为1模互质，不一定都是素数，互质条件下同余方程组就能和一个同余方程实现相互转化,技巧,最后的解的模为各mi的积M对于每个同余式分别计算2个值mi（自己的模）转化成M（最后的模）需要乘以的倍数即除了自身以外，其余各模的乘积这个乘积对于本同余式模mi的逆元只有对其他模都没有逆元求和得

48、解和的模为M,总结,还需知道孙子定理的最大价值不在于直接解同余方程组而在于大模的一个同余式化为小模的、模互质的同余方程组然后利用欧拉定理、费马小定理将式子化简通过解同余方程组来提高解原来同余式的速度特别是存在大指数的情况更有效,法一：1012=127*8-4 127=4*32-1所以（127，1012）=1，有解1=4*32-127 1=(127*8-1012)*32-127=127*255-1012*32所以127*255 1(mod 1012)所以两边同乘以255255*127x 255*833(mod 1012)907(mod 1012),练习,解 127x833(mod 1012),1

49、012=4*11*23，所以化为方程组127x833(mod 4)化简为：x-1(mod 4)127x833(mod 11)化简为：6x-3(mod 11)=x5(mod 11)127x833(mod 23)化简为：12x5(mod 23)=x10(mod 23)对于第一个：M1=11*23=253 因为2531(mod 4),M1=1对于第二个：M2=4*23=92 因为924(mod 11),M2=3对于第三个：M3=4*11=44 因为44-2(mod 23)，M3=11求和：x1*(-1)*1+4*5*3+(-2)*10*11 错误！应该：x253*(-1)*1+92*5*3+44*1

50、0*11-253+1380+48405967907(mod 1012),练习,解 127x833(mod 1012),最后的模应大于47*87，也就是大概为50*90=4500首先要找到各方程式的模，考虑47是个素数，87=3*29所以可以采用一个模为29，这样，一个同余式中会出现0方便计算，而不采用3是因为它与4500相差太远还需要150才能实现4500,150=15*10，所以考虑11和17建立方程组：xy47*870(mod 29)xy47*87-3(mod 11)xy47*87-4*29(mod 17),练习,X=47,y=87,利用孙子定理计算x*y,对于方程组：xy0(mod 29