信息安全技術(shù)基礎(chǔ)第5章

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

，以及正整數(shù)

，使得：

。定義2（歐拉數(shù)）：設(shè)n是一個(gè)正整數(shù)，

，即小于n的與n互素的正整數(shù)，稱為歐拉數(shù)。特別地，當(dāng)p是一個(gè)素?cái)?shù)時(shí)，則

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

。定理3：如果一個(gè)正整數(shù)n按“定理1”分解并表示為

，則

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

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

，d為奇數(shù)。對(duì)于所有的

如果：

而且

，則n是合數(shù)；否則n可能是素?cái)?shù)，也可能不是素?cái)?shù)。通過多次迭代，提高判定n是素?cái)?shù)概率。12如何快速產(chǎn)生素?cái)?shù)？5.1.3RSA算法實(shí)現(xiàn)中的計(jì)算問題模冪運(yùn)算滿足分配律

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

利用中間結(jié)果對(duì)n取模，即降低了存儲(chǔ)要求，并可實(shí)現(xiàn)高效算法。遞進(jìn)式指數(shù)計(jì)算

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

有：13如何快速進(jìn)行模指數(shù)運(yùn)算？5.1.3RSA算法實(shí)現(xiàn)中的計(jì)算問題采用擴(kuò)展歐幾里得算法快速計(jì)算d：

ax+by=gcd(a,b)

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

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

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

給定某個(gè)整數(shù)

，求c的模n的e次方根

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

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

。155.1.4RSA體制安全性分析（3）參數(shù)選取不當(dāng)造成的攻擊

選取p和q時(shí)應(yīng)該是隨機(jī)的且不應(yīng)太接近。

因?yàn)椋?/p>

，當(dāng)(p-q)/2很小時(shí)，那么(p+q)/2只比

大一點(diǎn)，因此逐個(gè)檢查大于

的整數(shù)x，使得

是一個(gè)完全平方數(shù)，記為y2，那么就有

：

和

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

攻擊者得到兩個(gè)明/密文對(duì)

、

，則可以獲得

的密文結(jié)果，因?yàn)?/p>

由明密文對(duì)

，可以獲得對(duì)

的加密結(jié)果，因?yàn)?/p>

此外，能夠獲得

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

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

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

y

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

G(r)。

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

則P+Q+O=O，于是有P=-Q。（4）如果曲線上兩個(gè)點(diǎn)P和Q的x坐標(biāo)不同，則連接P和Q得到一條直線與曲線交于R‘點(diǎn)，則P+Q+R’=O，若R是R‘的負(fù)點(diǎn)，則P+Q=-R’=R。（5）倍數(shù)運(yùn)算，定義一個(gè)點(diǎn)P的兩倍是它的切線與曲線的另一個(gè)交點(diǎn)R‘，則P+P=2P=-R’=R。553．橢圓曲線上加法運(yùn)算幾何含義5.4.1橢圓曲線基本概念563．橢圓曲線上加法運(yùn)算幾何含義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基于橢圓曲線的數(shù)字簽名算法645.4.4基于橢圓曲線的數(shù)字簽名算法655.4.5ECC安全強(qiáng)度分析66小結(jié)本章介紹公鑰密碼體制的工作原理和具體實(shí)現(xiàn)方法。介紹了典型公鑰密碼算法，如RSA、ElGamal，以及強(qiáng)度