深度剖析比特幣背后的技術(shù)細節(jié)

"擁有"一枚比特幣究竟意味著什么？

很多人都聽說過比特幣, 它是一種數(shù)字貨幣，并不需要特定政府發(fā)行, 也不依賴銀行來管理賬戶及驗證交易, 甚至都沒有人真正知曉其發(fā)明者，很多人都不知道上面那個問題的答案, 或者說至少不全了解. 要想搞明白，同時也為了讓比特幣背后的技術(shù)細節(jié)顯得直觀, 我們將從你會如何發(fā)明自的比特幣的過程中一步一步地闡明.

首先我們從你用于記錄你與好友們交易的公共賬本開始, 然而你與好友及世界上的其他人的互信開始逐漸降低. 但聰明的你引入了密碼學(xué)中的某些概念來解決信任危機, 你就創(chuàng)造了一種新事物，叫做"加密貨幣".

比特幣只是第一個被廣泛應(yīng)用的加密貨幣的例子, 而如今有了更多其他的加密貨幣并與傳統(tǒng)貨幣可以發(fā)生交易. 現(xiàn)在從你想要發(fā)明你自己的加密貨幣入手, 能幫助我們理解如今幾大主流加密貨幣的理論基礎(chǔ), 了解其背后在不同方面存在著不同的設(shè)計空間.

事實上我選這個選題是因為在過去一年中針對加密貨幣有大量的關(guān)注、資本投入甚至老實講還有媒體過分渲染. 我并不會對當(dāng)前及未來的匯率發(fā)表評論及預(yù)測, 但我想任何想要購買加密貨幣的人都應(yīng)搞明白加密貨幣究竟是怎么一回事.

我不會含糊地將其與挖礦作類比, 我會直接描述當(dāng)我們發(fā)送、接受、創(chuàng)造加密貨幣時候, 計算機內(nèi)部所發(fā)生的事情和原理.

我還要強調(diào)一點：雖然我們將花一些時間稍深入地了解背后的原理, 但是如果僅僅日常使用的話，我們并不需要了解其詳細技術(shù)原理, 就像你不需要了解你刷信用卡背后所發(fā)生的一切一樣. 與電子支付一樣，加密貨幣也有很多方便易用的App可以直接用于發(fā)送和接受貨幣, 而不需要知道是怎么實現(xiàn)的.

區(qū)別在于加密貨幣的背后并不是某家銀行來驗證交易, 而是一套基于密碼學(xué)中某些數(shù)學(xué)方法的, 來在去中心化的、互不信任的交易下驗證交易的可靠.

在開始講之前，你暫時把加密貨幣放在一邊, 我們先從更基本的概念入手：賬本和電子簽名。

如果你和你的朋友們有很頻繁的金錢來往, 比如AA支付晚餐的賬單等等, 總是用現(xiàn)金總是不方便的. 所以可能會用到一個公共賬本: 它記錄了未來將要償還的所有數(shù)目, 如Alice支付Bob 20元，Bob支付Charlie 40元等等.

這個賬本必須是公開的，每個人都能查閱, 就像一個網(wǎng)站一樣，每個人都能查閱并添加新的交易記錄. 而到了每個月底大家對交易記錄都無異議就會一起把賬算清. 如果你入不敷出，就要再掏錢出來. 如果仍有結(jié)余，就可以從中拿回自己多付的錢.

所以這個簡單體系的設(shè)計大概會是如下所述: 每個人都能向賬本添加新的交易信息，到月底再用真金白銀統(tǒng)一結(jié)算.

但這樣的公共賬本存在一個問題，正因為每個人都能添加交易記錄, 應(yīng)該怎樣避免Bob在沒有經(jīng)過Alice同意的情況下偷偷記下：Alice給Bob 100元. (這樣月底結(jié)算時候, Alice就要為這筆捏造出來的交易付錢出來了).

我們又憑什么相信賬本中的記錄都準確無誤呢, 這里就需要密碼學(xué)中的電子簽名技術(shù). 就像手寫簽名一樣，Alice需能在每筆交易信息邊上留下記錄, 以證明她了解并且認可這筆交易發(fā)生, 而且這個簽名不能被他人獲取并偽造.

電子簽名確保交易的真實性

乍一思索電子簽名似乎不太可能實現(xiàn), 無論電子簽名是如何存儲的，計算機都可以讀取并復(fù)制. 那究竟該如何防止偽造呢? 要實現(xiàn)電子簽名，每個人都需要生成一對秘鑰: 公共密鑰及私人密鑰.

每一個密鑰其實都是一串 0 或 1 比特串. 私人密鑰有時也被叫做"秘密"鑰匙, 以便能夠縮寫成 sk, 公共密鑰則縮寫成 pk.

正如其名，私人密鑰是由你自己保存的, 現(xiàn)實生活中，你本人所簽署的所有文件中的簽名都是一樣的. 電子簽名則更進一步，它會隨著簽署的內(nèi)容變化而改變. 它看上去就是一串10代碼，通常長度是256位. 而任何要加密內(nèi)容的一個字符的變動都會讓這串產(chǎn)生的新的簽名變得完全不同.

正式一點地講，產(chǎn)生這樣的簽名需要一個函數(shù) Sign, 它同時要求所簽署的內(nèi)容以及你的私人密鑰,也就是Sign(簽署的內(nèi)容, 秘鑰) → 生成新的簽名.

