1、1密碼基礎非對稱密碼又稱 公鑰密碼信息安全導論（模塊信息安全導論（模塊4密碼基礎）密碼基礎）2對稱密碼體制使用中存在的問題n密鑰分配問題：通信雙方要進行加密通信，需要通過秘密的安全信道協商加密密鑰，而這種安全信道可能很難實現n密鑰管理問題：在有多個用戶的網絡中，任何兩個用戶之間都需要有共享的秘密鑰，當網絡中的用戶n很大時，需要管理的密鑰數目非常大n(n-1)/23對稱加密示意圖注意注意注意注意4公鑰密碼體制n1976年，W.Diffie和M.E.Hellman發表了“密碼學的新方向”一文，提出了公鑰密碼學公鑰密碼學（Public-key cryptography）的思想，在公鑰密碼體制（Pub

2、lic-key cryptosystem）中加密密鑰和解密密鑰是不同的，加密密鑰可以公開傳播而不會危及密碼體制的安全性。n通信的一方利用某種數學方法可以產生一個密鑰對密鑰對，一個稱為公鑰公鑰（Public-key)，另外一個稱為私鑰私鑰（Private-key)。該密鑰對中的公鑰與私鑰是不同的，但又是相互對應的，并且由公鑰不能推導出對應的私鑰。選擇某種算法（可以公開）能做到：用公鑰加密的數據只有使用與該公鑰配對的私鑰才能解密。5公鑰密碼體制n公鑰密碼體制（非對稱）包括兩個密鑰:n公鑰：可以被任何人知道，用于加密n私鑰：只有消息的接收者知道，用于解密n加密者或其他人不能解密n從公鑰無法導出私鑰n

3、是密碼學幾千年歷史中最有意義的結果6n公鑰密碼的特點n由私鑰及其他密碼信息容易計算出公開密鑰 n由公鑰及算法描述，計算私鑰是困難的n因此，公鑰可以發布給其他人7注意注意注意注意非對稱加密示意圖8n公鑰密碼的核心是使用一種特殊的函數單項陷門函數，從一個方向求值是容易的，但逆向計算很困難n定義：設f是一個函數，如果對于任意給定的x，計算y，使得y=f(x)是容易計算的，但對于任意給定的y，計算x是難解的，即求f的逆函數是難解的，則稱f是一個單向函數9n定義：設f是一個函數，t是與f有關的一個參數。對于任意給定的x，計算y，使得y=f(x)是容易的。n如果當不知道參數t時，計算f的逆函數是難解的n但

4、當知道參數t時，計算f的逆函數是容易的n則稱f是一個單向陷門函數，參數t稱為陷門10n公鑰密碼中，加密函數就是一個單向陷門函數，只有解密者知道陷門，可以容易地進行解密，而不知道陷門的人則無法有效解密11典型的公鑰密碼算法1：背包算法n背包系統是1978年Merkle和Hellman基于求解背包問題的難解性提出的一個公鑰密碼系統n背包問題：121314例1516加解密運算：加解密運算：1718例1920發送方（加密）21接收方（解密）22典型的公鑰密碼算法2：RSAnRSA是Rivest、Shamire和Adleman于1978年在美國麻省理工學院研制的n其安全性建立在“大數分解和素性檢測”這一

5、數論難題基礎上n將兩個大素數相乘是容易計算的n將該乘積分解成兩個大素數因子是困難的（計算上不可行）231. 密鑰的產生 選兩個互異的大素數p和q。 計算n=pq，(n)=(p-1)(q-1)，其中(n)是n的歐拉函數值。 選一整數e，滿足1e(n)，且gcd(n),e)=1。 計算d，滿足de1 mod (n)，即d是e在模(n)下的乘法逆元，因e與(n)互素，由模運算可知，它的乘法逆元一定存在。 以e,n為公開鑰,d,p,q為秘密鑰。RSA算法242. 加密加密時首先將明文比特串分組，使得每個分組對應的十進制數小于n，即分組長度小于log2n。然后對每個明文m，作加密運算： cme mod

