量子計算或?qū)⑼{比特幣安全 信用卡等基于非對稱加密系統(tǒng)將不再可信

在奉上有關(guān)「共識機制」的文章前，我們先來點甜點。

在兩周前的 BBL 上，我給團隊介紹了 bitcoin，相關(guān)的 slides 見：

github.com/tyrchen/unchained

其中花了點時間談?wù)摿?quantum computing 對 bitcoin 的威脅。上周 google 發(fā)布了 72 量子比特通用量子計算機，引發(fā)了大家的熱議 —— 尤其是，看上去牢不可破的 cryptocurrency，是不是到了快要被終結(jié)的時刻？

下圖是當(dāng)時我 talk 時講的內(nèi)容：

首先我們看量子計算中已經(jīng)比較成型的算法：Shor’s algorithm（下文簡稱 Shor） 和 Grover’s algorithm（下文簡稱為 Grover）。

Shor 不是通用的算法，它解決因式分解的問題 —— 給定一個整數(shù) N，找到其質(zhì)因數(shù)。以下是 Wikipedia 的介紹：

On a quantum computer, to factor an integer N, Shor’s algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input).[1] Specifically it takes quantum gates of order O((log N)3) using fast multiplication,[2] demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus in the complexity class BQP. This is substantially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time – about O(pow(e, 1.9(log N)1/3(log log N)2/3)).[3] The efficiency of Shor’s algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings.

簡單說，Shor 就是把指數(shù)級的時間復(fù)雜度降維成了 polynomial time，也就是多項式時間。所謂多項式時間，就是 O(nk)，其中 k 是個常量。下圖是時間復(fù)雜度的對比，大家可以看到，指數(shù)（2n）到多項式（n2）差異非常大：

雖然 Shor 只能加速因式分解，但如果你了解非對稱加密的算法，你會記得 RSA 的基石就是兩個大質(zhì)數(shù) p 和 q 的合數(shù)很難被因式分解出 p 和 q。

大概五到十年前，人類通過通用計算機分解出來的最大的整數(shù)是 768 bit，因而理論上 RSA 密鑰低于這個數(shù)字就是不安全的。實際生活中，我們基本會用 4096 長度的密鑰：

$ ssh-keygen -t rsa -b 4096 -C "tyr@awesome.com"

對于一個 768bit（二進制）大小的整數(shù)，我們對比兩個算法的復(fù)雜度：

> n = 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

1.2301866845301178e+231

> logn = Math.log(n)

532.1043224155328

> loglogn = Math.log(logn)

6.276839564883618

> pow1 = Math.pow(logn, 1/3)

8.103368625868256

> pow2 = Math.pow(loglogn, 2/3)

3.402728919940164

> 1.9 * pow1 * pow

252.389776867137634

> Math.pow(e, 52.389776867137634)

5.65706279069233e+22

> Math.pow(logn, 3)

150657362.61267015

前者是 1022，后者 109，如果 1ns 完成一個 operation（當(dāng)然兩個算法一次 operation 的時間是不等的，但是常量），前者需要 180 萬年，后者需要 1s。

由此可見，Shor 對 RSA 體系的破壞性是顯而易見的，而且，它的變種，對基于橢圓雙曲線的 ECDSA 也有類似的降維殺傷力。從這個角度上講，量子計算機不斷走向成熟，整個非對稱加密體系下的算法都會受到巨大的沖擊 —— PKI 將坍塌，你訪問 chase.com，CA 已經(jīng)無法證明 chase.com 的 cert 屬于 Chase；你也無法使用公鑰去驗證某個私鑰的簽名，因為私鑰變得可以被公鑰推導(dǎo)出來。所以，岌岌可危的并非 bitcoin，而是整個 internet。你無法信任你的銀行的網(wǎng)站，銀行無法信任你的 USB token 里的私鑰提供出來的簽名。我們的數(shù)字化生活會走向暗黑時代。

然而你還是能信任你的 bitcoin 錢包。雖然 bitcoin 錢包的私鑰和錢包地址都來源于 ECDSA 的私鑰和公鑰，然而錢包地址并非直接是公鑰，而是公鑰的 hash。因而，你給一個錢包打錢，并不會需要錢包的公鑰；只有這個錢包使用里面的錢（給別人打錢）時，才需要把自己的公鑰放在 transaction 里。如果一個錢包只是收錢，那么它是安全的 —— 即便 Shor 算法也需要公鑰去逆向私鑰。因為公鑰沒有暴露出來，Shor 算法無法使用。因而即便量子計算破解了非對稱加密算法，對于那些沒有使用過的冷錢包（code wallet），也無法破解。對于那些需要 multisig 的錢包，也是類似。

如果非得破解冷錢包，那么需要先把錢包地址逆向出來其公鑰，而這個操作 Shor 無法完成，只能借助其他算法。

這個算法是 Grover。先看 Wiki：

Grover’s algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just O(sqrt N) evaluations of the function, where N is the size of the function’s domain. It was devised by Lov Grover in 1996.

基本上，Grover 對于函數(shù) f(x) = y，只要給定 y，以及 x 取值的一個列表，它可以以 O(sqrt N) 的時間復(fù)雜度，找到這個 x。換句話說，隨便一個算法，正常情況下暴力破解（在算法的定義域里一個個試），是 O(N)，Grover 將其降低成 O(sqrt N)，對于時間復(fù)雜度來說，這算法雖然看上去不錯，但大多數(shù)情況下只是聊勝于無。下圖是它和 log N 對比：

我們看一個 256bit 的公鑰，其 O(sqrt N) 是多大。我們先得找 256bit 數(shù)字的取值范圍：

> n_max = 0b111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

5.78960446186581e+76

> Math.sqrt(n_max)

2.4061596916800453e+38

> Math.log(n_max)

176.75253104278605

可以看到，雖然 sqrt 后量級已經(jīng)大大減少，但還是 trillion trillion trillion 級別，在一個可以預(yù)見的時間內(nèi)無法破解。所以，即便使用了 Grover 算法，也無法有效地通過錢包地址破解出公鑰，進而進一步使用 Shor 算法從公鑰破解出私鑰。

從這個意義上講，bitcoin 對 quantum computing 還是有一定免疫力的。在大家擔(dān)憂量子時代到來后（可能二三十年到來，也可能三五十年） bitcoin 的前景時，還是先擔(dān)憂一下現(xiàn)有的 PKI 體系吧，畢竟，信用卡，網(wǎng)銀，微信支付，支付寶等所有基于非對稱加密來保證安全的系統(tǒng)，可能都會變得不再可信。你以為你大爺是你大爺，可是你大爺真的不再是你大爺了。

原文標(biāo)題：《量子計算對 bitcoin 的威脅》

生成海報

免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請進一步核實，并對任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對有關(guān)資料所引致的錯誤、不確或遺漏，概不負(fù)任何法律責(zé)任。任何單位或個人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實內(nèi)容時，應(yīng)及時向本網(wǎng)站提出書面權(quán)利通知或不實情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關(guān)文章源頭核實，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。