公鑰密碼技術(shù)PPT課件

1、RSA公鑰密碼算法及其用于加密和簽名的實(shí)現(xiàn)。ElGamal公鑰密碼算法及其用于加密和簽名的實(shí)現(xiàn)。ECC公鑰密碼算法及其用于加密和簽名的實(shí)現(xiàn)。公鑰密碼算法的設(shè)計(jì)基本方法和安全性原理。公鑰密碼體制加密密鑰公開，解決了密鑰管理與分公鑰密碼體制加密密鑰公開，解決了密鑰管理與分發(fā)的問題。那么如何實(shí)現(xiàn)公鑰密碼呢？本章介紹幾個典型發(fā)的問題。那么如何實(shí)現(xiàn)公鑰密碼呢？本章介紹幾個典型的公鑰密鑰算法，包括基于大數(shù)分解難題的的公鑰密鑰算法，包括基于大數(shù)分解難題的RSARSA算法，基算法，基于有限域上求解離散對數(shù)難解問題的于有限域上求解離散對數(shù)難解問題的ElGamalElGamal算法，以及算法，以及基于橢圓曲線上求

2、解離散對數(shù)難解問題的基于橢圓曲線上求解離散對數(shù)難解問題的ECCECC算法。算法。 25.1 RSA公鑰密碼算法5.2 Diffie-Hellman密鑰協(xié)商機(jī)制5.3 ElGamal公鑰密碼體制5.4 橢圓曲線密碼體制34 RSA（public-key cryptography），以當(dāng)時在MIT的提出者Rivest、Shamir和Adleman三個人的名字命名，于1978年公開描述的。 RSA既可以用于加密也可以用于簽名。 RSA包括公鑰和私鑰兩個密鑰，公鑰可以讓任何人知道并用于加密消息，使用公鑰加密的消息只能使用對應(yīng)的私鑰解密。5信息安全技術(shù)基礎(chǔ) 張浩軍678 定義1（同余）：設(shè)a、b、m是正

