仨数公开俩，也能算密码？| 亲子科学系列（10）|赛先生

凭借当年看似无用的纯数学成果，我们现在可以在网络上安全地进行很多商业活动，签署巨额合同文件，甚至可以做大做强小双十一。(莎士比亚) (以英语发言)。

（图源：）

撰文 | 吴进远

我们前两篇文章谈到了摩尔斯电码和后来的一些其他编码方法，不过这些还都不是密码。人们编制代码的目的是为了传递人话，因此，编制代码的规则必须告诉接收方使之可以读明白。但很多时候，我们却不想让无关的人搞明白我们所传递的信息，这时就需要编制密码。

对称密码

密码包括两大类，一类叫做对称性密码，另一类叫非对称性密码。所谓对称性密码，是指不论发送方编码还是接收方解码用的都是同一套密钥。在二十世纪七十年代之前，所有的密码都属于对称性密码。发送方和接收方必须提前通过安全的方式，将密码本递送给对方，才能用密钥给电信通讯的内容加密。在战争时期，递送密码本是一个艰险的工作，《红灯记》中李玉和、李奶奶为了给抗日游击队递送密码本甚至牺牲了生命。

此外，由于加密规则是第三方不知道的，因此人们编制密钥时很可能不会深入考虑被破解的风险，结果使得加密的报文变得可以破解。在战争年代，由于破解敌方电报密码而导致战局变化的事例非常多。

非对称密码

而非对称性密码，加密与解密需要的密钥是不同的。通讯前，接收方把加密用的密钥传递给发送方，这个加密用的密钥不需要保密，因此称为公共密钥。发送方用加密的密钥把信息加密，发送给接收方。

在上述通讯过程中，网络上任何人都可以偷听到加密密钥以及通讯信息，但是加密密钥对于解密通讯内容完全无用。只有接收方，使用自己保管的解密密钥，或私有密钥，才能解密通讯内容。

形象地说，发送信息的人可以把信写好，放到一个保险箱里，用公共密钥锁起来。但这个保险箱却无法用公共密钥打开，必须用另一个私有密钥才能打开。

这样讲也许还有些抽象，我们通过一个实际的例子来进一步说明这种加密方法。

小明想给小莹写一段信息，可是周围灯泡环伺，这可怎么办呢？小莹得知后说好办，然后大大方方地在黑板上写了两串数字。“把信息用这两个数字加密，就无人可以破解，因为我还有一个数字，只有用这个秘密数字才可以解密。”尽管如此，小明还是有些发怵，用两个人人皆知的数字加密信息，可靠吗？

假设小明要发的信息是17281314，小莹写在黑板上的数是7和22，小明误以为编码方法就是把信息与这两个数相乘，那么，小明编出的“加密”信息为：

17281314*7*22 = 2661322356

编出来的这个数确实和原来信息长得很不像，但其他人想破解太容易了，只要把“加密”信息除以黑板上的两个数，就恢复了原始信息：

2661322356/(7*22) = 17281314

你可能觉得小明设想的加密方法太简单了。其实，问题不在于加密运算是不是简单，关键在于加密运算的逆运算是不是太容易。我们平常见到的各种运算大多数都有逆运算：加法对应减法，乘法对应除法，乘方对应开方，指数对应对数，它们互相之间都是逆运算。这些逆运算都太容易了，无法用在加密通讯上。

在实际应用中的一种常用加密方法，即RSA算法，则是一种逆运算极其困难的运算。这种算法的加密与解密方法可以用以下公式写出来：

加密：c = (m^e) mod n

解密：m = (c^d) mod n

在上面公式中，m是原始信息，一串很长的数，e和n是公共密钥，相当于黑板上的两串数字。公式中 mod n 的意思是把前面那个整数除以n，留下除不尽的余数，比如16除以5，余数为1。这样加密之后，得到一串数字c，想破解就不容易了，必须使用另一个整数d，也就是私有密钥才能得到结果。

当n=22，e=7的时候，这个私有密钥d就是3。下表显示了在这个简单的例子中，编码与解码的计算过程。

这样，小明发送的信息就可以利用这个算法来编码：17281314=> 1918020720 (17=>19; 2=>18;8=>02; 13=>07; 14=>20)。经过这样加密的数字其他人就很难破解了，甚至连小明自己也无法破解。只有小莹把私人密钥 d=3 代人解密公式：m = (c^d) mod n，才能恢复原始信息：17281314。

你可能会觉得，小莹的私人密钥 d=3 太容易猜出来了。的确，因为我们在这个简单的例子中用到的这三个数n，e，d都太小了。实际应用中，这三个数都是上千位的巨大数字，这样就很难猜了。

