Cryptography

Synchronization Link Tree

• Personal Website
• Medium
• LinkedIn
• Github

Intro

Ethereum 的地址是 Public Key 經過 hash 後的 20 bytes，再加上 0x。而為了要確保你真的是 EOA 的持有者，必須有 Public Key 相對應的 Private Key 進行 Sign。進行交易時，Ethereum 會使用 Private Key 驗證你建立的數位簽章（digital signature），是否符合 Public Key 的 Hash（Address）。

這時候我們需要一個演算法來幫助我們建立一個獨一無二的 public/private key pair，這個加密演算法必須容易創造，卻又難以從 Private key 往回推出 Private Key。例如我們用兩個質數 a, b 來得到一個數字 x，那在沒有任何提示的情況下要知道這個數字 x 是多少是非常困難的，即便是電腦都會難以計算出來。

在這裡的 Public Key Cryptography 又被稱為 Asymmetric Encryption（非對稱加密），我們用 Private Key 來 signs message，使用 Public Key 來 verifies 其 signature。簽核之後的 message（可能是一筆交易或任何形式的資料型態）會成為一個數位簽章，在生產的過程中我們常常使用 ECDSA 來做為演算法。也就是把 message 進行 hash 之後，將其與 Private Key 進行 ECDSA 運算。

function recoverPK(bytes32 message, uint8 v, uin32 r, uint32 s) public returns(address){
    return ecrecover(message, v, r, s);
}

Private Key -> Address

接下來我們將上述的簡介更進一步的梳理。

• Source: Ethereum Yellow Paper

解析黃皮書的公式之後我們可以發現從 Private Key 到 Address 主要有三個步驟，依序是：

1. 給定一個隨機產生，長度為 64 Hex Char 的 Private Key
2. 使用 Elliptic Curve Digital Signature Algorithm (ECDSA) 運算將 Private Key 化為 Public Key
3. 使用 Keccak-256 將 Public Key 進行 Hashing，並將結果取「後 40 characters / 20 bytes」，並在前方加上 0x 即可得到最終的 Address（長度為 40 + 2 characters）

主流標準為 SHA3-256，但以太坊使用的是 Keccak256

根據黃皮書，Private Key 的選擇為：A randomly selected positive integer (represented as a byte array of length 32 in big-endian form) in the range [1, secp256k1n − 1]

• EIP-55: Mixed-case checksum address encoding

Keccak256 in Solidity

• Hashing Functions In Solidity Using Keccak256

Public Key Cryptography

暗門函數（Trap-door function）：正向推導容易，反向推回困難

RSA

1. 隨機選擇兩個相異的大質數 p, q 並計算乘積 N。
2. 根據歐拉函數得到小於等於 N 正整數裡面與 N 互質的數目為 r = φ(N) = φ(p) * φ(q) = (p-1)(q-1)
3. 選出一個小於 φ(N) 且與 φ(N) 互質的正整數 e 來作為 Public Key。
4. 求得 d 由 e*d 等價於 1(mod r)，也就是 e 對 r 的模反元素，d 則為 Private Key。

Elliptic Curve Cryptography(ECC)

ECC 可以比 RSA 使用更小的密鑰長度就可以達到相似的安全性，ESDSA 方程式為 y^3 = x^3 + ax + b。

Digital Signatures

• Source: Electronic_signature

將交易/訊息做成 Digital Signature：

1. 有一筆交易稱作 tx_object

{
    from:...
    to:...
    value:...
    data:...
    gas, gasprice, nonce
}

2. tx_object -RLP-> Signing Data
3. Signing Data -Hash-> Signing Hash
4. Signing Hash -Private Key-> Signature (v, r, s)
5. tx_object + Sig -> Signed Tx

那上面的第三步 Signing Data -Hash-> Signing Hash 部分，“hashing algor.” 就是 keccak256("\x19Ethereum Signed Message:\n" + message.length + message) = Signing Hash = messageHash。

而第四步 Signing Hash -Private Key-> Signature (v, r, s) 中的 “Private Key signing algor.” 則為 secp256k1。

第五步的 tx_object + Sig -> Signed Tx 則是把兩個部分串在一起做 RLP：

1. tx_object = nonce, gasPrice, gasLimit, to, value, data
2. Signature = v, r, s

最後串起來做完 RLP 的結果就叫做 Signed Transaction = rawTransaction

Etherscan 上的 Transaction Hash = Signed Transaction = hash(rawTransaction)

Simple Replay Attack

將一個資訊在鏈下使用私鑰簽核之後回到合約中將其 ecrecover 並與儲存的地址比較就可以知道這筆資訊是不是我們從鏈下簽核而來的，這是一個非常重要的技巧！

然而這樣一筆交易可以被重複地播放在鏈上，即便我們當初在鏈下只簽核一次，有心人士依然可以直接 fetchh tx 的資訊並且重播。

• Signature Replay Example

EIP-155: Simple replay attack protection with ECDSA

• EIP-155: Simple replay attack protection

假設一筆交易具有九個元素，tx = (nonce, gasprice, startgas, to, value, data, v = chaindata, r = 0, s = 0)。

