基于Common Lisp的RSA加密实现

解晨

摘要：著名的非对称密钥加密系统——RSA公钥加密系统，是当今流行的加密系统，其简单的实现和高效的保密性使RSA加密算法成为当下最有影响力的公钥加密算法，并且其堪称完美的理论基础使得RSA加密算法可以抵抗目前所知的所有密码攻击。该文探究了RSA加密算法的原理，并使用一门小众语言Common Lisp对RSA加密进行了实现。

关键词：RSA加密算法；Common Lisp

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2013）08-1786-04

非对称密钥加密系统是由W.Diffie和M.Hellman在1976年发表的一篇论文中提出的，从那以后，非对称密钥加密就作为世界上两种主要的加密类别之一而造福人类。

简单来说，非对称密钥加密系统需要用两个密钥来完成整个加密的通讯过程，其中一个密钥为私钥，另一个则为公钥。公钥是公布于众的一个加密密钥，而私钥则是为个人所持有，其他任何人都不能知晓。当需要进行加密通讯时，发送方首先用公钥对信息进行加密，然后再发给接收方，最后接收方用私钥进行解密从而完成通讯。

例如，A生成一对非对称信息加密密钥E和P，A将P公布于众，则P就是公钥，而E则由A自已保管，不让他人知道。一旦有人要给A发信息，则发送信息的人使用公之于众的公钥P对信息进行加密。因为唯一能解密的私钥E只有A自已知道，所以对通过公钥P进行加密的信息也只有A能真正获得其内容，从而完成一次加密的通讯。

非对称加密算法在目前来说虽然加密过程所用时间较长，但是瑕不掩瑜，其优点还是极其值得称赞，其保密性无话可说，不用用户交换密钥，也就从很大程度上防止了密钥信息的泄露，并且使用简单，只需公布公钥即可。目前来说，非对称加密算法主要用来加密重要的关键信息，并通常与对称加密算法配合使用，从而增强信息保密的安全性。

RSA算法是最著名也是最经典的非对称加密算法，其保密性高，易于实现，理论基础堪称优美简洁。下面，就让我们来对RSA算法一探究竟。

1 RSA算法分析

RSA算法是于1977年由三位学者Ron Rivest、Adi Shamirh和LenAdleman所开发，RSA这个名字取自三位学者的名称首字母。

RSA的基本思想非常简单，以数论中的模运算为基础来进行加密和解密，同时，其高度的安全性基于以下事实：假设数A是由两个大素数进行相乘而得的一个数，在现有的计算条件下，对数A进行分析得出其两个大素数因子非常困难。

下面，让我们来详细分析一下RSA算法的加密通讯过程。

以数学上的角度为主来说，RSA可以分为以下几个步骤：

首先，我们得到大素数P和Q。

下面，作者使用一种小种语言Common Lisp对RSA算法进行实现。

2 RSA算法的Common Lisp实现

Common Lisp是函数式编程语言Lisp的最流行的方言，其非常适用于数学编程。用Common Lisp实现的程序代码段极短，完全可以以简洁的方式来表示任何程序。

在这里，作者利用Common Lisp语言来实现RSA算法的整个过程，原因主要有二：1）Common Lisp本身为函数是编程，其输入的数字无大小限制，从广义上来说，其输入的内容无限制，其变量的处理表达更灵活；2）Common Lisp实现的程序非常短小精干，可以以简洁优美的方式来表达RSA算法的数论算法过程。

下面，就跟着作者来逐步分析（本文中使用的Common Lisp编译器为标准的Lisp in box）。

2.1 大素数生成

对于RSA算法，首要任务是实现两个大素数的生成，即得到P和Q。在这里，我们使用一种几乎可行的素数测试方法来获得素数。

2.2 反复平方法

在数论中，求一个数的幂对另一个数的模的运算是经常出现的一种运算，也被称为模取幂。

一般来说，使用反复平方法便足以应对所有大数的挑战。

2.3 使用反复平方法实现的素数测试

测试用例中，作者使用了一个较小的测试数据和一个较大的测试数据进行测试，皆得到了正确的结果。

3 总结

在本文中，作者对著名的RSA加密算法进行了分析，并使用了一种非常方便的小众语言Common Lisp对RSA算法进行了实现。

RSA算法在目前来说是非常安全的，虽然有学者指出了其漏洞，并且也有学者指出其加密所耗时间太长，但是RSA仍在目前的信息安全领域中无可替代，RSA配合其他加密算法的使用，使之大展其优势。

然而，在不久的将来，当新一代的计算机诞生时，也许RSA算法最终也会难免被淘汰，但是相信到时，一定会有更高效更安全的算法出现。

参考文献：

[1] Thomas H.Cormen&Charles E.Leiserson&Ronald L.Rivest&Clifford Stein.算法导论[M].北京：机械工业出版社，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.算法分析导论[M].北京：机械工业出版社，2006.

[6] Sara Baase.计算机算法-设计与分析导论[M].北京：高等教育出版社，2001.