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

《第二章-同余-信安数学课件.ppt》由会员分享，可在线阅读，更多相关《第二章-同余-信安数学课件.ppt（131页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、余：v也记为： 或 ZbaZm,*2211,rmqbrmqa)(modmba bam)(mod0mbabam|kmba)(modmrba2.1 同余的基本概念与性质同余的基本概念与性质例：27? (mod 7)253天后星期几？v同时 ：a r (mod 7) 0r r 是一个满射v因此 ：可以按不同的余数对整数分类，也就是每一类余数相同，也就是同余v23=81 (mod 7) 所以25323*17+2 4 (mod 7) 2.1 同余的基本概念与性质同余的基本概念与性质定理 2.1.1 同余关系是一种等价关系：v自反性：v对称性： 则 v传递性： 则)(modmaa )(modmba )(m

3、odmab )(modmba )(modmcb )(modmca 2.1 同余的基本概念与性质同余的基本概念与性质例:证明(mn-1,m3)=12.1 同余的基本概念与性质同余的基本概念与性质性质2.2 设（1） 特别的：（2) 特别的： 以及：（6） , 且 则有ZkmdcmbaNm),(mod),(mod,)(modmdybxcyax)(modmkbka)(modmbdac )(modmbkak )(mod,mbaNnnn011)(axaxaxfnn011)(bxbxbxgnnZbaii,)(mod,1mbaniii)(modmyx )(mod()(mygxf2.1 同余的基本概念与性质同

4、余的基本概念与性质性质2.2 v（3） 特别的： , 若（m,n）=1 则 扩大： 扩大：若 ，d|(a,b,m) 则 v（4）d|m，则 特别的：若)(mod mbnan )(mod mba ),(modnmmba )(mod mba )(moddmdbda)(mod)(mod,*mnbnanmbaZn)(moddba )(mod,nbanml有2.1 同余的基本概念与性质同余的基本概念与性质性质2.2 （7）若 （8）（补充）若 ，则(a,m)=(b,m) 例作业(1):p57 第1题 NmniNmi,1,)(mod mba ),(mod)(mod1nimmbamba)(modmod).(

5、mod()(modmmbmamab2.1 同余的基本概念与性质同余的基本概念与性质 作业(2):p57 第5题2.1 同余的基本概念与性质同余的基本概念与性质问题： 一个十进制数，什么时候能被3整除结论：当各位和为3的倍数时如：248901why ？2.1 同余的基本概念与性质同余的基本概念与性质关键：10=33+1，100=33 3+1， 所以：若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)

6、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 同余的基本概念与性质同余的基本概念与性质补充，性质2.2（7）的特殊情况v（1）若vP,q不同素数， )(mod pba )(mod qba )(mod pqba 2.1 同余的基本概念与性质同余的基本概念与性质例：p

7、,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=32.1 同余的基本概念与性质同余的基本概念与性质（补充） ， 则存在唯一 使 因为存在ax+my=1 即 ax-1=my 若存在x1和x2两个逆元，则x1*a*x2x1x2(mod m)如若(a,m)1，则a-1不存在1),( ,maZa1a)(mod111maaaa2.1 同余的基本概念与性质同余的基本概念与性质求5模11的逆元11=5*2+1 5*2-1(m

8、od 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) ，所以x36-

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

10、素 rear=(rear+1)% max_sizev删除元素 front=(front+1)% max_sizev什么时候为空？ 什么时候为满v元素数量最多为 max_size-12.2 同余的应用同余的应用随机数（Random Number）n什么是随机数n有什么用：仿真、游戏、协议、密码nsrand(seed) int rand(viod)n产生方法：利用随机过程事先定制好的随机数表利用数学递推公式模拟 伪随机数（Pseudo-Random Number)随机数（Random Number）n伪随机数产生方法迭代取中法：代表性为平方取中乘同余线性乘同余，也叫混合同余改进：2.2 同余的应用

11、同余的应用)10)(mod10/(221ssnnII)(mod1mILInnmcaIInnmod)(13112mod)65539(nnII1961年由IBM提出mIbIaInnnmod)(212.2 同余的应用同余的应用仿射密码 Affine Ciphernyax+b(mod26)尝试解密：casear 考虑编程的解法nLXWPAJCDUJCRXWBnyx+3(mod 26)凯撒密码 Caesar Ciphern移位密码、加法密码2.2 同余的应用同余的应用0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 78 89 9 101011 1112121313141415150 04 4

12、8 812121 15 59 913132 26 6101014143 37 711 1115150 04 48 812125 59 913131 1101014142 26 615153 37 711 11循环左移循环左移1字节字节循环左移循环左移2字节字节循环左移循环左移3字节字节h h e e l ll lo o ww o o r rl ld db by ye eb by ye eh ho ol le ewwd db be eb by yl lo oe el lr ry y2.3 剩余类（系）剩余类（系） Residue同余是一种等价关系 =可以借助同余实现划分 令Ca=c| 定理2-1

13、 n(1)任意整数都包含于一个Cr中，0rm-1n(2)Ca=Cb n(3)要么 Ca=Cb ，要么CaCb =n(4)两两不同的Cr最多m个ZaNm,)(mod,mcaZc)(mod mba 0 04 48 812121 15 59 913132 26 61010 14143 37 711 1115152.3 剩余类（系）剩余类（系） Residue定义2.2.1nCa叫模m的一个剩余类，Ca中的任一数叫该类的代表元（ ），若 为m个整数，并且其中任两个数都不在同一个剩余类中， 叫模m的一个完全剩余系，若（r,m）=1,则这样的剩余类叫做模m的简化（紧缩/既约）剩余系,缩系元素的个数叫做欧拉

14、函数 (m)110,mrrr110,mrrra0 04 48 812121 15 59 913132 26 61010 14143 37 711 1115152.3 剩余类（系）剩余类（系） Residue2.3 剩余类（系）剩余类（系） Residue2.3 剩余类（系）剩余类（系） Residue例: a1,a2，an是一个模n的完系，则 ak 0 (mod n) n=2k+1 n/2(mod n) n=2kak 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 剩余类（系）

15、剩余类（系） Residue例2-10: a1,a2，an，b1,b2，bn是两个模n的完系，证明：当m是偶数时，a1+b1,a2+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/22.3 剩余类（系）剩余类（系） Residue例：将1(mod 5)写成模15的剩余类的和例：写出模9的完系，要求全

16、是奇数对于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为一个完系Nm2m1),( , 11:)(1:mlmllmkrkmaaa,21mnanana,21)(21,maaa

17、)(21,mnananamaaa,21)(21,maaa,)(21)(21mmrrraaamaaa,21,)(21)(_21mmrrrnanana)(21,maaa1, 1 , 0,_)_21mnananam1, 1 , 0,_21maaamZb2.3 剩余类（系）剩余类（系） Residue定理2-2 有所以2.3 剩余类（系）剩余类（系） Residue定理2-32.3 剩余类（系）剩余类（系） Residue2.3 剩余类（系）剩余类（系） Residue2.3 剩余类（系）剩余类（系） Residue定理2-4 若（m,n）=1那么 呢？)()()(nmmn)20()5()4()20(

18、2.3 剩余类（系）剩余类（系） Residue关键nn=pn时，其缩系的元素？n排除与其最大公约数大于1的,也就是该数为xpn(0,n-1)中，非缩系元素最小为0,最大pn-p,x取值0到pn-1 1，共pn-1个所以 ，如 =22-2=2)(np1)(nnnppp)4(2.3 剩余类（系）剩余类（系） Residue作业(6)： 用上面的方法计算 24的欧拉函数定理2-5 欧拉函数的计算np素1)1 ()11 ()()(,21111isieieisieisipnppnpnniii则时，1)11 ()(pppp1)11 ()(llllppppp)()(1llppp2.3 剩余类（系）剩余类（

19、系） 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，得证ndZndnd0,|)(,1)1 (0,|) /(dnddnn2.3 剩余类（系）剩余类（系） Residue2.3 剩余类（系）剩余类（系） Residue2.3 剩余类（系）剩余类（系） Residue例2-

20、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(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

21、 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 剩余类（系）剩余类（系） 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

22、,ap-1和b1,bp-1是模p的两组简化剩余系但a1ap-1 -1(modp) b1bp-1 -1(modp) 与 a1b1ap-1bp-1 -1(modp) 矛盾2.4 剩余类（系）的应用剩余类（系）的应用Hash(散列)函数n就是把任意长的输入字符串（预映射，Pre-image）变换成固定长（一般更短）的输出字符串n单向：多到一 = 碰撞（collision）必然存在n也叫压缩函数、缩短函数、消息摘要、指纹、密码校验和、信息完整性检验（DIC）、操作检验码（MDC）n著名的：MD5，SHA-1nMOD可以实现2.4 剩余类（系）的应用剩余类（系）的应用Hash函数是公开的，对处理过程不用

23、保密n安全性是它的单向性：输出不依赖于输入n预映射单个比特的改变，平均而言，将引起hash值中一半的比特改变。n已知一个hash值，要找到预映射的值，使它的hash值等于已知的hash值在计算上是不可行的。优良hash函数的条件：n已知输出，求输入困难:单向性。 n已知输入计算输出容易的:快速性。 n已知x，构造y使Hash（x）=hash(y)困难:抗碰撞性。 n输出的每一比特都与输入的每一比特有关，输入每改变一比特，都将对输出产生明显影响：雪崩性。 2.4 剩余类（系）的应用剩余类（系）的应用应用领域n密码学：特别是数字签名n密码保存n下载软件：emule：校验和标示n微支付：例如基于冲突

24、的micromint和基于hash链的支付paywordn文件系统：物理组织2.4 剩余类（系）的应用剩余类（系）的应用文件系统：物理组织n文件的组织形式：逻辑组织：用户看到的文件组织形式物理组织：逻辑组织到磁盘块的映射=地址映像n物理组织：顺序、链式、索引、hash结构nHash结构hash(key)=addr (在磁盘或文件中的存放位置)问题：冲突.文件空间空闲标志冲突记数记录内容记录内容空闲标志冲突记数记录内容记录内容Hash(key)=addr起始位置计算addr=hash(key)对应冲突记数加1本记录空闲顺取下一个标记为占用填记录内容保存记录：TF查找记录：计算addr=hash(

25、key)取addr对应记录的冲突记数countcount=0无此记录本记录空闲顺取下一记录key相等找到 hash(key)相等count:=count-1count=0无此记录顺取下一记录TFFTTFTFTF删除记录：调用查找过程(key)找到错误返回置空闲标志(找到记录)冲突记数-1对应hash(key)特点：按关键字检索速度非常快。用途：常用于目录检索。注意：文件可循环使用，满时保存失败。2.5 欧拉定理与费马小定理欧拉定理与费马小定理2.5 欧拉定理与费马小定理欧拉定理与费马小定理2.5 欧拉定理与费马小定理欧拉定理与费马小定理需要指出： 26 1(mod 7)，6并不是满足条件的最小

26、数, 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(mod 19)因为72(-8)(mod 19) x13*7*224-4*36 -4*7 10(mod 19)2.5 欧拉定理与费马小

27、定理欧拉定理与费马小定理计算31000000(mod 47)n1000000(mod 46)6 n原式36-13*9 -117 24(mod 47)作业(7)：计算 245678(mod 13), p58第19题(1)2.5 欧拉定理与费马小定理欧拉定理与费马小定理2.5 欧拉定理与费马小定理欧拉定理与费马小定理求证：3n5+5n3+7n 0(mod 15)n3n50 5n32n 7nn (mod 3) n3n53n 5n30 7n2n (mod 5) 2.5 欧拉定理与费马小定理欧拉定理与费马小定理例：证97104-1能被105整除就是要证97104 1（mod 105） 因为(97,105

28、)=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年提出机制：n(1)选择两个大素数p和q；n(2)计算n=pq,则 (n)=(p-1)(q-1)；n(3)随机选择一整数e，0e (n),满足( (n)，e)=1；n(4)计算d，满足de1(mod (n)n(5)d保

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

30、，一般的，an时间复杂度为O(logn)2.6 RSA公钥密码机制公钥密码机制第二种算法与二进制的关系n9=(1001)2， a9=(12*a)2)2)2*an10=(1010)2， a10=(12)*a)2)2*a)2从二进制第一位开始，遇到1就先平方乘以a，遇到0就直接平方2.6 RSA公钥密码机制公钥密码机制如何计算ab mod nnBR算法 Binary Representationn中国剩余定理能提高速度，下节内容n作业(9):p58 第20题d 1for i k down to 0 d (d * d) mod n if bi = 1then d (d * a) mod nretur

