RSA加密算法初探
·前言
本文全面的介绍了RSA算法的概念、原理、证明和实现。我在写作本文之前在网上查阅过相关资料，可这些资料不是含糊其辞就是满篇谬误。所以我力求用通俗易懂的文字将算法深入剖析，用最严谨的步骤进行论相关的各项算法，以降低文章的阅读难度。读者只要学过初中代数就可以理解全文，我衷心希望更多读者能认识到加密算法其实并不难。
文中的算法均为伪代码，由于伪代码没有办法进行测试，再加上我个人数学功底比较薄弱，所以错漏之处在所难免，还请各位老师给予指教。质疑或指正请发送电子邮件到fireseed1949@hotmail.com，我会认真阅读并回复的！
感谢北航数学系（毕业）李桢老师、西工大计算机系（毕业）张小宁老师在数学上对我的指点。
另注：文中mod就是求余的符号，X mod Y表示X除以Y所得的余数。
·概述
RSA算法是世界上第一个既能用于数据加密也能用于数字签名的非对称性加密算法。它易于理解和操作，所以流行甚广。算法的名字以发明者的名字命名，他们是：Ron Rivest，Adi Shamir 和Leonard Adleman。虽然RSA的安全性一直未能得到理论上的证实，但它经历了各种攻击，至今未被完全攻破。为了让读者更容易的理解RSA加密，先大概讲述一下信息加密技术的相关概念和原理。
我们对于在数字媒体上进行交换的数据进行加密的方法称为信息交换加密技术，它分为两类，即对称加密和非对称加密。
在对称加密技术中，对信息的加密和解密都使用相同的钥，也就是说一把钥匙开一把锁。这种加密方法可简化加密处理过程，信息交换双方都不必彼此研究和交换专用的加密算法。如果在交换阶段私有密钥未曾泄露，那么机密性和报文完整性就可以得以保证。对称加密技术也存在一些不足，如果交换一方有N个交换对象，那么他就要维护N个私有密钥，对称加密存在的另一个问题是双方共享一把私有密钥，交换双方的任何信息都是通过这把密钥加密后传送给对方的。如三重DES是DES（数据加密标准）的一种变形，这种方法使用两个独立的56为密钥对信息进行3次加密，从而使有效密钥长度达到112位。
在非对称加密（或称公开密钥加密）体系中，密钥被分解为一对，即公开密钥（公钥）和私有密钥（私钥）。这对密钥中任何一把都可以作为公开密钥，通过非保密方式向他人公开，而另一把作为私有密钥，加以妥善保存。公开密钥用于加密，私有密钥用于解密，私有密钥只能由生成密钥的交换方掌握，公开密钥可广泛公布，但它只对应于生成密钥的交换方。非对称加密方式可以使通信双方无须事先交换密钥就可以建立安全通信，广泛应用于身份认证、数字签名等信息交换领域。非对称加密体系一般是建立在某些已知的数学难题之上，是计算机复杂性理论发展的必然结果。最具有代表性是RSA公钥密码体制。
在RSA算法中，我们先要获得两个不同的质数P和Q做为算法因子，再找出一个正整数E，使得E与 ( P - 1 ) * ( Q - 1 ) 的值互质，这个E就是私钥。找到一个整数D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立，D就是公钥1。设N为P和Q的乘积，N则为公钥2。加密时先将明文转换为一个或一组小于N的整数I，并计算ID mod N的值M，M就密文。解密时将密文ME mod N，也就是M的E次方再除以N所得的余数就是明文。
因为私钥E与( P - 1 ) * ( Q - 1 )互质，而公钥D使( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。破解者可以得到D和N，如果想要得到E，必须得出( P - 1 ) * ( Q - 1 )，因而必须先对N进行因数分解。如果N很大那么因数分解就会非常困难，所以要提高加密强度P和Q的数值大小起着决定性的因素。一般来讲当P和Q都大于2128时，按照目前的机算机处理速度破解基本已经不大可能了。
·证明
下面将会开始讨论RSA算法的原理及其算法证明。如果您只关心RSA算法的实现，则可以略过这一步。我把每一个有用的定理都用粗标标记了，对于数学不很在行的朋友可以只了解一下相关定理的说明而不需要验证求证过程了。
一、 费马小定理[1]的转化
费马小定理：有N为任意正整数，P为素数，且N不能被P整除，则有：
NP mod P = N
费马小定理可变形为：
NP - N mod P = 0
( N ( NP - 1 - 1 ) ) mod P = 0
因为
( N ( NP - 1 - 1 ) ) mod N = 0
所以N和P的公倍数为：
N ( NP - 1 - 1 ) （1）
又因为N与P互质，而互质数的最小公倍数为它们的乘积，所以一定存在正整数M使得：N ( NP - 1 - 1 ) = MNP成立。并化简为：
NP - 1 - 1 = MP
( NP - 1 - 1 ) mod P = 0
可以变形为：
NP - 1 mod P = 1 （2）
（2）就是费马小定理的转化定理，为方便叙述，下文简称为定理一。小提示，可能很多人认为费马小定理本来就是（2），实际上不是这样，因为费马小定理的转化非常容易，而转化定理又是一个无论在数学上还是计算机程序上都很常用的公式，所以人们就普遍认为（2）就是费马小定理了。
二、 积模分解公式
有X、Y和Z三个正整数，且X * Y大于Z，则有：
( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z
证明如下
当X和Y都比Z大时，可以将X和Y表示为：
X = ZI + A （1）
Y = ZJ + B （2）
将（1）和（2）代入( X * Y ) mod Z得：
( ( ZI + A )( ZJ + B ) ) mod Z
( Z( ZIJ + IA + IB ) + AB ) mod Z （3）
因为Z( ZIJ + IA + IB )是Z的整数倍，所以（3）式可化简为：
AB mod Z
因为A和B实际上是X和Y分别除以Z的余数，所以有：
( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z成立。
当X比Z大而Y比Z小时
X = ZI + A
代入( X * Y ) mod Z得：
( ZIY + AY ) mod Z
AY mod Z
因为A = X mod Z， 又因为Y mod Z = Y，所以有：
( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z成立。
同理，当X比Z小而Y比Z大时，上式也成立。
当X和Y都比Z小时，X = X mod Z，Y = Y mod Z所以有：
( X * Y ) mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z成立。
积模分解公式成立。
三、 定理二
有P和Q两个互质数，如果有X mod P = 0，X mod Q = 0，则有：X mod PQ = 0
证明：
因为P和Q互质，所以它们的公倍数为KPQ（K为整数），最小公倍数为PQ。又因为X为P和Q的公倍数，所以X / PQ = K，所以X mod PQ = 0。
四、 定理三
有P和Q两个互质数，设有整数X和Y满足Y mod P = X，Y mod Q = X，则有：Y mod PQ = X
证明：
X = Y mod P
可以表示为：
Y = X + kP
Y - X = kP
即Y - X可以被P整除，同理Y - X可以被Q整除。又因为P、Q互质，根据定理二可得：
( Y - X ) mod PQ = 0
即
Y mod PQ = X
五、 定理三的逆定理
有P和Q两个互质数，设有整数X和Y满足Y mod PQ = X ，则有：Y mod P = X，Y mod Q = X
证明：
Y mod PQ = X
可以表示为：
( Y – X ) mod PQ = 0
显然
( Y – X ) mod P = 0且
( Y – X ) mod Q = 0
所以原命题成立。