密碼學(xué)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告

1、課 程 設(shè) 計(jì) 報(bào) 告科目： 密碼學(xué) 院系名稱： 計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè)班級(jí)： 信安1001班 學(xué) 號(hào)： U201014627 姓 名： 江 雪 指導(dǎo)教師： 湯學(xué)明 崔永泉 駱婷 報(bào)告日期： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院目 錄第一部分 數(shù)據(jù)加密標(biāo)準(zhǔn)DES3一、 實(shí)驗(yàn)?zāi)康?二、 實(shí)驗(yàn)題目及要求32.1 DES的編程實(shí)現(xiàn)32.2 DES的短塊處理32.3 DES弱密鑰過(guò)濾軟件設(shè)計(jì)32.4 DES密鑰差分攻擊設(shè)計(jì)4三、 實(shí)驗(yàn)原理43.1 DES基礎(chǔ)知識(shí)43.2 DES加解密過(guò)程43.3 DES弱密鑰93.4 6圈DES差分攻擊原理10四、 實(shí)驗(yàn)環(huán)境11五、 實(shí)驗(yàn)設(shè)計(jì)125.1 DES的編程實(shí)現(xiàn)和整體界面設(shè)計(jì)

2、125.2 DES短塊處理125.3 DES弱密鑰過(guò)濾145.4 DES差分攻擊14六、 實(shí)驗(yàn)結(jié)果156.1 DES編程實(shí)現(xiàn)156.2 DES短塊處理156.3 DES弱密鑰檢測(cè)176.4 DES差分攻擊18第二部分 公鑰密碼RSA20一、 實(shí)驗(yàn)?zāi)康?0二、 實(shí)驗(yàn)題目及要求20三、 實(shí)驗(yàn)原理203.1 RSA算法的加解密原理213.2 RSA算法的快速加解密原理21四、 實(shí)驗(yàn)環(huán)境23五、 實(shí)驗(yàn)設(shè)計(jì)245.1 RSA加解密245.2 RSA快速加解密24六、 實(shí)驗(yàn)結(jié)果24實(shí)驗(yàn)體會(huì)27參考文獻(xiàn)27第一部分 數(shù)據(jù)加密標(biāo)準(zhǔn)DES1、 實(shí)驗(yàn)?zāi)康?1、掌握DES中各加密函數(shù)對(duì)其性能影響； 2、DES的特性

3、分析，包括互補(bǔ)性和弱密鑰； 3、DES的實(shí)際應(yīng)用，包括各種數(shù)據(jù)類型的加/脫密、DES的短塊處理。2、 實(shí)驗(yàn)題目及要求2.1 DES的編程實(shí)現(xiàn)輸入加密密鑰和一串有意義的漢字，顯示相應(yīng)的加密結(jié)果；輸入密文和脫密密鑰，顯示所還原的一串有意義的漢字； 設(shè)計(jì)用戶界面，界面中要有加/脫密選擇、輸入明/密文欄、密鑰欄和加/脫密結(jié)果顯示欄。2.2 DES的短塊處理針對(duì)有短塊和無(wú)短塊二種情況，編寫并實(shí)現(xiàn)具有短塊處理功能的DES通用加/脫密軟件；短塊處理對(duì)用戶透明；設(shè)計(jì)用戶界面，其結(jié)構(gòu)與實(shí)驗(yàn)1的用戶界面基本相同，但要增設(shè)明文長(zhǎng)度和密文長(zhǎng)度欄。2.3 DES弱密鑰過(guò)濾軟件設(shè)計(jì) 設(shè)計(jì)用戶界面，當(dāng)用戶輸入弱密鑰時(shí)會(huì)出現(xiàn)

4、提示信息；編制過(guò)濾程序，實(shí)現(xiàn)對(duì)弱密鑰的過(guò)濾。2.4 DES密鑰差分攻擊設(shè)計(jì) 輸入一串密鑰，進(jìn)行6輪DES差分攻擊，將攻擊結(jié)果與原密鑰比較。3、 實(shí)驗(yàn)原理3.1 DES基礎(chǔ)知識(shí)DES算法是由美國(guó)IBM公司在20世紀(jì)70年代提出，并被美國(guó)政府、美國(guó)國(guó)家標(biāo)準(zhǔn)局和美國(guó)國(guó)家標(biāo)準(zhǔn)協(xié)會(huì)采納和承認(rèn)的一種標(biāo)準(zhǔn)加密算法。它屬于分組加密算法，即在明文加密和密文解密過(guò)程中，信息都是按照固定長(zhǎng)度分組后進(jìn)行處理的。混淆和擴(kuò)散是它采用的兩個(gè)最重要的安全特性?；煜侵竿ㄟ^(guò)密碼算法使明文和密文以及密鑰的關(guān)系非常復(fù)雜，無(wú)法從數(shù)學(xué)上描述或者統(tǒng)計(jì)。擴(kuò)散是指明文和密鑰中每一位信息的變動(dòng)，都會(huì)影響到密文中許多位信息的變動(dòng)，從而隱藏統(tǒng)計(jì)上

