【正文】 息安全原理與應(yīng)用 》， 169。 即可以有 11個元素的有限域，也可以有 256個元素的有限域，但不可能有 12個元素的有限域。 √ ●有限域 GF(2n)上的乘法群。版權(quán)所有 ,引用請注明出處 離散對數(shù)難題 ? 有限域 GF(p)上的離散對數(shù)問題 給定一個素數(shù) p和 GF(p)上的一個本原根 g，對于 任意整數(shù) b∈ Zp*={1， 2， ...， p1}，可以找到唯一 的整數(shù) i， i∈ Zp*={1， 2， ...， p1}， 滿足： b=gi mod p， 稱指數(shù) i為以 g為底模 p下的 b 的離散對數(shù)，記為： i=loggb。表 42給出了整數(shù)模 13的冪，表中帶 陰影的部分表明了該行整數(shù)在計算模冪時重復(fù)出 現(xiàn)的冪結(jié)果。因此，DiffieHellman密鑰交換算法只能用于建立共享密鑰，不能用于加 /解密和數(shù)字簽名。版權(quán)所有 ,引用請注明出處 DiffieHellman密鑰交換 ? 舉例 A和 B需用 DH密鑰交換算法進行密鑰交換，二者協(xié)商后決定采用大素數(shù) p=353及其一個本原根 a=3。 (2)每次密鑰交換后不必再保留各自秘密的信息 ,減少了保密的負擔(dān)。類似地，當(dāng) B加密一個消息發(fā)送給 A時， O能解密而 A不能。版權(quán)所有 ,引用請注明出處 46 內(nèi)容提要 ? 公開密鑰密碼經(jīng)典算法 – DiffieHellman密鑰交換算法 – 背包算法 – RSA算法 – ElGamal算法 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ? 背包問題的數(shù)學(xué)描述： 給定 n個不同的正整數(shù)的集合 A={a1, a2, …,a n}及正整數(shù) S，求一個由 0、 1組成的向量 X=(x1,x2, …,x n)，其中 xi∈ {0,1},使得： x1a1+x2a2+……+x nan=S成立。 ? 有兩類背包，一類可以在線性時間內(nèi)求解 ——易解的背包 ；另一類則不能 ——難解的背包 。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ◆ m與 w是保密的。 w1必須保密 。 （ 2）進行下列計算： a1’ =2 31 mod 105=62 a2’ =3 31 mod 105=93 a3’ =6 31 mod 105=81 a4’ =13 31 mod 105=88 a5’ =27 31 mod 105=102 （ 3）這樣就得到一個普通背包 A’ =(a1’ ,a2’ , a3’ ,a4’ , a5’ )=(62,93,81,88,102)， 將其作為公鑰 。 解密時，消息的合法接收者知道私鑰 ——超 遞增背包 A=(2,3,6,13,27)與 w和模數(shù) m的值。 如果擁有私鑰，就可以將問題轉(zhuǎn)換為容易求解的超遞增背包問題。版權(quán)所有 ,引用請注明出處 65 RSA算法 ? 繼背包算法之后，出現(xiàn)了第一個成熟的公鑰密碼算法 ——RSA。 RSA是應(yīng)用最廣泛的公鑰密碼算法 。 (2)計算 p和 q的乘積 n=pq。版權(quán)所有 ,引用請注明出處 RSA算法描述 ? 對于 RSA的加密和解密都是通過“ 乘方取模 ”完成的。 ③ 設(shè)第 i個密文分組對應(yīng)的數(shù)字為 ci，對 ci作解密運算。 (4)選取公鑰 e=1223，使 gcd(e,φ(n))=1。版權(quán)所有 ,引用請注明出處 76 RSA算法 ? RSA概述 ? RSA算法描述 ? RSA實現(xiàn)中的問題 ? RSA安全性分析 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ? 舉例： 計算 117 mod 13。版權(quán)所有 ,引用請注明出處 ② 如何提高加 /解密運算中指數(shù)運算的有效性 4)計算 520 mod 35有： 51 mod 35=[(50)2 51]mod 35=5 mod 35=5 52 mod 35=[(51)2]mod 35=52 moc 35=25 55 mod 35=[(52)2 51]mod 35=[(25)2 5]mod 35 =3125 mod 35=10 510 mod 35=[(55)2]mod 35=102 mod 35=30 520 mod 35=[(510)2]mod 35=302 mod 35=25 故： 520 mod 35=25 盡管“反復(fù)平方乘”算法中的步驟很多，但每一步都 很簡單，且在計算過程中不需要計算大小超過模數(shù) 立方的數(shù) 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ? 其安全性依賴于有限域上計算離散對數(shù)的困難性之上。 2）秘密選擇一個隨機整數(shù) k，并滿足 1≤k≤p1 3） 計算一次性密鑰 K=yk mod p。版權(quán)所有 ,引用請注明出處 舉例 第一步：生成密鑰 ①用戶 A選取素數(shù) p=19以及 Z19*的一個本原根 g=2。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 1為了恢復(fù) A的私鑰 x，攻擊者將會計算離散對數(shù) x=loggy。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。其中： a=gk mod p b=KM mod p 密文長度是明文的兩倍，信息有擴張。版權(quán)所有 ,引用請注明出處 算法描述 用戶 A首先要產(chǎn)生一對密鑰： 1）選擇一個素數(shù) p，以及 p的一個本原根 g。版權(quán)所有 ,引用請注明出處 RSA的安全性 ? RSA的安全性基于加密函數(shù) Ek(x)=xe mod n是一個單向函數(shù)，對攻擊者來說求其逆運算不可行 ? 攻擊者能解密的“陷門”是分解 n=pq，進而求得 φ(n)=(p1)(q1)，從而能夠確定 e模 φ(n)的乘法逆元 d，即 d≡e1 mod φ(n)，導(dǎo)致攻擊成功。版權(quán)所有 ,引用請注明出處 ① 如何計算 ab mod n ∵ 117=112 114 111 又 ∵ 112 mod 13=121 mod 13=4 114 mod 13=(112)2 mod 13=42 mod 13=3 ∴ 117 mod 13=(112 114 111)mod 13=[(112 mod 13)(114 mod 13)(111 mod 13)]mod 13 =[4 3 11]mod 13 =132 mod 13 =2 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 78 ① 如何計算 ab mod n ? RSA的加密、解密過程都是求一個整數(shù)的整數(shù)次冪，再取模。 （ d是保密的） 這里，設(shè)明文 =“ RSA ALGORITHM”。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。也就是說，將明文中的每個字符（包括空格）用兩位十進制數(shù)字表示，例如： 空格 =00， A/a=01， B/b=02， ...Z/z=26，再將轉(zhuǎn)換后的明文數(shù)字串分成若干個十進制數(shù)的數(shù)據(jù)塊，每個數(shù)據(jù)塊的值不能超過 n1 ②將明文比特串分組，使得每個分組對應(yīng)的十進制數(shù)小于 n，即分組長度小于等于 log2n+1。 (4) 選擇 e。版權(quán)所有 ,引用請注明出處 67 RSA算法 ? RSA概述 ? RSA算法描述 ? RSA實現(xiàn)中的問題 ? RSA安全性分析 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ? RSA密碼特點 它是一種分組密碼算法。超遞增背包中的每項應(yīng)該有 100到 200位長?？梢郧蟮?w1=61。版權(quán)所有 ,引用請注明出處 舉例 1 (4)假設(shè)要加密一個二進制消息 011001101010111，首先將其分成長度與背包序列等長的塊 X1=01100， X2=11010， X3=10111。 求解超遞增背包問題，將密文變?yōu)槊魑?X=D(S’)=∑aixi。版權(quán)所有 ,引用請注明出處 55 背包算法的加密 /解密過程 ? 加密 – 將明文分為長度為 n的塊 X=(x1,…,x n) – 然后用轉(zhuǎn)換背包 —公鑰 A 39。 設(shè)：背包序列為 {2,3,6,13,27,52}，求解 密文 S=70的 明文 X。 ◆ 難解的背包作為公鑰 ，可以實現(xiàn)加密。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ? 背包算法只能用于加密 /解密。版權(quán)所有 ,引用請注明出處 44 DiffieHellman密鑰交換的攻擊 ? 舉例 – A和 B選擇素數(shù) p以及 p的一個本原根 a(假定 O知道 ) – A選擇 Xap,計算 Ya=aXa mod p, A?B: Ya – O截獲 Ya,選 Xo,計算 Yo=aXo mod p,冒充 A?B:Yo – B選擇 Xbp,計算 Yb=aXb mod p, B?A: Yb – O截獲 Yb,冒充 B?A:Yo – A計算 : (Yo)Xa?(aXo)Xa?aXoXa mod p – B計算 : (Yo)Xb?(aXo)Xb?aXoXb mod p – O計算 : (Ya)Xo?aXaXo mod p, (Yb)Xo?aXbXo mod p ? 在這種攻擊方式中， O無法計算出 A和 B期望獲得的會話密鑰 K=aXaXb mod p，但 O與 A和 B分別建立了共享密鑰aXaXo mod p和 aXbXo mod p。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 計算過程如下： ① A計算 X=ax mod p=397 mod 353＝ 40，并發(fā)送給 B。版權(quán)所有 ,引用請注明出處 39 DiffieHellman密鑰交換 ? 算法描述： – 假定 A,B雙方共同選擇素數(shù) p以及 p的一個本原根 a（ p和 a可以公開 ） – 用戶 A選擇一個隨機數(shù) Xa p，計算 Ya=aXa mod p – 用戶 B選擇一個隨機數(shù) Xb p，計算 Yb=aXb mod p – 每一方保密 X值，而將 Y值通過公開信道交換給對方（ Ya和 Yb無需保密 ） – 用戶 A計算出 K=YbXa mod p=(aXb)Xa mod p =aXbXa mod p – 用戶 B計算出 K39。版權(quán)所有 ,引用請注明出處 36 內(nèi)容提要 ? 公鑰密碼算法概述 ? 公鑰密碼體制的基本原理 ? 公鑰密