【正文】 在書寫本文時，軟件并未完成全面細致的優(yōu)化。 使用中國余數(shù)定理對于用RSA加密解密的一方，是計算。這里n＝pq，p和q是兩個二進制長度接近的大素數(shù)。由于用私密密鑰加密或解密的一方實際知道n的分解，即p和q，所以這一計算可以分解為以下兩部分分別進行 (附錄中有中國余數(shù)定理的簡單介紹) 。其中的CCdd2如下：根據(jù)RSA算法的要求，私密密鑰d的二進制長度接近n的長度，因此，d1和d2的二進制長度僅有n的一半左右，這樣就節(jié)省了大量的計算工作。最后，應(yīng)用中國余數(shù)定理就能計算出的值m。，其中.如果應(yīng)用中國余數(shù)定理計算冪模，主要工作花在計算上，計算CCdd2和m的運算與冪摸運算相比，計算時間較短可以不計。而位數(shù)對冪摸運算速度影響很大，因此分開計算比計算要快很多。經(jīng)過測試，使用中國余數(shù)定理來簡化一些冪模運算，速度比不使用中國余數(shù)定理時有很大的提高。在書寫本文時軟件中尚未使用中國余數(shù)定理。第4章 可移植模塊的簡要說明與開發(fā)前景，分層設(shè)計給移植帶來方便，下面簡要敘述各層可能的移植方式。①實現(xiàn)RSA加密算法的C++核心類庫，是基于C和C++的標準庫創(chuàng)建的，沒有用到C++泛型計算、STL相關(guān)內(nèi)容，代碼中沒有任何與操作系統(tǒng)相關(guān)的內(nèi)容。這是一種移植特性最好的程序模塊，因為現(xiàn)今多數(shù)非PC設(shè)備支持C++編譯。一般可以直接將本模塊交叉編譯給嵌入式設(shè)備，或在其他操作系統(tǒng)編譯使用。在編譯前，include 一行去掉，然后連同各自的頭文件拷貝出來，僅這四個文件即為實現(xiàn)RSA加密算法的C++類庫代碼。例如，可以將它們在linux操作系統(tǒng)用gcc編譯成程序模塊，把RSA加密功能提供給系統(tǒng)上的其他程序使用。②封裝C++核心類庫的DLL組件可以被Windows上的很多開發(fā)環(huán)境引用。例如在VB6，要使用這個組件，只需在程序最開始以引用win32api的方式引用即可，即public declare function XXX的形式。③。但是由于底層DLL組件的存在，使應(yīng)用局限于PC上的Windows系統(tǒng)。在此層的使用不僅限于窗體應(yīng)用程序，.Net類庫可以由服務(wù)器程序（諸如aspx）方便的引用，以BS（瀏覽器服務(wù)器）的模式提供給網(wǎng)絡(luò)上的用戶使用，所以此應(yīng)用程序可以通過簡單的修改用于數(shù)字證書和數(shù)字簽名等身份驗證系統(tǒng)。，將任意文件加密成文本有其重要的意義。因為此應(yīng)用程序是可以將任意文件加密成文本的，所以加密成的數(shù)據(jù)可以方便的在Internet上傳送。由此想到xml在Internet上攜帶數(shù)據(jù)的應(yīng)用模式。實際上，此軟件可以通過簡單的修改實現(xiàn)將任意文件加密為一定格式的xml文件。通過這種加密方式，可以滿足重要的小應(yīng)用程序等小型二進制數(shù)據(jù)在網(wǎng)絡(luò)上安全順利傳輸?shù)囊?。而且，通過加密的數(shù)據(jù)以xml方式傳送，使web應(yīng)用的靈活性更好，此方式甚至可以看作一種通用的小型二進制數(shù)據(jù)安全交換協(xié)議來開發(fā)。結(jié)束語RSA應(yīng)用于文件加密適合交流管理小型文件，將任意文件以非對稱密鑰加密成文本可以對其更方便的交流和管理，有廣闊的開發(fā)前景。本項目應(yīng)用的設(shè)計模式兼顧執(zhí)行效率和可復(fù)用性。整個項目開放源代碼和各種開發(fā)資料，便于引用和繼續(xù)開發(fā)。應(yīng)用本程序可以方便的在公眾論壇等環(huán)境交流要求高度安全的各種數(shù)據(jù)，包括任意二進制和文本文件。謝 辭感謝蔣萍花老師的細心指導(dǎo)和各論壇程序員朋友的支持與建議。參考文獻1．華羅庚，數(shù)論導(dǎo)引，科學(xué)出版社， 1979．2．Montgomery PL， Modular multiplication without trialdivision［J］， Mathematics of Computation， 1985， 44(170)：519521．3．Oh JH，Moon S J， Modular multiplication method［J］， IEE Proceedings：Computers and Digital Tech－niques， 1998， 145(4)：317318．4．施向東 董平，基于RSA算法的一種新的加密核設(shè)計，微計算機信息 2005年第123期 中圖分類號：TP289文章編號：10080570(2005)123003903 頁碼3941 5．[AX931] ANSI Digital Signatures using Reversible Public Key Cryptography for the Financial Services Industry (rDSA)， Appendix A， American National Standards Institute， 1998．6．[COCK73] Clifford Cocks. A Note on 39。NonSecret Encryption39。， CESG Research Report， 20 November 1973， ．7．[KALI93] Burton Kalinski. Some Examples of the PKCS Standards， RSA Laboratories， November 1993， ftp://．8．[PKCS1] RSA Laboratories. PKCS 1 : RSA Encryption Standard. June 2002， ftp://．9．[RIVE78] R. Rivest， A. Shamir and L. Adleman. A Method for Obtaining Digital Signatures and PublicKey Cryptosystems．Communications of the ACM， 21 (2)， pp. 120126， February 1978．10．陳發(fā)來，中國科學(xué)技術(shù)大學(xué)數(shù)學(xué)系 數(shù)學(xué)實驗——素數(shù) 附 錄本項目源代碼和已編譯程序以及開發(fā)文檔的下載地址由于本軟件代碼量稍大，不方便全部附于本文，所以這里只提供下載地址。本軟件已經(jīng)在各下載站發(fā)布，如果下述連接下載過慢，可以Google搜索RSA Encrypter直接下載。本項目全部源代碼也已經(jīng)在VC代碼庫發(fā)布。編譯好的軟件下載地址：源代碼下載地址：相關(guān)開發(fā)資源站點：(提供各層接口函數(shù)和各類成員函數(shù)文檔)軟件使用幫助：在C使用Windows public class HighResolutionTimer { private long start。 private long stop。 private long frequency。 public HighResolutionTimer() { QueryPerformanceFrequency (ref frequency)。 } public void Start () { QueryPerformanceCounter (ref start)。 } public void Stop () { QueryPerformanceCounter (ref stop)。 } public float ElapsedTime { get { float elapsed = (((float)(stop start)) / ((float) frequency))。 return elapsed。 } } [(, CharSet=)] private static extern bool QueryPerformanceCounter(ref long performanceCount)。 [(, CharSet=)] private static extern bool QueryPerformanceFrequency(ref long frequency)。 }加密解密測試時使用的兩組密鑰密鑰位數(shù)并不精確，可能有幾位的差距。512bit私有密鑰（兩行分別為d、n）11C6EBA27BEA0A998C517D522DAE7ADA203F7325576C97853584C9253CD867B0FD6217579F8240F7FCB7474F1B532B8532794605C704D94513B240700BF04C9195F9E4D3ABD729F6C7E7B7B6AF58DA89A10147DB6ADF0F4F3FA988E4C2441C2130C449852A68E19E32768FB3B41775DD4EF97F92674F3D21547249CD6D70C5512bit公開密鑰（兩行分別為e、n）C359195F9E4D3ABD729F6C7E7B7B6AF58DA89A10147DB6ADF0F4F3FA988E4C2441C2130C449852A68E19E32768FB3B41775DD4EF97F92674F3D21547249CD6D70C51024bit私有密鑰（兩行分別為d、n）79113601A430BCE489C6CBD825161014211DCC3D090D86C8F56E0F6324C0994A4E22596588C08B38354BA08C31DB6857BF919B8A67FDC0054A2C5BC783EEDEC3C1900A3AE66FAE1498562C6953FD9B7E0DD6EA515FE190D8123C31933328F79A5F1C63320499D09A4AC8F242E06F6BE903349570CE902197E6B24F3B8AB7D5990640C3AA06DEC9ED00B8C232812B96F51979338282E782E8A10C5650D162781AC030747B0DEF22C42078036DDC6D42BC5728F5300CD6EDA1FFEC01D1F0B4FC06117BEC185E6429CA536D7BFB9B7235C6CC42A5C50C0C4798A04705212FC345170DEAB00A03E27D26292B7DE39F63874DC4FEB13DBE9C40B6DB9B593869EFD31024bit公開密鑰（兩行分別為e、n）C35990640C3AA06DEC9ED00B8C232812B96F51979338282E782E8A10C5650D162781AC030747B0DEF22C42078036DDC6D42BC5728F5300CD6EDA1FFEC01D1F0B4FC06117BEC185E6429CA536D7BFB9B7235C6CC42A5C50C0C4798A04705212FC345170DEAB00A03E27D26292B7DE39F63874DC4FEB13DBE9C40B6DB9B593869EFD3RSA算法可行性的證明求證：命題11 若 p, q 是相異素數(shù), ed ＝ 1 mod (p1)(q1), a 是任意一個正整數(shù), 則有 c ＝ a mod (pq)證明：∵ de ＝ 1 mod (p1)(q1)∴ de ＝ k(p1)(q1) + 1, 其中 k 是整數(shù)∵ 在 mod 中是 preserve 乘法的 (x ＝ y mod z and u ＝ v mod z a xu ＝ yv mod z), ∴ 首先，素數(shù)p、q要么能整除a，要么與a互素。1. 如果 a 不是 p 的倍數(shù), 也不是 q 的倍數(shù)時, 則 (費馬小定理) a (根據(jù)質(zhì)數(shù)算術(shù)基本定理，a與素數(shù)p互素，則am也與p互素，m是整數(shù)) (費馬小定理) a ∴ p, q 均能整除 1 a pq | 1 即 ＝ 1 mod pq a c ＝ ＝ a mod pq 2. 如果 a 是 p 的倍數(shù), 但不是 q 的倍數(shù)時, 則 (費馬小定理) a ＝ 1 mod q a c ＝ ＝ a mod q a q | c a ∵ p | a a c ＝ ＝ 0 mod p a p | c a ∴ pq | c a a c ＝ a mod pq 3. 如果 a 是 q 的倍數(shù)，但不是 p 的倍數(shù)時，證明同2理顯然 4. 如果 a 同時是 p 和 q 的倍數(shù)時, 則 pq | a a c ＝ ＝ 0 mod pq a pq | c a a c ＝ a mod pq 證畢□ 費馬小定理敘述：e 是任一素數(shù), n 是任一整數(shù), 則 ＝ n mod e (即如果 n 和 e 互質(zhì), 則 ＝ 1 mod e) 運用群論知識可以證出費馬小定理。命題11說明 a 經(jīng)過編碼為 b 再經(jīng)過解碼為 c 時, a ＝ c mod n (n = pq)，但在做編碼解碼時, 由于限制 0 = a n, 0 = c n, 此時顯然 a ＝ c, 所以這個過程能做到編碼解碼的功能。中國余數(shù)定理的簡單介紹令n=n1n2...nk，其中ni是兩兩互質(zhì)的數(shù)，則對0=an與0=aini且ai=a mod ni，a與(a1,a2...,ak)之間有一種一一對應(yīng)的關(guān)系，一切對a的操作均可被等價的轉(zhuǎn)換為對對應(yīng)k元組中的每一元進行同樣的操作。因此我們可以將一種表達經(jīng)過簡單的轉(zhuǎn)換后得出另一種表達，其中從a到(a1,a2...,ak)的轉(zhuǎn)換十分容易，而從(a1,a2...,ak)推得對應(yīng)的a則要稍微復(fù)雜一些。 首先定義mi=n/ni(i=1,2...k)，則mi是除了ni以外的所有nj的乘積，接下來令ci=mi與模n意義下mi的逆元的積，則a為(a1c1+a2c2+...+akck) (mod n)。例如，已知a模5余2 且 模13余3，那么a1=2,n1=m2=