5、的特性，增加密碼的安全。3.2 DES加解密過(guò)程DES算法將明文分成64位大小的眾多數(shù)據(jù)塊，即分組長(zhǎng)度為64位，同時(shí)用56位密鑰對(duì)64位明文信息加密，最終形成64位的密文。如果明文長(zhǎng)度不足64位，則將其擴(kuò)展為64位（如補(bǔ)零等方法）。具體加密過(guò)程首先是將輸入的數(shù)據(jù)進(jìn)行初始換位（IP），即將明文M中數(shù)據(jù)的排列順序按一定的規(guī)則重新排列，生成新的數(shù)據(jù)序列，以打亂原來(lái)的次序。然后將變換后的數(shù)據(jù)平分成左右兩部分，左邊記為L(zhǎng)0，右邊記為R0，然后對(duì)R0實(shí)行在子密鑰（由加密密鑰產(chǎn)生）控制下的變換f，結(jié)果記為，再與L0做逐位異或運(yùn)算，其結(jié)果記為R1，R0則作為下一輪的L1。如此循環(huán)16輪，最后得到L16、R16

6、。再對(duì)L16、R16實(shí)行逆初始置換IP-1，即可得到加密數(shù)據(jù)。解密過(guò)程與此類似，不同之處僅在于子密鑰的使用順序正好相反。DES全部16輪的加密過(guò)程如圖所示。圖3.1 DES加密流程圖DES的加密算法包括3個(gè)基本函數(shù)。1初始換位（IP）它的作用是把輸入的64位數(shù)據(jù)塊的排列順序打亂，每位數(shù)據(jù)按照下面換位規(guī)則重新組合，即將第58位換到第1位，第50位換到第2位，依次類推，重組后的64位輸出分為L(zhǎng)0、R0（左、右）兩部分，每部分分別為32位。58，50，42，36，18，10，2，60，52，44，36，28，20，12，4，62，54，46，38，30，22，14，6，64，56，48，40，32，

7、24，16，8，57，49，41，33，25，17，9，1，59，51，43，35，27，19，11，3，61，53，45，37，29，21，13，5，63，55，47，39，31，23，15，7，R0和K1經(jīng)過(guò)變換后的輸出結(jié)果，再和L0進(jìn)行異或運(yùn)算，輸出結(jié)果做為R1，R0則賦給L1。L1和R1同樣再做類似運(yùn)算生成L2和R2，經(jīng)過(guò)16次運(yùn)算后生成L16的R16。2f函數(shù)f函數(shù)是多個(gè)置換函數(shù)和替代函數(shù)的組合函數(shù)，它將32位比特的輸入變換為32位的輸出，如圖所示。圖3.2 DES算法中f函數(shù)的處理流程圖Ri經(jīng)過(guò)擴(kuò)展運(yùn)算E變換（表）后擴(kuò)展為48位的，與Ki+1進(jìn)行異或運(yùn)算后輸出的結(jié)果分成8組，每組6

8、比特的并聯(lián)B，B=B1B2B3B4B5B6B7B8，再經(jīng)過(guò)8個(gè)S盒（表）的選擇壓縮運(yùn)算轉(zhuǎn)換為4位，8個(gè)4位合并為32位后再經(jīng)過(guò)P變換（表）輸出為32位的。其中，擴(kuò)展運(yùn)算E與置換P主要作用是增加算法的擴(kuò)展效果。 表3.1 擴(kuò)展運(yùn)算E 表3.2 P變換 表3.3 DES的S盒 DES具體的子密鑰產(chǎn)生流程如圖3.3所示。圖3.3 DES子密鑰產(chǎn)生流程輸入的初始密鑰值為64位，但DES算法規(guī)定，其中第8、16、.64位是奇偶校驗(yàn)位，不參與DES運(yùn)算。所以，實(shí)際可用位數(shù)只有56位，經(jīng)過(guò)縮小選擇換位表1（表）即密鑰置換PC-1的變換后，初始密鑰的位數(shù)由64 位變成了56位，將其平分為兩部分C0、D0，然后

