Simple insights into SHA-256

quoted from https://blog.csdn.net/u011583927/article/details/80905740

A) Cryptographic hash function:

(1) 對於任一給定訊息, 都很容易運算出雜湊數值.
(2) 難以由一已知的雜湊數值, 推算出原始訊息.
(3) 修改訊息內容, 必會變更雜湊數值.
(4) 訊息不同, 則雜湊數值不同.

B) SHA-2 (Secure Hash Algorithm 2): SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256.

C) SHA-256 digest:

message => SHA-256 => digest,

digest: 256 bit = 32 Byte = 64個16進位字元 (1 Byte = 2^8 = 16^2 = 2個16進位字元)

e.g. 1744E7ADA5ACECB07674C10617C2634F151B0FEE64BE20D87DF49C0425DBCEF3

D) 8個Hash初始值:

取自然數中前8個質數 (prime number, 2, 3, 5, 7, 11, 13, 17, 19),
其平方根的小數部分, 乘2^32 (4,294,967,296).

取Hex:
h0: 0x6a09e667
h1: 0xbb67ae85
h2: 0x3c6ef372
h3: 0xa54ff53a
h4: 0x510e527f
h5: 0x9b05688c
h6: 0x1f83d9ab
h7: 0x5be0cd19
(共8*8=64個16進位字元).

e.g. √2 = 1.41421356237309504880168872420969,

0.41421356237309504880168872420969 * 2^32 = 1779033703.9520993849027770600526 = (6A09E667)16

E) 64個常量:

取自然數中前64個質數 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97…),
其立方根的小數部分, 乘2^32.

取Hex:
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

e.g. 2^(1/3) = 1.2599210498948731647672106072782,

0.2599210498948731647672106072782 * 2^32 = 1116352408.8404644807431890114042 = (428A2F98)16

F) Pre-processing:

F.1) 文末附加補位:

於文末補位, 至少補1位, 最多補512位, 補的第1位補"1″, 其後位都補"0″, 使長度 ≡ 448 (mod 512).

e.g. “abc":
a, b, c =>
ASCII: 97, 98, 99,
Binary 2進位: 01100001 01100010 01100011,
補的第1位補"1″: 01100001 01100010 01100011 1,
其後位都補"0″, 使長度 ≡ 448 (mod 512), 則補 448-25=423 個"0″:
01100001 01100010 01100011 10000000 00000000 … 00000000 (共56組).

2^448 = 2^(56*8) = 2^4^(14*8) = 16^(14*8)

補位完成若以16進位表示:
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 (共14組).

F.2) 附加長度資訊:

文末附加長度大小的資訊.

e.g. “abc":
Binary 2進位: 01100001 01100010 01100011, 長度 8*3 = 24 = (18)16

附加完成若以16進位表示:
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000018

G) 邏輯符號:

∧: 與; 若A與B二者都為真, 則陳述 A∧B 為真; 否則為假.

¬: 非; 陳述 ¬A為真, 若且唯若 A為假 (¬A為真是 A為假的充要條件). ˜ A 意思相同. ¬(¬A) ⇔ A.

⊕: xor; 陳述 A⊕B 為真, 在要麼A要麼B 但不是二者為真的時候為真. A⊻B 意思相同. (¬A)⊕A 總是真, A⊕A 總是假.

Sn: 右移n個bit.

Rn: 循環右移n個bit.

H) 邏輯函數:

Ch(x, y, z) = (x ∧ y) ⊕ (¬x ∧ z)

Ma(x, y, z) = (x ∧ y) ⊕ (x ∧ z) ⊕ (y ∧ z)

Σ0(x) = S2(x) ⊕ S13(x) ⊕ S22(x)

Σ1(x) = S6(x) ⊕ S11(x) ⊕ S25(x)

σ0(x) = S7(x) ⊕ S18(x) ⊕ R3(x)

σ1(x) = S17(x) ⊕ S19(x) ⊕ R10(x)

I) 計算訊息摘要(digest):

I.1) 分解訊息(break message)為 n 個 512 bit 大小的塊(chunk),

I.2) 令H0為前述的8個Hash初始值 (h0, h1… h7 共 8*8個16進位字元 = 256 bit)

I.3) 執行n次疊代, 以下為疊代內的演算:

I.3.1) 512 bit per chunk, 於疊代中, 分解單一 chunk 為 16個 32 bit 的 big-endian 的字(word) (32*16=512):
w[0], w[1], w[2], … w[15],

I.3.2) 建構 w[16]~w[63]:

W[t] = σ1(W[t−2]) + W[t−7] + σ0(W[t−15]) + W[t−16]

