Lecture03密码学的数学引论.ppt

1、第二章 古典密码总结,代替 单表代替 使用单词作为密钥的加密方法 仿射密码 多表代替 Playfair密码 Hill密码 Vigenere密码 换位,第三章密码学数学引论,学习要点： 了解数论、群论、有限域理论的基本概念 了解模运算的基本方法 了解欧几里德算法、费马定理、欧拉定理、中国剩余定理 了解群的性质 了解有限域中的计算方法,1、除数(因子)的概念：设z为由全体整数而构成的集合，若 b0且 使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子). 注:若a=mb+r且01被称为素数是指p的因子仅有1,-1,p,-p。 例：10以内的素数：2，3，5，7,31数论,算术基本定理：

2、 任何一个不等于0的正整数a都可以写成唯一的表达式aP11P22Ptt，这里P10 例： 91=7*13 11011=7*112*13 分解唯一 任一给定的正整数可通过简单列出所有后面公式中非零指数分量来说明。 整数12可表示为 a2=2,a3=1 即12=22 * 31 整数18可表示为 a2=1, a3=2 即18=21 * 32 两个数的乘法等同于对应指数分量的加法： 例如：k=12*18=216 k2=2+1=3 k3=1+2=3 k=23*33=216,最大公约数： 若a,b,cz，如果ca，cb，称c是a和b的公约数。正整数d称为a和b的最大公约数，用gcd(a,b)表示，如果它满

3、足 d是a和b的公约数。 对a和b的任何一个公约数c有cd。 将两个正整数分别表示为素数的乘积，确定它们的最大公因子。 例： 300=22*31*52 18=21*32 gcd(300,18)=21*31*50=6 注：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=11; m=7; 11=1*7+4; r=4 a=-11; m=7; -11=(-2)*7

4、+3; r=3 11 mod 7=4; -11 mod 7=3; 整数同余： 定义（同余）如果a mod m =b mod m，则称整数a模正整数m同余于整数b，并写ab（mod m）,m称为模数。,注： 1*.如果ma-b，则ab（mod m） 证明：a-b=km,a=km+b 2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质： 自反性：对任意整数a有aa（mod m） 对称性：如果ab(mod m)则ba（mod m） 传递性：如果ab (mod m）bc（mod m）则ac(mod m),3*.对于某个固定模m的同余式可以象普通的等式那样相加相减和

5、相乘： (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) 例如：11 mod 8=3 15 mod 8=7 (11+15)mod 8=(11 mod 8)+(15 mod 8)mod 8 =(3+7)mod 8=10 mod 8=2 例如：117 mod 13=? 112 mod 13=121 mod 13=4 114 mod 13=42 mod 13=3 117 mod 13=(112*114*11) mod 13 =(4*3*11)mod 13=2,例如：通过同余式演算证明5601是56的倍数

6、， 解： 53=12513(mod56) 于是有561691(mod56) 对同余式的两边同时升到10次幂， 即有56560-1。 证明：2231是47的倍数？,同理, 注意到26=64-30(mod47),于是 223=(26)325=(26 26)26 25 900*(-30)*(32) mod(47) (7)(-30)*(32) (mod47) 1(mod47) 于是有 47223-1 定理：(消去律)对于abac（mod m）来说，若gcd(a,m)1则bc(mod m),例如1：附加条件不满足的情况 63=182mod8 67=422mod8 但37mod8 例如2：附加条件满足的情

7、况 53157mod8 511=557mod8 311mod8,欧几里德算法,Euclid定理：对任意非负整数a和b： gcd(a,b)=gcd(b,a mod b) 例如：gcd(18,12)=gcd(12,6)=gcd(6,0)=6 gcd(11,10)=gcd(10,1)=gcd(1,0)=1,例: gcd (1970, 1066) 1970=1*1066+904 gcd(1066,904) 1066=1*904+162 gcd(904,162) 904=5*162+94 gcd(162,94) 162=1*94+68 gcd(94,68) 94=1*68+26 gcd(68,26) 6

8、8=2*26+16 gcd(26,16) 26=1*16+10 gcd(16,10) 16=1*10+6 gcd(10,6) 10=1*6+4 gcd(6,4) 6=1*4+2 gcd(4,2) 4=2*2+0 gcd(2,0),欧几里德算法：假定ab0, Euclid(a,b) X=a; Y=b; 如果Y=0,返回X R=X mod Y X=Y Y=R,扩展的欧几里德算法,如果gcd(d,f)=1，那么d有一个模f的乘法逆元，记作d-1, d* d-1mod f=1.,扩展的欧几里德算法,Extended Euclid(f, d) （设 f d） 1. (X1,X2,X3)(1,0,f);(

9、Y1,Y2,Y3)(0,1,d); 2. if Y3=0 then return X3=gcd(f, d)；无逆元; 3. if Y3=1 then return Y3=gcd(f, d)；Y2=d-1 mod f; 4. Q=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. goto 2。,求： gcd(4655,12075) 550-1mod 1723,费马(Format)定理,Format定理：如果p是素数并且a是不能被p整除的正整数,那么，a

10、p-11(mod p) Format定理的另一种形式： 对gcd（a，p）1 有apa(modp),例如：,a=7,p=19,求ap-1 mod p,解：72=4911mod19 74121mod197mod19 7849mod1911mod19 716121mod197mod19,ap-1=718=71672711mod191mod19,例如：,P=5, a=3, 35mod 5=3,欧拉（Euler）定理,小于n的且与n互素的正整数的个数，记作 例如： 小于24且与24互素的正整数有：1，5，7，11，13，17，19，23 为此,例子：,比7小而与7 互素的正整数为：1、2、3、4、5、

11、6。故 这12个数是： 1,2,4,5,8,10,11,13,16,17,19,20 9=32 1 2 4 5 7 8 ,欧拉定理,对于任何互素的整数a和n有：,中国剩余定理,例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？,答曰：二十三。 232*70+3*21+2*15(mod 105) （口诀：三人同行七十稀，五树梅花廿一枝， 七子团圆月正半，除百零五便得知。） 问，70，21，15如何得到的？ 原问题为： 求解同余方程组,注意：解题口诀提示我们先解下面三个特殊的同余方程组 (1) (2) (3) 的特殊解 =?=?=? 以方程（1）为对象，相当于解一个这样的同余方程 35y1(mod 3)， 解出y=2（mod 3）于是x35*2 70(mod105),类似地得到（2）、（3）方程的模105的解21、15。于是有：,中国剩余定理：设自然数m1,m2,mr两两互素，并记M=m1m2mr，b1.br表示r个整数，则同余方程组 （A） 在模M同余的意义下有唯一解。,例如： x1 mod 2 x2 mod 3 x3 mod 5 解： M=235=30 M1=15, M2=10,