Blockchain

SHA256 を Golang で実装する

By なんぞー 06 October 2018
SHA256 を Golang で実装する

こんにちは、なんぞーです！

今回は、Bitcoin で使われているハッシュ関数の一つである SHA-256 を学ぶために Golang でフルスクラッチで実装してみたいと思います！

あくまでも、仕組みを理解するためのコーディングなので、処理速度などは考慮せずに進めていきたいと思います。
コードについてのご指摘やアドバイスなどは Twitter()にいただけると非常にありがたいです！

SHA-2

SHA-2 とは Secure Hash Algorithm シリーズの暗号学的ハッシュ関数で、SHA-1 の改良版。SHA-2 シリーズは前身である SHA-1 の以下のような問題点を解決するために NSA[1]によって設計され 2001 年に NIST[2]によって FIPS PUB 180-4[3]として標準化されたハッシュ関数である。

  • SHA-1 の問題点
    • 出力が固定長
    • 2005 年に SHA1 に対する効果的な攻撃法が発見
    • 2017 年 2 月に衝突攻撃(高衝突耐性の突破)の成功が現実に示される

SHA-256

SHA-256 とは、SHA-2 シリーズの中でもハッシュ長が 256 ビット(32 バイト)のものを指している。
ビットコインのブロックチェーンでもこの SHA-256 が RIPEMD-160 と共に重要な役割を果たしている。

RIPEMD-160 についても今後記事にするつもりです！
さて、前置きはこのぐらいにしておいて、早速コーディングに移っていきたいと思います！

記号と演算子

今回 SHA-256 を実装していくにあたって、FIPS180-4[3]を参考に進めていくのですが、そこで使われる記号と演算子について軽く説明しておきます。

記号意味
wedge論理積(AND)
oplus排他的論理和(XOR)
lnot否定(NOT)
ll左シフト(x を n ビット左にシフトする)
gg右シフト(x を n ビット右にシフトする)
1
2
3
4
5
6
7
8
9
// ROTR ...
func ROTR(x uint32, n uint) uint32 {
	return (x >> n) | (x << (32 - n))
}
// SHR ...
func SHR(x uint32, n uint) uint32 {
	return x >> n
}

各関数の作成

まずはじめに、hash を計算するにあたって使用する関数を作成していきます！
SHA-256 の計算には以下の 6 つの関数を使用します。

SHA-256 Functions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Ch ...
func Ch(x, y, z uint32) uint32 {
	return (x & y) ^ ((^x) & z)
}
// Maj ...
func Maj(x, y, z uint32) uint32 {
	return (x & y) ^ (x & z) ^ (y & z)
}
// LargeSigma0 ...
func LargeSigma0(x uint32) uint32 {
	return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22)
}
// LargeSigma1 ...
func LargeSigma1(x uint32) uint32 {
	return ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25)
}
// SmallSigma0 ...
func SmallSigma0(x uint32) uint32 {
	return ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3)
}
// SmallSigma1 ...
func SmallSigma1(x uint32) uint32 {
	return ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10)
}

Padding

次にパディングというデータの長さを整える処理をおこなっていきます。

Padding the Message

SHA-256 では、ハッシュ化するメッセージ長が 512 ビット(64 バイト)の倍数になっていなくてはなりません。 したがって足りないデータを補うためにこのパディングという処理を行います。

パディング処理ではあるメッセージ M の長さを l(エル)とし

を満たす k を用いて表された以下の形式のデータを末尾に追加する処理です。
メッセージの後ろにビットの”1”を加え 0 で埋め、残り 64 ビットにメッセージの長さ l(エル)を加えます。

Padding the Message

こちらがそのコードになります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Padding ...
func Padding(message []byte) []byte {
	l := len(message)
	if l%64 < 56 {
		newlen := l % 64
		message = append(message[:], []byte{0x80}...)
		zero := make([]byte, 56-(newlen+1))
		message = append(message[:], zero[:]...)
		ms := make([]byte, 8)
		binary.BigEndian.PutUint64(ms, uint64(l*8))
		message = append(message[:], ms[:]...)
	} else {
		message = append(message[:], []byte{0x80}...)
		newlen := l%64 + 1
		zero := make([]byte, 120-newlen)
		message = append(message[:], zero[:]...)
		bs := make([]byte, 8)
		binary.BigEndian.PutUint64(bs, uint64(l*8))
		message = append(message[:], bs[:]...)
	}
	return message
}