I.3.3) 執行64次迴圈, 以完成1次疊代, 以下為迴圈內的演算:

02.1

圖中, ABCDEFGH 此8個word依一定的規則進行更新,
其中深藍色方塊為前述之非線性邏輯函數,
紅色田字方塊為 mod 2^32 addition (二數相加, 若和大於2^32 則除以2^32 取餘數),
ABCDEFGH 初始值分別為 H[i−1](0), H[i−1](1), … H[i−1](7),
Kt為第t個金鑰, 對應前述之64個常量,
Wt為此chunk產生第t個word.

原訊息被分為固定長度 512 bit 之chunk, 對每一chunk, 再分為64個word,

通過重複疊代n次對 ABCDEFGH 這8個word迴圈加密.

最後一次迴圈所產生的8個word合起來即為第i個chunk對應到的hash字串H[i].

I.4) H[0]經第一次運算後得H[1], H[1]經第二次運算後得H[2] ….. 依以類推, 經n次疊代後得H[n] 為最終的雜湊值 (即長度 256 bit 之 digest).

J) 虛擬碼(pseudocode):


//Pre-processing:
append the bit '1' to the message; 
append k bits '0', where k is the minimum number &gt;= 0 such that the resulting message length (in bits) is congruent to 448(mod 512); 
append length of message (before pre-processing), in bits, as 64-bit big-endian integer; 

//Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
{
  break chunk into sixteen 32-bit big-endian words w[0..15]

  //Extend the sixteen 32-bit words into sixty-four 32-bit words:
  for i from 16 to 63
  {
    s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor(w[i-15] rightshift 3);
    s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor(w[i-2] rightshift 10);
    w[i] := w[i-16] + s0 + w[i-7] + s1;
  }

  //Initialize hash value for this chunk:
  a := h0;
  b := h1;
  c := h2;
  d := h3;
  e := h4;
  f := h5;
  g := h6;
  h := h7;

  //Main loop:
  for i from 0 to 63
  {
    s0 := (a rightrotate 2) xor (a rightrotate 13) xor(a rightrotate 22);
    maj := (a and b) xor (a and c) xor (b and c);
    t2 := s0 + maj;
    s1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25);
    ch := (e and f) xor ((not e) and g);
    t1 := h + s1 + ch + k[i] + w[i];
    h := g;
    g := f;
    f := e;
    e := d + t1;
    d := c;
    c := b;
    b := a;
    a := t1 + t2;
  }

  //Add this chunk's hash to result so far:
  h0 := h0 + a;
  h1 := h1 + b;
  h2 := h2 + c;
  h3 := h3 + d;
  h4 := h4 + e;
  h5 := h5 + f;
  h6 := h6 + g;
  h7 := h7 + h;
}

//Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7;

Reference:

(1) SHA256演算法原理詳解 https://blog.csdn.net/u011583927/article/details/80905740
(2) SHA-2 https://zh.wikipedia.org/wiki/SHA-2
(3) 雪崩效應 https://zh.wikipedia.org/wiki/%E9%9B%AA%E5%B4%A9%E6%95%88%E5%BA%94
(4) 非線性系統 https://zh.wikipedia.org/wiki/%E9%9D%9E%E7%B7%9A%E6%80%A7%E7%B3%BB%E7%B5%B1
(5) 密碼雜湊函式 https://zh.wikipedia.org/wiki/%E5%AF%86%E7%A2%BC%E9%9B%9C%E6%B9%8A%E5%87%BD%E6%95%B8
(6) 第四章雜湊與亂數演算法 http://www.tsnien.idv.tw/Security_WebBook/%E7%AC%AC%E5%9B%9B%E7%AB%A0%20%E9%9B%9C%E6%B9%8A%E8%88%87%E4%BA%82%E6%95%B8%E6%BC%94%E7%AE%97%E6%B3%95.html
(7) 八、十與十六進位 (數字系統) 轉換教學 https://footmark.info/introduction-to-computer/digital-system-conversion
(8) Decimal to Hexadecimal Converter https://www.binaryhexconverter.com/decimal-to-hex-converter
(9) ASCII Table https://www.rapidtables.com/code/text/ascii-table.html
(10) log calculator http://logbase2.blogspot.com/2008/08/log-calculator.html
(11) 邏輯符號表 https://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E7%AC%A6%E5%8F%B7%E8%A1%A8
(12) 數學符號的意義與念法 http://ccckmit.wikidot.com/ma:symbol

Tsung

Simple insights into SHA-256

發表留言取消回覆

分享此文：

相關

發表留言 取消回覆

發表留言取消回覆