技术

“黎曼猜想”推翻区块链加密算法?

菲尔兹和阿贝尔奖双料得主迈克尔·阿蒂亚爵士宣称自己证明了黎曼猜想,要在9月24日海德堡获奖者论坛上宣讲。最近有些人啊,见得风,就是雨。Atiyah 已经证明了 Riemann 猜想,一场风暴已经在酝酿之中,所有加密算法已经危如累卵,区块链行业迟早要完,赶快收拾细软准备跑路吧,注意,一定要是细软哦。Riemann 猜想声称 zeta 函数的非平凡零点的实部都是1/2。可是这和区块链又有什么关系呢?

 

某媒体这样说

看到这条新闻

 

 

这一次或许你的朋友圈已经被震惊了,可是数学圈还没有。敢于质疑权威并不是你想像中的一个科学家所具有的稀有宝贵品质,而是一个科学家应该具有的基本素质。像 Atiyah 这样的活着的荣膺数学界两大桂冠 Fields,Abel 奖项的权威并不多见,他在指标定理,K理论和规范理论方面所作出的贡献是有目共睹了,但是数学界还是大多持怀疑态度。毕竟这是一个人人都可以上arXiv上宣布自己证明了 Riemann 猜想的年代。

 

 

据我所知,他本人在数论上的贡献并不能和上述领域比肩,要知道 Atiyah 现在已经89岁了,早已不是Hardy 说的创造力旺盛的年轻人。

Atiyah 本人也已经不是第一次差点搞个大新闻了,之前 Atiyah 在 arXiv 上发表了一篇预印文章The Non-Existent Complex 6-Sphere ,然而这篇文章的证明并不被专家认可

 

尴尬而又不失礼貌的微笑

 

其实我的说法已经过于委婉,John Baez甚至在Twitter上这样说

 

 

 

 

 

即使我们相信一个 Atiyah 是老骥伏历,可是 Riemann 猜想的证明真的能给网络安全致命一击吗?

让我们从 Diffie 和 Hellman 的1976年的革命性论文 New Directions in Cryptography 谈起。为了实现信息加密,Diffe 和 Hellman 在这篇文章中给了一个比较通用的方法去寻找一个单方向的函数。由于这个函数是单方向的,我们加密操作比较容易执行,而解密操作难于实现。Diffe 和 Hellman 认为在某些代数结构上求离散指数是很容易实现的,而求离散对数却通常不是那么容易。如果某个特殊的信息(也就是我们现在所熟知的加密密钥)可以让我们比较容易求解离散对数,那我们就可以实现对信息的加解密。

一年之后,Rivest,Shamir 和 Adleman 在离散整数模n群上给出了这样一个单向函数,这就是广为人知的RSA算法。如上所述,RSA算法本质上是离散整数环上难于求解离散对数,而求指数的过程就是加密过程,求对数的过程就是解密过程,这并不容易实现,所以我们的信息可以不被人窃取。

 

 

 

正是这里,Hardy 所希望没有什么用处的数论大显身手。我们上面说的能够帮助解密的特殊信息,在RSA算法里就是把n分解成两个大素数的积。如果我们知道这两个素数,利用 Fermat 小定理,我们可以比较容易地求出离散模n整数环的离散对数。这样就实现了信息的解密。

所以如果能够在多项式时间内分解质因数,RSA加密算法就能被快速破解,这种算法事实上确实存在,但是问题是这个算法 Shor’s algorithm 依赖于量子计算机。由于各种问题(比如量子退相干),量子计算机距离真正落地还有很长的路要走。而且一个能够破解RSA算法的量子计算机需要很多量子比特,人类离制造出这样一个计算机还很遥远,所以我们完全可以认为在可预见的将来RSA算法还是安全的。具体可参见How big an RSA key is considered secure today?

 

 

 

回到正题,如果 Riemann 猜想已经被证明了,地球还安全吗?证明黎曼猜想能够给素数分布提供很多启示,比方说我们可以用 Riemann 猜想来估计了素数定理的误差项,我们可以用Riemann猜想来估计相邻素数之间的间隙,我们可以用Riemann猜想来证明数论的一万个大定理,但是黎曼猜想被证明后可以分分钟破解RSA算法那就是痴人说梦

即使我们可以通过Riemann猜想来得知所谓的素数公式(我想当那些见得风就是雨的自媒体在谈论素数公式的时候,他们在谈论一个稍微有点数学修养的人都不会相信其存在性的素数通项公式),我们也没法用知道的可以所有素数这个事实来快速破解RSA算法。为了破解RSA算法,我们需要的不是素数公式,我们需要分解质因数。现在业界常用的RSA算法的加密密钥的大小是2048位,根据素数定理,这个大小范围内素数大约占了所有整数的几千分之一。我们或许可以用知道的这个区间内的所有来给破解RSA的算法提速数以万倍,但是这个数字很容易就被4096位的密钥是提高的安全性矮化,因为当从密钥长度2048增加到从4096位,General number field sieve解密的复杂度提高了将近一千亿倍,具体计算见这里

 

 

 

各位看官,看到这儿,你是不是心宽了很多。但是请注意,我们现在说的所有,还只不过是一种比较流行的加密算法。如果这个算法真的失效,我们完全可以选择另外一种更加安全的算法。加密解密这个猎和老鼠的游戏里没有永远的赢家和永远的输家。有时候有一条腿可能走得快一些,有时候另外一条腿走得快一些,但是如果某一条腿完全停了下来,另一条腿还能继续走下去吗?

后量子时代的密码学Post Quantum Cryptology这门新的学科已经展现出了强大的生命力。我们对于普通人加密解密安全性的担忧有点过于杞人忧天了。