信息安全技術基礎第5章

第5章公鑰密碼技術學習目標RSA公鑰密碼算法及其用于加密和簽名的實現。ElGamal公鑰密碼算法及其用于加密和簽名的實現。ECC公鑰密碼算法及其用于加密和簽名的實現。公鑰密碼算法的設計基本方法和安全性原理。公鑰密碼體制加密密鑰公開，解決了密鑰管理與分發(fā)的問題。那么如何實現公鑰密碼呢？本章介紹幾個典型的公鑰密鑰算法，包括基于大數分解難題的RSA算法，基于有限域上求解離散對數難解問題的ElGamal算法，以及基于橢圓曲線上求解離散對數難解問題的ECC算法。2目錄5.1RSA公鑰密碼算法5.2Diffie-Hellman密鑰協(xié)商機制5.3ElGamal公鑰密碼體制5.4橢圓曲線密碼體制3如何實現加密密鑰公開的加密算法？45.1.1RSA基本算法RSA（public-keycryptography），以當時在MIT的提出者Rivest、Shamir和Adleman三個人的名字命名，于1978年公開描述的。RSA既可以用于加密也可以用于簽名。RSA包括公鑰和私鑰兩個密鑰，公鑰可以讓任何人知道并用于加密消息，使用公鑰加密的消息只能使用對應的私鑰解密。5信息安全技術基礎張浩軍675.1.1RSA基本算法85.1.2RSA加密算法的數論基礎定義1（同余）：設a、b、m是正整數，如果m|(a-b)，即m整除(a-b)，則稱a和b模m同余，記為定理1：（素數分解定理）：對任意正整數n，存在唯一的正素數序列

，以及正整數

，使得：

。定義2（歐拉數）：設n是一個正整數，

，即小于n的與n互素的正整數，稱為歐拉數。特別地，當p是一個素數時，則

。95.1.2RSA加密算法的數論基礎定理2：如果n1和n2互素，則

。定理3：如果一個正整數n按“定理1”分解并表示為

，則

。定理4：（Euler定理，歐拉定理）設x和n都是正整數，如果gcd(x,n)=1，則定理5（Fermat小定理）：設x和p都是正整數。如果p是素數，則105.1.3RSA算法實現中的計算問題概率測試方法，選取特定比特長度的隨機數，通過多次迭代進行概率素性測試。例如Fermat素性測試：

給定整數n，選擇一些與n互素整數a，計算an-1modn，如果結果不是1，則n是合數；若結果是1，n可能是也可能不是素數。11如何快速產生素數？5.1.3RSA算法實現中的計算問題Miller-Rabin素性測試和Solovay-Stassen素性測試算法，對于任意合數n，至少3/4（Miller-Rabin）、1/2（Solovay-Stassen）的a可以作為n是合數的證據。也稱合數測試。Miller-Rabin方法：給定整數n，選擇一些整數a<n，令

，d為奇數。對于所有的

如果：

而且

，則n是合數；否則n可能是素數，也可能不是素數。通過多次迭代，提高判定n是素數概率。12如何快速產生素數？5.1.3RSA算法實現中的計算問題模冪運算滿足分配律

[(amodn)×(bmodn)]modn=(a×b)modn

利用中間結果對n取模，即降低了存儲要求，并可實現高效算法。遞進式指數計算

例如計算ad(modn)，為了便于計算機實現，其中指數d可以表示為k比特二進制(bk-1bk-2...b1b0)2，因此，d可以記為：

有：13如何快速進行模指數運算？5.1.3RSA算法實現中的計算問題采用擴展歐幾里得算法快速計算d：

ax+by=gcd(a,b)

gcd(a,b)表示a和b的最大公約數即求解x和y，使得上面等式成立。對應地，求解式子

ed+(-k)φ(n)=1中d和-k。14如何求解私鑰？5.1.4RSA體制安全性分析（1）窮舉攻擊

即列出所有可能的私鑰，顯然這是缺乏效率和困難的。（2）因數分解攻擊

給定某個整數

，求c的模n的e次方根

是一個困難問題，但如果整數n的素數分解已知，則上述問題易解。因此，因數分解攻擊RSA途徑包括：分解n為p和q。直接確定

，而不確定p和q。直接確定d，而不確定

。155.1.4RSA體制安全性分析（3）參數選取不當造成的攻擊

選取p和q時應該是隨機的且不應太接近。

因為，

，當(p-q)/2很小時，那么(p+q)/2只比

大一點，因此逐個檢查大于

的整數x，使得

是一個完全平方數，記為y2，那么就有

：

和

。165.1.4RSA體制安全性分析（4）選擇密文攻擊

攻擊者得到兩個明/密文對

、

，則可以獲得

的密文結果，因為

由明密文對

，可以獲得對

的加密結果，因為

此外，能夠獲得

