ハッシュ関数 SHA-256 のGoによる実装
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乗未満でなければならない。)
- ハッシュ値を計算する。
実際のコードは以下の通りです。
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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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」とすると、以下のように使うことができます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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 (著), 柴田 芳樹 (翻訳)