深入理解企業(yè)級(jí)區(qū)塊鏈Q(jìng)uorum和IPFS

深入理解企業(yè)級(jí)區(qū)塊鏈Q(jìng)uorum和IPFS目錄TOC\h\h第1章區(qū)塊鏈的前世今生\h1.1初識(shí)區(qū)塊鏈\h1.2區(qū)塊鏈技術(shù)的演進(jìn)\h1.3區(qū)塊鏈能否“改變世界”\h第2章區(qū)塊鏈中的共識(shí)機(jī)制\h2.1分布式系統(tǒng)的一致性挑戰(zhàn)\h2.1.1若干基本原理\h2.1.2拜占庭將軍問(wèn)題\h2.2常見(jiàn)共識(shí)算法\h2.2.1PBFT算法\h2.2.2Raft算法\h2.2.3PoW算法\h2.2.4PoS算法\h第3章密碼學(xué)探秘\h3.1密碼學(xué)基礎(chǔ)知識(shí)\h3.1.1加解密的一般過(guò)程\h3.1.2密碼學(xué)發(fā)展歷程\h3.1.3密碼算法的分類\h3.1.4基礎(chǔ)理論簡(jiǎn)析\h3.2公鑰密碼體制\h3.2.1RSA算法\h3.2.2ElGamal算法\h3.2.3橢圓曲線算法\h3.2.4公鑰密碼的安全性分析\h3.3數(shù)字簽名\h3.3.1哈希函數(shù)\h3.3.2RSA簽名\h3.3.3ElGamal簽名\h3.3.4DSA\h3.3.5橢圓曲線DSA\h3.3.6數(shù)字簽名方案的安全性分析\h3.4區(qū)塊鏈中的密碼學(xué)算法\h3.5密碼學(xué)新紀(jì)元\h3.5.1同態(tài)加密技術(shù)\h3.5.2抗量子攻擊密碼\h第4章區(qū)塊鏈核心技術(shù)最佳實(shí)踐——比特幣\h4.1比特幣要解決的問(wèn)題\h4.2技術(shù)解決方案\h4.3P2P網(wǎng)絡(luò)\h4.4賬本——區(qū)塊鏈\h4.4.1區(qū)塊結(jié)構(gòu)\h4.4.2創(chuàng)世區(qū)塊\h4.4.3區(qū)塊的驗(yàn)證和鏈接\h4.5比特幣地址\h4.5.1比特幣地址的生成過(guò)程\h4.5.2比特幣公鑰格式——壓縮和非壓縮\h4.5.3比特幣私鑰導(dǎo)入的格式——WIF\h4.5.4生成自己的比特幣地址\h4.6比特幣交易——Transaction\h4.6.1交易的輸入和輸出\h4.6.2UTXO——未花費(fèi)交易輸出\h4.7腳本語(yǔ)言\h4.7.1腳本操作碼\h4.7.2交易腳本——鎖定和解鎖\h4.7.3鎖定腳本——P2PKH\h4.7.4鎖定腳本——P2SH\h4.7.5解鎖腳本\h4.7.6交易驗(yàn)證——組合驗(yàn)證腳本\h4.7.7挖礦——PoW\h4.8礦場(chǎng)和礦池\h4.8.1礦場(chǎng)\h4.8.2礦池\h4.9SPV輕錢(qián)包\h4.10區(qū)塊鏈安全\h4.10.1私鑰碰撞\h4.10.2哈希破解\h4.10.3私鑰或錢(qián)包App\h4.10.451%攻擊\h4.10.5雙花\h4.10.6可塑性攻擊\h4.11隔離見(jiàn)證\h4.12比特幣分叉\h4.12.1硬分叉和軟分叉\h4.12.2核心開(kāi)發(fā)團(tuán)隊(duì)與中國(guó)礦工\h4.13側(cè)鏈——閃電網(wǎng)絡(luò)\h4.14支付通道\h4.14.1微支付通道\h4.14.2RSMC\h4.14.3HTLC\h4.14.4閃電網(wǎng)絡(luò)\h第5章區(qū)塊鏈應(yīng)用場(chǎng)景及政府監(jiān)管\h5.1跨境支付\h5.1.1SWIFT\h5.1.2Ripple\h5.1.3J.P.摩根——JPMCoin\h5.1.4螞蟻金服\h5.2數(shù)據(jù)存證\h5.2.1保全網(wǎng)\h5.2.2Factom\h5.2.3仲裁鏈\h5.3防偽溯源\h5.4區(qū)塊鏈電子發(fā)票\h5.5政府監(jiān)管\h第6章Quorum架構(gòu)\h6.1架構(gòu)概述\h6.1.1應(yīng)用層\h6.1.2工具層\h6.1.3隱私、性能和許可層\h6.1.4核心區(qū)塊鏈層\h6.1.5網(wǎng)絡(luò)層\h6.2節(jié)點(diǎn)結(jié)構(gòu)及啟動(dòng)過(guò)程\h6.2.1以太坊賬戶\h6.2.2網(wǎng)絡(luò)通信協(xié)議\h6.2.3以太坊服務(wù)\h6.2.4RPC服務(wù)\h6.2.5節(jié)點(diǎn)啟動(dòng)過(guò)程\h6.3賬戶管理\h6.3.1keystore文件\h6.3.2賬戶管理器\h6.3.3簽名交易\h6.4網(wǎng)絡(luò)\h6.4.1協(xié)議管理器\h6.4.2p2p.Server對(duì)象和啟動(dòng)\h6.4.3對(duì)等節(jié)點(diǎn)發(fā)現(xiàn)\h6.4.4對(duì)等節(jié)點(diǎn)連接\h6.5交易管理\h6.5.1交易池\h6.5.2交易提交\h6.5.3交易廣播\h6.6區(qū)塊和鏈管理\h6.6.1MPT樹(shù)\h6.6.2區(qū)塊和鏈結(jié)構(gòu)\h6.6.3區(qū)塊上鏈\h6.6.4世界狀態(tài)轉(zhuǎn)換\h6.6.5StateDB\h6.6.6企業(yè)以太坊數(shù)據(jù)存儲(chǔ)\h6.7IBFT共識(shí)\h6.7.1IBFT共識(shí)概述\h6.7.2IBFT實(shí)現(xiàn)\h6.7.3礦工\h6.7.4共識(shí)流程\h6.8Raft共識(shí)\h6.8.1RaftService服務(wù)\h6.8.2Raft協(xié)議管理器\h6.8.3區(qū)塊上鏈\h6.8.4鏈競(jìng)爭(zhēng)\h6.9權(quán)限\h6.9.1權(quán)限管理智能合約\h6.9.2權(quán)限管理服務(wù)\h6.10數(shù)據(jù)隱私\h6.10.1私有交易流程\h6.10.2私有交易和私有合約\h第7章EVM\h7.1EVM的設(shè)計(jì)目標(biāo)\h7.2EVM的實(shí)現(xiàn)機(jī)制\h7.2.1虛擬機(jī)結(jié)構(gòu)\h7.2.2合約的創(chuàng)建和調(diào)用\h7.2.3虛擬機(jī)執(zhí)行器\h7.3指令集和字節(jié)碼\h7.4智能合約事件\h7.4.1事件的實(shí)現(xiàn)\h7.4.2事件的查詢\h7.5狀態(tài)變量存儲(chǔ)\h7.5.1基本類型存儲(chǔ)\h7.5.2映射存儲(chǔ)\h7.5.3數(shù)組存儲(chǔ)\h7.6智能合約ABI\h7.6.1函數(shù)選擇器\h7.6.2參數(shù)類型\h7.6.3固定類型編碼\h7.6.4動(dòng)態(tài)類型編碼\h第8章IPFS存儲(chǔ)系統(tǒng)\h8.1IPFS概述\h8.1.1塊\h8.1.2MerkleDAG\h8.1.3文件抽象層\h8.2IPFS節(jié)點(diǎn)架構(gòu)\h8.3IPFS子協(xié)議\h8.3.1身份\h8.3.2網(wǎng)絡(luò)\h8.3.3路由\h8.3.4交換\h8.3.5對(duì)象\h8.3.6文件\h8.3.7命名\h8.4IPFS集群\h8.4.1IPFSCluster節(jié)點(diǎn)架構(gòu)\h8.4.2數(shù)據(jù)上傳和數(shù)據(jù)安全\h第9章開(kāi)發(fā)環(huán)境搭建\h9.1Quorum平臺(tái)搭建\h9.1.1搭建流程\h9.1.2Quorum的Tessera平臺(tái)搭建\h9.1.3Quorum的Docker平臺(tái)搭建\h9.1.4Truffle與智能合約\h9.2IPFS平臺(tái)搭建\h9.2.1IPFS和IPFSCluster的安裝\h9.2.2IPFS私有網(wǎng)絡(luò)的搭建\h9.2.3IPFS私有網(wǎng)絡(luò)的交互\h9.2.4IPFSDocker平臺(tái)的搭建\h第10章一款電子票據(jù)的實(shí)現(xiàn)\h10.1需求\h10.2實(shí)現(xiàn)方案\h10.2.1IPFS方案\h10.2.2Quorum方案\h10.2.3整體方案\h10.3代碼實(shí)現(xiàn)\h10.3.1IPFS客戶端\h10.3.2智能合約注：原文檔電子版（非掃描），需要的請(qǐng)下載本文檔后留言謝謝。第1章