9、分別進(jìn)行第1次循環(huán)左移，得到C1、D1，將C1（28位）、D1（28位）合并后得到56位的輸出結(jié)果，再經(jīng)過(guò)縮小選擇換位表2（表）即密鑰置換PC-2，從而便得到了密鑰K1（48位）。依此類推，便可得到K2、. K16，需要注意的是，16次循環(huán)左移對(duì)應(yīng)的左移位數(shù)要依據(jù)表中規(guī)則進(jìn)行。表3.1 左移位數(shù)規(guī)則 表3.2 縮小選擇換位表1 表3.3 縮小選擇換位表23逆初始置換函數(shù)IP-1它將L16和R16作為輸入，進(jìn)行逆初始換位得到密文輸出。逆初始換位是初始位的逆運(yùn)算，換位規(guī)則如下所列：40，8，48，16，56，24，64，32，39，7，47，15，55，23，63，3138，6，46，14，54，

10、22，62，30，37，5，45，13，53，21，61，2936，4，44，12，52，20，60，28，35，3，43，11，51，19，59，2734，2，42，10，50，18，58，26，33，1，41，9，49，17，57，253.3 DES弱密鑰DES的解密過(guò)程和DES的加密過(guò)程完全類似，只不過(guò)將16圈的子密鑰序列K1，K2K16的順序倒過(guò)來(lái)。即第一圈用第16個(gè)子密鑰K16，第二圈用K15，其余類推。       如果K16K1，K15K2，K9K8，則加密所用的子密鑰與解密所用的子密鑰相同，對(duì)一個(gè)明文X加密兩

11、次，得到的還是明文X。       更強(qiáng)的，若K1K2K16，則加密過(guò)程與解密過(guò)程完全一樣。       弱密鑰的定義也就是這樣定義：若k使得加密函數(shù)與解密函數(shù)一致，則稱k為弱密鑰。DES至少有4個(gè)弱密鑰，讓我們先來(lái)看看子密鑰的產(chǎn)生過(guò)程：64Bits的密鑰K經(jīng)PC-1之后，變?yōu)?6Bits，然后分為高28Bits和低28Bits，分別進(jìn)行移位。 LSi是循環(huán)左移。PC-2是從56Bits中選出48Bits輸出。若C0和D0為全0或全1，則經(jīng)過(guò)移位后顯然不變

12、，于是16個(gè)子密鑰都相同。C0和D0是獨(dú)立進(jìn)行移位的，組合一下，就有4個(gè)弱密鑰了。因此至少有4個(gè)弱密鑰。(1)K1K160x000000000000 (2)K1K160xFFFFFFFFFFFF(3)K1K160x000000FFFFFF (4)K1K160xFFFFFF000000檢測(cè)16個(gè)內(nèi)部密鑰是否完全相同，若完全相同則判斷為弱密鑰，否則為正常密鑰。3.4 6圈DES差分攻擊原理圖3.4 略去初始置換和末置換的3輪DES 我們先看3輪DES差分攻擊的原理：破解條件：已知一組明文E1、E2，以及對(duì)應(yīng)的密文C1、C2，其中E1和E2的低32bit相同。令E1.L0表示E1的高32bit, E

13、1.R0表示E1的低32bit, 同理E1.L1表示E1加密一圈后的高32bit，其它的數(shù)據(jù)同理表示。基本結(jié)論：置換傳遞差分；E擴(kuò)展傳遞差分；異或傳遞差分；如圖所示，設(shè)E1加密到位置1的值為E1.pos1，E1加密到位置2的值為E2.pos2。K3 = E1.pos1 E1.pos2 或者 K3 = E2.pos1 根據(jù)已知條件，位置1的值很容易獲得，關(guān)鍵是求出位置2的值或者位置2的值的可能情況。根據(jù)基本結(jié)論，對(duì)于這組數(shù)據(jù)，位置2和位置3的差分容易獲得：E1.pos1 = E(E1.R2) = E(C1.L3)（密文C1高32bit的E擴(kuò)展）E2.pos1 = E(E2.R2) = E(C2.

14、L3)（密文C2高32bit的E擴(kuò)展）E1.pos2 E2.pos2 = E1.pos1 E2.pos1 = E(C1.L3) E(C2.L3)E1.pos3 E2.pos3 = DeP(E1.L2 E1.R3) DeP(E2.L2 E2.R3) = DeP(C1.R3 C2.R3 E1.R1 E2.R0=0)E2.L0)(DeP為P的逆置換)這樣位置2和位置3的差分都可以求解得到，根據(jù)S盒構(gòu)造如下一張表，列舉出所有可能的E1.pos2情況，可以通過(guò)多組數(shù)據(jù)，匹配重疊的情況，就可以求解出K3或者K3可能的情況，由K3可以獲得K的48bit，對(duì)于剩余的8bit可以窮舉搜索得到。差分表如下形式（對(duì)

