【正文】 入磁盤。 針對以上三點，軟件應進行一系列改進和優(yōu)化。其中，冪模運算和尋找素數(shù)對時間的消耗最大，在核心優(yōu)化時應優(yōu)先考慮。現(xiàn)測試蒙哥馬利算法改進過的加密算法與普通 RSA加密算法，使用相同密鑰對，對相同文件加密所用時間。對于一定大小的文件，使用 512bit 的密鑰，私有密鑰解密需要的時間是公開密鑰加密需要時間的 3倍左右；而如果使用 1024bit 的密鑰，私有密鑰解密需要的時間是公開密鑰加密需要時間的 倍以上。統(tǒng)計消耗時間情況如表 32： 表 32：加密消耗時間測試 n 位數(shù) 文件大小 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可以看出，使用同一公開密鑰加密不同大小的文件，消耗時間隨著文件大小的增加線性的增加，和 小節(jié)分析的完全一致。這里給出幾組不同角度進行測試的數(shù)據(jù)。也就是說對于長密鑰來說， RSA 隨機生成密鑰消耗時間的可能范圍較大。測試 PC 配置為 CPU 奔騰 4 845 UltraAD 芯片組，下文測試中，未說明 PC 配置的也都在同一 PC 完成，不再重復。 測試數(shù)據(jù)與分析改進 密鑰生成測試 生成密鑰運算最費時的工作是尋找素數(shù)。 表 21： RSA 加密算法的 C++類庫中的類 CBigInt 主要包含大數(shù)四則運算，素數(shù)生成，檢測，密鑰生成，存儲， RSA 核心算法等。需要加密和解密的數(shù)據(jù)是通過字符串參數(shù)置入的。類中各成員頻繁的用到字符串和 vlong 類型的轉(zhuǎn)換，因為大數(shù)是用字符串置入的，而把大數(shù)讀出，也是保存在字符指針指向的一段內(nèi)存空間里，所以也是字符串。 文件的讀寫操作代碼見附。用來完成這種算法。 Rab()測試素數(shù) ？ N Y 完 成 結(jié)束 開始 給定不定方程 11x49y=1，求最小的 x （ 1） 11 x 49 y = 1 49 mod 11 = 5 （ 2） 11 x 5 y = 1 11 mod 5 = 1 （ 3） x 5 y = 1 5 mod 1 = 0 逆向代入： 令 y=0 代入（ 3）得 x=1 令 x=1 代入（ 2）得 y=2 令 y=2 代入（ 1）得 x=9 x=9。 開始 利用 Bits 初始化 m_ulValue[i] m_ulValue[i]=rand()*0x10000+rand()。即相當于求解 B、 N 都是未知數(shù)的二元一次不定方程 ABMN=1 的最小整數(shù)解。 } } 接下來，對可能為素數(shù)的數(shù)用拉賓米勒算法進行測試，測試通過，程序就判定這個數(shù)為找到的素數(shù)，將找到的素數(shù)返回給上層程序使用。 ((S,*this))。 for(i=0。i++){if(Mod(PrimeTable[i])==0)goto begin。 } m_ulValue[0]=m_ulValue[0]1。i0。im_nLength。 本工程在素數(shù)生成時，通過數(shù)組 m_ulValue[i]來存儲生成的素數(shù)，調(diào)用 C++已有的函數(shù) Rand()產(chǎn)生隨即數(shù)，再通過素數(shù)表排除非素數(shù)，最終得到待測試之素數(shù)。 經(jīng)過 和 小節(jié)，所有的大數(shù)運算功能都準備完畢，在此基礎(chǔ)上，本工程將尋找素數(shù)的功能置于類 CBigint 之中。 ((B))。 //A=A1,X=(X*N) MOD B ((Y))。 (1)。 （ 5）此時的 X即為所求結(jié)果 。 蒙哥馬利算法求乘方的模 調(diào)用方式： (A,B) 返回 值： X=N^A MOD B （ 1） X=1。為 r在模 m 下的逆元，那么運算 mm（ a,b,m） =a*b*R39。經(jīng)查閱相關(guān)數(shù)學著作，發(fā)現(xiàn)通常都是依據(jù)乘模的性質(zhì)nnbnanba m o d))m o d()m o d((m o d)( ??? ，先將冪模運算化簡為乘模運算。如果要計算1844674407370955161618446744073709551615，就類似于 10099： 00000001 00000000 00000000 ffffffff ffffffff = 0 0 1 ⑵ . 大數(shù)冪模與乘模運算 Montgomery 冪模算法 在實現(xiàn)了 CBigInt 類型后，大數(shù)的存儲和四則運算的功能都完成了。所以 1024 位的大數(shù)就是一個有 32 個元素的 unsigned long 數(shù)組。當然其優(yōu)點是算法符合人們的日常習慣，易于理解。而乘除法和取余也都是按照豎式運算的原理實現(xiàn)，并進行了必要的優(yōu)化。下面簡單介紹四則運算的實現(xiàn)原理。 2. 利用 MICROSOFT VISUAL C++平臺 從最初的 Visual C++ 到最近的 Visual C++.NET , Visual C++經(jīng)過近十年的發(fā)展，現(xiàn)已成為 Windows 操作系統(tǒng)環(huán)境下最主要，最權(quán)威的軟件開發(fā)工具。 軟件 二： ① 可以用指定密鑰以包含蒙哥馬利冪模運算的 RSA 算法加密簡單文本文件，加密生成的數(shù)據(jù)為純文本。 ② 可以用指定密鑰以 RSA算法加密簡單文本文件，加密生成的數(shù)據(jù)為純文本。 蒙哥馬利算法被認為是計算大數(shù)模乘的最快算法。蒙哥馬利算法是其中一種。 利用蒙哥馬利算法對 RSA冪模運算進行改進 由于進行的都是大數(shù)計算，使得 RSA 最快的情況也比 DES 慢上 百 倍，無論是軟件還是硬件實現(xiàn)。目前， RSA 的一些變種算法已被證明等價于大數(shù)分解。這些 API 內(nèi)部支持的算法不僅僅只有 RSA，但是 RSA 是數(shù)字簽名和證書中最常用的。 JCA (Java Cryptography Architecture)提供基本的加密框架，如證書、數(shù)字簽名、報文摘要和密鑰對產(chǎn)生器； JCA 由幾個實現(xiàn)了基本的加密技術(shù)功能的類和接口組成，其中最主要的是 包，此軟件包包含的是一組核心的類和接口， Java 中數(shù)字簽名的方法就集中在此軟件包中。另外，家喻戶曉的 IE瀏覽器，自然也實現(xiàn)了 SSL 協(xié)議，集成了使用 RSA 技術(shù)的加密功能，結(jié)合 MD5和 SHA1，主要用于數(shù)字證書和數(shù)字簽名，對于習慣于使用網(wǎng)上購物和網(wǎng)上銀行的用戶來說，幾乎天天都在使用 RSA 技術(shù)。加密連接、數(shù)字簽名和數(shù)字證書的核心算法廣泛使用 RSA。發(fā)展至今，電子安全領(lǐng)域的各方面已經(jīng)形成了較為完備的國際規(guī)范。 影響模乘運算速度關(guān)鍵在于模運算，模運算其實是除法運算，除運算相對與加減乘運算要費時的多。 當今公鑰加密更廣泛應用于互聯(lián)網(wǎng)身份認證，本課題將公鑰加密算法 RSA進行蒙哥馬利改進。雖然自 1978 年提出以來， RSA 的安全性一直未能得到理論上的證明，但它經(jīng)歷了各種攻擊，至今（ 2020 年）未被完全攻破。 目 錄 論文總 頁數(shù)： 22頁 前言 ....................................................................... 3 1 RSA應用現(xiàn)狀及蒙哥馬利模冪運算 ............................................ 4 RSA算法介紹與應用現(xiàn)狀 .................................................. 4 RSA算法加密的安全分析 .................................................. 5 利用蒙哥馬利算法對 RSA冪模運算進行改進 .................................. 5 2. RSA公鑰密碼加密軟件的設計與實現(xiàn) ......................................... 5 需求分析與總體設計 ...................................................... 5 功能分析 ........................................................... 6 工程方案選擇 ....................................................... 7 各部分的設計與開發(fā) ...................................................... 7 實現(xiàn) RSA加 密算法的 C++核心類庫 ...................................... 7 ................................................... 14 編寫測試各項性能需要的計時程序 ......................................... 14 測試數(shù)據(jù)與分析改進 ..................................................... 15 密鑰生成測試 ...................................................... 15 加解密測試 ........................................................ 16 性能分析與改進優(yōu)化 ..................................................... 17 參考文獻 .................................................................. 18 謝 辭 ..................................................... 錯誤 !未定義書簽。 RSA algorithm。本課題將 RSA 公鑰加密算法用蒙哥馬利算法實現(xiàn)。 畢業(yè)設計 ( 論文 ) RSA 公鑰密碼算法的一種快速實現(xiàn) 論文作者姓名： 申請學位專業(yè)： 申請學位類別： 指導教師姓名（職稱）： 論文提交日期： RSA 公鑰密碼算法的一種快速實現(xiàn) 摘 要 RSA 作為最重要的公開密鑰算法，在各領(lǐng)域的應用數(shù)不勝數(shù)。 蒙哥馬利算法對冪模運算的改進大大的提高了 RSA 的加解密效率。 關(guān)鍵詞 : RSA； RSA 算法；蒙哥馬利算法；加密；解密； A Rapid Way to Implement RSA Public Key Cryptography Algorithm Abstract The RSA encryption speed is very slow, and to apply it is difficult. So it constrained the development of the RSA algorithm. Modular multiplication is the speed bottleneck of algorithm in the whole using process. The advancing of Montgomery algorithm for the putation power module greatly improves the RSA encryption efficiency. The task implement RSA public key encryption algorithm with Montgomery algorithm. With the improvements of modular multiplication, it enhances the efficiency of RSA encryption. This paper mainly discusses the basic tes of RSA and the design and implementation of the correlation function. The development platform for RSA encryption algorithm is Microsoft Visual C + + . Key words: RSA。 Decryption。算法的名字以發(fā)明者的姓氏首字母命名： Ron Rivest, Adi Shamir 和 Leonard Adleman。網(wǎng)上交易加密連接、網(wǎng)上銀行身份驗證、各種信用卡使用的數(shù)字證書、智能移動電話和存儲卡的驗證功能芯片等，大多數(shù)使用 RSA 技術(shù)。蒙哥馬利算法是其中一種。 1 RSA 應用現(xiàn)狀及蒙哥馬利模冪運算