區(qū)塊鏈的前世今生近幾年來(lái)“區(qū)塊鏈”似乎橫空出世，引起廣泛的關(guān)注。區(qū)塊鏈從何而來(lái)？它到底是一種什么樣的技術(shù)？它是否意味著新一波的技術(shù)浪潮？它將如何改變這個(gè)世界？懷著這些問(wèn)題，我們一同來(lái)探究區(qū)塊鏈技術(shù)的前世今生。1.1初識(shí)區(qū)塊鏈2010年5月的一天，美國(guó)一個(gè)名叫Laszlo的年輕程序員，用10000枚比特幣購(gòu)買(mǎi)了兩個(gè)比薩餅的優(yōu)惠券。按照2017年12月17日比特幣的最高價(jià)格約20000美元一枚估算，當(dāng)時(shí)每個(gè)比薩餅大約花費(fèi)了1億美元，這應(yīng)該是有史以來(lái)最昂貴的比薩了。從2010年到2017年的短短8年中，比特幣的價(jià)格從幾美分上漲到超過(guò)20000美元，最高漲幅達(dá)到了數(shù)萬(wàn)倍。根據(jù)CoinMarketCap網(wǎng)站的數(shù)據(jù)顯示，2018年1月7日，數(shù)字貨幣整體市值曾達(dá)到8357億美元的峰值。這個(gè)數(shù)據(jù)非常驚人，因?yàn)楦鶕?jù)國(guó)際貨幣基金組織（IMF）的數(shù)據(jù)顯示，2017年全球也只有十多個(gè)國(guó)家的GDP超過(guò)8000億美元。虛擬貨幣價(jià)格的大幅波動(dòng)，引起了全世界范圍內(nèi)的關(guān)注。圖1-1展示了比特幣的漲幅曲線。圖1-1比特幣價(jià)格曾經(jīng)快速上漲隱藏在虛擬貨幣背后的是一種叫作“區(qū)塊鏈”的神秘技術(shù)。它究竟是何物？又從何而來(lái)？區(qū)塊鏈從何而來(lái)？“區(qū)塊鏈”源自英文BlockChain。普遍的觀點(diǎn)是，區(qū)塊鏈技術(shù)發(fā)源的標(biāo)志性事件是2008年中本聰（SatoshiNakamoto）提出了比特幣系統(tǒng)設(shè)計(jì)。在中本聰最初發(fā)布的《比特幣白皮書(shū)》中，Block和Chain這兩個(gè)詞是單獨(dú)出現(xiàn)的，而在后來(lái)的討論中，人們逐漸將這兩個(gè)詞連接起來(lái)，以BlockChain來(lái)稱呼這種技術(shù)。BlockChain（區(qū)塊鏈）這種提法后來(lái)流傳開(kāi)來(lái)。中本聰所提出的比特幣系統(tǒng)是一個(gè)電子貨幣系統(tǒng)，在不需要第三方信用背書(shū)的情況下，可以實(shí)現(xiàn)完全點(diǎn)對(duì)點(diǎn)的電子貨幣轉(zhuǎn)賬。雖然許多人主要是將比特幣作為一種虛擬的“幣”，但從技術(shù)的角度來(lái)看，比特幣系統(tǒng)中最重要的其實(shí)是分布式賬本。在中本聰?shù)脑O(shè)計(jì)理念中，遍布全球的分布式節(jié)點(diǎn)共同維護(hù)這個(gè)不斷延伸的鏈?zhǔn)劫~本，而所有關(guān)于“幣”的權(quán)屬的數(shù)據(jù)都完整地留存在分布式賬本中，不會(huì)被篡改或刪除。到目前為止，比特幣系統(tǒng)仍然是區(qū)塊鏈技術(shù)最具代表性的應(yīng)用案例。但時(shí)至今日，區(qū)塊鏈技術(shù)的范疇早已遠(yuǎn)遠(yuǎn)超過(guò)虛擬貨幣賬本本身，而逐步發(fā)展成為能應(yīng)用于多個(gè)行業(yè)和領(lǐng)域的綜合化信息技術(shù)。什么是區(qū)塊鏈？從信息的組織形式來(lái)看，區(qū)塊鏈?zhǔn)且粋€(gè)不斷增長(zhǎng)的數(shù)據(jù)鏈表，該數(shù)據(jù)鏈表的基本組成單位是一系列的“賬本”（通常也稱為“區(qū)塊”），這些賬本是通過(guò)密碼學(xué)技術(shù)連接起來(lái)的。從網(wǎng)絡(luò)結(jié)構(gòu)來(lái)看，區(qū)塊鏈上所有的數(shù)據(jù)由一系列分布式、相互獨(dú)立的“節(jié)點(diǎn)”共同維護(hù)。以上這些數(shù)據(jù)和網(wǎng)絡(luò)結(jié)構(gòu)方面的特殊規(guī)則保障了區(qū)塊鏈上的數(shù)據(jù)無(wú)法被隨意篡改，也不會(huì)失序、丟失。區(qū)塊鏈?zhǔn)侨舾蓪W(xué)科的交叉綜合，它涵蓋了分布式計(jì)算機(jī)系統(tǒng)、密碼學(xué)，乃至商業(yè)和經(jīng)濟(jì)等課題。在區(qū)塊鏈系統(tǒng)的設(shè)計(jì)中包含網(wǎng)絡(luò)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)、密碼學(xué)算法和分布式系統(tǒng)的一致性算法（即區(qū)塊鏈共識(shí)機(jī)制）等技術(shù)問(wèn)題。在本章后續(xù)部分中，我們將繼續(xù)了解區(qū)塊鏈技術(shù)的演進(jìn)歷程，以及區(qū)塊鏈技術(shù)的意義。在后續(xù)章節(jié)中，我們將以理論結(jié)合實(shí)操的方式深入學(xué)習(xí)區(qū)塊鏈的技術(shù)原理和開(kāi)發(fā)實(shí)踐。1.2區(qū)塊鏈技術(shù)的演進(jìn)首先，區(qū)塊鏈技術(shù)在發(fā)展過(guò)程中衍生出了多種類別。最常見(jiàn)的是根據(jù)節(jié)點(diǎn)間的組織形式和決策機(jī)制將區(qū)塊鏈系統(tǒng)分為公有鏈、私有鏈和聯(lián)盟鏈三類，具體如表1-1所示。表1-1區(qū)塊鏈系統(tǒng)的分類公有鏈也簡(jiǎn)稱為“公鏈”，它對(duì)分布式節(jié)點(diǎn)沒(méi)有特定要求，完全以算法、數(shù)據(jù)結(jié)構(gòu)和節(jié)點(diǎn)共識(shí)機(jī)制來(lái)組織。在這類系統(tǒng)中，節(jié)點(diǎn)之間是沒(méi)有任何信任約束的。私有鏈一般適用于企業(yè)或組織內(nèi)部，由內(nèi)部管理者進(jìn)行授權(quán)和管理。這類系統(tǒng)中，由于節(jié)點(diǎn)是由系統(tǒng)的發(fā)起者充分控制的，所以節(jié)點(diǎn)間是強(qiáng)信任的。聯(lián)盟鏈中，一般由若干相互獨(dú)立的主體共同形成聯(lián)盟，并由這些主體各自運(yùn)行一個(gè)或多個(gè)節(jié)點(diǎn)，只有被信任的聯(lián)盟成員才能加入節(jié)點(diǎn)網(wǎng)絡(luò)。這種系統(tǒng)中的節(jié)點(diǎn)面對(duì)著一定的網(wǎng)絡(luò)準(zhǔn)入和監(jiān)督機(jī)制。在實(shí)踐中，聯(lián)盟鏈常由行業(yè)內(nèi)的企業(yè)及監(jiān)管機(jī)構(gòu)共同發(fā)起和維護(hù)。區(qū)塊鏈技術(shù)的演進(jìn)過(guò)程大致可劃分為三個(gè)階段，如圖1-2所示。圖1-2區(qū)塊鏈技術(shù)的演進(jìn)過(guò)程第一階段以中本聰在2008年提出的比特幣區(qū)塊鏈為代表。比特幣區(qū)塊鏈的實(shí)質(zhì)是利用區(qū)塊鏈技術(shù)實(shí)現(xiàn)一種分布式的記賬機(jī)制，并以此為基礎(chǔ)實(shí)現(xiàn)比特幣虛擬貨幣的交易，其核心技術(shù)點(diǎn)包含UTXO交易模型、鏈?zhǔn)劫~本數(shù)據(jù)結(jié)構(gòu)、加密技術(shù)，以及基于“工作量證明”的共識(shí)機(jī)制等。在本書(shū)后續(xù)章節(jié)中將對(duì)這種區(qū)塊鏈技術(shù)進(jìn)行詳細(xì)講解。比特幣區(qū)塊鏈?zhǔn)枪墟湥扇虻姆植际焦?jié)點(diǎn)共同維護(hù)。同時(shí)代的區(qū)塊鏈應(yīng)用還有Namecoin、ColoredCoins，以及Metacoins等。比特幣區(qū)塊鏈有一些局限性。例如，UTXO模型缺少對(duì)狀態(tài)的支持，只適合簡(jiǎn)單、一次性的交易合約。這些限制使得它很難應(yīng)對(duì)金融領(lǐng)域中各種較復(fù)雜的場(chǎng)景。還有一些專家認(rèn)為比特幣區(qū)塊鏈中的“工作量證明”共識(shí)機(jī)制過(guò)于消耗計(jì)算量，平均10分鐘出一個(gè)區(qū)塊，效率很低。區(qū)塊鏈技術(shù)第二階段的主要特點(diǎn)是引入了“智能合約”理念，成為可編程的區(qū)塊鏈系統(tǒng)，進(jìn)而支持簡(jiǎn)單的金融合約業(yè)務(wù)場(chǎng)景。和第一階段的區(qū)塊鏈技術(shù)相比，這個(gè)階段的區(qū)塊鏈技術(shù)通過(guò)圖靈完備的編程語(yǔ)言，讓開(kāi)發(fā)者們能夠創(chuàng)建合約，實(shí)現(xiàn)去中心化應(yīng)用，以太坊和Fabric是這個(gè)階段的主要代表。其中，以太坊是繼比特幣之后一個(gè)很具影響力的公有鏈協(xié)議，它采用了合約賬戶的概念，能夠通過(guò)執(zhí)行智能合約實(shí)現(xiàn)兩個(gè)賬戶之間價(jià)值和狀態(tài)的轉(zhuǎn)換。Fabric是由IBM主導(dǎo)開(kāi)發(fā)的一個(gè)聯(lián)盟鏈，支持用容器技術(shù)運(yùn)行智能合約代碼，對(duì)高級(jí)語(yǔ)言開(kāi)發(fā)有良好的開(kāi)放性。該階段的區(qū)塊鏈技術(shù)在共識(shí)算法方面也有很多創(chuàng)新。第三個(gè)階段是區(qū)塊鏈在應(yīng)用領(lǐng)域、效率，以及安全性方面的擴(kuò)展，即目前的發(fā)展階段?？赡艿募夹g(shù)發(fā)展方向包含：利用分片、跨鏈等技術(shù)提升區(qū)塊鏈的記錄效率，接近高并發(fā)場(chǎng)景下的需求；利用新型的密碼技術(shù)提升區(qū)塊鏈系統(tǒng)的安全性，例如密鑰管理技術(shù)、抗量子攻擊密碼等；提升智能合約的開(kāi)放性，增加適用的行業(yè)場(chǎng)景等。據(jù)筆者觀察，這個(gè)階段目前尚處于探索階段，還未有標(biāo)志性的、被大規(guī)模運(yùn)用的系統(tǒng)出現(xiàn)。1.3區(qū)塊鏈能否“改變世界”加拿大學(xué)者、數(shù)字經(jīng)濟(jì)領(lǐng)域的知名專家DonTapscott曾將區(qū)塊鏈稱為一場(chǎng)“革命”，并認(rèn)為區(qū)塊鏈的底層技術(shù)可以改變貨幣、商業(yè)和世界。事實(shí)真是如此嗎？區(qū)塊鏈真能像工業(yè)化、互聯(lián)網(wǎng)化一樣改變世界，從而成為新一波技術(shù)浪潮嗎？如圖1-3所示，我們需要從多個(gè)維度來(lái)尋找這些問(wèn)題的答案。圖1-3從多個(gè)維度看區(qū)塊鏈的價(jià)值首先，談?wù)搮^(qū)塊鏈的影響時(shí)無(wú)法回避的是數(shù)字貨幣的話題。前文提到，整個(gè)虛擬貨幣市場(chǎng)的市值在2018年年初曾達(dá)到過(guò)峰值，隨后卻一路下跌。例如，比特幣的總市值較之前峰值回落了八成多。另外，由于比特幣等虛擬貨幣的價(jià)格波動(dòng)較大、結(jié)算便利性較差，在世界范圍內(nèi)一直未大規(guī)模地應(yīng)用于結(jié)算和支付等場(chǎng)景，我國(guó)的法定數(shù)字貨幣DCEP也尚在研究過(guò)程中。其次，從區(qū)塊鏈技術(shù)的商業(yè)模式看，較為受關(guān)注的有ICO、STO等。在這些模式中，區(qū)塊鏈技術(shù)主要被用于產(chǎn)生并記錄某種虛擬的權(quán)益憑證，有時(shí)也被稱為T(mén)oken。而投資人可以投資這些權(quán)益憑證，并通過(guò)區(qū)塊鏈系統(tǒng)進(jìn)行查詢、交易等。目前，上述模式并未得到有效推廣，主要原因在于各個(gè)國(guó)家和地區(qū)對(duì)它們的監(jiān)管和規(guī)范方法還未完備。例如，2017年美國(guó)的證券監(jiān)管部門(mén)曾發(fā)布公告，宣布要根據(jù)每個(gè)ICO項(xiàng)目的實(shí)際情況，考慮將其納入監(jiān)管范圍。在我國(guó)，2017年央行等多個(gè)部委也明確將ICO這種模式定義為非法融資行為。目前，基于區(qū)塊鏈技術(shù)的商業(yè)模式創(chuàng)新還尚未有重大突破，人們還需要結(jié)合各個(gè)國(guó)家和地區(qū)的法律法規(guī)，探索具有創(chuàng)新性的區(qū)塊鏈商業(yè)模式。最后，從行業(yè)應(yīng)用的角度來(lái)看，由于區(qū)塊鏈技術(shù)可實(shí)現(xiàn)數(shù)據(jù)隱私保密、防篡改和溯源等基礎(chǔ)功能，無(wú)疑會(huì)在金融、物流、制造和消費(fèi)等行業(yè)領(lǐng)域落地應(yīng)用。世界上許多國(guó)家和地區(qū)都在積極探索和支持區(qū)塊鏈技術(shù)的研究和行業(yè)落地。以我國(guó)為例，國(guó)務(wù)院、工信部等近年來(lái)頒布了一系列指導(dǎo)意見(jiàn)和發(fā)展建議，鼓勵(lì)區(qū)塊鏈技術(shù)的研究和發(fā)展。2016年10月，工信部發(fā)布《中國(guó)區(qū)塊鏈技術(shù)和應(yīng)用發(fā)展白皮書(shū)（2016）》，介紹了我國(guó)區(qū)塊鏈技術(shù)的發(fā)展及未來(lái)方向。同年，區(qū)塊鏈作為重要驅(qū)動(dòng)技術(shù)之一，被列入了國(guó)務(wù)院印發(fā)的《“十三五”國(guó)家信息化規(guī)劃》。2017年8月，國(guó)務(wù)院發(fā)布的《關(guān)于進(jìn)一步擴(kuò)大和升級(jí)信息消費(fèi)持續(xù)釋放內(nèi)需潛力的指導(dǎo)意見(jiàn)》提出開(kāi)展基于區(qū)塊鏈、人工智能等新技術(shù)的試點(diǎn)應(yīng)用。在銀行業(yè)，2015年成立的R3區(qū)塊鏈聯(lián)盟目前已經(jīng)擁有數(shù)十家來(lái)自全球的國(guó)際銀行組織，其致力于為銀行提供適用的探索區(qū)塊鏈的技術(shù)和產(chǎn)品。2016年，我國(guó)的一些金融企業(yè)、機(jī)構(gòu)在深圳聯(lián)合發(fā)起了“金融區(qū)塊鏈聯(lián)盟”，探索區(qū)塊鏈技術(shù)在金融領(lǐng)域的技術(shù)和應(yīng)用。在行業(yè)標(biāo)準(zhǔn)化方面，2018年年底，歐洲電信標(biāo)準(zhǔn)化協(xié)會(huì)（ETSI）宣布成立了一個(gè)新的行業(yè)規(guī)范小組（ISGPDL），專門(mén)研究獲準(zhǔn)使用的分布式賬簿。我國(guó)的通信標(biāo)準(zhǔn)化協(xié)會(huì)CCSA在2017年也成立了物聯(lián)網(wǎng)區(qū)塊鏈組。在此背景下，區(qū)塊鏈技術(shù)的落地應(yīng)用日益豐富。2018年8月，我國(guó)深圳開(kāi)出了第一張區(qū)塊鏈電子發(fā)票，同年，在我國(guó)杭州誕生了第一個(gè)運(yùn)用區(qū)塊鏈存證判決互聯(lián)網(wǎng)信息傳播侵權(quán)的案例?？傊?，斷言區(qū)塊鏈?zhǔn)欠駮?huì)帶來(lái)一個(gè)新的時(shí)代還為時(shí)過(guò)早，但毋庸置疑，區(qū)塊鏈已經(jīng)受到了極高的關(guān)注，社會(huì)各界的持續(xù)投入將促使其技術(shù)不斷完善、應(yīng)用不斷豐富，隨著時(shí)間的推移，它的影響將被更多人認(rèn)識(shí)和發(fā)現(xiàn)。第2章

