【正文】 s j Z? ? ? ?，等式 2 1(mod )jran?? 成立。 Fermat 定理： n 是一個(gè)奇素?cái)?shù)， a 是任何整數(shù) (1 1)an? ? ? ，則 1 1(mod )nan? ? 。 通過對(duì)比，選擇 MillerRabin 算法作為素?cái)?shù)測(cè)試算法。概率算法的誤判完全可以被控制在一個(gè)極低的可接受的概率范圍內(nèi)，誤判概率在 80(1/2) 以下足以滿足絕大部分的安全需求。目前最好的基于橢圓曲線的算法的時(shí)間復(fù)雜度是 6logn ?? ，基于割圓環(huán)的測(cè)試算法的時(shí)間復(fù)雜度是 loglogloglog n 。 概率素?cái)?shù)測(cè)試算法的特點(diǎn)是：算法速度較快、原理簡(jiǎn)單、易于編程實(shí)現(xiàn)、有一定的誤判概率。 由計(jì)算機(jī)函數(shù)產(chǎn)生的隨機(jī)數(shù)稱偽隨機(jī)數(shù)，有許多文章對(duì)偽隨機(jī)數(shù)的構(gòu)造原理、實(shí)現(xiàn)方法和效果（生產(chǎn)效率和隨機(jī)性）進(jìn)行了分析和研究，但由于 中有偽隨機(jī)數(shù)生成器 random()，所以不再重寫而是直接閱讀 MSDN (9)使用之。 } 3. 快速產(chǎn)生隨機(jī)素?cái)?shù) 如引論所說，沒有方法直接產(chǎn)生一個(gè)素?cái)?shù)，通常的做法是產(chǎn)生一個(gè)隨機(jī)奇數(shù)，判斷是 否為素?cái)?shù)，產(chǎn)生一個(gè)隨機(jī)數(shù)恰好是素?cái)?shù)的概率是。 b = 1。 1) r = (r * a) % n。 因此可以分解計(jì)算，有快速算法： int exp_mod(int a, int b, int n) { int r = 1?？焖倌邕\(yùn)算又稱快速冪取模，其原理是 m o d ( m o d ) ( m o d ) m o da b c a c b c c? 。 中山大學(xué)本科生畢業(yè)論文 9 然而，為了模冪運(yùn)算的效率，最終決定以 2 為基，用 bool 型數(shù)組而不是 int型，并重載加、減、乘、除、求余、相等、不等、大于、小于等運(yùn)算符。 109=（ 1000） 3102410=230，占 30 位，以 4Bytes 的整型長(zhǎng)度存儲(chǔ)的話，空間利用率可達(dá) %。如 C 中的 Unsigned long 型整數(shù)能處理整數(shù)值 4294967295（ 2321），占據(jù) 32bits 存儲(chǔ)空間，此時(shí)，大整數(shù)就是指大于 4294967295 的十位以上的整數(shù)。此外，計(jì)算 1 m od( ( ))d e n??? 需要用到 擴(kuò)展的歐幾里德算法 （ Extended Euclid）。同樣可以推出 ( ) 1 m oded k nm m m q? ??? 故有 中山大學(xué)本科生畢業(yè)論文 8 ( ) 1 m o dd ed k nc m m m n? ?? ? ? 二、實(shí)驗(yàn)部分 （一） 實(shí)驗(yàn) 目的 通過對(duì) RSA 的研究和實(shí)現(xiàn)，學(xué)習(xí) RSA 的數(shù)學(xué)基礎(chǔ)、掌握 RSA 加密的原理和方法、鞏固計(jì)算機(jī)編程能力。 故有 ( ) 1 1 ( 1 )( ) m ode d k n p k qm m m m m q? ? ? ?? ? ?。 （ 3）解密 對(duì)密文 c ，其對(duì)應(yīng)明文為 moddm c n? 。 公鑰為 (, )en ，私鑰為 d 。 (4) 中山大學(xué)本科生畢業(yè)論文 7 （ 1）密鑰生成 選擇兩個(gè)隨機(jī)大素?cái)?shù) p 和 q，并計(jì)算 n pq? 和 ( ) ( 1)( 1)n p q? ? ? ?。如果這樣的話，加密規(guī)則 ek 是一個(gè)公鑰，可以在一個(gè)目錄中公布（這也就是公鑰體制名稱的由來(lái)）。 （ 4）數(shù)字簽名 數(shù)字簽名（ Digital Signature）技術(shù)是不對(duì)稱加密算法的典型應(yīng)用。 （ 3）系統(tǒng)開放性 對(duì)稱密碼需要通信雙方有相同的密鑰才能進(jìn)行加密通信，這在雙方不認(rèn)識(shí)或者沒有安全的信道傳遞對(duì)稱密鑰的情況下，無(wú)法進(jìn)行加密通信。 （ 2）效率 由于非對(duì)稱加密通?；谀承?shù)學(xué)難題，通常來(lái)自于數(shù)論，這些問題的底層涉及到大量模冪運(yùn)算，相對(duì)于對(duì)稱密碼需要更多的計(jì)算資源。對(duì) n 個(gè)用戶，要保證 兩兩之間能夠安全通信，需要 2 * ( 1) / 2nC n n??個(gè)密鑰。因此，非對(duì)稱密碼又稱為公鑰密碼。 4. 對(duì)稱與非對(duì)稱密碼的區(qū)別 對(duì)稱密碼加密解密用的是同一個(gè)密鑰，而非對(duì)稱密碼卻是成對(duì)出現(xiàn)，一個(gè)用以加密，另一個(gè)用來(lái)解密。 （ 3）可證明安全性 即可以把密碼體制的安全性歸結(jié)為某個(gè)數(shù)學(xué)難題，而這個(gè)數(shù)學(xué)難題（如大整數(shù)分解）被證明是求解困難的。 （ 2）計(jì)算安全性 即攻它破所需的計(jì)算量遠(yuǎn)大于攻擊者的計(jì)算資源（或者攻破所能獲得的利益），就可以定義這個(gè)密碼算法是安全的。也就是說攻擊者在觀察密文前后，密鑰的不確定性沒有改變，這要求有跟消息一樣長(zhǎng)的隨機(jī)密鑰。下面僅介紹密碼算法安全性的評(píng)價(jià)標(biāo)準(zhǔn)，通常由以下三種方法評(píng)估。 中山大學(xué)本科生畢業(yè)論文 5 （ 4）抗抵賴性 即通信實(shí)體不能否認(rèn)之前的通信行為，包括發(fā)送過的信息以及收到的信息。通過加密、報(bào)文摘要和數(shù)字簽名等實(shí)現(xiàn)。 （ 2）數(shù)據(jù)完整性 即保證信息被使用時(shí)的內(nèi)容，跟它被制作出來(lái)時(shí)一致。 （ 1） 機(jī)密性 即保證信息不被未授權(quán)的人獲得信息內(nèi)容。美國(guó)、德國(guó)、日本和我國(guó)等許多國(guó)家已經(jīng)頒布了數(shù)字簽名法，使數(shù)字簽名在電子商務(wù)和電子政務(wù)等領(lǐng)域得到了法律的認(rèn)可，推動(dòng)了密碼學(xué)研究和應(yīng)用的發(fā)展。在數(shù)字簽名方面，各種具有不同實(shí)際應(yīng)用背景的簽名方案，如盲簽名、群簽名、一次性簽名、不可否認(rèn)簽名等不斷出現(xiàn)。如，過去普遍認(rèn)為有足夠安全性的 DES 密碼算法，在新的技術(shù)和分析方法前，被證明是不夠安全的，因此又確定了新的加密標(biāo)準(zhǔn) AES（ Advanced Encryption Standard，高級(jí)加密算法）。受到他們的思想啟迪， Ron Rivest、 Adi Shamirh 和 Len Adleman 提出了第一個(gè)較完整的公鑰密碼體制 —— RSA 體制，成為公鑰密碼的杰出代表和實(shí)施標(biāo)準(zhǔn)，在密碼學(xué)歷史上是一個(gè)里程碑。更具有重要意義的是 DES 密碼開創(chuàng)了公開全部密碼算法的先例，大大推動(dòng)了分組密碼理論的發(fā)展和技術(shù)應(yīng)用。 （ 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é)。 近代密碼時(shí)期可以看作是科學(xué)密碼學(xué)的前夜，這階段的密碼技術(shù)是一種技 巧和經(jīng)驗(yàn)的結(jié)合體，還不是一門科學(xué)。由于無(wú)線電的廣播性，為了實(shí)現(xiàn)保密，各國(guó)隨即開始研究無(wú)線電密碼的編制和破譯。這個(gè)時(shí)期的加密解密主要是用機(jī)電設(shè)備來(lái)實(shí)現(xiàn)的。這樣的密碼研究和應(yīng)用遠(yuǎn)沒有形成一門科學(xué)，最多能稱為密碼術(shù)。這種密碼的實(shí)現(xiàn)方式是把信中每個(gè)文字的字母都按字母順序表中相隔兩位后的一個(gè)字母取代。這是最早的移位密碼（也稱換位密碼或置換密碼）?！疤鞎笔峭ㄟ^把一個(gè)帶狀物如羊皮帶，成螺旋狀緊緊地纏繞在一根權(quán)杖或者木棍上，然后再沿著縱向書寫信息，展開后就成為無(wú)意義的點(diǎn)線。由于這個(gè)時(shí)期社會(huì)生產(chǎn)力底下，產(chǎn)生的許多密碼體制都是以“手工作業(yè)”的方式進(jìn)行，用紙筆或簡(jiǎn)單的器械實(shí)現(xiàn)加密和解密。 1. 密碼技術(shù)的發(fā)展 根據(jù)加密解密手段 和器械 的不同，密碼技術(shù)的發(fā)展歷史大致可以劃分古典密碼、近代密碼和現(xiàn)代密碼時(shí)期 這三個(gè)時(shí)期 。密碼技術(shù)不但可以保證信息的機(jī)密性，還有防篡改和數(shù)字簽名等功能。 然而隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)通信技術(shù)的發(fā)展，越來(lái)越多的電子政務(wù)、電子商務(wù)普遍需求安全通信，密碼技術(shù)才從軍用走向商用民用，并得到更加迅速的發(fā)展。 中山大學(xué)本科生畢業(yè)論文 2 （二） 背景知識(shí) 在古代 戰(zhàn)爭(zhēng) 中，因?yàn)?需要的保密通信 ，密碼技術(shù)應(yīng)運(yùn)而生 。因此驗(yàn)證素?cái)?shù)的算法速度也十分 重要。 3. 快速產(chǎn)生大素?cái)?shù)： RSA 算法中每一個(gè)密鑰的產(chǎn)生需要兩個(gè)隨機(jī)的大素?cái)?shù)參與運(yùn)算，然而現(xiàn)在還沒有產(chǎn)生任意大素?cái)?shù)的有用技術(shù)。為了有效地實(shí)現(xiàn) RSA 密碼體制，必須解決如下三個(gè)問題： (4) 1. 大整數(shù)類的實(shí)現(xiàn)：計(jì)算機(jī)中 ，通常 的 編程語(yǔ)言的長(zhǎng)整型 是 64bits 的，而計(jì)算安全的 RSA 要求密鑰長(zhǎng)度長(zhǎng)達(dá) 1024bits 或以上，故要設(shè)計(jì)出一個(gè)無(wú)限大（大于 10000bits）的整數(shù)類， 并重載各種初等運(yùn)算 。電子簽名技術(shù)的實(shí)現(xiàn)需要用到非對(duì)稱算法和報(bào)文摘要，所以， RSA 作為公鑰加密的標(biāo)準(zhǔn)算法，值得我去學(xué)習(xí)、 研究和實(shí)現(xiàn)。同年， RSA 公鑰加密算法由 Ron Rivest、 Adi Shamirh 和 Len Adleman 在美國(guó)麻省理工學(xué)院開發(fā)，是目前最有影響力的公鑰加密算法， 現(xiàn)已 被 ISO 推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。 密碼學(xué)真正得到革新，是在計(jì)算機(jī)的廣泛傳播之后。 prime number III 目錄 RSA 公鑰加密算法的設(shè)計(jì)與實(shí)現(xiàn) ...................... II The design and implementation of RSA public key encryption algorithm............................................. II 目錄 ............................................. III 一．前言 ............................................ 1 （一）引論 .............................................................................. 1 （二）背景知識(shí) ...................................................................