私人密鑰確保了只有你本人能產(chǎn)生這個電子簽名, 這個產(chǎn)生的簽名還取決于所要簽署的內(nèi)容, 就意味著其他人不能簡單地復(fù)制這個簽名, 并在其他捏造的內(nèi)容上偽造另一個簽名(因為捏造的內(nèi)容肯定與原內(nèi)容不同).

與此同時還有一個函數(shù) Verify 驗證用于驗證簽名是否真實, 而這個函數(shù)還需要三樣?xùn)|西:簽署的內(nèi)容, 生成的簽名, 公共密鑰. 它的作用是告訴我們這個簽名是否是由輸入公鑰對應(yīng)私鑰來生成的.

這里并不會具體討論這些函數(shù)具體如何實現(xiàn)([遇見數(shù)學(xué)]會在未來《圖解密碼學(xué)》中介紹), 但它保證了如果你不知道對方私鑰的情況下，幾乎不可能找到一個正確的簽名. 準確地講，只有通過窮舉并反復(fù)驗證才有可能找到正確的簽名, 然后用公開的公鑰 pk 來通過驗證.

現(xiàn)在想想256位比特到底有多少可能的簽名, 總共有2256次方個可能的簽名, 這是一個天文數(shù)字, 稱其為天文數(shù)字實際上又遠遠高估了天文學(xué)的范疇, 我還做了另一個補充視頻來演示這個數(shù)字究竟有多大，文后會詳細介紹。

現(xiàn)在如果一旦你驗證了一個簽名是真的, 你就能相當(dāng)有把握地認為, 這個簽名只能由他本人持有的私鑰加密產(chǎn)生.

編號確保交易唯一性

現(xiàn)在確保了每個人都會在交易信息后面簽名, 不過仍然會存在另一個問題, 比如Alice簽署了一條Alice支付Bob 100元的交易記錄, 即便Bob不能在Alice的新交易記錄上偽造簽名, 他還可以把這條記錄隨心所欲地復(fù)制好幾遍, 因為這些記錄以及它對應(yīng)的簽名都是正確的.

要解決這個問題，你在簽署每一筆新的交易信息時, 交易信息還必須包含一個唯一的編號與之對應(yīng). 那樣如果Alice多次支付Bob 100元的話, 賬本上的每條記錄都會要求一個新的簽名.

有了電子簽名就解決絕大部分了原本體系中的信任危機, 但要真正實現(xiàn)，仍然需要依賴一個類似的信用機構(gòu), 也就是說你信任每個人到了月底都會出現(xiàn)并用現(xiàn)金結(jié)算, 因為萬一Charlie欠了很多錢但就是不出來還錢該怎么辦, 這就是月底人們再次用現(xiàn)金結(jié)算的唯一原因 - 擔(dān)心某些人(比如 Charlie) 欠了很多錢.

聰明的你想到了一個方法就不需要真正再用現(xiàn)金結(jié)算, 只要能夠避免其中有些人的支出金額小于剩余可支付金額. 比如所有人剛開始就需要往賬上支付100元，賬本上最先記錄幾條：Alice獲得100元，Bob獲得100元，Charlie等等.

現(xiàn)在只需要拒絕在賬本上記錄某些人入不敷出的交易就可以了, 舉個例子，如果前兩條交易記錄是: Charlie支付Alice 50元，Charlie支付Bob 50元. 再來如果Charlie還要支付你20元的時候，那這項交易將是無效的，這就跟他沒有簽名一樣是無效的.

不過這就意味著驗證當(dāng)前的一條交易, 就需要了解截至當(dāng)前所有的歷史交易信息. 這在加密貨幣中同樣如此，并且仍有待優(yōu)化的余地.

但有趣的是，這個設(shè)計真正去掉了賬本和真實美元之間的聯(lián)系, 理論上如果世界上所有人都是用這個賬本, 你整個一生都可以在這個賬本上支付并獲得收入中度過, 根本沒有必要獲得真實的貨幣.

為了強調(diào)這一點，我們把賬本上的貨幣單位稱之為"賬本元"，并簡稱為LD. 當(dāng)然, 你也可以隨時將LD自由地兌換成真的美元.

舉個例子，Alice在現(xiàn)實中給了Bob 100元, 同時Bob在公共賬本上記上Bob支付Alice 100元. 但這樣的兌換并不在這套系統(tǒng)的設(shè)計初衷之內(nèi), 所以不會受協(xié)議的保護. 這樣的兌換與美元和歐元或市場上其他的貨幣兌換類似, 那是另外一個事情了.

比特幣的核心

這是理解比特幣和其他加密貨幣的最重要的信息了, 它實際上就是一個賬本, 所有的歷史交易就視為貨幣的實體.

當(dāng)然就比特幣而言, 人們只有用現(xiàn)金購買和使用比特幣才會在賬本上記錄. 但新的比特幣如何產(chǎn)生我一會兒再細說.

但此之前，我們的LD體系和實際的加密貨幣還有一處不同, 我剛提到這個公共賬本存在于某個公共地點. 比如一個網(wǎng)站，所有人都能登陸并添加記錄, 那樣的話我們就必須信任這一中心機構(gòu). 那究竟誰來管理這個網(wǎng)站，誰來控制添加記錄的規(guī)則呢?

