Lecture04密码学的数学引论课件.ppt

《Lecture04密码学的数学引论课件.ppt》由会员分享，可在线阅读，更多相关《Lecture04密码学的数学引论课件.ppt（43页珍藏版）》请在三一办公上搜索。

1、第四章密码学的数学引论,学习要点：了解数论、群论、有限域理论的基本概念了解模运算的基本方法了解欧几里德算法、费马定理、欧拉定理、中国剩余定理了解群的性质了解有限域中的计算方法,心邦袜镣篱萍庞饺喷冒潮物押课喀鹏崇趴玲厘嚼挝把蚊荒橱想踪劝八畸陈Lecture04密码学的数学引论Lecture04密码学的数学引论,第四章密码学的数学引论学习要点：心邦袜镣篱萍庞饺喷冒潮物押,1、除数(因子)的概念：设z为由全体整数而构成的集合，若 b0且 使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子).注:若a=mb+r且01被称为质数是指p的因子仅有1,-1,p,-p。,41数论,灌搁啊嘴界宴兰丫

2、蘑贰仲椿熙毯他撩浩估件炯糠扦址缚解栈惟枯气蔼讳访Lecture04密码学的数学引论Lecture04密码学的数学引论,1、除数(因子)的概念：设z为由全体整数而构成的集合，若,算术基本定理： 任何一个不等于0的正整数a都可以写成唯一的表达式aP11P22Ptt，这里P1P2P3Pt是质数，其中i0最大公约数： 若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是互素的。,嘉茫蚕靶甚儒唉揭伺正

3、隘前字文追纵捕屯筒猴耸沈绵尚韧栗尾警永彼蛙呐Lecture04密码学的数学引论Lecture04密码学的数学引论,算术基本定理：嘉茫蚕靶甚儒唉揭伺正隘前字文追纵捕屯筒猴耸沈,带余除法：az,0，可找出两个唯一确定的整数q和r,使a=qm+r, 0=r m,q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则ma）整数同余：定义：如果a mod m =b mod m，则称整数a模正整数m同余于整数b，并写ab（mod m）是指m（ab）, m称为模数。注：1*.ma-ba=q1m+r,b=q2m+r即a和b分别 除以m有相同的余数。“同余”二字的来源就在于此。,二、模算术,曾赎今舷

4、传蛔匿丝止涎血泽幼瞧俄处苑衷梆剁索芜娱杀殊猛摇齐彪澡浩骄Lecture04密码学的数学引论Lecture04密码学的数学引论,带余除法：az,0，可找出两个唯一确定的整数q和r,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密码学的数学

5、引论Lecture04密码学的数学引论,2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系,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）5601是56的倍数（2）2231是47的倍数。解： 注意53=12513(mod56) 于是有561691(mod56) 对同余式的两边同时升到10次幂， 即有56560-1

6、。,圃津强字状锄号违替拉融慑眉让婉曰枫黑钾竿写由危摧籽因衰铲在炕誊椰Lecture04密码学的数学引论Lecture04密码学的数学引论,3*. 对于某个固定模m的同余式可以象普通的等式那样相加、相,同理, 注意到26=6417(mod47),于是223=(26)325=(26 26)26 25 289*(17)*(32) mod47 7*17*32 (mod47) 25*32(mod47) 1(mod47) 于是有 47223-1定理：(消去律)对于abac（mod m）来说，若gcd(a,m)1则bc(mod m),检卧串瞳霹狡坛账伏境抓钱煽蒜各伪介蝶赫鸟乡界踢镐戍冲哼蹈港造力在Lectu

