ハッシュ関数 SHA-256 のGoによる実装

2017-12-28 Go

ビットコインのしくみにも利用されていて，このところ話題になることの多いハッシュ関数SHA-256を、Goで実装してみました。

実行効率は考えずに、NISTの Secure Hash Standard のページにある FIPS PUB 180-4 のファイルの記述に従って、わかりやすさを重視して作成しました。SHA-256のアルゴリズムを理解するのに役に立つと思います。

SHA-256のアルゴリズムは大きく分けて、以下の3つの段階に分かれます。

処理するメッセージ M の後ろに「1」のビットを1つ足して、その後ろに、メッセージの長さが (512の倍数 – 64) ビットになるまで「0」のビットを足す。
その後ろに、元のメッセージ M の長さ（ビット数）の2進数表現を 64ビット足す。（このため、SHA-256で処理するメッセージの長さは 2の64乗未満でなければならない。）
ハッシュ値を計算する。

実際のコードは以下の通りです。

// Package mysha256 implements the SHA256 hash algorithms as defined in FIPS 180-4.
package mysha256

// FIPS 180-4: 4 FUNCTIONS AND CONSTANTS: 4.2 Constants: 4.2.2 SHA-224 and SHA-256 Constants
// sixty-four constant 32-bit words
var K = []uint32{
	0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
	0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
	0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
	0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
	0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
	0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
	0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
	0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
}

// FIPS 180-4: 5. PREPROCESSING: 5.1 Padding the Message: 5.1.1 SHA-1, SHA-224 and SHA-256
func padding(data []byte) []byte {
	len := len(data)
	newlen := len
	if len%64 < 56 {
		newlen += (64 - len%64)
	} else {
		newlen += (64 - len%64) + 64
	}
	newdata := make([]byte, newlen, newlen)
	copy(newdata, data)

	// Suppose that the length of the Message, M, is l bits.
	// Append the bit "1" to the end of the message, followed by k zero bits, where k is the
	// smallest, non-negative solution to the equation l+1+k ≡ 448 mod 512.
	var tmp1 [64]byte
	tmp1[0] = 0x80 // 10000000
	if len%64 < 56 {
		copy(newdata[len:], tmp1[0:56-len%64])
	} else {
		copy(newdata[len:], tmp1[0:64+56-len%64])
	}

	// Then append the 64-bit block that is equal to the number l expressed using a binary
	// representation.
	var tmp2 [8]byte
	nbits := len << 3 // the length of the message M, l bits == (len * 8) == (len << 3)
	for i := uint(0); i < 8; i++ {
		tmp2[i] = byte(nbits >> (56 - 8*i))
	}
	copy(newdata[newlen-8:], tmp2[0:8])

	return newdata
}

// FIPS 180-4: 5. PREPROCESSING: 5.2 Parsing the Message: 5.2.1 SHA-1, SHA-224 and SHA-256
// the message and its padding are parsed into N 512-bit blocks, M[0], M[1], ..., M[N-1].
// Since the 512 bits of the input block may be expressed as sixteen 32-bit words,
// the first 32 bits of message block i are denoted M[i][0], the next 32 bits are M[i][1],
// and so on up to M[i][15].
func parsing(p []byte) [][16]uint32 {
	var M [][16]uint32

	for len(p) >= 64 {
		var w [16]uint32
		for i := 0; i < 16; i++ {
			j := i * 4
			w[i] = uint32(p[j])<<24 | uint32(p[j+1])<<16 | uint32(p[j+2])<<8 | uint32(p[j+3])
		}
		M = append(M, w)
		p = p[64:]
	}

	return M
}

// FIPS 180-4: 4 FUNCTIONS AND CONSTANTS: 4.1 Functions: 4.1.2 SHA-224 and SHA-256 Functions

// Ch(x, y, z)
func Ch(x, y, z uint32) uint32 {
	return (x & y) ^ ((^x) & z)
}

// Maj(x, y, z)
func Maj(x, y, z uint32) uint32 {
	return (x & y) ^ (x & z) ^ (y & z)
}

// The rotate right (circular right shift) operation
func ROTR(x uint32, n uint) uint32 {
	return (x >> n) | (x << (32 - n))
}

// The right shift operation
func SHR(x uint32, n uint) uint32 {
	return x >> n
}

// Σ0
func SIGMA0(x uint32) uint32 {
	return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22)
}

// Σ1
func SIGMA1(x uint32) uint32 {
	return ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25)
}

// σ0
func sigma0(x uint32) uint32 {
	return ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3)
}

// σ1
func sigma1(x uint32) uint32 {
	return ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10)
}

