安全與保密通用課件

1、2.1 信息論2.1.1 熵與疑義度2.1.2 自然語言率2.1.3 密碼系統(tǒng)的安全性2.1.4 確定性距離2.1.5 混亂與擴散2.1.1 熵與疑義度假設(shè)所有的消息都有相等的可能性。一條消息中的信息量：要將消息中所有可能的含意編碼所需的最少的比特位數(shù)。熵：用來形式化地衡量一條消息M中的信息量，記為H(M)。當(dāng)用比特來衡量時，為log2n，其中n為消息的狀態(tài)個數(shù)，假設(shè)所有狀態(tài)有相等的出現(xiàn)概率。例：數(shù)據(jù)庫中表示“星期”的字段寬度不超過3bit的信息 000 星期一 001 星期二 010 星期三 011 星期四 100 星期五 101 星期六 110 星期日 111 不 用表示星期的信息的熵 H

2、(M)= log2n= log27=2.807表示性別的信息的熵 H(M)= log2n= log22=1表示季節(jié)的信息的熵 H(M)= log2n= log24=2表示月份的信息的熵 H(M)= log2n= log212=3.585疑義度：消息的熵同時也可衡量其不確定性（疑義度），即將消息隱藏在密文中時，要破譯它所需的明文比特數(shù)。例：性別的疑義度為12.1.2 自然語言率自然語言率：對于給定的一種語言，其自然語言率為r = H(M)/ N其中N為消息長度。英語的自然語言率：1.0比特/字母1.5比特/字母絕對語言率：每個字符編碼的最大比特數(shù)，這里假設(shè)每個字符序列出現(xiàn)的機會相等。若語言中有L

3、個字母，則絕對語言率為：R = log2L 為單個字母的最大熵。英語的絕對語言率：log226 4.7比特/字母冗余度：語言的冗余度記為D，定義為：D = R - r其中，R為絕對語言率，r為自然語言率。英語：r = 1.3比特/字母，則 D = 4.7 -1.3=3.4比特/字母。2.1.3 密碼系統(tǒng)的安全性絕對安全的密碼系統(tǒng)：一次一密（密鑰與消息本身一樣長，密鑰隨機產(chǎn)生且不重復(fù)使用）密碼系統(tǒng)的熵：衡量密鑰空間K的大小的一個標(biāo)準(zhǔn)，通常是密鑰數(shù)以2為底的對數(shù)。H（K） = log2k2.1.4 確定性距離對于長度為n的消息，能夠?qū)⒁欢蚊芪南⒔饷艹膳c原始明文同種語言的可懂文本的密鑰個數(shù)為：2H

4、(K)- nD - 1確定性距離：能夠唯一地確定密鑰的最短的密文長度的近似值。對稱密碼系統(tǒng)的確定性距離：定義為密碼系統(tǒng)的熵除以語言的冗余度。U = H（K）/ D理想安全的密碼系統(tǒng)：確定性距離無限大的密碼系統(tǒng)。2.1.5 混亂與擴散混亂：在加密變換中，讓密鑰與密文的關(guān)系盡可能復(fù)雜的做法。實現(xiàn)混亂的方法：代替（愷撒密碼）擴散：在加密過程中，盡可能將明文的統(tǒng)計特性在密文中消除。實現(xiàn)擴散的方法：換位（鑰控序列加密法）2.2 復(fù)雜性理論2.2.1 算法復(fù)雜性2.2.2 問題復(fù)雜性2.2.1 算法復(fù)雜性算法的復(fù)雜性通常由兩個變量來衡量：T（時間復(fù)雜性）和S（空間復(fù)雜性，或存儲需求）。T和S都用n的函數(shù)來

