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

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

当迪菲和赫尔曼提出“公钥密码系统”时，人们并不知道如何利用这项理论设计“公钥”和“私钥”。两年后，才由美国马萨诸塞理工学院的三位研究员里维斯特、沙米尔和艾德莱曼联名提出了第一个实用的公钥密码方案——后被称为“RSA方法”。这是一种用来产生密钥的方法，由它形成的密码几乎能够抵御一切密码攻击。如今，该方法已在互联网上广泛使用。RSA方法依赖于初等数论中一条著名的定理：费马小定理，即设p是任意大于2的素数，a是任意的与p互素的非零整数，则必然有ap-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），并计算然后将发送给乙。乙收到甲发来的后，就用自己的私钥计算用费马小定理可以证明：于是得到原文M。外人并不知道乙的私钥，所以不能获取原文。

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

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

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

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

【微问题】你能自己构造一套简单的密码系统吗？

【关键词】公钥密码系统　RSA方法