考慮到如果讓所有人都能獲取這份賬本也就不需要信任中心機構(gòu)了. 當(dāng)你需要發(fā)生交易，如Alice支付Bob 100元, 你需要將這個信息廣播給網(wǎng)絡(luò)中所有的其他人, 他人收到了這個信息都在自己那份賬本上記下這條交易.

這樣想法雖然簡單，但真的這樣設(shè)計就會相當(dāng)糟糕, 因為如何確保所有人手里都是正確的那份賬本呢

當(dāng)Bob收到了如Alice支付Bob 10 LD 的交易，他如何確保并相信其他所有人也同樣收到了這一信息, 以便未來能讓他在可以用這 10 LD支付給Charlie做交易呢?

試著想想是你自己收聽著來自外界的交易信息廣播, 該如何確保其他人和你一樣以相同的順序接受交易信息, 這才是關(guān)鍵所在，也是一個有趣的難題.

你能想出一個協(xié)議來決定接受或拒絕收到的交易信息, 而且你確信其他所有人在這個方法下能以同樣的順序接受交易信息, 最終可以形成一模一樣的賬單, 這也是比特幣原始論文中詳述的部分.

簡單地講，比特幣給出解決辦法是: 選擇信任消耗最多計算資源(計算量最大)的那份賬本. 我會花一些時間詳細講是什么意思, 它涉及到"加密散列函數(shù)"這個概念.

基本的思路如下：如果你將計算資源的消耗作為你信任的基礎(chǔ)，那么偽造交易記錄和賬本不一致的情形所要耗費的計算力成本要高到不可行。

這個想法實在是太酷了！如果你懂了，你就會理解比特幣和其他加密貨幣的核心.

那么首先，什么是散列(哈希)函數(shù)？這些函數(shù)的輸入可以是任何信息或文件, 它們會輸出一個固定長度的比特字符串，如256位, 這個輸出值叫做這個信息的散列值，或者稱其為"摘要", 它故意設(shè)計成會輸出看似相當(dāng)隨機的內(nèi)容, 但并不是隨機的，只要是給定相同的信息總是輸出相同的內(nèi)容.

但如果你將輸入稍作修改，也許僅僅只是修改了其中一個字符，最終的散列值會變得面目全非. 事實上，我這里做演示的散列函數(shù)叫做"SHA256" .

輸入的輕微修改，輸出就會完全不同，毫無規(guī)律可言, 明白了吧，這不是普通的散列函數(shù)，這是加密散列函數(shù), 這就意味著逆向計算是不可能的.

如果告訴你一串 256 位的1,0的字符串然后問你, 找到SHA256 函數(shù)輸入的內(nèi)容, 使得兩者經(jīng)過 SHA256 后具有同樣的結(jié)果. 你只有一個一個暴力去試錯的方法.

不過你想感受一下2^256次方個嘗試究竟需要計算多久, 可以看看這個補充視頻(《256位加密有多安全?》過幾天[遇見數(shù)學(xué)]會整理出來).

你會想如果知道了這個函數(shù)的運作細節(jié), 是不是就可以不用瞎猜, 而是可以倒推回來猜出這個輸入呢. 但目前沒有人可以做到.

有趣的是，目前還沒有嚴格的證明逆向計算是困難的, 但目前大量的安全行業(yè)和加密需求都取決于加密散列函數(shù)以及它的這個性質(zhì).

如果你細看瀏覽器和 youtube 建立的加密連接背后的加密算法, 或瀏覽器連接銀行網(wǎng)站時, 你很可能會看到SHA256算法.

但現(xiàn)在，我們的關(guān)注點會是這樣的散裂函數(shù)如何證明賬單上一系列的交易是和一個很大計算量有關(guān)系呢?

想想如果有人給你一份交易記錄，并說"嘿！我發(fā)現(xiàn)了一個特殊的數(shù)字(下圖中賬本中綠色數(shù)字 1073765433)，你把這個數(shù)字放在這份交易記錄后面, 然后在給整個交易記錄信息進行SHA256函數(shù)計算后, 前面30個數(shù)字都會是0！"

你想想找到這樣的一個數(shù)字有多難？對于一個隨機的信息，其散列值前30位都是0的概率是2的30次方分之一, 也就是差不多是十億分之一, 而且因為SHA256是一個加密散列函數(shù), 找到這個特殊數(shù)字的唯一方法只能是暴力窮舉驗證, 所以你基本上已經(jīng)嘗試了十億次, 才找到了這個特別數(shù)字.

而你一旦知道了這個數(shù)字，很快計算一下這個交易列表和數(shù)字在一起作為輸入, 經(jīng)過散列計算后發(fā)現(xiàn)開頭確實是30個0就行列.

換言之，你能很快地驗證他們確實經(jīng)過了大量的計算, 而你不需要親自消耗這么大計算量。這叫做"工作量證明".

重要的是，這個工作量證明本身就對應(yīng)列這份交易記錄. 如果你更改了其中一條交易信息，即便是修改列一個數(shù)字, 也會完全改變最終的散列值. 所以就又需要經(jīng)過十億次嘗試才能找到新的工作量證明 - 即找到那個特別數(shù)字, 接在你修改后的交易列表后面, 使得對應(yīng)的散列值開頭是 30 個0.