5、表示，其中n為輸入的大小。數(shù)量級法：當(dāng)n增大時，復(fù)雜性函數(shù)中增加得最快的一項。時間復(fù)雜性為4n5+7n+12復(fù)雜性的階為n5 , 表示為O(n5)多項式時間算法：O(1)：常數(shù)的O(n)：線性的O(n2)：平方的O(nm)：m為常數(shù)指數(shù)時間算法：O(tf(n)，其中t為大于1的常數(shù)，f(n)為n的多項式函數(shù)。超多項式時間算法：O(cf(n)，其中c為大于1的常數(shù)，f(n)大于常數(shù)，小于線性。2.2.2 問題復(fù)雜性圖靈機：一個有限狀態(tài)機，具有無限的讀寫存儲磁帶，是一個理想化的計算模型。問題：易解的問題：可以在多項式時間內(nèi)求解難解的問題：只能在指數(shù)時間內(nèi)求解不確定的問題：找不出解決的算法，不考慮算

6、法的時間復(fù)雜性問題復(fù)雜性的劃分：P問題：可以在多項式時間內(nèi)求解的問題。NP問題：只能在一個非確定性的圖靈機（能夠進行猜測的一種圖靈機）上在多項式時間內(nèi)求解的問題。NP完全問題：一些特定的NP問題，與其他NP問題同等困難。P空間問題：可以在多項式空間內(nèi)求解，但不能在多項式時間內(nèi)求解的問題。P空間完全問題：與其他P空間問題同等困難。指數(shù)時間問題：在指數(shù)時間內(nèi)求解。PNPNP完全的P空間P空間完全的指數(shù)時間的2.3 初等數(shù)論2.3.1 模運算2.3.2 素數(shù)2.3.3 最大公因數(shù)2.3.4 乘法逆元素2.3.5 Fermat小定理及歐拉函數(shù)2.3.6 中國剩余定理2.3.7 二次剩余2.3.8 Le

7、gendre（勒讓得）符號2.3.9 Jacobi（雅各比）符號2.3.10 生成元2.3.11 有限域中的計算2.3.1 模運算同余：如果a = b + kn，k為整數(shù)，則a b（mod n）含義：b是a除以n的余數(shù)； b為a模n的余數(shù)； a與b模n同余。a mod n ：a模n操作，表示a除以n的余數(shù)，為 0到n 1之間的整數(shù)。例如：(78) mod 12 = 15 mod 12 = 3 15 3(mod)12 模運算（+、 ）滿足交換律、結(jié)合律和分配律。按模計算原理：對中間結(jié)果作模運算與做完了全部運算后再做模運算結(jié)果相同。按模指數(shù)運算：am mod n將指數(shù)運算作為一系列乘法運算，每次做

8、一次模運算。例：a8 mod n = (a2 mod n)2 mod n)2 mod n當(dāng)m不是2的乘方時，將m表示成2的乘方和的形式。例如：25=(11001)2，即25=24+23+20 a25 mod n = (a16 a8 a) mod n = (a2)2)2)2 (a2)2)2 a) mod n = (a2 a)2)2)2 a) mod n適當(dāng)存儲中間結(jié)果，則只需6次乘法：(a2mod n) a)mod n)2mod n)2mod n)2mod n) a)mod n例：315 mod 11=57 mod 13= 213 mod 9=711 mod 12=415 mod 7 =315

9、mod 11=157 mod 13= 8213 mod 9=2711 mod 12= 7415 mod 7 =12.3.2 素數(shù)素數(shù)（質(zhì)數(shù)）：大于1的整數(shù)，只能被1和本身整除。有無窮多個素數(shù)。如：2，73，2521，2365347734339，2756839-12.3.3 最大公因數(shù)公因數(shù)：兩個整數(shù)a，b的公因數(shù)定義為能同時整除a，b的所有整數(shù)。最大公因數(shù)：a與b的公因數(shù)中能被所有a，b的公因數(shù)整除的正整數(shù)，記為gcd(a，b)。 例：gcd(48,36)=12互素（互質(zhì)）：兩個整數(shù)稱為互素的，如果它們除了1以外沒有其他的公因數(shù)，即 gcd(a,b)=1。最大公因數(shù)的求法：輾轉(zhuǎn)相除法例如：求g

10、cd(15,36) gcd(54,30) 36=15 2+6 54=30+24 15=6 2+3 30=24+6 6=3 2+0 24=4 6+0因此，gcd(15,36)=3 gcd(54,30)=6原理：若a b (mod c)，則 gcd(a,c) = gcd(b,c)這里，gcd(36,15) = gcd(6,15) = gcd(6,3) = 3求最大公因數(shù)的Euclid算法 p16 a b 15 36 36 15 15 6 6 3 3 0 2.3.4 乘法逆元素求x，滿足 (a x) mod n = 1, 即 x a-1(mod n)當(dāng)a與n互素時, 方程 x a-1(mod n)

11、有唯一解；即：ax-kn=1當(dāng)a與n不互素時, 此方程無解。一個數(shù)關(guān)于某一個模的乘法逆元不一定存在。2關(guān)于模14的乘法逆元不存在，因為2與14不互素a與n互素，a關(guān)于模n的乘法逆元才存在求乘法逆元：擴展的Euclid算法例：求5關(guān)于模14的乘法逆元輾轉(zhuǎn)相除：14 = 5 2 + 4 5 = 4 + 1逆推：1 = 5 - 4 = 5 - （14 - 5 2）= 5 3 - 14 因此，5關(guān)于模14的乘法逆元為3。例：求4關(guān)于模7的乘法逆元 7=4 1+3 4=3+1 1=4-3 =4-(7-4) =4 2-7 所以4關(guān)于模7的乘法逆元為2練習(xí)練習(xí)：求17關(guān)于模26的乘法逆元。答案求17關(guān)于模2

