仨数公开俩，也能算密码？| 亲子科学系列
正是一批当年看起来很没有用处的纯数学成果，使得我们现在可以在网络上可以安全地从事很多商务活动，大到签署巨额合同文件，小到双十一剁手。
撰文 | 吴进远
我们前两篇文章谈到了和后来的一些，不过这些还都不是密码。人们编制代码的目的是为了传递人话，因此，编制代码的规则必须告诉接收方使之可以读明白。但很多时候，我们却不想让无关的人搞明白我们所传递的信息，这时就需要编制密码。
密码包括两大类，一类叫做对称性密码，另一类叫非对称性密码。所谓对称性密码，是指不论发送方编码还是接收方解码用的都是同一套密钥。在二十世纪七十年代之前，所有的密码都属于对称性密码。发送方和接收方必须提前通过安全的方式，将密码本递送给对方，才能用密钥给电信通讯的内容加密。在战争时期，递送密码本是一个艰险的工作，《红灯记》中李玉和、李奶奶为了给抗日游击队递送密码本甚至牺牲了生命。
此外，由于加密规则是第三方不知道的，因此人们编制密钥时很可能会不深入考虑被破解的风险，结果反而使得加密的报文变得可以破解。在战争年代，由于破解敌方电报密码而导致战局变化的事例非常多。
而非对称性密码，加密与解密需要的密钥是不同的。通讯前，接收方把加密用的密钥传递给发送方，这个加密用的密钥不需要保密，因此称为公共密钥。发送方用加密的密钥把信息加密，发送给接收方。在上述通讯过程中，网络上任何人都可以偷听到加密密钥以及通讯信息，但是加密密钥对于解密通讯内容完全无用。只有接收方，使用自己保管的解密密钥，或私有密钥，才能解密通讯内容。
形象地说，发送信息的人可以把信写好，放到一个保险箱里，用公共密钥锁起来。但这个保险箱却无法用公共密钥打开，必须用另一个私有密钥才能打开。
这样讲也许还有些抽象，我们通过一个实际的例子来进一步说明这种加密方法。
设想小明想给小莹写一段信息，可是周围灯泡环伺，这可怎么办呢？小莹得知后说好办，然后大大方方地在黑板上写了两串数字。“把信息用这两个数字加密，就无人可以破解，因为我还有一个数字，只有用这个秘密数字才可以解密。”
尽管如此，小明还是有些发怵，用两个人人皆知的数字加密信息，可靠吗？我们设想小明要发的信息是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)
经过这样加密的数字：1918020720，其他人就很难破解了，甚至连小明自己也无法破解。只有小莹，把私人密钥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 里面的数字就会出现伤筋动骨级别的变化，根本无法靠复制粘贴这样的操作来达到鱼目混珠的目的。况且，为了保险起见，任何人都可以要求我编制出他所指定的信息。有趣的是，出题的人并不知道答案是什么，但是看到答案却知道对不对。
如果大家读数学打哈欠了，那么我们换个角度。一千多年前，有人给了我们一套公钥：“苦吟”，“炼字”，“两句三年得，一吟双泪流”（用“行车太规范，自己两行泪”比较好记）。他用手中的私钥生成一段文字，贴到朋友圈：“松下问童子，言师采药去，只在此山中，云深不知处”。由此，我们可以把这个签名翻译出来：碣石山人贾岛到此一游。
假设不知哪劫哪世，闹市上一人口中念念有词：“十年磨一剑，霜锋未曾试”。您会不会有些疑惑，他是贾岛呢？还是假贾岛呢？
为了做出判定，您可以出题考考他：“到朋友府上去串门，该怎么说？”
您虽然出了题，但您也不知道该写成什么样。但别人写出来，您却可以根据公开的公钥判断回答者是不是贾岛。
如果他不假思索地吟道：“小扣柴扉久不开”，您完全可以膜拜膜拜。这确实是位著名诗人，只不过是宋代的叶绍翁，但不是唐代的贾岛。
如果他迟疑地字斟句酌道：“鸟宿池边树， 僧敲月下门”，那么，恭贺您，贾岛老师本尊穿越过来给您补习功课了。
当然，作诗所用的“私钥”与“公钥”相对而言比较复杂，涉及的模糊因素太多，比较难定义，在这里只是一个比喻。但在数学中，电子签名这一类算法的定义是非常清楚的。其可靠性，是人们多年来数论研究所取得的成果所保障的。
正是这样一批当年看起来很没有用处的纯数学成果，使得我们现在可以在网络上可以安全地从事很多商务活动，大到签署巨额合同文件，小到双十一剁手。
·
·
·
·
·
·
·