現(xiàn)在回過頭來考慮我們的分布式賬本的情形：每個人都在廣播交易信息，我們想找到一個方法能讓所有人都認可一份正確的賬單. 我前面說過比特幣原始論文的核心點就是, 每個人都信任需要消耗最大計算量的那份賬單.

要實現(xiàn)這個想法首先需要將賬單整理成"區(qū)塊". 這些區(qū)塊包含了一系列交易信息以及其工作量證明, 也即有一個特別數(shù)字滿足其散列值以一系列0開頭.

我們暫時先定60個0開頭吧，一會兒我們會回頭來看如何系統(tǒng)地確定這些0的個數(shù).

類比于交易信息要經(jīng)過發(fā)送方簽名才被認定為有效, 同樣的, 一個區(qū)塊只有當(dāng)它有工作量證明時才被認定為有效.

而且為了確保這些區(qū)塊有一個標準的順序, 我們規(guī)定前一區(qū)塊的散列值必須加入到當(dāng)前區(qū)塊的頭部信息中.

這樣的話，如果你回頭想改變其中某個區(qū)塊的內(nèi)容, 或交換兩個區(qū)塊的順序, 你就會改變它后一個區(qū)塊的內(nèi)容, 也就改變了那個區(qū)塊的散列值, 然后又影響到再下一個區(qū)塊......

這就需要重新計算所有這些區(qū)塊的散列值，重新尋找每個特別數(shù)字使得區(qū)塊的散列值以60個0開頭. 因為所有的區(qū)塊以這種方式相互鏈接, 所以我們一般不把它叫做賬本，而是為"區(qū)塊鏈"(blockchain).

在這個新的體系之下，我們現(xiàn)在允許世界上的每個人都參與建造區(qū)塊, 意思是說他們都可以收聽網(wǎng)絡(luò)中的交易信息，整理這些信息生成區(qū)塊，然后花大量的計算工作, 找到那個特別數(shù)字使得區(qū)塊的散列值以60個0開頭.

一旦找到了這個數(shù)字，他們就將這個區(qū)塊廣播出去. 為了獎勵這個區(qū)塊建立者所消耗巨大的計算量付出，當(dāng)她建立了一個區(qū)塊，我們規(guī)定她可以把一筆特別的交易信息放在賬單開頭，即：讓她憑空獲得10 LD。這叫做"區(qū)塊獎勵"，這并不屬于任何交易, 它并不來自于其他人，所以也并不需要簽名。

這也意味著, 每一個新建的區(qū)塊都會增添新的虛擬貨幣, 建立區(qū)塊通常叫做"挖礦"，因為它會需要消耗大量的計算工作量, 挖礦會為整個經(jīng)濟中引入新的貨幣量.

所以當(dāng)你聽到或看到礦工時, 你現(xiàn)在明白他們所做的其實就是:收聽交易信息，建立區(qū)塊，廣播區(qū)塊，并獲得新貨幣的獎勵，如此而已．

而在礦工眼中，每個區(qū)塊就像是一個小型的彩票，每個人都想盡可能快得猜對那個特殊的數(shù)字，直到其中有一個幸運兒找到了那個特別數(shù)字，能讓區(qū)塊的散列值以很多0開頭，然后他們就得到獎勵.

而對于其他只是想利用這個系統(tǒng)做交易的人而言，并不需要收聽交易記錄，他們只需要收聽被礦工廣播的區(qū)塊即可，然后更新自己保持的區(qū)塊鏈就可以了.

現(xiàn)在我們協(xié)議的關(guān)鍵點來了, 如果我們收到了兩份完全不同的區(qū)塊鏈，其中交易信息相沖突的時候, 你只保留最長的那一個，也就是包含最大的工作量的那一份(比如區(qū)塊鏈長度為 4和5 , 就選擇長度為 5 的那份)。

如果暫時難分上下，等待下一個區(qū)塊的廣播，總有一個會形成更長的區(qū)塊鏈, 所以即便沒有中心權(quán)威機構(gòu)，所有人也都各自記錄自己的那份區(qū)塊鏈, 但如果每個人都信任最多工作量的那個區(qū)塊鏈，我們就達到了一個去中心化的共識.

為了理解這個系統(tǒng)為什么可信，以及怎樣才應(yīng)該相信每一筆交易是否真實. 我們其實可以去理解, 要怎么做才能在這個系統(tǒng)下進行欺騙.

也許Alice想要用一個偽造的區(qū)塊欺騙Bob, 也就是她給Bob一個區(qū)塊里包含里她支付Bob 100賬元的信息, 但她沒有把這個區(qū)塊廣播給網(wǎng)絡(luò)中的其他人. 那樣的話，其他人都還以為她仍然持有那100賬元. 為了做到這一點, 她要比其他所有礦工先找到工作量證明才能欺騙所有人, 因為所有的礦工他們也都在獨立建造區(qū)塊.

而這確實是有可能發(fā)生的！有可能Alice剛好比其他所有人都先找到了這個表示計算量的特殊數(shù)字, 但Bob也還會收到來自其他礦工的區(qū)塊廣播. 所以為了讓他相信她那份偽造的區(qū)塊，Alice后面都要持續(xù)重新計算, 她那份偽造給Bob的區(qū)塊后面的所有區(qū)塊, 這些區(qū)塊和Bob收到了來自其他礦工的區(qū)塊都不同.

