现代密码学05---理论基础

现代密码学林喜军[e-mail]现代密码学的理论基础第5章23概率论信息论分析安全性的基本工具(略)(不安全事件有多大可能性发生)数论抽象代数基本构造工具计算复杂性理论理论基础现代密码学主要用到的理论知识本章内容45.1数论基础5.2抽象代数5.3计算复杂性理论5.1数论基础56数论研究整数的性质现代密码学中主要利用整数的性质7•一个大于1，且只能被1和它本身整除的正整数,称为素数;否则称为合数.•由此可知，正整数集合可分为三部分:–素数、合数和1•一些性质–素数的个数是无穷的–除2以外的素数一定是奇数，也称为奇素数–任意两个相邻的正整数n和n＋l(n＞3)中必有一个不是素数–相邻整数均为素数的只有2和3素数8素数举例(1—100)23571113171923293137414347535961677173798389979若b|a，且b是素数,称b是a的素因子素因子：例：12=3×4,3是12的素因子,2也是12的素因子，而4不是10•定理：任意一个正整数a1总可以分解为一系列素数乘积的形式，而且分解形式是唯一的a＝p1a1×p2a2×p3a3×……×pnan整数分解唯一性定理例：36＝22×323600＝24×32×5211•假如a和b的分解为：a=p1a1p2a2…pnanb=p1b1p2b2…pnbn则ab如下：ab=p1a1+b1p2a2+b2…pnan+bn•例:a=84=2·2·3·7=22·31·71b=96=2·2·2·2·2·3=25·31·70ab=22+5·31+1·70+1=27·32·71=8064利用唯一性定理求ab12如何生成素数现代密码学，特别是公钥密码学，常用随机的大素数习惯上，常用符号p或q表示素数Q:如何生成一个随机的大素数?先生成一个随机数，然后将之分解得到其素因子，从而得到素数，这种方法是否可行？不行！就目前而言，对某些大整数进行素因子分解是计算上不可行的13随机产生一个大奇数，然后检测它是否是素数生成素数的正确方法——素性检测在诸多素性检测算法中，Miller-Rabin算法是容易实现且广泛使用的算法14①随机产生一个n比特的随机数p(如通过伪随机序列发生器)。②将p的最高位和最低位设置为1(最高位设置为1的目的是确保素数达到最大有效长度，最低位设置为1的目的是确保该数是奇数)。③检查p不能被所有小于2000的素数整除(有方法可使这一步做得很快)。④随机选择a,且ap。⑤用a对p进行素性测试(如用Miller-Rabin算法)。若p没有通过测试,抛弃p,转到①(或将p加2作为新的p,然后转到③)。⑥如果通过测试,转到④。如果p通过足够次数的测试(如5次)，认为p是素数。随机素数的生成过程15•基于的原理•在整数n附近，约每ln(n)个整数中就有一个素数•事实上，在长度为512比特的整数中，约有10151个素数•素数的密度相当可观，因此这种概率检测法是很实用的•在实际执行算法时，生成素数是很快的(上述过程通常可在几分钟,甚至几秒钟内生成一个素数)16•它永远不会把素数误判为合数，却可能把合数误判为素数，但概率很低•对一个随机数重复进行多次素性测试，误判的概率会比你中六合彩还低•因此，误判这个问题我们根本不必担心素性检测算法是概率算法，会有一定的错误概率17数论基础公约数设al,a2,…,an和d都是正整数(n≥2).若d|ai(1≤i≤n),则称d是al,a2,…,an的公约数(公因子).公约数(公因子)18公约数中最大的那个称为al,a2,…,an的最大公约数,记为gcd(al,a2,…,an).最大公约数例：gcd(11,77)=11gcd(24,36)=12数论基础最大公约数若gcd(al,a2,…,an)=1,称al,a2,…,an是互素的.如果a和b互素，我们通常记为gcd(a,b)=1互素19最大公约数的性质•在互素的正整数中,不一定有素数.–例：gcd(25,36)=1,但25和36都不是素数.•在个数不少于3个的互素正整数中,不一定两两互素.–例:gcd(6,10,15)=1,但gcd(6,10)=2,gcd(6,15)=3,gcd(10,15)=5.数论基础最大公约数20计算GCD的算法——欧几里得算法•又称辗转相除法•记于公元前300年欧几里得所著名为Elements的书中•历史学家们相信，该算法并非欧几里得发明，早在此前200年该算法就已经出现。•它是幸存到现在的最古老的非凡算法，至今它仍是完好的。Euclid数论基础最大公约数21•基于的原理若a=b*d+r，则gcd(a,b)=gcd(b,r)。(a是被除数，b是除数，d为商,r为余数)数论基础最大公约数例：a=38,b=26,则gcd(a,b)=2欧几里得算法计算过程：①38=26*1+12②26=12*2+2③12=2*6最后一个非零余数(最后一步的除数)就是所求的gcd22•intgcd(inta,intb){intg;if(a0)a=-a;if(b0)b=-b;if(0==a+b)returnERROR;//a和b同为零g=a;//确保b等于零时，将a作为gcd返回while(b0){g=b;b=a%b;//设置新除数a=g;//设置新被除数}returng;}数论基础最大公约数23•重要定理设两个正整数a、b,最大公约数设为gcd(a,b)，则必存在两个整数x和y,使得ax＋by=gcd(a,b)•推论当a和b互素时，必存在两个整数x和y，使得ax+by=1–该推论在后面介绍公钥密码学时很有用•如何计算该定理中的x和y?–利用欧几里得算法计算a和b的最大公约数时，一些中间结果可以用于计算x和y–因此，将欧几里得算法改版一下便可。所得新算法称为“扩展的欧几里得算法”数论基础最大公约数•六十年一甲子24甲子乙丙丁癸壬丑寅卯亥戌数论基础最小公倍数25•模运算，即为求余数的运算•模运算的运算符记为modamodn＝r表示a除以n所得的余数为r。•上式中的n通常称为模数数论基础模运算例：17mod11=68mod7=126•定义若amodn＝bmodn＝r，则记a≡b(modn)称a和b在模n下是同余的(a和b在模n下有相同的余数)数论基础同余例：13≡20(mod7)20≡7(mod13)27模运算的性质•(a＋b)modn＝(amodn＋bmodn)modn•(a－b)modn＝(amodn－bmodn)modn•(a×b)modn＝(amodn×bmodn)modn•其他性质–交换律–结合律–分配律数论基础模运算的性质28不要直接计算(a×a×…×a)modn会导致因中间结果巨大而计算溢出如何计算ammodn？利用模运算的性质简化中间结果但即使这样，仍然有技巧解决的思路如果直接计算a×(a×…×(amodn)modn)modn需要计算m次模运算，仍然不够优化数论基础乘法链算法29将m看成2的幂次方之和,再利用模运算的性质正确思路数论基础乘法链算法计算a25modn（m=25是11001）a25=11001a1a8a1630•计算a25modn的过程：m=25是11001数论基础乘法链算法31•unsignedlongqe2(unsignedlonga,unsignedlongm,unsignedlongn){unsignedlongs=1,t=a,u=m;while(u){if(u&1)s=(s*t)%n;u=1;t=(t*t)%n;}returns;}时间复杂度：O(logm)数论基础乘法链算法32•其计算结果是小于等于n且与n互素的正整数的个数。Euler1707—1783数论基础欧拉函数φ(n)例：小于等于8且与8互素的正整数有1,3,5,7.所以φ(8)=433欧拉函数举例数论基础欧拉函数φ(n)34欧拉函数的性质•性质：若p、q都是素数，则–φ(p)=p-1–φ(p×q)=φ(p)φ(q)=(p-1)(q-1)数论基础欧拉函数φ(n)例：n＝15＝3×5＝p×q则φ(15)＝(3－1)×(5－1)＝8即1、2、4、7、8、11、13、1435•定理：若p为素数，k为正整数，则φ(pk)＝pk-1(p－1)数论基础欧拉函数φ(n)例：φ(8)=φ(23)=22φ(2)=436•推论：若gcd(a,b)＝1，则φ(ab)＝φ(a)φ(b)数论基础欧拉函数φ(n)例：φ(12)=φ(3)φ(4)而φ(3)＝2，φ(4)＝2所以φ(12)＝4(小于等于12且与12互素的正整数有1、5、7、11总共4个)37•欧拉定理设n≥2，如果gcd(a,n)=1，则aφ(n)≡1(modn)，同理有aφ(n)＋1≡a(modn)数论基础欧拉定理例：n＝15＝3×5，有φ(n)＝(3-1)(5-1)=8则48、78、118≡1(mod15)38•求132001mod60•解:因为gcd(13，60)＝1，则可用欧拉定理计算，故而有13φ(60)1(mod60)容易求得φ(60)＝16故而，1316≡1(mod60)所以，132001＝1316×125+1≡13(mod60)数论基础欧拉定理的应用39•费马小定理：若p是素数,且gcd(a,p)=1,则ap-1≡1(modp)同理有ap≡a(modp)Fermat1601—1665数论基础费马小定理例：25-1≡1(mod5)411-1≡1(mod11)40•求310198mod199。•解:因为199是素数,且gcd(310,199)=1，根据费马小定理，有310199-1≡1(mod199)所以,310198≡1(mod199)数论基础费马小定理的应用41•定义：设a是小于n(n1)的正整数，且gcd(a,n)=1。如果存在x，使x2≡a(modn)成立，那么称a是模n下的二次剩余。数论基础二次剩余模n下二次剩余的集合QRn模n下二次非剩余的集合QNRn不是所有的a都满足这一特性42•例：n=7，二次剩余是1,2,4•因为：12≡1(mod7)22≡4(mod7)32≡2(mod7)42≡2(mod7)52≡4(mod7)62≡1(mod7)•所以，QR7={1,2,4};QNR7={3,5,6}数论基础二次剩余举例43•性质1：二次剩余的判定标准如果a(p-1)/2≡1(modp)，其中p2是素数，1≤ap则a∈QRp•性质2：当模数是素数时，设为p2–模p下的二次剩余恰有(p-1)/2个，与其二次非剩余的数目相同(各占一半)–如果a=x2(modp)是二次剩余，那么a恰好有两个平方根。一个是x,另一个是p-x。数论基础二次剩余的一些特性44孙子歌诀三人同行七十稀，五树梅花廿一枝。七子团圆正半月，除百零五便得知。数论基础中国剩余定理70*2+21*3+15*2=233=2*105+23韩信点兵问题：3人一列余2人5人一列余3人7人一列余2人问共多少人？45•中国剩余定理(孙子定理)设n1,n2,…,nk是两两互素的正整数，对于任意整数b1,b2,…,bk，下列同余方程组x≡b1(modn1)x≡b2(modn2)…x≡bk(modnk)xn1n2…nk有唯一解数论基础中国剩余定理46扩展阅读勒让德符号雅可比符号Blum整数5.2抽象代数4748群环域交换群循环群49•代数结构由两部分组成：集合、作用在集合上的运算。•一般写为(G,*)，其中G是一个集合，*是作用在G上的运算。•也有具有多个运算的代数结构，最常用的是具有两个运算的。代数结构50EvaristeGalois(伽罗瓦)(1811–1832)19世纪法国天才少年数学家(伽罗瓦理论创始人)NielsHenrikAbel(阿贝尔)(1802—1829)19世纪挪威最伟大的数学家(埃尔米特曾说：阿贝尔留下的思想可供数学家们工作150年)代数结构51•群的定义设代数结构(G,*)，对于任意G中的元素a、b、c，满足以下条件，则它是一个群：(1)封闭性:a*b∈G(2)结合性:a*(b*c)=(a*b)*c(3)单位元:存在e∈G使得a*e=e*