// FIPS 180-4: 6. SECURE HASH ALGORITHMS: 6.2 SHA-256: 6.2.2 SHA-256 Hash Computation
func hashcomp(M [][16]uint32) [32]byte {
	// FIPS 180-4: 5. PREPROCESSING: 5.3 Setting the Initial Hash Value: 5.3.3 SHA-256
	H := [8]uint32{0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A,
		0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19}

	var w [64]uint32
	for _, Mi := range M {
		// Prepare the message schedule, {W_t}
		for t := 0; t <= 15; t++ {
			w[t] = Mi[t]
		}
		for t := 16; t <= 63; t++ {
			w[t] = sigma1(w[t-2]) + w[t-7] + sigma0(w[t-15]) + w[t-16]
		}

		// Initialize the eight working variables, a, b, c, d, e, f, g, and h,
		// with the (i-1)st hash value
		a, b, c, d, e, f, g, h := H[0], H[1], H[2], H[3], H[4], H[5], H[6], H[7]

		for t := 0; t <= 63; t++ {
			t1 := h + SIGMA1(e) + Ch(e, f, g) + K[t] + w[t]
			t2 := SIGMA0(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[1] += b
		H[2] += c
		H[3] += d
		H[4] += e
		H[5] += f
		H[6] += g
		H[7] += h
	}

	var digest [32]byte
	for i, s := range H {
		digest[i*4] = byte(s >> 24)
		digest[i*4+1] = byte(s >> 16)
		digest[i*4+2] = byte(s >> 8)
		digest[i*4+3] = byte(s)
	}

	return digest
}

// Sum256 returns the SHA256 checksum of the data.
func Sum256(data []byte) [32]byte {
	// FIPS 180-4: 5. PREPROCESSING: 5.1 Padding the Message: 5.1.1 SHA-1, SHA-224 and SHA-256
	data = padding(data)

	// FIPS 180-4: 5. PREPROCESSING: 5.2 Parsing the Message: 5.2.1 SHA-1, SHA-224 and SHA-256
	M := parsing(data)

	// FIPS 180-4: 6. SECURE HASH ALGORITHMS: 6.2 SHA-256: 6.2.2 SHA-256 Hash Computation
	return hashcomp(M)
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

// Package mysha256 implements the SHA256 hash algorithms as defined in FIPS 180-4.

package mysha256

// FIPS 180-4: 4 FUNCTIONS AND CONSTANTS: 4.2 Constants: 4.2.2 SHA-224 and SHA-256 Constants

// sixty-four constant 32-bit words

var K = []uint32{

0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,

0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,

0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,

0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,

0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,

0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,

0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,

0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,

}

// FIPS 180-4: 5. PREPROCESSING: 5.1 Padding the Message: 5.1.1 SHA-1, SHA-224 and SHA-256

func padding(data []byte) []byte {

len := len(data)

newlen := len

if len%64 < 56 {

newlen += (64 - len%64)

} else {

newlen += (64 - len%64) + 64

}

newdata := make([]byte, newlen, newlen)

copy(newdata, data)

// Suppose that the length of the Message, M, is l bits.

// Append the bit "1" to the end of the message, followed by k zero bits, where k is the

// smallest, non-negative solution to the equation l+1+k ≡ 448 mod 512.

var tmp1 [64]byte

tmp1[0] = 0x80 // 10000000

if len%64 < 56 {

copy(newdata[len:], tmp1[0:56-len%64])

} else {

copy(newdata[len:], tmp1[0:64+56-len%64])

}

// Then append the 64-bit block that is equal to the number l expressed using a binary

// representation.

var tmp2 [8]byte

nbits := len << 3 // the length of the message M, l bits == (len * 8) == (len << 3)

for i := uint(0); i < 8; i++ {

tmp2[i] = byte(nbits >> (56 - 8*i))

}

copy(newdata[newlen-8:], tmp2[0:8])

return newdata

}

// FIPS 180-4: 5. PREPROCESSING: 5.2 Parsing the Message: 5.2.1 SHA-1, SHA-224 and SHA-256

// the message and its padding are parsed into N 512-bit blocks, M[0], M[1], ..., M[N-1].

// Since the 512 bits of the input block may be expressed as sixteen 32-bit words,

// the first 32 bits of message block i are denoted M[i][0], the next 32 bits are M[i][1],

// and so on up to M[i][15].

func parsing(p []byte) [][16]uint32 {

var M [][16]uint32

for len(p) >= 64 {

var w [16]uint32

for i := 0; i < 16; i++ {

j := i * 4

w[i] = uint32(p[j])<<24 | uint32(p[j+1])<<16 | uint32(p[j+2])<<8 | uint32(p[j+3])

}

M = append(M, w)

p = p[64:]

}

return M

}

// FIPS 180-4: 4 FUNCTIONS AND CONSTANTS: 4.1 Functions: 4.1.2 SHA-224 and SHA-256 Functions

// Ch(x, y, z)

func Ch(x, y, z uint32) uint32 {

return (x & y) ^ ((^x) & z)

}

// Maj(x, y, z)

func Maj(x, y, z uint32) uint32 {

return (x & y) ^ (x & z) ^ (y & z)

}

// The rotate right (circular right shift) operation

func ROTR(x uint32, n uint) uint32 {

return (x >> n) | (x << (32 - n))

}

// The right shift operation

func SHR(x uint32, n uint) uint32 {

return x >> n

}

// Σ0

func SIGMA0(x uint32) uint32 {

return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22)

}

// Σ1

func SIGMA1(x uint32) uint32 {

return ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25)

}

// σ0

func sigma0(x uint32) uint32 {

return ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3)

}

