应用密码学-2016-(第4讲)

应用密码学,计算机科学与技术学院田秀霞83876668,第四讲同余与同余式,本章主要内容,1同余及其基本性质2剩余类与剩余系3几个著名定理4RSA公钥密码体制5同余式与一次同余式6中国剩余定理,4.1同余及其基本性质1.xymodmx模m同余y这种关系叫模m的同余。等价的说法有xymodm当且仅当m|x-y。2.同余的性质对于固定的整数m，模m同余是一个等价关系。自反性：对于任意的x，总有xxmodm；对称性：xymodmyxmodm；传递性：xymodm,yzmodmxzmodm。其他性质：(1)xymodmaxaymodm,xayamodm；(2)xymodmaxaymodam,a0；(3)(ab)modm(amodmbmodm)modm。,第四讲同余,第四讲同余,3.命题两个整数x和x，x=qm+r,x=qm+r,0r,r|m|，则xxmodm当且仅当rrmodm。对于固定的模数m，如果xx，那么对于y有x+yx+ymodmxyxymodm,推论：同余直接继承了普通算术运算的一些性质。分配律：x(y+z)xy+xzmodm加法结合律：(x+y)+zx+(y+z)modm乘法结合律：(xy)zx(yz)modm1的性质：1xx1xmodm0的性质：0+xx+0xmodm,第四讲同余,4.2剩余类与剩余系,第四讲同余,Z/m或者Zm整数模m等价类的集合给定整数x和模数m，x模m等价类：yZ:yxmodm通常记为x或x，又称为x模m的同余类或者剩余类。,第四讲同余,例：对于模数12，有,模m等价类的集合表示形式：,模m等价类的集合,模m的代表元组成的集合,例子：,第四讲同余,Z/m中的结论：m0modmx+(-x)0modmxkmxmodm(x+y)%m=(x%m)+(y%m)%m(xy)%m=(x%m)(y%m)%m,4.Z/mX或ZmX,ZmX=yZm|gcd(y,m)=1即：Zm中与m互素的元素的集合。例如：Z15X=1,2,4,7,8,11,13,14Z11X=1,2,3,4,5,6,7,8,9,10,第四讲同余,5.定理,定理1：设m,n是两个互素的正整数，如果x,y分别遍历模m,n的完全(简化)剩余系，则nx+my遍历模mn的完全(简化)剩余系。举例：分别用模4和模5的完全剩余系和简化剩系来表示模20的完全剩余系和简化剩余系。Z4=0,1,2,3Z4X=1,3Z5=0,1,2,3,4Z5X=1,2,3,4所以：Z20=0,4,8,12,16,5,9,13,17,21,10,14,18,22,26,15,19,23,27,31Z20X=9,13,17,21,19,23,27,31,第四讲同余,欧拉函数：,欧拉函数(n),定理2：若正整数m,n，满足gcd(m,n)=1，则有：(mn)=(m)(n),第四讲同余,4.3两个著名的定理,1.欧拉定理对n1,如果gcd(x,n)=1，则有：x(n)=1modn,2.费马小定理对任意的整数x和素数p，有xp-11modp,3.欧拉函数(n)的定义对于正整数n，与其互素的小于等于n的正整数的个数表示为(n)，称为欧拉函数。也可以理解为ZnX中的元素个数。,预习RSA算法,(n)是什么用？,RSA基于因子分解难题？,medmodnm,第四讲同余,4.欧拉函数(n)的计算,举例：计算(7)，(10)，(35),Z7X=1,2,3,4,5,6,所以(7)=6,Z10X=1,3,7,9,所以(10)=4,Z35X=1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34,所以：(35)=24,那么：(10000)=？,问题：如何求欧拉函数？,回顾整数惟一分解定理每个整数n1都可以用惟一的方式表示为素数的乘积。,其中，p1,p2,pm是互不相同的素数，所有的指数都是正整数。,第四讲同余,123456789101112131415161718192021222324252627282930,举例：n=30=235,第四讲同余,123456789101112131415161718192021222324252627282930,举例：n=30=235,第四讲同余,证明：,特别地，当n为素数时，(n)=n-1,第四讲同余,那么(10000)=？,10000=2454,所以(10000)=(2-1)23(5-1)53,=84125,=4000,验证(35)=24,35=57,所以(35)=(5-1)51-1(7-1)71-1,=46,=24,第四讲同余,小结：,(1)(n)是什么？,(2)欧拉函数(n)的计算方法,作业：,计算(28)，(1234)。,第四讲同余,思考：,RSA算法的可解性和安全性分析。,(n)是欧拉函数，对正整数n，(n)是满足以下条件的i的个数：1in且gcd(i,n)=1,因子分解难题,第四讲同余,4.4RSA算法,由Rivest、Shamir和Adleman开发，既能加密又可签名，易理解和实现，因而最流行。,密钥的生成：(1)选择两个大素数p和q，计算：n=pq以及(n)=(p-1)(q-1)；例如：p=11,q=17;n=187,(n)=1016=160(2)选择随机数1e(n),gcd(e,(n)=1，计算：d=e-1mod(n)；例如：e=7,则d=23,1.RSA算法过程,第四讲同余,(3)则公钥为(e,n)，私钥(d,n)；例如：公钥为(7,187);私钥为(23,187)加密m：c=memodn解密c：m=cdmodnRSA比较慢，一般选e为3,17,65537等等。公钥私钥的关系：d=e-1mod(n)；已知e和n，要得到d，需要知道(n)，由(n)的计算公式(n)=(p-1)(q-1)可知需要知道n的因子分解。当n很大时，这是一个难题。,第四讲同余,Bob的公钥为(7,187)，私钥为(23,187)；Alice要将保险柜密码88发送Bob。,密码分析,公共网络,Alice,Bob,88,887mod187=11,11,1123mod187=88,Eve,2.举例,第四讲同余,(1)欧拉定理：如果gcd(x,n)=1，则有：x(n)=1modn(2)明文x与模数n要互素，不互素的概率为：,(3)e,d必须与(n)互素；(4)具有形式为n=pq的整数称为Blum整数。其中p和q都是模4同余3的素数。,3.可解性分析,第四讲同余,依赖于将整数n分解为素因子的难度。EDI攻击标准使用的RSA算法中规定n的长度为512至1024比特位之间，且为128的倍数。国际数字签名标准ISO/IEC9796中规定n的长度为512比特位。,从安全性考虑，p与q必为足够大的素数，使n的分解无法在多项式时间内完成。要求n至少要有1024或者2048比特(十进制的308位或616位)。,4.安全性分析,简单同余方程：,4.5一次同余式,第四讲同余,第四讲同余方程,1.定理设m不整除a，模m的一次同余式ax=b(modm)有解的充要条件是(a,m)|b。有解的解数是(a,m)，若x0是它的一个解，则它的(a,m)个解为：,2.分析若ax=b(modm)有解x=x1(modm)，则存在某个整数y1，使得ax1=b+my1(modm)，则有(a,m)|b。反之若(a,m)|b，则有：as+mr=(a,m)从而有：,因此,是方程的解。,第四讲同余方程,3.举例(1)6x=2(mod9)(2)3x=2(mod5)(3)3x=15(mod6)(4)19x=38(mod57),解:,(1)因为(6,9)=3不整除2，无解；,(2)因为(3,5)=1|2，有解，解为x=4(mod5)；,(3)因为(3,6)=3|15，有解，解为：x=-1,1,3(mod6)；,(4)因为(19,57)=19|38，有解，观察可得解为：x=2(mod57)所以同余式的所有解为：x=2+2i(mod57)i=0,1,2,18,第四讲同余,例1：,倍数,第四讲同余,例2：,倍数,第四讲同余,第四讲同余,分析：,第四讲同余,4.6中国剩余定理,第四讲同余,第四讲同余,第四讲同余,第四讲同余,中国数学史书上记载：在两千多年前的我国古代算书孙子算经中，有这样一个问题及其解法：今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？,答曰：23孙子算经给出了这道题目的解法和答案，用算式表示即为：70*2+21*3+15*4-105*2=23,第四讲同余,第四讲同余,第四讲同余,第四讲同余,举例:,x=2mod11x=7mod13x=3mod7,x=2mod11x=7mod13,(1),(2),应用中国剩余定理，可以简化一些复杂的运算。如计算47317mod713解：因为713=2331，令x=47317，则计算xmod713等价于求解同余方程：x=47317mod23=1317mod23x=47317mod31=817mod31,即：x=6mod23x=2mod31根据中国剩余定理可得解x=374(mod713)因此：47317mod713=374(mod713),4.7同余方程,第四讲同余,2.模是合数的根(n=p1p2pk)当方程的模数为合