【正文】 ORITHM”。 (6)把明文中的每個字符（包括空格）用兩位十進制數(shù)字表示，例如：空格 =00， A=01， B=02， ...， Z=26。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 舉例 (7)將要加密的明文消息分成若干個由十進制數(shù)字組成的數(shù)據(jù)塊，每個數(shù)據(jù)塊的值不超過 n1。結果如下 (n=2867)： 1819 0100 0112 0715 1809 2022 1300 (8)利用加密變換公式 ci=mie mod n，分別對每個數(shù)據(jù)塊進行加密，產生相應的密文塊。例如：c1=18191223 mod 2867=2756 (9)類似的，可以得到整個明文序列對應的密文序列： 2756 2022 0542 0669 2347 0408 1815 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 76 RSA算法 ? RSA概述 ? RSA算法描述 ? RSA實現(xiàn)中的問題 ? RSA安全性分析 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 77 實現(xiàn)中的問題 ① 如何計算 ab mod n ② 如何提高加 /解密運算中指數(shù)運算的有效性 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 78 ① 如何計算 ab mod n ? RSA的加密、解密過程都是求一個整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計算，則中間結果非常大，有可能超出計算機所允許的整數(shù)取值范圍。 ? 利用模運算的性質： (a b) mod n=[(a mod n) (b mod n)] mod n 可減小中間結果。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 ① 如何計算 ab mod n ? 通常在計算中要使用一些特殊的方法 ——反復平方乘 。并且在反復平方乘的過程中，對每一步產生的中間結果進行 ——取模約簡 ，以避免產生過大的數(shù)。 ? 舉例： 計算 117 mod 13。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 ① 如何計算 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è)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 ② 如何提高加 /解密運算中指數(shù)運算的有效性 ? 求 am可如下進行，其中 a， m是正整數(shù)： 將指數(shù) m表示為二進制形式 bk bk1…b 0，即m=bk2k+bk12k1+…+b 121+b0 。 ? 例如： (19)10=(10011)2，則19=b424+b323+b222+b121+b0=1 24+0 23+022+1 21+1 20 ? 舉例 計算 520 mod 35。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 ② 如何提高加 /解密運算中指數(shù)運算的有效性 1)將指數(shù) 20表示成二進制形式： 10100。 2)10100可以通過每次處理一位來實現(xiàn)： (0,1,10,101,1010,10100)2=(0,1,2,5,10,20)10 3)因此，指數(shù) 20可以通過一系列步驟構造出來： 1=0 2+1 2=1 2 5=2 2+1 10=5 2 20=10 2 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 ② 如何提高加 /解密運算中指數(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 盡管“反復平方乘”算法中的步驟很多，但每一步都 很簡單，且在計算過程中不需要計算大小超過模數(shù) 立方的數(shù) 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 84 RSA算法 ? RSA概述 ? RSA算法描述 ? RSA實現(xiàn)中的問題 ? RSA安全性分析 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 RSA的安全性 ? RSA的安全性基于加密函數(shù) Ek(x)=xe mod n是一個單向函數(shù)，對攻擊者來說求其逆運算不可行 ? 攻擊者能解密的“陷門”是分解 n=pq，進而求得 φ(n)=(p1)(q1)，從而能夠確定 e模 φ(n)的乘法逆元 d，即 d≡e1 mod φ(n)，導致攻擊成功。 ? 若要使 RSA安全， p與 q必須為足夠大的素數(shù)，建議選擇 p和 q大約是 100～ 200位十進制數(shù)字。模 n的長度要求是一個 1024bit～ 2048bit的數(shù)。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 86 內容提要 ? 公鑰密碼經(jīng)典算法 – DiffieHellman密鑰交換算法 – 背包算法 – RSA算法 – ElGamal算法 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 87 ElGamal算法 ? 既可以用于加密，也可以用于數(shù)字簽名。 ? 其安全性依賴于有限域上計算離散對數(shù)的困難性之上。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 算法描述 用戶 A首先要產生一對密鑰： 1）選擇一個素數(shù) p，以及 p的一個本原根 g。 2）隨機選取整數(shù) x，并滿足 1＜ x＜ p1。 3）計算 y=gx mod p。 4）得到 A的密鑰對為： 公鑰： {p,g,y}， 私鑰： x（ x即為以 g為底模 p下的 y的離散對數(shù)）。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 算法描述 其他任何用戶 B通過 A的公鑰可以加密信息： 1）將明文信息表示為 {0,1， ...， p1}范圍內的一個整數(shù) M，以分組密碼的方式來加密消息。 2）秘密選擇一個隨機整數(shù) k，并滿足 1≤k≤p1 3） 計算一次性密鑰 K=yk mod p。 4）將明文 M加密成密文對（ a,b）。其中： a=gk mod p b=KM mod p 密文長度是明文的兩倍，信息有擴張。 注意： 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 算法描述 用戶 A恢復明文（解密）： 1）通過計算 K=ax mod p恢復密鑰。 2）計算 K在模 p下的乘法逆元 K1，且 K1∈ GF(p) 3）計算 M=(bK1)mod p。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 算法描述 說明： 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 舉例 第一步：生成密鑰 ①用戶 A選取素數(shù) p=19以及 Z19*的一個本原根 g=2。 ② A選取私鑰 x=10，并計算： y=gx mod p=210 mod 19=17 ③ A的公鑰是 {p=19,g=2,y=17}，私鑰是 x=10 第二步：加密 (消息 m=16∈ GF(19)={0,1,2,...,18}) ① B選取一個隨機整數(shù) k=9。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 舉例 ②計算 K=yk mod p=179 mod 19=1 ③計算 a=gk mod p=29 mod 19=18， b=KM mod p=(1*16)mod 19=16 ④ B發(fā)送 (a,b)=(18,16)給 A。 第三步：解密 ① K=ax mod p=1810 mod 19=1 ②在 GF(19)中計算密鑰 K的乘法逆元 K1， K1=1 mod 19=1 ③ m=(bK1)mod p=(16*1)mod 19=16 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 ElGamal算法安全性分析 ? 攻擊 ElGamal公鑰算法等價于求解離散對數(shù)問題，要使用不同的隨機數(shù) k加密不同的消息。 ? 每個明文分塊要有唯一的 k，且 k必須保密 。如果 k用于多個明文分塊的加密，假設用同一個 k加密兩個消息 m1， m2，所得密文分別為 (a1,b1)和 (a2,b2)，則 a1=a2， b1/b2=m1/m2，若 m1已知，則很容易算出 m2。 電子工業(yè)出版社 ，《 信息安全原理與應用 》， 169。版權所有 ,引用請注明出處 ElGamal算法安全性分析 ? 該算法的安全性是建立在“計算離散對數(shù)的困難性之上”。 1為了恢復 A的私鑰 x，攻擊者將會計算離散對數(shù) x=loggy。 2為了計算密鑰 K，攻擊者將會選擇隨機數(shù) k，計算離散對數(shù) k=logga。 3)當模數(shù) p≥300時，計算離散對數(shù)將是不可行的。