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

应用密码学计算机科学与技术学院田秀霞[e-mail]第四讲同余与同余式本章主要内容•1同余及其基本性质•2剩余类与剩余系•3几个著名定理•4RSA公钥密码体制•5同余式与一次同余式•6中国剩余定理4.1同余及其基本性质1.x≡ymodmx模m同余y这种关系叫模m的同余。等价的说法有x≡ymodm当且仅当m|x-y。2.同余的性质对于固定的整数m，模m同余是一个等价关系。自反性：对于任意的x，总有x≡xmodm；对称性：x≡ymodmy≡xmodm；传递性：x≡ymodm,y≡zmodmx≡zmodm。其他性质：(1)x≡ymodmax≡aymodm,x±a≡y±amodm；(2)x≡ymodmax≡aymodam,a0；(3)(a·b)modm≡(amodm·bmodm)modm。第四讲同余第四讲同余3.命题两个整数x和x’，x=qm+r,x’=q’m+r’,0≤r,r’≤|m|，则x≡x’modm当且仅当r≡r’modm。对于固定的模数m，如果x≡x’，那么对于y有x+y≡x’+ymodmxy≡x’ymodm推论：同余直接继承了普通算术运算的一些性质。分配律：x(y+z)≡xy+xzmodm加法结合律：(x+y)+z≡x+(y+z)modm乘法结合律：(xy)z≡x(yz)modm1的性质：1·x≡x·1≡xmodm0的性质：0+x≡x+0≡xmodm第四讲同余4.2剩余类与剩余系第四讲同余Z/m或者Zm整数模m等价类的集合给定整数x和模数m，x模m等价类：{y∈Z:y≡xmodm}通常记为x或x，又称为x模m的同余类或者剩余类。第四讲同余例：对于模数12，有012122400113112401{0,1,2,,2,1}{0,1,2,,2,1}mmmm模m等价类的集合表示形式：/3{0,1,2}{9,31,1}Z模m等价类的集合模m的代表元组成的集合模m的完全剩余系•例子：第四讲同余Z/m中的结论：m≡0modmx+(-x)≡0modmx±km≡xmodm(x+y)%m=((x%m)+(y%m))%m(xy)%m=((x%m)·(y%m))%m4.Z/mX或ZmXZmX={y∈Zm|gcd(y,m)=1}即：Zm中与m互素的元素的集合。例如：Z15X={1,2,4,7,8,11,13,14}Z11X={1,2,3,4,5,6,7,8,9,10}第四讲同余模m的简化剩余系==缩系5.定理定理1：设m,n是两个互素的正整数，如果x,y分别遍历模m,n的完全(简化)剩余系，则nx+my遍历模mn的完全(简化)剩余系。举例：分别用模4和模5的完全剩余系和简化剩系来表示模20的完全剩余系和简化剩余系。Z4={0,1,2,3}Z4X={1,3}Z5={0,1,2,3,4}Z5X={1,2,3,4}所以：Z20={0,4,8,12,16,5,9,13,17,21,10,14,18,22,26,15,19,23,27,31}Z20X={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)=1modn2.费马小定理对任意的整数x和素数p，有xp-1≡1modp3.欧拉函数(n)的定义对于正整数n，与其互素的小于等于n的正整数的个数表示为(n)，称为欧拉函数。也可以理解为ZnX中的元素个数。(1)=1预习RSA算法(n)是什么用？RSA基于因子分解难题？medmodnm第四讲同余4.欧拉函数(n)的计算举例：计算(7)，(10)，(35)Z7X={1,2,3,4,5,6}所以(7)=6Z10X={1,3,7,9}所以(10)=4Z35X={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)=？问题：如何求欧拉函数？121111122()(1)(1)...(1)meeemmnpppppp推论：正整数1212...meeemnppp的欧拉函数(n)值为：回顾整数惟一分解定理每个整数n1都可以用惟一的方式表示为素数的乘积。其中，p1,p2,…,pm是互不相同的素数，所有的指数都是正整数。第四讲同余memeepppn...2211123456789101112131415161718192021222324252627282930举例：n=30=2×3×530330)530(2(30)30第四讲同余12345678910111213141516171819202122232425262728293030(30)30(230)353025举例：n=30=2×3×530(2330330)53023530(15106)(532)18第四讲同余112(1)123()(...)(...)(...)...mmmnnnnnnppppppnppp12111(1)(1)...(1)mnppp121212111(...)(1)(1)...(1)meeemmpppppp证明：121111122(1)(1)...(1)meeemmpppppp特别地，当n为素数时，(n)=n-1容斥原理第四讲同余那么(10000)=？10000=24×54所以(10000)=(2-1)×23×(5-1)×53=8×4×125=4000验证(35)=2435=5×7所以(35)=(5-1)×51-1×(7-1)×71-1=4×6=24第四讲同余小结：(1)(n)是什么？(2)欧拉函数(n)的计算方法1212...meeemnppp121111122()(1)(1)...(1)meeemmnpppppp作业：计算(28)，(1234)。第四讲同余思考：RSA算法的可解性和安全性分析。(n)是欧拉函数，对正整数n，(n)是满足以下条件的i的个数：1in且gcd(i,n)=1因子分解难题111qppq第四讲同余4.4RSA算法由Rivest、Shamir和Adleman开发，既能加密又可签名，易理解和实现，因而最流行。密钥的生成：(1)选择两个大素数p和q，计算：n=pq以及(n)=(p-1)×(q-1)；例如：p=11,q=17;n=187,(n)=10×16=160(2)选择随机数1e(n),gcd(e,(n))=1，计算：d=e-1mod(n)；例如：e=7,则d=231.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。知道7,187,不能得到23。密码分析公共网络AliceBob88加密密钥7,187887mod187=11111123mod187=88解密密钥23Eve2.举例第四讲同余(1)欧拉定理：如果gcd(x,n)=1，则有：x(n)=1modn(2)明文x与模数n要互素，不互素的概率为：(1)(1)1111pqpqpqpq(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)个解为：0(mod),0,1,2,...,(,)1(,)imxximiamam(mod)(,)sbxmam2.分析若ax=b(modm)有解x=x1(modm)，则存在某个整数y1，使得ax1=b+my1(modm)，则有(a,m)|b。反之若(a,m)|b，则有：as+mr=(a,m)从而有：因此是方程的解。(,)(,)bbasmrbamam(mod),0,1,2,...,(,)1(,)(,)ibmxsimiamamam第四讲同余方程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=3mod7x=2mod11x=7mod13(1)(2)应用中国剩余定理，可以简化一些复杂的运算。如计算47317mod713解：因为713=2331，令x=47317，则计算xmod713等价于求解同余方程：x=47317mod23=1317mod23x=47317mod31=817mod31即：x=6mod23x=2mod31根据中国剩余定理可得解x=374(mod713)因此：47317mod713=374(mod713)4.7同余方程第四讲同余2.模是合数的根(n=p1p2…pk)当方程的模数为合数n(p1p2…pk)时，如何求解？如方程x2=amodp1p2(p1和p2互素)解决办法：分别求解x2=amodp1和x2=amodp2，再利用孙子定理求解x2=amodp1p2。举例：x2=-1mod13×17×29解：x2=-1mod13x=±5(mod13)x2=-1mod17x=±4(mod17)x2=-1mod29x=±12(mod29)•例2：第四讲同余•例2：第四讲同余•例2：第四讲同余