【正文】 Microsoft .Net Framework 使用 C 編程語(yǔ)言 （三）實(shí)驗(yàn)步驟 在引論中寫(xiě)了要實(shí)現(xiàn) RSA，必須先解決 大整數(shù)類的實(shí)現(xiàn) 、模冪運(yùn)算 的快速計(jì)算 以及 快速產(chǎn)生大素?cái)?shù) 這三個(gè)問(wèn)題。 （ 4）證明 由于 1mod( ( ))de n?? ，故存在整數(shù) k 滿足 ( ) 1de k n???。 選擇一個(gè)隨機(jī)數(shù) e ， 1 ( )en??? ，滿足 gcd( , ( )) 1en? ? ，并計(jì)算 1 m od( ( ))d e n??? 。 (6) 5. 公鑰： RSA 密碼體制 公鑰密碼體制的一個(gè)想法就是：也許能找到一個(gè)密碼體制，使得由給定的ek 來(lái)求 dk 是計(jì)算上不可行的。所以通常公鑰密碼只用于加密少量數(shù)字信息，通過(guò)公鑰加密傳輸對(duì)稱加密密鑰來(lái)加密文件。 （ 1）密鑰數(shù)量 對(duì)稱加密要求每一對(duì)用戶都有一個(gè)密鑰來(lái)保證 安全 通信?？勺C明安全性是計(jì)算安全的。符合這個(gè)要求的一次一密密碼體制因?yàn)槊荑€的分配問(wèn)題，往往并不實(shí)用。 3. 密碼系統(tǒng)的安全性 密碼系統(tǒng)的安全性由密碼算法的 安全性和密鑰管理的安全性組成，必須同時(shí)完善密碼算法以及密鑰管理才能保證密碼系統(tǒng)的安全。要防止的修改包括篡改、插入、刪除和重放。 2. 密碼學(xué) 的主要任務(wù) 經(jīng)典的密碼技術(shù)研究的是加密和解密的理論，然而現(xiàn)在的密碼學(xué)不再 局限于此，而是成為信息安全的重要組成部分，為存儲(chǔ)和傳輸中的數(shù)字信息提供如下幾個(gè)方面的安全保護(hù)。在公鑰密碼領(lǐng)域，橢圓曲線密碼體制由于其安全性高、計(jì)算速度快等優(yōu)點(diǎn)引起人們的普 遍關(guān)注和研究，并在公鑰密碼技術(shù)中取得重大進(jìn)展，成為公鑰密碼研究的新方向。 1976 年，美國(guó)斯坦福大學(xué)的注明密碼學(xué)迪菲（ W. Diffie）和赫爾曼（ M. Hellman）發(fā)表了“密碼學(xué)新方向”疑問(wèn)，首次提出了公鑰密碼體制的概念和設(shè)計(jì)思想，開(kāi)辟了公開(kāi)密鑰密碼學(xué)的新領(lǐng)域，掀起了公鑰密碼研究的序幕。密碼學(xué)專家常常通過(guò)經(jīng)驗(yàn)和技巧來(lái)設(shè)計(jì)加密算法（即轉(zhuǎn)輪機(jī)），而沒(méi)有形成系統(tǒng)的理論體系。 1895 年無(wú)線電誕生后，各國(guó)在通信，特別是軍事通信中普遍采用無(wú)線電技術(shù)。 這一時(shí)期的密碼技術(shù)僅是一門文字變換藝術(shù)，如上面所說(shuō)的置換密碼和替換密 碼。解密時(shí)，找一個(gè)同樣直徑的木棍纏繞上，就可以看到明文。 (5) （ 1） 古典密碼時(shí)期 這一時(shí)期從古代到 19 世紀(jì)末，長(zhǎng)達(dá)數(shù)千年。 在如今的信息時(shí)代，信息安全的重要性日益彰顯，密碼學(xué)作為信息安全的核心也受到各個(gè)機(jī)構(gòu)的重視。 接下來(lái)，我會(huì)參考各個(gè)相關(guān)文獻(xiàn)，找出辦法解決問(wèn)題，并實(shí)現(xiàn) RSA 算法。 2. 模冪運(yùn)算 modman的快速計(jì)算： RSA 的加密解密算法都需要大量的模 n指數(shù)運(yùn)算，而模 n 和指數(shù) m 都很大，所以模冪運(yùn)算的快速算法十分重要。 (2) 2020 年電子簽名法的施行 (3)，是中國(guó)信息化進(jìn)程發(fā)展的必然需求和有力保障，說(shuō)明了密碼學(xué)被公眾相信、使用，并被立法支持。如同我們寄信會(huì)把信紙放入信封并在封口簽名，以免他人獲知信件內(nèi)容以及在投遞過(guò)程中被更改丟失原意，使用密碼是為了保證信息的秘密性、不可更改性等。s theorem in elementary number theory. In order to ensure the security of encryption, when it es to industry, we often require the key pair is greater than 1Kbits. However, the integer class of puters occupies 32bits, which constitutes a contradiction. In addition, RSA39。在工業(yè)實(shí)現(xiàn)上，為了保證加密的安全性，通常要求密鑰對(duì)大于 1Kbits，然而計(jì)算機(jī)的整型變量為 32bits，這構(gòu)成一個(gè)矛盾。 I RSA 公鑰加密算法的設(shè)計(jì)與實(shí)現(xiàn) II RSA 公鑰加密算法的設(shè)計(jì)與實(shí)現(xiàn) 【論文摘要】 RSA公鑰加密算法是目前最有影響力的非對(duì)稱加密算法，為 ISO的推薦的加密標(biāo)準(zhǔn)。此外， RSA密鑰的生成需要產(chǎn)生隨機(jī)的大素?cái)?shù)，這也是本文需要解決的問(wèn)題。s keygeneration needs a random large prime number, which is also a problem to be solved. 【 Keywords】 RSA。 密碼學(xué)真正得到革新，是在計(jì)算機(jī)的廣泛傳播之后。電子簽名技術(shù)的實(shí)現(xiàn)需要用到非對(duì)稱算法和報(bào)文摘要，所以， RSA 作為公鑰加密的標(biāo)準(zhǔn)算法，值得我去學(xué)習(xí)、 研究和實(shí)現(xiàn)。 3. 快速產(chǎn)生大素?cái)?shù)： RSA 算法中每一個(gè)密鑰的產(chǎn)生需要兩個(gè)隨機(jī)的大素?cái)?shù)參與運(yùn)算，然而現(xiàn)在還沒(méi)有產(chǎn)生任意大素?cái)?shù)的有用技術(shù)。 中山大學(xué)本科生畢業(yè)論文 2 （二） 背景知識(shí) 在古代 戰(zhàn)爭(zhēng) 中，因?yàn)?需要的保密通信 ，密碼技術(shù)應(yīng)運(yùn)而生 。密碼技術(shù)不但可以保證信息的機(jī)密性，還有防篡改和數(shù)字簽名等功能。由于這個(gè)時(shí)期社會(huì)生產(chǎn)力底下，產(chǎn)生的許多密碼體制都是以“手工作業(yè)”的方式進(jìn)行，用紙筆或簡(jiǎn)單的器械實(shí)現(xiàn)加密和解密。這是最早的移位密碼（也稱換位密碼或置換密碼）。這樣的密碼研究和應(yīng)用遠(yuǎn)沒(méi)有形成一門科學(xué)，最多能稱為密碼術(shù)。由于無(wú)線電的廣播性，為了實(shí)現(xiàn)保密，各國(guó)隨即開(kāi)始研究無(wú)線電密碼的編制和破譯。 （ 3）近代密碼時(shí)期 1949 年香農(nóng)（ Claude Shannon）的奠基性論文“保密系統(tǒng)的通信理論”的發(fā)表，首次將信息論引入密碼技術(shù)的研究，用統(tǒng)計(jì)的觀點(diǎn)對(duì)信源、密碼源、秘聞進(jìn)行數(shù)學(xué)描述和定量分析，引入了不確定性、多余度、唯一解距離等安全性測(cè)度概念和計(jì)算方法，為現(xiàn)代密碼學(xué)研究與發(fā)展奠定了堅(jiān)實(shí)的理論基礎(chǔ)，把已有數(shù)千年歷史的密碼技術(shù)推向了科學(xué)的軌道，使密碼學(xué)成為一門真正的科學(xué)。受到他們的思想啟迪， Ron Rivest、 Adi Shamirh 和 Len Adleman 提出了第一個(gè)較完整的公鑰密碼體制 —— RSA 體制，成為公鑰密碼的杰出代表和實(shí)施標(biāo)準(zhǔn)，在密碼學(xué)歷史上是一個(gè)里程碑。在數(shù)字簽名方面，各種具有不同實(shí)際應(yīng)用背景的簽名方案，如盲簽名、群簽名、一次性簽名、不可否認(rèn)簽名等不斷出現(xiàn)。 （ 1） 機(jī)密性 即保證信息不被未授權(quán)的人獲得信息內(nèi)容。通過(guò)加密、報(bào)文摘要和數(shù)字簽名等實(shí)現(xiàn)。下面僅介紹密碼算法安全性的評(píng)價(jià)標(biāo)準(zhǔn)，通常由以下三種方法評(píng)估。 （ 2）計(jì)算安全性 即攻它破所需的計(jì)算量遠(yuǎn)大于攻擊者的計(jì)算資源（或者攻破所能獲得的利益），就可以定義這個(gè)密碼算法是安全的。 4. 對(duì)稱與非對(duì)稱密碼的區(qū)別 對(duì)稱密碼加密解密用的是同一個(gè)密鑰，而非對(duì)稱密碼卻是成對(duì)出現(xiàn)，一個(gè)用以加密，另一個(gè)用來(lái)解密。對(duì) n 個(gè)用戶，要保證 兩兩之間能夠安全通信，需要 2 * ( 1) / 2nC n n??個(gè)密鑰。 （ 3）系統(tǒng)開(kāi)放性 對(duì)稱密碼需要通信雙方有相同的密鑰才能進(jìn)行加密通信，這在雙方不認(rèn)識(shí)或者沒(méi)有安全的信道傳遞對(duì)稱密鑰的情況下，無(wú)法進(jìn)行加密通信。如果這樣的話，加密規(guī)則 ek 是一個(gè)公鑰，可以在一個(gè)目錄中公布（這也就是公鑰體制名稱的由來(lái)）。 公鑰為 (, )en ，私鑰為 d 。 故有 ( ) 1 1 ( 1 )( ) m ode d k n p k qm m m m m q? ? ? ?? ? ?。此外，計(jì)算 1 m od( ( ))d e n??? 需要用到 擴(kuò)展的歐幾里德算法 （ Extended Euclid）。 109=（ 1000） 3102410=230，占 30 位，以 4Bytes 的整型長(zhǎng)度存儲(chǔ)的話，空間利用率可達(dá) %?？焖倌邕\(yùn)算又稱快速冪取模，其原理是 m o d ( m o d ) ( m o d ) m o da b c a c b c c? 。 1) r = (r * a) % n。 } 3. 快速產(chǎn)生隨機(jī)素?cái)?shù) 如引論所說(shuō)，沒(méi)有方法直接產(chǎn)生一個(gè)素?cái)?shù)，通常的做法是產(chǎn)生一個(gè)隨機(jī)奇數(shù)，判斷是 否為素?cái)?shù)，產(chǎn)生一個(gè)隨機(jī)數(shù)恰好是素?cái)?shù)的概率是。 概率素?cái)?shù)測(cè)試算法的特點(diǎn)是：算法速度較快、原理簡(jiǎn)單、易于編程實(shí)現(xiàn)、有一定的誤判概率。概率算法的誤判完全可以被控制在一個(gè)極低的可接受的概率范圍內(nèi)，誤判概率在 80(1/2) 以下足以滿足絕大部分的安全需求。 Fermat 定理： n 是一個(gè)奇素?cái)?shù)， a 是任何整數(shù) (1 1)an? ? ? ，則 1 1(mod )nan? ? 。 MillerRabin 算法的誤判概率為 (1/4)t ，時(shí)間復(fù)雜度為 32(log ( ))On，其中 t 為測(cè)試次數(shù)。a b a x b yb a b b x a b y?? ?? 恒等變換得 39。 （四）代碼設(shè)計(jì) 1. 大整數(shù)類 在前文中已經(jīng)說(shuō)明了我的大整數(shù)類的數(shù)據(jù)結(jié)構(gòu)定為布爾型數(shù)組。類的數(shù)據(jù)結(jié)構(gòu)與字段如下： 圖 十進(jìn)制整數(shù)類 圖 二進(jìn)制整數(shù)類 字段 ，類名 Bigint 類中，用數(shù)組儲(chǔ)存大整數(shù)的絕對(duì)值，符號(hào)放在 sign 中，并用 length 表示長(zhǎng)度。并賦值 length 為 2。下面的私有函數(shù)用以輔助上面的函數(shù)實(shí)現(xiàn)，如 BinaryCheckZero 用于確定 body 的有效數(shù)位；BinaryDividestep 用于做除法運(yùn)算中的一步，即被除數(shù)頂位減除數(shù)。 圖 輸入與構(gòu)造函數(shù) 輸入主要是從 string 型到 Bigint 型，同樣用參數(shù) c 傳遞數(shù)據(jù)類型， d 為十進(jìn)制輸入， b 為二進(jìn)制輸入。而在實(shí)現(xiàn)隨機(jī)數(shù)產(chǎn)生、 MillerRabin 素?cái)?shù)測(cè)試等算法的時(shí)，發(fā)現(xiàn)直接對(duì)數(shù)組 body 進(jìn)行操作能大大提高代碼效率，故在 Bigint 類中添加了幾個(gè)完整的功能函數(shù)。 為了避免設(shè)置生成順序與