區(qū)塊鏈中的共識(shí)機(jī)制區(qū)塊鏈這樣的去中心化網(wǎng)絡(luò)是如何做出一致性決策的？這看起來(lái)似乎是一個(gè)矛盾的命題，但它又是區(qū)塊鏈技術(shù)的重要組成部分。本章將抽絲剝繭、深入淺出地帶你看懂分布式系統(tǒng)的一致性挑戰(zhàn)，了解區(qū)塊鏈中的一致性算法（又稱為共識(shí)算法）。2.1分布式系統(tǒng)的一致性挑戰(zhàn)2.1.1若干基本原理全球比特幣區(qū)塊鏈系統(tǒng)中的節(jié)點(diǎn)數(shù)量約一萬(wàn)多個(gè)。在如此龐大的分布式網(wǎng)絡(luò)中，并沒(méi)有一個(gè)“權(quán)威”的中心節(jié)點(diǎn)進(jìn)行協(xié)調(diào)，如圖2-1所示。那么中本聰一定需要設(shè)計(jì)一套協(xié)議機(jī)制，讓整個(gè)比特幣系統(tǒng)較高效地持續(xù)達(dá)成一致，持續(xù)生成比特幣“賬本”。這樣一套以達(dá)成一致為目的協(xié)議機(jī)制就是區(qū)塊鏈系統(tǒng)的“共識(shí)機(jī)制”。推而廣之，該問(wèn)題的模型是分布式系統(tǒng)中各個(gè)“節(jié)點(diǎn)”的一致性決策。圖2-1分布式系統(tǒng)的一致性挑戰(zhàn)為了更多地了解該課題，我們先從若干基本原理開(kāi)始學(xué)習(xí)，然后通過(guò)具體算法加深理解。在無(wú)歧義的情況下，下文并不嚴(yán)格區(qū)分“進(jìn)程”“節(jié)點(diǎn)”或“單元”等概念，而將它們統(tǒng)稱為“節(jié)點(diǎn)”。形象地講，“節(jié)點(diǎn)”就是參與分布式系統(tǒng)一致性決策的基本單元。表2-1概括了FLP不可能原理、CAP理論，以及ACID和BASE原則。這些理論和原則是分布式系統(tǒng)設(shè)計(jì)和工程實(shí)踐的基礎(chǔ)，很多實(shí)際算法都是沿著它們的思路所進(jìn)行的探索。本節(jié)后續(xù)部分將對(duì)這些原理做簡(jiǎn)要梳理。表2-1分布式系統(tǒng)一致性的主要原理/原則1.FLP不可能原理FLP不可能原理的相關(guān)研究獲得了2017年的Dijkstra獎(jiǎng)。該原理由Fisher、Lynch和Paterson三位科學(xué)家在1985年提出。FLP不可能原理指出，在一個(gè)異步分布式系統(tǒng)中，只要有一個(gè)節(jié)點(diǎn)出錯(cuò)（比如長(zhǎng)時(shí)間不響應(yīng)、出錯(cuò)、中斷服務(wù)等），就不可能設(shè)計(jì)出一個(gè)完備的一致性決策方案。FLP并不是說(shuō)一致性決策永遠(yuǎn)都沒(méi)法達(dá)成，它的含義是，在特定的系統(tǒng)假設(shè)下，沒(méi)有算法是完美的或是充分可信任的。FLP的理論證明過(guò)程較為煩瑣，可以簡(jiǎn)單理解如下。如果一個(gè)分布式系統(tǒng)是異步的，那么系統(tǒng)中任一參與共識(shí)的節(jié)點(diǎn)都可能出錯(cuò)，且節(jié)點(diǎn)之間的通信鏈路也可能出錯(cuò)，這在概率意義上是無(wú)法避免的。而且，在信息傳遞的整個(gè)過(guò)程中，系統(tǒng)中各個(gè)節(jié)點(diǎn)都可能收到新的消息，并可能進(jìn)行狀態(tài)遷移。在這種情況下，任何時(shí)間點(diǎn)上希望達(dá)成一致且要求這種一致性在概率上完備都是不可能的。所以沒(méi)有算法能處理一切潛在的錯(cuò)誤，因此這個(gè)理論也被稱為FLP“不可能”原理。雖然FLP只是一個(gè)概率意義上的理論判定，但它為后續(xù)的理論和算法研究奠定了方向性的基礎(chǔ)。2.CAP理論繼FLP不可能原理之后，該領(lǐng)域的研究成果更加具體和細(xì)化。其中比較有影響力的是美國(guó)加州大學(xué)伯克利分校的計(jì)算機(jī)科學(xué)家EricBrewer提出的CAP理論。CAP理論簡(jiǎn)單明了地指出，在分布式系統(tǒng)中最多只能確保一致性、可用性和分區(qū)容錯(cuò)性這三個(gè)特性中的兩項(xiàng)。也就是說(shuō)，CAP理論告訴我們雖然理論完備的一致性決策方案不存在，但是可以在這些維度中做折中選擇，設(shè)計(jì)出“足夠好”的方案。那么一致性、可用性和分區(qū)容錯(cuò)性是哪些維度呢？一致性指信息的準(zhǔn)確性，即所有的節(jié)點(diǎn)都能夠獲取最新的信息?？捎眯允侵讣皶r(shí)性，即能保證所有的節(jié)點(diǎn)都及時(shí)得到響應(yīng)，但獲得的不一定是最新信息。分區(qū)容錯(cuò)性主要是指系統(tǒng)在部分節(jié)點(diǎn)錯(cuò)誤或丟失信息情況下的穩(wěn)健性，即出現(xiàn)這種情況時(shí)網(wǎng)絡(luò)可以正常運(yùn)行。我們接著分析一下，實(shí)際中該如何選擇。顯然，一般情況下我們無(wú)法完全規(guī)避通信鏈路或部分節(jié)點(diǎn)出錯(cuò)，因此分區(qū)容錯(cuò)性似乎是有必要的。換一個(gè)角度，如果在系統(tǒng)設(shè)計(jì)中，強(qiáng)制要求對(duì)所有“分區(qū)”的錯(cuò)誤零容忍，這種設(shè)計(jì)準(zhǔn)則過(guò)于苛刻，實(shí)現(xiàn)起來(lái)代價(jià)會(huì)很大。那么，在分區(qū)容錯(cuò)的前提下，一致性和可用性應(yīng)該如何取舍？從圖2-2中，我們可以做一些觀察。假設(shè)節(jié)點(diǎn)A和B分別位于分區(qū)P1和P2中。圖2-2中左、中和右側(cè)分別代表時(shí)刻1、時(shí)刻2和時(shí)刻3的不同狀態(tài)。在時(shí)刻1，節(jié)點(diǎn)A向數(shù)據(jù)庫(kù)發(fā)起數(shù)據(jù)更新D1，該更新在時(shí)刻2體現(xiàn)在了分區(qū)P1的數(shù)據(jù)庫(kù)。但是，由于兩個(gè)分區(qū)間的通信鏈路出現(xiàn)故障，時(shí)刻2分區(qū)P2并沒(méi)有及時(shí)更新數(shù)據(jù)，其數(shù)據(jù)還是D0。想象一下，在時(shí)刻2，外部訪問(wèn)者如果向分區(qū)P1和分區(qū)P2同時(shí)請(qǐng)求數(shù)據(jù)將會(huì)出現(xiàn)什么情況。如果要確保一致性，分區(qū)P2要等待網(wǎng)絡(luò)故障排除，再對(duì)最新數(shù)據(jù)庫(kù)進(jìn)行查詢，并刷新；而如果要確?？捎眯?，分區(qū)P1和P2可能需要在一定的響應(yīng)時(shí)間內(nèi)各自返回?cái)?shù)據(jù)，而這兩個(gè)數(shù)據(jù)是不同的。從數(shù)據(jù)接收者的角度來(lái)看，可能需要向更多的分區(qū)請(qǐng)求數(shù)據(jù)，自行判斷數(shù)據(jù)的有效性。總之，一致性和可用性是不可兼得的。圖2-2CAP原理示意圖3.ACID和BASE原則既然魚(yú)與熊掌不可兼得，那么該如何做選擇呢？ACID和BASE原則就是兩種比較有影響力的思路。ACID是四個(gè)英文單詞的縮寫(xiě)，即原子性（Atomicity）、一致性（Consistency）、孤立性（Isolation）和持續(xù)性（Durability）。原子性可以理解為每個(gè)操作都是最小細(xì)分，不論成功或失敗都狀態(tài)明確。孤立性指不同的操作間不耦合，不互相影響。持續(xù)性是指狀態(tài)的變化不會(huì)失效。ACID的核心要求是，系統(tǒng)中狀態(tài)變化的最小顆粒度是唯一并明確的，系統(tǒng)從一個(gè)狀態(tài)明確地切換到下一個(gè)狀態(tài)，沒(méi)有中間態(tài)。很顯然，ACID代表著強(qiáng)一致性的模型。以數(shù)據(jù)庫(kù)系統(tǒng)為例，典型的關(guān)系型數(shù)據(jù)庫(kù)Oracle、MYSQL等都體現(xiàn)了ACID原則的思路。BASE是BasicallyAvailable、Softstate、Eventualconsistency的簡(jiǎn)寫(xiě)。實(shí)際上，BASE是選擇確?？捎眯缘?。具體地說(shuō)，它包含基本可用、軟狀態(tài)，以及最終一致性三個(gè)維度。基本可用是指允許分布式網(wǎng)絡(luò)損失部分可用性，保證核心功能可用，例如網(wǎng)站出現(xiàn)高并發(fā)訪問(wèn)時(shí)，一部分用戶可能被引導(dǎo)到降級(jí)版本的頁(yè)面。軟狀態(tài)是指允許系統(tǒng)存在不影響整體可用性的中間狀態(tài)，例如分布式系統(tǒng)中數(shù)據(jù)可以有不同副本，允許不同的刷新延時(shí)。顧名思義，最終一致性是指，隨著時(shí)間的推移，最終在分布式網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都會(huì)得到最新數(shù)據(jù)。顯然，BASE原則是一種“弱保障”。以數(shù)據(jù)庫(kù)系統(tǒng)為例，NoSQL類型數(shù)據(jù)庫(kù)主要確?？捎眯裕芨玫貞?yīng)用于大數(shù)據(jù)、并行計(jì)算等場(chǎng)景，體現(xiàn)了BASE的思路。2.1.2拜占庭將軍問(wèn)題在一個(gè)網(wǎng)絡(luò)中還可能存在“惡意”節(jié)點(diǎn)。例如，一些節(jié)點(diǎn)通過(guò)發(fā)送錯(cuò)誤的記賬信息，試圖修改賬本、篡改交易數(shù)據(jù)等。這一類問(wèn)題可能對(duì)分布式系統(tǒng)的穩(wěn)定和安全帶來(lái)很大挑戰(zhàn)。針對(duì)這類挑戰(zhàn)，人們提出了經(jīng)典的“拜占庭將軍”問(wèn)題。關(guān)于“拜占庭將軍”問(wèn)題的討論始于1982年，學(xué)者們基于古代戰(zhàn)場(chǎng)場(chǎng)景描述出一個(gè)決策問(wèn)題。拜占庭是東羅馬帝國(guó)的首都。由于國(guó)土遼闊，許多拜占庭將軍的軍隊(duì)在地理上相隔很遠(yuǎn)，這些將軍只能通過(guò)信使相互傳遞消息。當(dāng)戰(zhàn)爭(zhēng)發(fā)生時(shí)，這些將軍需要達(dá)成共識(shí)，所有的將軍都意見(jiàn)一致才向敵軍發(fā)起攻擊。由于可能會(huì)有將軍反叛，部分錯(cuò)誤信息可能導(dǎo)致整個(gè)決策出現(xiàn)偏差，影響戰(zhàn)局。例如，在9位將軍中，有4個(gè)同意進(jìn)攻并發(fā)出信息，另外4個(gè)同意撤退并發(fā)出信息，剩余的一個(gè)將軍如果向這兩方發(fā)出不同的信息，可能誤導(dǎo)他們分別做出“進(jìn)攻”和“撤退”的共識(shí)。顯然，這是假的共識(shí)，在戰(zhàn)場(chǎng)上會(huì)導(dǎo)致嚴(yán)重的失敗。這種情形被稱為“拜占庭失敗”。拜占庭將軍問(wèn)題是對(duì)存在潛在錯(cuò)誤或惡意節(jié)點(diǎn)的情況下的分布式系統(tǒng)一致性決策的一種模型化描述。根據(jù)理論分析，假設(shè)一個(gè)包含n個(gè)節(jié)點(diǎn)的分布式系統(tǒng)，其錯(cuò)誤或惡意節(jié)點(diǎn)數(shù)量為f，當(dāng)n≥3f+1時(shí)，可以設(shè)計(jì)出共識(shí)算法來(lái)保障所有節(jié)點(diǎn)達(dá)成正確共識(shí)。拜占庭將軍問(wèn)題及其理論邊界被提出后，學(xué)者們開(kāi)始研究“拜占庭容錯(cuò)”的共識(shí)算法。2.2常見(jiàn)共識(shí)算法在前述諸多原理的指引下，人們對(duì)分布式系統(tǒng)中的一致性算法（即共識(shí)算法）進(jìn)行了很多探索。比較常見(jiàn)的算法有PBFT、Paxos、Raft、PoW、PoS和DPoS等。這些算法的應(yīng)用場(chǎng)景有所區(qū)別。PBFT、Paxos和Raft等算法側(cè)重于強(qiáng)一致性，它們?cè)诎?jié)點(diǎn)準(zhǔn)入和控制的私有鏈或聯(lián)盟鏈系統(tǒng)中比較常用。PoW、PoS和DPoS等算法側(cè)重于可用性，在公有鏈系統(tǒng)中比較常用。下面對(duì)以上算法進(jìn)行逐一介紹。2.2.1PBFT算法1999年MiguelCastro等學(xué)者提出了PBFT（PracticalByzantineFaultTolerance）算法，該算法的主要過(guò)程如圖2-3所示。圖2-3PBFT過(guò)程算法中將節(jié)點(diǎn)劃分為兩類：主節(jié)點(diǎn)和其他節(jié)點(diǎn)。每一次請(qǐng)求要經(jīng)歷五個(gè)步驟：發(fā)起（Request）、預(yù)準(zhǔn)備（Pre-prepare）、準(zhǔn)備（Prepare）、確認(rèn)（Commit）和響應(yīng)（Reply）。對(duì)這些步驟簡(jiǎn)述如下。首先，從全網(wǎng)節(jié)點(diǎn)選舉出一個(gè)主節(jié)點(diǎn)（Leader），新區(qū)塊由主節(jié)點(diǎn)負(fù)責(zé)生成。主節(jié)點(diǎn)的選擇方法是類輪詢的方式。假設(shè)Node0是主節(jié)點(diǎn)，當(dāng)客戶端向它發(fā)起請(qǐng)求后，就從發(fā)起階段進(jìn)入了預(yù)準(zhǔn)備階段。在預(yù)準(zhǔn)備階段，主節(jié)點(diǎn)把該請(qǐng)求廣播到所有節(jié)點(diǎn)。為了確保請(qǐng)求的時(shí)間順序不錯(cuò)亂，主節(jié)點(diǎn)會(huì)給當(dāng)前的請(qǐng)求分配一個(gè)編號(hào)p。所有節(jié)點(diǎn)收到這個(gè)請(qǐng)求信息后，都會(huì)各自對(duì)該消息進(jìn)行校驗(yàn)，當(dāng)確認(rèn)時(shí)序正確、校驗(yàn)信息無(wú)誤后，該節(jié)點(diǎn)會(huì)進(jìn)入下一階段。在準(zhǔn)備階段，每個(gè)節(jié)點(diǎn)將收到的請(qǐng)求信息存入消息隊(duì)列，在請(qǐng)求信息中嵌入其自身編號(hào)i，并繼續(xù)向所有其他節(jié)點(diǎn)廣播處理后的請(qǐng)求信息（即Prepare消息），完成后進(jìn)入下一階段。在確認(rèn)階段，如果某個(gè)節(jié)點(diǎn)收到了來(lái)自其他2f個(gè)節(jié)點(diǎn)（f代表PBFT最大容錯(cuò)節(jié)點(diǎn)數(shù)量，算法中假設(shè)f不大于總節(jié)點(diǎn)數(shù)的1/3）的Prepare消息，并確認(rèn)這些消息和自己之前收到的一致，就可以執(zhí)行Commit操作，即向所有其他節(jié)點(diǎn)發(fā)送一條Commit確認(rèn)消息，這條消息中包含消息編號(hào)n和節(jié)點(diǎn)編號(hào)i。最后是響應(yīng)階段。在該階段中，如果一個(gè)節(jié)點(diǎn)收到來(lái)自2f+1個(gè)不同節(jié)點(diǎn)的Commit消息，則確認(rèn)成功，并向最初發(fā)起請(qǐng)求的客戶端發(fā)送響應(yīng)信息。請(qǐng)求的發(fā)起者會(huì)等待，直到收到f+1個(gè)響應(yīng)，才接受這個(gè)結(jié)論。至此，整個(gè)算法流程結(jié)束。簡(jiǎn)而言之，PBFT算法通過(guò)兩種手段實(shí)現(xiàn)拜占庭容錯(cuò)：以類似輪詢的方式選擇主節(jié)點(diǎn)；每一次請(qǐng)求都要在主節(jié)點(diǎn)和其他節(jié)點(diǎn)之間互相驗(yàn)證，只有足夠多的節(jié)點(diǎn)確認(rèn)后才達(dá)成共識(shí)。PBFT比經(jīng)典拜占庭協(xié)議的復(fù)雜度低，應(yīng)用性更強(qiáng)。2.2.2Raft算法在了解Raft算法前，先簡(jiǎn)述Paxos算法。Paxos算法最早于1989年提出，在20世紀(jì)八九十年代被廣泛討論。該算法強(qiáng)調(diào)一致性，將節(jié)點(diǎn)分為Client、Voters、Proposer、Learner和Leader等多種角色，對(duì)應(yīng)于不同的職責(zé)權(quán)限。從步驟上來(lái)說(shuō)，算法包含Prepare、Promise、Accept和Accepted等多個(gè)步驟。通過(guò)這些角色和步驟的定義，在節(jié)點(diǎn)中反復(fù)確認(rèn)并達(dá)成一致性決策。經(jīng)過(guò)理論證明，Paxos是可以滿足一致性和分區(qū)容錯(cuò)的。谷歌公司曾在分布式數(shù)據(jù)庫(kù)Chubby系統(tǒng)中應(yīng)用Paxos算法，微軟公司在搜索引擎Bing的并行計(jì)算系統(tǒng)中也嘗試運(yùn)用了Paxos算法。Paxos被詬病的原因是其邏輯過(guò)于復(fù)雜，難于理解，因此在教學(xué)和工程實(shí)踐中，人們運(yùn)用Paxos算法的困難較大。Raft（Reliable、Replicated、Redundant和Fault-Tolerant）是Paxos的一種簡(jiǎn)化變種，同樣追求的是分布式系統(tǒng)中的強(qiáng)一致性。假設(shè)節(jié)點(diǎn)的總數(shù)為n，Raft的最大容錯(cuò)節(jié)點(diǎn)數(shù)量為(n-1)/2。Raft算法主要分為兩個(gè)基本步驟：Leader的選舉以及Log同步。算法將節(jié)點(diǎn)分為兩類：Leader和Follower。Raft算法中將時(shí)間劃分為若干個(gè)分塊（term），在每一個(gè)term中Leader不變，分塊結(jié)束后，發(fā)起新的Leader選舉。該算法也定義了一些機(jī)制以允許Follower在一些情況下發(fā)起Leader選舉，例如長(zhǎng)時(shí)間未收到任何請(qǐng)求時(shí)。在每個(gè)term中，所有節(jié)點(diǎn)在唯一Leader的管理下執(zhí)行Log同步的過(guò)程。當(dāng)Leader收到來(lái)自客戶端的新請(qǐng)求時(shí)，便將該新請(qǐng)求指令增補(bǔ)到日志中，并向所有節(jié)點(diǎn)發(fā)送日志刷新消息。日志中的指令按時(shí)間順序排列編號(hào)，Log序列中每一個(gè)輸入都包含其所對(duì)應(yīng)的term編號(hào)以及指令本身。Follower收到日志刷新消息后，會(huì)向Leader發(fā)回響應(yīng)信息?；谶@些響應(yīng)信息，Leader可以判定某個(gè)新的指令是否獲得了超過(guò)半數(shù)的節(jié)點(diǎn)響應(yīng)，如果是，則這條指令被認(rèn)為成功地同步了。Leader會(huì)執(zhí)行成功同步過(guò)的指令，并將執(zhí)行結(jié)果返回到最初發(fā)起請(qǐng)求的客戶端。由于Leader會(huì)持續(xù)刷新最新的Log同步信息，其中包含最新成功同步的指令序號(hào)，各個(gè)Follower可以將其和自己所存的Log序列進(jìn)行比對(duì)，以判斷自己是否曾錯(cuò)過(guò)了之前的消息指令，從而確保系統(tǒng)中的一致性。2.2.3PoW算法PoW（Proof-of-Work）算法最早于20世紀(jì)90年代被提出，它的基本思路是，用“工作量證明”的方式來(lái)避免類似于DoS的攻擊。其基本原理是用高“工作量”提高作惡的成本，從而達(dá)到規(guī)避惡意節(jié)點(diǎn)破壞的目的。PoW算法的一般過(guò)程如圖2-4所示。首先客戶端要進(jìn)行復(fù)雜運(yùn)算完成“解題”，然后把計(jì)算結(jié)果連同指令請(qǐng)求一起發(fā)送給服務(wù)器，在服務(wù)器端對(duì)計(jì)算結(jié)果進(jìn)行驗(yàn)證，如果驗(yàn)證通過(guò)，則服務(wù)器接受指令請(qǐng)求，否則拒絕。為了便于實(shí)現(xiàn)，這類算法都有一個(gè)顯著特點(diǎn)：“工作量證明”的計(jì)算過(guò)程很復(fù)雜，但是校驗(yàn)過(guò)程非常簡(jiǎn)單快速。例如，我們假設(shè)要求是“對(duì)信息序列增補(bǔ)隨機(jī)數(shù)后再進(jìn)行哈希函數(shù)運(yùn)算，其輸出結(jié)果以特定字符串開(kāi)頭”。該題目的結(jié)果是很容易檢驗(yàn)的，只需要用序列計(jì)算哈希，驗(yàn)證是否以特定字符串開(kāi)頭即可。但是從函數(shù)的輸入端來(lái)說(shuō)，需要大量地嘗試可能的隨機(jī)數(shù)序列，才能得到滿足題目要求的結(jié)果，這意味著很大的工作量。圖2-4PoW算法過(guò)程示意圖PoW共識(shí)機(jī)制的一個(gè)例子是HashCash系統(tǒng)，該系統(tǒng)可以用來(lái)防止互聯(lián)網(wǎng)上的惡意DoS和垃圾信息攻擊。簡(jiǎn)言之，HashCash要求在電子郵件的消息頭中增加一個(gè)哈希戳（HashCashstamp）。PoW算法的另一個(gè)典型應(yīng)用是比特幣區(qū)塊鏈系統(tǒng)。在比特幣區(qū)塊鏈系統(tǒng)中，得出“工作量證明”的過(guò)程通常被稱為“挖礦”，后續(xù)章節(jié)將會(huì)詳細(xì)介紹這一過(guò)程。2.2.4PoS算法PoS（Proof-of-Stake）的特點(diǎn)是將所持有“權(quán)益”作為選擇下一個(gè)區(qū)塊記賬節(jié)點(diǎn)的標(biāo)準(zhǔn)。在加密數(shù)字貨幣系統(tǒng)中，權(quán)益一般對(duì)應(yīng)的就是數(shù)字貨幣本身。PoS機(jī)制最早在2012年運(yùn)用于Peercoin系統(tǒng)，后來(lái)該機(jī)制的各種演化版本也應(yīng)用于BlackCoin、Nxt和以太坊等區(qū)塊鏈系統(tǒng)中。形象地說(shuō)，哪個(gè)節(jié)點(diǎn)擁有的數(shù)字貨幣更多或持有時(shí)間更長(zhǎng)，就提高它的優(yōu)先級(jí)，讓它能更容易地成為記賬節(jié)點(diǎn)。在不同的系統(tǒng)中，PoS的具體形式可能不一樣。例如，前面提到的Peercoin系統(tǒng)基本是在比特幣區(qū)塊鏈的PoW基礎(chǔ)上做了改變，在每個(gè)節(jié)點(diǎn)求解復(fù)雜數(shù)據(jù)運(yùn)算時(shí)引入不同的權(quán)值（有關(guān)比特幣區(qū)塊鏈的具體原理，可參見(jiàn)后續(xù)章節(jié)），使得特定節(jié)點(diǎn)的計(jì)算復(fù)雜度與它持有的虛擬貨幣數(shù)量和時(shí)間成反比。以太坊中的Casper共識(shí)機(jī)制也基于PoS原理。和前文中的PoW相比，PoS計(jì)算量較小。但也有觀點(diǎn)認(rèn)為，PoS算法中節(jié)點(diǎn)的作惡成本過(guò)低，不能夠像PoW那樣完全基于計(jì)算復(fù)雜度這種更絕對(duì)的指標(biāo)來(lái)執(zhí)行共識(shí)決策。在以太坊區(qū)塊鏈系統(tǒng)中采用的PoS引入了“保證金”的概念。首先，所有驗(yàn)證者節(jié)點(diǎn)要鎖定其擁有的一部分以太坊虛擬貨幣作為保證金，付出保證金后才有資格做新區(qū)塊驗(yàn)證和投票。然后，驗(yàn)證者節(jié)點(diǎn)都可以驗(yàn)證節(jié)點(diǎn)，當(dāng)發(fā)現(xiàn)新區(qū)塊并驗(yàn)證其合法后，可以投票。如果所投票的區(qū)塊被選中添加到區(qū)塊鏈，驗(yàn)證者可以獲得和投票成比例的獎(jiǎng)勵(lì)。該機(jī)制也規(guī)定，如果驗(yàn)證者向錯(cuò)誤的分支投票，保證金將會(huì)被罰沒(méi)。在PoS的基礎(chǔ)上，又進(jìn)一步演化出了DPoS算法。其基本思路是，從所有網(wǎng)絡(luò)節(jié)點(diǎn)中預(yù)先選擇固定數(shù)量的節(jié)點(diǎn)來(lái)構(gòu)成區(qū)塊鏈驗(yàn)證者節(jié)點(diǎn)子集，僅在這個(gè)子集中選擇驗(yàn)證節(jié)點(diǎn)對(duì)新區(qū)塊進(jìn)行驗(yàn)證。本質(zhì)上，DPoS進(jìn)一步向CAP原理描述的“可用性”進(jìn)行了傾斜。DPoS還有助于緩解PoW和PoS中固有的“算力”或“財(cái)力”過(guò)于集中而導(dǎo)致權(quán)力集中的問(wèn)題。第3章

