第2章信息安全数学基础(数论)ppt课件

第2章信息安全数学基础(数论)ppt课件电子科技大学计算机科学与工程学院计算系统与网络安全ComputerSystemandNetworkSecurity.子夏曰：“贤贤易色；事父母，能竭其力；事君，能致其身；与朋友交，言而有信。虽日未学，吾必谓之学矣。”人际关系：父子；君臣；朋友；夫妻数论基础.第2章信息安全数学基础（数论）.第2章信息安全数学基础（数论）.2.整除的基本性质(N—整数集)(1)a(a≠0),a|0,a|a(同理bN,1|b)(2)b|a,cb|ca(3)a|b,b|ca|c.（传递性）(4)a|b,a|ca|(xb+yc)...

电子科技大学计算机科学与工程学院计算系统与网络安全ComputerSystemandNetworkSecurity.子夏曰：“贤贤易色；事父母，能竭其力；事君，能致其身；与朋友交，言而有信。虽日未学，吾必谓之学矣。”人际关系：父子；君臣；朋友；夫妻数论基础.第2章信息安全数学基础（数论）.第2章信息安全数学基础（数论）.2.整除的基本性质(N—整数集)(1)a(a≠0),a|0,a|a(同理bN,1|b)(2)b|a,cb|ca(3)a|b,b|ca|c.（传递性）(4)a|b,a|ca|(xb+yc)(x,yN)(5)b|a且a≠0|b|≤|a|(6)cb|ca,b|a1.定义：设整数a和b,且a≠0，如果存在整数k使得b=ak，那么就说a整除a（或b能被a整除），记作a|b，或者说b是a的倍数。举例：3|15,-15|60整除定义及性质. 证明：（1）作一个整数序列（2）反证法带余数除法：如果a，b是两个整数，其中b>0，则存在两个整数q和r，使得a＝bq＋r（0≤r＜b）成立，且q和r是唯一的。带余数除法.非负最小剩余的性质：（1）=<+>（2）=<->（3）=<>定义（非负最小剩余）a＝bq＋r（0≤r＜b）中r叫做非负最小剩余，常记做b=r（在不致引起混淆的情况下，b常常省略）带余数除法.1.定义：一个大于1的整数p，只能被1或者是它本身整除,而不能被其他整数整除，则称整数为素数(primenumber)，否则就叫做合数(composite)。eg素数（2，3，5，7，11，13等）合数（4，6，8，9，12等）素数定义及素数个数定理.2.补充定理(1)：设a是任一大于1的整数，则a的除1外的最小正因子q是素数，并且当a是合数时：素数补充定理.2.补充定理(2)：若p是一个素数，a是任一整数，则有p|a或(p,a)=1素数补充定理（续）.素数补充定理（续）2.补充定理：p为素数，且p|ab,那么p|a或p|b。更一般地，如果ab…z能够被素数p整除，那么a,b,…,z中的某个数必能被p整除。.3.素数个数定理（1）：素数的个数是无限的原因：（1）N（N>1）的除1外的最小正因数q是一个素数（2）如果q=pi，（i＝1,2,…,k),且q|N，因此q|(N-p1p2,…..pk)，所以q|1，与q是素数矛盾。素数个数定理及证明证明：反证法假设正整数个数是有限的，设为p1,p2,…..,pk令：p1p2…pk+1=N(N>1)则N有一个素数p，且p≠pi（i=1,2,…,k).故p是上述k个素数外的另外一个素数。因此与假设矛盾。.素数定义及素数个数定理3.素数个数定理（2）：设(x)是小于x的素数个数，则(x)≈x/lnx,即x→∝时，比值(x)/(x/lnx)→1eg:可以估算100位素数的个数：(10100)-(1099)≈10100/(ln10100)–1099/(ln1099)≈3.9*1097..1.整数的唯一分解定理定理（算术基本定理）:设n∈Z,有分解式,n=±p1e1p2e2...pmem,其中p1,p2,…,pm∈Z+是互不相同的素数,e1,e2,…,em∈Z+,并且数对(p1,e1),(p2,e2),…,(pm,em)由n唯一确定（即如果不考虑顺序，n的分解是唯一的）.eg:504=23327,1125=3253整数的唯一分解定理.1.定义两个整数a,b的最大公约数，就是能同时整除a和b的最大正整数,记为gcd(a,b)，或(a,b).eg:gcd(5,7)=1，gcd(24,60)=12，最大公约数定义及求法2.求最大公约数的两种方法：(1)因数分解：eg:1728=2632,4536=23347,gcd(1728,4536)=2332=72..(2)欧几里得(Euclid)算法设a,bN,a>b>0,用以下方法可求出gcd(a,b).最大公约数的欧几里得算法.Euclid算法实例：求gcd(132,108).最大公约数的欧几里得算法（续）.欧几里得算法（例1）gcd（1180，482）＝2求：gcd（1180，482）最大公约数的欧几里得算法（续）.欧几里得算法（例2）：求gcd(12345,1111)最大公约数的欧几里得算法（续）.欧几里得算法抽象规律：余数－除数－被除数－忽略最大公约数的欧几里得算法（续）.欧几里得算法实现最大公约数的欧几里得算法（续）.特别a,b为素数时gcd(a,b)=1，存在ma+nb=1.上述求rn=ma+nb的方法叫做扩展的Euclid算法利用该方法我们可以求ax+by=d的解,这里d=(a,b)证明：根据Euclid算法a=bq1+r1b=r1q2+r2r1=r2q3+r3,……rn-2=rn-1qn+rngcd(a,b)=rn=rn-2-rn-1qn=……=ma+nb3.定理设a,b∈Z+,则存在m,n∈Z使得gcd(a,b)=ma+nb.扩展的欧几里得算法.计算出了gcd(a,b);但是并没有计算出两个数m，n来，使得：ma+nb=gcd(a,b)扩展的欧几里得算法的结果计算出了gcd(a,b);计算出两个数m，n来，使得：ma+nb=gcd(a,b)扩展的欧几里得算法（续）欧几里得算法的结果.利用该方法我们可以求密码学方程ax+by=d的解,这里d=(a,b)例如:求132x+108y=12的解解：12=gcd(132,108)12=108-424=108-4(132-1081)=108–4132+4108=5*108–4*132扩展的欧几里得算法（续）.第2章信息安全数学基础（数论）.证明：必要性:设a≡b(modm),a=mp+r,b=mq+r,0≤r0，C1，…Cm-1是模数m的剩余类，则有：（1）每一个整数恰好包含在某一个类Cj中（0≤j≤m-1）（2）两个整数x和y属于同一个类的充要条件是x≡y（modm）剩余类和完全剩余系（续）.定义（完全剩余系）：在模数m的剩余类C1，…Cm-1中各取一数aj（j=0，1，…，m-1），此m个数a0，a1，…，am-1称为模数m的一组完全剩余系。剩余类和完全剩余系（续）例如：m＝3C0＝｛0，3，6，9，…｝C1＝｛1，4，7，10，…｝C2＝｛2，5，8，11，…｝则a0＝0，a1＝1，a2＝2就是模m的一组完全剩余系。.定理（完全剩余系）：m个整数组成模数m的一组完全剩余系的充要条件是两两对模数m不同余。剩余类和完全剩余系（续）定义（非负最小完全剩余系）由0，1，2，…，m-1组成的剩余系称为模数m的非负最小完全剩余系。.定理（完全剩余系）：设（k,m）＝1，a0，a1，…，am-1是模数m的一组完全剩余系，则：ka0，ka1，…，kam-1也是模数m的一组完全剩余系。剩余类和完全剩余系（续）.（1）剩余类可能包含多个集合（即：模数m的剩余类是多个集合）（2）完全剩余系专指一个集合剩余类和完全剩余系（续）定义（模数m互素的剩余类）如果一个模数m的剩余类里面的数与m互素，就称之为与模数m互素的剩余类。例如：m＝3C1＝｛1，4，7，10，…｝C2＝｛2，5，8，11，…｝都是模m互素的剩余类。.定义（缩系）在与模数m互素的全部剩余类中，各取一个数所组成的集合叫做模数m的一组缩系。剩余类和完全剩余系（续）例如：m＝3C1＝｛1，4，7，10，…｝C2＝｛2，5，8，11，…｝是模m互素的剩余类，而C＝｛4，5｝是模数m的一组缩系。问题：缩系含有多少个数？.欧拉函数的求法：（1）如果n是素数，则ϕ(n)=n-1（2）n＝pq，其中p，q为素数，则ϕ(n)=(p-1)(q-1)（3）1.定义（欧拉函数）欧拉函数ϕ(n)是一个定义在正整数上的函数，ϕ(n)的值等于序列0，1，2，…，n－1中与n互素的数的个数。费马小定理和欧拉定理.定理（缩系中数的个数）模数m的缩系含有ϕ(n)个数。费马小定理和欧拉定理（续）例如：m＝3，ϕ(m)＝2，因而C＝｛1，2｝含有两个数。定理（缩系）若a1，a2，…，aϕ(m)是ϕ(m)个与m互素的整数，则a1，a2，…，aϕ(m)是模数m的一组缩系的充要条件是它们两两对模数m不同余。.定理：若（a，m）＝1，x通过模数m的缩系，则ax也通过模数m的缩系。费马小定理和欧拉定理（续）证明：当x通过模数m的缩系，则ax通过ϕ(m)个整数，由于（a，m）=1，（x，m）=1，因此（ax，m）=1。若ax1≡ax2（modm），可知x1≡x2（modm），与假设x通过模数m的缩系矛盾，故ax通过模数m的缩系。.(2)欧拉定理设m>1，如果gcd(a,n)=1,则:aϕ(n)≡1modn.eg:求7803的后三位数字解：7803（mod1000）的结果ϕ(1000)=1000(1-1/2)(1-1/5)=400，有7803≡(7400)273≡343(mod1000)费马小定理和欧拉定理（续）.推论（Fermat小定理）:p素数,a是整数且不能被p整除,则:ap-1≡1modp.费马小定理和欧拉定理（续）例如：求253(mod11)=?由Fermat小定理:210=1024≡1(mod11)253=(210)523≡1523≡8(mod11).（1）通常情况下，如果2n-1≡1(modn),n为素数,然而,也有例外:561=31117是合数,但2560≡1(mod561)。因此，如果2n-1≡1(modn),那么n可能为素数。（2）但2n-1模n不等于1,那么n不可能为素数这为我们提供一种寻找素数的方法，给定一个n,计算2n-1模n是否等于1，如果不等于1，n为非素数，如果等于1，还需用更复杂的方法来判断是否为素数，比如：(1)索洛维-斯特拉森(Solovay-Strassen)素性检测算法(2)米勒-罗宾(Miller-Rabin)素性检测算法(3)AKS算法费马小定理和欧拉定理的应用.解：（1）由费尔马定理2100（mod1001）＝1（mod101）（2）243210≡(2100)432210≡210≡1024(mod101)=14eg:计算243210（mod101）欧拉定理的应用.7.一次同余式(1)定义:设m∈Z+,a,b∈Z,a≠0,我们把ax+b≡0(modm)称为模数m的一次同余式.如果x0∈Z满足:ax0+b≡0(modm)则称x≡x0(modm)是同余式的解.eg:同余式2x+1≡0(mod3)有解x0=1.同余式2x+1≡0(mod4)无解.同余式2x+1≡0(mod5)有解x0=2.一次同余式.(2)一次同余式的解定理1:设m∈Z+,a,b∈Z,a≠0,(a,m)=1,则同余式ax≡b(modm)恰有一个解x≡baϕ(m)-1(modm).eg:同余式2x+1≡0(mod5)有解:x0=(-1)×2ϕ(5)-1≡4×23≡32≡2(mod5)一次同余式（续）.定理2:设m∈Z+,a,b∈Z,a≠0,(a,m)=d,则同余式ax≡b(modm)有解的充要条件是d|b.在d|b的条件下,同余式有d个解.eg:同余式2x≡3(mod4)无解⇐d=(2,4)=2ł3.同余式2x≡4(mod6)d=(2,6)=2|4有2个解:x=2,5.一次同余式的解.第2章信息安全数学基础（数论）.《孙子算经》中记载着一道世界闻名的“孙子问题”：“今有无不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”孙子问题等同于下面这样一个问题：已知x=2mod3，x=3mod5且x=2mod7，求整数x。中国剩余定理.中国剩余定理（续）.中国剩余定理（续）.中国剩余定理（续）.中国剩余定理(孙子:SunZe,公元前450年,孙子定理)：设自然数m1,m2,…mr两两互素，并记M=m1m2…mr，则同余方程组:x≡b1(modm1)x≡b2(modm2)..............x≡br(modmr)有唯一解：x≡b1*M1*y1+b2*M2*y2+…+br*Mr*yr(modM)Mi=M/mi,yi=Mi-1(modmi)(1ir)中国剩余定理（续）.例如:求以下同余方程组的解：x≡5mod7x≡3mod11x≡10mod13中国剩余定理解同余方程组解：r=3,m1=7,m2=11,m3=13;b1=5,b2=3,b3=10;模M=m1m2m3=1001,M1=M/m1=m2m3=143,M2=91,M3=77.y1=M1-1(modm1)=143-1(mod7)=5,y2=4,y3=12.解为:x=b1M1y1+b2M2y2+b3M3y3(modM)=51435+3914+107712(mod1001)=13907(mod1001)=894验证:x=894=1277+5=5(mod7).中国剩余定理：其中：m=miMiMi’Mi=1(modm)中国剩余定理（续）.中国剩余定理（续）.例如（孙子算经）解法：表格法中国剩余定理求解同余方程组.中国剩余定理（续）.中国剩余定理（续）.中国剩余定理（续）.第2章信息安全数学基础（数论）.计算Xa(modn),其中x,a,n∈Z+Eg:计算21234(mod789)一种有效的方法：24≡1628≡256216≡2562≡49232≡492≡34264≡342≡3672128≡3672≡5592256≡5592≡372512≡372≡58021024≡5802≡2861234=1024+128+64+16+2（1234=(10011010010)2）21234=286559367494≡481(mod789)模的幂运算优势：模的幂运算可快速完成，并且不需要太大内存.模的幂运算（续）但是，上述计算过程并不适合于计算机程序实现。为此，可以采用“重复平方-乘”运算来进行指数模运算。.模的幂运算（续）重复平方-乘算法.第2章信息安全数学基础（数论）.整数的次数由欧拉定理知道：如果(a,m)＝1，m>1，则aϕ(n)≡1(modm)也就是说，如果(a,m)＝1，m>1，则存在一个整数γ满足:aγ≡1(modm)定义（整数的次数）：若(a,m)＝1，m>1，则使得同余式aγ≡1(modm)成立的最小正整数γ叫做a对模m的次数。.整数的次数（续）定理：设a对模数m的次数为l，an≡1（modm），则l|n。证明：如果结论不成立，则必有两个整数q和r，使得：n＝ql＋r（00,(g,m)=1,如果整数g对m的次数为ϕ(m)，则g叫做m的一个本原根（或原根）.eg:3是模7的本原根因为3ϕ(7)≡36≡1(mod7)本原根定义.本原根定义（续）例如：m＝7，a＝2Φ(m)＝6＝2×322（mod7）＝423（mod7）＝1因此：a对模数m的次数为3≠Φ(m)所以：2不是7的本元根。.定理（原根）设整数m>0,(g,m)=1,则g是m的一个原根的充要条件是：g，g2，…gϕ(m)组成模数m的一组缩系。本原根判断定理说明：如果g是m的一个原根，则模数m的一组缩系可表示为形如定理中的几何级数。.2.定理：设对素数p而言，如果g是一个本原根(1)如果n是整数，那么gn≡1(modp)当且仅当n≡0(modp-1)(2)如果j和k都是整数，那么gj≡gk当且仅当j≡k(modp-1)本原根有关定理.问题：是否所有的正整数都有原根？本原根有关定理（续）例如：m＝12Φ(m)＝6＝2×3，与m互素的正整数包括5，7，11。52（mod12）＝1因此，5对12的次数是272（mod12）＝1因此7对模数m的次数为2112（mod12）＝1因此11对模数m的次数为2因此m＝12没有原根。.定理（整数存在原根的必要条件）：设m>1，若m有原根，则m必为下列诸数之一：2，4，pl，2pl（l≥1，p为奇素数）。本原根有关定理（续）定理（整数存在原根的充分条件）：设m＝2，4，pl，2pl（l≥1，p为奇素数）时，则m有原根。定理（整数原根个数）：设m有一个原根g，则m恰有ϕ(ϕ(m))个对模数m不同余的原根，这些原根由以下集合给出：.本原根有关定理（续）.原根的判断：一般来说，判断g是否时一个素数m的原根时，不需要逐一计算g1，g2，…，gϕ(m)，而仅需要计算gt(modm），其中t|ϕ(m)。本原根有关定理（续）.本原根有关定理（续）.本原根有关定理（续）定理（原根的计算）：.本原根有关定理（续）.本原根有关定理（续）.本原根有关定理（续）定理（原根的计算）：.本原根有关定理（续）一个计算原根的算法：.本原根有关定理（续）.本原根有关定理（续）.指数如果整数m>0有一个元根g，g，g2，…gϕ(m)(或数1,g，g，g2，…gϕ(m)-1）组成模数m的一组缩系。例如，3是模7的本原根，因此：31≡332≡233≡634≡435≡536≡1上述六个数刚好是模数m的一组缩系。.指数（续）定义：任一整数n，（n，m）＝1，必有唯一的整数k（0≤k<ϕ（m）），满足：n≡gk（modm）其中k叫做n对模数m的指数，记做k＝indgn（简记为indn）(指数也叫做离散对数)。.指数（续）.指数（续）.指数（续）.指数的性质：设g是m的原根，如果(a,m)＝(b,m)＝1：指数（续）.指数（续）.指数（续）.指数（续）.离散对数困难问题基于离散对数困难性假设，EIGamal提出了EIgamal公钥密码体制。.离散对数困难问题（续）.第2章信息安全数学基础（数论）.模n逆矩阵定理：一个平方矩阵是模n可逆的当且仅当它的行列式和n是互素的.证明：假设M平方矩阵在模n下有逆矩阵N,则MN≡I(modn)det(MN)≡det(M)det(N)≡det(I)≡1(modn)因为det(M)可逆(det(M),n)=1Eg:22矩阵,通常的求逆为：ab-1d-b=1/(ad-bc)cd-ca.12假如要求(mod11)的逆34因为ad-bc=-2,需求-2(mod11)的逆，因为5(-2)≡1(mod11)124-24-291≡1/(-2)≡5≡(mod11)34-31-3175模n逆矩阵（续）.第2章信息安全数学基础（数论）.模n平方根定义(二次剩余）设n是一个大于1的正整数，a∈Z,a≠0(modn).如果同余方程x2≡a(modn)有一个解1≤x≤n-1,则称a是模数n的二次剩余，而x称之为a模n的平方根。如果上述方程无解，则a称之为模数n的非二次剩余。.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.模n平方根（续）.第2章信息安全数学基础（数论）.有限域.有限域（续）.多项式.多项式（续）.多项式（续）.多项式（续）.多项式（续）.多项式（续）.多项式（续）.多项式（续）.多项式（续）.多项式（续）.多项式（续）.多项式（续）.多项式（续）.多项式（续）.eg:GF（23）域的构造：p=2,z2=｛0,1｝,不可约多项式m(x)=1+x2+x3,多项式F[x]=Z2[x]GF（23）=Z2[x]/<1+x2+x3>=｛0，1，x,x+1,x2,x2+1,x2+x,x2+x+1｝有限域.参考书参考书：杨义先等，信息安全理论与技术，邮电出版社MaoWenbo，ModernCryptography:TheoryandPractice ，电子工业出版社，2004BruceSchneier,AppliedCryptography,Protocols,algorithms,andsourcecodeinC(2ndEdition)(应用密码学－协议、算法与C源程序，吴世忠、祝世雄、张文政等译)《PrinciplesofComputerSecurity》Wm.A.Conklin,McGraw-Hill,2005《信息安全原理及应用》阙喜戎等，清华大学出版社，2003年其他信息安全相关学术论文.课外阅读资料MaoWenbo，ModernCryptography:TheoryandPractice ，电子工业出版社，2004.AnyQuestion?Q&A.

                    本文档为【第2章 信息安全数学基础(数论)ppt课件】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

第2章 信息安全数学基础(数论)ppt课件

你可能还喜欢

第2章信息安全数学基础(数论)ppt课件