这三个数可以随便挑吗？当然不是。计算机在生成这三个数的时候，首先随机寻找两个千位量级的质数（素数）p，q，然后相乘得到n（即：n=p*q，比如我们前面例子中，22=2*11）。然后利用p和q，找到e和d（前面例子中的7和3）。这一对密钥具有下面的特性：

( ((m^e) mod n)^d) mod n = m

也就是说，任意一个整数m（就是我们发送的信息），经过加密与解密这样一对操作，一定能够恢复。可见，e和d是一对作用互反的数字，不过，仅仅从n和e无法计算出d，必须知道p和q。

聪明如你一定会发现，既然我们已经知道n=p*q，使用强大的超级计算机，应该可以把两个质数p，q分解出来吧？有了p，q，又知道e，不就可以算出d，从而破解密码了吧？

这是个很好的问题，它揭示了RSA密码的关键所在，当我们用两个不太大的质数相乘，从得到的乘积很容易分解出这两个质数乘数。但当这两个质数的非常大的时候，计算的难度急剧增长，远远超过现有超级计算机在合理时间内的计算能力。因此从这个意义上说，这种密码是无法破解的。

除了我们这里介绍的RSA加密算法，现实应用中还有其他算法。它们的原理都是基于一种叫做单向函数的理念。也就是说，一个正向运算很容易，比如两个质数相乘p*q，但它的逆运算，比如把乘积分解，却非常难。

有了这样的单向函数，我们就可以把整套密钥中的三个数大大方方地公开两个，而不用担心通讯信息被人破解。

这么大的数怎么算？

敏锐如你一定会发现，我们在加密和解密的过程中的操作，比如(m^e)，是非常高次的乘方。可以想象由此得到的数一定很大，这种操作未免太猛如虎了吧？的确，你在计算器上试算一下98765432^23456789，这个数大约有上亿位，计算器不死算我输。

其实真正计算中并不会出现这么巨大的数，因为我们算的是以n为除数的余数。计算两个数乘积的余数时，我们可以先求出两个数的余数再相乘，这样的乘法就容易计算多了。具体到算一个数m的平方的余数，算法如下图所示：

我们这里把m分解成为K*n，即n的整倍数，以及余数r这样两部分。这样只有r^2这部分，即上面图中涂色的小方块，可能对m的平方的余数有贡献。上面图中所有白色的方块都必然是n的整倍数，对于余数的贡献一定是0，因此我们只需要计算r^2就可以了。当然r^2这个结果本身完全可能大于n，这就要求我们对r^2再做取余数的运算，最终得到 m^2 mod n。

我们现在用个小一点的实际数字来进一步说明一下，比如老师出个题：

98765432^2，这个数的个位是多少？同学们掏出计算器一通按，得到结果：9754610558146624，总共16位数，其个位为4。

您家娃很可能没有掏计算器就举手，二二得四，立刻得到答案：个位数是4。在这个问题中，一个数字的个位数，其实就是它以10为除数的余数。不管多少位数做乘法（包括平方），十位以上的数对于结果的个位数一定没有贡献，我们在每次做乘法之前，先取余数，这样就可以避免用很大的数相乘。

在计算机加密解密操作中，除数n有上千位，但只要计算时及时取余数，算出的结果就会始终保持在千位量级。这个数虽然很大，但比起上亿位来说，还是小得多了。

大家可能还是有些不放心，在 (m^e) 之中，除了m是千位量级的大数，指数e也是个很大的数，我们前面讨论了怎样有效地计算 (m^2) mod n 的问题，可 (m^2) 与 (m^e) 之间还差得很多呀。比如我们找个小一点的实际数字做例子，在计算 (m^23456789) 的时候，难道我们要计算两千多万次乘法吗？

实际上，我们可以找到更好更简单的算法。比如，我们可以把23456789这个数翻译成二进制：

23456789 (base 10) = 1011001011110110000010101 (base 2)

这告诉我们，这个数可以看成是若干个数的和：

23456789 = 2^24 + 2^22 + 2^21 + 2^18 + 2^16 ...

于是，用这样一个大数作为指数时，计算的过程可以看成是一个乘积：

m^23456789 = m^(2^24) * m^(2^22) * m^(2^21) *m^(2^18) * m^(2^16) ...

可是，像 m^(2^24) 这样的数，似乎也很难算呀。其实仔细想想，并没有那么难。我们已经可以计算平方了，把平方出来的结果再平方，就可以得到更高方次的结果。例如：

