【正文】 K1=1 mod 19=1 ③ m=(bK1)mod p=(16*1)mod 19=16 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 算法描述 用戶 A恢復明文（解密）： 1）通過計算 K=ax mod p恢復密鑰。 3）計算 y=gx mod p。模 n的長度要求是一個 1024bit～ 2048bit的數(shù)。 ? 例如： (19)10=(10011)2，則19=b424+b323+b222+b121+b0=1 24+0 23+022+1 21+1 20 ? 舉例 計算 520 mod 35。 ? 利用模運算的性質(zhì)： (a b) mod n=[(a mod n) (b mod n)] mod n 可減小中間結(jié)果。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。即將消息mi以加密指數(shù) e做乘方，并取模 n，即： ci=mie mod n (0≤min) ④最后得到的密文 C由所有長度相同的密文分組 ci組成。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 ( 1 ) 若明文是以 二進制形式 存在 ， 則每個二進制分組 的值均小于 n（ 即每個二進制分組轉(zhuǎn)換成的相應 的十進制數(shù)值必須小于 n） ， 也就是說 ， 分組的 長度必須小于或等于 log2n+1。 RSA密碼體制的 安全性是建立在大整數(shù)的質(zhì)因子分解困難性之上 。 ? 實際實現(xiàn)時，用隨機序列發(fā)生器來產(chǎn)生這些值，這樣的背包才能抵抗“強力攻擊”。版權所有 ,引用請注明出處 舉例 1 （ 8）求解超遞增背包問題，將密文塊變?yōu)槊魑膲KX=D(S’ )=∑aixi。計算結(jié)果如下： ①對于 X1=01100 所以S1=E(X1)=∑ai’ xi=0*62+1*93+1*81+0*88+0*102=93+81 =174 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 2）用作加密的明文應為二進制序列，故若原明 文不是二進制序列，在加密前應將其轉(zhuǎn)換成對應 的二進制序列。, …, a n 39。版權所有 ,引用請注明出處 易解的背包問題 ——超遞增背包 ——私鑰 解： ∵ S=70＞ a6=52 ∴ 7052=18 且 x6=1 ∵ 18＜ a5=27 ∴ x5=0 ∵ 18＞ a4=13 ∴ 1813=5 且 x4=1 ∵ 5＜ a3=6 ∴ x3=0 ∵ 5＞ a2=3 ∴ 53=2 且 x2=1 ∵ 2=a1=2 ∴ x1=1 所以，密文 S=70對應的明文 X=(x1x2x3x4x5x6)=110101, 即： x1a1+x2a2+x3a3+x4a4+x5a5+x6a6=1 2+1 3+0 6+1 13+0 27 +1 52=70 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。需要的 總重量是 S=172。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 DiffieHellman密鑰交換的攻擊 接下來， A和 B 之間的通信以下列方式泄密： (1)A發(fā)送一份加過密的消息 M： EaXaXo mod p(M) (2)O截獲該密文，并進行解密恢復出 M。 ? 一個主動的竊聽者 O可能截取 A發(fā)給 B的消息以及 B發(fā)給 A的消息，并且他用自己的消息替換這些消息。 ④ B計算 k39。=aXaXbmod p 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 38 DiffieHellman密鑰交換 ? 是第一個公鑰方案 ? 其安全性建立在 “有限域 中計算離散對數(shù)的困難性 ”的基礎上。版權所有 ,引用請注明出處 b 離散對數(shù)難題 ? 舉例： 素數(shù) p=19的本原根有 g=2,3,10,13,14,15。版權所有 ,引用請注明出處 離散對數(shù)難題 ? 定義素數(shù) p的本原根 g 素數(shù) p的本原根：又稱為素數(shù) p的“生成元”，為一 種能生成 1～ p1之間所有數(shù)的一個數(shù)。 最簡單的有限域是 GF(2)，該域元素的個數(shù)為 2個，分別是 0 和 1，即 GF(2)={0,1}=Z2。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 群和域的概念 ? 域的概念 定義： F是至少含有兩個元素的集合，對 F定義了兩種運算“ +”和“ ”，并且滿足下列三個條件的代數(shù)系統(tǒng) F,+, 稱為域： ⑴用 0代表“ +”的單位元， 1代表“ ”的單位元。版權所有 ,引用請注明出處 群和域的概念 ? 群的概念 定義：給定一個集合 G={a,b,……} 和該集合上的運算 *(*具有一般性，可以指加法，乘法或者其他數(shù)學運算 )，它結(jié)合了任何兩個元素 a和 b而形成另一個元素，記為a*b。 ? 推論 : p是素數(shù)， a是任意正整數(shù)， ap≡a mod p 此時不要求 gcd(a,p) =1。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 公鑰密碼體制的概念 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。其主要步驟如下： (1)發(fā)送方 A先用自己的私鑰 KRa對消息進行簽名，然后再用接收方 B的公鑰 KUb加密， AB: Z=EKUb(EKRa(X)) (2)接收方 B收到密文，先用自己的私鑰 KRb解密，再用 A的公鑰 KUa驗證簽名的正確性，DKUa(DKRb(Z))=X 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 應用一：加 /解密 基于公鑰密碼算法的加 /解密過程如圖 41所示 Bob的密鑰對： 公鑰 KUb 私鑰 KRb Alice的密鑰對： 公鑰 KUa 私鑰 KRa 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 公鑰密碼體制的概念 ? 公鑰密碼算法的特點 (1)加密與解密由不同的密鑰完成。 無法實現(xiàn)“不可否認性”?。。? 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。公鑰密碼學與之前的密碼學完全不同。版權所有 ,引用請注明出處 概述 ? 公鑰密碼學的發(fā)展是整個密碼學發(fā)展史上最偉大的一次革命。例如： n= 100時， C(100,2)=100*(1001)/2=4,995 n= 5000 時 , C(5000,2)=5000*(50001)/2=12,497,500 (3)對稱密鑰密碼體制無法解決對消息的篡改、偽造和否認等問題 ——即無法實現(xiàn)“數(shù)字簽名”。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 公鑰密碼體制的概念 ? 公鑰密碼的應用 公鑰密碼算法可以用于加密 /解密，數(shù)字簽名 (身份鑒別 )和 密鑰交換。由于只有 A擁有私鑰 KRa，所以 除 A以外的所有人都無法解密密文 Y。版權所有 ,引用請注明出處 公鑰密碼體制的概念 應用三：同時實現(xiàn)保密性和身份鑒別 如果兩次使用公鑰密碼算法，則可以既實現(xiàn)保密通 信，又實現(xiàn)身份鑒別。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 在數(shù)學上可以用“單向陷門函數(shù)”來表達上述要求。因此，研究公鑰密碼算法就是要找出合適的單向陷門函數(shù)。版權所有 ,引用請注明出處 Fermat定理 ? 費馬定理 : 若 p是素數(shù) , a是正整數(shù)，且 gcd(a,p)=1 則： ap1≡1 mod p。版權所有 ,引用請注明出處 Euler定理 ? Euler定理 : 若 a與 n為互素的正整數(shù) ， 則 ： a?(n) ? 1 mod n ? 推論 : 若 n=pq， p?q都是素數(shù) ， k是任意整數(shù) ， 則 mk(p1)(q1)+1 ? m mod n， 對任意 0?m?n 即歐拉函數(shù) φ(n) 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 ? a*b=b*a這個等式在整數(shù)集合的加法運算下的群中總是成立，因為對于任何兩個整數(shù)都有a+b=b+a,在乘法運算下的非零實數(shù)集合也成立 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 ? 在密碼學中，更多得是對 包含有限個元素的域進行研究。 GF(p)中的所有非 0元素都存在乘法逆元。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 37 內(nèi)容提要 ? 公鑰密碼經(jīng)典算法 – DiffieHellman密鑰交換算法 – 背包算法 – RSA算法 – ElGamal算法 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。=YaXb mod p=(aXa)Xb mod p =aXaXb mod p – 雙方獲得一個共享密鑰 K=K39。 ② B計算 Y=ay mod p=3233 mod 353＝ 248，并發(fā)送給 A ③ A計算 k=Yx mod p＝ 24897 mod 353=版權所有 ,引用請注明出處 DiffieHellman密鑰交換的攻擊 ? “中間人攻擊”是一種主動攻擊方式。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 ? 背包算法的安全性基于“背包問題”。版權所有 ,引用請注明出處 背包問題 ? 舉例 假設重量分別為 85,13,9,7,47,27,99,86。 ◆ 易解的背包作為私鑰 ，可以實現(xiàn)解密，不知道私鑰的人只能求解困難的背包問題（即單向函數(shù)問題）。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。 = (a1 39。（ i=1,2,...,n）