東南大學(xué)信息安全課件.ppt

1、第二章 信息安全數(shù)學(xué)基礎(chǔ),東南大學(xué) 網(wǎng)絡(luò)空間安全學(xué)科 胡愛群 教授,2020/7/29,1,主要內(nèi)容,素數(shù)、素數(shù)性質(zhì) 、大素數(shù)生成方法； 同余、中國剩余定理； 群、環(huán)、域、有限域。,2020/7/29,2,素數(shù),定義：設(shè)整數(shù)n0, 1。如果除了 1和 n外，n沒有其它因數(shù) （因子），則n是素數(shù)（或質(zhì)數(shù)、不可約數(shù)）。否則n叫合數(shù)。 素數(shù)總是指正整數(shù)，通常寫成 p.,例子： 2，3，5，7都是素數(shù)，而4，6，10，15，21都是合數(shù)。,2020/7/29,3,互素的概念,(a,b)=(b,a); 如果 b|a, 則（a,b）=b; 如果 pa，則（p,a）=1,即互素。,a,b是整數(shù)，p是素數(shù),2

2、020/7/29,4,素數(shù)的判定和生成,2020/7/29,5,練習(xí)：判斷139為素數(shù)還是合數(shù)？,2020/7/29,6,同余的概念,練習(xí)：39=4 mod(7); 61=5 mod(7).,2020/7/29,7,Euler函數(shù),定義： 設(shè)m是一個正整數(shù)，把0,1,m-1中與m互素的數(shù)的個數(shù)記作(m), (m)就叫做Euler函數(shù)。,練習(xí)： 求(10)=？ (77)=?,定理： 設(shè)m、n是兩個互素的正整數(shù)，則(mn)=(m)(n).,2020/7/29,8,對于素數(shù)m ，(m)=?,Euler函數(shù)的推論,設(shè)p、q是不同的素數(shù)， 則 （1）(pq)=pq-p-q+1. 設(shè)n=pq, 則（2）如

3、果知道n和(n)，就可求出p和q.,練習(xí)：證明素數(shù)的性質(zhì)（1）和（2）。,可求解該二元方程組得到p和q.,2020/7/29,9,Euler定理,設(shè)m是大于1的整數(shù)，(m)是m的Euler函數(shù)。如果a是滿足（a,m）=1的整數(shù)，則,練習(xí)：驗證 210=1 mod(11)。,解：m=11, a=2, (m)=10, (2,11)=1, 根據(jù)Euler定理，上式成立。,也可以這樣做：210=1024=1023+1=93*11+1=1 mod(11),2020/7/29,10,Fermat定理,練習(xí)：p=17, a=4, 417=4 mod (17),2020/7/29,11,大素數(shù)的生成,逐個查找

4、太費時間，可以利用Euler定理進行檢驗，稱為Fermat素性檢驗。,Euler定理：設(shè)n是大于1的整數(shù)，(n)是n的Euler函數(shù)。如果a是滿足（a,n）=1的整數(shù)，則,如果n是一個素數(shù)，則(n)=n-1, 有an-1=1 mod(n). 反過來說，如果有一個整數(shù)a, 且（a, n）=1, 使得an-11 mod(n), 那么n是一個合數(shù)，不是素數(shù)。,例子：n=63. 假定a=2, 262=26022=(26)10 22=6410 221 mod(63) 因此63不是素數(shù)。,=1 mod(63),2020/7/29,12,素性檢驗,給定奇數(shù)n3和安全參數(shù)t， 隨機選取整數(shù)b, 2bn-2;

5、計算r=bn-1 (mod n); 如果r1, 則n是合數(shù)； 重復(fù)上述過程t次。,注意：上述方法可以檢驗出來是合數(shù)，但若滿足r=1的n未必是素數(shù)。 練習(xí)：n=561是合數(shù)，但依然滿足r=1. 提示：561=3.11.17,2020/7/29,13,中國剩余定理,2020/7/29,14,2020/7/29,15,求解韓信點兵問題：,2020/7/29,16,利用中國剩余定理求解大的冪次數(shù),2020/7/29,17,Euclid除法及廣義Euclid除法,任意兩個整數(shù)a、b(b0),則對于任意的整數(shù)c, 存在唯一的整數(shù)q、r，使得 a=qb+r，crb+c.,例子： 121=248+25,例子：

