目目 錄錄 摘摘 要要 1 前前 言言 3 第第 1 章章 RSA 應用現狀及應用于文件加密的分析應用現狀及應用于文件加密的分析 4 1 11 1 RSARSA 算法介紹與應用現狀算法介紹與應用現狀 4 1 21 2 RSARSA 應用于文件加密的分析應用于文件加密的分析 5 第第 2 2 章章 RSARSA 文件加密軟件的設計與實現文件加密軟件的設計與實現 9 2 12 1 需求分析與總體設計需求分析與總體設計 9 2 22 2 各部分的設計與開發各部分的設計與開發 12 第第 3 3 章章 軟件整體測試與分析改進軟件整體測試與分析改進 28 3 13 1 編寫測試各項性能需要的精確計時類編寫測試各項性能需要的精確計時類 28 3 23 2 測試數據與分析改進測試數據與分析改進 28 3 33 3 使用中國余數定理使用中國余數定理 40 第第 4 4 章章 可移植模塊的簡要說明與開發前景可移植模塊的簡要說明與開發前景 42 總結與體會總結與體會 44 致謝詞致謝詞 45 參考文獻參考文獻 46 需要設計源碼請聯系 QQ 731767310 摘摘 要要 分析 RSA 算法的應用現狀 論證文件加密應用 RSA 算法的可行性和意 義 設計一套完整實用的 RSA 文件加密解決方案 具體編碼實現 對 RSA 算法進行研究 從常規 RSA 算法出發 用 C 實現 RSA 加密算法類庫 并 在 32 位 windows 平臺封裝成組件 在 Net 平臺引用此組件 實現可以對任 意文件進行 RSA 加密操作的窗體應用程序 經過加密的文件以及密鑰文件 都是文本文件 給出關鍵類類圖 整個應用程序的結構描述文檔 關鍵模塊 流程圖 較詳細的接口文檔 所有源代碼 對應用程序進行測試 對測試結 果進行分析研究 進而對應用程序進行改進 對關鍵算法進行盡可能的優化 最終得到一個在 windows 運行的可以用指定密鑰對任意文件進行 RSA 加密 并可解密的完整應用程序 和一些相關的可移植組件 關鍵詞 RSA RSA 算法 文件加密 加密成文本 需要設計源碼請聯系 QQ 731767310 AbstractAbstract Do research about the application area of RSA encryption and reason that RSA can be used for file encryption Design a RSA file encrypt solution and complete an application on Microsoft Windows Design a C class based on normal RSA algorithm And make a DLL module based on the class Then complete a Net Framework window application using that DLL The application can encrypt any file and decrypt them The file after encryption can be saved as a text file And the encryption keys also can be saved as text Provide pivotal classes chart project description core algorithm flowchart all source code and module interfaces document Do application performance test and record the performance data Analyze the result then optimize core algorithm and improve the application Finally create a practical application using RSA algorithm that can encrypt and decrypt any file And several modules in the project can be reuse by other applications For instance the C class can be cross compiled for handheld devices the DLL can be referenced by other win32 applications and the Net class can be easily referenced by web server applications or web services Key words RSA RSA algorithm file encryption encrypt to text 需要設計源碼請聯系 QQ 731767310 前前 言言 RSA 公鑰加密算法是第一個既能用于數據加密也能用于數字簽名的算法 它易于理解和操作 也十分流行 算法的名字以發明者的姓氏首字母命名 Ron Rivest Adi Shamir 和 Leonard Adleman 雖然自 1978 年提出以來 RSA 的安全性一直未能得到理論上的證明 但它經歷了各種攻擊 至今 2007 年 未被完全攻破 隨著越來越多的商業應用和標準化工作 RSA 已 經成為最具代表性的公鑰加密技術 VISA MasterCard IBM Microsoft 等 公司協力制定的安全電子交易標準 Secure Electronic Transactions SET 就采用了標準 RSA 算法 這使得 RSA 在我們的生活中幾 乎無處不在 網上交易加密連接 網上銀行身份驗證 各種信用卡使用的數 字證書 智能移動電話和存儲卡的驗證功能芯片等 大多數使用 RSA 技術 當今公鑰加密更廣泛應用于互聯網身份認證 本課題將公鑰加密算法 RSA 應用于小型文件加密 將任意文件加密成文本的解決方案 使其使用更 加靈活 整個工程的分層設計 給引用移植和后續開發帶來便利 需要設計源碼請聯系 QQ 731767310 第 1 章 RSA 應用現狀及應用于文件加密的分析 1 11 1 RSARSA 算法介紹與應用現狀算法介紹與應用現狀 RSA 算法可以簡單敘述如下 取素數 p q 令 n p q 取與 p 1 q 1 互素的整數 e 由方程 d e 1 mod p 1 q 1 解出 d 二元組 e n 作為公開密鑰 二元組 d n 作為私有密鑰 b ae mod n c bd mod n 附錄中給出了證明 a c mod n 具體的 RSA 算法協議見 http www di au rsa alg html 提及的算法中的字母與協議文檔中的一致 不再另做解釋 RSA 公開密鑰加密算法自 20 世紀 70 年代提出以來 已經得到了廣泛認 可和應用 發展至今 電子安全領域的各方面已經形成了較為完備的國際規 范 RSA 作為最重要的公開密鑰算法 在各領域的應用數不勝數 RSA 在硬件 方面 以技術成熟的 IC 應用于各種消費類電子產品 RSA 在軟件方面的應用 主要集中在 Internet 上 加密連接 數字簽名 和數字證書的核心算法廣泛使用 RSA 日常應用中 有比較著名的工具包 Open SSL SSL Security Socket Layer 是一個安全傳輸協議 在 Internet 上進行數據保護和身份確認 Open SSL 是一個開放源代碼的實現了 SSL 及相 關加密技術的軟件包 由加拿大的 Eric Yang 等發起編寫的 相關詳細介紹 見 http www openssl org about Open SSL 應用 RSA 實現簽名和密鑰 交換 已經在各種操作系統得到非常廣泛的應用 另外 家喻戶曉的 IE 瀏覽 器 自然也實現了 SSL 協議 集成了使用 RSA 技術的加密功能 結合 MD5 和 SHA1 主要用于數字證書和數字簽名 對于習慣于使用網上購物和網上銀行 需要設計源碼請聯系 QQ 731767310 的用戶來說 幾乎天天都在使用 RSA 技術 RSA 更出現在要求高度安全穩定的企業級商務應用中 在當今的企業級 商務應用中 不得不提及使用最廣泛的平臺 j2ee 事實上 在 j2se 的標準 庫中 就為安全和加密服務提供了兩組 API JCA 和 JCE JCA Java Cryptography Architecture 提供基本的加密框架 如證書 數字簽名 報 文摘要和密鑰對產生器 JCA 由幾個實現了基本的加密技術功能的類和接口 組成 其中最主要的是 java security 包 此軟件包包含的是一組核心的類 和接口 Java 中數字簽名的方法就集中在此軟件包中 JCE Java Cryptography Extension 在 JCA 的基礎上作了擴展 JCE 也是由幾個軟件 包組成 其中最主要的是 javax crypto 包 此軟件包提供了 JCE 加密技術操 作 API javax crypto 中的 Cipher 類用于具體的加密和解密 在上述軟件包 的實現中 集成了應用 RSA 算法的各種數據加密規范 RSA 算法應用規范介紹 參見 這些 API 內部支持的算法不僅僅只有 RSA 但是 RSA 是數字簽名和證書中最常用的 用戶程序可以直接使用 java 標準庫中提供的 API 進行數字簽名和證書的各種 操作 單機應用程序使用 RSA 加密尚比較少見 例如使用 RSA 加密任意一個文 件 1 21 2 RSARSA 應用于文件加密的分析應用于文件加密的分析 1 2 1 文件加密使用 RSA 的可行性 通過 1 1 節的論述 不難看出 RSA 當今的應用多在于數字簽名和證書等 方面 之所以只應用于這些短小數據的加密解密 是因為 RSA 算法加密極慢 速度是 DES 對稱密鑰加密速度的千分之一左右 正是因為這樣 把 RSA 應用 于普通文件加密的想法一直被忽略 通常文件被想象成大數據塊 但是實際 上在日常應用中 有些極其重要的文本資料是并不太大的 比如因擔心遺忘 而用普通文本記錄的銀行帳號和密碼 不應被陌生人知道的重要電話號碼 幾千字節大的重要小圖片等 雖然 RSA 加密運算的速度十分慢 但是在 PC 性能越來越好的今天 對于 需要設計源碼請聯系 QQ 731767310 幾千字節的數據進行一次幾百位密鑰的 RSA 加密 所消耗的時間應該是可以 接受的 下面結合大數運算程序的調試 從理論上簡單的分析消耗時間 在 一臺普通配置的 PC 機上對一個整數進行冪模運算 因為公開密鑰的 e 通常取 的較小 所以指數取一個小整數 比如 C353 模一個 70 字節長的整數 140 位十六進制 大數單元以線性組方式實現 對應到 RSA 算法中 這相當于約 560bit 的 n 調試一個函數測試 按初等數論中的知識對程序進行算法優化 最終在一臺配置為 AMD Athron2800 外頻 333MHZ 物理內存 512MB 的 PC 上 測試需要約 45 毫秒時間 如果按這種速度 逐字節對 1KB 的數據進行同樣的 運算 所消耗的時間理論上為 45 毫秒的 1024 倍即約 45 秒 這個時間并不是 非常長 其實從一個簡單的角度來說 既然 RSA 用于數字簽名可行 那就完全可 以用于同樣大小的普通文件 對于較大的文件 如果分成與數字簽名同樣大 小的段 這里假設數字簽名較短 不分段一次計算加密完成 分開的各段逐 一進行加密運算 那所需要的時間也只是按文件大小線性的增長 通常數字 簽名為幾十字節 加密運算并不需要很長的等待 這就說明對于幾百字節或 一兩 K 字節大小的文件來說 如果進行 RSA 加密 并不會是非常漫長的工作 當然 如果文件更大 加密就顯得十分漫長了 比如按前面敘述的 45 毫秒大 數運算程序推理 加密 1M 字節大小的文件需要約 1 天的時間 所以 要在普 通 PC 用幾百位以上的長密鑰 RSA 加密文件 文件不能過大 一般可以接受的 上限是幾 KB 如果要在較短時間內加密大文件 需要縮短密鑰長度以減小運 算量 這將帶來安全性隱患 本文的第 3 章將根據實際調試好的軟件 測試給出具體的時間消耗數據 例如 在一臺配置為 AMD Athron2800 外頻 333MHZ 物理內存 512MB 的 PC 上測試實現的軟件 以 560bit 的 n 逐字節加密一個 1KB 大小的文件需要 55 秒 通常記錄如銀行帳號密碼等重要數據的文本文件大小不足百字節 加密 只需要數秒鐘 所以對于小型文件 進行較長密鑰的 RSA 加密是完全可行的 1 2 2 文件加密使用 RSA 的意義 如 1 2 1 節所述 小型文件加密可以使用 RSA 比如 因擔心遺忘而用 需要設計源碼請聯系 QQ 731767310 普通文本記錄的銀行帳號和密碼 不應被陌生人知道的重要電話號碼 幾千 字節大的重要小圖片等 可行的方法未必是必要的 本小節討論何種文件適 合用非對稱密鑰加密 即 RSA 加密文件的意義所在 對于前面敘述的帶有重要信息的小型文本和二進制數據的維護 如果 不加密 將無法放心的保存在計算機上 尤其是連網的或機房里的公共計算 機 如果借助功能強大的大型多用戶數據保護程序維護幾個小型文件 顯 得十分煩瑣 好比殺雞用牛刀 如果采用對稱密鑰加密 即加密解密的密 鑰相同 只適合部分情況 在某些情況下 使用對稱密鑰加密文件 交流使 用不夠方便 比如 張三由于某種原因 需要將自己的某個文件在公共計算 機上留給李四 而不希望別人看到內容 如果采用對稱密鑰加密 張三和李 四提前約好一個密碼就可以 但是如果張三想要在同一臺公共計算機上再留 一個秘密文件給王五 而不希望別人看到 就要和王五另外約定一個密碼 如果需要在這臺公共計算機上留十個文件給不同的人 自己就要記和十個人 約定好的密碼 這樣以來交流起來不夠方便 因為對于張三 要自己維護太 多的密鑰 非對稱密鑰 公開密鑰方式 恰好解決這樣的問題 只要大家都在 這臺計算機或這臺計算機可以訪問到的地方 留下自己的公開密鑰 一切就 變的容易解決了 張三要留給李四的文件 就用李四的公開密鑰加密 要留 給王五的文件 就用王五的公開密鑰加密 李四和王五只要把留給自己的文 件用自己的私有密鑰解密 就可以得到留給自己的文件了 顯然 非對稱密 鑰體制更適合多用戶交流 而將這種加密方式直接應用于文件加密 使我們 在公開場合的交流更加靈活方便 一種更實際的情況是 我們想通過 Internet 上的公眾論壇或郵件發送重 要保密信息給某人 例如發送一個銀行帳號和密碼給某人 這種情況要保證 安全 在當今互聯網絡上是比較棘手的 如果用公眾論壇直接留言給指定 用戶 論壇管理員和服務器管理員通常有方法看到數據 如果發送郵件 雖然傳送過程是加密的 但是密碼畢竟是由郵件服務器維護 所以系統管理 員通常也有辦法看到內容 問題的關鍵在于我們所有的數據包括密鑰保存在 服務器之上 在這種情況下 我們需要使用公開密鑰方式 并自己維護私有 密鑰 RSA 文件加密可以靈活的解決這些問題 例如 我們可以將任意一個 文件用某人的公開密鑰加密變換成一段可以復制粘貼的文本 然后粘貼在公 需要設計源碼請聯系 QQ 731767310 眾互聯網上 對方只需把需要解密的文本復制保存成一個文本文件 在本地 機用自己的私有密鑰解密即可 我們可以將自己的私有密鑰通過 DES 加密后 保存在自己的移動磁盤上 使用的時候只要將其解密讀取即可 用完后立即 從當前操作環境清除 這樣 我們自己維護自己的私有密鑰 利用簡單并且 公開的方式 可以安全傳送任意小型數據 包括一切二進制文件 所以 對于使用小型文件進行數據交換的情況 更好的方案是通過一個 小型應用程序對這些文件進行非對稱密鑰加密 為了適合前面敘述的在公共 BBS 與特定的某人交流重要保密信息的情況 加密生成的數據應該是文本 這樣可以方便復制粘貼 綜上所述 使用前面敘述的方式加密文件有兩點重要意義 應用非對 稱密鑰加密任意文件 使非對稱密鑰的應用不僅僅局限于互聯網絡 非對 稱加密后的數據變換成文本 使得我們可以通過幾乎任何方式安全傳遞任意 文件 比如在只有 http 的環境使用 xml 方式 需要設計源碼請聯系 QQ 731767310 第第 2 2 章章 RSARSA 文件加密軟件的設計與實現文件加密軟件的設計與實現 2 12 1 需求分析與總體設計需求分析與總體設計 2 1 1 功能分析 經過 1 2 2 節的論述 我們可以將對軟件的要求總結如下 可以按要求的位數生成非對稱密鑰 可以保存密鑰和裝載密鑰 密鑰保存為純文本 可以用指定密鑰以 RSA 算法加密任意一個文件 加密生成的數據為純 文本 可以裝載加密過的文件 并用指定的密鑰解密還原出原文件 提示信息完整 操作舒適 圖形界面雅觀 按上述描述 給出 Use Case 和 Statechart 如圖 2 1 圖 2 1 本項目的 Use Case 和 Statechart 根據以上分析 一般來說 需要進行編碼的程序有 需要設計源碼請聯系 QQ 731767310 RSA 密鑰生成 RSA 加密解密 任意文件的讀取和保存操作 各環 節必要的數據編碼轉換 圖形操作界面 2 1 2 工程方案選擇 結合現有的常見開發模式綜合分析 有多種實現方案 下面陳述其中幾 種 并分析選擇一種解決方案 并給出工程框架 1 整個工程使用 java 平臺實現 RSA 密鑰生成 RSA 加密解密的功能實現十分簡單 因為標準庫中集成幾 乎所有功能 不需要從 RSA 算法出發進行編碼 在 j2se 標準庫中 javax crypto 中的 Cipher 類用于具體的加密和解密 java security 包直接 提供了數字簽名的相關方法 因為有強大的標準庫支持 文件的讀取和保存 操作 各環節必要的數據編碼轉換 圖形操作界面的實現也很簡單 使用 java io java awt 或 javax swing 等包 如果結合一種快速開發的 IDE 比如 JBuilder 整個軟件可以在很短的時間內編碼完成 如果不考慮非 PC 設備和機器效率等問題 java 平臺幾乎是最佳解決方案 但是缺點也很明顯 如果想把核心算法和功能應用到非 PC 設備 例如嵌入式手持設備 則要求設 備上有支持前面提及的加密類庫的 CVM 對于在 PC 上運行 JVM 的數據運算 速度要遠遠落后于本地化代碼在 PC 上的運算速度 本軟件需要進行大量運算 這一點不適合由 java 完成 2 整個工程使用 Net 平臺實現 與使用 java 平臺完全類似 加密等有 Net 基礎類庫的支持 不需要大 量編碼實現 另外由于 Visual Studio 的強大便利 這種規模的工程可以十 分迅速的完成 缺點是只能在有微軟 Net Framework 的環境運行 在 Windows 操作系統 Net Framework 的機器效率好于 java 平臺 但是相比于 本地化的代碼 還是十分拖沓的 3 整個工程使用 Windows 本地化程序實現 在不應用 Windows 或第三方現成組件的情況下 需從 RSA 算法出發編碼 實現 其他各功能的設計開發 如文件操作 數據編碼轉換和圖形界面等 可以使用 ATL MFC 或 Windows API 實現 這種工程幾乎是為 Windows 量身訂 做 執行效率最好 但是對于非 PC 設備 只能方便的移植到運行 Windows 嵌 需要設計源碼請聯系 QQ 731767310 入式操作系統的設備 向其他操作系統移植困難 需要重新編寫大量代碼 通常解決本地化代碼的移植問題 都是使用 C 標準庫 即功能盡量多的由 C 標準庫完成 這樣在移植的時候 只需要重新編寫操作系統相關的代碼即 可 這種開發方式比起前兩種 缺點就是設計開發模式陳舊 代碼煩瑣 不 方便維護 流行的 Net 上的語言引用各種功能比較麻煩 4 考慮可能的復用 針對具體情況分層開發實現 綜合考慮復用性 可維護性和執行效率 較妥當的方法是分層設計 核 心的 RSA 算法由 C 類庫實現 針對用戶所在的操作系統封裝成本地化組件 其他各功能如文件操作 數據編碼轉換和圖形界面等 由托管代碼借助虛擬 機平臺標準庫的功能快速開發實現 本文針對選用 Net 上的 C 論述 選用 java 由 JNI 或其他方式調用本地組件 設計模式上是完全類似的 這種開 發方式 核心功能集中在最底層 在不斷的封裝中針對具體環境對組件功能 不斷擴充 任意一個層面的封裝都可以被直接應用到其他項目 比如在 Web 使用以前為某窗體程序寫的組件 給嵌入式設備交叉編譯算法庫等 但是每 一層都需要依賴底層的所有組件 圖 2 2 形象的說明了分層設計給復用帶來 的好處 圖 2 2 綜合考慮復用性 可維護性和執行效率的分層設計 選用第四種設計方案 上層使用 C 底層算法使用 C 可以由一個 Visual Studio 解決方案管理 給調試帶來極大的方便 整個工程分四層 實現 RSA 加密算法的 C 核心類庫 封裝 C 核心類庫的 DLL 組件 引用 DLL 的 Net 類 實現文件操作功能的 Net 窗體應用程序 2 2 節詳細介紹各部分 需要設計源碼請聯系 QQ 731767310 的設計與開發 考慮到工作量 本軟件加解密數據沒有嚴格遵從 RSA 標準 PKCS 1 而 是在滿足設計要求的前提下 以一種盡可能簡單的方式實現加密和解密 2 22 2 各部分的設計與開發各部分的設計與開發 2 2 1 實現 RSA 加密算法的 C 核心類庫 1 大數存儲和四則運算 根據 RSA 算法的要求 為了實現大數的各種復雜運算 需要首先實現大 數存儲和基本四則運算的功能 當今開源的大數運算 C 類有很多 多用于 數學分析 天文計算等 本文選用了一個流行的大數類型 并針對 RSA 算法 和本項目的具體需要對其進行了擴充和改進 下面簡單介紹大數存儲和四則 運算的實現原理 最先完成的功能是大數的存儲 存儲功能由 flex unit 類提供 和普通 的類型一樣 每一個大數對應一個 flex unit 的實例 類 flex unit 中 用 一個無符號整數指針 unsigned a 指向一塊內存空間的首地址 這塊內存空 間用來存儲一個大數 所以可以說 大數是被存儲在一個以 unsigned 為單元 的線性組中 在方法 void reserve unsigned x 中通過 C 的 new 來給 a 開辟空間 當 flex unit 的實例中被存入比當前存儲的數更大的數時 就會 調用 reserve 來增加存儲空間 但是當 flex unit 的實例中被存入比當前存 儲的數更小的數時 存儲空間并不會自動緊縮 這是為了在運算的時候提高 執行效率 結合指針 a 有兩個重要的無符號整數來控制存儲 unsigned z 和 unsigned n z 是被分配空間的單元數 隨數字變大不斷增大 不會自己 緊縮 而 n 是當前存儲的大數所占的單元數 組成一個大數的各 unsigned 單 元的存入和讀出由 set get 方法完成 變量 n 是只讀的 類型 unsigned 在 32 位機是 32 位的 所以對于 flex unit 這個大數類來說 每個大數最大可 以達到 個字節長 這已經超過了 32 位機通常的最大內存容量 所以是足夠 進行 RSA 所需要的各種運算的 圖 2 3 形象的說明了大數存儲類 flex unit 對大數的管理 需要設計源碼請聯系 QQ 731767310 a unsigned 類型的指針類型的指針 大數占大數占 n 個單元個單元 開辟了開辟了 z 個單元大的內存個單元大的內存 內存空間內存空間 圖 2 3 flex unit 對大數的管理 在 flex unit 的存儲功能基礎上 將其派生 得到 vlong value 在 vlong value 中實現四則運算函數 并實現強制轉換運算符 unsigned 以方 便大數類型和普通整數的互相賦值 當大數被強制轉換為 unsigned 時 將取 其最低四字節的值 四則運算實現的原理十分簡單 都是按最基本的算術原 理實現的 四則運算過程的本質就是按一定數制對數字的計算 比如相加 就是低位單元對齊 逐單元相加并進位 減法同理 而乘除法和取余也都是 按照豎式運算的原理實現 并進行了必要的優化 雖然實現了四則運算函數 但是若是程序里的運算都要調用函數 顯得煩瑣而且看起來不美觀 所以我 們另寫一個類 vlong 關聯 Associate 即使用 vlong value 類型的對象或 其指針作為成員 vlong value 在 vlong 重載運算符 這樣 當我們操作 vlong 大數對象的時候 就可以像使用一個簡單類型一樣使用各種運算符號 了 之所以將 vlong value 的指針作為成員而不是直接構造的對象 也是為 了提高執行效率 因為大型對象的拷貝要消耗不少機器時間 2 大數冪模與乘模運算 MontgomeryMontgomery 冪模算法 在實現了 vlong 類型后 大數的存儲和四則運算的功能都完成了 考慮 到 RSA 算法需要進行冪模運算 需要準備實現這些運算的方法 所以寫一個 vlong 的友元 完成冪模運算功能 冪模運算是 RSA 算法中比重最大的計算 最直接地決定了 RSA 算法的性能 針對快速冪模運算這一課題 西方現代數 學家提出了很多的解決方案 經查閱相關數學著作 發現通常都是依據乘模 的性質 先將冪模運算化簡為乘模nnbnanbamod mod mod mod 運算 通常的分解習慣是指數不斷的對半分 如果指數是奇數 就先減去一變 需要設計源碼請聯系 QQ 731767310 成偶數 然后再對半分 例如求 D E 15 可分解為如下 6 個乘模nC E mod 運算 nCnCCCmodmod 2 1 nCnCCCmodmod 3 12 nCnCCCmodmod 6 223 nCnCCCmodmod 7 34 nCnCCCmodmod 14 445 nCnCCCmodmod 15 56 歸納分析以上方法 對于任意指數 E 可采用如圖 2 4 的算法流程計算 需要設計源碼請聯系 QQ 731767310 開始 D 1 P C mod n E 0 E 為奇數 nPDDmod E E 1 nPPPmod E 為偶數 E E 2 Yes No Result D 結束 Yes Yes No No 圖 2 4 冪模運算分解為乘模運算的一種流程 按照上述流程 列舉兩個簡單的冪模運算實例來形象的說明這種方法 求的值17mod215 開始D 1P 2 mod 17 2 E 15 需要設計源碼請聯系 QQ 731767310 E 奇數D DP mod n 2P PP mod n 4E E 1 2 7 E 奇數D DP mod n 8P PP mod n 16E E 1 2 3 E 奇數D DP mod n 9P PP mod n 1E E 1 2 1 E 奇數D DP mod n 9P PP mod n 1E E 1 2 0 最終 D 9 即為所求 求的值13mod28 開始D 1P 2 mod 17 2 E 8 E 偶數D 1P PP mod n 4E E 2 4 E 偶數D 1P PP mod n 3E E 2 2 E 偶數D 1P PP mod n 9E E 2 1 E 奇數D DP mod n 9P 不需要計算 E E 1 2 0 最終 D 9 即為所求 觀察上述算法 發現 E 根據奇偶除以二或減一除以二實際就是二進制的 移位操作 所以要知道需要如何乘模變量 并不需要反復對 E 進行除以二或 減一除以二的操作 只需要驗證 E 的二進制各位是 0 還是 1 就可以了 同 樣是計算 下面給出從右到左掃描二進制位進行的冪模算法描nCD E mod 述 設中間變量 D P E 的二進制各位下標從左到右為 u u 1 u 2 0 Powmod C E n D 1 需要設計源碼請聯系 QQ 731767310 P C mod n for i 0 to u do if Ei 1 D D P mod n P P P mod n return D 有些文獻將上述算法稱為平方乘積二進制快速算法 例如參考文獻中的 基于 RSA 算法的一種新的加密核設計 其實這種算法本質上和圖 2 4 的流 程完全一致 只是把根據指數奇偶分開的減一和除以二合并成對指數二進制 各位的判斷而已 在本軟件的代碼中采用直接掃描 vlong 二進制各位的辦法 剩下的問題就是乘模運算了 提高乘模運算的速度是提高模冪運算速度 的關鍵 一般情況下 n 是數百位乃至千位以上的二進制整數 用普通的除 法求模而進行乘模運算是不能滿足速度的要求的 為此 Montgomery 在 1983 年提出了一種模加右移的乘模算法 主要著作發表于 1985 年 從而避免了 通常求模算法中費時的除法步驟 本軟件僅僅是應用 Montgomery 蒙哥馬利 算法 算法的具體推導證明需要頗多數論知識 不在本文的討論范圍內 如 需了解可參見蒙哥馬利的相關著作 下面簡單描述 RSA 中常用的 Montgomery 蒙哥馬利 算法供參考理解源程序 選擇與模數 n 互素的基數 R 2k n 滿足 2k 1 n 2k n 應為奇數 并且 選擇 R 1及 n 滿足 0 R 1 n 0 n n 使得 RR 1 nn 1 對于 0 m Rn 的任意整數 Montgomery 給出求模乘法 mR 1 mod n 的快速算法 M m M m Rnmt RRnRm 0 mod mod if t n return t n else return t 需要設計源碼請聯系 QQ 731767310 因為 故 t 為整數 同時 得Rmmnnnmod nmtRmod 由于 M m 中 t 結果范圍是nmRtmod 1 RnRnnm 0 0 t n x n return x exp C E n D R n P C R mod n i 0 while true if E 的當前二進制位 Ei 1 D M D P 從低位到高位 檢測二進制位 i 1 if i E 的二進制位數 break P M P P 需要設計源碼請聯系 QQ 731767310 return D R 1 mod n 在具體的實現中 對應 monty 類的 mul 和 exp 方法 全局函數 modexp 初 始化 monty 對象并調用其 exp 方法 使用的時候直接調用 modexp 即可 3 尋找素數 EratosthenesEratosthenes 篩選與 FermatFermat 素數測試 首先要說明的是 事實上 當今的計算機還不足以聰明到立刻計算生成 一個很大的隨機素數 一般來說 要得到 100 準確的大素數 都是通過查已 經計算好的素數表的方式 但是素數表的方式給 RSA 的安全性帶來隱患 因 為攻擊者如果得到了密鑰生成時所使用的素數表 攻破 RSA 加密的難度將會 大大降低 本程序起初使用素數表的方式 后來考慮到安全性問題 生成密 鑰的方式改為隨機計算生成 這樣 短時間內如果要得到一個 100 準確的大 素數是很困難的 只能以盡可能高的概率得到一個大素數 經過 2 2 1 1 和 2 2 1 2 小節 所有的大數運算功能都準備完畢 在此 基礎上 本工程將尋找素數的功能置于類 Prime factory san 之中 外部只 要調用本類實例的成員 vlong find prime vlong i np i unsigned p pl i unsigned r start vlong p if r r p r while r 0 x r 圖 2 5 在素數搜索范圍內剔除小素數因子 p 的倍數 接下來 對可能為素數的數 即標記數組 b 中值為 1 的元素對應的數 進行素數測試 數論學家利用費馬小定理研究出了多種素數測試方法 本程 序使用一種最簡單的方式 直接應用費馬小定理 取一個與 p 互素的整數 A 對于大素數 p 來說應該滿足 Ap 1mod p 1 但是我們把 p 代入一個大整數 滿足這個關系的數不一定是素數 這時我們改變 A 進行多次測試 如果多 次測試都通過 這個數是素數的概率就比較大 按這種原理 我們編寫素數 測試函數如下 需要設計源碼請聯系 QQ 731767310 int is probable prime san const vlong 測試次數 const unsigned any rep 2 3 5 7 測試用的底數 for unsigned i 0 i rep i 1 if modexp any i p vlong 1 p vlong 1 return 0 modexp 是冪模函數 按上一小節敘述的算法編碼 這里 modexp 計算 any i p 1mod p return 1 測試通過 程序就判定這個數為找到的素數 將找到的素數返回給上層 程序使用 在這里其實有一個不可忽視的問題 就是得到一個測試通過的合 數 對于這種情況 RSA 算法加密解密是否還可以實現 是一個需要從數學 角度論證的問題 因為得到素數的概率很高 經過一整天的生成密鑰和加密 操作 沒有發現失敗的密鑰 所以本文暫沒有對這個問題進行討論 綜上所述 總結素數尋找的流程 如圖 2 6 所示 需要設計源碼請聯系 QQ 731767310 開始 按 start 參數初始化標記數組 b SS i 0 計數 i8 以上公式其實也可以從理論上得到 因為模數 n 取 8 位時 冪模運算的 結果仍然近似為 8 位 這時一個字節的數據經過加密 得到的數據大小近似 不變 轉換成十六進制文本 大小就增加了 1 倍 按此原理 冪模運算結果 長度近似為加密模數 n 的長度 加密后數據長度是加密前的 N 8 倍 N 是加 密位數 而轉換為十六進制文本后長度又增大 1 倍 加密后得到的文本長度 就是加密前原始數據大小的 N 4 倍 所以 B A N 4 這與前面從實驗結果總 結得到的公式基本一致 可以把公式中的 260 修正為更精確一些的 256 3 以多字節為步長 對文件進行加密 默認的設置是加密時逐個字節進行 RSA 運算 可以通過設置窗體把分塊 的大小更改為其他長度 比如 2 字節一組 4 字節一組 進行 RSA 運算 下 面測試多字節為步長的加密執行效率 取一個 480 字節長的文件作為加密對 象 對其進行 512bit RSA 公鑰加密 私鑰解密還原 記錄所消耗的時間 統 計數據如表 3 6 所示 表 3 6 加密分段大小改變對效率的影響測試 消耗時間單位 秒 加密方 式 步 長 2 字節4 字節6 字節8 字節10 字節 512bit 公鑰加 密 23 555112 82057 81175 91855 1848 512bit 私鑰解 密 46 308323 608916 108311 48209 2541 可見 增大加密步長使加密解密速度大幅增加 而且大步長的加密生成 的文本文件體積也比小步長的小 這都是因為增大了步長后 文件被分成的 塊數少了 冪模運算次數下降 所以在使用 RSA 加密時 設置使用合適的數 需要設計源碼請聯系 QQ 731767310 據分塊也是提高加密速度的關鍵 4 在更快的 PC 對進行文件加密測試 在一些性能更好的 PC 上 本軟件可以獲得更好的性能 測試數據同樣可 以分析得到以上段落敘述的結論 下面對照表 3 4 給出一組其他 PC 上同樣 的測試得到的數據 測試 PC 配置為 CPU AMD Athron2800 外頻 333MHZ 物 理內存 512MB 數據見表 3 7 表 3 7 待加密文件大小與加密時間的關系再次測試 時間單位 秒 n 位數 文件大 小 50Byte100Byte150Byte200Byte250Byte 512bit 公鑰加 密 2 43474 89757 17289 450811 9837 512bit 私鑰解 密 4 77259 442714 00219 012523 6544 1024bit 公鑰加 密 6 350112 236418 245924 300130 1284 1024bit 私鑰解 密 20 010139 875460 212679 335199 5482 對于這組數據 表 3 4 后的推理分析仍都成立 在此 PC 測試填寫表 3 6 同樣得到了類似規律的數據 在此不再羅列 經過一系列各種機型 各種 Windows 操作系統 包括 Windows XP 2000SP4 ME 98 均需 Net 框架 上的 測試 本軟件均能正常運行 在 2006 年初主流配置的 PC 上運行此軟件 逐 字節加密 1KB 大小的文件 消耗時間均在 1 分鐘以內 3 2 4 性能分析與改進優化 經過一系列的 RSA 密鑰生成 文件輸入輸出和加密解密測試 做簡要的 需要設計源碼請聯系 QQ 731767310 性能分析如下 軟件消耗時間的運算 大部分集中在 C 核心類庫 即 RSA 相關的各 種運算 其中 冪模運算和尋找素數對時間的消耗最大 在核心優化時應優 先考慮 文件輸入輸出消耗時間其次 因為磁盤讀寫速度要遠遠低于內存讀寫 速度 所以 應該將頻繁的讀寫操作盡量集中到內存 然后一次性寫入磁盤 針對以上兩點 軟件應進行一系列改進和優化 主要有以下幾方面 在要對文件進行加密解密的時候 先將文件按一定的數據結構讀入內 存 然后進行加密或解密操作 運算數據都讀取自內存 在對加密或解密完成的數據進行寫出的時候 都是將其直接寫到指定 好的文件 即直接寫入磁盤 這是因為 考慮到中途可能因為意外斷電等原 因引起操作中斷 為了保護已經花費時間運算完成的數據 將其直接寫入磁 盤 在關鍵算法上做進一步優化 例如在尋找素數時 素數測試使用更快 速的算法 還有 3 3 節提到的 在用私有密鑰進行冪模運算時使用中國余數 定理等 對 C 核心類庫進行重點優化 使其運算效率盡可能提高 其中包括 對各類之間的組織細節 各程序模塊的具體編寫等 進行全面細致的檢查和 修改 例如將大數據類型以對象指針傳遞而不拷貝 將簡單的 for 循環展開 等 由于開發時間倉促等因素 在書寫本文時 軟件并未完成全面細致的優 化 3 33 3 使用中國余數定理使用中國余數定理 對于用 RSA 加密解密的一方 是計算 mod d MCn 這里 n p q p 和 q 是兩個二進制長度接近的大素數 由于用私密密鑰加密或解密的一方實 際知道 n 的分解 即 p 和 q 所以這一計算可以分解為以下兩部分分別進行 需要設計源碼請聯系 QQ 731767310 附錄中有中國余數定理的簡單介紹 12 1122mod mod dd mCp mCq 其中的 C1 C2 d1 d2 如下 1 2 1 2 mod mod mod 1 mod 1 CCp CCq ddp ddq 根據 RSA 算法的要求 私密密鑰 d 的二進制長度接近 n 的長度 因此 d1 和 d2 的二進制長度僅有 n 的一半左右 這樣就節省了大量的計算工作 最后 應用中國余數定理就能計算出的值 m 其npymqymmmod 2211 中 qpypqymod1 mod1 21 如果應用中國余數定理計算冪模 主要工作花在計算 12 1122mod mod dd mCp mCq 上 計算 C1 C2 d1 d2 和 m 的運算與冪摸 運算相比 計算時間較短可以不計 而位數對冪摸運算速度影響很大 因此 分開計算 12 1122mod mod dd mCp mCq 比計算 mod d MCn 要快很多 經過 測試 使用中國余數定理來簡化一些冪模運算 速度比不使用中國余數定理 時有很大的提高 在書寫本文時軟件中尚未使用中國余數定理 需要設計源碼請聯系 QQ 731767310 第第 4 4 章章 可移植模塊的簡要說明與開發前景可移植模塊的簡要說明與開發前景 如 2 1 2 節所敘述 分層設計給移植帶來方便 下面簡要敘述各層可能 的移植方式 實現 RSA 加密算法的 C 核心類庫 是基于 C 和 C 的標準庫創建的 沒有用到 C 泛型計算 STL 相關內容 代碼中沒有任何與操作系統相關的內 容 這是一種移植特性最好的程序模塊 因為現今多數非 PC 設備支持 C 編 譯 一般可以直接將本模塊交叉編譯給嵌入式設備 或在其他操作系統編譯 使用 在編譯前 將 rsa san cpp 和 vlong cpp 文件中的 include stdafx h 一行去掉 然后連同各自的頭文件拷貝出來 僅這四個文件即為 實現 RSA 加密算法的 C 類庫代碼 例如 可以將它們在 linux 操作系統用 gcc 編譯成程序模塊 把 RSA 加密功能提供給系統上的其他程序使用 封裝 C 核心類庫的 DLL 組件可以被 Windows 上的很多開發環境引用 例如在 VB6 要使用這個組件 只需在程序最開始以引用 win32api 的方式引 用即可 即 public declare function XXX 的形式 作為 Net 類庫 此模塊可以被幾十種支持 Net 的語言引用 但是由于 底層 DLL 組件的存在 使應用局限于 PC 上的 Windows 系統 在此層的使用不 僅限于窗體應用程序 Net 類庫可以由服務器程序 諸如 aspx 方便的引用 以 BS 瀏覽器服務器 的模式提供給網絡上的用戶使用 所以此應用程序可 以通過簡單的修改用于數字證書和數字簽名等身份驗證系統 如 1 2 2 節最后所分析的 將任意文件加密成文本有其重要的意義 因為此應用程序是可以將任意文件加密成文本的 所以加密成的數據可 以方便的在 Internet 上傳送 由此想到 xml 在 Internet 上攜帶數據的應用 模式 實際上 此軟件可以通過簡單的修改實現將任意文件加密為一定格式 的 xml 文件 通過這種加密方式 可以滿足重要的小應用程序等小型二進制 數據在網絡上安全順利傳輸的要求 而且 通過加密的數據以 xml 方式傳送 使 web 應用的靈活性更好 此方式甚至可以看作一種通用的小型二進制數據 安全交換協議來開發 需要設計源碼請聯系 QQ 731767310 總結與體會總結與體會 RSA 應用于文件加密適合交流管理小型文件 將任意文件以非對稱密鑰 加密成文本可以對其更方便的交流和管理 有廣闊的開發前景 本項目應用 的設計模式兼顧執行效率和可復用性 整個項目開放源代碼和各種開發資料 便于引用和繼續開發 應用本程序可以方便的在公眾論壇等環境交流要求高 度安全的各種數據 包括任意二進制和文本文件 通過對 RSA 文件加密的畢業論文設計 學習到了很多關于密碼學的有關 信息 為今后的工作有很大的幫助 也對如何設計一款好性能的軟件有了進 一步的認識和了解 在寫論文的過程中老師 同學們的熱心指導給了我非常 大的幫助 致謝詞致謝詞 需要設計源碼請