31、n d2.6 RSA公钥密码机制公钥密码机制公钥发布n当要通信时向对方索要其公钥可能假冒，因此仍需要额外的可信保障扩散n通过可信的朋友之间的辗转交换，如PGP(Pretty Good Privacy)n公开的目录服务目录的维护得由信得过的机构执行每个用户在目录里有一项身份信息，其公钥 n证书中心CA(Certificate Authentication )PKI的核心2.6 RSA公钥密码机制公钥密码机制RSA可能受到的攻击n枚举枚举所有可能明文m，用e加密和c比较枚举所有可能的私钥dn数学方法分解n=pq，就可以计算(n)，就可从e求得d不分解n，而直接求(n)，再求d 不求(n)，直接求d

32、2.6 RSA公钥密码机制公钥密码机制从攻击对象：n对RSA的定点攻击n对RSA的共模攻击n对RSA的选择密文攻击n对RSA的小加密指数攻击n对RSA的小解密指数攻击n时间性攻击：取决于解密算法的运算时间2.6 RSA公钥密码机制公钥密码机制定点攻击n第三者截获密文C后，反复计算e次幂 ce me2 ce2 me3 （mod n）一旦 cet c me（mod n） = m cet-1 （mod n） nt不是很大时这种攻击可行n如何避免？如何让t很大？今后分解 2.6 RSA公钥密码机制公钥密码机制选择密文攻击n利用同态：Ek(x1x2)=Ek(x1)Ek(x2)n例1：m3 m1m2(mo

33、d n),让A给其中两个签名就能够得到其对第3个的签名n例2：收集到用A公钥加密的密文C，想要得到明文M 他首先选择随机数r,使r=2, ，则同余方程组 解为 kiimM1kkamxamxamxmodmodmod2211iiiikkkmMmMMMaMmMaMmMaMmMxmod1mod)(222111满足kmm,12.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

34、=5*6*7=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)所以，对