3、整數(shù)，如果m|(a-b)，即m整除(a-b)，則稱a和b模m同余，記為 定理1：（素數(shù)分解定理）：對任意正整數(shù)n，存在唯一的正素數(shù)序列 ，以及正整數(shù) ，使得： 。 定義2（歐拉數(shù)）：設(shè)n是一個正整數(shù)， ，即小于n的與n互素的正整數(shù)，稱為歐拉數(shù)。 特別地，當(dāng)p是一個素數(shù)時，則 。9)(modmba mppp.21m,.,21mmpppn.2121| 1),gcd(, 11 | |)(nxnxxn1)( pp 定理2：如果n1和n2互素，則 。 定理3：如果一個正整數(shù)n按“定理1”分解并表示為 ，則 。 定理4：（Euler定理，歐拉定理）設(shè)x和n都是正整數(shù)，如果gcd(x,n)=1，則 定理5（

4、Fermat小定理）：設(shè)x和p都是正整數(shù)。如果p是素數(shù)，則10)()()(2121nnnnmmpppn.2121)/11).(/11)(/11 ()(21mpppnn)(mod1)(nxn)(mod pxxp 概率測試方法，選取特定比特長度的隨機(jī)數(shù)，通過多次迭代進(jìn)行概率素性測試。 例如Fermat素性測試：給定整數(shù)給定整數(shù)n，選擇一些與，選擇一些與n互素整數(shù)互素整數(shù)a，計(jì)算，計(jì)算an-1 mod n，如果結(jié)果不是如果結(jié)果不是1，則，則n是合數(shù)；若結(jié)果是是合數(shù)；若結(jié)果是1，n可能是也可可能是也可能不是素數(shù)能不是素數(shù)。11如何快速如何快速產(chǎn)生素數(shù)產(chǎn)生素數(shù)？ Miller-Rabin素性測試和Sol

5、ovay-Stassen素性測試算法，對于任意合數(shù)n，至少3/4（Miller-Rabin）、1/2（Solovay-Stassen）的a可以作為n是合數(shù)的證據(jù)。也稱合數(shù)測試。 Miller-Rabin方法：給定整數(shù)n，選擇一些整數(shù)an，令 ，d為奇數(shù)。對于所有的 如果： 而且 ，則n是合數(shù)；否則n可能是素數(shù)，也可能不是素數(shù)。通過多次迭代，提高判定n是素數(shù)概率。12如何快速如何快速產(chǎn)生素數(shù)產(chǎn)生素數(shù)？10sr 模冪運(yùn)算滿足分配律 (a mod n) (b mod n) mod n = (a b) mod n利用中間結(jié)果對利用中間結(jié)果對n n取模，即降低了存儲要求，并可實(shí)現(xiàn)高取模，即降低了存儲要求

6、，并可實(shí)現(xiàn)高效算法。效算法。 遞進(jìn)式指數(shù)計(jì)算例如計(jì)算ad (mod n)，為了便于計(jì)算機(jī)實(shí)現(xiàn)，其中指數(shù)d可以表示為k比特二進(jìn)制(bk-1bk-2.b1b0)2，因此，d可以記為：有：13如何快速進(jìn)行模指數(shù)運(yùn)算？如何快速進(jìn)行模指數(shù)運(yùn)算？02ibidmodmodmod0)2(0)2(iiiibbdnanana 采用擴(kuò)展歐幾里得算法快速計(jì)算d：ax+by = gcd(a,b)gcd(a,b)表示a和b的最大公約數(shù) 即求解x和y，使得上面等式成立。對應(yīng)地，求解式子ed+(-k)(n) =1中d和-k。14如何如何求解私鑰求解私鑰？ （1）窮舉攻擊即列出所有可能的私鑰，顯然這是缺乏效率和困難的。 （2）

7、因數(shù)分解攻擊給定某個整數(shù) ，求c的模n的e次方根 是一個困難問題，但如果整數(shù)n的素數(shù)分解已知，則上述問題易解。因此，因數(shù)分解攻擊RSA途徑包括： 分解n為p和q。 直接確定 ，而不確定p和q。 直接確定d，而不確定 。15)(n)(n （3）參數(shù)選取不當(dāng)造成的攻擊選取p和q時應(yīng)該是隨機(jī)的且不應(yīng)太接近。因?yàn)椋?，當(dāng)(p-q)/2很小時，那么(p+q)/2只比 大一點(diǎn)，因此逐個檢查大于 的整數(shù)x，使得 是一個完全平方數(shù)，記為y2，那么就有 ： 和 。164/)(4/)(22qpqppqnnnnx 2yxpyxq （4）選擇密文攻擊攻擊者得到兩個明/密文對 、 ，則可以獲得 的密文結(jié)果，因?yàn)?由明密

8、文對 ，可以獲得對 的加密結(jié)果，因?yàn)?此外， 能夠獲得 的解密結(jié)果，就可以恢復(fù)出c對應(yīng)的明文。17),(00cm),(11cm10mm )(mod)(mod )(101010nccnmmmmeee),(00cmrm0)(mod)(00ncmrer)(mod2(nce1819（6）?。┬?e 攻擊攻擊 采用很小加密指數(shù)，如采用很小加密指數(shù)，如 e=3，加密值很小的消息，加密值很小的消息 m，如，如 mn1/e，即，即me遠(yuǎn)小于模數(shù)遠(yuǎn)小于模數(shù) n，這，這樣樣，直接計(jì)算，直接計(jì)算 e 的指數(shù)的指數(shù)，密文很容易被破解。，密文很容易被破解。 此外，若多個人使用相同的此外，若多個人使用相同的 e=3，但彼

9、此，但彼此 n 不同，設(shè)有不同，設(shè)有 3 個人分個人分別使用別使用 n1、n2、n3，若他們加密相同消息，若他們加密相同消息 m，即有：即有： )(mod131nmc 、)(mod232nmc 、)(mod333nmc ， 因?yàn)橐话闱闆r下因?yàn)橐话闱闆r下 n1、n2、n3是互素的，使用中國剩余定理可得：是互素的，使用中國剩余定理可得： )(mod3213nnnmc， 又因?yàn)橛忠驗(yàn)?m n1,n2,n3，所以所以 m3 n1 n2 n3，則，則3cm 。 隨機(jī)填充機(jī)制加密消息優(yōu)化非對稱加密填充OAEP（Optimal Asymmetric Encryption Padding）機(jī)制 添加隨機(jī)元素將

