計(jì)算機(jī)網(wǎng)絡(luò)安全技術(shù)第2章

1、第二章 預(yù)備知識(shí),21 數(shù)論基礎(chǔ) 數(shù)論是一門(mén)古老的數(shù)學(xué)分支。以前人們都認(rèn)為它是完全純粹的數(shù)學(xué)，在現(xiàn)實(shí)生活中很難找到它的實(shí)際應(yīng)用。自從1976年公開(kāi)密鑰體制誕生以來(lái)，現(xiàn)代密碼學(xué)就和數(shù)論有著千絲萬(wàn)縷的聯(lián)系。因此，我們先簡(jiǎn)單介紹一下有關(guān)的數(shù)論基本概念。 1 引言 我們約定：字母N表示全體自然數(shù)集合，Z表示全體整數(shù)集合，即 N = 0,1,2, Z = ,-2,-1,0,1,2,定義2.1.1 如果存在一個(gè)整數(shù)kZ使得n = kd，則稱d整除n，記作dn ，其中d稱作n的因數(shù)，n稱作d的倍數(shù)。如果不存在這樣一個(gè)整數(shù)kZ使得n = kd，則稱d不整除n，記作d + n 。 定義2.1.2 整數(shù)p（ 1）

2、,稱為素?cái)?shù)，如果除了1和其本身外，p沒(méi)有任何其他因數(shù)。不是素?cái)?shù)的整數(shù)稱為合數(shù)。 例21 6 = 23 ，6是合數(shù)，26 ，2是6的因數(shù)，6是2的倍數(shù)。7 = 17，除了1和7之外，沒(méi)有其他因數(shù)，因此7是素?cái)?shù)。 定理2.1.1 （帶余數(shù)除法）設(shè)a，b是兩個(gè)整數(shù)，其中b 0 。則存在兩個(gè)整數(shù)q，r使得 a = bq + r 0 r b 成立，其中q和r是唯一確定的。,設(shè)a，b是兩個(gè)整數(shù)。既是a的因數(shù)又是b的因數(shù)的數(shù)稱為a，b的公因數(shù)，a和b的所有公因數(shù)中最大者，稱為a和b的最大公因數(shù)，記作gcd ( a , b )。既是a的倍數(shù)又是b的倍數(shù)的數(shù)稱為a和 b的公倍數(shù)，a和b的所有公倍數(shù)中最小者稱為a

3、和b 的最小公倍數(shù)，記作lcm ( a , b )。顯然a和b的最大公因數(shù)與最小公倍數(shù)滿足下列等式： lcm (a , b ) gcd ( a , b ) = ab 如果對(duì)兩個(gè)整數(shù)a , b有g(shù)cd (a ,b ) = 1，則稱a與b互素。 定理2.1.2 設(shè)a ，b N，則存在兩個(gè)整數(shù)u和v使得 ua + vb =gcd ( a ，b ) 定理2.1.3 （算術(shù)基本定理）任何一個(gè)正整數(shù)m都存在唯一的因數(shù)分解形式 m = 其中，eiN，pi是素?cái)?shù)且p1p2p n。 這個(gè)分解形式也稱為m的標(biāo)準(zhǔn)分解形式。,例22 6 =23， 20=225， 100 =2252 有了算術(shù)基本定理后，就可以把任意整

4、數(shù)分解為標(biāo)準(zhǔn)形式，從而可以方便地求出兩個(gè)整數(shù)的最大公因數(shù)和最小公倍數(shù)。設(shè)a，b是兩個(gè)整整數(shù)，且有標(biāo)準(zhǔn)分解形式：,， ei ，fiN,則 gcd (a，b) = lcd (a，b) = 其中，min x ,y 表示x，y中最小者，max x ，y 表示x，y中最大者。,2Euclid算法 利用算術(shù)基本定理，原則上可以求得任何兩個(gè)整數(shù)的最大公因數(shù)，但當(dāng)兩個(gè)整數(shù)比較大時(shí)求他們的標(biāo)準(zhǔn)分解式就非常困難，目前還沒(méi)有有效的算法，因此求他們的最大公因數(shù)也變得非常困難。Euclid算法從另一方面解決了求兩個(gè)整數(shù)的最大公因數(shù)的問(wèn)題。 Euclid算法由稱為輾轉(zhuǎn)相除法，即帶余數(shù)除法，有下列不等式： a = bq1

