計算機網(wǎng)絡安全技術(shù)第2章

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

2、,稱為素數(shù)，如果除了1和其本身外，p沒有任何其他因數(shù)。不是素數(shù)的整數(shù)稱為合數(shù)。 例21 6 = 23 ，6是合數(shù)，26 ，2是6的因數(shù)，6是2的倍數(shù)。7 = 17，除了1和7之外，沒有其他因數(shù)，因此7是素數(shù)。 定理2.1.1 （帶余數(shù)除法）設a，b是兩個整數(shù)，其中b 0 。則存在兩個整數(shù)q，r使得 a = bq + r 0 r b 成立，其中q和r是唯一確定的。,設a，b是兩個整數(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 如果對兩個整數(shù)a , b有g(shù)cd (a ,b ) = 1，則稱a與b互素。 定理2.1.2 設a ，b N，則存在兩個整數(shù)u和v使得 ua + vb =gcd ( a ，b ) 定理2.1.3 （算術(shù)基本定理）任何一個正整數(shù)m都存在唯一的因數(shù)分解形式 m = 其中，eiN，pi是素數(shù)且p1p2p n。 這個分解形式也稱為m的標準分解形式。,例22 6 =23， 20=225， 100 =2252 有了算術(shù)基本定理后，就可以把任意整

4、數(shù)分解為標準形式，從而可以方便地求出兩個整數(shù)的最大公因數(shù)和最小公倍數(shù)。設a，b是兩個整整數(shù)，且有標準分解形式：,， ei ，fiN,則 gcd (a，b) = lcd (a，b) = 其中，min x ,y 表示x，y中最小者，max x ，y 表示x，y中最大者。,2Euclid算法 利用算術(shù)基本定理，原則上可以求得任何兩個整數(shù)的最大公因數(shù)，但當兩個整數(shù)比較大時求他們的標準分解式就非常困難，目前還沒有有效的算法，因此求他們的最大公因數(shù)也變得非常困難。Euclid算法從另一方面解決了求兩個整數(shù)的最大公因數(shù)的問題。 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 因為每進行一次帶余數(shù)的除法，余數(shù)至少減1，而b是有限的。所以，最多進行b次帶余數(shù)的除法，總可以得到一個余數(shù)是0的等式，即最后一個等式，而最后一個不為0的余數(shù)rn就是我們要求的最大公因數(shù)gcd( a，b )。,從上面的Euclid算法中可以看出，將r1 = a bq1代入第二個等式中，將r2 = b r1q2代入到第三個等式中， ，將rn-1 = rn-3 rn-2qn-1代入倒數(shù)第二個等式中，就可得到rn關(guān)于a

6、, b的一個表示式，其中 a , b的系數(shù)分別就是定理2.1.2中的u , v。故最后一個不為零的余數(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,進行回代 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 假設a 和b是兩個整數(shù)，m是一個正整數(shù)，如果m b a ，則稱a 和b對模m同余。記作 a b (mod m )。 例24 3和1對模2同余，4和1對模3同余，即3 1（mod 2），41（mod 3） 定理2.1.4 同余的性質(zhì) 設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）,假設a和b被m除，獲得整數(shù)商和余數(shù)，這個余數(shù)在0和m-1之間，即a = q1m +r1和b = q2m +r2 ，0r1m-1 ，0r2m-1 。不難看出，a b（mod m），當且僅當r1 = r2 。我們使用符號a（mod m）來表示a 被m除時的余數(shù)，即上面的r1 ，這樣a b（mod m），當且僅當a（mod m ）b（mod m）。如果我們用a（mod m）來代替a ，我們說a是被模m約簡的。 現(xiàn)在我們能夠定義模m的算術(shù)：Zm是一個集合0，1，。，m-1，它有兩種運算+和 。在Zm中的加法和乘法，除了將結(jié)果被模m約減外，恰好象實數(shù)加法和乘法。 例 25 在Z2種作加法 0+0

9、0（mod 2 ）,0+11(mod 2 ) ,1+01(mod 2 ) , 1+10(mod 2 ) 一般地，在Z2種的加法稱為模2加，有時也稱為比特異或，用記號表示。 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ù)的個數(shù)，記作（m）。 例26 m = 6 , 1,2,3,4,5中與6互素的數(shù)為1，5，共有兩個，所以， （m）= （6）=2 定理2.1.5 設

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

11、(mod m) 叫做同余式的一個解。,定理2.1.7 （中國剩余定理） 設m1，m2，mk，是k個兩兩互素的整數(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）二次剩余 設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 兩個模p的二次剩余的乘積或兩個模p的非二次剩余的乘積，還是模p的二次剩余，一個模p的二次剩余與另一個

13、模p的非二次剩余的乘積是非二次剩余。 定義2.1.5 Legendre符號（）是一個對于給定素數(shù)p定義在一切整數(shù)a上的函數(shù)，它的值規(guī)定如下：,例210 ， ，,定理2.1.10 legendre符號的性質(zhì) a ) b ) 如果a b(mod p )，則 c) d) e)設p，q均為奇素數(shù)，pq，則,定義2.1.6 設m = ei0是一個奇正整數(shù)，u是與m互素的整數(shù)，則Jacobi符號定義為 （u/m）= 其中（）是Legendre符號。 定理2.1.11 Jacobi符號的性質(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 當且僅當m = 1(mod 4) 5) (2/m) = 1 當且僅當m = +1，-1(mod 8) 6) 設m，n都是奇數(shù)，且gcd(m,n) = 1則=（-1）(m-1)(n-1)/4,22信息論基礎 Shannon信息論是密碼學的理論基礎，本節(jié)介紹Shannon信息論的基本概念，與密碼學有關(guān)的概念將在后面介紹。 1熵的概念 熵是信息的測度或不確定性，它是作為概率分布的一個函數(shù)來計算的。假設有一個隨機變量x，它根據(jù)概率分布p(x)在一個有限集合上取值。根據(jù)分布p(x)發(fā)生的事件來獲得的信息是什么？等價地，如果一個事件還沒有發(fā)生，有關(guān)這個結(jié)果的不確定性是多

15、少？這個量稱為x的熵并用H(x)表示。 定義2.2.1 離散隨機變量x的熵H(x)定義為 H(x) = -P(x) Log2P(x) 其中，P(x)表示隨機變量x的概率分布。,例211 設離散隨機變量x取0，1兩個值，其中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 下面我們來定義聯(lián)合熵和條件熵。 定義2.2.2 兩個離散隨機變量（x,y）的聯(lián)合熵定義為 H(xy) = -1P(xy) Log2P(xy) 其中，P(xy)表示離散隨機變量(x，y)的聯(lián)合概率分布。

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

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

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

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

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