巧妙的“可能与不可能”

在公钥密码中，典型的密码算法是RSA算法，它是基于“大整数因子分解的难解性”来进行设计的。即：给定一个大整数n，若要将它分解成两个素数因子p和q的乘积（n=p×q）是非常困难的。当n足够大时（例如达到数百位），即使用计算机也难以实现。

通俗地说，就是知道p和q，计算n是容易的，但如果只知道n，求p和q却是困难的。

下图是RSA算法的三位设计者：罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）。

RSA算法的三位设计者

RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对不相同的密钥，使用其中一个加密，用另一个才能解密。

生成公钥和私钥的算法如下：

1.随机选择两个大素数p和q；

2.计算n=p×q和（p-1）×（q-1）；

3.随机选择与（p-1）×（q-1）互质的整数e；

4.利用等式d×e mod（（p-1）×（q-1））=1，求得d；

这样，就产生了一对密钥e和d，e是公钥，d是私钥，还有一个参数n。

从上述算法中可以看出，计算两个大素数p和q的乘积n是容易的，但要反过来从n中分解出p和q却是困难的。因此，只要在生成密钥后将p和q销毁，即便将n和e公开，别人也不容易从中反推出d。因此，e、n和加密解密的算法，都是可以公开的。

若M为明文，C为密文，则RSA加密和解密算法分别为：

C=Memod n

M=Cdmod n

我们用一个实例来说明RSA算法加密和解密的过程。

用户A需要将明文“love”进行加密后发送给用户B，再由用户B对其解密。

假设B已经计算出了自己的相关参数：n=187，公钥e=7，私钥d=23，并且将n和e对外公开。

按照事先约定，A将明文“love”的每一个字母转换成对应的ASCII码，这样就把文字转换成了整数。转换的结果是“108111118101”。真正计算时，这些整数都将用二进制表示。

1.A利用B公开的参数n=187和e=7对明文进行加密，根据加密公式可得到：

1087mod 187=48

1117mod 187=155

1187mod 187=101

1017mod 187=84

2.A将密文“4815510184”发送给B；

3.B接收到密文后，利用自己保管的私钥d=23进行解密，根据解密公式可得到：

4823mod 187=108

15523mod 187=111

10123mod 187=118

8423mod 187=101

4.B利用ASCII码表将整数“108111118101”转换成对应的字符“love”。

以上仅是利用“小整数”来说明RAS算法的原理。在实际应用中，n的长度要大于1024bit，p与q应该严格按照随机方式产生，并且不能靠得太近。

加密与解密的过程

RSA算法是一种高强度的密码算法，它的安全性依赖于大数分解，当n小于1024bit时，已经被证明是不安全的，而且由于RSA算法进行的都是大数计算，使得它的运算速度比DES算法慢很多，这是RSA算法最大的缺陷，因此，RSA算法通常被用于加密少量信息或者加密密钥。