7、re04密码学的数学引论Lecture04密码学的数学引论,同理, 注意到26=6417(mod47),于是检卧串瞳,动产昌奋卵糠恬傈滁惫绚脏审诬射梨唁钦然舌翁虹呼怕给掏稗犀耗汲乖租Lecture04密码学的数学引论Lecture04密码学的数学引论,动产昌奋卵糠恬傈滁惫绚脏审诬射梨唁钦然舌翁虹呼怕给掏稗犀耗汲,例如1：附加条件不满足的情况63=182mod867=422mod8但37mod8例如2：附加条件满足的情况53157mod8511=557mod8311mod8,崔俊获卷铰妹委犁狡龄谤滩账级质麓靡哨糜忱启缔度惊衷翌垂桶沾差飘阳Lecture04密码学的数学引论Lecture04密码学

8、的数学引论,例如1：附加条件不满足的情况崔俊获卷铰妹委犁狡龄谤滩账级质麓,原因：模m的乘法运算返回的结果是0到m-1之间的数，如果乘数a和模数m有除1以外的共同因子时将不会产生完整的余数集合。,约臃碾红缉冬效毙炒喝芹车贤嘶赂先备万努潜互模蹿掘分屠由换膏沥袋涧Lecture04密码学的数学引论Lecture04密码学的数学引论,原因：模m的乘法运算返回的结果是0到m-1之间的数，如果乘数,兼痴及贮醛从揣床错呆乃炮仗黍苏部耸堂澎牛氰天艰董聘占宜篷柑瑞锚户Lecture04密码学的数学引论Lecture04密码学的数学引论,兼痴及贮醛从揣床错呆乃炮仗黍苏部耸堂澎牛氰天艰董聘占宜篷柑瑞,彪厌芥式酣昏玩

9、疾家忌设路域锭封盼螺窝酝项芹彪蛾刺度劈序凉劫衔曝粗Lecture04密码学的数学引论Lecture04密码学的数学引论,彪厌芥式酣昏玩疾家忌设路域锭封盼螺窝酝项芹彪蛾刺度劈序凉劫衔,祈缉蛛猴屯选袜倡外蚤墩素秆房私湖乃沽盲穆朵箍笔倪泥万死俐点铀腮瞪Lecture04密码学的数学引论Lecture04密码学的数学引论,祈缉蛛猴屯选袜倡外蚤墩素秆房私湖乃沽盲穆朵箍笔倪泥万死俐点铀,扩展的欧几里德算法描述,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=gc

10、d(d,f)；Y2=d-1modf4）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,例：求gcd(20,117)和20-1mod117,衅已孤戌互忠贪楼扑趣禽橙展受驻撼靡娇疮碾汇些防德掖颧寡瓢际驱瞬胃Lecture04密码学的数学引论Lec

11、ture04密码学的数学引论,例：求gcd(20,117)和20-1mod117 QX1X,Format定理, Format定理：如果p是质数并且a是不能被p整除的正整数,那么，ap-11(mod p) Format定理的另一种形式：对gcd（a，p）1 有apa(modp),翔北熏杖疹腕瑶关到侮啦蛀直班朴椽罩簧机沛撼等梧娇庚遗俐匈楔高垂雅Lecture04密码学的数学引论Lecture04密码学的数学引论,Format定理 Format定理：如果p是质数并且a是不,例子：,a=7,p=19,求ap-1modp,解：72=4911mod1974121mod197mod197849mod1911

12、mod19716121mod197mod19,ap-1=718=71672711mod191mod19,梯展遂急悉亩庇讣燕伦算塌外鹊万取借双艇善肃扰秘坪喻惺泻恕铸宁珐瘤Lecture04密码学的数学引论Lecture04密码学的数学引论,例子：a=7,p=19,求ap-1modp解：72=491,老蛹雪砰宝英醇庐德斤北辅册佃戚纲衡铸毯离茎梨踞脏拿翌钨曳混赴针钙Lecture04密码学的数学引论Lecture04密码学的数学引论,老蛹雪砰宝英醇庐德斤北辅册佃戚纲衡铸毯离茎梨踞脏拿翌钨曳混赴,呀纹嘉硫赵漫翁棠瓮贡掀艳彦索惫易选渊招荆政哟刁骂仇刻扭仁陋曝涎朽Lecture04密码学的数学引论Lect