5、+ r1 0 r1 b b = r1q2 + r2 0 r2 r1 rn-2 = rn-1 q n+rn 0 rn rn-1 rn-1 = rnqn+1 +rn+1 rn+1 = 0 因?yàn)槊窟M(jìn)行一次帶余數(shù)的除法，余數(shù)至少減1，而b是有限的。所以，最多進(jìn)行b次帶余數(shù)的除法，總可以得到一個(gè)余數(shù)是0的等式，即最后一個(gè)等式，而最后一個(gè)不為0的余數(shù)rn就是我們要求的最大公因數(shù)gcd( a，b )。,從上面的Euclid算法中可以看出，將r1 = a bq1代入第二個(gè)等式中，將r2 = b r1q2代入到第三個(gè)等式中， ，將rn-1 = rn-3 rn-2qn-1代入倒數(shù)第二個(gè)等式中，就可得到rn關(guān)于a

6、, b的一個(gè)表示式，其中 a , b的系數(shù)分別就是定理2.1.2中的u , v。故最后一個(gè)不為零的余數(shù)就是a、b的最大公因數(shù)。 例23 求gcd 1694,917 1694=1917+777 917=1777+140 777=5140+77 140=177+63 77=163+14 63=414+7 14=27+0 所以 gcd (1694，917) = 7,進(jìn)行回代 7=63-414 =63-4（77-63） = -477+563 =-477+5（140-77） =5140-977 =5140-9（777-5140） =-9777+50140 =-9777+50（917-777） =5091

7、7-59777 =50917-59（1694-917） -591694+109917 即 7= u1694+v917 其中 u =-59， v = 109,3. 同余 定義2.1.3 假設(shè)a 和b是兩個(gè)整數(shù)，m是一個(gè)正整數(shù)，如果m b a ，則稱a 和b對(duì)模m同余。記作 a b (mod m )。 例24 3和1對(duì)模2同余，4和1對(duì)模3同余，即3 1（mod 2），41（mod 3） 定理2.1.4 同余的性質(zhì) 設(shè)a，b，c和m是整數(shù)，則有： i. a a（mod m） ii. 若a b（mod m），則b a（mod m） . 若a b（mod m），b c（mod m）， 則a c（mod

8、 m）,假設(shè)a和b被m除，獲得整數(shù)商和余數(shù)，這個(gè)余數(shù)在0和m-1之間，即a = q1m +r1和b = q2m +r2 ，0r1m-1 ，0r2m-1 。不難看出，a b（mod m），當(dāng)且僅當(dāng)r1 = r2 。我們使用符號(hào)a（mod m）來(lái)表示a 被m除時(shí)的余數(shù)，即上面的r1 ，這樣a b（mod m），當(dāng)且僅當(dāng)a（mod m ）b（mod m）。如果我們用a（mod m）來(lái)代替a ，我們說(shuō)a是被模m約簡(jiǎn)的。 現(xiàn)在我們能夠定義模m的算術(shù)：Zm是一個(gè)集合0，1，。，m-1，它有兩種運(yùn)算+和 。在Zm中的加法和乘法，除了將結(jié)果被模m約減外，恰好象實(shí)數(shù)加法和乘法。 例 25 在Z2種作加法 0+0

