【正文】 1） n的長度應(yīng)與背包序列等長。 (5)再對每個明文塊計算對應(yīng)的密文塊。 （ 7）進(jìn)行解密計算： ① S1’ =w1S1 mod m=61 174 mod 105=9 ② S2’ =w1S2 mod m=61 243 mod 105=18 ③ S3’ =w1S3 mod m=61 333 mod 105=48 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ? 模數(shù) m應(yīng)該有 200到 400位長。 每個明文分組和密文分組的值均在 0～ n1之間（ n的大小為 1024位二進(jìn)制數(shù)或 309位十進(jìn)制數(shù)）。版權(quán)所有 ,引用請注明出處 68 RSA算法描述 ● RSA算法 對明文以分組為單位進(jìn)行加密 。 用戶從 (1, φ(n))中 隨機選擇 一個與 φ(n)互素的數(shù) e(即 gcd(e, φ(n))=1)作為公開加密指數(shù) 。 ③設(shè)第 i個明文分組對應(yīng)的數(shù)字為 mi，對 mi作加密運算。版權(quán)所有 ,引用請注明出處 RSA算法描述 ? 簽名過程：計算簽名 y=Sig(m)=md mod n ? 驗證簽名過程：驗證簽名 m’ =ye mod n，并判斷是否與原來的 m相同。 (6)把明文中的每個字符（包括空格）用兩位十進(jìn)制數(shù)字表示，例如：空格 =00， A=01， B=02， ...， Z=26。如果按其含義直接計算，則中間結(jié)果非常大，有可能超出計算機所允許的整數(shù)取值范圍。版權(quán)所有 ,引用請注明出處 ② 如何提高加 /解密運算中指數(shù)運算的有效性 ? 求 am可如下進(jìn)行，其中 a， m是正整數(shù)： 將指數(shù) m表示為二進(jìn)制形式 bk bk1…b 0，即m=bk2k+bk12k1+…+b 121+b0 。 ? 若要使 RSA安全， p與 q必須為足夠大的素數(shù)，建議選擇 p和 q大約是 100～ 200位十進(jìn)制數(shù)字。 2）隨機選取整數(shù) x，并滿足 1＜ x＜ p1。 注意： 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 舉例 ②計算 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。 2為了計算密鑰 K，攻擊者將會選擇隨機數(shù) k，計算離散對數(shù) k=logga。如果 k用于多個明文分塊的加密，假設(shè)用同一個 k加密兩個消息 m1， m2，所得密文分別為 (a1,b1)和 (a2,b2)，則 a1=a2， b1/b2=m1/m2，若 m1已知，則很容易算出 m2。版權(quán)所有 ,引用請注明出處 算法描述 說明： 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 算法描述 其他任何用戶 B通過 A的公鑰可以加密信息： 1）將明文信息表示為 {0,1， ...， p1}范圍內(nèi)的一個整數(shù) M，以分組密碼的方式來加密消息。版權(quán)所有 ,引用請注明出處 87 ElGamal算法 ? 既可以用于加密，也可以用于數(shù)字簽名。 2)10100可以通過每次處理一位來實現(xiàn)： (0,1,10,101,1010,10100)2=(0,1,2,5,10,20)10 3)因此，指數(shù) 20可以通過一系列步驟構(gòu)造出來： 1=0 2+1 2=1 2 5=2 2+1 10=5 2 20=10 2 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。并且在反復(fù)平方乘的過程中，對每一步產(chǎn)生的中間結(jié)果進(jìn)行 ——取模約簡 ，以避免產(chǎn)生過大的數(shù)。例如：c1=18191223 mod 2867=2756 (9)類似的，可以得到整個明文序列對應(yīng)的密文序列： 2756 2022 0542 0669 2347 0408 1815 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 （ n是公開的） (3)φ(n)=(p1)(q1)=46*60=2760。 ② 將以上數(shù)字串分段，使得每一段數(shù)字均小于 n。則 RSA的密鑰對為： 公鑰： (n,e) 私鑰 :（ p,q,d) 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 RSA算法描述 ( 1 ) 為了產(chǎn)生 RSA的公鑰和私鑰對 ， 用戶需要秘密選擇 兩個大素數(shù) p和 q(各 100～ 200位十進(jìn)制數(shù)字 ),且 p和 q等長 ， 但 p≠q。版權(quán)所有 ,引用請注明出處 RSA算法 ? RSA密碼特點 RSA既可以用來加密 /解密，又可以實現(xiàn)數(shù)字簽名。版權(quán)所有 ,引用請注明出處 64 RSA算法 ? RSA概述 ? RSA算法描述 ? RSA實現(xiàn)中的問題 ? RSA安全性分析 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ? 單向性 : 體現(xiàn)在普通背包容易用來加密，但難解密 。版權(quán)所有 ,引用請注明出處 舉例 1 （ 5）所以，密文為 174,243,333。令 w=31，模數(shù) m=105（滿足 gcd(w,m)=1）。 w1又稱為 “轉(zhuǎn)換因子 ”。這樣得到的背包 A’ =(a1’ ,a2’ ,...,an’ )是非超遞增背包 ——普通背包。這樣的背包也稱為 “簡單背包 ”。版權(quán)所有 ,引用請注明出處 背包算法的思想 ? 背包問題用于公鑰密碼學(xué)的基本做法是：假設(shè)明文為 X（即明文為二進(jìn)制向量）， S為密文。其中，“ W1,W2,W3,……,W n”稱為“背包序列” 。 ★防止 DiffieHellman密鑰交換算法中間人攻擊的一個方法是讓 A和 B分別對消息進(jìn)行認(rèn)證，即加上 數(shù)字簽名 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ? 當(dāng) A加密一個消息發(fā)送給 B時， O能解密而 B不能。版權(quán)所有 ,引用請注明出處 DiffieHellman密鑰交換 ? 優(yōu)點 (1)任何兩個用戶都可通過協(xié)商計算出會話密鑰 ,不需事先擁有對方的公開或秘密信息。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ? 該算法的唯一目的是使兩個用戶能夠通過公開信道交換彼此的信息，得到一個共享的會話密鑰。 可以驗證： 元素 2,6,7,11中的每一個均能生成 Z13* ，因此，這四個元素都可以作為素數(shù) 13的本原根 （生成元）。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 離散對數(shù)難題 密碼學(xué)中常用的是三個有限域上的離散對數(shù)， 這三個有限域分別是： ●有限域 GF(p)上的乘法群。 有限域的階數(shù)必須是素數(shù)或者素數(shù)的冪。其中，“ F\{0}”表示集合 F除去元素 {0}后的元素 ⑷對于 a,b,c∈ F分配律成立。 ⑶ 存在單位元 e： 即存在 e∈ G,對任意的 a∈ G，恒有a*e=e*a=a ⑷ 存在逆元： 對于 a∈ G，恒有 b∈ G，使 a*b=b*a=e(這里 e為單位元，則元素 b稱為元素 a的逆元素，用 a1表示記為： a1=b 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。特別的，有如下幾種情況： – n是素數(shù) ， ?(n)=n1 – 若 n的因子分解為 n=?Piai, ai0,Pi互不相同 ， 則 ?(n)= ?Piai?(11/Pi)=n(11/p1)(11/p2)…(1 1/pn) p1,p2,…,p n是 n的素數(shù)因子 – 若 gcd(m,n)=1， 則 ?(mn)=?(m)?(n)， – 特別地 ， 若 gcd(m,n)=1且 m?n且都是素數(shù) ， ?(mn)=?(m)?(n)=(m1)(n1) ? 舉例： 20=2 2 5，它有兩個素數(shù)因子 2和 5，故 φ(20)=20(11/2)(11/5)=8。 (3)合法用戶利用陷門信息 —私鑰，容易由 Y求出明文 X，實現(xiàn)解密。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 ●對于攻擊者，利用 B的公鑰 KUb來推斷其私鑰 KRb在計算上是不可行的。 密鑰交換是通過“ DH密鑰交換算法”實現(xiàn)，從而得到會話密鑰 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。版權(quán)所有 ,引用請注明出處 公鑰密碼體制的概念 應(yīng)用二：數(shù)字簽名 其主要步驟如下： (1)用戶 B用自己的私鑰 KRb對消息 X簽名Y=EKRb(X) (2)收到簽名 Y的其他人可以用 B的公鑰 KUb對消息的簽名進(jìn)行驗證， DKUb(Y)=DKUb(EKRb(X))=X。并且 每一個用戶可以擁有其他多個用戶的公鑰 。 加密： XY: Y = EKU(X) 解密： YX: X = DKR(Y) = DKR(EKU(X)) (2)知道加密算法，從加密密鑰得到解密密鑰在計算上是不可行的。 ? 公鑰密碼算法： RSA，背包密碼和 ElGamal算法。版權(quán)所有 ,引用請注明出處 概述 ? 對稱密鑰密碼體制的缺陷： (1)由于對稱密鑰密碼系統(tǒng)的保密性主要取決于密鑰的安全性，故在進(jìn)行保密通信前，通信雙方必須通過安全的信道傳送所用的密鑰，對于相距較遠(yuǎn)的用戶可能要付出巨大的代價，甚至難以實現(xiàn)。電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 (2)隨著網(wǎng)絡(luò)規(guī)模的擴大，在對稱密鑰密碼體制中，密鑰的管理成為一個難點。 電子工業(yè)出版社 ，《 信息安全原理與應(yīng)用 》， 169。 (3)兩個密鑰中任何一個都可以用作加密而另一個則用作解密。 (3)若 B要給 A發(fā)送消息，則用 A的公鑰 KUa對消息X加密， BA:Y=EKUa(X)。因為只有 B才擁有能夠產(chǎn)生簽名的私鑰 KRb，所以，如果用 B的公鑰 KUb驗證正確的話，就可以相信消息的確是 B發(fā)出的。版權(quán)所有 ,引用請注明出處 公鑰密碼體制的概念 ? 小結(jié)： 公鑰密碼體制的應(yīng)用可以分為三類： ◆ 加 /解密： 發(fā)送方用接收方的公鑰加密，接收方用自己的私鑰解密。 ●已知公鑰 KUb和密文 Y，想恢復(fù)明文 X在計算上是不可行的。版權(quán)所有 ,引用請注明出處 公鑰密碼體制的思想和要求 ? 例如：計算兩個素數(shù) p和 q的乘積 N=pq是容易的，但給定 N，要分解出它的質(zhì)因子 p和 q則是非常困難的。 (4)不掌握陷門信息者無法由密文求得明文。 即 20中有 8個整數(shù)與 20是互素的。版權(quán)所有 ,引用請注明出處 群和域的概念 ? 進(jìn)行群運算的次序非常重要。即： （ a+b） *c=a*c+b*c c*(a+b)=c*a+c*b 電子工業(yè)出版社 ，《 信