12、6的乘法逆元。答案：2326 = 17 + 9 1 = 9 - 817 = 9 + 8 = 9 - (17 - 9)9 = 8 + 1 = 9 2 - 17 = (26 - 17) 2 - 17 = 26 2 - 17 3 = 17 (-3) + 26 2+17 26- 17 26 = 17 23 - 26 152.3.5 Fermat小定理及歐拉函數(shù)Fermat小定理：如果m為素數(shù)，a不能被m整除，則 am-1 1 (mod m)例：210 1 mod 11 610 1 mod 11 710 1 mod 11 810 1 mod 11 36 1 mod 7 模n的簡化剩余集：模n的完全剩余集

13、的一個子集，其中每個元素與n互素。如果n為素數(shù)，則模n的簡化剩余集為從1 n-1。例：模12的簡化剩余集為1，5，7，11 模7的簡化剩余集為1，2，3，4，5，6 歐拉函數(shù)：記為(n)，為模n的簡化剩余集中元素的個數(shù)。如果n是素數(shù)，則(n) = n-1若n=pq，其中p、q為素數(shù)，則(n)=（p-1)(q-1)例：n=15 , n=3 5 , p=3, q=5 (n)=2 4=8 15的簡化剩余集為1，2，4，7，8，11，13，14歐拉擴展的Fermat小定理：如果gcd(a,n) = 1，則 a(n) mod n = 1。a的乘法逆元：x=a (n)-1 mod n例：求5關(guān)于模7的乘法

