こんにちは、エンジニアインターンの南条です！

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

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

SHA-2
SHA-256
記号と演算子
各関数の作成
Padding
Parse
初期値の設定
ローテーション処理
Sum関数
出力結果
まとめ
Tip us!
参考文献

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)
x $ll$ n	左シフト(xをnビット左にシフトする)
x $gg$ n	右シフト(xをnビット右にシフトする)

// 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つの関数を使用します。

// 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

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

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

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

を満たすkを用いて表された以下の形式のデータを末尾に追加する処理です。

メッセージの後ろにビットの”1”を加え0で埋め、残り64ビットにメッセージの長さl(エル)を加えます。

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

// 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個のかたまりに分割します。

// 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
}

初期値の設定

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

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

ローテーション処理

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

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

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

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

// 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関数

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

func Sum256(data []byte) string {
	padData := Padding(data)
	parsedData := Parse(padData)
	return HashComp(parsedData)
}

出力結果

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

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(@nandehu0323)もやっておりますのでぜひご感想やアドバイスお待ちしております！

Tip us!

エンジニアチームのブログを書くモチベーションが上がります 💪

address — 0xd6d478dCe4585a394834690158cf83581223C08f

SHA256をGolangで実装する

Contents

SHA-2

SHA-256

記号と演算子

各関数の作成

SHA-256 Functions

Padding

Padding the Message

Padding the Message

Parse

初期値の設定

Initial Hash

ローテーション処理

Lotation Hash

Sum関数

出力結果

まとめ

Tip us!

0xd6d478dCe4585a394834690158cf83581223C08f

参考文献