【正文】 7 第 3 章 RSA 的數(shù)學原理及其算法實現(xiàn) RSA 的數(shù)學原理 RSA 算法 基于下面的兩個事實，保證 RSA 算法的安全有效性： 1）已有確定一個數(shù)是不是素數(shù)的快速算法； 2）尚未找到確定一個合數(shù)的質(zhì)因子的快速算法： RSA 算法的工作原理 （ 1） 任意選取兩個不同的大質(zhì)數(shù) p 和 q ，計算乘積 qpn ?? ， )1()1()( ???? qpn? ； （ 2） 任意選取一個大整數(shù) e ， e 與 )1()1( ??? qp 互素，整數(shù) e 用做加密密鑰，（注意：e 的選取是很容易的，例如，所有大于 p 和 q 的質(zhì)數(shù)都可用） （ 3） 確定解密密鑰 d ： )1)(1m od(1 ???? qped ，根據(jù) e ， p ， q ，可以容易的計算出 d ； （ 4） 公開整數(shù) n 和 e ，將 d 保密； （ 5） 將明文 p （假設 p 是一個小于 n 的整數(shù)）加密為密文 c ，計算方法為： npc e mod? （ 6） 將密文 c 解密為明文 p，計算方法為： ncp d mod? 然而，只根據(jù) n 和 e （不是 p 和 q ），要計算出 d 是不可能的，因此，任何人都可以對明文進行加密，但只有授權用戶（知道 d ）才可以對密文進行解密。因此 )(21 , naxaxax ?? 構成 )(n? 個與 n 互素的數(shù)，且兩兩不同余。 費馬定理和歐拉定理 定理 ：（費馬 小 定理 ）若 p 是素數(shù)， ap|? ，則 pa p mod11 ?? . 費馬定理的等價形式： paap mod? . 定義 ：設 n 為正整數(shù)，歐拉函數(shù) )(n? 定義為滿足條件： nb??0 且 1),( ?nb 的整數(shù) b 的個數(shù)。 記作 ),( bad? ，如果 1),(, ?? baZba ，則稱 a 和 b 互素。 定理 ：（帶余除法）設 0, ?? bZba ，則存在唯一確定的整數(shù) q 和 r ，使得： rqba ?? ， br??0 定義 ： 設 ba, 是不全為 0 的整數(shù)， a 和 b 的最大公因數(shù) 是指滿足 下述條件的整數(shù)d ， （ 1） d 為 a 和 b 的公因數(shù)，即 ad| ，且 bd| 。第 2 章 相關數(shù)論知識 4 第 2 章 相關數(shù)論知識 整除與互素 定義 ：設 a 為 b 是整數(shù)， 0?b ，如果存在 Zc? ，使得 bca? ，則稱 b 整除 a ，記為 ab| ，并且稱 b 是 a 的一個因子，而 a 為 b 的倍數(shù)，若不存在 Zc? 使得 bca? ，則稱 b 不整除 a ，記作 ab|? 。 （ 4）不可抵賴性： 發(fā)送者無法 事后否認其發(fā)送過消息，消息的接收者可以像中立的第三方 CA 證實所指的發(fā)送者確實發(fā)出了消息。 （ 2）數(shù)據(jù)完整性：保證 通信中的信息不會被非法篡改，入侵者不能利用其他假消息替換原始消息。 RSA 的簡介 RSA 是目前最為流行的公鑰密碼體制之 一 ，其安全性是基于分解大素數(shù)的困難性，由于其加密函數(shù)是一個單向函數(shù)，所以對第三方而言，試圖在有效的時間內(nèi)在計算四川理工學院畢業(yè)論文 3 機上非法解密密文是不可能的 。例如，甲將他的加密 密鑰公開，任何想與甲通信的都可以采用這個加密密鑰把要傳送的信息（明文）加密成密文發(fā)送給甲，只有甲知道解密密鑰，能夠將密文還原為明文，而任何第三方即使截獲到密文也不能知道密文所傳遞的信息。此外，在一些需要驗證消息的真實性和消息發(fā)送方身份的場合，或在進行電子交易時 ，必須有手寫簽名的數(shù)字形式即數(shù)字簽名來確認身份，這是對稱密碼無法實現(xiàn)的。很久以來，密鑰分發(fā)的問題一直困擾著密碼專家，隨著計算機網(wǎng)絡的逐漸擴大，密鑰分配所造成的時間延遲和費用問題日益凸顯出來。 對稱密鑰體制的加密密鑰和解密密鑰是相同的，只要知道加密密鑰，就能推出解密密鑰，通信雙方分別持有加密密鑰和解密密鑰，需要定期更新密鑰。 密 碼技術是密碼學的重要內(nèi)容，它是集數(shù)學，計算機科學，電子與通信等諸多學科于一身的的交叉學科，它不僅 能夠保證機密信息的加密，而且能夠實現(xiàn) 數(shù)字簽名，身份驗證，系統(tǒng)安全等功能 。 由于時間關系，再加上筆者的能力有限，本文中尚有許多不足之處，敬請讀者批評指正。對其數(shù)學原理進行了簡單的說明， 詳細介紹了其具體算法。 本文較為詳細的介紹了密碼體制的相關內(nèi)容， 包括 RSA 的主要應用及其在計算機網(wǎng)絡中的重要性。 關鍵詞 ： RSA 公鑰密碼體制 加密 解密 MATLAB 安全性 ABSTRACT RSA is an algorithm which can be used for both encryption and digital signature. It is easy to understand as well as to operate, and has an upper security which makes it popular. This paper firstly delivers information on the basic purpose, the mathematic principle and the specific arithmetic of RSA. Then it presents an implementation of RSA on the application software MATLAB. After that, this article also analyzes the security of RSA, including its potential leaks, parameter options, which helps us to know further of RSA. Keywords : RSA public key cryptography encryption decrypt MATLAB security 目 錄 前 言 .......................................................................................................................................... 1 第 1 章 RSA 簡介 ........................................................................................................................ 2 密碼體制簡介 ...................................................................................................................... 2 RSA 的簡介 .......................................................................................................................... 2 第 2 章 相關數(shù)論知識 ................................................................................................................. 4 整除與互素 ..................................................................................