【待更新】北京大學肖臻老師《區塊鏈技術與應用》公開課筆記 02-BTC-密碼學原理-有解無憂

北大肖臻老師《區塊鏈技術與應用》課程鏈接：點擊這里

全系列文章鏈接：點擊這里

主要參考的書籍文獻及圖片來源：《區塊鏈：技術驅動金融》

該系列文章如中有任何侵權內容，或者有鏈接無法打開、圖片加載上傳失敗等情況，請及時與我個人聯系洗掉或修改，

位元幣又名加密貨幣，顧名思義，加密貨幣著力采用密碼技術，

加密數字貨幣系統構建主要用到密碼學中的哈希演算法（Hash）和數字簽名（digital signature）技術，

一、哈希函式

哈希函式是一個數學函式，其具有以下三個特性：

（1）其輸入可為任意大小的字串；（2）它產生固定大小的輸出；（3）它能進行有效計算，

這些特性定義了一般哈希函式，以這個函式為基礎，我們可以創建資料結構，例如哈希表，

但要使哈希函式達到密碼安全，則要求其具有以下三個附加特性：

（1）碰撞阻力（collision-resistance）；（2）隱秘性（hiding）；（3）謎題友好（puzzle-friendliness），

（1）碰撞阻力（collision-resistance）

首先，這里的碰撞是指，對于兩個不同的輸入，產生相同的輸出，可表達為：x≠y，H(x)=H(y)，

而碰撞阻力，即指無法找到兩個值x和y，x≠y，而H(x)=H(y)，

哈希碰撞存在的原因，是由于其輸入空間包含所有長度的任意字串，但輸出空間則只包含特定固定長度的字串，在輸入空間比輸出空間大的情況下（輸入空間是無限的，而輸出空間是有限的），一定會有輸入字串映射到相同的輸出字串，

對于加密的哈希函式，我們雖然說應該找不到碰撞，但有些方法是能保證找到碰撞的，

假設，有一個256位輸出大小的哈希函式，最壞的演算法是進行 $2^{256}$ +1次哈希函式計算，我們在檢驗第 $2^{256}$ +1個輸入之前便很可能找到碰撞，但這個檢測演算法的耗時是一個天文數字，蠻力求解不可行，

之前的MD5哈希函式，在多年的努力之后最終找到了碰撞，導致該函式在實踐中被逐漸淘汰，最終被棄用，

碰撞阻力的應用：資訊摘要（message digest），

已知哈希函式具有碰撞阻力，假設x和y是兩個不同的輸入，那么可以假設它們的哈希函式H(x)和H(y)也不同，如果已知x和y不同，但哈希值H相同，那么H具有碰撞阻力的假設就不成立，

這個論證使我們可以將哈希輸出作為資訊摘要（message digest），

哈希函式對于一個資訊生成固定長度的摘要，或生成了簡明總結，這為我們提供了一種記住之前所見事物，并在今后認出這些事物的有效方法，雖然整個檔案可能非常大，但其哈希值的長度固定，假設哈希函式為256位，這樣極大地降低存盤要求，

（2）隱秘性（hiding）

即，通過哈希函式的輸出y=H(x)，我們沒有可行的辦法算出輸入值x，

但是，如果我們要反解的 x 的取值，就像猜一枚硬幣的正反面，或者第二天股市是否漲停一樣，只有兩種可能，那么還是能將函式對應的哈希值計算出來，這時hiding是不成立的，

上面表述若要成立，則必須使輸入值x的取值來自一個非常廣泛的集合，這里可以引入“高階最小熵”的概念，

當其輸入 r 選自一個高階最小熵（high min-entroy）的概率分布，在給定H（r‖x）條件下，來確定x是不可行的，

在資訊論中，最小熵是用于測驗結果可預測性的手段，而高階最小熵這個概念比較直觀描述了分布（如隨機變數）的分散程度，具體來說，在從這樣分布中取樣時，我們將無法判定取樣的傾向，舉個具體的例子，如果 r 是從長度為256位的字串中隨意選出的，那么任意特定字串被選中的概率為 $1/{2^{256}}$ ，這是一個小到幾乎可以忽略的取值，