但系統(tǒng)協(xié)議規(guī)定Bob總是信任他所指的最長的那一個區(qū)塊鏈, Alice在前幾個區(qū)塊還有可能保持領(lǐng)先 - 剛好碰巧她比其他所有礦工都先找到那個區(qū)塊.

但除非她擁有接近所有礦工的計算資源的50%, 否則, 從概率上看, 基本能肯定的是其他所有礦工計算的區(qū)塊會比Alice偽造給Bob的區(qū)塊形成的區(qū)塊鏈更長更快.

所以經(jīng)過足夠長的時間，Bob會拒絕他收到的來自Alice的區(qū)塊鏈, 而選擇其他所有人都在使用的最長的區(qū)塊鏈.

注意了, 這意味著你不一定要信任你剛剛接受到的新區(qū)塊, 而應(yīng)該等后面有新的幾個區(qū)塊添加后, 如果你還沒收聽到更長的區(qū)塊鏈，你就能信任這個區(qū)塊的確屬于其他所有人都在用的那條鏈上.

到此，我們講解了所有主要內(nèi)容, 這個基于工作量證明的分布式賬本系統(tǒng), 基本上就是比特幣還有其他加密貨幣的工作原理. 再講講更多的細節(jié), 剛我講到工作量證明, 就是尋找那一個特別數(shù)字, 滿足其區(qū)塊的散列值以60個0開頭. 而現(xiàn)實的比特幣協(xié)議中會定理改變 0 的個數(shù), 好保證平均每10分鐘可以產(chǎn)生一個新的區(qū)塊.

當(dāng)有越來越多的礦工加入到"挖礦"的行列中后, 這個計算的挑戰(zhàn)性也越來越高. 好讓這個小彩票, 大約每 10 分鐘才能有一個人中獎. 很多新的加密貨幣有更短的區(qū)塊時間間隔.

比特幣體系中所有的比特幣都來自于生成新區(qū)塊的獎勵, 在一開始，是每區(qū)塊50個比特幣. 還有一個叫做"Block Explorer"的網(wǎng)站你可以去看看, 上面能輕松地看到比特幣區(qū)塊鏈中的信息, 如果你看區(qū)塊鏈最初識的那幾個區(qū)塊, 它們除了獎勵給礦工的50個比特幣之外并沒有其他交易.

但每過210000個區(qū)塊，差不多每4年，區(qū)塊獎勵就會減半. 現(xiàn)在，每個區(qū)塊的獎勵是12.5個比特幣, 也因為這個獎勵隨著時間等比減少, 也就意味著最終可獲取的比特幣不會超過21000000. 但這并不是說礦工最終賺不到錢, 除了區(qū)塊獎勵外，礦工還可以獲得交易費, 每當(dāng)你支付時，你可選擇一小筆交易費一起支付, 這筆交易費最終會給包含這筆記錄的區(qū)塊建立者, 你這么做能夠激勵礦工們繼續(xù)工作, 將包含你這筆交易信息的區(qū)塊廣播給網(wǎng)絡(luò)中的其他人.

在比特幣中，每個區(qū)塊包含約2400筆交易記錄, 很多批判家認為這個限制過于嚴格, 與VISA比較，VISA每秒平均處理約1700筆交易, 而有能力每秒能夠處理多達24000筆交易. 相比而言比特幣較慢的交易速度使得它的交易費用更高, 正是交易費用決定了礦工哪些交易加入到新的區(qū)塊中.

除了以上這些加密貨幣的基礎(chǔ)知識, 還有其他許多不同的加密貨幣的系統(tǒng)設(shè)計尚未涉及, 但我希望這個視頻能稱為堅實的求知欲基石, 感興趣的話, 可以擴展閱讀, 繼續(xù)學(xué)習(xí). 正如我開頭所說，我做此視頻的初衷是因為許多的資金涌入加密貨幣中, 是好是壞我并不過多評價, 但我認為想要進入這一領(lǐng)域的人, 至少了解這門技術(shù)的基礎(chǔ), 應(yīng)該是很有益的.

256加密有多安全

為了攻破一個安全系統(tǒng), 你必須得猜對一個256位的比特串. 第一次是在電子簽名的部分提的, 第二次是在密碼散列函數(shù)的部分提到的.

比如說，假如你想找到一條信息讓它的SHA256 散列值(哈希值)等于某個 256位比特串的話, 沒有其他辦法，只能暴力猜測, 并檢驗結(jié)果. 這需要嘗試

22562256次.

這個數(shù)字比我們通常遇到的數(shù)都要大得多, 因此很難去體會它的規(guī)模. 不過我們不妨試一試,22562256也就是232232, 和它自己相乘 8 次

這樣分解的好處在于我們知道232232大約是 40億這樣一個數(shù)量.

我們起碼可以想象"小一點"這個數(shù)字吧, 嗯，再來就是去體會 40 億連續(xù)相乘 8 次是怎樣的概念？很多人知道，我們的電腦里的 GPU 可以飛速的進行大量的并行計算. 因此要請你專門讓 GPU 反復(fù)計算密碼散列函數(shù). 一個性能很好的 GPU 每秒也許能算出接近 10 億個散列值.