6、nRSA算法253. 解密對密文分組的解密運算為：mcd mod n證明證明RSA算法中解密過程的正確性算法中解密過程的正確性.證明過程用到數論中的知識 cd mod n med mod n mRSA算法26例： 選p=7，q=17. 求得n=pq=119，(n)=(p-1)(q-1)=96.取e=5，滿足1e(n)，且gcd(n),e)=1，計算滿足de=1 mod 96且小于96的d.因為775=385=496+1，所以d為77，因此公開鑰為5，119，秘密鑰為77，7，17.設明文m=19，則由加密過程得密文為c195 mod 1192476099 mod 11966;解密過程為 m 6

7、677mod 11919.RSA算法271. RSA的加密與解密過程 RSA的加密、解密過程都為求一個整數的整數次冪，再取模。如果按其含義直接計算，則中間結果非常大，有可能超出計算機所允許的整數取值范圍。如上例中解密運算6677 mod 119，先求6677再取模，則中間結果就已遠遠超出了計算機允許的整數取值范圍。而用模運算的性質：(ab) mod n=(a mod n)(b mod n) mod n就可減小中間結果。RSA中的計算問題28 2. 模指數運算的快速算法 例如求x16，直接計算的話需做15次乘法。然而如果重復對每個部分結果做平方運算即求x，x2，x4，x8，x16則只需4次乘法。

8、 求am可如下進行，其中a，m是正整數： 將m表示為二進制形式bk bk-1b0，即m=bk2k+bk-12k-1+b12+b0因此12012222kkkbbbbbmaaaaaa RSA中的計算問題29例例：求a1919=124+023+022+121+120所以 a19=(a1)2a0)2a0)2a1)2a1 RSA中的計算問題30n3、乘法逆元的求法（歐幾里德算法）n整數e，滿足1e(n)，且gcd(n),e)=1n計算d，滿足de1 mod (n)，即d是e在模(n)下的乘法逆元，因e與(n)互素，它的乘法逆元一定存在RSA中的計算問題31RSA中的計算問題32RSA中的計算問題33RS

9、A中的計算問題34前例則則1965195191 mod96則則5的乘法逆元在的乘法逆元在 mod96下為下為1935例3637驗證：驗證：171728939611 mod9638RSA的安全性的安全性是基于分解大整數困難的假定 如果RSA的模數n被成功地分解為pq，則獲得(n)=(p-1)(q-1)，從而攻擊者能夠從公鑰e解出d，即de-1 mod (n)，攻擊成功. RSA算法的安全性39 隨著人類計算能力的不斷提高，原來被認為是不可能分解的大數已被成功分解.例如RSA-129（即n為129位十進制數，大約428個比特）已在網絡上通過分布式計算歷時8個月于1994年4月被成功分解，RSA-1

10、30 已于1996年4月被成功分解.RSA算法的安全性40n商用安全要求nn的長度在10242048比特np和q的長度相差不能太多np-1和q-1都應該包含大的素數因子np-1和q-1的最大公因子要盡可能小41典型的公鑰密碼算法3：ElGamal算法nElGamal公鑰密碼體制是由T.ElGamal于1985年提出的n可用于數據加密，也可用于數字簽名n安全性依賴于有限域上計算離散對數的難題42ElGamal算法43特點44安全性分析n其安全性是建立在有限域上求離散對數難解問題的基礎上n有限域上的離散對數問題：4546ElGamal中參數選擇的安全性要求n素數p至少應為150位以上的十進制數np

11、-1至少應該有一個大的素數因子47公鑰密碼的特點n計算量大，運算速度慢n主要用于密鑰協商n數據加密主要用對稱密碼48n對稱密碼算法，加/解密速度快，但密鑰分發問題嚴重n非對稱密碼算法，加/解密速度較慢，但密鑰分發問題易于解決n為解決每次傳送更換密鑰的問題，結合對稱加密技術和非對稱密鑰加密技術的優點，產生了電子信封技術，用來傳輸數據49加密技術的使用50n加密n認證n數字簽名n身份認證n消息認證51小結n古典密碼術n現代密碼學n對稱密碼，非對稱密碼n典型的對稱密碼，非對稱密碼52作業n背包算法的練習（n8）n兩位同學一組，班內序號(1,2), (3,4), n班內序號為奇數的同學：每人設計一個背包公鑰密碼系統，給出公開鑰，保留秘密鑰n班內序號為偶數的同學：每人用你同伴的公開鑰加密一個明文信息，將密文交給該同學，由該同學解密n每組同學提交一個算法報告（算法的設計過程、公開鑰、秘密鑰、明文、密文、加解密運算過程等）53作業nR