《2019Lecture04密码学的数学引论.ppt》由会员分享，可在线阅读，更多相关《2019Lecture04密码学的数学引论.ppt（43页珍藏版）》请在三一文库上搜索。
1、第四章 密码学的数学引论,学习要点： 了解数论、群论、有限域理论的基本概念 了解模运算的基本方法 了解欧几里德算法、费马定理、欧拉定理、中国剩余定理 了解群的性质 了解有限域中的计算方法,1、除数(因子)的概念： 设z为由全体整数而构成的集合，若 b0且 使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子). 注:若a=mb+r且01被称为质数是指p的因子仅有1,-1,p,-p。,41 数论,算术基本定理： 任何一个不等于0的正整数a都可以写成唯一的表达式aP11P22Ptt，这里P1P2P3Pt是质数，其中i0 最大公约数： 若a,b,cz，如果ca，cb，称c是a和b的公约数。
2、正 整数d称为a和b的最大公约数，如果它满足 d是a和b的公约数。 对a和b的任何一个公约数c有cd。 注：1*. 等价的定义形式是： gcd（a,b）maxk ka且kb 2*若gcd（a,b）=1，称a与b是互素的。,带余除法： 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有相同
3、的余数。“同余”二字的来源就在于此。,二、模算术,2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质： 自反性：对任意整数a有：aa（mod m） 对称性：如果ab(mod m)，则ba（mod m） 传递性：如果ab (mod m）bc（mod m），则ac(mod m) 于是，全体整数集合z可按模m（m1）分成一些两两不交的等价类。,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
4、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。,同理, 注意到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
5、)1则bc(mod m),例如1：附加条件不满足的情况 63=182mod8 67=422mod8 但37mod8 例如2：附加条件满足的情况 53157mod8 511=557mod8 311mod8,原因：模m的乘法运算返回的结果是0到m-1之间的数，如果乘数a和模数m有除1以外的共同因子时将不会产生完整的余数集合。,扩展的欧几里德算法描述,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-1modf 4）Q=ma
6、x_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）,例：求gcd(20,117)和20-1mod117,Format定理, Format定理：如果p是质数并且a是不能被p整除的正整数,那么，ap-11(mod p) Format定理的另一种形式： 对gcd（a，p）1 有apa(modp),例子：,a=7,p=19,求ap-1modp,解：72=4911mod19 74121mod197mod19 7849mod1911mod19 716
7、121mod197mod19,ap-1=718=71672711mod191mod19,例子：,比24小而与24 互素的正整数为：1、5、7、11、13、17、19、23。故 这12个数是： 1,2,4,5,8,10,11,13,16,17,19,20,欧拉定理（Euler）（文字表述）： 若整数a与整数n互素，则a (n)1(mod n) 注： 1*. np时，有ap-11(mod p)为Format定理！ 2*.易见a (n)+1a(mod n),阶与本原元,am=1modn，如果a与n互素，则至少有一个整数m（如m=phi(n)）满足这一方程，称满足方程的最小正整数m为模n下a的阶。 如
8、果a的阶m=phi（n ），则称a为n的本原元。 本原元并不一定唯一 并非所有的整数都有本原元，只有以下形式的整数才有本原元：2,4,pa,2pa（a为整数，p为奇质数）,例子：,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的本原元。,中国剩余定理,例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？,答曰：二十三。 232*70+3*21+2*15(mod 105) （口诀：三人同行七十稀，五树梅花廿一枝， 七子团圆月正半，除百零五便
9、得知。） 问，70，21，15如何得到的？ 原问题为： 求解同余方程组,注意：若x0为上述同余方程组的解，则x0=x0+105*k(kz) 也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组 (1) (2) (3) 的特殊解 =? =? =? 以方程（1）为对象，相当于解一个这样的同余方程 35y1(mod 3)，为什么呢？ 原因是，从（1）的模数及条件知，x应同时是5和7的倍数，即应是35的倍数，于是可以假设x35y有：,35y1(mod 3)相当于2y1(mod)3 解出y=2（mod3） 于是x35*2 70(mod105) 类似地得到（2）、（3）方程的模
10、105的解21、15。 于是有： 得,中国剩余定理：设自然数m1,m2,mr两两互素，并记M=m1m2mr，b1br表示r个整数，则同余方程组 （A） 在模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,所
11、以： X0 bhMhyh mod mh bh mod mh。即满足(A)式，x0是其解。 下面证明x0是模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）的解是唯一的。,例如： x1 mod 2 x2 mod 3 x3 mod 5 解： M=235=30 M1=15, M2=10, M3=6 15y11mod2, y1=1 10y21mod3, y
12、2=1 6y31mod5, y3=1 所以,x=1151+2101+361=5323 mod 30,42 群论,群的概念 是由一个非空集合G组成，在集合G中定义了一个二元运算符“ ”，并满足以下性质的代数系统，记为G, ,交换群：,有限群 无限群 有限群的阶 循环群 循环群的生成元,群的性质,群中的单位元是唯一的 群中每一个元素的逆元是唯一的 (消去律) 对任意的 ，如果 ，或 ，则,43 有限域理论,域的概念 域是由一个非空集合F组成，在集合F中定义了两个二元运算符：“+”和“ ”，并满足： 域记为F,+,两个定义：,有限域 有限域的阶,域的实质： 域是一个可以在其上进行加法、减法、乘法和除法运算 而结果不会超出域的集合。如有理数集合、实数集合、 复数集合都是域，但整数集合不是,减法：a-b=a+(-b) 除法：a/b=a(b-1),有限域的两个定理,密码学常用素域GF(p)或阶为2m的域GF(2m),GF(p)有限域中的计算,生成元与逆元,生成元 可证明：在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次方幂的形式，g称为GF(p)的生成元 逆元,生成元的例子,有限域GF（23），5是GF（23）的生成元,GF（2m)域,生成元与逆元,生成元： 逆元,例子：GF（24）,取： GF（24）的元素：,例子（续）,生成元为：a=x,