《東南大學信息安全課件》由會員分享，可在線閱讀，更多相關《東南大學信息安全課件（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第二章 信息安全數(shù)學基礎東南大學 網(wǎng)絡空間安全學科胡愛群 教授 2021-6-5 1 主要內(nèi)容 素數(shù)、素數(shù)性質(zhì) 、大素數(shù)生成方法； 同余、中國剩余定理； 群、環(huán)、域、有限域。 2021-6-5 2 素數(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ù)。 2021-6-5 3 互素的概念(a,b)=(b,a);如果 b|a, 則（a,b）=b;如果 p a，則（p,a）=1,即互素。a,b是整數(shù)，p是素數(shù) 2021-6-5 4
2、素數(shù)的判定和生成 2021-6-5 5 練習：判斷139為素數(shù)還是合數(shù)？2021-6-5 6 同余的概念練習：39=4 mod(7); 61=5 mod(7). 2021-6-5 7 Euler函數(shù)定義： 設m是一個正整數(shù)，把0,1,m-1中與m互素的數(shù)的個數(shù)記作(m), (m)就叫做Euler函數(shù)。練習： 求(10)=？ (77)=?定理： 設m、n是兩個互素的正整數(shù)，則(mn)=(m)(n). 2021-6-5 8對于素數(shù)m ，(m)=? Euler函數(shù)的推論設p、q是不同的素數(shù)， 則 （1）(pq)=pq-p-q+1. 設n=pq, 則（2）如果知道n和(n)，就可求出p和q.練習：證明
3、素數(shù)的性質(zhì)（1）和（2）。可求解該二元方程組得到p和q. 2021-6-5 9 Euler定理 設m是大于1的整數(shù)，(m)是m的Euler函數(shù)。如果a是滿足（a,m）=1的整數(shù)，則 練習：驗證 210=1 mod(11)。解：m=11, a=2, (m)=10, (2,11)=1, 根據(jù)Euler定理，上式成立。 也可以這樣做：2 10=1024=1023+1=93*11+1=1 mod(11)2021-6-5 10 Fermat定理練習：p=17, a=4, 4 17=4 mod (17) 2021-6-5 11 大素數(shù)的生成 逐個查找太費時間，可以利用Euler定理進行檢驗，稱為Ferma
4、t素性檢驗。 Euler定理：設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, 2 62=26022=(26)10 22=6410 221 mod(63)因此63不是素數(shù)。=1 mod(63)2021-6-5 12 素性檢驗給定奇數(shù)n3和安全參數(shù)t， 隨機選取整數(shù)b, 2bn-2; 計算r=bn-1 (mod n); 如果r1, 則n是合數(shù)； 重復
5、上述過程t次。注意：上述方法可以檢驗出來是合數(shù)，但若滿足r=1的n未必是素數(shù)。練習：n=561是合數(shù)，但依然滿足r=1.提示：561=3 .11.17 2021-6-5 13 中國剩余定理 2021-6-5 14 2021-6-5 15 求解韓信點兵問題： 2021-6-5 16 利用中國剩余定理求解大的冪次數(shù) 2021-6-5 17 Euclid除法及廣義Euclid除法 任意兩個整數(shù)a、b(b0),則對于任意的整數(shù)c, 存在唯一的整數(shù)q、r，使得 a=qb+r，crb+c.例子： 121=248+25例子：設a=169, b=121, 求a和b的最大公因子，即（a,b）利用廣義Euclid
6、除法： 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. 2021-6-5 18 RSA算法中私鑰的計算設有兩個素數(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 d=6574832021-6-5 19 群的概念定義：設G是一個具有結(jié)合法的非空集合，如果：（1）滿足結(jié)合律： a,b,cG, 都有 (ab)c=a(bc
7、);（2）G中存在單位元： e G, 對任意aG，都有 ae=ea=a;（3）G中的元素具有可逆元： 對任意aG， a -1 G, 使得aa-1=a-1a=e.G的結(jié)合法寫作乘法時，G稱為乘群；G的結(jié)合法寫作加法時，G稱為加群。2021-6-5 20 同態(tài)的概念設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)。 2021-6-5 21 環(huán)的概念定義：設R具有兩種結(jié)合法（通常表示為加法和乘法）的非空集合，如
8、果下列條件成立：（1）R對于加法構(gòu)成一個交換群；（2）（結(jié)合律） a,b,cR, 都有 (ab)c=a(bc);（3）（分配律） a,b,cR, 都有a(b+c)=ab+ac;則R叫做環(huán)。 2021-6-5 22 有限域的概念集合F=a，b，對F的元素定義了兩種運算：“+”和“*”，并滿足以下3個條件：（1）F的元素關于運算“+”構(gòu)成交換群，設其單位元素為0；（2）F0的元素關于運算“*”構(gòu)成交換群。即F中元素排除元素0后，關于“*”法構(gòu)成交換群。（3）分配律成立，即對于任意元素a，b，c F，恒有a*(b+c)=(b+c)*a=a*b+a*c。 p是素數(shù)時，F(xiàn)0，1，2，p-1，在mod p
9、意義下，關于求和運算“+” 及乘積“*”，構(gòu)成了域。F域的元素數(shù)目有限時稱為有限域, 記為GF(p)。有限域元素的數(shù)目稱為有限域的階。 2021-6-5 23 GF(p)有限域中的運算p=5 2021-6-5 24 三大難解數(shù)學問題 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ù)很困難。2
10、021-6-5 25 2、離散對數(shù)問題已知有限循環(huán)群G=gk|k=0,1,2,及其生成元g和階n=|G|. 給定整數(shù)a, 計算元素ga=h很容易； 給定元素h, 計算整數(shù)x, 0 xn, 使得gx=h非常困難。例如：給定p=20000000000000002559, g=11,a=20030428, 可以計算出g a=1134889584997235257 (mod p)但要求整數(shù)x, 使得gx=1134889584997235257 (mod p) 非常困難。 2021-6-5 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，計算整數(shù)x, 使得 xP=Q非常困難。 2021-6-5 27 習題1. 利用素數(shù)判定定理，求所有不超過110的素數(shù).2. 證明N=131為素數(shù).3. 求m=91的Euler函數(shù)(91)=?4. 用Euler定理，驗證 212=1 mod(11).5. 用中國剩余定理，求 x=2 100000 mod(55). 2021-6-5 28
東南大學信息安全課件