密碼學(xué)探秘眾所周知，密碼學(xué)原理是區(qū)塊鏈技術(shù)的核心支柱，但很多讀者在面對(duì)密碼算法時(shí)，總會(huì)感覺(jué)力不從心。究其原因，密碼學(xué)原理背后多是復(fù)雜的數(shù)學(xué)理論，而現(xiàn)有的文獻(xiàn)和資料大都用嚴(yán)密的數(shù)學(xué)語(yǔ)言去講述，自然會(huì)比較繁復(fù)，這給技術(shù)開(kāi)發(fā)者的學(xué)習(xí)帶來(lái)了很大的挑戰(zhàn)。在本章后續(xù)內(nèi)容中，筆者試圖以簡(jiǎn)明的語(yǔ)言介紹密碼學(xué)的基本原理，兼顧數(shù)學(xué)理論和工程意義，使技術(shù)開(kāi)發(fā)者對(duì)這些看似高深的算法做到“知其然也知其所以然”。下面讓我們共同踏上密碼學(xué)的探秘之旅吧！3.1密碼學(xué)基礎(chǔ)知識(shí)3.1.1加解密的一般過(guò)程在信息系統(tǒng)中，惡意竊聽(tīng)和攻擊的威脅從未間斷。加密的目的是讓明文轉(zhuǎn)化成密文，通過(guò)密文方式發(fā)送信息可以防止明文信息被獲取。為方便后續(xù)討論，我們先建立一套標(biāo)準(zhǔn)的語(yǔ)言體系。通常情況下，可將整個(gè)過(guò)程劃分為信息加密、信道和信息解密三個(gè)階段。如圖3-1所示，按照常見(jiàn)的提法，將信息的發(fā)送方和接收方分別稱為Alice和Bob，而將信道中潛在的惡意方稱為Carl。圖3-1加密和解密的一般過(guò)程Alice加密的過(guò)程是：s=e(m,k1)其中，e(x,y)是加密函數(shù)，k1是加密密鑰，m和s分別是明文和密文。Bob解密的過(guò)程是：m=d(s,k1)其中，d(x,y)是解密函數(shù)，k2是解密密鑰。我們用不同的符號(hào)表示加密和解密密鑰，是因?yàn)樵谠S多加密算法中，這兩個(gè)密鑰是不相同的。Carl總會(huì)嘗試破解上述過(guò)程。他的目的是獲取當(dāng)前乃至之后的所有原文，手段是找到加密算法和密鑰。Carl可能采用以下多種方式發(fā)起攻擊。唯密文攻擊：Carl只獲得了密文s。已知明文攻擊：Carl獲得了某一份密文s及其對(duì)應(yīng)的明文m。選擇明文攻擊：Carl有機(jī)會(huì)接觸加密設(shè)備，他可以獲得任意明文m對(duì)應(yīng)的密文s。選擇密文攻擊：Carl有機(jī)會(huì)接觸解密設(shè)備，他可以獲得任意密文s對(duì)應(yīng)的明文m。顯然，這些攻擊的強(qiáng)度是遞增的。一般考慮較多的是前兩種場(chǎng)景。Carl執(zhí)行上述攻擊的前提是他知道Alice和Bob采用的是哪種加密算法。這個(gè)假設(shè)是否合理呢？密碼學(xué)理論研究中有一個(gè)被廣泛認(rèn)同的Kerckhoffs原則。Kerckhoffs原則指出，在設(shè)計(jì)密碼算法時(shí)不能夠假設(shè)Carl不知道加密算法。換個(gè)角度講，由于系統(tǒng)設(shè)計(jì)者無(wú)法確保Carl對(duì)加密算法并不知情（有各種因素會(huì)導(dǎo)致消息泄露），因此從安全性的角度考慮必須假設(shè)“敵人知道系統(tǒng)”。美國(guó)科學(xué)家香農(nóng)在20世紀(jì)中葉也獨(dú)立地論證了這一理論。密碼分析是密碼學(xué)的一個(gè)子學(xué)科，它研究上述各種情況下破解一套密碼算法的方法及計(jì)算難度。密碼算法設(shè)計(jì)和密碼分析是“矛”和“盾”的關(guān)系，它們其實(shí)是相輔相成的。3.1.2密碼學(xué)發(fā)展歷程加密技術(shù)的應(yīng)用可以追溯到數(shù)千年前的軍事活動(dòng)。我國(guó)周朝兵書(shū)《六韜》中就有用不同長(zhǎng)短的“符”及其組合表示信息的記錄。古希臘城邦的戰(zhàn)爭(zhēng)中，也有使用簡(jiǎn)單密碼保護(hù)軍事情報(bào)的記錄。在“二戰(zhàn)”中，美軍對(duì)日軍的密碼破譯成為左右太平洋戰(zhàn)爭(zhēng)戰(zhàn)局的關(guān)鍵點(diǎn)。特別是20世紀(jì)的后幾十年中，密碼學(xué)經(jīng)歷了日新月異的發(fā)展。人們一般將密碼技術(shù)的發(fā)展歷程大致劃分為三個(gè)階段。第一個(gè)階段的密碼技術(shù)主要是簡(jiǎn)單的古典密碼，如移位碼和仿射密碼等。這類密碼通?；诤?jiǎn)單的經(jīng)驗(yàn)設(shè)計(jì)或代數(shù)設(shè)計(jì)。人們常將這個(gè)階段的密碼算法稱為“古典”密碼算法或“經(jīng)典”密碼算法。第二階段開(kāi)啟的標(biāo)志是在1949年，ClaudeElwoodShannon發(fā)表了具有廣泛影響力的學(xué)術(shù)論文“CommunicationTheoryofSecrecySystems”。Shannon（香農(nóng)）生于1916年，曾獲得麻省理工學(xué)院博士學(xué)位，他的主要研究成果都在麻省理工學(xué)院和貝爾實(shí)驗(yàn)室完成。香農(nóng)啟發(fā)人們基于信息和編碼理論研究密碼，真正意義上將密碼研究帶入了“密碼學(xué)”的學(xué)科研究時(shí)代。第三個(gè)階段的標(biāo)志是非對(duì)稱加密技術(shù)的發(fā)源。1976年，WhitfieldDiffie與MartinHellman發(fā)表的論文“NewDirectionsinCryptography”給出了一種新的思路：加密和解密可以使用不同的函數(shù)及密鑰，規(guī)避了使用同一密鑰時(shí)密鑰本身的泄密問(wèn)題。后來(lái)，一些專家和學(xué)者基于這一全新思路構(gòu)建了許多非對(duì)稱加密算法。非對(duì)稱加密技術(shù)是諸多互聯(lián)網(wǎng)安全協(xié)議的重要技術(shù)基礎(chǔ)，為互聯(lián)網(wǎng)應(yīng)用的迅猛發(fā)展提供了安全保障。Whitfield和Martin由于在密碼學(xué)方面做出了卓越貢獻(xiàn)而榮獲2015年的ACM圖靈獎(jiǎng)。3.1.3密碼算法的分類常見(jiàn)的密碼算法分類方式如表3-1所示。表3-1密碼算法的分類根據(jù)算法和密鑰的異同，可以將密碼算法分為對(duì)稱加密和非對(duì)稱加密兩類。在對(duì)稱加密中，加密和解密函數(shù)在形態(tài)或原理上非常相似，而且加密和解密過(guò)程中使用的密鑰k1和k2是相同的?？梢詫D3-1形象地看作：Alice將信息存入一個(gè)密碼箱并加鎖，而B(niǎo)ob得到同一個(gè)密碼箱，并用復(fù)制的鑰匙打開(kāi)密碼箱獲得信息。對(duì)稱加密算法面臨著兩個(gè)挑戰(zhàn)。第一，如何保護(hù)密鑰的安全？密鑰不能和信息在同一信道上進(jìn)行傳輸，需另外開(kāi)辟一條安全通道。第二，在實(shí)際應(yīng)用中，如何規(guī)避通信雙方之間的欺詐？例如，若Alice是采購(gòu)方，Bob是供應(yīng)商，Alice將加密后的訂單發(fā)給Bob作為采購(gòu)需求發(fā)起的標(biāo)志。由于Alice和Bob都知道密鑰，Bob可以偽裝訂單信息，或者Alice可以稱某個(gè)真實(shí)訂單是由Bob偽造的。非對(duì)稱加密中的加密和解密使用不同的密鑰（k1≠k2），可以很好地解決類似問(wèn)題。在非對(duì)稱加密算法中，一般將加密密鑰k1稱為公鑰，而將解密密鑰k2稱為私鑰（注意這并不是絕對(duì)的）。非對(duì)稱加密算法一般有兩個(gè)基本要求：第一，通過(guò)公鑰不能夠輕易推算出私鑰；第二，利用公鑰不可能進(jìn)行解密計(jì)算。在后續(xù)章節(jié)中，我們會(huì)進(jìn)一步理解其中的奧妙。根據(jù)對(duì)信息序列的計(jì)算處理方式，可以將密碼算法分為分組密碼和流密碼兩類。分組密碼一般是將原文序列m劃分為若干個(gè)分組，即每個(gè)分組是一定長(zhǎng)度的信息塊。各信息塊再通過(guò)相同或不同的密鑰分別進(jìn)行加密，稱為密文序列。在接收端，解密函數(shù)對(duì)各信息塊分別進(jìn)行解密，然后重構(gòu)原文序列m。一般情況下，單個(gè)信息塊的長(zhǎng)度要兼顧計(jì)算復(fù)雜度和加密算法的安全性來(lái)選取。流密碼對(duì)原文序列m中的單個(gè)比特進(jìn)行加密操作。首先采用一定的方法產(chǎn)生和原文序列m等長(zhǎng)的密鑰序列k，然后利用密鑰序列中相應(yīng)位置的密鑰逐位對(duì)原文序列信息位進(jìn)行加密。流密碼的安全性主要依賴于所采用的密鑰序列，一般情況下基于長(zhǎng)的偽隨機(jī)序列或遞歸的方式來(lái)構(gòu)建。3.1.4基礎(chǔ)理論簡(jiǎn)析密碼學(xué)基礎(chǔ)理論中涉及的代數(shù)、信息論等原理比較繁復(fù)，為達(dá)到深入淺出的目的，本節(jié)只對(duì)其中的精要進(jìn)行概述。在不影響讀者理解后續(xù)密碼算法的前提下，我們并不試圖涵蓋所有理論細(xì)節(jié)。1.密碼學(xué)的數(shù)學(xué)定義首先，現(xiàn)代密碼學(xué)的發(fā)端是將密碼算法的研究表述為數(shù)學(xué)問(wèn)題，并利用諸多數(shù)學(xué)原理去分析和設(shè)計(jì)。一般來(lái)說(shuō)，密碼學(xué)的研究課題是構(gòu)建一個(gè)五元組：{M,S,K,E,D}其中，M是明文空間，它代表全體明文構(gòu)成的集合；S和K分別是密文和密鑰空間；E和D分別是加密算法和解密算法構(gòu)成的集合。E中包含一系列可能的加密變化，其中任意一個(gè)加密變化都可將M中的一個(gè)元素?fù)Q算為S中的一個(gè)元素；集合D中則包含一系列的解密變化，完成和集合E相反的映射。在下文中，在不特別指出時(shí)，我們將用大寫(xiě)字母代表空間或集合，用小寫(xiě)字母代表集合中的某個(gè)元素?；诖耍粋€(gè)密碼體制成立的條件是：對(duì)于任意m∈M，都有e∈E、d∈D、k∈K，以及s∈S，且滿足：s=e(m,k)以及m=d(s,k)以上就是密碼體制的數(shù)學(xué)定義。根據(jù)Kerckhoffs原則，Carl可能知道Alice和Bob所采用的密碼體制，但是并不知道密鑰。Alice和Bob可以事先約定一個(gè)密鑰k∈K。由于密鑰空間K足夠大，Carl不可能輕易地破解Alice和Bob使用的是密鑰空間中的哪個(gè)密鑰。我們還可以看出，一個(gè)密碼體制成立的必要條件是加密函數(shù)e必須是一個(gè)一對(duì)一映射函數(shù)，否則會(huì)出現(xiàn)一個(gè)密文s可能對(duì)應(yīng)多個(gè)原文m的情況，導(dǎo)致Bob在解密的時(shí)候不可避免地出現(xiàn)歧義。此外，還要注意，一些情況下密鑰k可以是一個(gè)加、解密的密鑰對(duì)：k={ke,kd}兩個(gè)密鑰對(duì)應(yīng)于加密和解密過(guò)程中采用的不同密鑰。2.香農(nóng)信息理論美國(guó)科學(xué)家香農(nóng)的主要研究工作完成于20世紀(jì)中葉，他是信息論和編碼理論領(lǐng)域的奠基人，他的研究為現(xiàn)代密碼學(xué)理論打下了堅(jiān)實(shí)的基礎(chǔ)。香農(nóng)在1949年發(fā)表了論文“CommunicaitonTheoryofSecrecySystems”，率先用信息論的相關(guān)數(shù)學(xué)模型來(lái)研究加密系統(tǒng)。他的論述在數(shù)十年后才開(kāi)始產(chǎn)生廣泛影響。正是在香農(nóng)理論的啟發(fā)之下，1976年，Diffie和Hellman提出了新的思路，將密碼算法帶向了公鑰加密方向。香農(nóng)的信息論原理的內(nèi)容非常多，可作為一門(mén)專門(mén)的學(xué)科進(jìn)行學(xué)習(xí)，我們下面做一下密碼學(xué)方向的初探。香農(nóng)信息論的研究框架是三段論。Step1：將通信過(guò)程建模成一個(gè)數(shù)學(xué)模型，信源、信道和信宿都可以建模成隨機(jī)過(guò)程；Step2：利用概率論、信息論的數(shù)學(xué)工具研究上述過(guò)程，摸清統(tǒng)計(jì)特性和各種規(guī)律；Step3：找到通信中各種算法的理論界限，提出設(shè)計(jì)的指導(dǎo)思路。密碼學(xué)中的加密、攻擊和解密等也可以用上述過(guò)程來(lái)建模。香農(nóng)首先建議以“信息熵”為基本度量來(lái)研究{M,S,K,E,D}等各個(gè)集合的統(tǒng)計(jì)特性。“熵”原本是一個(gè)熱力學(xué)概念，后被香農(nóng)引入了信息理論中。以密鑰空間K為例，假設(shè)K包含n個(gè)元素{k1,k2,…,kn}，且任一元素ki被使用的概率為Pr(ki)，則空間K的熵可以表示為：很容易看出，H(K)是一個(gè)用密鑰空間K中各個(gè)元素出現(xiàn)的概率來(lái)加權(quán)求和一系列變量的結(jié)果，且這一系列變量的大小和該元素出現(xiàn)概率的大小成反比。這些變量可以被不甚嚴(yán)格地理解為“信息量”，比如1個(gè)等概率取值0或1的隨機(jī)數(shù)，其任一取值的信息量恰好為1，那么由于0和1出現(xiàn)的概率都是50%，因此加權(quán)求和得到的信息熵為1位。那么，H(K)衡量的是什么呢？可以想象，當(dāng)密鑰空間K中的元素越多時(shí)，可能性就越大，則H(K)的值也越大。H(K)衡量的就是密鑰空間中包含的不確定性，其值越大，說(shuō)明密鑰空間不確定性越大。反過(guò)來(lái)，如果密鑰空間只有一個(gè)元素k1，那么Pr(k1)=1，則H(K)=0。顯然，這樣的密鑰空間是沒(méi)有實(shí)際意義的。香農(nóng)還建立了用“熵”的模型判斷加密體制的方式。根據(jù)他的理論可以得出：H(K/S)=H(K)+H(M)-H(S)這里H(K/S)，即“條件熵”，是一個(gè)非常有價(jià)值的變量。它衡量的是Carl已知密文S后，對(duì)于密鑰K還有多少不確定性。如果說(shuō)H(K/S)=0，說(shuō)明已知S時(shí)K就沒(méi)有額外不確定性了，這說(shuō)明Carl很容易從S中猜出K，加密體制設(shè)計(jì)失敗。反之，H(K/S)越大，系統(tǒng)越安全。還有一個(gè)啟發(fā)，假設(shè)明文和密文空間一樣大，且明文和密文中的元素都是等概率出現(xiàn)、充分隨機(jī)的，那么H(M)和H(S)相等，這時(shí)密鑰空間越大，即H(K)越大，密碼體制越安全。有了這些數(shù)學(xué)工具，人們?cè)诿鎸?duì)一種新的算法時(shí)就可以有的放矢地進(jìn)行分析了。以這些理論為基礎(chǔ)，香農(nóng)進(jìn)一步提出了若干密碼算法設(shè)計(jì)的概念，如表3-2所示。表3-2密碼算法設(shè)計(jì)的概念我們?cè)诤罄m(xù)章節(jié)中會(huì)反復(fù)看到，現(xiàn)代密碼學(xué)體制會(huì)貫徹這些思想，充分地將明文、密鑰進(jìn)行擴(kuò)散和混淆。在分組密碼中，我們也會(huì)看到利用多輪迭代來(lái)構(gòu)造出乘積密碼的結(jié)構(gòu)，從而增強(qiáng)加密算法安全性的例子。密碼學(xué)研究的課題是對(duì)明文、密文、密鑰集合以及加密和解密變換集合的研究，因此密碼學(xué)理論中貫穿著集合的概念。為了更好地理解密碼學(xué)算法，要進(jìn)行一些必要的知識(shí)準(zhǔn)備。我們對(duì)于集合并不陌生，如整數(shù)、實(shí)數(shù)、素?cái)?shù)（又稱質(zhì)數(shù)）等都是集合。由于計(jì)算機(jī)處理的特性，在密碼學(xué)算法中主要考慮整數(shù)集合Z的子集，即由一部分特殊性質(zhì)的整數(shù)構(gòu)成的集合。群、環(huán)和域就是由一系列的篩選規(guī)則來(lái)定義的。我們理解這些知識(shí)的思路是，首先定義集合上最基本的數(shù)學(xué)運(yùn)算，然后基于這些基本運(yùn)算理解重要的群、環(huán)和域的概念。基本的數(shù)學(xué)運(yùn)算包含模加法和模乘法兩種，它們和一般加法、乘法的區(qū)別是，模加和模乘的結(jié)果是將一般加法、乘法的結(jié)果再做模運(yùn)算得到的余數(shù)。例如，在一個(gè)集合Z6={0,1,2,3,4,5}中做模加和模乘的計(jì)算如下：（3+4）mod5=2以及（2×3）mod5=1有了這些基本運(yùn)算，就可以定義幾個(gè)基本的集合概念。這些重要的概念如表3-3所示。表3-3幾個(gè)重要的集合概念讓我們從“群”的概念開(kāi)始。首先要理解群的概念是基于某個(gè)集合和某個(gè)運(yùn)算來(lái)說(shuō)的，例如某個(gè)群G對(duì)于模和運(yùn)算構(gòu)成加法群。如果集合G對(duì)某種數(shù)學(xué)運(yùn)算滿足以下四個(gè)性質(zhì)，則稱集合G是一個(gè)加法群。封閉性：任何G中的兩個(gè)元素a和b的模和(a+b)的結(jié)果仍是G的元素。結(jié)合律：(a+b)+c=a+(b+c)。單位元：存在u，使得a+u=a，u+a=a；對(duì)于加法來(lái)說(shuō)，有u=0。逆元：存在b，使得a+b=0；b稱為a的加法逆元，或者說(shuō)b=a-1。以上這些性質(zhì)很容易理解。還可以驗(yàn)證：一個(gè)基本的整數(shù)集Zm={0,1,…,m-1}就是一個(gè)“加法群”。顯然，集合Zm乘法不構(gòu)成群，因?yàn)椴粷M足逆元存在的要求。如果集合G在滿足上述條件的基礎(chǔ)上進(jìn)一步滿足交換律，則我們稱它為“交換群”或“阿貝爾群”。如果上述交換群G再增加一些關(guān)于乘法的性質(zhì)，就可以得到“環(huán)”的概念。具體地說(shuō)，如果交換群G滿足對(duì)乘法的結(jié)合律、封閉性、單位元，并且滿足乘法和加法的分配律，那么將集合G稱為一個(gè)“環(huán)”；如果G進(jìn)一步滿足乘法的交換律，就構(gòu)成“交換環(huán)”。如果在上述條件的基礎(chǔ)上，G進(jìn)一步滿足以下條件，則稱G為一個(gè)“域”：對(duì)任何G中的元素a，如果a≠0，均能找到a的乘法逆元b=a-1，使得a×b=b×a=1。簡(jiǎn)而言之，如果在環(huán)G中非零元素a都能找到乘法逆元，則G構(gòu)成一個(gè)“域”。我們所熟知的實(shí)數(shù)、有理數(shù)等集合，對(duì)一般意義的加法和乘法來(lái)說(shuō)都構(gòu)成域。如果某個(gè)域所包含的元素個(gè)數(shù)有限，則稱其為“有限域”。另一個(gè)重要概念是“循環(huán)群”：如果一個(gè)群G中可以找到一個(gè)元素g，使得G中任意元素都是g的乘方，那么G是一個(gè)循環(huán)群，而g是G的一個(gè)生成元或本原元。為什么要理解這些看上去較為復(fù)雜的集合概念呢？我們已經(jīng)知道，密碼學(xué)研究的課題就是對(duì)明文、密文、密鑰等集合{M,S,K,E,D}進(jìn)行選擇。在選擇這些集合時(shí)，需要利用群、環(huán)和域的一些性質(zhì)，并且我們也需要理解各種加密、解密運(yùn)算是如何作用于這些集合的。所以，花些時(shí)間理解這些集合的概念和相應(yīng)運(yùn)算的性質(zhì)是有必要的。至此我們簡(jiǎn)要了解了群、環(huán)和域的概念，也認(rèn)識(shí)了乘法逆、循環(huán)群及其生成元。在后續(xù)密碼學(xué)算法的介紹中，我們還會(huì)反復(fù)接觸這些基本概念。3.2公鑰密碼體制前述算法面臨著一個(gè)共同的挑戰(zhàn)，即密鑰的泄露問(wèn)題。在系統(tǒng)設(shè)計(jì)中，需要考慮傳輸密鑰的安全通道，這本身又是一個(gè)加密系統(tǒng)。為了避免陷入這種循環(huán)嵌套的難題，現(xiàn)代密碼學(xué)走出了“公鑰”密碼體制的新方向。自1976年WhitfieldDiffie與MartinHellman提出理論方向后，公鑰加密算法的研究已經(jīng)持續(xù)了數(shù)十年。表3-4歸納了目前常見(jiàn)的公鑰加密算法的主要技術(shù)方向。表3-4公鑰加密算法的主要技術(shù)方向?qū)τ谝粋€(gè)隱秘的私鑰ks，公鑰加密算法的一般要求是：Bob很容易驗(yàn)證某個(gè)特定的km是否和ks“匹配”，若能匹配，則令km為公鑰；Alice很容易用公鑰km來(lái)加密明文；Bob很容易用私鑰來(lái)ks解密密文；Carl無(wú)法用公鑰km來(lái)解密密文，且無(wú)法從km中推算出ks。公鑰加密算法的核心是構(gòu)建一個(gè)“數(shù)學(xué)難題”，使得人們很難從公開(kāi)的km推算出ks，但是可以很容易地驗(yàn)證某個(gè)特定km是否和ks匹配。所謂“匹配”，即滿足“公鑰加密，私鑰解密”的過(guò)程。為了方便理解，我們可以簡(jiǎn)稱上述密鑰的特征為“易驗(yàn)證，難推算”。由于“易驗(yàn)證”，Bob可以隨機(jī)選擇一個(gè)私鑰并快速找到能匹配的公鑰。由于“難推算”，在圖3-2中，Carl即使得知了公鑰，也無(wú)法計(jì)算私鑰。圖3-2使用公/私鑰進(jìn)行加密和解密的過(guò)程3.2.1RSA算法RSA是由羅納德·李維斯特（RonRivest）、阿迪·薩莫爾（AdiShamir）和倫納德·阿德曼（LeonardAdleman）在1977年共同提出的，并由此三人的名字命名。該算法是具有代表性的基于大整數(shù)分解的非對(duì)稱加密算法。下面通過(guò)兩部分了解RSA算法：公、私鑰參數(shù)生成以及加、解密過(guò)程。RSA的公、私鑰參數(shù)生成過(guò)程如下。Step1：選擇大素?cái)?shù)p和q。然后根據(jù)p和q直接計(jì)算n以及φ(n)，滿足n=pq，且φ(n)=(p-1)(q-1)。Step2：隨機(jī)選擇公鑰t，使得t和φ(n)的最大公約數(shù)為1，且t<φ(n)。Step3：計(jì)算t的乘法逆元h，滿足t×hmodφ(n)=1。上述結(jié)果中，{p,q,h}為私鑰，{n,t}為公鑰。生成參數(shù)之后，就可以進(jìn)行相應(yīng)的加、解密操作了。加、解密的過(guò)程如下。Step1：Bob計(jì)算RSA密鑰參數(shù)，并將公鑰{n,t}公開(kāi)發(fā)布，將私鑰{p,q,h}本地保存。Step2：Alice知道公鑰{n,t}，利用函數(shù)s=mtmodn對(duì)原文m進(jìn)行加密。Step3：Bob得到密文s，并利用私鑰{p,q,h}對(duì)密文進(jìn)行解密，計(jì)算函數(shù)為m=shmodn。上述所有計(jì)算過(guò)程都是在集合Zn={0,1,…,n-1}中完成的。這些過(guò)程看上去復(fù)雜，不禁讓人產(chǎn)生疑問(wèn)：為什么這些參數(shù)和運(yùn)算可以將明文加密再恢復(fù)成密文呢？我們不妨對(duì)該過(guò)程進(jìn)行簡(jiǎn)單的推導(dǎo)。由于參數(shù)生成的過(guò)程中有t×hmodφ(n)=1，顯然(mt)hmodn=ma×φ(n)+1modn這里a為整數(shù)。如果加密過(guò)程能恢復(fù)出明文m，需要有ma×φ(n)modn=1。大家可以了解mφ(n)modn=1這個(gè)結(jié)論是成立的。而且，當(dāng)m和n的最大公約數(shù)為1時(shí)，這個(gè)結(jié)論是數(shù)論中非常著名的“歐拉定理”；當(dāng)m和n的最大公約數(shù)不為1時(shí)，由于n是兩個(gè)素?cái)?shù)p和q的乘積，我們可以把m表示為p或q的倍數(shù)，那么mφ(n)modn=1這個(gè)結(jié)論也比較容易驗(yàn)證，在此不展開(kāi)具體證明。以上是RSA算法的密鑰生成和加、解密的基本過(guò)程。下面對(duì)RSA背后的數(shù)學(xué)原理做一些解釋。在參數(shù)生成的過(guò)程中，再一次用到了乘法逆的概念。我們已經(jīng)知道，t的乘法逆h存在的充分必要條件是t和φ(n)的最大公約數(shù)為1。如果Carl能很容易地把公鑰n分解且得到n=p×q，并計(jì)算φ(n)，就可以像Bob一樣計(jì)算出私鑰{p,q,h}。但在實(shí)際中，這是不可能的。其原理在于大整數(shù)n的素?cái)?shù)分解一直是世界級(jí)的數(shù)學(xué)難題。以目前的研究進(jìn)展來(lái)看，長(zhǎng)度為1024位的大整數(shù)是無(wú)法破解的。當(dāng)Bob試圖生成公、私鑰參數(shù)時(shí)，由于他也無(wú)法解決上述難題，不可能先隨機(jī)找到一個(gè)大整數(shù)n再做素?cái)?shù)分解?？尚械姆椒ㄊ?，Bob先找到兩個(gè)比較大的素?cái)?shù)p和q，然后用它們來(lái)計(jì)算n和φ(n)。這里就涉及數(shù)論中的另一個(gè)經(jīng)典問(wèn)題，即素性檢測(cè)。目前的RSA算法實(shí)現(xiàn)常選取512位的p和q、1024位的n。幸運(yùn)的是，對(duì)于這種數(shù)量級(jí)來(lái)說(shuō)，隨機(jī)生成一個(gè)整數(shù)且剛好為素?cái)?shù)的概率約為幾百分之一。Bob完全可以隨機(jī)生成p和q，然后判斷它們是否為素?cái)?shù)。這種操作的復(fù)雜度是可以接受的。目前，比較常見(jiàn)的素性檢測(cè)算法有費(fèi)馬檢測(cè)、Miller-Rabin檢測(cè)和Solovay-Strassen檢測(cè)等，這些算法都是比較高效的。Bob在得到n和φ(n)后，還需要能快速計(jì)算出和φ(n)互素的整數(shù)t，以及t的乘法逆h，這可以用歐幾里得算法高效實(shí)現(xiàn)。RSA算法要求將明文m也表示成大整數(shù)，即m∈Zn。如果原文信息m太長(zhǎng)，超出了RSA算法的要求，可以先對(duì)原文進(jìn)行分塊，再對(duì)每一塊執(zhí)行RSA加密。3.2.2ElGamal算法ElGamal算法的過(guò)程分為三個(gè)步驟：第一步，Bob基于某個(gè)數(shù)學(xué)難題構(gòu)造私鑰和公鑰參數(shù)，并將公鑰公布，私鑰自存；第二步，Alice根據(jù)公鑰生成密文，并將密文發(fā)送給Bob；第三步，Bob利用私鑰對(duì)密文解密。大家會(huì)發(fā)現(xiàn)上述過(guò)程和RSA并無(wú)二致，因?yàn)檫@正是非對(duì)稱加密的一般框架。但是，ElGamal算法和RSA算法到底有哪些區(qū)別呢？簡(jiǎn)要地說(shuō)，區(qū)別主要有以下兩個(gè)方面。第一，算法基于的數(shù)學(xué)難題不同，RSA的基礎(chǔ)是大整數(shù)的素?cái)?shù)分解，而ElGamal算法是基于離散對(duì)數(shù)問(wèn)題構(gòu)建的。第二，加密和解密的計(jì)算過(guò)程也不同，在ElGamal算法中Alice除了用公鑰對(duì)明文進(jìn)行加密之外，還利用自己秘密生成的一個(gè)隨機(jī)數(shù)生成一個(gè)隨機(jī)密碼，并將該隨機(jī)密碼和密文一起發(fā)給Bob，Bob利用私鑰、隨機(jī)密碼和密文恢復(fù)明文。下面對(duì)這兩個(gè)方面進(jìn)行詳細(xì)的介紹。Bob生成密鑰參數(shù)的操作有以下幾步：Step1：找到一個(gè)大素?cái)?shù)p。Step2：基于p，滿足一定條件的整數(shù)α，以及另一個(gè)整數(shù)t；其中t需要滿足2≤t≤p-2。Step3：計(jì)算β=αtmodp。上述過(guò)程中，參數(shù){α,β,p}為公鑰，t為私鑰。Alice利用公鑰參數(shù)加密的步驟如下：Step1：選擇秘密的隨機(jī)數(shù)i，滿足2≤i≤p-2。Step2：計(jì)算隨機(jī)密碼ka=αimodp。Step3：用公鑰對(duì)明文m進(jìn)行加密得到密文s，即s=m×βimodp。Step4：將隨機(jī)密碼ka和密文s都發(fā)送給Bob。Bob利用私鑰參數(shù)進(jìn)行解密的過(guò)程較簡(jiǎn)單，其計(jì)算方法如下：m=s×[(ka)t]-1modp從表面的數(shù)學(xué)形式來(lái)看，上述過(guò)程非常容易推導(dǎo)，其核心是β=αtmodp。但實(shí)際上，上述過(guò)程中參數(shù){α,β,p}以及i的選擇都有一定的限制條件，其背后有著比較豐富的數(shù)論原理。下面我們?cè)噲D以比較簡(jiǎn)明的語(yǔ)言來(lái)解釋ElGamal算法涉及的數(shù)論知識(shí)。通常情況下，上述ElGamal算法的運(yùn)算都發(fā)生在一個(gè)特殊的整數(shù)集合中。表示所有小于p且和p最小公約數(shù)為1的整數(shù)所構(gòu)成的集合。我們需要了解，集合有以下兩個(gè)重要的性質(zhì)。該集合中任意一個(gè)元素都有乘法逆，即對(duì)任意都有。這確保了加密和解密算法中的求逆運(yùn)算有效。該集合中可以找到α，使得集合中任何一個(gè)元素都可以用α的冪來(lái)表示。這種情況下，稱α為該集合的生成元。這個(gè)性質(zhì)就使得以α為根來(lái)構(gòu)造離散對(duì)數(shù)問(wèn)題比較簡(jiǎn)單。在數(shù)論中，有經(jīng)典算法可以幫助我們根據(jù)p和快速找到適合的α。除此之外，算法中的乘法、求冪和求逆都是比較簡(jiǎn)單的操作。至此，我們便可更加形象地理解ElGamal算法的原理了。簡(jiǎn)單地說(shuō)，由于的特殊構(gòu)造，集合中所有元素都可以表示為α的冪，當(dāng)然β也可以表示成α的t次冪。由于β很大，以α底來(lái)求解其對(duì)數(shù)很難，因此只有Bob知道私鑰t，其他人只知道公鑰{α,β,p}。剩下的過(guò)程非常簡(jiǎn)單：Alice利用βi對(duì)明文進(jìn)行加權(quán)，而B(niǎo)ob用[(ka)t]-1去除加權(quán)效果。因?yàn)椋涸诤罄m(xù)討論中可以看到，ElGamal利用的離散對(duì)數(shù)問(wèn)題也是數(shù)學(xué)難題，利用窮舉或通用算法破解離散對(duì)數(shù)的計(jì)算復(fù)雜度非常高。并且，和RSA算法相比，ElGamal具有概率的特征，由于Alice選擇隨機(jī)密碼i時(shí)有不確定性，對(duì)于相同的明文m1和m2，加密的密文是不同的。由于i也是在一個(gè)很大的集合中隨機(jī)選擇的，這顯著增加了窮舉型破解方式的計(jì)算復(fù)雜度。3.2.3橢圓曲線算法ElGamal算法的思路可以從中推廣到其他類型的群。橢圓曲線加密算法就是一個(gè)很好的例子。橢圓曲線算法于20世紀(jì)80年代被提出，稍晚于RSA和ElGamal算法。在相同密鑰長(zhǎng)度的情況下，攻擊橢圓曲線算法的計(jì)算復(fù)雜度遠(yuǎn)高于RSA和ElGamal算法。而且，一般情況下橢圓曲線算法的計(jì)算復(fù)雜度也較低。但是，橢圓曲線的數(shù)學(xué)原理比之前提到的大整數(shù)分解、離散對(duì)數(shù)等都更復(fù)雜。在下面的篇幅中，我們?cè)噲D以較為簡(jiǎn)明的語(yǔ)言闡述其基本原理。在代數(shù)中常用方程式來(lái)定義曲線，例如直線、圓周和拋物線等。橢圓曲線也一樣，它由一個(gè)二元方程來(lái)定義。為了構(gòu)建加密算法，我們先要在橢圓曲線上構(gòu)建數(shù)學(xué)運(yùn)算，這就是橢圓曲線上的“加法”。這里的加法運(yùn)算和簡(jiǎn)單的加法或模和是完全不同的。從幾何的角度來(lái)看，橢圓曲線上兩個(gè)點(diǎn){P,Q}的加法P+Q過(guò)程等效為定位一個(gè)點(diǎn)U，使得U是“P和Q點(diǎn)連線的延長(zhǎng)線與曲線的交點(diǎn)的x軸對(duì)稱點(diǎn)”。依此類推，可繼續(xù)利用P和2P在橢圓曲線上定位3P這個(gè)點(diǎn)。通過(guò)合理地構(gòu)造橢圓曲線，我們可以保證在n足夠大的時(shí)候，nP總是曲線上的某個(gè)點(diǎn)。這里又一次用到了“生成元”的概念。在一定條件下，橢圓曲線上所有的點(diǎn)都可以用P的多次“加法”來(lái)得到。于是，引申出橢圓曲線加密中用到的數(shù)學(xué)難題，即：給定兩個(gè)點(diǎn)P和Q，若已知P=nQ，求n。由于n足夠大，通過(guò)P和Q求解n是很困難的。Bob確定橢圓曲線上的某個(gè)點(diǎn)G，然后根據(jù)一個(gè)秘密的隨機(jī)數(shù)k來(lái)計(jì)算出F=kG，其中{G,F}為公鑰，k為私鑰。然后是基于上述密鑰的加密和解密過(guò)程?，F(xiàn)簡(jiǎn)要介紹如下。當(dāng)Alice得到公鑰后，分兩個(gè)步驟構(gòu)建密文。Step1：找出一個(gè)隨機(jī)數(shù)r，然后在橢圓曲線上找到rG；Step2：用公鑰加密明文m，即s=m+rF。Alice把兩部分密文{rG,s}一并發(fā)給Bob。Bob解密的過(guò)程比較簡(jiǎn)單。當(dāng)Bob收到密文后，利用私鑰和兩部分密文進(jìn)行運(yùn)算，計(jì)算方式為：m=s–krG由于krG=rF，所以很容易驗(yàn)證上述加密、解密過(guò)程成立。實(shí)際上，上述算法的幾何意義非常容易理解。Bob生成私鑰的過(guò)程，就是利用點(diǎn)G和隨機(jī)選擇的秘密參數(shù)k來(lái)找到點(diǎn)F。Alice利用rF加法操作將明文對(duì)應(yīng)的點(diǎn)在橢圓曲線上搬運(yùn)到密文對(duì)應(yīng)的點(diǎn)，然后Bob利用krG加法操作把密文映射回明文。研究表明，當(dāng)橢圓曲線的參數(shù)p很大時(shí)，從G和F來(lái)推算k是非常困難的。例如，如果p是一個(gè)200位的數(shù)，那么橢圓曲線上可能的點(diǎn)的數(shù)量級(jí)是2160。在這樣一個(gè)巨大的集合中，在橢圓曲線上回溯k基本是不可能做到的。但是反過(guò)來(lái)，如果已知n，則有快速算法可以直接由P求出Q。這和公鑰加密算法中“易驗(yàn)證，難推算”的精神是一致的。3.2.4公鑰密碼的安全性分析RSA算法的核心是大整數(shù)分解。在過(guò)去數(shù)十年中，許多學(xué)者對(duì)該難題進(jìn)行了研究，提出了諸如二次篩選法、橢圓曲線算法、數(shù)域篩選法等一系列的算法，在這個(gè)方向上做出了一些成績(jī)。但是，從20世紀(jì)90年代至今，算法或架構(gòu)上并沒(méi)有跨越性的新突破。這是RSA算法成立的重要基礎(chǔ)。在花費(fèi)大量財(cái)力和物力、組織大規(guī)模計(jì)算能力的前提下，目前已有學(xué)者提出可以分解512位甚至是768位長(zhǎng)度的大整數(shù)。有研究表明，分解算法每十年約能多提升100位的分解長(zhǎng)度。到目前為止，分解1024位乃至更大的整數(shù)在工程實(shí)現(xiàn)上基本是不可能的。因此，RSA一般選擇1024或2048位的大整數(shù)長(zhǎng)度。ElGamal利用的離散對(duì)數(shù)問(wèn)題也是數(shù)學(xué)難題。如果在集合Zp中遍歷地尋找密鑰d，其復(fù)雜度為2p。ElGamal算法一般選擇p為1024位或2048位，這意味著暴力破解基本是不可能的。離散對(duì)數(shù)也有相應(yīng)的通用算法，例如Shanks算法和Pohling-Hellman算法等。研究表明，這些算法的計(jì)算復(fù)雜度不低于2(p/2)。在密鑰長(zhǎng)度相同的情況下，橢圓曲線的破解是最困難的。橢圓曲線的基本運(yùn)算（求“和”是在曲線上做點(diǎn)的映射）比RSA和ElGamal復(fù)雜得多，因此一般認(rèn)為密鑰長(zhǎng)度為160位的橢圓曲線算法和密鑰長(zhǎng)度為1024位的RSA/ElGamal算法安全性相當(dāng)。實(shí)際中，常用的橢圓曲線算法密鑰長(zhǎng)度為256位。3.3數(shù)字簽名現(xiàn)實(shí)生活中，我們常用簽名來(lái)驗(yàn)證某個(gè)文件或許可的授權(quán)者。簽名的動(dòng)作是授權(quán)，驗(yàn)證筆跡的過(guò)程是確認(rèn)簽名的真實(shí)性。在多種信息系統(tǒng)中，我們也會(huì)用到相似的數(shù)字簽名方案。簽名方案一般包括簽名和認(rèn)證兩個(gè)算法。下面依然以Alice和Bob的交互為例來(lái)說(shuō)明。假設(shè)Bob要發(fā)給Alice一條信息m，而且兩人希望建立一套機(jī)制，幫助Alice在收到信息時(shí)能驗(yàn)證這條信息是否真的來(lái)自于Bob，而不是Carl偽造出來(lái)的。算法的基本過(guò)程如下。Step1：Bob生成私鑰kr和公鑰kp等參數(shù)，并將公鑰kp公開(kāi)。Step2：Bob利用私鑰kr為信息m生成簽名s，生成簽名后的數(shù)據(jù)為{m,s}，并將該數(shù)據(jù)發(fā)送給Alice。Step3：Alice利用公鑰kp對(duì){m,s}進(jìn)行驗(yàn)證。如果驗(yàn)證通過(guò)，則確認(rèn)該條信息來(lái)自Bob，反之則否認(rèn)?？梢钥吹?，數(shù)字簽名方案背后的基本原理和非對(duì)稱密碼算法是相似的，但似乎公鑰和私鑰的使用過(guò)程反過(guò)來(lái)了。下面簡(jiǎn)要介紹哈希函數(shù)和幾種常見(jiàn)的數(shù)字簽名算法。3.3.1哈希函數(shù)實(shí)際中，信息m可能很長(zhǎng)，直接對(duì)m進(jìn)行簽名是低效的。一般的方法是先為信息m生成“摘要”，然后對(duì)摘要進(jìn)行簽名，這并不影響簽名的安全性。哈希函數(shù)就是生成數(shù)字摘要的有效手段。哈希函數(shù)的計(jì)算過(guò)程可用y=h(x)表示。x是原始信息，y是x的短摘要。哈希函數(shù)有幾個(gè)重要特點(diǎn)。第一，它是單向的，即只能由x求解y，而不能輕易用y反推x。第二，它要抗碰撞，即在計(jì)算上很難找到兩個(gè)不同的原始消息x1和x2，使它們的摘要相等，即h(x1)=h(x2)。最常見(jiàn)的哈希函數(shù)有MD5和SHA-1算法。它們的哈希摘要長(zhǎng)度不同，SHA-1算法的哈希摘要長(zhǎng)度為160，而MD5算法的摘要長(zhǎng)度為128。1979年，Merkle提出了一種統(tǒng)一的哈希函數(shù)構(gòu)造。該構(gòu)造中，消息m被劃分為若干等份，然后迭代式地運(yùn)用一個(gè)壓縮函數(shù)f對(duì)每一塊進(jìn)行處理，最終得出摘要。這個(gè)過(guò)程如圖3-3所示。圖3-3哈希函數(shù)的通用架構(gòu)MD5函數(shù)和SHA-1函數(shù)都采用上述通用架構(gòu)。MD5將原文消息劃分為長(zhǎng)度為512比特的等份。由于原文消息的長(zhǎng)度是任意的，在MD5算法的開(kāi)始階段首先要對(duì)消息進(jìn)行填充，使得它恰好為512的整數(shù)倍。對(duì)每一個(gè)512長(zhǎng)度的分塊，按照通用架構(gòu)的過(guò)程，利用函數(shù)fMD5進(jìn)行迭代式的處理。fMD5函數(shù)的內(nèi)部結(jié)構(gòu)也是迭代的，它包含64步操作，主要由邏輯與、或、異或和否等運(yùn)算組成，中間結(jié)果保存在4個(gè)32位的寄存器中，非常便于計(jì)算機(jī)實(shí)現(xiàn)。上述兩個(gè)層次的迭代和多種邏輯運(yùn)算，使得MD5輸出的128位摘要值的每一位都和輸入消息m的每一位相關(guān)，充分地混淆和擴(kuò)散了數(shù)據(jù)。由于具有這樣的效果，因此人們也將哈希函數(shù)稱為“散列”函數(shù)。SHA-1算法對(duì)原始信息的分塊預(yù)處理、整體的運(yùn)算架構(gòu)和MD5算法并無(wú)重大區(qū)別。但在每一輪迭代的壓縮函數(shù)fSHA-1比MD5算法設(shè)計(jì)更精妙。SHA-1算法中的每個(gè)數(shù)據(jù)塊要經(jīng)過(guò)80輪的運(yùn)算，每一輪計(jì)算的中間結(jié)果保存在5個(gè)32位的寄存器中。進(jìn)一步來(lái)說(shuō)，在每一輪運(yùn)算中，fSHA-1引入了可變的運(yùn)算子函數(shù)和加法常量，冗余度和復(fù)雜性都比MD5更高。SHA-1的哈希摘要長(zhǎng)度比MD5長(zhǎng)32位，因此一般認(rèn)為SHA-1的抗攻擊性稍高，但是其計(jì)算復(fù)雜度也更高一些。一般認(rèn)為，摘要長(zhǎng)度越長(zhǎng)，哈希函數(shù)的安全性越高。在SHA-1之后，美國(guó)標(biāo)準(zhǔn)局又引入了SHA-256、SHA-384和SHA-512，進(jìn)一步擴(kuò)展了摘要長(zhǎng)度。3.3.2RSA簽名我們已經(jīng)學(xué)習(xí)過(guò)RSA非對(duì)稱加密算法。RSA簽名方案就是基于該算法構(gòu)建的，其過(guò)程如下。Bob計(jì)算密鑰參數(shù)：{p,q,h}為私鑰，{n,t}為公鑰。將公鑰發(fā)送給Alice。假設(shè)原始信息m的摘要為x，Bob利用簽名函數(shù)對(duì)x進(jìn)行簽名，生成y。計(jì)算函數(shù)如下：y=xhmodn然后，Bob將信息和簽名數(shù)據(jù)發(fā)給Alice。Alice利用公鑰參數(shù)對(duì)簽名進(jìn)行驗(yàn)證。計(jì)算函數(shù)如下：xv=ytmodn如果xv=xmodn，則驗(yàn)證通過(guò)；否則驗(yàn)證失敗?；赗SA算法的數(shù)學(xué)原理，我們知道只有通過(guò)私鑰簽名的函數(shù)才能夠被公鑰參數(shù)驗(yàn)證。在RSA簽名方案中，由于只有Bob擁有私鑰參數(shù)，當(dāng)Alice驗(yàn)證簽名成功后，就可以直接確定該簽名來(lái)自Bob本人了。另一個(gè)附加的功能是，Alice也可以驗(yàn)證原始信息m和x的匹配性，如果m和x匹配，則證明消息傳輸過(guò)程中沒(méi)有遺漏。RSA簽名算法一般選擇參數(shù)n的長(zhǎng)度為1024或2048比特，簽名的長(zhǎng)度和n相同。3.3.3ElGamal簽名ElGamal數(shù)字簽名方案的過(guò)程和RSA簽名方案相似，但采用的參數(shù)和簽名函數(shù)不同?；仡橢lGamal加密算法，密鑰參數(shù)中{α,β,p}為公鑰，d為私鑰。Bob簽名的計(jì)算過(guò)程如下。選擇一個(gè)臨時(shí)的隨機(jī)密鑰w，滿足w<=p