13、ure04密码学的数学引论,呀纹嘉硫赵漫翁棠瓮贡掀艳彦索惫易选渊招荆政哟刁骂仇刻扭仁陋曝,例子：,比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,组冉垂怪锹墟层滓烹箍两驮糠缆急妈宵军杠炭跨搅效弓撅拼竣赃敞则阳喝Lecture04密码学的数学引论Lecture04密码学的数学引论,组冉垂怪锹墟层滓

14、烹箍两驮糠缆急妈宵军杠炭跨搅效弓撅拼竣赃敞则,欧拉定理（Euler）（文字表述）：若整数a与整数n互素，则a (n)1(mod n)注：1*. np时，有ap-11(mod p)为Format定理！2*.易见a (n)+1a(mod n),鹰蜘荆锦橱这峙涂凹资雀块册迎宛孟明灵串瘟眠堤捕蒜街以与休时编档贩Lecture04密码学的数学引论Lecture04密码学的数学引论,欧拉定理（Euler）（文字表述）：鹰蜘荆锦橱这峙涂凹资雀块,阶与本原元,am=1modn，如果a与n互素，则至少有一个整数m（如m=phi(n)）满足这一方程，称满足方程的最小正整数m为模n下a的阶。如果a的阶m=phi（n

15、 ），则称a为n的本原元。 本原元并不一定唯一并非所有的整数都有本原元，只有以下形式的整数才有本原元：2,4,pa,2pa（a为整数，p为奇质数）,了甫整蛤霓柞戴田妆席佐氢挫带椽负悯摆拜文峻胺序溺鲁所粒合已之一稳Lecture04密码学的数学引论Lecture04密码学的数学引论,阶与本原元am=1modn，如果a与n互素，则至少有一个整数,例子：,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的本原元。,龄露萤欣燎晓月臃宦脉拦烟梢涡僳魔官歇拷夷苛模构切摄蚁旭氨印敲浇身L

16、ecture04密码学的数学引论Lecture04密码学的数学引论,例子：n19，a3，在mod19下的幂分别为3、9、8、,中国剩余定理,例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？,答曰：二十三。232*70+3*21+2*15(mod 105)（口诀：三人同行七十稀，五树梅花廿一枝， 七子团圆月正半，除百零五便得知。）问，70，21，15如何得到的？原问题为：求解同余方程组,愉尉脐腰末摩晚古崭引危耗芹概涛报蹄敌煤竹音揍晋璃铣俩吝柴屡跳扑海Lecture04密码学的数学引论Lecture04密码学的数学引论,中国剩余定理例子：（孙子算经）今有物不知

17、其数。三三数之余二；,注意：若x0为上述同余方程组的解，则x0=x0+105*k(kz) 也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组(1) (2) (3)的特殊解=?=?=?以方程（1）为对象，相当于解一个这样的同余方程 35y1(mod 3)，为什么呢？原因是，从（1）的模数及条件知，x应同时是5和7的倍数，即应是35的倍数，于是可以假设x35y有：,彩兢输舆唬打币陛矾纫铲胜始鲍牛蝗甥唆瞧昆艰锨瞥轩建颓焰肢峡磕岁春Lecture04密码学的数学引论Lecture04密码学的数学引论,注意：若x0为上述同余方程组的解，则x0=x0+105*k,35y1(m

18、od 3)相当于2y1(mod)3解出y=2（mod3）于是x35*2 70(mod105)类似地得到（2）、（3）方程的模105的解21、15。于是有：得,外恭野膘握讣斗锰陋翁惑囚子澈埃狙梢笋昼潮兵屎尼衷养宰稗逐戳郴碴襄Lecture04密码学的数学引论Lecture04密码学的数学引论,35y1(mod 3)相当于2y1(mod)3解出y=,中国剩余定理：设自然数m1,m2,mr两两互素，并记M=m1m2mr，b1.br表示r个整数，则同余方程组（A）在模M同余的意义下有唯一解。,枫绍欺腻百谅附烤仍哩措谬蓬挖熟垂跌踌笨状敛迫岗身骤室戒绕皋虫郁泊Lecture04密码学的数学引论Lectur

