Chapter 18
ハッシュ関数・MAC・デジタル署名
暗号は「秘密を守る」だけの技術ではない. むしろ実務では、「これは改ざんされていないか」「本当にこの人が書いたのか」を 保証する場面のほうが多い。パスワード保管、ソフトウェア更新、電子契約、ブロックチェーン—— どれも秘密より完全性と認証が主題である。
09 章で「CRC は改ざん検知に使えない」、14 章で「暗号化だけでは改ざんを防げない」と述べた。 その宿題をここで回収する。
1. 暗号学的ハッシュ関数
定義と要件
任意長の入力から固定長の出力（ダイジェスト）を作る関数\(H\)。次の 3 性質が要求される:
| 性質 | 内容 | 破られると |
|---|---|---|
| 原像計算困難性 | \(h\)から\(H(m)=h\)なる\(m\)を見つけられない | パスワードが逆算される |
| 第 2 原像計算困難性 | \(m_1\)から\(H(m_1)=H(m_2)\)なる別の\(m_2\)を見つけられない | 文書のすり替え |
| 衝突困難性 | \(H(m_1)=H(m_2)\)なる任意の対を見つけられない | 偽造証明書 |
誕生日攻撃 — なぜ出力長が 2 倍必要か
\(n\)ビット出力のハッシュで:
- 原像を見つけるには\(2^n\)回
- 衝突を見つけるには\(2^{n/2}\)回だけ
導出: \(k\)個のランダムな値の中に衝突が含まれない確率は
これが\(1/2\)になるのは\(k \approx 1.18\sqrt{2^n} = O(2^{n/2})\) ∎
「同じ誕生日の人が 2 人いる確率は、23 人で 50% を超える」という有名なパラドックスと同じ計算. 365 日あるのに 23 人で十分なのは、比べるペアの数が\(\binom{23}{2}=253\)通りもあるから。
帰結: 128 ビット安全性が欲しければ、ハッシュは 256 ビット必要。 SHA-256 が標準的に使われるのはこのためである。
主なハッシュ関数
| 名前 | 出力 | 構造 | 状態 |
|---|---|---|---|
| MD5 | 128 | Merkle-Damgård | 破綻（衝突が数秒で作れる） |
| SHA-1 | 160 | Merkle-Damgård | 破綻（2017 年 SHAttered、2020 年選択接頭辞衝突） |
| SHA-256/512 | 256/512 | Merkle-Damgård | 現役標準 |
| SHA-3 | 可変 | スポンジ構造 | 標準（2015） |
| BLAKE2/3 | 可変 | HAIFA / Merkle 木 | 高速、広く使われる |
SHA-1 の破綻がもたらしたもの. 2017 年、Google と CWI が同じ SHA-1 ハッシュを持つ 2 つの異なる PDF を公開した（SHAttered）。 計算量は\(2^{63.1}\)——理論値\(2^{80}\)より大幅に少なかった。
これにより Git（オブジェクト ID に SHA-1 を使用）や証明書業界が対応を迫られた。 「まだ実際には破られていない」は「安全」を意味しないという教訓である。
Merkle-Damgård 構造と長さ拡張攻撃
MD5/SHA-1/SHA-256 は、入力をブロックに分けて圧縮関数を繰り返し適用する:
この構造には弱点がある——長さ拡張攻撃. \(H(m)\)と\(|m|\)を知っていれば、\(m\)の内容を知らなくても\(H(m \| \text{pad} \| m')\)が計算できる。 最終ハッシュ値がそのまま内部状態だからである。
これが単純な MAC を壊す: \(\mathrm{MAC} = H(K \| m)\)という素朴な構成は、 攻撃者が\(m\)を延長した上で正しい MAC を作れてしまう。 だから次節の HMAC という入れ子構造が必要になる。
なお SHA-3 のスポンジ構造にはこの弱点が無い。
2. MAC（メッセージ認証コード）
目的
共有鍵を持つ 2 者間で、「このメッセージは改ざんされていない」ことを保証する。
鍵を知らない者は正しい\(t\)を作れない。
HMAC
（\(\mathrm{ipad} = \texttt{0x36}\)の繰り返し、\(\mathrm{opad}=\texttt{0x5C}\)の繰り返し。）
なぜ 2 重にするのか: 内側のハッシュ結果を、さらに鍵付きでハッシュし直すことで、 長さ拡張攻撃を無効化する（外側の出力から内部状態が推測できない）。
CRC・ハッシュ・MAC の違い（重要な整理）
| 手段 | 偶発的誤り | 悪意ある改ざん | 必要なもの |
|---|---|---|---|
| CRC | ✓ 検出 | ✗ 無力（線形なので再計算される） | なし |
| ハッシュ単体 | ✓ 検出 | ✗ 無力（攻撃者もハッシュを計算できる） | なし |
| MAC / HMAC | ✓ | ✓ 防御 | 共有鍵 |
| デジタル署名 | ✓ | ✓ 防御 + 第三者証明 | 公開鍵ペア |
「ハッシュを付けておけば改ざん検知できる」は誤り. 攻撃者はデータを書き換えた上で、そのハッシュも計算し直して付け替えるだけでよい。 ハッシュが有効なのは、ハッシュ値自体が安全な経路で別途伝わる場合だけである （例: 公式サイトに掲載された SHA-256 と、ミラーからダウンロードしたファイルを照合する）。
鍵が無ければ改ざんは防げない。 これがセキュリティの鉄則である。
3. デジタル署名
MAC との決定的な違い
| MAC | 署名 | |
|---|---|---|
| 鍵 | 共有鍵（両者が同じ鍵） | 秘密鍵で署名、公開鍵で検証 |
| 検証できる人 | 鍵を持つ人だけ | 誰でも |
| 否認防止 | ✗ できない | ✓ できる |
なぜ MAC では否認防止ができないのか. MAC は Alice と Bob が同じ鍵を持っている。 だから Bob が「Alice がこう言った」と主張しても、 Bob 自身が同じ MAC を作れるので第三者は判断できない。
署名なら、秘密鍵を持つのは Alice だけ。だから「Alice が署名した」ことを裁判所でも主張できる。 これが電子契約や e-Gov で署名が必須とされる理由である。
RSA 署名
署名: \(\sigma = H(m)^d \bmod n\)（秘密鍵で「復号」の演算をする） 検証: \(\sigma^e \bmod n \stackrel{?}{=} H(m)\)
なぜ\(m\)自体でなく\(H(m)\)に署名するのか. 3 つの理由:
- 長さ: RSA は\(n\)未満の数しか扱えない。長いメッセージは直接署名できない
- 速度: べき乗計算は重い。固定長のハッシュ 1 個で済む
- 安全性: 16 章で見た乗法準同型性\(\sigma_1\sigma_2 = (m_1m_2)^d\)により、 既存の 2 つの署名から新しい署名を偽造できてしまう。 ハッシュを挟むと\(H(m_1)H(m_2) = H(m_3)\)となる\(m_3\)を見つける必要があり、これは困難
実用では RSA-PSS（確率的パディング）を使う。
ECDSA / EdDSA
17 章参照。現代の主流は Ed25519（決定論的なので乱数生成器の事故が起きない）。
4. 応用
パスワード保管
やってはいけない: 平文保存、単純なハッシュ（SHA256(password)）
理由: レインボーテーブル（事前計算表）で一瞬で逆引きされる。 また GPU なら SHA-256 を毎秒数十億回計算できる。
正しい方法: ソルト（ユーザごとのランダム値）+ 計算コストの高い KDF
| 関数 | 特徴 |
|---|---|
| PBKDF2 | 反復回数で調整。古いが広く使われる |
| bcrypt | メモリも少し使う |
| scrypt | メモリ困難（GPU/ASIC に不利） |
| Argon2 | 現在の推奨（Password Hashing Competition 優勝） |
わざと遅くするのがポイント. 正規ユーザは 1 回しか計算しないので 0.1 秒かかっても問題ない。 攻撃者は数十億回試すので、1 回 0.1 秒なら総当たりが事実上不可能になる。
ブロックチェーン
- 各ブロックが前ブロックのハッシュを含む → 過去の改ざんが連鎖的に検出される
- マークル木: 多数のトランザクションを木構造でハッシュし、 ルート 1 個で全体の完全性を保証。特定の 1 件の存在証明が\(O(\log n)\)で済む
証明書チェーン (PKI)
- CA が「この公開鍵は example.com のものである」と署名した証明書を発行
- ブラウザは CA の公開鍵（OS/ブラウザに組み込み済み）で署名を検証
- 検証できれば、その公開鍵で TLS ハンドシェイクを行う
17 章の「DH は中間者攻撃を防げない」という宿題がここで解決する. 証明書によって「通信相手が本物か」を検証し、その上で ECDHE により鍵を共有する。 暗号化（機密性）と認証（真正性）は別々の仕組みで、両方揃って初めて安全になる。
5. 全体のまとめ — このシリーズで学んだこと
| 部 | 内容 | 中心となる数学 |
|---|---|---|
| 第 I 部 | 合同算術 → 群環体 → GF(p) → 多項式 → GF(2^m) | 抽象代数 |
| 第 II 部 | 符号の限界 → 線形符号 → ハミング → CRC → BCH → RS | 有限体上の線形代数・多項式 |
| 第 III 部 | 古典暗号 → LFSR → AES → 数論 → RSA → ECC → 署名 | 数論・有限群 |
同じ数学が両方を支えている
| 数学 | 誤り訂正での役割 | 暗号での役割 |
|---|---|---|
| 合同算術（01 章） | CRC の余り計算 | RSA のべき乗剰余 |
| 有限体 GF(2^m)（05 章） | RS 符号のシンボル演算 | AES の S-box と MixColumns |
| 多項式の除算（04 章） | CRC そのもの | — |
| 原始多項式（04 章） | RS の符号長最大化 | LFSR の最長周期 |
| バーレカンプ・マッシー（11 章） | 誤り位置の特定（味方） | LFSR の解読（敵） |
| 有限群の位数（02 章） | — | フェルマー・オイラー → RSA |
| MDS の概念（06 章） | RS 符号の最適性 | AES の MixColumns 行列 |
最後に. 「壊れても直す」技術と「読まれないようにする」技術は、目的こそ正反対だが、 同じ代数の言葉で書かれている。
誤り訂正は「復元しやすさ」を最大化するように有限体の構造を使い、 暗号は「復元しにくさ」を最大化するように同じ構造を使う。
どちらも、有限の世界で四則演算が完結するという 02〜05 章の事実の上に立っている。 そこが分かれば、この 2 つの分野は 1 つの学問として見えてくるはずである。