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

学习目标掌握同余、剩余类（系）、欧拉函数、费马定理、孙子定理了解同余理论和孙子定理在计算机和密码学的应用课程内容的设置同余的基本概念、性质和应用剩余类、完全剩余系、简化剩余系及应用欧拉函数、费马定理及应用孙子定理同余式2.0问题的提出50天后星期几？234567天后呢？计算机中的溢出问题循环队列的的实现？%数学中的同余整除中：a=qb+r0≤r<b：同余就是余相等如：19=12*1+77=12*0+72.0问题的解决——同余理论07012)7-127112)192.1同余的基本概念与性质定义2.1.1,若r1=r2,则称a，b模m同余：也记为：或2.1同余的基本概念与性质例：27≡?(mod7)253天后星期几？同时：a≡r(mod7)0≤r<7a->r是一个满射因此：可以按不同的余数对整数分类，也就是每一类余数相同，也就是同余23=8≡1(mod7)所以253≡23*17+2≡4(mod7)2.1同余的基本概念与性质定理2.1.1同余关系是一种等价关系：自反性：对称性：则传递性：则2.1同余的基本概念与性质例:证明(mn-1,m3)=1证：设（mn-1,m3）=p所以mn-1≡0(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=12.1同余的基本概念与性质性质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=3×3+1，100=33×3+1，……所以：若n=am10m+am-110m-1+…+a110+a0

3|n<=>3|am+am-1+…+a1+a0

2.1同余的基本概念与性质例：快速判断某个数整除7的余数？10≡3(mod7),100≡30≡2(mod7),1000≡20≡-1(mod7)10002k+1≡-1(mod7),10002k≡1(mod7)若n=am1000m+am-11000m-1+…+a11000+a0对于637692≡692-637=55=6(mod7)2.1同余的基本概念与性质扩展：怎样快速判断一个数可以被19整除？提示：凑成19的倍数2位数字？多于2位时？作业(3)：怎样快速判断一个数可以被31整除？,p57第3题2.1同余的基本概念与性质补充，性质2.2（7）的特殊情况（1）若P,q不同素数，2.1同余的基本概念与性质例：p,p+10,p+14均是素数？求p因为10=2*5，14=2*7，所以p≠2,5,7对于p=3，若p≡1(mod3)，则p+14≡0(mod3)，排除若p≡2(mod3)，则p+10≡0(mod3)，排除所以p≡0(mod3)因为p素，所以p=32.1同余的基本概念与性质（补充），则存在唯一使

因为存在ax+my=1即ax-1=my若存在x1和x2两个逆元，则x1*a*x2≡x1≡x2(modm)如若(a,m)≠1，则a-1不存在2.1同余的基本概念与性质求5模11的逆元11=5*2+15*2≡-1(mod11)5*(-2)≡1(mod11)5模11的逆元为-2（但更常写为9）求233模1211的逆元1211=233*5+46233=46*5+346=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(mod19)19=17+217=8*2+1所以17*9-19*8=1所以17*9≡1(mod19)因为(4,9)=1所以17*36≡4(mod19)，所以x≡36≡-2(mod19)作业(4):p59第25题(1)(3)2.2同余的应用主要应用补码、随机数、文件系统、hash、密码、检错码等编程时求余的主要实现modexcel、vb、asp、delphi、vfp等%c、c++、c#、java等2.2同余的应用补码Two’scomplement为什么会有补码如何计算口诀原理：异或：模2加2.2同余的应用循环队列数组queue[max_size]队首指针front，指向队首元素的前一个位置队尾指针rear，指向队尾元素初始化front=rear=0插入元素rear=(rear+1)%max_size删除元素front=(front+1)%max_size什么时候为空？什么时候为满元素数量最多为max_size-12.2同余的应用随机数（RandomNumber）什么是随机数有什么用：仿真、游戏、协议、密码……srand(seed)intrand(viod)产生方法：利用随机过程事先定制好的随机数表利用数学递推公式模拟伪随机数（Pseudo-RandomNumber)随机数（RandomNumber）伪随机数产生方法迭代取中法：代表性为平方取中乘同余线性乘同余，也叫混合同余改进：2.2同余的应用1961年由IBM提出2.2同余的应用仿射密码AffineCiphery≡ax+b(mod26)尝试解密：casear考虑编程的解法LXWPAJCDUJCRXWBy≡x+3(mod26)凯撒密码CaesarCipher移位密码、加法密码ABCDEFABCDEFXYZWXYZABCZABCDEF2.2同余的应用012345678910111213141504812159132610143711150481259131101426153711循环左移1字节循环左移2字节循环左移3字节helloworldbyebyeholewdbebyloelry2.3剩余类（系）Residue同余是一种等价关系=〉可以借助同余实现划分令Ca={c|}定理2-1(1)任意整数都包含于一个Cr中，0≤r≤m-1(2)Ca=Cb<=>(3)要么Ca=Cb，要么Ca∩Cb=Ø(4)两两不同的Cr最多m个04812159132610143711152.3剩余类（系）Residue定义2.2.1Ca叫模m的一个剩余类，Ca中的任一数叫该类的代表元（），若为m个整数，并且其中任两个数都不在同一个剩余类中，叫模m的一个完全剩余系，若（r,m）=1,则这样的剩余类叫做模m的简化（紧缩/既约）剩余系,缩系元素的个数叫做欧拉函数(m)04812159132610143711152.3剩余类（系）Residue2.3剩余类（系）Residue2.3剩余类（系）Residue例:a1,a2，…，an是一个模n的完系，则∑ak≡0(modn)n=2k+1n/2(modn)n=2k∑ak≡1+2+…+n≡n(1+n)/2（modn）若n=2k+1则，∑ak≡n*(k+1)≡0(modn)若n=2k则，∑ak≡k*(n+1)≡k(modn)2.3剩余类（系）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是在1~m/2和m互素的整数所以，ai和m-ai组成了m的最小正简化剩余系共ψ(m)/2对，和为mψ(m)/2思考：为什么没有考虑m/22.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-32.3剩余类（系）Residue2.3剩余类（系）Residue2.3剩余类（系）Residue定理2-4若（m,n）=1那么呢？2.3剩余类（系）Residue关键n=pn时，其缩系的元素？排除与其最大公约数大于1的,也就是该数为xp(0,n-1)中，非缩系元素最小为0,最大pn-p,x取值0到pn-1–1，共pn-1个所以，如=22-2=22.3剩余类（系）Residue作业(6)：用上面的方法计算24的欧拉函数定理2-5欧拉函数的计算p素2.3剩余类（系）Residue定理2-6设m是1,2,…,n中的任一数，可以按照(m,n)的不同对1,2,…,n分类,则n的正因子的个数即为类的个数（因为m≤n）,各类中正整数个数之和为n。设d’为n的一个正因子，若(x,n)=d’，则(x/d’,n/d’)=1，由于x/d’≤n/d’,所以1,2,…,n中满足x的个数等于1,2,…,n/d’中，满足(y,n/d’)=1的y的个数，故有(n/d’)个。因此，记d=n/d’，得证2.3剩余类（系）Residue2.3剩余类（系）Residue2.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剩余类（系）Residue2.3剩余类（系）Residue推论：如果(p-1)!≡-1(modp)，则p是素数反证：如果p=ab，a,b>=2则(ab-1)!≡-1(modab)，则(ab-1)!≡-1(moda),(ab-1)!≡-1(modb)因为a<ab-1,所以a|(ab-1)!所以(ab-1)!≡0(moda)矛盾2.3剩余类（系）Residue例2-17设p为奇素，求证∏k2≡(-1)(p+1)/2(modp)其中1≤k≤p-2,k≡1(mod2)考虑-1(modp)是与(n-1)!同余，所以凑k≡-(p-k)(modp)而k是奇，p-k就是偶所以∏k2≡∏k∏[-(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的两组简化剩余系但a1…ap-1≡-1(modp)b1…bp-1≡-1(modp)

与a1b1…ap-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本记录空闲顺取下一个标记为占用填记录内容保存记录：TF查找记录：计算addr=hash(key)取addr对应记录的冲突记数countcount=0无此记录本记录空闲顺取下一记录key相等找到

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

≡1(mod7)，6并不是满足条件的最小数,23

≡1(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,ax≡b(modn)解为x≡baφ(n)-1(modn)例:求解7x≡13(mod19)

x≡13*717(mod19)因为72≡(-8)(mod19)x≡13*7*224≡-4*36≡-4*7≡10(mod19)2.5欧拉定理与费马小定理计算31000000(mod47)1000000(mod46)≡6原式≡36≡-13*9≡-117≡24(mod47)作业(7)：计算245678(mod13),p58第19题(1)2.5欧拉定理与费马小定理2.5欧拉定理与费马小定理求证：3n5+5n3+7n≡0(mod15)3n5≡05n3≡2n7n≡n(mod3)3n5≡3n5n3≡07n≡2n(mod5)2.5欧拉定理与费马小定理例：证97104-1能被105整除就是要证97104≡

1（mod105）因为(97,105)=1105=3*5*7，所以(105)=2*4*6=4897104≡9748*2+8≡978(mod105)978≡1(mod3)，978≡1(mod5)，978≡972≡(-1)2(mod7)所以978≡1(mod105)成立作业(8):p58第24(4)题2.6RSA公钥密码机制麻省理工学院的Rivest、Shamir和Adleman三人研究小组于1978年提出机制：(1)选择两个大素数p和q；(2)计算n=p×q,则(n)=(p-1)×(q-1)；(3)随机选择一整数e，0<e<(n),满足((n)，e)=1；(4)计算d，满足de≡1(mod(n))(5)d保密，(d,n)是私钥；发布(e,n)是公钥；销毁p,q(6)若m表示明文，用c表示密文(m和c均小于n)，则加密：；解密：2.6RSA公钥密码机制实现中的问题（1）如何计算abmodn（2）如何判定一个给定的整数是素数？（3）如何找到足够大的素数p和q?2.6RSA公钥密码机制如何计算abmodn1）计算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.6RSA公钥密码机制第二种算法与二进制的关系9=(1001)2，a9=(((12*a)2)2)2*a10=(1010)2，a10=((((12)*a)2)2*a)2从二进制第一位开始，遇到1就先平方乘以a，遇到0就直接平方2.6RSA公钥密码机制如何计算abmodnBR算法BinaryRepresentation中国剩余定理能提高速度，下节内容作业(9):p58第20题d1forikdownto0d(d*d)modnifbi=1 thend(d*a)modnreturnd2.6RSA公钥密码机制公钥发布当要通信时向对方索要其公钥可能假冒，因此仍需要额外的可信保障扩散通过可信的朋友之间的辗转交换，如PGP(PrettyGoodPrivacy)公开的目录服务目录的维护得由信得过的机构执行每个用户在目录里有一项{身份信息，其公钥}证书中心CA(CertificateAuthentication)PKI的核心2.6RSA公钥密码机制RSA可能受到的攻击枚举枚举所有可能明文m，用e加密和c比较枚举所有可能的私钥d数学方法分解n=pq，就可以计算φ(n)，就可从e求得d不分解n，而直接求φ(n)，再求d不求φ(n)，直接求d2.6RSA公钥密码机制从攻击对象：对RSA的定点攻击对RSA的共模攻击对RSA的选择密文攻击对RSA的小加密指数攻击对RSA的小解密指数攻击时间性攻击：取决于解密算法的运算时间2.6RSA公钥密码机制定点攻击第三者截获密文C后，反复计算e次幂ce≡

me^2ce^2≡me^3……（modn）一旦ce^t≡c≡me（modn）=〉m≡ce^t-1（modn）

t不是很大时这种攻击可行如何避免？如何让t很大？今后分解

2.6RSA公钥密码机制选择密文攻击利用同态：Ek(x1x2)=Ek(x1)Ek(x2)例1：m3≡

m1m2(modn),让A给其中两个签名就能够得到其对第3个的签名例2：收集到用A公钥加密的密文C，想要得到明文M他首先选择随机数r,使r<n.然后用A的公开密钥e计算x≡remodn y≡xc

modn让A对y签名，得到u≡ydmodnr-1ydmodn≡r-1xdcdmodn≡cdmodn≡m不要用RSA对陌生人的随机文件签名，签名前先使用一个散列函数2.6RSA公钥密码机制共模攻击如果相同的消息曾用两个不同的指数加密，而这两个指数是互素、加密的用户共模，则明文可以不用任何一个解密密钥来恢复。设用户的公开密钥分别为e1,e2,且e1,e2互素，明文消息为m,密文为C1≡me1modnC2

≡me2modn因为（e1,e2)=1, r*e1+s*e2=1假定r为负数则：(C1-1)r*C2s=mmodn所以：不要共模2.6RSA公钥密码机制总结加/解密、密钥交换、数字签名使用最广泛注：实际使用时RSA加密的一般不是直接的明文，而是会话密钥，然后用对称算法加解密公钥算法加密解密速度慢误区:公开密钥密码算法更安全公开密钥密码使对称密钥密码过时了公钥的分发是简单和一目了然的2.5同余方程的一般理论2.5同余方程的一般理论2.5同余方程的一般理论2.5同余方程的一般理论2.5同余方程的一般理论法二：直接删除x4化为：≡3x2+4x+2x3+x+x2+x3+2x2+x≡3x3+x2+x(mod5)问题的提出代数的主要问题就是解方程隋朝之前有部《孙子算经》提出“物不知数”问题：今有物不知数，三三数之有二，五五数之有三，七七数之有二，问物有几何韩信点兵有兵一队，若列成五行，末行一人，若列成六行，末行五人，列成七行，末行四人，列成十一行，末行十人，求兵数解决：大衍求一术，鬼谷算天文、历法的需要中国剩余定理ChineseRemainderTheorem

Letnbeapositiveintegersuchthatitleavestheremainders2,3,2whenitisdividedby3,5,7respectively.Findn.最简单直接的方法：

Sincen=3k+2willleaveremainder2whenitisdividedby3,n=2,5,8,11,14,17,20…….Wefoundthatn=8cansatisfythefirsttwoconditionsbutnotthethirdone.AstheL.C.M.of3,5is15,weaddthenumber8by15eachtimeuntilwegetoursolutions.n=23Anyothersolutions?GeneralSolutions?2.7孙子定理2.3孙子定理明朝程大位《算数统筹》：三人同行七十稀，五树梅花甘一枝，七子团圆整半月，除百零五便得知。

2.3孙子定理利用算式表示：２７０＋３２１＋２１５＝２３３再把２３３－１０５－１０５＝２３233+105n均是答案

３除余数５除余数７除余数７０１００２１０１０１５００１

３除余数５除余数７除余数７０２２００２１３０３０１５２００２２３３２＋０＋０＝２０＋３＋０＝３２＋０＋０＝２三人同行七十稀五树梅花甘一枝七子团圆整半月除百零五便得知2.3孙子定理把问题一般化如何找70、21、15

３除余数５除余数７除余数７０１００２１０１０１５００１

３除余数５７＝３５除余数35x=3y+1１０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=385M3=2310/7=5*6*11=330;M4=2310/11=5*6*7=210第3步：求出逆元Mi-1考虑Mi*x≡Mibi(modM)x≡Mi-1Mibi

(modM)但上面Mi-1是不存在的，因为（M,Mi）=M/mi，但（mi,Mi）=1Mi*x≡Mibi(modM)=>Mi*x≡Mibi(modmi)=>x≡MibiMi-1(modmi)所以求出：462*3≡1(mod5)变成x≡462*1*3(mod5)同理：x≡385*5*1(mod6);x≡330*4*1(mod7);x≡210*10*1(mod11)2.3孙子定理第4步：求出解考虑x≡462*3(mod5)：此时的x≡0(mod6)\(mod7)\(mod11)所以，对于其他方程组，这个x同余于0，可以直接加其实x≡MibiMi-1(modmi)其他mj都|Mi因此下面的解满足各方程x≡462*3+385*5*1+330*4*1+210*10*1(mod2310)≡6731≡2111(mod2310)2.3孙子定理练习解方程组：7x≡5(mod18);13x≡2(mod15)首先7x≡5(mod18)化为：7x≡5(mod2)和7x≡5(mod9)即：x≡1(mod2)和7x≡5(mod9)13x≡2(mod15)化为:13x≡2(mod5)和13x≡2(mod3)即：3x≡2(mod5)和x≡2(mod3)对于7x≡5(mod9)可以推出7x≡5(mod3)即x≡2(mod3)所以只有3个：3x≡2(mod5)，x≡1(mod2)和7x≡5(mod9)解：x≡4*2*2*9+1*1*5*9+2*1*5*2≡209≡29(mod90)作业：P59第34题系数都化为1:x≡4(mod5)，x≡1(mod2)和x≡2(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加密：c≡653≡51(mod1081)变成“3”解密：m≡51675(mod1081)m≡51675≡(46+5)22*30+15≡515≡5*257≡5*27≡20*32≡-4(mod23)m≡51675≡(47+4)46*14+31≡262≡216≡212≡18(mod47)直接使用孙子定理m≡-4*47*1+18*23*(-2)≡-1016≡65(mod1081)2.5加速RSA的实现速度JavaDocumentC#RSAParameters2.5加速RSA的实现速度分析对N求模，现在变成了对P和Q求模,余数的大小是P和Q的剩余系里的数了。按位数来算，现在的乘数的二进制位数是原来乘数的二进制位数的一半根据理论分析，用了中国剩余定理后，RSA的速度又提高了约50%2.5加速RSA的实现速度可能受到出错攻击设备可能出错此时如果Cp计算错误，而Cq计算正确，则可以分解n若Cp被计算成Cp’，最终计算的C变成C’,=M’(modn)则M-M’≡0(modq)M-M’≡0(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群签名方案可能遭受的攻击群中心伪造群成员的签名

显然该方案中群中心知道所有的群成员的签名秘钥，因此一个不诚实的群中心可以伪造其他群成员的合法签名而不被发现联合攻击假设群成员联合对方案攻击，他们分别掌握可知为和为的公因子联合人越多成功的可能越大也可以自己通过多次加入群实现总结同余：余数相同，关注余数，离不开除数一定是模m的意义下同余a≡b(modm)<=>m|a-b<=>a=b+km≡非常类似于==：左右可以同时加减乘除同一个数，但不能除以0≡:同一个m，左右可以同时加减乘除同余的数但不能除以与0同余的数如14≡28(mod7)不能=>2≡4(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=15≡3*1515-2*153-2(mod7)≡3*115-2*13-2(mod7)

≡-1(mod7)类似：求解123456789(mod7)练习例：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就是缩系0481215913261014371115总结关于缩系与完系的定理模m都可统一到0到m-1之间，简化x遍历缩（完）系，则ax+b也遍历，其中（a,m）=1结合右图扩展：a也是缩系中的一员，若b=0，如对于72*1≡2

2*2≡42*3≡62*4≡12*5≡32*6≡5(mod7)可形成分离的循环1*2≡2

2*2≡44*2≡1；

2*3≡62*6≡52*5≡30481215913261014371115总结技巧不规则的数简化为0，1，…，m的形式要证完系，分别证有m个，两两不同余要证缩系，先证完系，在证与m互质练习证明：当m>2时，02,12,…,(m-1)2一定不是模m的完全剩余系。m个,所以只需证存在两个同余(m-1)2=m2-2m+1≡1(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整数，a7≡a(mod63)首先63=7*9，所以分解：先证a7≡a(mod7)，直接根据费马定理再由于(9)=9-3=6，所以若(a,9)=1或9时，a7≡a(mod9)

若(a,9)=3，a2k≡0(mod9)

所以(a,9)=3时是不成立注意：欧拉定理与费马小定理的不同之处总结应用：判断素数的方法之四首先计算2n，若模n是否同余于2注意：此时的判断方法与费马小定理的推理正好相反。如果p质数则成立vs.如果成立，则p是质数所以只能排除合数，并不能肯定素数伪素数总结应用：RSA(1)选择两个大素数p和q；(2)计算n=p×q,则(n)=(p-1)×(q-1)；(3)任选整数e，0<e<(n),满足((n)，e)=1；(4)计算d，满足de≡1(mod(n))(5)(d,n)是私钥；发布(e,n)是公钥；销毁p,q(6)m表