35、于其他方程组，这个x同余于0，可以直接加其实 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 孙子定理孙子定理练习解方程组：n7x5(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

36、)可以推出7x5(mod 3)即x2(mod 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网络热身赛网络热身赛青蛙的约会 两只青蛙在网上相识了，觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点

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

38、，并让他重新建立猪圈。这回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(mod 1081) 变成“3”解密：m51675(mod 1081) m51675(46+5)22*30+155155*2575*2720*32-4(mod23)m51675(

39、47+4)46*14+3126221621218(mod47)直接使用孙子定理 m-4*47*1+18*23*(-2)-1016 65(mod 1081)2.5 加速加速RSA的实现速度的实现速度Java DocumentC#nRSAParameters 1p) 1(modpd) 1(mod qd2.5 加速加速RSA的实现速度的实现速度分析n对N求模，现在变成了对P和Q求模, 余数的大小是P和Q的剩余系里的数了。按位数来算，现在的乘数的二进制位数是原来乘数的二进制位数的一半n根据理论分析，用了中国剩余定理后，RSA 的速度又提高了约50%2.5 加速加速RSA的实现速度的实现速度可能受到出错

40、攻击n设备可能出错n此时如果Cp计算错误，而Cq计算正确，则可以分解n若Cp被计算成Cp，最终计算的C变成C, =M(mod n)则 M-M 0(mod q) M-M 0(mod p)所以gcd(M-M),n)=q其中eC )(2.6 群签名方案群签名方案中国剩余定理最主要的价值在于将单个方程式和一个方程组等价起来若干用户组成一个群体，使用相关的签名方案群中心负责为群管理员和群成员分配秘钥，群管理员则在必要的时候打开签名确定签名者的身份。可用在电子投票、电子拍卖等领域一个基本的群签名应具有n匿名性即同一个群中的成员不能识别其他群成员的签名; n不相关性即决定两个不同的签名是否来自于同一个人计算

41、上是不可行的; n不可伪造性即任何多个群成员不能伪造其他成员的签名。2.6 群签名方案群签名方案签名机制n秘钥生成群中心随机地生成两个大素数 p，q，计算n=pq，选择公开hash函数h(x)选择 ，并求d，使随机选择 ,使 选择素数 ,且 ,将( )送给用户 做密钥 验证 ，以确信消息是群中心送来的群中心将( )送给群管理员，其中 是群成员的身份。设系统有k个成员，群中心利用中国剩余定理，可求同余方程组： 的解C 群中心将（n,e,c）作为公钥，（d,p,q）为群中心的私钥 nZe)(mod1nedniiZyx,)(mod1nyxiiiiyp jippji 时，idiippx,iUiU)(m

42、od)(nppediiiiyID ,iID2.6 群签名方案群签名方案签名机制n成员的加入和撤销 在有成员加入或撤销时，群中心只需重新求解c 的值并公布出去，而不必改变其他群成员的秘钥。n签名 群成员 要对消息m签名,首先计算h(m),再计算 则 即为 的签名。n验证 若Alice 要对 的签名 进行验证，Alice利用群公钥e 计算： ，得到 ，然后验证： 是否成立。若成立，签名合法，否则不接受签名。群管理员通过 对应的IDi确定签名者的身份。iUiUiUiyiy2.6 群签名方案群签名方案可能遭受的攻击n群中心伪造群成员的签名 显然该方案中群中心知道所有的群成员的签名秘钥，因此一个不诚实的

43、群中心可以伪造其他群成员的合法签名而不被发现n联合攻击假设群成员 联合对方案攻击，他们分别掌握 可知 为 和 为的公因子联合人越多成功的可能越大 也可以自己通过多次加入群实现jiUU ,)(mod111nyx)(mod122nyx)(n111yx122yx总结总结同余：余数相同，关注余数，离不开除数n一定是模m的意义下同余ab (mod m) m|a-ba=b+km非常类似于=n=：左右可以同时加减乘除同一个数，但不能除以0n:同一个m，左右可以同时加减乘除同余的数但不能除以与0同余的数 如1428(mod7)不能=24(mod7)除了以后仍然得为整数n:a,b不变，m变m可以变成其一个因子，

44、等式仍然成立M可分解成n个不同的素数：方程与方程组的互化逆元练习练习一般技巧n同时减去同余于0的数的倍数，即模m的倍数n将几个乘数凑成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)(a-c)(a-d)(b-c)(b-d)(c-d)只