假如你拿上一堆這樣的 GPU , 而讓你這臺超級電腦每秒能算 40 億個散列值, 那么就開始的 40 億代表了你這臺超級電腦每秒算出的散列值的數(shù)目.

想象一下 40 億臺這樣滿載 GPU 的超級電腦, 跟 Google 對比下, 雖然谷歌沒有對外公布他們的服務(wù)器數(shù)量, 但是有估計說大概有幾百萬臺. 現(xiàn)實中他們大部分服務(wù)器的算力都不如我們滿載 GPU 的電腦強, 我們假設(shè)谷歌把上百萬個服務(wù)器全換成這樣的超級電腦. 那么 40 億臺超級電腦大概是 1000 個這種打了雞血后的谷歌. 我們就把這個算力叫做 "千谷歌"吧.

我們再往右看, 全世界的人口大概有73億, 接下來我們假設(shè)一多半的人(40億臺)都擁有自己的千谷歌,

然后想象, 40 億個這樣的地球, 作為對比，銀河系大約有 1000 到 4000 億顆恒星, 雖然我們并不確定，但估算大致就在這個范圍. 所以這相當(dāng)于銀河系的 1% 恒星, 并且每個地球上一半的人口都擁有自己的千谷歌.

接著想象, 40 億個這樣的銀河系, 我們把它叫做"億萬星系超級計算機", 每秒能猜21602160次.

40 億秒, 大概是 126.8 年, 它的 40 億倍, 就是 5070 億年, 差不多是宇宙年齡的37倍. 所以就算你有( GPU 滿滿的超級計算機) * (地球上超過一般人都擁有千谷歌) * (行星云集) * (億萬星系計算機) * (猜上 37 倍宇宙年齡的時間), 也只有 40 億分之一的可能性猜測到正確的數(shù)字.

密碼學(xué)原理

知道什么是公鑰密碼學(xué)的人可能已經(jīng)聽說過ECC、ECDH或是ECDSA。第一個術(shù)語是橢圓曲線密碼學(xué)（Elliptic Curve Cryptography） 的縮寫，后兩個是基于它的算法名稱。

如今，我們可以在TLS、PGP和SSH中見到橢圓曲線加密系統(tǒng)，這是現(xiàn)代網(wǎng)絡(luò)和IT世界所依賴的三種主要技術(shù)。比特幣和其他加密貨幣就是利用這種加密算法進行加密的。

在ECC流行起來之前，幾乎所有的公鑰算法都是基于RSA、DSA和DH ———— 基于模運算的可選加密系統(tǒng)。RSA及其友類算法在當(dāng)前仍非常重要，經(jīng)常與ECC一并使用。不過，RSA及其友類算法背后的原理很容易解釋，因而被廣泛理解，一些簡單的實現(xiàn)也可以很容易編寫出來；但ECC的實現(xiàn)基礎(chǔ)對于大多數(shù)人來說仍很神秘。

通過一系列的博文，我打算用一個通俗的方式介紹橢圓曲線密碼學(xué)。我的目標不是提供ECC完整和詳細的指導(dǎo)（網(wǎng)上有這方面的充足信息），而是簡單概述“ECC是什么、為什么它被認為是安全的”，避免把時間浪費在長篇的數(shù)學(xué)證明和惱人的實現(xiàn)細節(jié)上。我還將提供一些輔助示例以及可視化圖形工具和腳本給大家使用。

具體來說，我將觸及以下主題：

1. 基于實數(shù)域的橢圓曲線和群公理（本文中涉及）

2. 基于有限域的橢圓曲線和離散對數(shù)問題

3. 密鑰對的生成以及兩個ECC算法：ECDH和ECDSA

4. 破壞ECC安全性的算法，并與RSA作對比

為了能夠理解本文所述的內(nèi)容，你需要了解集（set)理論、幾何、模運算等基本概念，并大致知道對稱式和非對稱式加密。此外，你需要清楚的知道什么是“易解”問題，什么是“難解”問題，以及它們在密碼學(xué)中的角色。

準備好了嗎？開始！

橢圓曲線

首先，什么是橢圓曲線？ MathWorld 線上數(shù)學(xué)百科全書給出了一個極好并完整的定義。不過，針對我們的學(xué)習(xí)目的，橢圓曲線將簡化為用下面這個等式所描述的點的集合：

其中， 4a3 + 27b2 ≠ 0 (這是為了排除奇曲線)。上面的等式稱為橢圓曲線的魏爾斯特拉斯范式（ Weierstrass normal form）

不同的橢圓曲線的不同形狀 (b = 1, a 取值由 2 變化至 -3).

奇點類型: 左側(cè), 帶一個尖角的曲線 (y2 = x3)。右側(cè), 帶一個自交叉的曲線 (y2 = x3 – 3x + 2). 這兩種都不是有效的橢圓曲線。

根據(jù)a和b的值，橢圓曲線在平面上可以呈現(xiàn)不同形狀?？梢院苋菀卓闯霾Ⅱ炞C： 橢圓曲線是關(guān)于x-軸對稱的。為了實現(xiàn)我們的目標，我們還需要把一個無窮遠點（亦稱之為理想點) 視為橢圓曲線的一部分。從現(xiàn)在開始，我們將用符號0（零）來代表無窮遠點。

如果我們想顯式地將無窮遠點納入考慮，我們可以按如下的方式細化橢圓曲線的定義：