14、逆元解：方法一：7=5+2 5=2 2+1 1=5-2 2 =5-2 (7-5) =3 5-2 7 5關(guān)于模7的乘法逆元為3方法二： n=7 n為素數(shù)，gcd(5,7)=1, (n)=n-1=7-1=6x= a (n)-1 mod n =5 6-1 mod 7=55mod 7=3例：4關(guān)于模7的乘法逆元解： (7)=7-1=6 n為素數(shù) gcd(4,7)=1 x= a (n)-1 mod n =46-1 mod 7=45mod 7=22.3.6 中國剩余定理定理：如果n的素數(shù)因子分解式為p1p2 pt，則一組方程 (x mod pi）= ai，其中i = 1,2,t，有唯一解x，其中x小于n（

15、其中某些pi可能相等）。例：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？x mod 3 = 2x mod 5 = 3x mod 7 = 2解法：令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7，n=p1 p2 p3=3 5 7=105，M1=n/p1=35, M2=n/p2=21, M3=n/p3=15求解 35 x1 mod 3=1, 得x1=2求解 21 x2 mod 5=1, 得x2=1求解 15 x3 mod 7=1, 得x3=1則 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (35 2 2+21 1 3+15

16、 1 2) mod 105 = 233 mod 105 = 23練習(xí)：今有數(shù)不知其數(shù)，兩兩數(shù)之剩1，三三數(shù)之剩2，五五數(shù)之剩2，求該數(shù)。解法：令a1=1，a2=2，a3=2，p1=2，p2=3，p3=5，n=p1 p2 p3=2 3 5=30M1=n/p1=15, M2=n/p2=10, M3=n/p3=6求解 15 x1 mod 2=1, 得x1=1求解 10 x2 mod 3=1, 得x2=1求解 6 x3 mod 5=1, 得x3=1則 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (15 1 1+10 1 2+6 1 2) mod 30 = 47

17、mod 30 = 17課后練習(xí)：今有數(shù)不知其數(shù)，五五數(shù)之剩2，七七數(shù)之剩5，十一十一數(shù)之剩3，求該數(shù)。2.3.7 二次剩余定義：設(shè)p為素數(shù)，a0且ap，如果存在某個x，滿足x2 a (mod p)，則稱a為模p的二次剩余。否則稱a為模p的非二次剩余。例1：p=5, a=4 x=2 22 4 （mod 5）例2：p=11, a=5 x=4 42 5 （mod 11）2.3.8 Legendre（勒讓得）符號記為L(a,p)，其中a為任意整數(shù)，p為大于2的素數(shù)。定義：L(a,p) = 0，如果a能被p整除；L(a,p) = 1，如果a是模p的二次剩余；L(a,p) = -1，如果a是模p的非二次剩

18、余；計算：L(a,p) = a(p-1)/2 mod p公式驗證：L(a,p) = a(p-1)/2 mod p = (a(p-1) mod p)1/2 = 1 Fermat小定理： am-1 1 (mod m) = 1 L(a,p) = -1=p-1Legendre符號的用途用Legendre符號來驗證a是否是模p的二次剩余舉例:驗證：a=5是否是p=11的二次剩余？L(a,p) = a(p-1)/2 mod p=5(11-1)/2 mod 11=55 mod 11=1 即 L(5,11) =1 所以5是模11的二次剩余 (72 5 mod 11) 再如： L(6,11)= 6(11-1)/

19、2 mod 11=65 mod 11=10=p-1 所以6不是模11的二次剩余22 4 mod 5 L(4,5)=4(5-1)/2 mod 5 =1 42 5 mod 11 L(5,11)=5(11-1)/2 mod 11 =12.3.9 Jacobi（雅各比）符號記為J(a,n)，是Legendre符號的擴展，其中a為任意整數(shù)，而n為任意奇數(shù)。定義：J(a,n)只對n為奇數(shù)時有意義J(0,n)=0如果n為素數(shù)，且a能被n整除，則J(a,n)=0如果n為素數(shù)，且a是模n的二次剩余，則J(a,n) = 1(即x2 a mod n)如果n為素數(shù)，且a是模n的非二次剩余，則J(a,n) = -1如果

20、n是合數(shù)，則J(a,n)=J(a,p1)J(a,p2)J(a,pm)，其中將n因數(shù)分解為p1p2pmBlum整數(shù)：若p和q為兩個素數(shù)，且都與3模4同余，則n = pq稱為Blum整數(shù)。若n為Blum整數(shù)，則每個模n的二次剩余恰好有4個平方根，其中一個也是一個二次剩余，稱為原平方根。例如，139的模437的原平方根為24，另三個平方根為185，252和413。n=437=19*23 p=19 q=23242 139 （mod 437） 1852 139 （mod 437）2522 139 （mod 437） 4132 139 （mod 437）2.3.10 生成元定義：如果p為素數(shù)，gp，如果對

21、每個b從1到p-1，存在a，使ga b (mod p)，則g為模p的生成元。例：p=11，2為模11的生成元g=2 p=11 b=110 都可表示成：2a mod p1 210 mod 11 6 29 mod 11 2 21 mod 11 7 27 mod 11 3 28 mod 11 8 23 mod 11 4 22 mod 11 9 26 mod 11 5 24 mod 11 10 25 mod 11生成元的測試q=p-1 q=q1*q2*qn對每個qi, 若 g (p-1)/qi mod p=1，則g不是生成元。例：p=11 q=10=2*5 g=2 2 (11-1)/2 mod 11=

22、 10 2 (11-1)/5 mod 11= 4 所以 2是模11的生成元 g=3 3 (11-1)/2 mod 11= 1 3 (11-1)/5 mod 11= 9 所以 3不是模11的生成元練習(xí)：求模11的生成元一共有幾個？2.3.11 有限域中的計算有限域：元素個數(shù)有限的域。在有限域中，非0數(shù)的加、減、乘、除都有定義。加法單位元是0，乘法單位元是1，每個非0元素都有一個唯一的乘法逆元。有限域中運算滿足交換律、結(jié)合律和分配律。有限域中元素個數(shù)為素數(shù)或素數(shù)的乘方：設(shè)p為素數(shù)，則有限域可記為GF(p)或GF(pn)。不可約多項式：一個多項式如果除了1和本身外，不能分解成其他多項式的乘積形式，則

23、成為不可約多項式。 例：x2+1 而x3+ 2x2+x = x(x+1)(x+1) 不是不可約多項式本原多項式：一個有限域內(nèi)的生成元多項式，其系數(shù)是互素的。在GF(qn)中，所有運算都是模p(x)的運算，其中p(x)是n階不可約多項式。P(x)=xn+x+12.4 因數(shù)分解對一個數(shù)進行因數(shù)分解，是指找出這個數(shù)的素數(shù)因子。6=2 38=2 2 29=3 310=2 560=2 2 3 5252601=41 61 1012.5 素數(shù)的產(chǎn)生2.5.1 Solovay-Strassen方法2.5.2 Lehmann法2.5.3 強素數(shù)2.5.1 Solovay-Strassen方法用Jacobi符號來測試p是否為素數(shù)：（1）選擇一個隨機數(shù)a，ap；（2）如果gcd(a,p)1，則p是合數(shù)，停止檢測；（3）計算i=a(p-1)/2 mod p；（4）計算Jacobi符號J(a,p)；（5）如果i J(a,p)，則p不是素數(shù)；（6）如果i= J(a,p)，則p不是素數(shù)的概率小于50%。對t個不同的隨機數(shù)a，重復(fù)進行這個測試。能通過所有t個測試的奇數(shù)是合數(shù)的概率小于1/2t。2.5.2 Lehmann法測試p是否為素數(shù)：