9、0（mod 2 ）,0+11(mod 2 ) ,1+01(mod 2 ) , 1+10(mod 2 ) 一般地，在Z2種的加法稱為模2加，有時(shí)也稱為比特異或，用記號(hào)表示。 0 0 =0 ， 0 1 = 1 ， 1 0 = 1 ， 1 1 = 0,例25 在Z16作乘法1113 1113=143 =816+15 所以， 1113(mod16)=15 定義2.1.4 Euler函數(shù)是定義在整數(shù)上的函數(shù)，它在正整數(shù)m的值等于1，2， ，m-1中與m互素的數(shù)的個(gè)數(shù)，記作（m）。 例26 m = 6 , 1,2,3,4,5中與6互素的數(shù)為1，5，共有兩個(gè)，所以， （m）= （6）=2 定理2.1.5 設(shè)

10、正整數(shù)的標(biāo)準(zhǔn)分解形式為 m = ， 則 （m）= m（1-1/p1）（1-1/p2）（1-1/pn） 例27 m=6 ，其標(biāo)準(zhǔn)分解形式為 6 = 23 所以， （6）= 6（1-1/2）（1-1/3）=2,定理2.1.6（Euler定理） 若a和m互素，則 a(m) 1(mod m) 設(shè)f(x)表示多項(xiàng)式：anxn + an-1xn-1 + +a0 ,其中an 0 ，aiN(i=1,2,n)。設(shè)n是一個(gè)正整數(shù)，則 f(x)= 0(mod m) 稱作模m的同余式，n稱作同余式的次數(shù)，n = 1稱為一次同余式， n = 2稱為二次同余式。 若a是使f(a)0(mod m)成立的一個(gè)整數(shù)，則x a

11、(mod m) 叫做同余式的一個(gè)解。,定理2.1.7 （中國(guó)剩余定理） 設(shè)m1，m2，mk，是k個(gè)兩兩互素的整數(shù)，m= m1m1mk，Mi =m/mi ，i=1,2,k 。則同余方程組 x b1(mod m1) , x b2(mod m2) , x bk(mod mk) 有解 x =(M1M1b1+ M2M2b2+MkMkbk)(mod m) 其中 MiMi 1(mod mi) ,i=1,2,k 由此定理可以看出，Mi可以利用前面介紹的Euclid算法求出。,4）二次剩余 設(shè)gcd(a,m)=1，若同余式x2a(mod m)有解，則a稱作模m的二次剩余，否則稱作模m的非二次剩余。 例29 考慮

12、下列同余式 x21(mod 5)，x22(mod 5)，x23(mod 5)，x24(mod 5) 不難發(fā)現(xiàn)：x=1, x=4滿足x21(mod 5) x=2, x=3滿足x24(mod 5) 不存在整數(shù)x滿足 x22(mod 5)，x23(mod 5) 所以1，4是模5的二次剩余，而2，3是模5的非二次剩余。 定理2.1.8 若gcd(a,p)=1，則a是模p的二次剩余的充要條件為 ap-1/21(mod p) a是模p的非二次剩余的充要條件為 ap-1/2-1(mod p),定理2.1.9 兩個(gè)模p的二次剩余的乘積或兩個(gè)模p的非二次剩余的乘積，還是模p的二次剩余，一個(gè)模p的二次剩余與另一個(gè)

13、模p的非二次剩余的乘積是非二次剩余。 定義2.1.5 Legendre符號(hào)（）是一個(gè)對(duì)于給定素?cái)?shù)p定義在一切整數(shù)a上的函數(shù)，它的值規(guī)定如下：,例210 ， ，,定理2.1.10 legendre符號(hào)的性質(zhì) a ) b ) 如果a b(mod p )，則 c) d) e)設(shè)p，q均為奇素?cái)?shù)，pq，則,定義2.1.6 設(shè)m = ei0是一個(gè)奇正整數(shù)，u是與m互素的整數(shù)，則Jacobi符號(hào)定義為 （u/m）= 其中（）是Legendre符號(hào)。 定理2.1.11 Jacobi符號(hào)的性質(zhì) 1）（u/m）=(u-m)/m) 2) (uv/m) = (u/m)(v/m) 3) (u/mn) =(u/n)(u

14、/m) 4) (-1/m) = 1 當(dāng)且僅當(dāng)m = 1(mod 4) 5) (2/m) = 1 當(dāng)且僅當(dāng)m = +1，-1(mod 8) 6) 設(shè)m，n都是奇數(shù)，且gcd(m,n) = 1則=（-1）(m-1)(n-1)/4,22信息論基礎(chǔ) Shannon信息論是密碼學(xué)的理論基礎(chǔ)，本節(jié)介紹Shannon信息論的基本概念，與密碼學(xué)有關(guān)的概念將在后面介紹。 1熵的概念 熵是信息的測(cè)度或不確定性，它是作為概率分布的一個(gè)函數(shù)來(lái)計(jì)算的。假設(shè)有一個(gè)隨機(jī)變量x，它根據(jù)概率分布p(x)在一個(gè)有限集合上取值。根據(jù)分布p(x)發(fā)生的事件來(lái)獲得的信息是什么？等價(jià)地，如果一個(gè)事件還沒(méi)有發(fā)生，有關(guān)這個(gè)結(jié)果的不確定性是多