// σ1

func sigma1(x uint32) uint32 {

return ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10)

}

// FIPS 180-4: 6. SECURE HASH ALGORITHMS: 6.2 SHA-256: 6.2.2 SHA-256 Hash Computation

func hashcomp(M [][16]uint32) [32]byte {

// FIPS 180-4: 5. PREPROCESSING: 5.3 Setting the Initial Hash Value: 5.3.3 SHA-256

H := [8]uint32{0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A,

0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19}

var w [64]uint32

for _, Mi := range M {

// Prepare the message schedule, {W_t}

for t := 0; t <= 15; t++ {

w[t] = Mi[t]

}

for t := 16; t <= 63; t++ {

w[t] = sigma1(w[t-2]) + w[t-7] + sigma0(w[t-15]) + w[t-16]

}

// Initialize the eight working variables, a, b, c, d, e, f, g, and h,

// with the (i-1)st hash value

a, b, c, d, e, f, g, h := H[0], H[1], H[2], H[3], H[4], H[5], H[6], H[7]

for t := 0; t <= 63; t++ {

t1 := h + SIGMA1(e) + Ch(e, f, g) + K[t] + w[t]

t2 := SIGMA0(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[1] += b

H[2] += c

H[3] += d

H[4] += e

H[5] += f

H[6] += g

H[7] += h

}

var digest [32]byte

for i, s := range H {

digest[i*4] = byte(s >> 24)

digest[i*4+1] = byte(s >> 16)

digest[i*4+2] = byte(s >> 8)

digest[i*4+3] = byte(s)

}

return digest

}

// Sum256 returns the SHA256 checksum of the data.

func Sum256(data []byte) [32]byte {

// FIPS 180-4: 5. PREPROCESSING: 5.1 Padding the Message: 5.1.1 SHA-1, SHA-224 and SHA-256

data = padding(data)

// FIPS 180-4: 5. PREPROCESSING: 5.2 Parsing the Message: 5.2.1 SHA-1, SHA-224 and SHA-256

M := parsing(data)

// FIPS 180-4: 6. SECURE HASH ALGORITHMS: 6.2 SHA-256: 6.2.2 SHA-256 Hash Computation

return hashcomp(M)

}

この作成したパッケージの名前を「mysha256」とすると、以下のように使うことができます。

package main

import (
	"crypto/sha256"
	"fmt"
	"mysha256"
)

func main() {
	s := "hello"

	sum1 := mysha256.Sum256([]byte(s))
	fmt.Printf("%x\n", sum1)

	sum2 := sha256.Sum256([]byte(s))
	fmt.Printf("%x\n", sum2)
}

package main

import (

"crypto/sha256"

"fmt"

"mysha256"

)

func main() {

s := "hello"

sum1 := mysha256.Sum256([]byte(s))

fmt.Printf("%x\n", sum1)

sum2 := sha256.Sum256([]byte(s))

fmt.Printf("%x\n", sum2)

}

標準ライブラリに含まれるSHA-256の実装である「crypto/sha256」も、比較のために入れてあります。

実行効率を考えたSHA-256の実装については、Goに含まれる「crypto/sha256」のコードを参照してください。(Goの配置されたディレクトリ以下の「src/crypto/sha256」にある「sha256.go」と「sha256block.go」のファイルに含まれています。)

参考文献

「プログラミング言語Go」 Alan A.A. Donovan (著),‎ Brian W. Kernighan (著),‎ 柴田芳樹 (翻訳)