的解密結果，就可以恢復出c對應的明文。175.1.4RSA體制安全性分析185.1.4RSA體制安全性分析195.1.5RSA填充加密機制隨機填充機制加密消息——優(yōu)化非對稱加密填充OAEP（OptimalAsymmetricEncryptionPadding）機制添加隨機元素將確定密碼機制（如基本RSA）轉換為一個概率機制。部分密文解密（或其他信息泄露），只要不能翻轉單向陷門函數，攻擊者仍不能解密任何密文部分。20使用相同公鑰，加密相同明文能否得到不同密文？5.1.5RSA填充加密機制（1）明文m后面填充k1個0。（2）產生k0比特隨機數r。（3）使用G將k0比特隨機數r擴展為(n-k0)長度比特串。（4）計算x=m00…0

G(r)。（5）使用H將(n-k0)長度x壓縮為長度k0比特串。（6）計算y=r

H(x)。（7）最后輸出x||y。21解密操作：（1）恢復隨機串r=

y

H(x)。（2）恢復消息m00…0=x

G(r)。

5.1.6RSA簽名算法22能否在不安全的通信信道上傳輸一些公開信息，最終使得雙方獲得秘密信息？23目錄5.1RSA公鑰密碼算法5.2Diffie-Hellman密鑰協(xié)商機制5.3ElGamal公鑰密碼體制5.4橢圓曲線密碼體制245.2Diffie-Hellman密鑰協(xié)商機制D-H密鑰協(xié)商機制，可以實現在不安全信道中為兩個實體建立一個共享秘密，協(xié)商的秘密可以作為后續(xù)對稱密碼體制的密鑰使用。25信息安全技術基礎張浩軍5.2Diffie-Hellman密鑰協(xié)商機制26D-H協(xié)商協(xié)議描述及實例5.2Diffie-Hellman密鑰協(xié)商機制27D-H協(xié)議中間人攻擊基于離散對數難解問題設計的公鑰密碼算法？28目錄5.1RSA公鑰密碼算法5.2Diffie-Hellman密鑰協(xié)商機制5.3ElGamal公鑰密碼體制5.4橢圓曲線密碼體制29305.3.1ElGamal加密算法315.3.2ElGamal公鑰密碼體制的安全性離散對數難解問題，即給定ga，求解a是困難的。325.3.2ElGamal公鑰密碼體制的安全性335.3.3ElGamal簽名算法34如何發(fā)現可用于公鑰密碼體制的代數系統(tǒng)？35目錄5.1RSA公鑰密碼算法5.2Diffie-Hellman密鑰協(xié)商機制5.3ElGamal公鑰密碼體制5.4橢圓曲線密碼體制365.4.1橢圓曲線基本概念375.4.1橢圓曲線基本概念385.4.1橢圓曲線基本概念395.4.1橢圓曲線基本概念405.4.1橢圓曲線基本概念415.4.1橢圓曲線基本概念425.4.1橢圓曲線基本概念435.4.1橢圓曲線基本概念445.4.1橢圓曲線基本概念455.4.1橢圓曲線基本概念465.4.1橢圓曲線基本概念475.4.1橢圓曲線基本概念485.4.1橢圓曲線基本概念495.4.1橢圓曲線基本概念505.4.1橢圓曲線基本概念515.4.1橢圓曲線基本概念525.4.1橢圓曲線基本概念53橢圓曲線上點群法則規(guī)定如下：設P、Q是E上的兩個點，連接兩個點得到一條直線，如果直線與曲線交叉，則得到第3個點（如圖所示得到點R）；如果該直線在其中一個點與曲線相切，則該點計兩次；如果直線與y軸平行，則定義第3個點為無窮遠點。3．橢圓曲線上加法運算幾何含義5.4.1橢圓曲線基本概念543．橢圓曲線上加法運算幾何含義5.4.1橢圓曲線基本概念性質：（1）曲線上三個點在一條直線上，則它們的和等于O。（2）曲線上點P，則存在一個負點，記為-P，P+(-P)=O。（3）若一條垂直x軸的豎線交于曲線上兩點P、Q，

則P+Q+O=O，于是有P=-Q。（4）如果曲線上兩個點P和Q的x坐標不同，則連接P和Q得到一條直線與曲線交于R‘點，則P+Q+R’=O，若R是R‘的負點，則P+Q=-R’=R。（5）倍數運算，定義一個點P的兩倍是它的切線與曲線的另一個交點R‘，則P+P=2P=-R’=R。553．橢圓曲線上加法運算幾何含義5.4.1橢圓曲線基本概念563．橢圓曲線上加法運算幾何含義5.4.2基于橢圓曲線的加密體制575.4.2基于橢圓曲線的加密體制585.4.2基于橢圓曲線的加密體制595.4.2基于橢圓曲線的加密體制605.4.2基于橢圓曲線的加密體制615.4.2基于橢圓曲線的加密體制625.4.3橢圓曲線D-H密鑰協(xié)商635.4.4基于橢圓曲線的數字簽名算法645.4.4基于橢圓曲線的數字簽名算法655.4.5ECC安全強度分析66小結本章介紹公鑰密碼體制的工作原理和具體實現方法。介紹了典型公鑰密碼算法，如RSA、ElGamal，以及強度