“黎曼猜想”推翻區塊鏈加密演算法?
菲爾茲和阿貝爾獎雙料得主邁克爾·阿蒂亞爵士宣稱自己證明了黎曼猜想,要在9月24日海德堡獲獎者論壇上宣講。最近有些人啊,見得風,就是雨。Atiyah 已經證明了Riemann猜想,一場風暴已經在醞釀之中,所有加密演算法已經危如累卵,區塊鏈行業遲早要完,趕快收拾細軟準備跑路吧,注意,一定要是細軟哦。Riemann 猜想聲稱zeta函式的非平凡零點的實部都是1/2。可是這和區塊鏈又有什麼關係呢?
某媒體這樣說:
看到這條新聞後,,
01
這一次或許你的朋友圈已經被震驚了,可是數學圈還沒有。敢於質疑權威並不是你想像中的一個科學家所具有的稀有寶貴品質,而是一個科學家應該具有的基本素質。像 Atiyah 這樣的活著的榮膺數學界兩大桂冠Fields,Abel獎項的權威並不多見,他在指標定理,K理論和規範理論方面所作出的貢獻是有目共睹了,但是數學界還是大多持懷疑態度。畢竟這是一個人人都可以上arXiv上宣佈自己證明了 Riemann 猜想的年代。
據我所知,他本人在數論上的貢獻並不能和上述領域比肩,要知道Atiyah現在已經89歲了,早已不是Hardy說的創造力旺盛的年輕人。
Atiyah 本人也已經不是第一次差點搞個大新聞了,之前Atiyah在arXiv上發表了一篇預印文章The Non-Existent Complex 6-Sphere ,然而這篇文章的證明並不被專家認可。
其實我的說法已經過於委婉,John Baez甚至在Twitter上這樣說:
02
即使我們相信一個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?
03
回到正題,如果Riemann猜想已經被證明了,地球還安全嗎?證明黎曼猜想能夠給素數分佈提供很多啟示,比方說我們可以用Riemann猜想來估計了素數定理的誤差項,我們可以用Riemann猜想來估計相鄰素數之間的間隙,我們可以用Riemann猜想來證明數論的一萬個大定理,但是黎曼猜想被證明後可以分分鐘破解RSA演算法那就是痴人說夢。
即使我們可以通過Riemann猜想來得知所謂的素數公式(我想當那些見得風就是雨的自媒體在談論素數公式的時候,他們在談論一個稍微有點數學修養的人都不會相信其存在性的素數通項公式),我們也沒法用知道的可以所有素數這個事實來快速破解RSA演算法。為了破解RSA演算法,我們需要的不是素數公式,我們需要分解質因數。現在業界常用的RSA演算法的加密金鑰的大小是2048位,根據素數定理,這個大小範圍內素數大約佔了所有整數的幾千分之一。我們或許可以用知道的這個區間內的所有來給破解RSA的演算法提速數以萬倍,但是這個數字很容易就被4096位的金鑰是提高的安全性矮化,因為當從金鑰長度2048增加到從4096位,General number field sieve解密的複雜度提高了將近一千億倍,具體計算見這裡。
各位看官,看到這兒,你是不是心寬了很多。但是請注意,我們現在說的所有,還只不過是一種比較流行的加密演算法。如果這個演算法真的失效,我們完全可以選擇另外一種更加安全的演算法。加密解密這個獵和老鼠的遊戲裡沒有永遠的贏家和永遠的輸家。有時候有一條腿可能走得快一些,有時候另外一條腿走得快一些,但是如果某一條腿完全停了下來,另一條腿還能繼續走下去嗎?
後量子時代的密碼學Post Quantum Cryptology這門新的學科已經展現出了強大的生命力。我們對於普通人加密解密安全性的擔憂有點過於杞人憂天了。