SHAの仕様と実装比較(SHA-256編)

前回、SHA-1の仕様と実装について比較したので、今回はSHA-256について比較してみようと思います。

今回の比較に使用するソースコードは、GitHubにあるopensslのソースコードを
使用しました。その中の、crypto/sha/sha256.cです。

openssl GitHub

念のため、FIPS 180-4のリンクも置いておきます。

FIPS 180-4 2015/08

SHAの共通点やWordの操作については、SHA-1編を参照してください。

SHA-256の仕様と実装の比較

1．ブロックサイズやWordサイズ

SHA-256のブロックサイズは512bits、Wordサイズは32bitsです。
各ブロックは16個の32bitに分けられて処理されます。

2．ハッシュの初期値

FIPS 180-4で記述されているSHA-256の初期値は以下です。

crypto/sha/sha256.cに設定されている値と一致します。

 34 int SHA256_Init(SHA256_CTX *c)
 35 {
 36     memset(c, 0, sizeof(*c));
 37     c->h[0] = 0x6a09e667UL;
 38     c->h[1] = 0xbb67ae85UL;
 39     c->h[2] = 0x3c6ef372UL;
 40     c->h[3] = 0xa54ff53aUL;
 41     c->h[4] = 0x510e527fUL;
 42     c->h[5] = 0x9b05688cUL;
 43     c->h[6] = 0x1f83d9abUL;
 44     c->h[7] = 0x5be0cd19UL;
 45     c->md_len = SHA256_DIGEST_LENGTH;
 46     return 1;
 47 }

3．定数

FIPS 180-4で記述されているSHA-256の定数は以下です。

64個の32bitの定数を使用します。これらはSHA-224でも同じ値を使用するようです。

crypto/sha/sha256.cでも同じ値が設定されています。

134 static const SHA_LONG K256[64] = {
135     0x428a2f98UL, 0x71374491UL, 0xb5c0fbcfUL, 0xe9b5dba5UL,
136     0x3956c25bUL, 0x59f111f1UL, 0x923f82a4UL, 0xab1c5ed5UL,
137     0xd807aa98UL, 0x12835b01UL, 0x243185beUL, 0x550c7dc3UL,
138     0x72be5d74UL, 0x80deb1feUL, 0x9bdc06a7UL, 0xc19bf174UL,
139     0xe49b69c1UL, 0xefbe4786UL, 0x0fc19dc6UL, 0x240ca1ccUL,
140     0x2de92c6fUL, 0x4a7484aaUL, 0x5cb0a9dcUL, 0x76f988daUL,
141     0x983e5152UL, 0xa831c66dUL, 0xb00327c8UL, 0xbf597fc7UL,
142     0xc6e00bf3UL, 0xd5a79147UL, 0x06ca6351UL, 0x14292967UL,
143     0x27b70a85UL, 0x2e1b2138UL, 0x4d2c6dfcUL, 0x53380d13UL,
144     0x650a7354UL, 0x766a0abbUL, 0x81c2c92eUL, 0x92722c85UL,
145     0xa2bfe8a1UL, 0xa81a664bUL, 0xc24b8b70UL, 0xc76c51a3UL,
146     0xd192e819UL, 0xd6990624UL, 0xf40e3585UL, 0x106aa070UL,
147     0x19a4c116UL, 0x1e376c08UL, 0x2748774cUL, 0x34b0bcb5UL,
148     0x391c0cb3UL, 0x4ed8aa4aUL, 0x5b9cca4fUL, 0x682e6ff3UL,
149     0x748f82eeUL, 0x78a5636fUL, 0x84c87814UL, 0x8cc70208UL,
150     0x90befffaUL, 0xa4506cebUL, 0xbef9a3f7UL, 0xc67178f2UL
151 };

4．関数

FIPS 180-4で記述されているSHA-256の関数は以下です。

crypto/sha/sha256.cでは以下のように定義されています。

153 /*
154  * FIPS specification refers to right rotations, while our ROTATE macro
155  * is left one. This is why you might notice that rotation coefficients
156  * differ from those observed in FIPS document by 32-N...
157  */
158 # define Sigma0(x)       (ROTATE((x),30) ^ ROTATE((x),19) ^ ROTATE((x),10))
159 # define Sigma1(x)       (ROTATE((x),26) ^ ROTATE((x),21) ^ ROTATE((x),7))
160 # define sigma0(x)       (ROTATE((x),25) ^ ROTATE((x),14) ^ ((x)>>3))
161 # define sigma1(x)       (ROTATE((x),15) ^ ROTATE((x),13) ^ ((x)>>10))
162
163 # define Ch(x,y,z)       (((x) & (y)) ^ ((~(x)) & (z)))
164 # define Maj(x,y,z)      (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))