15、少？這個(gè)量稱為x的熵并用H(x)表示。 定義2.2.1 離散隨機(jī)變量x的熵H(x)定義為 H(x) = -P(x) Log2P(x) 其中，P(x)表示隨機(jī)變量x的概率分布。,例211 設(shè)離散隨機(jī)變量x取0，1兩個(gè)值，其中P(x=0)=P(x=1)=1/2，則 H(x) = -1 P(x=0)Log2P(x=0) - P(x=1)Log2P(x=1) = -1/2(-1) 1/2(-1) = 1 下面我們來(lái)定義聯(lián)合熵和條件熵。 定義2.2.2 兩個(gè)離散隨機(jī)變量（x,y）的聯(lián)合熵定義為 H(xy) = -1P(xy) Log2P(xy) 其中，P(xy)表示離散隨機(jī)變量(x，y)的聯(lián)合概率分布。

16、 類似地，可以定義n個(gè)離散隨機(jī)變量(x1，x2，xn，)的聯(lián)合熵。,定義2.2.3 兩個(gè)離散隨機(jī)變量(x，y)的條件熵定義為 H(xy) = - P(xy)Log2P(xy) 其中，P(xy)表示離散隨機(jī)變量（x，y）的聯(lián)合概率分布，P(xy)表示兩離散隨機(jī)變量的條件分布。 利用聯(lián)合熵與條件熵的定義，容易證明 定理2.2.1 H(xy) = H(x) + H(yx) 2互信息 互信息是一個(gè)事件含有另一個(gè)事件的信息的度量；或者是已知另外一個(gè)事件（稱作B）的情況下，事件（稱作A）不確定性的減少。,定義2.2.4 兩個(gè)離散隨機(jī)變量x和y，它具有概率分布P(x)和P(y)和聯(lián)合概率分布密度P(xy)，

17、則互信息定義為 I (x ；y) = 從互信息的定義可以看出，如果隨機(jī)變量x和y統(tǒng)計(jì)獨(dú)立，即y中不含x的任何信息，則I(x ；y) = 0 。 互信息具有對(duì)稱性，這就是 定理2.2.2 I (x ；y) = H(x) - H(yx) = H(y) - H(xy) = I(y ；x),23 3 計(jì)算復(fù)雜度簡(jiǎn)介 計(jì)算復(fù)雜度理論是計(jì)算機(jī)科學(xué)理論的一個(gè)分支，它提供了一種分析不同密碼技術(shù)和算法保密強(qiáng)度的方法。它對(duì)密碼算法和技術(shù)進(jìn)行比較，然后確定它們的安全性。現(xiàn)代密碼學(xué)的許多理論和技術(shù)是建立在某些計(jì)算問(wèn)題的復(fù)雜性基礎(chǔ)之上的。,1算法復(fù)雜度 一個(gè)算法的計(jì)算復(fù)雜度用符號(hào)“O”來(lái)表示，計(jì)算復(fù)雜度的數(shù)量級(jí)是這種類