45、需证明 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的剩余类：n同余的归一类：2类或者完全一样，或者完全不同n完全不同的最多m个：完全剩余类模m的剩余系n每个剩余类中找出一个代表元，组成一个系n完全剩余类 完系，0

46、，1，,m-1n紧缩剩余类 缩系, (m)n缩系最大的价值：每个元素都有逆元nm为素的价值：完系-0就是缩系0 04 48 812121 15 59 913132 26 61010 14143 37 711 111515总结总结关于缩系与完系的定理 模mn都可统一到0到m-1之间，简化nx遍历缩（完）系，则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 04 48 812121 15 59 913132

47、 26 61010 14143 37 711 111515总结总结技巧n不规则的数简化为0，1，m的形式n要证完系，分别证有m个，两两不同余n要证缩系，先证完系，在证与m互质练习练习证明：当m2时，02,12,(m-1)2一定不是模m的完全剩余系。nm个,所以只需证存在两个同余n(m-1)2=m2-2m+11(mod m)类似：m个整数，都不属于剩余类0(mod m) 则其中必有2个数属于同一剩余类练习练习求证：模m简化剩余系每个元素的和模m与0同余n若r为模m的简化剩余，则m-r也是n所以，可以两两凑对求和，每对和与0同于总结总结欧拉函数的计算n公式：n更常用两个：(m,n)=1时 和)()

48、()(nmmn)11 ()(1isipnn1)(nnnppp总结总结Wilson定理n(p-1)! -1(mod p) p是素数判断素数的方法之三n之一：用不大于sqrt(n)的质数试除（3,i+=2）n之二：爱托拉斯散筛法总结总结欧拉定理费马小定理技巧：n指数化简，指数中减去欧拉函数的倍数n模若为合数，先分离成多个模互质的方程练习练习证明：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时是不成立注

49、意：欧拉定理与费马小定理的不同之处总结总结应用：判断素数的方法之四n首先计算2n，若模n是否同余于2注意：此时的判断方法与费马小定理的推理正好相反。如果p质数则成立 vs. 如果成立，则p是质数所以只能排除合数，并不能肯定素数伪素数总结总结应用：RSAn(1)选择两个大素数p和q；n(2)计算n=pq,则 (n)=(p-1)(q-1)；n(3)任选整数e，0e 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

50、 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*10*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，所以考虑