群

數(shù)學(xué)中的“群”是一個由我們定義了一種二元運算的集合，二元運算我們稱之為“加法”，并用符號“+”來表示。為了讓一個集合G成為群，必須定義加法運算并使之具有以下四個特性：

1. 封閉性：如果a和b是集合G中的元素，那么（a + b)也是集合G中的元素。

2. 結(jié)合律：(a + b) + c = a + (b + c);

3. 存在單位元0，使得a + 0 = 0 + a =a;

4. 每個元素都有逆元，即：對于任意a，存在b，使得a + b = 0.

如果我們增加第5個條件：

5. 交換律： a + b = b + a

那么，稱這個群為阿貝爾（abelian)群。

配上通常概念的加法時，整數(shù)的集合Z就是一個群（同時還是個阿貝爾群）。而自然數(shù)的集合（N）就不是群，因為它不滿足第4個特性。

“群”很有用，因為一旦我們證明它具備上述4個特性，那么我們就可以自由地獲取到一些其他特性。比如：單位元是唯一的；此外，逆元也是唯一的，即：對于每一個a，存在唯一的一個b，使得a + b = 0 （我們可以將b寫成-a）。后面我們會發(fā)現(xiàn)，群的這些特性以及其他存在的事實，或者直接或者間接，對于我們來說非常重要。

橢圓曲線的群公理

我們可以定義一個基于橢圓曲線的群。如下：

? 群中的元素是一條橢圓曲線上的點;

? 單位元為無窮遠點O;

? 點P的逆元是其關(guān)于x-軸的對稱點;

? 加法，滿足以下規(guī)則: 對于3個處在同一直線上的非零點 P, Q 和 R, 它們的和 P + Q + R = 0.

同一直線上的三個點之和等于0.

注意一下最后一個規(guī)則，我們需要的只是三個點同線，與點的次序無關(guān)。這意味著，如果P、Q和R同線，那么P + (Q + R) = Q + (P + R) = R + (P + Q) = ? ? ? = 0. 這樣，我們直觀地證明了我們的“+”運算既滿足結(jié)合律也滿足交換律：我們創(chuàng)建了一個阿貝爾群。

到目前還很不錯。但我們?nèi)绾螌嶋H計算任意兩點之和呢？

幾何加法

得益于我們使用的是一個阿貝爾群，我們可以把 P + Q + R = 0 寫成P + Q = –R。方程的這一形式，讓我們可以推導(dǎo)出計算兩點P和Q之和的幾何方法：畫一條過P和Q點的直線，這條直線與曲線相交得到第3個點R（這一事實意味著P、Q、R必然共線）。如果我們獲取了該點的逆元-R，那么我們就得到了P + Q的結(jié)果。

過P和Q畫一條直線。該直線與曲線相交與第3點R。與之對稱的點-R即為P+Q 的結(jié)果

這種幾何方法可以成立，但還需一些改進。特別是，我們需要回答以下幾個問題：

? 當(dāng)P = 0或Q = 0時怎么辦? 顯然，我們無法畫任何直線（0點不在xy-平面上）。不過，由于我們定義了0點為單位元，所以，對于任意P和任意Q，都有：P + 0 = P ， 0 + Q = Q

? 當(dāng)P= –Q時怎么辦? 這種情況下，通過兩點的直線是一條垂線，與曲線不會有第三個交點。不過，由于P是Q的逆元，那么由逆元的定義可知P + Q = P + (-P) = 0 .

? 當(dāng)P= Q時怎么辦? 這種情況下，經(jīng)過該點的直線有無數(shù)條。事情開始有點復(fù)雜了。不過，先想像一個點 Q’ ≠ P。如果我們令Q’ 向P逼近，越來越靠近P會怎么樣？

隨著兩個點越來越接近，過這兩點的直線最終變成了曲線的切線

隨著Q’ 趨向P, 過P和Q’ 的直線最終成為曲線的切線?？吹竭@一點，我們可以定義 P + P = –R, 其中R是過P點的切線與曲線的交點。

? 當(dāng)P ≠ Q，但找不到第三個點R時怎么辦? 這種情況和上面那個非常類似。實際上，這是因為過P和Q的直線與曲線相切。

如果直線與曲線只有兩個交點，那么該直線為曲線的切線?？梢院苋菀椎乜闯觯瑑牲c相加的結(jié)果是其中一點的對稱點

? 假設(shè)P是切點，在上一情況中，我們已經(jīng)得出P + P = –Q. 等式現(xiàn)在變?yōu)?P + Q = –P。 如果Q 是切點，正確的等式應(yīng)為 P + Q = –Q.

現(xiàn)在，用幾何方法可以完全覆蓋所有情況了。用一支鉛筆和一把尺，我們可以做任意橢圓曲線上所有點的加法運算。如果你想試試，請到 HTML5/JavaScript visual tool 看一下，這是我建的一個工具，用來計算橢圓曲線的加法!

代數(shù)加法

如果我們想把點的加法運算計算機來完成，那么需要將幾何方法轉(zhuǎn)化為代數(shù)方法。將上面描述的規(guī)則轉(zhuǎn)換為一組公式看似簡單，實際上是非常繁瑣的，因為需要求解三次方程。因此，這里我只通報結(jié)果。