15、于每個(gè)S盒）：X1X2Y1Y2X1可能的值列表對(duì)于6圈DES來(lái)說(shuō)，和3輪基本類似。問(wèn)題是對(duì)于6輪的攻擊，假設(shè)的輸出異或是正確的概率僅為1/16。如果我們從特征的正確對(duì)開始運(yùn)作，則正確密鑰Ji一定在testi中。如果從特征的錯(cuò)誤對(duì)開始運(yùn)作，由于Ci。錯(cuò)誤，因此testi可假設(shè)為隨機(jī)的。4、 實(shí)驗(yàn)環(huán)境操作系統(tǒng)：Windows 7編程工具：QT Creator5、 實(shí)驗(yàn)設(shè)計(jì)5.1 DES的編程實(shí)現(xiàn)和整體界面設(shè)計(jì)DES算法的編程實(shí)現(xiàn)現(xiàn)在已經(jīng)非常普遍了，所以這一部分我是直接從網(wǎng)上拷貝下來(lái)的程序，經(jīng)過(guò)自己的修改調(diào)試，再加上RSA的一部分，最終界面如圖5.1所示。圖5.1 界面效果預(yù)覽圖5.2 DES短塊處

16、理短塊處理采用了兩種方式：填充方式和密文挪用。在填充方式下，如果最后一個(gè)塊長(zhǎng)度不滿8字節(jié)，則在后面填充0，并在最后一個(gè)字節(jié)放上填充0的數(shù)目。在密文挪用方式下，把最后一個(gè)不滿8字節(jié)的塊和前面一個(gè)加密后的塊拼接成8字節(jié)再加密。如圖5.2所示。圖 密文挪用原理示意圖核心代碼如下：if (mode = FillMode) if (count) memset(plainBlock + count, '0', 7-count); plainBlock7 = 8 - count; DESEncryptBlock(plainBlock, subKeys, cipherBlock); outFi

17、le.write(cipherBlock, 8); else if (mode = PeculateMode) if (inFile.size() < 8) SetLastError(QString("密文挪用方式下明文長(zhǎng)度必須大于8！"); return false; if (count) for (int i = 0; i < 8-count; +i) tempBlocki = cipherBlockcount+i; for (int i = 0; i < count; +i) tempBlock8-count+i = plainBlocki; DES

18、EncryptBlock(tempBlock, subKeys, cipherBlock); outFile.seek(outFile.pos()+count-8); outFile.write(cipherBlock, 8); 5.3 DES弱密鑰過(guò)濾在DES程序中加入一個(gè)弱密鑰檢測(cè)函數(shù)，通過(guò)檢測(cè)其16個(gè)內(nèi)部密鑰是否相同，來(lái)判斷所輸入的密鑰是否為弱密鑰。核心代碼如下：bool isWeakKey(char subKeys1648) for (int i = 1; i < 16; +i) for (int j = 0; j < 24; +j) if (subKeys0j != su

19、bKeysij) return false; return true;5.4 DES差分攻擊 在6圈DES差分攻擊中，我們采用了以下兩個(gè)圈特征：40080000 04000000X；00200008 00000400X。這兩個(gè)特征中每個(gè)特征都找到K 6 的30 bit 的子密鑰。它們?cè)诘? 圈分別有5 個(gè)S 盒的輸入異或?yàn)?，根據(jù)差分的性質(zhì)，其輸出異或也為0，其中第一個(gè) 的5 個(gè)S 盒為S 2, S 5, S 6, S 7, S 8，第二個(gè)的5個(gè)S盒為S1,S2,S4,S5,S6 ，使用兩個(gè)圈特征，就能找到K 6 的42 bit 的子密鑰。余下的14bit 可以采用窮舉的方法找到。6、 實(shí)驗(yàn)結(jié)

