ハッシュ関数

任意のサイズのデータを入力し、固定サイズの出力を返す関数です。

• 例：ビットごとのXOR

任意長のメッセージを入力し、

固定長のメッセージダイジェスト

を出力する関数$h$です。

暗号学的ハッシュ関数は、次の条件を満たす必要があります。

1. 計算効率
   (Computational Efficiency)
   • 入力$m$が与えられたら、$h(m)$を効率よく計算できる必要があります。
2. 一方向性
   、または
   原像計算困難性
   (One-way or Pre-image Resistance)
   • $y$が与えられたとき、$h(m')=y$を満たす$m'$を見つけることが、計算量的に不可能である必要があります。
3. 第二原像計算困難性
   、または
   弱衝突困難性
   (Second Pre-image Resistance or Weak Collision Resistance)
   • $m$が与えられたとき、$h(m')=h(m)$を満たす$m'$を見つけることが、計算量的に不可能である必要があります。
4. 衝突困難性
   (Collision Resistance)
   • $m, m'$について、$h(m)=h(m')$を満たす$m, m'$を見つけることが、計算量的に不可能である必要があります。

1. 初期化ベクトル (IV: Initialization Vector)
2. メッセージブロック (Message Block)
3. 圧縮関数c (Compression Function)
4. ハッシュ出力 (Hash Output)

1. 初期値
   • $A, B, C, D, E$
2. ラウンド関数
   • $f_t(B, C, D)$は、ラウンド番号$t$に応じて異なる論理演算を行います。
3. ビットの循環シフト
   • $A$と$B$を、それぞれ5ビット、30ビット循環シフトします。
   • ビットを左へ回転させ、最も左のビットは最も右へ移します。
4. 演算と更新
   • 各ラウンドで、$A, B, C, D, E$を、それぞれ$f_t$やほかの演算によって更新します。
   • $A = f_t(B, C, D) + K_t + W_t + E$のような式で更新します。

• $A = ((A << 5) + f_t(B, C, D) + E + K_t + W_t)$
• $B = A$：元の$A$の値を$B$へ保存します。
• $C = B << 30$
• $D = C$
• $E = D$

• $f$はブロックを置換するための関数で、XOR、AND、NOT演算から構成されます。