Lecture04密码学的数学引论课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章密码学的数学引论,学习要点：,了解数论、群论、有限域理论的基本概念,了解模运算的基本方法,了解欧几里德算法、费马定理、欧拉定理、中国剩余定理,了解群的性质,了解有限域中的计算方法,心邦袜镣篱萍庞饺喷冒潮物押课喀鹏崇趴玲厘嚼挝把蚊荒橱想踪劝八畸陈Lecture04密码学的数学引论Lecture04密码学的数学引论,第四章密码学的数学引论学习要点：心邦袜镣篱萍庞饺喷冒潮物押,1,1、除数(因子)的概念：,设z为由全体整数而构成的集合，若 b0且 使得a=mb,此时称b整除a.记为ba,还称b为a的,除数,(,因子,),.,注,:若a=mb+r且0r1被称为,质数,是指p的因子仅有1,-1,p,-p。,41数论,灌搁啊嘴界宴兰丫蘑贰仲椿熙毯他撩浩估件炯糠扦址缚解栈惟枯气蔼讳访Lecture04密码学的数学引论Lecture04密码学的数学引论,1、除数(因子)的概念：设z为由全体整数而构成的集合，若,2,算术基本定理,：,任何一个不等于0的正整数a都可以写成唯一的表达式aP,1,1,P,2,2,P,t,t,，,这里P,1,P,2,P,3,P,t,是质数，其中,i,0,最大公约数：,若a,b,cz，如果ca，cb，称c是a和b的,公约数,。正,整数d称为a和b的,最大公约数,，如果它满足,d是a和b的公约数。,对a和b的任何一个公约数c有cd。,注,：1,*,.等价的定义形式是：,gcd（a,b）maxk ka且kb,2,*,若gcd（a,b）=1，称a与b是,互素,的,。,嘉茫蚕靶甚儒唉揭伺正隘前字文追纵捕屯筒猴耸沈绵尚韧栗尾警永彼蛙呐Lecture04密码学的数学引论Lecture04密码学的数学引论,算术基本定理：嘉茫蚕靶甚儒唉揭伺正隘前字文追纵捕屯筒猴耸沈,3,带余除法,：,az,0，可找出两个唯一确定的整数q和r,使a=qm+r,0=r0，可找出两个唯一确定的整数q和r,4,2,*,.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质：,自反性,：对任意整数a有：aa（mod m）,对称性,：如果ab(mod m)，则ba（mod m）,传递性,：如果ab(mod m）bc（mod m），则ac(mod m),于是，全体整数集合z可按模m（m1）分成一些两两不交的等价类。,胺驶铜棘常痒椒转涨吞杰各吮牡杖没翘兽戳烈棵款盾玛徐序黍琢辩戎泉粪Lecture04密码学的数学引论Lecture04密码学的数学引论,2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系,5,3*,.对于某个固定模m的同余式可以象普通的等式那样,相加,、,相减,和,相乘，可结合,：,(1)a(mod m)b(mod m)mod m=(ab)(mod m),(2)a(mod m)*b(mod m)mod m=a*b(mod m),(3)(a*b)modm+(a*c)modm=a*(b+c)modm,例子.通过同余式演算证明：,（1）5,60,1是56的倍数,（2）2,23,1是47的倍数。,解：,注意5,3,=12513(mod56),于是有5,6,1691(mod56),对同余式的两边同时升到10次幂，,即有565,60,-1。,圃津强字状锄号违替拉融慑眉让婉曰枫黑钾竿写由危摧籽因衰铲在炕誊椰Lecture04密码学的数学引论Lecture04密码学的数学引论,3*.对于某个固定模m的同余式可以象普通的等式那样相加、相,6,同理,注意到2,6,=6417(mod47),于是,2,23,=(2,6,),3,2,5,=(2,6,2,6,)2,6,2,5,289*(17)*(32)mod47,7*17*32(mod47),25*32(mod47),1(mod47),于是有 472,23,-1,定理,：(消去律)对于abac（mod m）来说，若gcd(a,m)1则bc(mod m),检卧串瞳霹狡坛账伏境抓钱煽蒜各伪介蝶赫鸟乡界踢镐戍冲哼蹈港造力在Lecture04密码学的数学引论Lecture04密码学的数学引论,同理,注意到26=6417(mod47),于是检卧串瞳,7,动产昌奋卵糠恬傈滁惫绚脏审诬射梨唁钦然舌翁虹呼怕给掏稗犀耗汲乖租Lecture04密码学的数学引论Lecture04密码学的数学引论,动产昌奋卵糠恬傈滁惫绚脏审诬射梨唁钦然舌翁虹呼怕给掏稗犀耗汲,8,例如1：附加条件不满足的情况,63=182mod8,67=422mod8,但37mod8,例如2：附加条件满足的情况53157mod8,511=557mod8,311mod8,崔俊获卷铰妹委犁狡龄谤滩账级质麓靡哨糜忱启缔度惊衷翌垂桶沾差飘阳Lecture04密码学的数学引论Lecture04密码学的数学引论,例如1：附加条件不满足的情况崔俊获卷铰妹委犁狡龄谤滩账级质麓,9,原因：模m的乘法运算返回的结果是0到m-1之间的数，如果乘数a和模数m有除1以外的共同因子时将不会产生完整的余数集合。,Z8,0,1,2,3,4,5,6,7,乘以6,0,6,12,18,24,30,36,42,模8后的余数,0,6,4,2,0,6,4,2,Z8,0,1,2,3,4,5,6,7,乘以5,0,5,10,15,20,25,30,35,模8后的余数,0,5,2,7,4,1,6,3,约臃碾红缉冬效毙炒喝芹车贤嘶赂先备万努潜互模蹿掘分屠由换膏沥袋涧Lecture04密码学的数学引论Lecture04密码学的数学引论,原因：模m的乘法运算返回的结果是0到m-1之间的数，如果乘数,10,兼痴及贮醛从揣床错呆乃炮仗黍苏部耸堂澎牛氰天艰董聘占宜篷柑瑞锚户Lecture04密码学的数学引论Lecture04密码学的数学引论,兼痴及贮醛从揣床错呆乃炮仗黍苏部耸堂澎牛氰天艰董聘占宜篷柑瑞,11,彪厌芥式酣昏玩疾家忌设路域锭封盼螺窝酝项芹彪蛾刺度劈序凉劫衔曝粗Lecture04密码学的数学引论Lecture04密码学的数学引论,彪厌芥式酣昏玩疾家忌设路域锭封盼螺窝酝项芹彪蛾刺度劈序凉劫衔,12,祈缉蛛猴屯选袜倡外蚤墩素秆房私湖乃沽盲穆朵箍笔倪泥万死俐点铀腮瞪Lecture04密码学的数学引论Lecture04密码学的数学引论,祈缉蛛猴屯选袜倡外蚤墩素秆房私湖乃沽盲穆朵箍笔倪泥万死俐点铀,13,扩展的欧几里德算法描述,Extended EUCLID(d,f)：,1）(X1,X2,X3)(1,0,f)；(Y1,Y2,Y3)(0,1,d),2）如果Y3=0返回X3=gcd(d,f)；无逆元,3）如果Y3=1返回Y3=gcd(d,f)；Y2=d,-1,modf,4）Q=max_int(X3/Y3),5）(T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3),6）(X1,X2,X3)(Y1,Y2,Y3),7）(Y1,Y2,Y3)(T1,T2,T3),8）回到 2）,革没伶摄吩仁悸崎紫小颇急狈搁顶痛旗闯辗归菠十妄书东陋诞茵啪翰鸟飘Lecture04密码学的数学引论Lecture04密码学的数学引论,扩展的欧几里德算法描述Extended EUCLID(d,f,14,例：求gcd(20,117)和20,-1,mod117,Q,X1,X2,X3,Y1（T1）,Y2（T2）,Y3(T3),-,1,0,117,0,1,20,5,0,1,20,1,-5,17,1,1,-5,17,-1,6,3,5,-1,6,3,6,-35,2,1,6,-35,2,-7,41,1=gcd,衅已孤戌互忠贪楼扑趣禽橙展受驻撼靡娇疮碾汇些防德掖颧寡瓢际驱瞬胃Lecture04密码学的数学引论Lecture04密码学的数学引论,例：求gcd(20,117)和20-1mod117 QX1X,15,Format定理,Format定理,：如果p是质数并且a是不能被p整除的正整数,那么，a,p-1,1(mod p),Format定理的另一种形式：,对gcd（a，p）1 有a,p,a(modp),翔北熏杖疹腕瑶关到侮啦蛀直班朴椽罩簧机沛撼等梧娇庚遗俐匈楔高垂雅Lecture04密码学的数学引论Lecture04密码学的数学引论,Format定理 Format定理：如果p是质数并且a是不,16,例子：,a=7,p=19,求a,p-1,modp,解：7,2,=4911mod19,7,4,121mod197mod19,7,8,49mod1911mod19,7,16,121mod197mod19,a,p-1,=7,18,=7,16,7,2,711mod191mod19,梯展遂急悉亩庇讣燕伦算塌外鹊万取借双艇善肃扰秘坪喻惺泻恕铸宁珐瘤Lecture04密码学的数学引论Lecture04密码学的数学引论,例子：a=7,p=19,求ap-1modp解：72=491,17,老蛹雪砰宝英醇庐德斤北辅册佃戚纲衡铸毯离茎梨踞脏拿翌钨曳混赴针钙Lecture04密码学的数学引论Lecture04密码学的数学引论,老蛹雪砰宝英醇庐德斤北辅册佃戚纲衡铸毯离茎梨踞脏拿翌钨曳混赴,18,呀纹嘉硫赵漫翁棠瓮贡掀艳彦索惫易选渊招荆政哟刁骂仇刻扭仁陋曝涎朽Lecture04密码学的数学引论Lecture04密码学的数学引论,呀纹嘉硫赵漫翁棠瓮贡掀艳彦索惫易选渊招荆政哟刁骂仇刻扭仁陋曝,19,例子：,比24小而与24 互素的正整数为：1、5、7、11、13、17、19、23。故,这12个数是：,1,2,4,5,8,10,11,13,16,17,19,20,梭堕栖潞吹闺能您候谐移彪刻阮砧谷洞墓题禾楷嚼项疹勤鉴僳屑衙开败铰Lecture04密码学的数学引论Lecture04密码学的数学引论,例子：比24小而与24 互素的正整数为：1、5、7、11、1,20,组冉垂怪锹墟层滓烹箍两驮糠缆急妈宵军杠炭跨搅效弓撅拼竣赃敞则阳喝Lecture04密码学的数学引论Lecture04密码学的数学引论,组冉垂怪锹墟层滓烹箍两驮糠缆急妈宵军杠炭跨搅效弓撅拼竣赃敞则,21,欧拉定理（Euler）（文字表述）：,若整数a与整数n互素，则a,(n),1(mod n),注,：,1,*,.np时，有a,p-1,1(mod p)为Format定理！,2,*,.易见a,(n)+1,a(mod n),鹰蜘荆锦橱这峙涂凹资雀块册迎宛孟明灵串瘟眠堤捕蒜街以与休时编档贩Lecture04密码学的数学引论Lecture04密码学的数学引论,欧拉定理（Euler）（文字表述）：鹰蜘荆锦橱这峙涂凹资雀块,22,阶与本原元,a,m,=1modn，如果a与n互素，则至少有一个整数m（如m=phi(n)）满足这一方程，称满足方程的最小正整数m为模n下a的,阶,。,如果a的阶m=phi（n），则称a为n的,本原元,。,本原元并不一定唯一,并非所有的整数都有本原元，只有以下形式的整数才有本原元：2,4,p,a,2p,a,（a为整数，p为奇质数）,了甫整蛤霓柞戴田妆席佐氢挫带椽负悯摆拜文峻胺序溺鲁所粒合已之一稳Lecture04密码学的数学引论Lecture04密码学的数学引论,阶与本原元am=1modn，如果a与n互素，则至少有一个整数,23,例子：,n19，a3，在mod19下的幂分别为3、9、8、5、15、7、2、6、18、16、10、11、14、4、12、17、13和1。即3的阶为18phi(19)，所以3为19的本原元。,龄露萤欣燎晓月臃宦脉拦烟梢涡僳魔官歇拷夷苛模构切摄蚁旭氨印敲浇身Lecture04密码学的数学引论Lecture04密码学的数学引论,例子：n19，a3，在mod19下的幂分别为3、9、8、,24,中国剩余定理,例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？,答曰：二十三。,232*70+3*21+2*15(mod 105),（口诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除