首先，先拋開最惱人的極端情況。我們已經(jīng)知道P + (-P) = 0, 還知道P + 0 = 0 + P = P。所以，在我們的公式中 ，我們將避免這兩種情況，只考慮兩個非零、非對稱點 P = (xP, yP) 和Q = (xQ, yQ).

如果 P 和 Q 不相同， (xP ≠ xQ), 過這兩點的直線斜率為:

該直線與橢圓曲線交于第三點 R = (xR, yR):

或是, 等價形式:

因此，(xP, yP) + (xQ, yQ) = (xR, –yR) (注意正負號，記住P + Q = –R).

如果我們想檢查這一結(jié)果是否正確，我們將不得不檢查R是否在曲線上，同時P、Q、Q是共線。檢查點是否共線輕而易舉，但檢查R是否在曲線上就不容易了，因為需要求解三次方程，這可不是什么好玩的事兒。

不過，我們可以用一個例子來試一下：根據(jù) 可視化工具的計算， 當(dāng) P = (1, 2) 、Q = (3, 4) ，橢圓曲線 y2 = x3 – 7x + 10, 兩點之和 P + Q = –R = (-3, 2). 讓我們看一下與我們的公式是否一致:

好的，正確!

注意上面的公式即使在其中一個點P或Q是切點的情況下也成立。讓我們試一下P = (-1, 4) 、 Q = (1, 2).

我們計算出 P + Q = (1, -2), 與使用 可視化工具計算出的結(jié)果相同。

P = Q 的情況需要做點不同的處理：方程中 xR 和 yR 相同, 由于 xP = xQ, 我們必須使用不同的公式來計算斜率：

注意，我們可以料到，m的表達式實際是下面這個函數(shù)的一階導(dǎo)數(shù):

為了證明結(jié)果的有效性，只要檢查R是否在曲線上，以及P和R在曲線上只有兩個交點就足夠了。但同樣，我們不去證明這一事實，而是試算一個例子: P = Q = (1, 2).

公式計算出 P + P = –R = (-1, -4).正確!

盡管推導(dǎo)過程真的是極其繁瑣，不過最后的公式還是很簡潔。這要感謝魏爾斯特拉斯范式：要是沒有這一范式，最后的公式會真的又長又復(fù)雜。

標量乘法

在加法之外，我們還可以定義另一種運算：標量乘法，即：

nP，其中n為自然數(shù)。我為標量乘法也寫了個 可視化工具 ，如果你想試算時可以使用。

用這種形式表示時，計算nP似乎需要n次加法運算。如果n有k個二進制位，那么算法的時間復(fù)雜度將為O（2^k)，這真不是很好。不過存在一些更快的算法。

其中一種是“加倍（double)與相加（add)”算法。

計算的原理可以用一個例子來更好地解釋。取n = 151。它的二進制表示形式為100101112 。這一二進制表示形式可以轉(zhuǎn)換為一系列2的冪之和。

(取n的 每個二進制位上的數(shù)字，并用它乘以一個2的冪.)

用這種方法，我們可以將n這樣寫:

“加倍（double)與相加（add)”算法需要這樣做:

? 取 P.

? 加倍，得到2P.

? 2P與P相加(為了得到 21P + 20P).

? 加倍 2P，得到22P.

? 與前一結(jié)果相加 (得到 22P + 21P + 20P).

? 加倍 22P，得到23P.

? 對23P不做任何操作.

? 加倍23P，得到24P.

? 與前一結(jié)果相加 (得到 24P + 22P + 21P + 20P).

? …

最后，我們可以計算151 ? P ，只需7次“加倍”運算和4次“相加”運算。

如果還不夠清楚，這里有一個實現(xiàn)該算法的python代碼段：

如果“加倍”和“相加”操作復(fù)雜度均為O(1),那么 該算法的時間復(fù)雜度為O(log n) (或是O(k)，如果我們考慮的是二進制位的長度），這相當(dāng)不錯。比最初O(n)的算法肯定要好得多。

對數(shù)

給定n和P, 我們現(xiàn)在至少有一個多項式時間算法來計算Q = nP。不過，逆運算需要計算多少輪呢？如果已知Q和P，我們想求解n會怎么樣？這一問題被稱為對數(shù)問題。我們稱之為“對數(shù)”而不是“除法”是為了與其他加密系統(tǒng)（在術(shù)語上）保持統(tǒng)一（那些系統(tǒng)中，不稱“乘法”，而稱“冪”）。

我不知道任何關(guān)于對數(shù)問題的“易解”算法，不過，通過擺弄乘法 ，很容易發(fā)現(xiàn)一些模式。例如，對于曲線 y2 = x3 – 3x + 1和點 P = (0, 1). 我們可以立即驗證出, 如果n為奇數(shù)，nP在曲線的左半面，如果n為偶數(shù)，nP在曲線的右半面。如果我們嘗試更多次，我們或許可以找出更多的模式，最終可以讓我們寫出一個算法來高效計算那條曲線的對數(shù)問題。

不過，對數(shù)問題有一個變體：離散對數(shù)問題。在下一篇博文中，我們將看到，當(dāng)我們對橢圓曲線的域進行縮減后，標量乘法仍舊”易解“，而離散對數(shù)問題成為了”難解”問題。這種雙重性是橢圓曲線密碼學(xué)的關(guān)鍵基石。