20、果6.1 DES編程實(shí)現(xiàn)運(yùn)行程序，進(jìn)入DES加解密界面，如圖所示：圖6.1 DES加解密界面6.2 DES短塊處理6.2.1 填充方式 在輸入數(shù)據(jù)框中輸入明文，選擇輸入數(shù)據(jù)操作和填充，加密結(jié)果如圖6.2所示，明、密文長(zhǎng)度分別為10、16。圖6.2 填充方式加密解密時(shí)，把密文復(fù)制到輸入數(shù)據(jù)框中。如圖6.3所示，成功解密，明文長(zhǎng)度和密文長(zhǎng)度不變。圖6.3 填充方式解密6.2.2 密文挪用采用密文挪用加解密時(shí)，只需要將“填充”改為選擇“密文挪用”即可，加密結(jié)果如圖6.4所示，解密結(jié)果如圖6.5所示。可以看到，明、密文的長(zhǎng)度均為14，符合密文挪用的特點(diǎn)。圖6.4 密文挪用加密圖6.5 密文挪用解密6.

21、3 DES弱密鑰檢測(cè)如果輸入的是弱密鑰，在加解密時(shí)會(huì)被檢測(cè)出來(lái)，并彈出提示框，如圖6.6所示。圖6.6 弱密鑰檢測(cè)6.4 DES差分攻擊在主界面中選擇“6圈DES差分攻擊”，如圖6.7所示。圖6.7 DES差分攻擊界面設(shè)置密鑰為，如圖6.8.圖6.8 設(shè)置密鑰 點(diǎn)擊“破解密鑰”，結(jié)果如圖6.9所示。圖6.9 破解密鑰第二部分 公鑰密碼RSA1、 實(shí)驗(yàn)?zāi)康?1、通過(guò)實(shí)際編程掌握非對(duì)稱密碼算法RSA的加密和解密以及快速加、解密過(guò)程，加深對(duì)非對(duì)稱密碼算法的認(rèn)識(shí)； 2、實(shí)現(xiàn)對(duì)RSA的解密密鑰攻擊。2、 實(shí)驗(yàn)題目及要求1、編制或網(wǎng)上下載大素?cái)?shù)生成算法，產(chǎn)生二個(gè)大素?cái)?shù)p和q；2、編寫RSA的加/解密過(guò)程和

22、快速加/解密過(guò)程；3、通過(guò)調(diào)用時(shí)鐘對(duì)二種加/解密方法的時(shí)間開銷進(jìn)行測(cè)試；4、設(shè)計(jì)用戶界面，界面要有加/解密方式選擇，快速方式與一般方式的選擇及時(shí)間開銷顯示。3、 實(shí)驗(yàn)原理前面講的對(duì)稱密碼算法要求通信雙方通過(guò)交換密鑰實(shí)現(xiàn)使用同一個(gè)密鑰，這在密鑰的管理、發(fā)布和安全性方面存在很多問(wèn)題，而非對(duì)稱密碼算法解決了這個(gè)問(wèn)題。非對(duì)稱密碼算法是指一個(gè)加密系統(tǒng)的加密密鑰和解密密鑰是不同的，或者說(shuō)不能用其中一個(gè)推導(dǎo)出另一個(gè)。在非對(duì)稱密碼算法的兩個(gè)密鑰中，一個(gè)是用于加密的密鑰，它是可以公開的，稱為公鑰；另一個(gè)是用于解密的密鑰，是保密的，稱為私鑰。非對(duì)稱密碼算法解決了對(duì)稱密碼體制中密鑰管理的難題，并提供了對(duì)信息發(fā)送人的

23、身份進(jìn)行驗(yàn)證手段，是現(xiàn)代密碼學(xué)最重要的發(fā)明。RSA密碼體制是目前為止最成功的非對(duì)稱密碼算法，它是在1977年由Rivest、Shamir和Adleman提出的第一個(gè)比較完善的非對(duì)稱密碼算法。它的安全性是建立在“大數(shù)分解和素性檢測(cè)”這個(gè)數(shù)論難題的基礎(chǔ)上，即將兩個(gè)大素?cái)?shù)相乘在計(jì)算上容易實(shí)現(xiàn)，而將該乘積分解為兩個(gè)大素?cái)?shù)因子的計(jì)算量相當(dāng)大。雖然它的安全性還未能得到理論證明，但經(jīng)過(guò)20多年的密碼分析和攻擊，迄今仍然被實(shí)踐證明是安全的。3.1 RSA算法的加解密原理1公鑰選擇兩個(gè)互異的大素?cái)?shù)p和q，n是二者的乘積，即n=pq，使為歐拉函數(shù)。隨機(jī)選取正整數(shù)e，使其滿足，即e和互質(zhì)，則將作為公鑰。2私鑰求出正

