【正文】 圖表整潔，布局合理，文字注釋必須使用工程字書寫，不準(zhǔn)用徒手畫 3）畢業(yè)論文須用 A4 單面打印，論文 50 頁以上的雙面打印 4）圖表應(yīng)繪制于無格子的頁面上 5）軟件工程類課題應(yīng)有程序清單，并提供電子文檔 1）設(shè)計(jì)（論文） 2）附件：按照任務(wù)書、開題報(bào)告、外文譯文、譯文原文（復(fù)印件）次序裝訂 3）其它 。 ：任務(wù)書、開題報(bào)告、外文譯文、譯文原文（復(fù)印件）。 涉密論文按學(xué)校規(guī)定處理。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。 作者簽名： 日 期： 中山大學(xué)本科生畢業(yè)論文 29 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。對(duì)本研究提供過幫助和做出過貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說明并表示了謝意。 中山大學(xué)本科生畢業(yè)論文 28 畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文），是我個(gè)人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。 隨著這篇本科畢業(yè)論文的最后落筆，我四年的大學(xué)生活也即將劃上一個(gè)圓滿的句號(hào)。 在本文的撰寫過程中，譚軍老師作為我的指導(dǎo)老師，他學(xué)識(shí)淵博，不但教我掌握了通用的研究方法，還讓我明白了許多待人接物與為人處世的道理。感謝所有在畢業(yè)設(shè)計(jì)中曾經(jīng)幫助過我的良師益友和同學(xué)，以及在設(shè)計(jì)中被我引用或參考的論著的作者。授人以魚不如授人以漁，置身其間，耳濡目染，潛移默化，使我不僅接受了全新的思想觀念，樹立了宏偉的學(xué)術(shù)目標(biāo)，學(xué)會(huì)了不同的思考方式。這時(shí)候，才突然這么深刻地發(fā)現(xiàn)自己對(duì)這個(gè)學(xué)校的熱愛。但較為遺憾的是，由于時(shí)間的緣故，許多函數(shù)需要進(jìn)行效率上的優(yōu)化，某些地方可能有錯(cuò)漏，甚至可能要有較大的調(diào)整才能作為工業(yè)實(shí)現(xiàn)應(yīng)用。在邊學(xué)邊寫的模式下，這個(gè)程序耗費(fèi)我近一個(gè)月的時(shí)間，超過 900 行近 20200 字符，完成了滿足需求的大整數(shù)類，實(shí)現(xiàn)了 RSA 公鑰加密算法的實(shí)際應(yīng)用。此外，選取一個(gè)隨機(jī)奇數(shù)，這個(gè)數(shù)恰好是素?cái)?shù)的概率為 2/lnn 。 表 各個(gè)保密級(jí)別密鑰長(zhǎng)度 中山大學(xué)本科生畢業(yè)論文 24 保密級(jí)別 對(duì)稱密鑰長(zhǎng)度（ bits） RSA密鑰長(zhǎng)度（ bits） ECC 密鑰長(zhǎng)度（ bits） 保密年限 80 80 1024 160 2020 112 112 2048 224 2030 128 128 3072 256 2040 192 192 7680 384 2080 256 256 15360 512 2120 （ 3）密鑰產(chǎn)生困難 RSA 密鑰的產(chǎn)生受限于素?cái)?shù)產(chǎn)生技術(shù)，而素?cái)?shù)的產(chǎn)生效率取決于素?cái)?shù)判定算法的效率。目前， SET（ Secure Electronic Transaction）協(xié)議中要求 CA（ Certification Authority）采用 2048bits 長(zhǎng)的密鑰，其他實(shí)體使用 1024bits 的密鑰。 （ 1） 密鑰長(zhǎng)度大 為了保證安全性，模數(shù) n 至少要 600bits 以上，這使得運(yùn)算代價(jià)很高，速度較對(duì)稱加密算法慢幾個(gè)數(shù)量級(jí)。為了達(dá)到這個(gè)目的，給程序加上一個(gè)時(shí)間變量，并進(jìn)行 10 次運(yùn)算，測(cè)試 10 次密鑰產(chǎn)生的平均時(shí)長(zhǎng)。 2. RSA 效率 RSA 算法的效率比起對(duì)稱加密算法十分低，這個(gè)粗糙的程序更是遠(yuǎn)遠(yuǎn)達(dá)不到工業(yè)水平，不過這不妨礙我通過完成這個(gè)程序達(dá)到學(xué)習(xí)加密算法的目的。設(shè) M 為信息明文，加密密鑰分別為 12,ee， 1212modmodeeC M nC M n?? 攻擊者知道 1 2 1 2, , , ,n e e C C ，就可以計(jì)算出 M 。 （ 1）選擇密文攻擊 攻擊者將信息作了偽裝讓擁有私鑰的實(shí)體簽署，然后通過計(jì)算可以得到它想中山大學(xué)本科生畢業(yè)論文 22 要的信息，這是利用了一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)， ( ) * ( m od )d d dX M X M n? 這個(gè)問題來自于公鑰密碼系統(tǒng)中最有用的特征 —— 每個(gè)人都能使用公鑰，因而無法從算法上解決這個(gè)問題，只能在管理上保證不能隨意對(duì)不知來源的信息簽名，并最好使用單向加密作 HASH 處理等。因此，模數(shù) n 必須選大一些，因具體使用情況而定。不管怎樣，分解 n 是最顯然的攻擊方法。假設(shè)存在一種無須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。然而， RSA 算法卻有一些比較明顯的弱點(diǎn)。 2. RSA 密鑰產(chǎn)生 點(diǎn)擊 中山大學(xué)本科生畢業(yè)論文 19 （ 1）模數(shù) N 產(chǎn)生 點(diǎn)擊 （ 2） 密鑰產(chǎn)生 點(diǎn)擊 中山大學(xué)本科生畢業(yè)論文 20 3. 加密解密 展示 （ 1）加密 鍵入 202005，點(diǎn)擊 （ 2）解密 點(diǎn)擊 中山大學(xué)本科生畢業(yè)論文 21 （二） RSA 分析 RSA 算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作，是被研究得最廣泛的公鑰算法。按鈕功能如下： ：展示當(dāng)前 RSA 字段； ：重新生成模數(shù) N 以及密鑰； ：在當(dāng)前 N 的基礎(chǔ)上生成新密鑰； ：把輸入框 1 中的整數(shù)用當(dāng)前 RSA 加密； ：把輸入框 2 中的整數(shù)用當(dāng)前 RSA 解密； 1mi2mod3：輸入框 1 為 a ，輸入框 2 為 b ，輸入框 3 為 c ，計(jì)算 modbac； ：返回輸入框 3 是否為素?cái)?shù)； 1gcd2：求出輸入框 1 與輸入框 2 的公約數(shù)。 （ 1）快速模冪運(yùn)算 中山大學(xué)本科生畢業(yè)論文 17 （ 2） MillerRabin 素?cái)?shù)測(cè)試 （ 3）擴(kuò)展的歐幾里德算法 其中， (b)出現(xiàn)的原因是“ %”的重載會(huì)修改兩個(gè)參數(shù)的值，這個(gè)可以通過改進(jìn)“ %”算法修正。 圖 常數(shù)聲明 這兩個(gè)長(zhǎng)度都是指二進(jìn)制隨機(jī)數(shù)產(chǎn)生時(shí)的位數(shù)。 圖 輔助函數(shù) 創(chuàng)建了一個(gè)結(jié)構(gòu) ExtendedEuclidReturn 用于返回?cái)U(kuò)展的歐幾里德算法解值； ExtendedEuclid()是擴(kuò)展的歐幾里德函數(shù)； PrimeEngineer()是素?cái)?shù)產(chǎn)生函數(shù)。 圖 生成函數(shù) 前兩個(gè)函數(shù)分別是產(chǎn)生 n 的函數(shù)和產(chǎn)生 (, )ed 的。 圖 字段 其中， PrimeA 是素?cái)?shù) p ； PrimeB 是素?cái)?shù) q ； N 是素?cái)?shù)積 n pq? ； MultiPrime是產(chǎn)生密鑰的中間變量 ( ) ( 1)( 1)n p q? ? ? ?； EnCodekey 是加密密鑰 e ； DeCodekey是解密密鑰 d 。 為了避免設(shè)置生成順序與引用的麻煩，把 Bigint 類改為 public 類型，方便下面 Rsa 類對(duì)其的引用。 類里還有幾個(gè)常數(shù)聲明或者只讀變量。而在實(shí)現(xiàn)隨機(jī)數(shù)產(chǎn)生、 MillerRabin 素?cái)?shù)測(cè)試等算法的時(shí)，發(fā)現(xiàn)直接對(duì)數(shù)組 body 進(jìn)行操作能大大提高代碼效率，故在 Bigint 類中添加了幾個(gè)完整的功能函數(shù)。靜態(tài)構(gòu)造函數(shù)是設(shè)定一個(gè)全文的隨機(jī)種子。 圖 輸入與構(gòu)造函數(shù) 輸入主要是從 string 型到 Bigint 型，同樣用參數(shù) c 傳遞數(shù)據(jù)類型， d 為十進(jìn)制輸入， b 為二進(jìn)制輸入。 圖 進(jìn)制轉(zhuǎn)換 中山大學(xué)本科生畢業(yè)論文 13 十進(jìn)制到二進(jìn)制的轉(zhuǎn)換是通過一般的“除 2 取余，逆序排列” (11)方式，但二進(jìn)制轉(zhuǎn)十進(jìn)制卻不是用通常的“按權(quán)相加”法，而是“乘 2 加 1”的方法。下面的私有函數(shù)用以輔助上面的函數(shù)實(shí)現(xiàn)，如 BinaryCheckZero 用于確定 body 的有效數(shù)位；BinaryDividestep 用于做除法運(yùn)算中的一步，即被除數(shù)頂位減除數(shù)。 圖 大整數(shù)類運(yùn)算符重載 其中包括一個(gè)從 int 型到 Bigint 型的隱式轉(zhuǎn)換函數(shù)，可以在進(jìn)行 Bigint 型與int 型值進(jìn)行運(yùn)算時(shí)節(jié)約代碼。并賦值 length 為 2。大整數(shù)絕對(duì)值在 bool 數(shù)組中的儲(chǔ)存方式是，把大整數(shù)二進(jìn)制化，低位放在數(shù)組低位，高位在數(shù)組高位。類的數(shù)據(jù)結(jié)構(gòu)與字段如下： 圖 十進(jìn)制整數(shù)類 圖 二進(jìn)制整數(shù)類 字段 ，類名 Bigint 類中，用數(shù)組儲(chǔ)存大整數(shù)的絕對(duì)值，符號(hào)放在 sign 中，并用 length 表示長(zhǎng)度。這樣的類可以靈活處理數(shù)據(jù)，比如錄入一個(gè)十進(jìn)制數(shù)，和另外一個(gè)十進(jìn)制數(shù)相加再輸出時(shí)，可以直接調(diào)用兩個(gè)十進(jìn)制數(shù)相加的函數(shù)，并直接輸出，節(jié)約了三次進(jìn)制轉(zhuǎn)換。 （四）代碼設(shè)計(jì) 1. 大整數(shù)類 在前文中已經(jīng)說明了我的大整數(shù)類的數(shù)據(jù)結(jié)構(gòu)定為布爾型數(shù)組。 ( / ) 39。a b a x b yb a b b x a b y?? ?? 恒等變換得 39。 其實(shí)現(xiàn)方法是在進(jìn)行輾轉(zhuǎn)相除法時(shí)，因?yàn)? 中山大學(xué)本科生畢業(yè)論文 11 g c d ( , )g c d ( , m o d ) 39。 MillerRabin 算法的誤判概率為 (1/4)t ，時(shí)間復(fù)雜度為 32(log ( ))On，其中 t 為測(cè)試次數(shù)。 MillerRabin 算法的理論基礎(chǔ)：如果 n 是一個(gè)奇素?cái)?shù)，將 1n? 表示為 2*s r 的形式（ r 是奇數(shù)）， a 是和 n 互素的任何整數(shù)，那么 1(mod )ran? 或者對(duì)某個(gè)j (0 1, )j