.
陈凯师

陈凯师质数如何用于信息加密?-火星科普

陈凯师质数如何用于信息加密?-火星科普

陈凯师
黑客如果试图用每秒钟测试100万个组合的计算机,来破解隐藏银行卡信息的400位加密编码,大约需要10^194秒才能完成这一壮举。相比之下,宇宙年龄不到10^18秒。就目前而言,破解这样的密码似乎是一项相当繁琐的任务。
早在17世纪,以费马大定理而闻名的费马发明了一种精妙的方法,来确定一个数字是质数还是合数时,其他人无法理解这个证明的实用性。这个证明被认为就像一尊雕像,美丽但无用。那时,关于质数的发现仅仅是为了揭示和理解数学中隐藏的复杂性,它们还没有为现实世界的问题提供任何实质性的解决方案。
直到400年后互联网诞生之时,数十亿用户的隐私,从机密的电子邮件内容到电子商务网站的交易都完全依赖于质数。那么,质数是如何被用于加密的呢?

质数只能被1和自身整除,它们通常被称为数字领域的“原子”,因为它们是构成每个数字基本的、不可分割的单位。例如,10可以写成2和5的乘积,这就是两个质数。或者150作为15和10的乘积,可以进一步分解,写成是3和5、2和5的乘积,这些都是质数。又或者,更大的数字,比如126356,可由更大的质数组成,2、2、31和1019。
在数学中,把一个合数变成质数乘积的过程被称为质因子分解。对于一台计算机来说,把两个很大的质数相乘,即使每一个质数长达100位,计算出结果也并不难。然而,把一个很大的数分解成质数的乘积则是出了名的困难,即使对于超级计算机来说也是如此。这个难点被李维斯特、萨莫尔和阿德曼三位数学家在1977年发明的RSA加密算法时利用。

假设C是两个质数P和Q的乘积,当加密时,比如加密银行卡信息,数字C被用来生成公开密匙,即公钥。正如其名字所示,这个密钥是公开的,这意味着它可以被网络中的任何人拦截和读取。众所周知,银行使用的公钥长度为1024位(309位数字),以确保私人交易信息。
通过把一个公钥锁在一个“盒子”中,它的句柄与一个几百位数的组合密码锁紧密地结合在一起,从而保护私有信息。这个盒子本身可以被任何人访问,但是里面的内容不行。当一个黑客想暗中窃取这个盒子,他在不知道密码组合以及没有私钥的情况下不可能解锁它。这个私钥只由信息发送者和接收者——银行和用户所持有。

RSA加密算法
在不知道私钥的情况下,黑客必须把C进行质因子分解,如果这个数很大,位数达到上千位,他可能要花上几千年的时间才能分解出来。这是因为把一个很大的数分解成两个较大质数相当困难,有些质数确实可以很大。目前已知最大的质数为2^77232917-1,它的素性已经被计算机验证了。这个数有2300万位,如果要把这个数字写在A4纸上,写完这个数估计要用4500张。
虽然大数的分解质因数并非不可能,只是所需耗费的时间太长。随着技术的进步,我们也许能够更快地处理数字。量子计算机可能会实现这一目标,但目前,在它们变得功能齐全、普遍存在之前,还有很长的路要走。目前,计算机分解的最大数达到了768位(232位数字),而现行公钥为1024位(309位数字),有些甚至已经升级到2048位(617位数字),所以我们基本上不用担心信息被泄露。