24、數(shù)d，使其滿足，則將(n,d)作為私鑰。3加密算法對(duì)于明文M，由，得到密文C。4解密算法對(duì)于密文C，由，得到明文M。如果竊密者獲得了n、e和密文C，為了破解密文必須計(jì)算出私鑰d，為此需要先分解n。為了提高破解難度，達(dá)到更高的安全性，一般商業(yè)應(yīng)用要求n的長(zhǎng)度不小于1024位，更重要的場(chǎng)合不小于2048位。3.2 RSA算法的快速加解密原理3.2.1 模重復(fù)平方在計(jì)算時(shí)，將K化成二進(jìn)制序列，則由此將乘法次數(shù)由下降至。模重復(fù)平方法是加快RSA運(yùn)算速度的主要手段。3.2.2 中國(guó)剩余定理中國(guó)剩余定理用在RSA解密過(guò)程中，可以大大提高解密速度，對(duì)加密無(wú)效。中國(guó)剩余定理(ChineseRemainderT

25、heorem,CRT)是初等數(shù)論中重要的基本定理之一，它主要是刻畫剩余系的結(jié)構(gòu)和求解形如xdi(modpi)(1is)的一次同余式方程組。定理  (CRT)3，4，5設(shè)p1，p2，ps是兩兩互素的正整數(shù)，即GCD(pi，pj)=1(ij)，對(duì)于任意整數(shù)d1，d2，ds(0dipi-1，i=1，2，s)，同余式方程組：    xd1(modp1)xd2(modp2)xds(modps)有惟一解。計(jì)算數(shù)論中，計(jì)算中國(guó)剩余定理惟一解的方法有兩種：?jiǎn)位鶖?shù)轉(zhuǎn)換法(Single2RadexConversion，SRC)和混合基數(shù)轉(zhuǎn)換法(Mixed2Rade

26、xConver2sion，MRC)，這兩種方法都是非常實(shí)用的計(jì)算方法。這里我們略過(guò)單基數(shù)轉(zhuǎn)換法不談，直說(shuō)混合基數(shù)轉(zhuǎn)換法。利用混合基數(shù)轉(zhuǎn)換法(MRC)求CRT惟一解的方法是H.L.Garner在1958年首先提出的。之后，并進(jìn)行了有益的改進(jìn)。經(jīng)Kunth改進(jìn)后的MRC方法用算法描述如下：算法1  CRT的混合基數(shù)轉(zhuǎn)換法(MRC)3。(1) 計(jì)算Bjip-1j(modpi)，(1j<is)；(2)分別計(jì)算v1d1(modp1)；v2(d2-v1)B12(modp2)；vs(ds-(v1+p1(v2+p2(v3+ps-2vs-1)B1sB2sB(s-1)s(mod ps).(3)計(jì)算

27、惟一解Xvsps-1p2p1+v3p2p1+v2p1+v1。在上述算法的第(2)步中，感覺(jué)上計(jì)算v1，v2，vs的過(guò)程好象比較雜亂,不容易實(shí)現(xiàn)。其實(shí)不然,深入分析各式，發(fā)現(xiàn)其中隱含著遞歸成分，很容易利用遞歸公式完成相應(yīng)計(jì)算。在此基礎(chǔ)上有以下改進(jìn)的算法：算法2  改進(jìn)的MRC算法(MMRC)。(1)計(jì)算Bjip-1j(modpi),(1j<is)；(2)令ai1=di(1is),由遞歸公式ai(j+1)=(aij-ajj)Bji(modpi),1j<is。計(jì)算出三角形數(shù)值表斜邊上的數(shù)值(即a11，a22，ass)；(3)計(jì)算惟一解xa11+a22p1+a33p1p2+assp1p2p3ps。由于利用MMRC的解密算法是實(shí)現(xiàn)RSA解密的最佳算法，它使RSA的解密速度加快大約4倍，可大大提高用于RSA的軟硬件解密實(shí)現(xiàn)。故我們采用MMRC算法。算法描述如下：(1)計(jì)算d1d(modp-1)與d2d(modq-1)；(2)計(jì)算C1c(modp)與C2c(modq)；(3)計(jì)算M1Cd11(modp)與M2Cd22(modq)；(4)計(jì)算Bp-1(modq)；(5)計(jì)算mM1+(M2-M1)*B(modq)