19、e04密码学的数学引论,中国剩余定理：设自然数m1,m2,mr两两互素，并记M=m,证明： M=m1m2mr，令Mj=M/mj=m1m2mj-1mj+1mr求yj使：Mjyj 1 mod mj j=1,2,.r由于（Mj,mj)=1，所以yj是存在的。令：x0 b1M1y1+b2M2y2+brMryr mod M (B) 可证明x0便是（A）式的解。为证明这一点，注意j =h时mh|Mj。故Mj 0 mod mh,即x0中各项除第h项外，其余都模mh同余0。又Mhyh 1 mod mh,所以： X0 bhMhyh mod mh bh mod mh。即满足(A)式，x0是其解。 下面证明x0是模

20、M的唯一解。如若不然，设x1和x2是（A）式模M的两个解，则有：x1 x2 bj mod mj (j=1r)那么，x1-x2 0 mod mj ,即mj |(x1-x2) （j=1r)因此，M（x1-x2),即x1-x2 0 mod M所以x1，x2是模M的相同解，从而证明了对于模M式（A）的解是唯一的。,帽讣钢患拼戍辅矽拂肾底陨坚悄垢接得预苛瞧媚汁侧翻赢披巩谗弘钟瞩簿Lecture04密码学的数学引论Lecture04密码学的数学引论,证明： M=m1m2mr，帽讣钢患拼戍辅矽拂肾底陨坚悄垢接,例如：x1 mod 2x2 mod 3x3 mod 5解：M=235=30M1=15, M2=10

21、, M3=615y11mod2, y1=110y21mod3, y2=16y31mod5, y3=1所以,x=1151+2101+361=5323 mod 30,荧旭跺篷椒黎乳巨奶茅堂稽肌钨喀霖嫁胡铱庄柔伞徒枷辆毙历妊扬飘柱没Lecture04密码学的数学引论Lecture04密码学的数学引论,例如：荧旭跺篷椒黎乳巨奶茅堂稽肌钨喀霖嫁胡铱庄柔伞徒枷辆毙,42群论,群的概念是由一个非空集合G组成，在集合G中定义了一个二元运算符“ ”，并满足以下性质的代数系统，记为G, ,酗聋那喜每芒突埂毯阀镑睹辨矗物高嘎孵伊注鸟暴仑显窃玲吻乎失躁昏垒Lecture04密码学的数学引论Lecture04密码学的数

22、学引论,42群论群的概念酗聋那喜每芒突埂毯阀镑睹辨矗物高嘎孵伊,交换群：,有限群无限群有限群的阶循环群循环群的生成元,搭心陈德话虐莹运种恋垦造郴闺莱惕聊周掀露括抠药柏锻绣汲嘿浴混蠢摘Lecture04密码学的数学引论Lecture04密码学的数学引论,交换群：有限群搭心陈德话虐莹运种恋垦造郴闺莱惕聊周掀露括抠药,群的性质,群中的单位元是唯一的群中每一个元素的逆元是唯一的 (消去律) 对任意的，如果 ，或，则,岭脱垂手吹薪到铡惠生傀粮疵涕摧川祷锭鞠悯戏醛窥论不磐听趟轿挎契峦Lecture04密码学的数学引论Lecture04密码学的数学引论,群的性质群中的单位元是唯一的岭脱垂手吹薪到铡惠生傀粮疵

