基于Common Lisp的RSA加密實(shí)現(xiàn)

解晨

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

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

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

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

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

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

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

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

1 RSA算法分析

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

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

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

以數(shù)學(xué)上的角度為主來(lái)說(shuō)，RSA可以分為以下幾個(gè)步驟：

首先，我們得到大素?cái)?shù)P和Q。

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

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

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

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

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

2.1 大素?cái)?shù)生成

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

2.2 反復(fù)平方法

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

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

2.3 使用反復(fù)平方法實(shí)現(xiàn)的素?cái)?shù)測(cè)試

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

3 總結(jié)

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

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

然而，在不久的將來(lái)，當(dāng)新一代的計(jì)算機(jī)誕生時(shí)，也許RSA算法最終也會(huì)難免被淘汰，但是相信到時(shí)，一定會(huì)有更高效更安全的算法出現(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ì)算機(jī)算法-設(shè)計(jì)與分析導(dǎo)論[M].北京：高等教育出版社，2001.