《信息保障與安全》05-數(shù)論入門

1、. 數(shù)論入門數(shù)論入門 .2022-1-1華中農(nóng)業(yè)大學(xué)信息學(xué)院2n整數(shù)：整數(shù)：q整數(shù)集整數(shù)集 , -3, -2, -1, 0, 1, 2, 3, 記為記為Z。n整除：整除：q設(shè)設(shè)a, b為整數(shù)。若存在某個整數(shù)為整數(shù)。若存在某個整數(shù)c, 使得使得b=ac, 則則稱稱a整除整除b（等價地，稱（等價地，稱a是是b的一個因子，或者的一個因子，或者說說a為為b的一個因子）。若的一個因子）。若a整數(shù)整數(shù)b，則記為，則記為 a | b 。n例如：例如：.2022-1-1華中農(nóng)業(yè)大學(xué)信息學(xué)院3n整除的基本性質(zhì)：整除的基本性質(zhì)：q對所有的整數(shù)對所有的整數(shù)a，b，c，有以下正確結(jié)論：，有以下正確結(jié)論：q a | a

2、q若若 a | b 且且 b | c ，則，則 a | c 。q若若 a | b 且且 a | c，則對于所有的整數(shù)，則對于所有的整數(shù)x，y，有有a |（bx+cy）。）。q若若 a | b 且且 b | a，則，則 a = + b 或或 a = -b 。n例如例如 .2022-1-1華中農(nóng)業(yè)大學(xué)信息學(xué)院4n整數(shù)的整除算法整數(shù)的整除算法q若若a，b均為整數(shù)，且均為整數(shù)，且b=1, 則按照則按照a除以除以b的普的普通長除法可以找到整數(shù)通長除法可以找到整數(shù)q（商）和（商）和r余數(shù)，使余數(shù)，使得：得：a=qb+r，其中，其中0=r Ring Field.域相關(guān)概念及定理n域的特征 - 任意元素a的n

3、次累計和為0的最小的n；域的特征要么是素數(shù)，要么是0(沒有)；n素域：沒有非0真子域的域；n有限域的階是pn（其中p是素數(shù)）；n有限域的乘法群是循環(huán)群；.可逆在加/解密中的重要性n加密的操作對象是比特分組，通常被看作整數(shù)加密是對整數(shù)的變換。這種變換必須能恢復(fù)(解密時)，即可逆。如果加密是乘法，則解密就是除法，而域上正好有除法-乘法逆元。n對于8bits字節(jié)，希望Z256是域，但它不是；于是轉(zhuǎn)而尋求GF(28)，它是域。nAES的S盒是基于模2系數(shù)的模某8次不可約多項式的剩余類。.4.2 模運算n模運算即求余數(shù)（C語言中的運算符）x mod na其中0ab)gcd(a, b) = gcd(b,

4、a mod b)n求最大公因子輾轉(zhuǎn)相除法（歐幾里德算法）gcd(a, b) = gcd(b%a, a%b).GCD(1970,1066)1970 = 1 x 1066 + 904 gcd(1066, 904)1066 = 1 x 904 + 162 gcd(904, 162)904 = 5 x 162 + 94 gcd(162, 94)162 = 1 x 94 + 68 gcd(94, 68)94 = 1 x 68 + 26 gcd(68, 26)68 = 2 x 26 + 16 gcd(26, 16)26 = 1 x 16 + 10 gcd(16, 10)16 = 1 x 10 + 6 gc

5、d(10, 6)10 = 1 x 6 + 4 gcd(6, 4)6 = 1 x 4 + 2 gcd(4, 2)4 = 2 x 2 + 0 gcd(2, 0).函數(shù)gcd(a, b)nint gcd(int a, int b)nnif (a=0) | (b=0)nreturn a+b;nelsenreturn gcd(a%b, b%a);n.4.4 有限域GF(p)n域，無限域n有限域，又叫Galoris域有限域的階都有pn的形式階為p的有限域記為GF(p)n唯一性 (Isomorphism)q在同構(gòu)意義下，某階有限域只有一個nGF(p)：(Zp, +, x)GF(pm)：q系數(shù)在Zp上的模某不

6、可約多項式的多項式域GF(2n)：p=2.GF(p)：(Zp, +, x)n逆元q由于p是素數(shù)，所以除了0外都有逆元nGF(p=2)：(Z2, +, x)GF(p=7)：(Z7, +, x)* GF(p=8)：(Z8, +, x)不是域.求逆元：擴(kuò)展Euclid算法n擴(kuò)展擴(kuò)展Euclid算法算法做歐幾里德算法的計算序列做歐幾里德算法的計算序列r0q1r1r2 (令令r0n，r1a)r1q2r2r3r2q3r3r4rm-2qm-1rm-1rm (1)rm-1qmrm rm+1 (0)記記 t0 rm+1，t1rm，依依 tjtj-2 qi-1 tj-1 mod r0，得得 tm逆逆 r1的逆的逆

7、.擴(kuò)展Euclid算法舉例n22 1 mod 31311229-122 9 即 3022 9 mod 312229422-2(3022) 4 即 322 4 mod 31 92413022-2(322) 1即2422 1 mod 31n28 1 mod 757522819-22819 即 732819 mod 7528119928-1(7328)9 即 328 9 mod 7519291 (7328)-2(338)1 即6728 1 mod75n269 1 mod 349349126980 -126980 即 -126926938029 269-3(-1269)29 即 4269 802292