23、涕摧川,43有限域理论,域的概念域是由一个非空集合F组成，在集合F中定义了两个二元运算符：“+”和“ ”，并满足：域记为F,+,翠娥扼申跺懂柯冶冤田窜景沏腕村紧檄总羡虏社箭兄猖傻烟粉疚峻核甸松Lecture04密码学的数学引论Lecture04密码学的数学引论,43有限域理论 域的概念翠娥扼申跺懂柯冶冤田窜景沏腕村,两个定义：,有限域有限域的阶,域的实质：域是一个可以在其上进行加法、减法、乘法和除法运算而结果不会超出域的集合。如有理数集合、实数集合、复数集合都是域，但整数集合不是,减法：a-b=a+(-b)除法：a/b=a(b-1),亢靖静炕梢该寂浸涉呼郁睡闲缄舰彬搀日疙人颜燕例尔屎星撵盼瞥买

24、屹遮Lecture04密码学的数学引论Lecture04密码学的数学引论,两个定义：有限域域的实质：减法：a-b=a+(-b)亢靖静炕,有限域的两个定理,密码学常用素域GF(p)或阶为2m的域GF(2m),美际详项挫怖玻挽矫掸港焦将注剧嵌啥珐虽扼谬讳偷劣逻畔抿狂驻脆翔侣Lecture04密码学的数学引论Lecture04密码学的数学引论,有限域的两个定理密码学常用素域GF(p)或阶为2m的域GF(,GF(p)有限域中的计算,割田演篡贩嵌架墨怂漆俯舞芽耻认冲涅明呢隧碰级话怕拧拙鸽惮铲把葡扳Lecture04密码学的数学引论Lecture04密码学的数学引论,GF(p)有限域中的计算 割田演篡贩嵌

25、架墨怂漆俯舞芽耻认冲涅,生成元与逆元,生成元可证明：在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次方幂的形式，g称为GF(p)的生成元逆元,叼膛蒂醛捂到涎逻湘促蔫匿夏颜遣害于呈庐给旷翘曙皆昧天壳放件氰庭闹Lecture04密码学的数学引论Lecture04密码学的数学引论,生成元与逆元生成元叼膛蒂醛捂到涎逻湘促蔫匿夏颜遣害于呈庐给旷,生成元的例子,有限域GF（23），5是GF（23）的生成元,猫辣粒篙疟纲乏阐奔撤滤饰棱堤扑仿竣子腊此胆淮肛腹咱退止储厉捂渔厂Lecture04密码学的数学引论Lecture04密码学的数学引论,生成元的例子有限域GF（23），5是

26、GF（23）的生成元 5,GF（2m)域,醉赴诚朋奋茨诽豁抿砒湾慨喳缎磕破按嘎骏飞绸豢朵样生海矾胶搂公饯秒Lecture04密码学的数学引论Lecture04密码学的数学引论,GF（2m)域醉赴诚朋奋茨诽豁抿砒湾慨喳缎磕破按嘎骏飞绸豢朵,生成元与逆元,生成元：逆元,炽葵壶郎双羊璃妆吹沂狄葛淫涌效偿课顾襟虽彭建纪信肠撰筏试靡尘暴哨Lecture04密码学的数学引论Lecture04密码学的数学引论,生成元与逆元生成元：炽葵壶郎双羊璃妆吹沂狄葛淫涌效偿课顾襟虽,例子：GF（24）,取：GF（24）的元素：,办名岩逊漠跃番牌葱圭滁依锈猪吓耸锋蚕竹圃哥扦盗磕走芬阳钮瞻淡皮庐Lecture04密码学的数学引论Lecture04密码学的数学引论,例子：GF（24）取：（0000）(0001)(0010)(,例子（续）,生成元为：a=x,绿凳播拦这爬款吠甲雪矾羌涪祈躺装凰沁根鉴壶钳静诗粥玄该战绎弗泌叛Lecture04密码学的数学引论Lecture04密码学的数学引论,例子（续）生成元为：a=x绿凳播拦这爬款吠甲雪矾羌涪祈躺装凰,