(m^2)^2 = m^4; (m^4)^2 = m^8; (m^8)^2 = m^16; (m^16)^2 = m^32 ...

因此，只要不停地做平方（即乘法）运算23次，就可以得到 m^(2^24) 这样的数（当然，每次乘法运算之后都要进行取余数，即 mod n 的运算）。而上述这样一个计算过程的中间结果，包含了 m^(2^22)，m^(2^21)，m^(2^18) 等等。这就使得这样的高方次计算成为可能。

取余数运算的威力

至此，大家可能可以看出一点眉目了，正是算法中使用了取余数（mod n）这样的运算，使得合法通讯双方的计算量大大下降，使得巨大数的巨大方次乘方运算 (m^e) 这种“猛如虎”的操作，可以用250次乘法这种量级的计算量实现。

另一方面，如果我们设想加密算法中没有取余数的运算：

加密：c = (m^e)

暂且不论这个数字的巨大，单从加密角度看，也没有达到目的。这个数字包括了高位数上的所有信息，因此其逆运算非常简单。乘方的逆运算就是开方，窃听者很容易就可以用你公布的密钥把信息解密：

解密：m = c^(1/e)

因此，正是算法中使用了取余数（mod n）这样的运算，隐去了高位数携带的信息，使得开方这类简单的逆运算变得不可行。这样一来，窃听者必须进行的逆运算，就需要连超级计算机都无法提供的计算量。
电子签名

在RSA算法中，加密和解密的密钥，也就是e和d这两个数的位置是可以互换的，用公式写出来就是：

( ((m^e) mod n)^d) mod n = ( ((m^d) mod n)^e)mod n = m

这个公式说明了什么呢？这个公式表示，由于我手中持有私钥d，因此我可以用这个私钥把我的名字（加上日期时间以及序列号等信息）s编制出一段密码：

(s^d) mod n = x

任何人都可以利用我以前公布的公钥，即e和n这两个数字，计算出我所编制的信息。

(x^e) mod n = s

这样，就只有我可以编制出这样一个x信息，而这个x密码就成为我的电子签名。这个x密码尽管直接看像鬼画符一样，但大家用e和n这两个数字就可以计算出是有意义的内容。

那么别人能不能假冒我的电子签名呢？当然任何人都可以随意编一个鬼画符一样的信息y，但由于他们手中没有d这个数，因此大家把这个编出的y以及以前公布的e和n代入公式，就会发现得到的结果仍然是鬼画符一般。

当然，网络上的其他人可以截获我以前用过的签名x，不过这个签名中除了我的名字，还有日期时间等信息，是过期作废的。如果有人企图修改这些信息，x里面的数字就会出现伤筋动骨级别的变化，根本无法靠复制粘贴这样的操作来达到鱼目混珠的目的。况且，为了保险起见，任何人都可以要求我编制出他所指定的信息。有趣的是，出题的人并不知道答案是什么，但是看到答案就知道对不对。

如果大家读数学打哈欠了，那么我们换个角度。一千多年前，有人给了我们一套公钥：“苦吟”“炼字”“两句三年得，一吟双泪流”（用“行车太规范，自己两行泪”比较好记）。他用手中的私钥生成一段文字，贴到朋友圈：“松下问童子，言师采药去，只在此山中，云深不知处。”由此，我们可以把这个签名翻译出来：碣石山人贾岛到此一游。

假设不知哪劫哪世，闹市上一人口中念念有词：“十年磨一剑，霜锋未曾试。”您会不会有些疑惑，他是贾岛呢？还是假贾岛呢？

为了做出判定，您可以出题考考他：“到朋友府上去串门，该怎么说？”

您虽然出了题，但您也不知道该写成什么样。但别人写出来，您却可以根据公开的公钥判断回答者是不是贾岛。

如果他不假思索地吟道：“小扣柴扉久不开”，您完全可以膜拜膜拜。这确实是位著名诗人，只不过是宋代的叶绍翁，但不是唐代的贾岛。

如果他迟疑地字斟句酌道：“鸟宿池边树， 僧敲月下门”，那么，恭贺您，贾岛老师本尊穿越过来给您补习功课了！

当然，作诗所用的“私钥”与“公钥”相对而言比较复杂，涉及的模糊因素太多，比较难定义，在这里只是一个比喻。但在数学中，电子签名这一类算法的定义是非常清楚的。其可靠性，是人们多年来数论研究所取得的成果所保障的。

正是这样一批当年看起来很没有用处的纯数学成果，使得我们现在可以在网络上可以安全地从事很多商务活动，大到签署巨额合同文件，小到双十一剁手。