Parse

次に 512 ビットの倍数長に整えられたメッセージブロックを 32 ビット 16 個のかたまりに分割します。

1
2
3
4
5
6
7
8
9
10
// Parse ...
func Parse(message []byte) [][16]uint32 {
	M := make([][16]uint32, len(message)/64)
	for i := 0; i < len(message)/64; i++ {
		for j := 0; j < 16; j++ {
			M[i][j] = uint32(message[64*i+j*4+3]) | uint32(message[64*i+j*4+2])<<8 | uint32(message[64*i+j*4+1])<<16 | uint32(message[64*i+j*4])<<24
		}
	}
	return M
}

初期値の設定

次に、ローテーション処理と呼ばれる心臓部の処理をおこなっていくのですが、ローテーション処理に変化を与えるための材料として、初期値が決められています。

Initial Hash

この一見ランダムなハッシュの初期値ですが、8 つの素数(2,3,5,7,11,13,17,19)の平方根をとり、その小数点以下 32 ビットを初期値としているようです。

ローテーション処理

ようやくハッシュ関数の重要な処理部分にやってまいりました。 ここまでやった内容としては

  • メッセージのパディングおよびパース
  • 初期値を設定した

を行いました。 次に以下の計算式に基づき計算をおこなっていきます。

Lotation Hash

こちらがそのコードになります。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// HashComp ...
func HashComp(M [][16]uint32) string {
	W := [64]uint32{}
	for _, m := range M {
		a := H[0]
		b := H[1]
		c := H[2]
		d := H[3]
		e := H[4]
		f := H[5]
		g := H[6]
		h := H[7]
		for t := 0; t < 64; t++ {
			if 0 <= t && t <= 15 {
				W[t] = m[t]
			} else if 16 <= t && t <= 63 {
				W[t] = SmallSigma1(W[t-2]) + W[t-7] + SmallSigma0(W[t-15]) + W[t-16]
			}
		}
		for t := 0; t < 64; t++ {
			T1 := h + LargeSigma1(e) + Ch(e, f, g) + K[t] + W[t]
			T2 := LargeSigma0(a) + Maj(a, b, c)
			h = g
			g = f
			f = e
			e = d + T1
			d = c
			c = b
			b = a
			a = T1 + T2
		}
		H[0] = a + H[0]
		H[1] = b + H[1]
		H[2] = c + H[2]
		H[3] = d + H[3]
		H[4] = e + H[4]
		H[5] = f + H[5]
		H[6] = g + H[6]
		H[7] = h + H[7]
	}
	var hash string
	for _, s := range H {
		hash += fmt.Sprintf("%x", s)
	}
	return hash
}

Sum 関数

上記の一連の処理をまとめた関数を作成しました。

1
2
3
4
5
func Sum256(data []byte) string {
	padData := Padding(data)
	parsedData := Parse(padData)
	return HashComp(parsedData)
}

出力結果

今回は既存のライブラリである’crypto/sha256’を用いて検証を行いました。

1
2
3
4
5
6
7
8
func main() {
	data := []byte("abc")
	fmt.Printf("SHA-256 : %s\n", Sum256(data)) // "今回実装したコード"
	fmt.Printf("SHA-256 : %x\n", sha256.Sum256(data)) // "crypto/sha256"
}
> SHA-256 : ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
  SHA-256 : ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

まとめ

今回 1 から SHA-256 を実装してみて、ハッシュ関数がどのようにして強衝突耐性を実現しているのかが少し理解できた気がします！
次は RIPEMD-160 の実装に挑戦してみようと思います！

最後まで読んで頂きましてありがとうございました！

コード全体は Github Gist に上がっています！ https://gist.github.com/nandehu0323/ada044a7aa51e7abcc8542c0c1e7111e

Twitter()もやっておりますのでぜひご感想やアドバイスお待ちしております！

参考文献