仨数公开俩,也能算密码?| 亲子科学系列-深度-知识分子

仨数公开俩,也能算密码?| 亲子科学系列

2019/12/31
导读
也许,你将成为破译专家!

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

(图源:pixabay.com


撰文 | 吴进远


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


对称密码

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


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


非对称密

而非对称性密码,加密与解密需要的密钥是不同的。通讯前,接收方把加密用的密钥传递给发送方,这个加密用的密钥不需要保密,因此称为公共密钥。发送方用加密的密钥把信息加密,发送给接收方。在上述通讯过程中,网络上任何人都可以偷听到加密密钥以及通讯信息,但是加密密钥对于解密通讯内容完全无用。只有接收方,使用自己保管的解密密钥,或私有密钥,才能解密通讯内容。


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


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


设想小明想给小莹写一段信息,可是周围灯泡环伺,这可怎么办呢?小莹得知后说好办,然后大大方方地在黑板上写了两串数字。“把信息用这两个数字加密,就无人可以破解,因为我还有一个数字,只有用这个秘密数字才可以解密。”


尽管如此,小明还是有些发怵,用两个人人皆知的数字加密信息,可靠吗?我们设想小明要发的信息是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 里面的数字就会出现伤筋动骨级别的变化,根本无法靠复制粘贴这样的操作来达到鱼目混珠的目的。况且,为了保险起见,任何人都可以要求我编制出他所指定的信息。有趣的是,出题的人并不知道答案是什么,但是看到答案却知道对不对。


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


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


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


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


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


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


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


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


往期回顾

· 为什么二维码里面有三个大方块?| 亲子科学系列(9)

· 滴!刷卡的时候发生了什么?| 亲子科学系列(8)

· 肥皂泡,光盘上的彩色和彩虹是一回事吗?| 亲子科学系列(7)

· 学文还是学理?所有的知识都不会白学 | 亲子科学系列(6)

· 爬门框、拆车轮,玩也是一种学习方式 | 亲子科学系列(5)

· 被海淀家长碾压?多和孩子一起读无字之书 | 亲子科学系列(4)

· 切薯格、拆门锁,生活中的冷知识也有讲究 | 亲子科学系列(3)

· 玩手机,学会考试需要的硬核知识 | 亲子科学系列(2)

· 带娃漫步荷塘边,有月色,还可谈科学 | 亲子科学系列(1)

参与讨论
0 条评论
评论
暂无评论内容
《赛先生》微信公众号创刊于2014年7月,创始人为饶毅、鲁白、谢宇三位学者,成为国内首个由知名科学家创办并担任主编的科学传播新媒体平台,共同致力于让科学文化在中国本土扎根。
订阅Newsletter

我们会定期将电子期刊发送到您的邮箱

GO