SHA256 - killelder/cryptocurrency GitHub Wiki

(更新至2018/10/04 已更新完畢, 不再更新)
SHA256 wiki

在了解算法以前先看一下SHA256的一些特性
SHA256的input需要小於2^64-1 bits ~= 2091752 TB
SHA256的output固定式256 bits

由於input >> output, 從代數空間來看, 鐵定是會發生碰撞(collision)的,

那為什麼還可以認為SHA256是安全的呢?
網路上找到的資料是Why haven't any SHA-256 collisions been found yet?
Descriptions of SHA256

因為假設以現在bitcoin擁有的算力來當作指標,
現在有的算力是4 * 10^17 hashes/s,
假設需要計算2^128次可以找到碰撞,
那麼也要花上13.7*10^9年,
對我們的lifetime來說也是一個天文數字了
加上考慮生日攻擊的話, 可能也要將近1000年才會發生碰撞

SHA256無法反推
SHA256是採用非線性運算迭代產生出來的結果,
這些操作包括了 XOR, AND, OR, INVERSE, mod(2^32 addition), right shift, right rotation
目前還沒人找出破解的方法, 也還沒有發現碰撞

SHA256實作
參考SHA-256 Cryptographic Hash Algorithm
首先SHA256不能算是加密函數, 因為他是單向的不能被解密,
然後hash function不適合拿來儲存密碼, 因為他被設計來是為了快速驗證,
會成為暴力攻擊的目標,
因為計算hash對攻擊者的硬件來說太簡單了,

計算SHA256預處理

  1. 先把message轉換成bits

M = 01100001 01100010 01100011

  1. 最後面補1 bit 1

M' = 01100001 01100010 01100011 1

  1. 然後M'後面補0讓mod(M'', 512) == 448

M'' = 01100001 01100010 01100011 1 0.....0

  1. 在M''最後面補上原先M的bit length (原先24 bits)

M''' = 01100001 01100010 01100011 1 0.....0 0...11000

  1. 把M'''每512 bits切成一個塊
    M''' ==> M1, M2, ... Mn

  2. 然後每一個512 bits區塊, 再細分成每32bits一個區塊, 所以會分出16個
    M1 ==> M1_0, M1_1, ... M1_15
    M2 ==> M2_0, M2_1, ... M2_15
    .
    .
    MN ==> MN_0, MN_1, ... MN_15

哈希初值, 哈希常數

h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

哈希初值, 是在第一個iteration會用到的, 這些初值是由自然數中前8個質數(2,3,5,7,11,13,17,19)的平方根小數部分取前32bits

K = [
428a2f98 71374491 b5c0fbcf e9b5dba5
3956c25b 59f111f1 923f82a4 ab1c5ed5
d807aa98 12835b01 243185be 550c7dc3
72be5d74 80deb1fe 9bdc06a7 c19bf174
e49b69c1 efbe4786 0fc19dc6 240ca1cc
2de92c6f 4a7484aa 5cb0a9dc 76f988da
983e5152 a831c66d b00327c8 bf597fc7
c6e00bf3 d5a79147 06ca6351 14292967
27b70a85 2e1b2138 4d2c6dfc 53380d13
650a7354 766a0abb 81c2c92e 92722c85
a2bfe8a1 a81a664b c24b8b70 c76c51a3
d192e819 d6990624 f40e3585 106aa070
19a4c116 1e376c08 2748774c 34b0bcb5
391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3
748f82ee 78a5636f 84c87814 8cc70208
90befffa a4506ceb bef9a3f7 c67178f2
]

哈希常數, 這些常數是由自然數中前64個質數的立方根小數部分取前32bits

Operation

SHA256會用到的幾個bitwise operation,
XOR, AND, OR, +, Rn, Sn
其中特別介紹一下
+ : mod(2^32) addition, 因為所有的都在32bits內做處理, 所以超過2^32次方就不考慮
Rn : Right shift by n bits
Sn : Right rotation by n bits

Main loop

我發現用python實作的時候, operation不是最難的, 而是2進位, 字串, 10進位, 16進位的轉換才是比較煩人的
Main loop可以直接參考paper裡面的pseudo code
建議可以參照paper裡面的例子,
因為裡面有每一個步驟的a,b,c,d,e,f,g,h值,
比較方便debug

python程式碼會上傳到git上面

Appendix - Hash的碰撞機率

Hash Collision Probabilities
這篇很重要, 可以幫你估計Hash 碰撞的機率