信息安全技術(shù)基礎(chǔ) 張浩軍楊衛(wèi)東譚玉波等編著 第5章.pptx

《信息安全技術(shù)基礎(chǔ) 張浩軍楊衛(wèi)東譚玉波等編著 第5章.pptx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第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橢圓曲線密碼體制

2、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

3、(a-b)，即m整除(a-b)，則稱a和b模m同余，記為定理1：（素?cái)?shù)分解定理）：對(duì)任

4、意正整數(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è)試方法，選取特定比特長(zhǎng)度的隨機(jī)數(shù)，通過多次迭代進(jìn)行概率素性測(cè)試。例如Fermat素性測(cè)試：給定整數(shù)n，選擇

5、一些與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

6、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如何求解私

7、鑰？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)?，，?dāng)(p-q)/2很小時(shí)，那么(p+q)/2只比大一點(diǎn)，因此逐個(gè)檢查大于的整數(shù)x，使得是一個(gè)完全平方數(shù)，記為y2，那么就有：和。165.1.4RSA體制安全性分析（4）選擇密

8、文攻擊攻擊者得到兩個(gè)明/密文對(duì)、，則可以獲得的密文結(jié)果，因?yàn)橛擅髅芪膶?duì)，可以獲得對(duì)的加密結(jié)果，因?yàn)榇送猓軌颢@得的解密結(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)單