ROTATEは、crypto/des/des_locl.hで以下のように定義されています。

 90 # if (defined(OPENSSL_SYS_WIN32) && defined(_MSC_VER))
 91 #  define ROTATE(a,n)     (_lrotr(a,n))
 92 # elif defined(__ICC)
 93 #  define ROTATE(a,n)     (_rotr(a,n))
 94 # elif defined(__GNUC__) && __GNUC__>=2 && !defined(__STRICT_ANSI__) && !defined(OPENSSL_NO_ASM) && !defined(OPEN    SSL_NO_INLINE_ASM) && !defined(PEDANTIC)
 95 #  if defined(__i386) || defined(__i386__) || defined(__x86_64) || defined(__x86_64__)
 96 #   define ROTATE(a,n)   ({ register unsigned int ret;   \
 97                                 asm ("rorl %1,%0"       \
 98                                         : "=r"(ret)     \
 99                                         : "I"(n),"0"(a) \
100                                         : "cc");        \
101                            ret;                         \
102                         })
103 #  endif
104 # endif
105 # ifndef ROTATE
106 #  define ROTATE(a,n)     (((a)>>(n))+((a)<<(32-(n))))
107 # endif

i386やx86_64系ではアセンブリが適用されるみたいですね。
ROTATEで実行する処理は、ROTR^n(X)と同じようです。

よく見るとcrypto/sha/sha256.cでROTATEに渡す引数の数値が、FIPS 180-4で記述されている値と異なりますが、32bitsのWordサイズでは以下が成立するためです。

5．メッセージスケジュールの生成

FIPS 180-4で記述されているSHA-256のメッセージスケジュールの生成方法は以下です。

crypto/sha/sha256.cでは以下のように定義されています。

187         for (i = 0; i < 16; i++) {
188             (void)HOST_c2l(data, l);
189             T1 = X[i] = l;
...(中略)...
202         for (; i < 64; i++) {
203             s0 = X[(i + 1) & 0x0f];
204             s0 = sigma0(s0);
205             s1 = X[(i + 14) & 0x0f];
206             s1 = sigma1(s1);
207
208             T1 = X[i & 0xf] += s0 + s1 + X[(i + 9) & 0xf];

iが16まではそのままの値を使用し、16から64まではSHA-1の代替方法と同じように、0xfとマスクを取った位置にある要素からWtを算出しています。その際、0xfを法として合同な位置にある要素を使用する点には注意が必要です。

6．ハッシュ値の計算

FIPS 180-4に記述されている方法は、以下です。

crypto/sha/sha256.cの該当部分は以下です。

187         for (i = 0; i < 16; i++) {
188             (void)HOST_c2l(data, l);
189             T1 = X[i] = l;
190             T1 += h + Sigma1(e) + Ch(e, f, g) + K256[i];
191             T2 = Sigma0(a) + Maj(a, b, c);
192             h = g;
193             g = f;
194             f = e;
195             e = d + T1;
196             d = c;
197             c = b;
198             b = a;
199             a = T1 + T2;
200         }
201
202         for (; i < 64; i++) {
203             s0 = X[(i + 1) & 0x0f];
204             s0 = sigma0(s0);
205             s1 = X[(i + 14) & 0x0f];
206             s1 = sigma1(s1);
207
208             T1 = X[i & 0xf] += s0 + s1 + X[(i + 9) & 0xf];
209             T1 += h + Sigma1(e) + Ch(e, f, g) + K256[i];
210             T2 = Sigma0(a) + Maj(a, b, c);
211             h = g;
212             g = f;
213             f = e;
214             e = d + T1;
215             d = c;
216             c = b;
217             b = a;
218             a = T1 + T2;
219         }

iが16まで処理と16から64までの処理では、メッセージスケジュールを生成している部分だけが異なりますが、その他は全て同じです。
FIPS 180-4のアルゴリズムがそのままの形で実装されていることが分かります。

変数のdからe、hからaに移る時に値が変っていくイメージです。

最後に32bitの8つの変数の値を並べることで、256bitのメッセージダイジェストが得られます。

以上がSHA-256の仕様とその実装の比較でした。
opensslのSHA-256のソースコードでは、FIPS 180-4の仕様が割とそのまま実装されているという印象を受けました。
次回はSHA-512編です。