8、2 (-1269)-2(4269)22 即 -9269 291227 (4269)-1(-9269)7 即 13269 22371 (-9269)-3(13269)1即-48269 得301.函數(shù)reverse()nint reverse(int a, int m)nint b, b1=1, b2=0; / 逆元nint r, r1=a, r2=m; /ndo r = r2 % r1; / y-kx = rnb = (b2-(r2/r1)*b1)%m;nr2 = r1;b2 = b1;nr1 = r;b1 = b;n while (r1);nif (r=0) return 0;nif (b 1

9、是素數(shù)，當(dāng)且僅當(dāng)它只有因子是素數(shù)，當(dāng)且僅當(dāng)它只有因子1和和 p。q素數(shù)不能寫作其它數(shù)的乘積素數(shù)不能寫作其它數(shù)的乘積 q1是素數(shù)，但一般對它沒興趣是素數(shù)，但一般對它沒興趣 n例如：例如：2, 3, 5, 7是素數(shù)，是素數(shù)，4, 6, 8, 9, 10 不是素數(shù)不是素數(shù)n200以內(nèi)的素數(shù)以內(nèi)的素數(shù): 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197

10、199 2022-1-1.442022-1-1.4520004000600080001000020040060080010001200素數(shù)的個數(shù)2022-1-1.46素因子分解素因子分解n算數(shù)基本定理：算數(shù)基本定理：任意整數(shù)任意整數(shù) a 1 都可以唯一地因子分解為都可以唯一地因子分解為a = p1a1p2a2ptat ，其中，其中，pi 均是素數(shù)，且均是素數(shù)，且p1p20q如如. 91 = 7 x 13 ; 3600 = 24 x 32 x 52 2022-1-1.47互素和最大公因子互素和最大公因子n兩個數(shù)兩個數(shù) a, b 互素，如果它們沒有除互素，如果它們沒有除1以外的公因子以外的公因子

11、q如如 ( 8, 15 ) = 1 n最大公因子最大公因子q如如: 300 = 22 x 31 x 52 18 = 21 x 32 因此因此 GCD( 18, 300 ) = 21 x 31 x 50 = 62022-1-1.482 Fermat定理和定理和Euler定理定理nap-1 1 ( mod p)qp是素數(shù)，是素數(shù)，gcd( a, p ) = 1nFermat小定理小定理qap a (mod p)qp是素數(shù)，是素數(shù)，a是任意整數(shù)是任意整數(shù)2022-1-1.49n小于小于n且與且與n互素的正整數(shù)的個數(shù)互素的正整數(shù)的個數(shù) 如如 n = 10, 0, 1, 2, 3, 4, 5, 6, 7

12、, 8, 9 ，1, 3, 7, 9 (10) = 4n素數(shù)素數(shù) p (p) = p-1 n素數(shù)素數(shù)p, q，有，有 (pq) = (p-1) x (q-1) n如：如：(37) = 36(21) = (31) x (71) = 2 x 6 = 12n約定：約定： (1) = 12022-1-1.50n定定 理：理：設(shè)設(shè) n = p1e1 p2e2 prer，pi pj, pi為素數(shù)，為素數(shù)，ei1,則則(n) = n (1-p1-1) (1-p2-1)(1-pr-1)例如：例如：12 = 2 * 3 2022-1-1.512022-1-1.52na(n) 1 (mod n)對任意對任意 a,

13、 n，gcd(a, n) = 1n另一種表示：另一種表示：a(n)+1 a (mod n)對任意對任意 a, nn如：如：a = 3; n = 10; (10) = 4; 則則 34 = 81 1 mod 10a = 2; n = 11; (11) = 10;則則 210 = 1024 1 mod 11nFermat定理是定理是Euler定理的推論，或者說，定理的推論，或者說， Euler定理是定理是Fermat定理的更一般化形式。定理的更一般化形式。2022-1-1.53n與與RSA有關(guān)的結(jié)果有關(guān)的結(jié)果q兩個素數(shù)兩個素數(shù) p 和和 q，整數(shù)，整數(shù)m 和和 n，n = pq, 0 m 0, q

14、 是奇數(shù)，使得是奇數(shù)，使得 (n1) = 2kq 2. 隨機(jī)選擇整數(shù)隨機(jī)選擇整數(shù) a, 1 a n1 3. if aq mod n = 1 then 返回返回 (“不確定不確定); 4. for j = 0 to k 1 do 5. if (a2jq mod n = n-1) then 返回返回(“ 不確定不確定) 6. return (“合數(shù)合數(shù))2022-1-1.56概率方面的考慮概率方面的考慮n如果如果Miller-Rabin測試返回測試返回 “合數(shù)合數(shù)”，則該數(shù)，則該數(shù)一定不是素數(shù)；返回一定不是素數(shù)；返回“不確定不確定”，則該數(shù)可，則該數(shù)可能是素數(shù)，也可能是偽素數(shù)能是素數(shù)，也可能是偽素數(shù)n遇到偽素數(shù)的概率遇到偽素數(shù)的概率 1, (a, m) = 1, 則使得同余式則使得同余式 ai 1(mod m)成立的最小正整數(shù)成立的最小正整數(shù)i，叫做，叫做a對模對模m的離散對數(shù)。的離散對數(shù)。n指數(shù)一定是歐拉函數(shù)的因子指數(shù)一定是歐拉函數(shù)的因子n對任意整數(shù)對任意整數(shù)b和模數(shù)和模數(shù)p的本原根的本原根a，有唯一的冪，有唯一的冪i，使得，使得b ai mod p, 其中其中0 i p-1該指數(shù)該指數(shù)i稱為以稱為以a為底模為底模p的離散對數(shù)，記為的離散對數(shù)，記為 dloga, p(b)n離散對數(shù)不僅與模有關(guān)，而且與本原根有關(guān)。離散對數(shù)不僅與模有關(guān)，而且與本原根有關(guān)。n