10、確定密碼機(jī)制（如基本RSA）轉(zhuǎn)換為一個概率機(jī)制。 部分密文解密（或其他信息泄露），只要不能翻轉(zhuǎn)單向陷門函數(shù)，攻擊者仍不能解密任何密文部分。20使用相同公鑰，加密相同明文能否得到不同密文？（1）明文m后面填充k1個0。（2）產(chǎn)生k0比特隨機(jī)數(shù)r。（3）使用G將k0比特隨機(jī)數(shù)r擴(kuò)展為(n-k0)長度比特串。（4）計(jì)算x=m000G(r)。（5）使用H將(n-k0)長度x壓縮為長度k0比特串。（6）計(jì)算y=rH(x)。（7）最后輸出x|y。21解密操作：（1）恢復(fù)隨機(jī)串r= yH(x)。（2）恢復(fù)消息m000 = x G(r)。 22235.1 RSA公鑰密碼算法5.2 Diffie-Hellman

11、密鑰協(xié)商機(jī)制5.3 ElGamal公鑰密碼體制5.4 橢圓曲線密碼體制24 D-H密鑰協(xié)商機(jī)制，可以實(shí)現(xiàn)在不安全信道中為兩個實(shí)體建立一個共享秘密，協(xié)商的秘密可以作為后續(xù)對稱密碼體制的密鑰使用。25信息安全技術(shù)基礎(chǔ) 張浩軍26D-H協(xié)商協(xié)議描述及實(shí)例27D-H協(xié)議中間人攻擊285.1 RSA公鑰密碼算法5.2 Diffie-Hellman密鑰協(xié)商機(jī)制5.3 ElGamal公鑰密碼體制5.4 橢圓曲線密碼體制293031pmggmababakakkkmod/ 離散對數(shù)難解問題，即給定ga，求解a是困難的。323334355.1 RSA公鑰密碼算法5.2 Diffie-Hellman密鑰協(xié)商機(jī)制5.

12、3 ElGamal公鑰密碼體制5.4 橢圓曲線密碼體制363738394041424344454647484950515253 橢圓曲線上點(diǎn)群法則規(guī)定如下：設(shè)P、Q是E上的兩個點(diǎn)，連接兩個點(diǎn)得到一條直線，如果直線與曲線交叉，則得到第3個點(diǎn)（如圖所示得到點(diǎn)R）；如果該直線在其中一個點(diǎn)與曲線相切，則該點(diǎn)計(jì)兩次；如果直線與y軸平行，則定義第3個點(diǎn)為無窮遠(yuǎn)點(diǎn)。3橢圓曲線上加法運(yùn)算幾何含義橢圓曲線上加法運(yùn)算幾何含義543橢圓曲線上加法運(yùn)算幾何含義橢圓曲線上加法運(yùn)算幾何含義性質(zhì)：（1）曲線上三個點(diǎn)在一條直線上，則它們的和等于O。（2）曲線上點(diǎn)P，則存在一個負(fù)點(diǎn)，記為-P，P+(-P)=O。（3）若一條垂直

13、x軸的豎線交于曲線上兩點(diǎn)P、Q，則P+Q+O=O，于是有P=-Q。（4）如果曲線上兩個點(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)算，定義一個點(diǎn)P的兩倍是它的切線與曲線的另一個交點(diǎn)R，則P+P=2P=-R=R。553橢圓曲線上加法運(yùn)算幾何含義橢圓曲線上加法運(yùn)算幾何含義563橢圓曲線上加法運(yùn)算幾何含義橢圓曲線上加法運(yùn)算幾何含義57585960616263646566本章介紹公鑰密碼體制的工作原理和具體實(shí)現(xiàn)方法。本章介紹公鑰密碼體制的工作原理和具體實(shí)現(xiàn)方法。介紹了典型公鑰密碼算法，如介紹了典型公鑰密碼算法，如RSARSA、ElGamalElGamal，以及強(qiáng)度更高，以及強(qiáng)度更高的橢圓曲線密碼體制。描述了相關(guān)公鑰密碼算法的實(shí)現(xiàn)機(jī)理的橢圓曲線密碼體制。描述了相關(guān)公鑰密碼算法的實(shí)現(xiàn)機(jī)理和對應(yīng)密碼體制的工作過程，討論了和對應(yīng)密碼體制的工作過程，討論了RSARSA算法具體實(shí)現(xiàn)過程算法具體實(shí)現(xiàn)過程中素數(shù)產(chǎn)生、模數(shù)運(yùn)算等