为什么RSA方法是制造密码的强大武器

当迪菲和赫尔曼提出“公钥密码系统”时，人们并不知道如何利用这项理论设计“公钥”和“私钥”。两年后，才由美国马萨诸塞理工学院的三位研究员里维斯特、沙米尔和艾德莱曼联名提出了第一个实用的公钥密码方案——后被称为“RSA方法”。这是一种用来产生密钥的方法，由它形成的密码几乎能够抵御一切密码攻击。如今，该方法已在互联网上广泛使用。RSA方法依赖于初等数论中一条著名的定理：费马小定理，即设$p$是任意大于2的素数，$a$是任意的与$p$互素的非零整数，则必然有$a^{p-1}≡1(mod\ p)$，［一般地，$m≡n(mod\ k)$表示$m-n$被$k$($k$≠0)整除］其中$mod\ p$就表示被$p$除后的余数。

里维斯特、沙米尔和艾德莱曼

用RSA方法产生私钥和公钥的过程大致如下：首先是随机寻找两个大素数$p$和$q$，计算$n=pq$，$ϕ(n)=(p–1)(q–1)$；然后找一个与$ϕ(n)$互素的合适的正整数$e$，并用欧几里得辗转相除法找到另一个正整数$d$，使得$ed≡1(mod\ ϕ(n))$；最后把整数对($e$,$n$)作为“公钥”放在公共网络上，$(d,ϕ(n))$则是“私钥”，需要保密。

如果网络用户甲要给乙发送一段需要保密的文本信息$M$（不妨假设$M$是一个正整数且小于$n$），则甲应如此操作：找到乙的公钥$(e,n)$，并计算$\tilde{M}≡M^e(mod\ n)$；然后将$\tilde{M}$发送给乙。乙收到甲发来的$\tilde{M}$后，就用自己的私钥计算$\tilde{M}^d(mod\ n)$。用费马小定理可以证明：$\tilde{M}^d≡M^{ed}≡M(mod\ n)$，于是得到原文M。外人并不知道乙的私钥，所以不能获取原文。

通过类似的操作，用RSA方法也能够容易地实现数字签名。

RSA方法之所以可行，是基于以下关于大整数运算的若干事实：第一，可以运用计算机实现两个大整数的快速相乘；计算两个$m$位数相乘所需要的基本运算次数约为$m\lg m$，所以，即使是几千位数字的相乘也可以很快完成；第二，存在寻找大素数的快速计算方法，数论知识告诉我们，在不大于$n$的正整数中，平均存在着$n / \ln n$个素数，所以运用计算机可以很快找到所需素数；第三，不存在分解一个大整数的有效方法。

任何人企图破解密文就必须知道私钥$(d,ϕ(n))$中任意一个值；而要利用公钥$(e,n)$来算出$d$或$ϕ(n)$，就必须分解$n$。所以，谁要是能找到分解大整数的有效方法，就能攻破RSA密码，整个互联网也因此会立刻崩溃。

所幸的是，我们已经知道分解整数属于NP问题。对于NP问题是否存在有效算法，这是一个世界著名难题，而且答案很可能是否定的。所以，互联网目前还很安全。