畢業設計-rsa公鑰密碼算法的一種快速實現—論文(編輯修改稿)

　

【文章內容簡介】 y=2 令 y=2 代入（ 1）得 x=9 x=9。y=2 即為所求。 程序中，函數 Euc(CBigIntamp。 A)。用來完成這種算法。對應前面的敘述，參數 a 對應 A，函數返回值即為 X 的最小值。 ⑸ .文件操作 本工程的核心是利用蒙哥馬利算法快速實現 RSA 加密，為了便于研究對字符串的加密過程，以及記錄字 符串的密文樣本，程序把字符串寫入 TXT文檔，再進行加密解密操作，這樣就需要對文件進行操作，以二進制數據流對文件進行讀出寫入操作。在這里使用一個 CFILE 類，使用 CFILE 類對文件進行簡單的讀寫操作十分方便，本工程以一個 char 型的指針 data 來存放獲得的字符串，用 DWORD型變量 flen 來存放 Cfile 類中成員函數 GetLength()獲得的字符串長度，然后直接使用成員函數 read(),write()來進行文件的讀寫操作。 文件的讀寫操作代碼見附。 ⑹ . 按常規 RSA 算法實現加密與解密 最后，類 CDemoDlg 基于前面的準備工作，實現 RSA 密鑰生成和加解密的界面化功能。（界面代碼多由 C++編譯器自動生成，在此不再贅述）在類 CDemoDlg的構造函數里，執行準備一對隨機密鑰的操作。之后可以直接使用類的其他成員進行 RSA 加解密操作，也可以載入用戶寫入的密鑰或再次隨機生成密鑰。類中各成員頻繁的用到字符串和 vlong 類型的轉換，因為大數是用字符串置入的，而把大數讀出，也是保存在字符指針指向的一段內存空間里，所以也是字符串。所以，需要實現一系列的編碼轉換函數，比如將 unsigned 指針指向的一段空間里保存的一個大數，表 示成十六進制形式的字符串文本。編碼轉換通常是用 C風格的指針操作。 由于是對文件進行加密，所以涉及對文件內容進行讀寫操作，這里使用到了CFile 類。需要加密和解密的數據是通過字符串參數置入的。由于字符串的結尾字符“ \0”實際上也可能是需要加密的數據，所以置入的串長度并不能以“ \0”來決定，程序里引入一個 unsigned 類型的參數來決定置入的串長度，通過 Cfile 類中的 Getlength()函數獲得文件中字符串的長度，這樣就解決了加密連 \0數據時候被截斷的問題。 加密解密流程均為標準 RSA 算法，具體過程和使用方 法參見源程序和接口文檔。 ⑺ . 核心類庫綜述 綜上幾小節所述，實現 RSA 加密算法的 C++核心類庫由兩個類組成，類名和對應的功能描述總結如表 21 和圖 22 所示。 表 21： RSA加密算法的 C++類庫中的類 CBigInt 主要包含大數四則運算，素數生成，檢測，密鑰生成，存儲， RSA 核心算法等。 CDemoDlg 主要包含界面功能的實現，按鈕觸發時間等。 圖 22：主要函數成員 編寫測試各項性能需要的計時程序 由于對幾個字符的字符串進行 RSA 加密，所用時間只需 10 幾毫秒，一般的程序計時函數無法達到要求測試結果很可能是 0，于是在這里定義了 2 個 long型變量 t1,t2 來分別存儲加密函數運行前后 GetTickCount()函數獲得的系統時間 ,然后將兩個值相減獲得消耗時間，這樣做還會有較大誤差，于是再次進行了改進，通過一個簡單的 for循環讓程序運行 1000 次 ，然后將 t2t1 的值除 1000， 以獲得較為精確的時間。 附錄中給出了這段操作的源代碼。 測試數據與分析改進 密鑰生成測試 生成密鑰運算最費時的工作是尋找素數。如 小節所敘述，尋找素數是一項頗為復雜的工作，其速度可能受以下影響： RSA加密需要的 n的位數（尋找素數的整數起點大小 bits），素數通過小素數表進行檢查，通過拉賓米勒算法測試素數。其中最具影響力的因素顯然是 RSA 加密需要的 n 的位數。以下對 N的位數對生成密鑰時間影響進行測試，暫且忽略操作系統調度對測試的影響。測試 PC 配置為 CPU 奔騰 4 845 UltraAD 芯片組，下文測試中，未說明 PC 配置的也都在同一 PC 完成，不再重復。 密鑰生成測試數據見表 31。 表 31： RSA加密模數 n與密鑰生成耗時的關系 加密位數 n (bit) 第一次 （毫秒） 第二次（毫秒） 第三次（毫秒） 第四次（毫秒） 第五次（毫秒） 平均值（毫秒） 128 22 20 21 21 21 21 256 126 125 118 131 130 126 512 844 875 812 935 770 847 1024 7030 3205 4785 3926 6399 5069 （紅色為行中最大，蘭色為行中最小） 觀察表上的統計數據，很容易發現隨著加密位數的增加，密鑰生成需要的時間顯 著增加。在測試范圍內，隨著加密位數增大，每一行中的最大最小值差距也呈粗略的增大趨勢。也就是說對于長密鑰來說， RSA 隨機生成密鑰消耗時間的可能范圍較大。這是因為對于大整數來說，可能出現在較長一段區間中沒有素數的情況。 此表僅能從實驗的角度直觀理解，具體到一次密鑰生成的運算，所需要的時間是很不確定的，比如，一次 512 位的密鑰生成，需要的時間完全可能比一次256 位的密鑰生成時間短，由于素數分布規律非常奧妙，加上測試運算需要的時間頗長，這里很難給出對于一個具體位數的密鑰生成所需時間的統計模型。 加解密測 試 加密解密測試是本工程的核心，重在反映 RSA算法對小型文本文件加密的可行性，以及蒙哥馬利算法對 RSA 算法的提速效果。這里給出幾組不同角度進行測 試的數據。 ⑴ .用相同的密鑰對不同長度的文件公鑰加密，私鑰解密，各自消耗的時間與待加密字符串大小的關系 隨即生成兩組密鑰，一組 n 長 512bit，一組 n 長 1024bit。密鑰具體數據見附錄。 分別對一組不同大小的文件進行公鑰加密。統計消耗時間情況如表 32： 表 32：加密消耗時間測試 n 位數 文件大小 20Byte（毫秒） 40Byte 60Byte 80Byte 100Byte 512bit公鑰加密 119 123 125 128 138 512bit私鑰解密 330 453 473 503 508 1024bit 公鑰加密 442 464 469 473 479 1024bit 私鑰解密 681 721 721 741 743 從表 3可以看出，使用同一公開密鑰加密不同大小的文件，消耗時間隨著文件大小的增加線性的增加，和 小節分析的完全一致。對于較大的文件，加密位數對時間的影響十分明顯。對于 100 字節的文件來說， 1024bit 的公鑰加密比 512bit 的耗時多 倍左右； 1024bit 的私鑰解密比 512bit 的耗時多 以上。對于一定的加密位數來說，私鑰解密所需要的時間比公鑰加密需要的時間長。對于一定大小的文件，使用 512bit 的密鑰，私有密鑰解密需要的時間是公開密鑰加密需要時間的 3倍左右；而如果使用 1024bit 的密鑰，私有密鑰解密需要的時間是公開密鑰加密需要時間的 倍以上。可見，本軟件密鑰長度越長，私有密鑰解密與公開密鑰加密的耗時比越大，這和其他軟件是一致的。因為根據PCKS 1 的 RSA 的應用建議， e是比較短的，而 d 和 n的長度差不多，這就 使得求與 d、 n 有關的冪模運算量比與 e、 n 有關的冪模運算量大很多，而且隨著 n的增加，兩組冪模運算的運算量差距也迅速加大。 ⑵ .利用蒙哥馬利算法進行冪模運算改進，加密時間與改進前 RSA 加密時間的對比測試 蒙哥馬利冪模運算是對 RSA 算法優化的最常見手段，是提高加密速度，實現相對快速的 RSA 加密的關鍵。現測試蒙哥馬利算法改進過的加密算法與普通 RSA加密算法，使用相同密鑰對，對相同文件加密所用時間。如表 33： 表 33：蒙哥馬利改進測試 文件大小（ B） 20 40 60 80 100 512位密鑰 Montgomery所用時間（毫秒） 35 35 34 37 42 普通 RSA 所用時間（毫秒） 119 123 128 133 133 1024為密鑰 Montgomery所用時間（毫秒） 70 73 89 101 105 普通 RSA 所用時間（毫秒） 442 461 463 469 467 通過上表可以得出，使用蒙哥馬利冪模運算確實一定程度上提高了 RSA 加密速度，使用 512 位密鑰加密文件蒙哥馬利算法改進后的加密所需時間為為改進的算法所用時間的三分之一左右，而 1024 位密鑰加密文件時，僅為四分之一左 右，蒙哥馬利冪模運算大大提高了加密效率，當文件大小更大，密鑰長度更長的情況下，蒙哥馬利冪模運算的優勢將更能體現。 性能分析與改進優化 經過一系列的 RSA 密鑰生成、文件輸入輸出和蒙哥馬利加密解密測試，做簡要的性能分析如下。 ① 軟件消耗時間的運算，大部分集中在 C++核心類庫，即 RSA 相關的各種運算。其中，冪模運算和尋找素數對時間的消耗最大，在核心優化時應優先考慮。 ② 文件輸入輸出消耗時間其次，因為磁盤讀寫速度要遠遠低于內存讀寫速度。所以，應該將頻繁的讀寫操作盡量集中到內存，然后一次性寫入磁盤。 ③蒙 哥馬利算法對 RSA 加密效率的提高非常明顯，對于優化冪模運算起到了非常重要的工作。 針對以上三點，軟件應進行一系列改進和優化。主要有以下幾方面。 ① 在要對文件進行加密解密的時候，先將文件按一定的數據結構讀入內存，然后進行加密或解密操作。運算數據都讀取自內存。 ② 在對加密或解密完成的數據進行寫出的時候，都是將其直接寫到指定好的文件，即直接寫入磁盤。這是因為，考慮到中途可能因為意外斷電等原因引起操作中斷，為了保護已經花費時間運算完成的數據，將其直接寫入磁盤。 ③ 在安全性上做進一步優化，例如在尋找素數時，素數 測試使用更安全的算法，例如，本系統采用的是查已經計算好的素數表的方式得到準確的素數，但是素數表的方式給 RSA 的安全性帶來隱患，因為攻擊者如果得到了密鑰生成時所 使用的素數表，攻破 RSA 加密的難度將會大大降低。可以考慮使用幾組小素數，這些小素數用來當作因子，他們的倍數將被從大素數搜索范圍內剔除。 ④ 對 C++核心類庫進行重點優化，使其運算效率盡可能提高。其中包括對各類之間的組織細節、各程序模塊的具體編寫等，進行全面細致的檢查和修改，例如將大數據類型以對象指針傳遞而不拷貝，將簡單的 for 循環展開等。 由于開發時間 倉促等因素，在書寫本文時，軟件并未完成全面細致的優化。 結束語 RSA 應用于文件加密適合交流管理小型文件，將任意文件以非對稱密鑰加密成文本可以對其更方便的交流和管理，有廣闊的開發前景。而要實現較為快速的RSA 文件加密系統，對冪模運算的優化是核心，只要充分利用蒙哥馬利冪模運算原理，對 RSA 加密算法進行適當的改進， RSA文件加密將通過瓶頸，在小型文件加密上有著巨大的發展空間。 參考文獻 [1]羅斌等 . Visual c++ 編程技巧精選 500 例 [M] .北京：中國水利水電出版社 ,2021 年 1月 ,193205 [2]張耀仁 . C++程序設計徹底研究 [M].北京：中國鐵道出版社 2021年 7月 280284 [3]鄭莉，董淵 . C++語言程序設計 [M].北京：清華大學出版社第 2版 2021年 7月 [4]丁有和 鄭進 周怡軍 . Visual c++使用教程 .北京：電子工業出版社 2021年 1月 [5]于秋生，魏俊鵬 .C++Builder 6 實用編程 100 例 [M].北京：中國鐵道出版社 2021 年 7月 [6]王許書 ,王新輝 ,夏宏 . Montgomery方法及其在偽隨機數發生器中的應用 [J].計算機應用與軟件 2021年 6月 2324 [7]陳逢林 ,蘇厚勤 .Montgomery 算法的改進及其在 RSA 中的運用 [J].計算機應用與軟件 2021年 4月 2526 [8]CFile操作詳解 [EB]。 。 致 謝 本論文的工作是 2021 年 2 月至 2021 年 6 月在成都信息工程學院網絡工程 系完成的。文中除了特別加以標注地方外，不包含他人已經發表或撰寫過的 研究成果，也不包含為獲得成都信息工程學院或其他教學機構的學位或證書而使用過的材料。除非另有說明，本文的工作是原始性工作。 本文是在吳震老師的熱情關心和指導下完成的，他淵博的知識和嚴謹的治學作風使我受益匪淺，對順利完成本課題起到了極大的作用。在此向他表示我最衷心的感謝！ 在論文完成過程中，本人還得到了各論壇程序愛好者的熱心幫助，本人向他們表示深深的謝意！ 最后向在百忙之中評審本文的各位專家、老師表示衷心的感謝！ 作者簡介： 姓 名： 時超 性別： 男 出生年月： 1984 年 9 月 25 日 民族： 漢 Email: