解晨

摘要：著名的非對稱密鑰加密系統(tǒng)——RSA公鑰加密系統(tǒng)，是當(dāng)今流行的加密系統(tǒng)，其簡單的實現(xiàn)和高效的保密性使RSA加密算法成為當(dāng)下最有影響力的公鑰加密算法，并且其堪稱完美的理論基礎(chǔ)使得RSA加密算法可以抵抗目前所知的所有密碼攻擊。該文探究了RSA加密算法的原理，并使用一門小眾語言Common Lisp對RSA加密進(jìn)行了實現(xiàn)。

關(guān)鍵詞：RSA加密算法；Common Lisp

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）08-1786-04

非對稱密鑰加密系統(tǒng)是由W.Diffie和M.Hellman在1976年發(fā)表的一篇論文中提出的，從那以后，非對稱密鑰加密就作為世界上兩種主要的加密類別之一而造福人類。

簡單來說，非對稱密鑰加密系統(tǒng)需要用兩個密鑰來完成整個加密的通訊過程，其中一個密鑰為私鑰，另一個則為公鑰。公鑰是公布于眾的一個加密密鑰，而私鑰則是為個人所持有，其他任何人都不能知曉。當(dāng)需要進(jìn)行加密通訊時，發(fā)送方首先用公鑰對信息進(jìn)行加密，然后再發(fā)給接收方，最后接收方用私鑰進(jìn)行解密從而完成通訊。

例如，A生成一對非對稱信息加密密鑰E和P，A將P公布于眾，則P就是公鑰，而E則由A自已保管，不讓他人知道。一旦有人要給A發(fā)信息，則發(fā)送信息的人使用公之于眾的公鑰P對信息進(jìn)行加密。因為唯一能解密的私鑰E只有A自已知道，所以對通過公鑰P進(jìn)行加密的信息也只有A能真正獲得其內(nèi)容，從而完成一次加密的通訊。

非對稱加密算法在目前來說雖然加密過程所用時間較長，但是瑕不掩瑜，其優(yōu)點還是極其值得稱贊，其保密性無話可說，不用用戶交換密鑰，也就從很大程度上防止了密鑰信息的泄露，并且使用簡單，只需公布公鑰即可。目前來說，非對稱加密算法主要用來加密重要的關(guān)鍵信息，并通常與對稱加密算法配合使用，從而增強(qiáng)信息保密的安全性。

RSA算法是最著名也是最經(jīng)典的非對稱加密算法，其保密性高，易于實現(xiàn)，理論基礎(chǔ)堪稱優(yōu)美簡潔。下面，就讓我們來對RSA算法一探究竟。

1 RSA算法分析

RSA算法是于1977年由三位學(xué)者Ron Rivest、Adi Shamirh和LenAdleman所開發(fā)，RSA這個名字取自三位學(xué)者的名稱首字母。

RSA的基本思想非常簡單，以數(shù)論中的模運(yùn)算為基礎(chǔ)來進(jìn)行加密和解密，同時，其高度的安全性基于以下事實：假設(shè)數(shù)A是由兩個大素數(shù)進(jìn)行相乘而得的一個數(shù)，在現(xiàn)有的計算條件下，對數(shù)A進(jìn)行分析得出其兩個大素數(shù)因子非常困難。

下面，讓我們來詳細(xì)分析一下RSA算法的加密通訊過程。

以數(shù)學(xué)上的角度為主來說，RSA可以分為以下幾個步驟：

首先，我們得到大素數(shù)P和Q。

下面，作者使用一種小種語言Common Lisp對RSA算法進(jìn)行實現(xiàn)。

2 RSA算法的Common Lisp實現(xiàn)

Common Lisp是函數(shù)式編程語言Lisp的最流行的方言，其非常適用于數(shù)學(xué)編程。用Common Lisp實現(xiàn)的程序代碼段極短，完全可以以簡潔的方式來表示任何程序。

在這里，作者利用Common Lisp語言來實現(xiàn)RSA算法的整個過程，原因主要有二：1）Common Lisp本身為函數(shù)是編程，其輸入的數(shù)字無大小限制，從廣義上來說，其輸入的內(nèi)容無限制，其變量的處理表達(dá)更靈活；2）Common Lisp實現(xiàn)的程序非常短小精干，可以以簡潔優(yōu)美的方式來表達(dá)RSA算法的數(shù)論算法過程。

下面，就跟著作者來逐步分析（本文中使用的Common Lisp編譯器為標(biāo)準(zhǔn)的Lisp in box）。

2.1 大素數(shù)生成

對于RSA算法，首要任務(wù)是實現(xiàn)兩個大素數(shù)的生成，即得到P和Q。在這里，我們使用一種幾乎可行的素數(shù)測試方法來獲得素數(shù)。

2.2 反復(fù)平方法

在數(shù)論中，求一個數(shù)的冪對另一個數(shù)的模的運(yùn)算是經(jīng)常出現(xiàn)的一種運(yùn)算，也被稱為模取冪。

一般來說，使用反復(fù)平方法便足以應(yīng)對所有大數(shù)的挑戰(zhàn)。

2.3 使用反復(fù)平方法實現(xiàn)的素數(shù)測試

測試用例中，作者使用了一個較小的測試數(shù)據(jù)和一個較大的測試數(shù)據(jù)進(jìn)行測試，皆得到了正確的結(jié)果。

3 總結(jié)

在本文中，作者對著名的RSA加密算法進(jìn)行了分析，并使用了一種非常方便的小眾語言Common Lisp對RSA算法進(jìn)行了實現(xiàn)。

RSA算法在目前來說是非常安全的，雖然有學(xué)者指出了其漏洞，并且也有學(xué)者指出其加密所耗時間太長，但是RSA仍在目前的信息安全領(lǐng)域中無可替代，RSA配合其他加密算法的使用，使之大展其優(yōu)勢。

然而，在不久的將來，當(dāng)新一代的計算機(jī)誕生時，也許RSA算法最終也會難免被淘汰，但是相信到時，一定會有更高效更安全的算法出現(xiàn)。

參考文獻(xiàn)：

[1] Thomas H.Cormen&Charles E.Leiserson&Ronald L.Rivest&Clifford Stein.算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2013.

[2] Peter Seibel.Pratcical Common Lisp[M].北京：人民郵電出版社，2011.

[3] Paul Graham.On Lisp[M].2007.

[4] Paul Graham.Hackers and Painters[M].北京：人民郵電出版社，2011.

[5] Robert Sedgewick.算法分析導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2006.

[6] Sara Baase.計算機(jī)算法-設(shè)計與分析導(dǎo)論[M].北京：高等教育出版社，2001.