《Lecture03_密码学的数学引论.ppt》由会员分享，可在线阅读，更多相关《Lecture03_密码学的数学引论.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 古典密码总结n代替n单表代替使用单词作为密钥的加密方法仿射密码n多表代替Playfair密码Hill密码Vigenere密码n换位第三章密码学数学引论n学习要点：学习要点：了解数论、群论、有限域理论的基本概念了解数论、群论、有限域理论的基本概念了解模运算的基本方法了解模运算的基本方法了解欧几里德算法、费马定理、欧拉定理、了解欧几里德算法、费马定理、欧拉定理、中国剩余定理中国剩余定理了解群的性质了解群的性质了解有限域中的计算方法了解有限域中的计算方法1 1、除数、除数(因子因子)的概念：的概念：设设z z为由全体整数而构成的集合，若为由全体整数而构成的集合，若 b0b0且且 使得使得a=
2、a=mbmb,此时称此时称b b整除整除a.a.记为记为ba,ba,还称还称b b为为a a的的除数除数(因子因子).注注:若若a=a=mb+rmb+r且且0rb,0r1p1被称为被称为素数素数是指是指p p的因子仅有的因子仅有1,-1,p,-1,-1,p,-p p。例：10以内的素数：2，3，5，731数论数论算术基本定理算术基本定理：任任何何一一个个不不等等于于0 0的的正正整整数数a a都都可可以以写写成成唯唯一一的的表表达达式式a aP P1 111P P2 222PPt ttt，这里这里P P1 1PP2 2PP3 3P00n例：例：91=7*13 11011=7*112*13 分解
3、唯一分解唯一n任一给定的正整数可通过简单列出所有后面公式中任一给定的正整数可通过简单列出所有后面公式中非零指数分量非零指数分量来说明。来说明。整数整数1212可表示为可表示为 a a2 2=2,a=2,a3 3=1 =1 即即12=212=22 2*3*31 1整数整数1818可表示为可表示为 a a2 2=1,a=1,a3 3=2 =2 即即18=218=21 1*3*32 2n两个数的乘法等同于对应指数分量的加法：两个数的乘法等同于对应指数分量的加法：例如：例如：k=12*18=216k=12*18=216 k k2 2=2+1=3=2+1=3 k k3 3=1+2=3=1+2=3 k=2
4、 k=23 3*3*33 3=216=216最大公约数：最大公约数：若若a,b,cza,b,cz，如果，如果caca，cbcb，称，称c c是是a a和和b b的公约数。的公约数。正整数正整数d d称为称为a a和和b b的的最大公约数最大公约数，用，用gcd(a,bgcd(a,b)表示，如表示，如果它满足果它满足d d是是a a和和b b的公约数。的公约数。对对a a和和b b的任何一个公约数的任何一个公约数c c有有cdcd。n将两个正整数分别表示为素数的乘积，确定它们的最将两个正整数分别表示为素数的乘积，确定它们的最大公因子。大公因子。例：例：300=2300=22 2*3*31 1*5
5、*52 2 18=2 18=21 1*3*32 2 gcd(300,18)=2 gcd(300,18)=21 1*3*31 1*5*50 0=6=6注注：1 1*.等价的定义形式是：等价的定义形式是：gcdgcd（a,ba,b）maxkmaxk kaka且且kbkb 2 2*若若gcdgcd（a,ba,b）=1=1，称，称a a与与b b是是互素互素的。的。二、模算术带余除法：带余除法：az,0az,0，可找出两个唯一确定的整数可找出两个唯一确定的整数q q和和r,r,使使a=a=qm+rqm+r,0=r m,q,0=rb0,ab0,nEuclid(a,bEuclid(a,b)X=a;Y=b;
6、X=a;Y=b;如果如果Y=0,Y=0,返回返回X XR=X mod YR=X mod YX=YX=YY=RY=R扩展的欧几里德算法n如果如果gcd(d,fgcd(d,f)=1)=1，那么，那么d d有一个模有一个模f f的乘法逆元，记的乘法逆元，记作作d d-1-1,d*d,d*d-1-1mod f=1.mod f=1.扩展的欧几里德算法Extended Extended Euclid(fEuclid(f,d),d)（设设 f df d）1.(X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d);1.(X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d);2.
7、if Y3=0 then return X3=2.if Y3=0 then return X3=gcd(fgcd(f,d),d)；无逆元无逆元;3.if Y3=1 then return Y3=3.if Y3=1 then return Y3=gcd(fgcd(f,d),d)；Y2=dY2=d-1-1 mod f;mod f;4.Q=X3/Y3 4.Q=X3/Y3；5.(T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3);5.(T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1,X2,X3)(Y1,Y2,Y3);6.(X1,X2,X3)(Y1,Y2,Y3);
8、7.(Y1,Y2,Y3)(T1,T2,T3);7.(Y1,Y2,Y3)(T1,T2,T3);8.8.gotogoto 2 2。n求：n gcd(4655,12075)n 550-1mod 1723费马费马(Format)定理定理v FormatFormat定理定理：如果：如果p p是素数并且是素数并且a a是是不能被不能被p p整整除的正整数除的正整数,那么，那么，a ap-1p-11(mod p)1(mod p)v FormatFormat定理的另一种形式：定理的另一种形式：对对gcdgcd（a a，p p）1 1 有有a ap pa(modpa(modp)例如：例如：a=7,p=19,求a
9、p-1 mod p解：72=4911mod1974121mod197mod197849mod1911mod19716121mod197mod19ap-1=718=71672711mod191mod19例如：例如：P=5,a=3,35mod 5=3欧拉（Euler）定理n小于小于n的且与的且与n互素的正整数的个数，记作互素的正整数的个数，记作n例如：例如：n小于小于24且与且与24互素的正整数有：互素的正整数有：1，5，7，11，13，17，19，23 为此为此例子：例子：n比比7 7小而与小而与7 7 互素的正整数为：互素的正整数为：1 1、2 2、3 3、4 4、5 5、6 6。故故 n 这
10、这1212个数是：个数是：1,2,4,5,8,10,11,13,16,17,19,201,2,4,5,8,10,11,13,16,17,19,20n9=39=32 2 1 2 4 5 7 8 1 2 4 5 7 8 欧拉定理n对于任何互素的整数a和n有：中国剩余定理中国剩余定理例例子子：（孙孙子子算算经经）今今有有物物不不知知其其数数。三三三三数数之之余余二二；五五数之余三；七七数之余二。问物几何？五五数之余三；七七数之余二。问物几何？答曰：二十三。答曰：二十三。232*70+3*21+2*15(mod 105)232*70+3*21+2*15(mod 105)（口口 诀诀：三三 人人 同同
11、行行 七七 十十 稀稀，五五 树树 梅梅 花花 廿廿 一一 枝枝，七子团圆月正半，除百零五便得知。）七子团圆月正半，除百零五便得知。）问，问，7070，2121，1515如何得到的如何得到的？原问题为：原问题为：求解同余方程组求解同余方程组注意注意：解题口诀提示我们先解下面三个特殊的同余方：解题口诀提示我们先解下面三个特殊的同余方程组程组(1)(2)(3)的特殊解的特殊解=?=?=?以方程（以方程（1 1）为对象，相当于解一个这样的同余方程）为对象，相当于解一个这样的同余方程 35y1(mod 3)35y1(mod 3)，解出解出y=2y=2（mod 3mod 3）于是于是x x 35*2 3
12、5*2 70(mod105)70(mod105)类类似似地地得得到到（2 2）、（3 3）方方程程的的模模105105的的解解2121、1515。于是有：于是有：中中国国剩剩余余定定理理：设自然数m1,m2,mr两两互素，并记M=m1m2mr，b1.br表示r个整数，则同余方程组（A）在模M同余的意义下有唯一解。例如：例如：x1 mod 2x1 mod 2x2 mod 3x2 mod 3x3 mod 5x3 mod 5解：解：M=235=30M=235=30M1=15,M2=10,M3=6M1=15,M2=10,M3=615y11mod2,y1=115y11mod2,y1=110y21mod3,y2=110y21mod3,y2=16y31mod5,y3=16y31mod5,y3=1所以所以,x=1151+2101+361=5323 mod 30,x=1151+2101+361=5323 mod 30练习：思考题与习题n编写一个程序找出编写一个程序找出100-200100-200间的素数间的素数n计算计算:(-7503)mod 81 ,(-81)mod 7503:(-7503)mod 81 ,(-81)mod 7503n编写程序实现欧几里德算法和扩展的欧几里德算法。编写程序实现欧几里德算法和扩展的欧几里德算法。n利用中国剩余定理求利用中国剩余定理求：