18、型的函數(shù)，即當(dāng)n變大時(shí)，增長(zhǎng)最快的函數(shù)（n是輸入尺寸），所有常數(shù)和較低階形式的函數(shù)忽略不計(jì)。例如，一個(gè)所給的算法復(fù)雜度是5n2+8n+10 ，那么，其計(jì)算復(fù)雜性表示為O (n2)。 通常，算法按其事件和空間的復(fù)雜性進(jìn)行分類，如果一個(gè)算法的復(fù)雜性是不依賴于n ：O (1) ，那么，它是“常數(shù)級(jí)的”。如果它的復(fù)雜性是隨n線性增長(zhǎng)的，那么它是“線性的”。O隨n增長(zhǎng)的其他一些算法也稱為“二次方的”，“三次方的”，等等。所有這些算法都是“多項(xiàng)式的”，他們的復(fù)雜性是O (nt )，這里t是一個(gè)常數(shù)。有一個(gè)多項(xiàng)式的時(shí)間復(fù)雜性的算法簇稱之為多項(xiàng)式時(shí)間算法。 復(fù)雜性是O (tf(n) 的算法，被稱為是“指數(shù)的”

19、，這里t是一個(gè)常數(shù)，f (n)是n的多項(xiàng)式函數(shù)。,2問(wèn)題的分類 復(fù)雜性理論按照解決問(wèn)題的算法對(duì)問(wèn)題進(jìn)行分類。能夠用多項(xiàng)式時(shí)間算法解決的問(wèn)題稱之為易解決的；不能在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題稱之為難處理的，難處理的問(wèn)題有時(shí)也稱為難解決的。 定義2.3.1 P類問(wèn)題：在多項(xiàng)式時(shí)間內(nèi)可以解決的問(wèn)題。 NP類問(wèn)題：多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問(wèn)題。 由于在多項(xiàng)式時(shí)間內(nèi)可以解決的問(wèn)題，在多項(xiàng)時(shí)間內(nèi)也完全可以驗(yàn)證其正確性，因此一般有P NP，但現(xiàn)在還不知道是否有“P = NP”成立。 在NP問(wèn)題中有些特殊的問(wèn)題能夠被證明與此類問(wèn)題中的任何問(wèn)題一樣困難，這類問(wèn)題稱之為NP-完全類問(wèn)題。有人已經(jīng)編輯了一份NP-完全類問(wèn)題

20、的目錄，下面將列出幾個(gè)例子。,3幾個(gè)例子 1）整數(shù)分解問(wèn)題 前面介紹了算術(shù)基本定理，根據(jù)這個(gè)定理，任何一個(gè)正整數(shù)都可以分解成標(biāo)準(zhǔn)形式 m = pi 是常數(shù)，ei N 當(dāng)m較小時(shí)，這個(gè)問(wèn)題不太困難，例如 6=23 ， 100=2252 但當(dāng)m較大時(shí)，這個(gè)問(wèn)題就變得非常困難了，例如你能立即指出整數(shù)8616460789的標(biāo)準(zhǔn)分解形式嗎？特別是當(dāng)m達(dá)到幾百位時(shí)，根據(jù)現(xiàn)有的算法用最快的計(jì)算機(jī)也不行。但反過(guò)來(lái)，如果給出一個(gè)整數(shù)的標(biāo)準(zhǔn)分解時(shí)，則可以很快驗(yàn)證這個(gè)標(biāo)準(zhǔn)分解式是否是這個(gè)整數(shù)的標(biāo)準(zhǔn)分解式了。 例212 861646079的標(biāo)準(zhǔn)分解式為 861646079 = 89681 96079 我們能立即驗(yàn)證這個(gè)分解式的正確性。,2）背包問(wèn)題 背包問(wèn)題是這樣一個(gè)問(wèn)題：已知長(zhǎng)度為k的圓形背包及長(zhǎng)度分別為a1，a2，an的n個(gè)圓形物品。假定這些物品的半徑和背包的半徑相同，要求從n個(gè)物品中選出若干個(gè)正好裝滿這個(gè)背包