| RSA算法是非对称算法，由Ronald Rivest、Adi Shamir、Leonard Adleman三人共同在1977年公开发表。在RSA加密算法中，公钥和私钥都可以用于加密消息，用于加密消息的密钥与用于解密消息的密钥相反。RSA算法提供了一种保护网络通信和数据存储的机密性、完整性、真实性和不可否认性的方法。目前，SSH、OpenPGP、S/MIME和SSL/TLS都依赖于RSA进行加密和数字签名功能。RSA算法在浏览器中使用，能够在不可信任的互联网中建立安全连接。RSA签名验证是网络连接系统中最常见的执行操作之一。
|
|
|
| RSA算法基于大整数因子分解的困难性，该算法的步骤如下：
|
|
|
|
|
|
|
| 第三步，计算小于n并且与n互素的整数的个数，即欧拉函数φ(n)=(p-1)(q-1)。
|
|
|
| 第四步，选取一个随机数e，且满足1<e<φ(n)，并且e和φ(n)互素，即gcd(e，φ(n))=1。
|
|
|
|
|
| 第六步，保密d、p和q，而公开n和e，即d作为私钥，而n和e作为公钥。
|
|
|
| 下面，举一个RSA加密的具体实例。设素数p=3，q=17，并令e=13，则RSA的加密操作如下：
|
|
|
| 第一步，计算n，n=pq=3×17=51，得出公钥n=51，e=13。
|
|
|
第二步，计算φ(n)和d，φ(n)=(p-1)(q-1)=2×16=32。因为d=e-1modφ(n)，所以 ，其中k是p-1和q-1的最大公约数。由此算出d=（2×32+1）/13=5，即解密密钥d=5。
|
|
|
| 第三步，加密和解密处理计算。假设Bob的公开密钥是e=13、n=51，Alice需要将明文“2”发送给Bob，则Alice首先用Bob的公开密钥加密明文，即：
|
|
|
| C=Memodn=213mod 51=8192 mod 51=32
|
|
|
| 然后，Bob收到Alice发来的密文C后，用自己的私钥d解密密文C，即：
|
|
|
| M=Cdmodn=325mod 51=1024×1024×32 mod 51=512 mod 51=2
|
|
|
| RSA安全性保证要做到选取的素数p和q足够大，使得给定了它们的乘积n后，在事先不知道p或q的情况下分解n是计算上不可行的。因此，破译RSA密码体制基本上等价于分解n。基于安全性考虑，要求n长度至少应为1024比特，然而从长期的安全性来看，n的长度至少应为2048比特，或者是616位的十进制数。
|
|
|