6、設(shè)a=169, b=121, 求a和b的最大公因子，即（a,b） 利用廣義Euclid除法： 169=1121+48 121=2 48+25 48=1 25+23 25=1 23+2 23=11 2+1 2=2 1 因此 （169，121）=1.,2020/7/29,18,RSA算法中私鑰的計算,設(shè)有兩個素數(shù)p=719, q=1283. n=p q=719 1283=922477 (n)=(p) (q)=(p-1)(q-1)=920476 隨機選取整數(shù)e, 1e(n), 使得（e, (n)）=1. 公鑰是Kp=n,e, 私鑰為d, 1d(n)，滿足e d=1 mod(n),需要把上式寫成：1=

7、？(n)+ed,(n)=920476=1314967+4 7=24+(-1) 1=-7+24 =(-1)7+2（920476-1314967） =2920476+（-262993）7 =（2-7）920476+（920476-262993）7 =（-5）920476+6574837 = d=657483,2020/7/29,19,群的概念,定義：設(shè)G是一個具有結(jié)合法的非空集合，如果： （1）滿足結(jié)合律： a,b,cG, 都有 (ab)c=a(bc); （2）G中存在單位元： e G, 對任意aG，都有 ae=ea=a; （3）G中的元素具有可逆元： 對任意aG， a-1 G, 使得aa-1=a

8、-1a=e.,G的結(jié)合法寫作乘法時，G稱為乘群；G的結(jié)合法寫作加法時，G稱為加群。,2020/7/29,20,同態(tài)的概念,設(shè)G、G是兩個群，f是G到G的一個映射，如果對任意的a、bG，都有 f(ab)=f(a)f(b) 則f叫做G到G的一個同態(tài)。,如果f是一個加密過程，即 E(ab)=E(a)E(b), 稱為乘同態(tài)。 E(a+b)=E(a)+E(b), 稱為加同態(tài)。,2020/7/29,21,環(huán)的概念,定義： 設(shè)R具有兩種結(jié)合法（通常表示為加法和乘法）的非空集合，如果下列條件成立： （1）R對于加法構(gòu)成一個交換群； （2）（結(jié)合律） a,b,cR, 都有 (ab)c=a(bc); （3）（分配

9、律） a,b,cR, 都有a(b+c)=ab+ac; 則R叫做環(huán)。,2020/7/29,22,有限域的概念,集合F=a，b，對F的元素定義了兩種運算：“+”和“*”，并滿足以下3個條件： （1）F的元素關(guān)于運算“+”構(gòu)成交換群，設(shè)其單位元素為0； （2）F0的元素關(guān)于運算“*”構(gòu)成交換群。即F中元素排除元素0后，關(guān)于“*”法構(gòu)成交換群。 （3）分配律成立，即對于任意元素a，b，cF，恒有a*(b+c)=(b+c)*a=a*b+a*c。 p是素數(shù)時，F(xiàn)0，1，2，p-1，在mod p意義下，關(guān)于求和運算“+” 及乘積“*”，構(gòu)成了域。F域的元素數(shù)目有限時稱為有限域, 記為GF(p)。 有限域元素

10、的數(shù)目稱為有限域的階。,2020/7/29,23,GF(p)有限域中的運算,p=5,2020/7/29,24,三大難解數(shù)學(xué)問題,1、大整數(shù)的因數(shù)分解問題 給定兩個大的素數(shù)p、q, 計算乘積p q=n很容易； 給定大整數(shù)n，求n的素因數(shù)p、q，使得n=p q非常困難。 如：p=20000000000000002559, q=8000000000000001239是兩個大素數(shù)，它們的乘積 n=1600000000000000229500000000000003170601 但要分解這個數(shù)很困難。,2020/7/29,25,2、離散對數(shù)問題,已知有限循環(huán)群G=gk|k=0,1,2,及其生成元g和階n

11、=|G|. 給定整數(shù)a, 計算元素ga=h很容易； 給定元素h, 計算整數(shù)x, 0 xn, 使得gx=h非常困難。 例如：給定p=20000000000000002559, g=11,a=20030428, 可以計算出ga=1134889584997235257 (mod p) 但要求整數(shù)x, 使得gx=1134889584997235257 (mod p) 非常困難。,2020/7/29,26,3、橢圓曲線離散對數(shù)問題,已知有限域Fp上的橢圓曲線點群 E(Fp)=(x,y)FpFp|y2=x3+ax+b, a,bFpUO 點P=(x,y)的階為一個大的素數(shù)。 給定整數(shù)a, 計算點Q=aP=(xa, ya)很容易； 給定點Q，計