简介：

     RSA算法是著名和可靠的非对称密钥和加密算法。介绍RSA算法之前，先要知道素数的概念，因为这是RSA算法的基础。

素数就是只能被1和本身整除的数，1和2是素数，2以上的素数只能是奇数。

RSA算法就是基于这样的数学事实：两个大素数相乘很容易，而对得到的积求因子则很难。RSA中的私钥和公钥基于大素数（100位以上），算法本身很简单，但实际难度在于RSA选择和生成的私钥和公钥。

RSA运算结构：

如何生成私钥和公钥，如何用其进行加密和解密。

（1）选择两个大素数 P、Q

（2）计算 N = P * Q

（3）选择一个公钥（即加密密钥）E，使其不是(P-1)(Q-1)的因子

（4）选择私钥（即解密密钥）D，满足下列条件：
		（D * E)  mod （P-1) * (Q-1) = 1
		
（5）加密时，从明文PT计算密文CT如下:
		CT = PT^E mod N
		
（6）将密文CT发送给接收方

（7）解密时，从密文CT计算明文PT如下:
		PT = CT^D mod N

RSA示例：

（1）选择两个大素数 P、Q。
	设计P = 7,Q = 17
	
（2）计算N = P * Q
	得 N = 7 * 17 = 119
	
（3）选择一个公钥（即加密密钥）E，使其不是(P-1)(Q-1)的因子
	·求出(7-1)(17-1)=6*16=96
	·96的因子为2，2，2，2，2，3（因为96=2*2*2*2*2*3）
	·因此，E不能有因子2和3。例如，不能选择4（因为2是它的因子），15（因为3是它的因子）或6（2，2都是它的因子）
	·假设选择E为5.
	
（4）选择私钥（即解密密钥）D，满足下列条件：
	(D*E) mod (P-1)*(Q-1) = 1
	·将E、P、Q的值带入公式。
	·得到：（D*5) mod (7-1)(17-1) = 1
	·经过计算，取D=77。
	
（5）加密时，从明文PT计算密文CT如下：
	CT = PT^E mod N
	·假设要加密的明文10。则
	·CT = 10^5 mod 119 = 100000 mod 119 = 40
	
（6）将密文CT发送给接收方。
	将密文40发送给接收方
	
（7）解密时，从密文CT计算明文PT如下：
	PT = CT^D mod N
	计算如下:
	·PT = CT^D mod N
	·即PT = 40^77 mod 119 =10
	·解出明文

下面来看上面相同的示例，但稍有不同。

（1）取P=7,Q=17
（2）因此N=P*Q=119
（3）选择公钥E为5
（4）选择私钥D为77
	根据这些值，考虑上图所示的加密和解密过程。这里A是发送方，B是接收方。可以看出，可以用编码机制编码字母：
	A=1,B=2······Z=26。假设用这个机制编码字母，那么B的公钥为77（A和B知道），B的私钥为5（只有B知道）

	其工作如下，假设发送方A要向接收方B发送一个字母F。利用RSA算法，字母F编码如下：
	（1）用字母编号机制，F为6，因此将F的编码为6.
	（2）求这个数与指数为E的幂，即6^5.
	（3）计算6^5 mod 119，得到41，这是发送的加密信息
	接收方用下列方法解密41，得到初始密码F:
	（1）求这个数与指数为D的幂，即41^77
	（2）计算41^77 mod 119 得到6
	（3）按照字母编号机制得到F

了解RSA的关键

     根据实例的计算，可以看出RSA算法本身很简单，关键是选择正确定的密钥。假设B要接收A的保密信息，则要生成私钥(D)和公钥(E)，然后把公钥和数字N发给A。A用E和N加密消息，然后将加密信息发给B。B用私钥(D)解密消息。
     问题是，既然B能计算和求出D，别人也能计算和求出D，但并不容易，这就是RSA的关键所在。
     ***者只要知道公钥E和数字N，好像就可以通过试错法找到私钥D，但在实际中，P和Q选择很大的数，因此要从N求出P和Q并不容易。数学分析表明，N为100位时，要70对年才能求出P和Q。

RSA的安全性

     尽管到目前为止还没有关于成功***RSA的报道，但未来发生***的可能性不是没有。下面介绍一些针对RSA的可能***

明文***
     明文***又进一步分为如下三个子类型。

     （1）利用较短消息的***。假设***者知道一些明文块，如果是这样，那么***者就可以尝试对每个明文块进行加密，看看是否能得到已知的密文。要防止这种***，建议在对明文进行加密之前，进行一定的防护

     （2）周期性的***。这里，***者假设密文是通过以某种方式对明文进行置换而得到的。如果这种假设成立，那么***者就可以进行逆向处理，即不断对已知密文进行置换操作，以获得原来的明文。但是，对***者来说，这里的困难是，在使用这种方法时，***者并不知道哪些可以认为是正确的明文。因此，***者不断地对密文进行置换操作，直到得到密文本身，那么***者就可以知道，在得到原来密文地前一步所获得的文字肯定就是原来的明文。因此，这种***称为周期性***

     （3）利用公开消息的***。理论上，在极少情况下，加密所得的密文与原来的明文相同！如果是这样，那么原来的明文消息就不能隐藏了。这种***就称为利用公开消息的***。因此，在利用RSA进行加密后，在把密文发送给接收方之前，应确保密文与原来的明文是不同的

选定部分密文的***
     这种***中，***者使用扩展欧几里得算法，基于原来的密文，找出明文。

因数分解***
     RSA的整个安全性是基于这样一种假设：***者无法把数字N分解位两个引述P和Q。如果***者能够从等式N = P * Q中得到P和Q，那么***者就可以得到私钥，如前文所述，假设N是十进制的300位数字，***者要找到P和Q并不容易。

对加密密钥的***
     当公钥E数值很小时，RSA的运行会更快，导致出现潜在的***，这种***称为对加密密钥的***，因此，推荐使用E为65537或接近整个数的值。

对解密密钥的***
     这种***又可以进一步分为两类：
     （1）猜解解密值数的***。如果***者能够猜测出解密密钥D，那么不仅用相应的加密密钥E加密明文所得密文的危险，甚至后面的消息也危险。为防止这种***，建议发送方为P,Q,N，E使用不常用的值。
     （2）对较小解密指数的***。类似在加密密钥中所解释的那样，为解密密钥D使用较小数，可以使RSA运行更快。这将有助于***者在***时猜测出解密密钥D。