1. 若交易資料為：

tx = {nonce = 9, gasprice = 20 * 10**9, startgas = 21000, to = 0x3535353535353535353535353535353535353535, value = 10**18, data=''}

2. 我們將 tx 進行 RLP 可以得到 Signing Data 為：

0xec098504a817c800825208943535353535353535353535353535353535353535880de0b6b3a764000080018080

3. 將上述結果進行 Hash 可以得到 Signing Hash 為：

0xdaf5a779ae972f972197303d7b574746c7ef83eadac0f2791ad23db92e4c8e53

4. 如果我們將這筆交易使用 Private Key 0x4646464646464646464646464646464646464646464646464646464646464646 Sign，並且調整 v 後，可以得到：

(v, r, s) = 
(37, 18515461264373351373200002665853028612451056578545711640558177340181847433846, 46948507304638947509940763649030358759909902576025900602547168820602576006531)

最後的結果 (v, r, s) 便是 Signature。

當簽名算出的 （x, y) = k*G
r = x
當 y 座標是偶數的時候，v = 27; 反之為 28 
那為什麼要這樣設計，試想橢圓曲線上，取同一個 x 座標，會有兩個點，一個 y 一個 -y 

只有在固定 y 下，我們才能夠得到同一個公鑰；不然可能會對到兩個地址，那個 V 就是一個限定是那個座標的用法而已
微補充：
(1) 正負 y 同義於奇偶 y under modulo prime p，因為 p 是奇數，所以負 y 同餘 p-y 同餘偶 y
(2) Bitcoin 直接規定 address 如果是 0x02 開頭就是取偶y，0x03 開頭取奇 y，0x04 開頭則是 x y 並列的未壓縮格式

Recursive Length Prefix(RLP)

RLP 編碼只能作用於 String(i.e. bytes of binary data) 和 List，除了空字串和空串列之外，也可以處理兩者的組合，例如：["cat", ["puppy", "cow"], "horse", [[]], "pig", [""], "sheep"]

RLP encoding 的編碼規則有幾種：

1. 如果「單一個字元（長度為 1 bytes）」的值介於 [0x00, 0x7f] (decimal [0, 127])，則可以直接使用 ASCII 的編碼規則進行轉換。
2. 如果一個「長度低於 55（含） bytes 的字串」，則編碼規則為0x80 + len(str) 再接續每一個字元的 ASCII，
   • 例如長度為三的字串 "dog" = [ 0x83, 'd', 'o', 'g']
3. 如果是「長度大於 55（不含） bytes 的字串」，則編碼規則為 『0xb7(dec. 183) 加上「字串長度以 binary 表達的長度」』，接續「字串長度」，最後接續每個字元的 ASCII
   • 例如一個長度為 1024 byte 的字串，會被 RLP 編碼成 \xb9\x04\x00 (dec. 185, 4, 0) 接續每個字元的 ASCII。
   • 其中 0xb9 (183 + 2 = 185) 是第一個前綴，為字串長度的長度加上 183
   • 第二個前綴為字串實際長度 0x0400 (dec. 1024) 會被切成 \x04\x00。
4. 列表長度低於 56（含）時，編碼規則為將所有元素的 RLP Encoding 接連在一起，將其長度加上 192(dec. 0xc0) 得到前綴，後接續每個字串元素的個別 RLP 編碼，
   • 也就是說為 String 組成的 List 可以依此進行編碼 [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ]
5. 列表長度高於 56（不含）的時候，第一個前綴為「所有元素取 RLP Encoding 接在一起之後的長度的長度（這裡沒打錯）再加上 247(dec. 0xf7)」，第二個前綴為「所有元素取 RLP Encoding 接在一起之後的長度」

RLP decoding 的解碼規則為：

1. 先透過前綴值域判斷資料類型跟長度：
   • [0x00, 0x7f] (decimal [0, 127])：單個字元的 String
   • [0x80, 0xb7] (dec. [128, 183])：長度小於等於 55 的單一 String
   • [0xb8, 0xbf] (dec. [184, 191])：長度大於等於 56 的單一 String
   • [0xc0, 0xf7] (dec. [192, 247])：元素數量小於等於 55 的 List
   • [0xf8, 0xff] (dec. [248, 255])：元素數量大於等於 56 的 List
2. 透過第一個前綴可以判斷接下來幾個元素代表長度
3. 看完長度之後可繼續往後推出哪些是目前字串的字元

• Ethereum Wiki - Recursive-length prefix (RLP)
• Replacing SSZ with RLP, Zip and SHA256

Verify Signature

當我們要驗證一個 Digital Signature 時，則需要使用 Signature 中的 s 來代入 ECDSA 計算，並查看得到的 r 是否合法。

Closing

今天的內容主要落在密碼學的部分，明天會繼續在交易的部分詳述。

Reference

• Bitcoin
• go-ethereum/accounts/key.go
• wizardofozzie/pybitcointools
• Understanding Ethereum Cryptography
• noble-secp256k1
• Understanding How ECDSA Protects Your Data.

最後歡迎大家拍打餵食大學生0x2b83c71A59b926137D3E1f37EF20394d0495d72d