ダイジェストアルゴリズム
ダイジェストアルゴリズム (ハッシュ関数)には,入力データの変換処理にブロック暗号を用いる方法と換字と置換を繰り返す専用のアルゴリズムを用いる方法とがある.前者の方法は ISO
で標準化されているが,ブロック暗号として何を用いるかは規定されていない.後者の代表的なハッシュ関数には,以下に概要を示す SHA がある (ハッシュ関数の種類). SHA は,米国の標準技術研究所 (NIST)によって政府標準のハッシュ関数
Secure Hash Standard (SHS) として採用されているものである.
SHA には,生成するビット長が異なる SHA-1 (160ビット),SHA-224,SHA-256,SHA-384,SHA-512 の 5種類がある.このうち SHA-224 以外は 2002年8月の FIPS Publication 180-2の初版に含まれている.SHA-224 は 2004年2月に同規格で追加されている.SHA-224,SHA-256,SHA-384,SHA-512 は,まとめて SHA-2 と言われている.
SHA-1 は,以前から広範囲に使われていたハッシュ関数である MD5 に代わるものとして現在も広く使われているが,SHA-1 に対する攻撃(ハッシュ値の強衝突耐性突破)が見つかっていることから,現在では SHA-2
への移行が推奨されている.
また,ハッシュ関数に対する攻撃の進展に対応するため,SHA-2 の次の世代のハッシュ関数アルゴリズムが 2007年より NIST により公募され,2012年10月 SHA-3 として選定された (SHA-3 アルゴリズム).但し,SHA-2 を置き換える位置付けではなく,補完的,バックアップ的位置付けである.すなわち,当面 SHA-2 でも問題がないという判断である.
SHA-1
- SHA-1とは
SHA-1 は,NIST(National Institute of Standards and Technology)によって提案されたハッシュ関数である(FIPS180-2). SHA-1 は各メッセージブロックに対し,4 ラウンド 80 ステップの演算を行い,160 ビットのハッシュ値を出力する.標準ハッシュ関数として現在まで広く使われてきている.
- SHA-1 仕様
任意長のメッセージを入力し,160 ビットのハッシュ値を出力する.入力されたデータは 512 ビットのブロックとして処理される.処理の流れは次の 5 つのステップからなる.
- パディングビットの付加
入力メッセージは,そのビット長が $448 \bmod 512$ ビットとなるように加工する.このとき $448 \bmod 512$ の長さを満たしていたとしても,付加ビットは必ず付けられる.パディングビットは、先頭が“1”で必要な数だけ“0”という形であり,メッセージビットの直後に付加される.
- 長さ情報の付加
パディングされる前の元の入力メッセージのビット長の $\bmod 264$ をパディングビットの後に 64 ビットの長さで付加する.ここまでで,元のメッセージは 512 ビットの倍数のビット長に変換されている.拡大されたメッセージは,512 ビットの $L$ 個のブロック系列 $Y_0$, $Y_1$, $Y_2$, $\ldots$ $Y_{L-1}$ のように表現でき,合計ビット長は $512 \times L$ ビットとなる.
- バッファの初期化
ハッシュ値を保存するバッファ(連鎖変数)を 5 個の 32 ビットレジスタを使って(A, B, C, D, E)と表現する.この 160 ビットのバッファは,ハッシュ値の中間値を保存して圧縮関数の入力として利用されたり,最終結果を格納する.最初の圧縮関数に入る前に,これらのレジスタに次の値が格納される.
- A = 0x67452301
- B = 0xEFCDAB89
- C = 0x98BADCFE
- D = 0x10345476
- E = 0xC3D2E1F0
- 圧縮処理
SHA-1 のメイン処理は,20 ステップを 1 ラウンドとした 4 ラウンドからなる圧縮関数である.この 4 ラウンドはそれぞれ同様の構造をしているが,各々 $f_1$, $f_2$, $f_3$, $f_4$ という異なる論理演算関数を使って圧縮を行う.各ラウンドは現在処理している 512 ビットブロック $Y_q$ と160 ビットバッファの値を入力とし,各ラウンドの出力値で 160 ビットバッファ ABCDE の値を更新していく.4 ラウンド目(80 ステップ目)の出力は,その圧縮関数の 1 ラウンド目の入力 ($CV_q$) と加算され $CV_{q+1}$ となり,次の圧縮関数で利用される.この加算は 5 つのバッファで独立な $\bmod 2^{32} $ で加算される.
- メッセージダイジェストの出力
$L$ 個の 512 ビット長ブロックを圧縮関数ですべて処理した後,160 ビットバッファ内にあるハッシュ値を出力する.
- SHA-1 演算関数 (圧縮処理)
\begin{eqnarray}
f_t (x, y, z)
=
\begin{cases}
Ch(x, y, z) = (x \land y) \oplus (\lnot x \land z) & (0 \le t \le 19) \\
Parity(x, y, z) = x \oplus y \oplus z & (20 \le t \le 39) \\
Maj(x, y, z) = (x \land y) \oplus (x \land z) \oplus (y \land z) & (40 \le t \le 59) \\
Parity(x, y, z) = x \oplus y \oplus z & (60 \le t \le 79)
\end{cases}
\end{eqnarray}
- SHA-1 データ例
SHA-1 のハッシュ値の例として,3 つの ASCII文字列に対するハッシュ値を示す.
- ASCII文字列 “abc”
a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d
- ASCII文字列 "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq“
84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1
- ASCII文字列 1,000,000個の“a”
34aa973c d4c4daa4 f61eeb2b dbad2731 6534016f
SHA-2
SHA-2 は.SHA-224,SHA-256,SHA-384,SHA-512 の総称であり.ハッシュ長は順に 224 ビット,256 ビット,384 ビット,512 ビットである.
これらのハッシュ関数は,ハッシュ長の違いよりむしろ利用環境でのCPU基本演算系の違いを意識したものである.32 ビット演算系での利用を前提とする場合には SHA-224 と SHA-256 を,64 ビット演算での利用を前提とする場合には SHA-384 と SHA-512 を使うことが想定されている(SHA-256は 32 ビット単位の処理,SHA-512 は 64 ビット単位の処理). SHA-224 と SHA-384 は,それぞれ SHA-256 または SHA-512 と同様の演算をした後に,それらのハッシュ値の一部(下位 32 ビットまたは 128 ビット)を切り捨てる形でハッシュ長を短くしている.そのため,処理性能的には SHA-224 と SHA-256,SHA-384 と SHA-512 はそれぞれ同等である.
NIST は 2012年3月に FIPS PUB 180-4 において,SHA-2ファミリーとして SHA-512/224 と SHA-512/256 を追加している.これらは,SHA-2ファミリーの1つである
SHA-384 と同じ考え方により作られたアルゴリズムで,SHA-512 をベースに計算したのちハッシュ長としてそれぞれ
224 ビット,256 ビットに切り出すハッシュ関数である.64 ビットCPUで高速に演算できるように作られている SHA-512 を使って 224 ビットや 256 ビットのハッシュ関数を新たに作るアルゴリズムであり,主流となりつつある 64 ビットCPU向けに SHA-2ファミリーの環境を拡充したものと言える.