基本情報技術者 2018年 秋期 午前（科目A） 問37

AES-256 の鍵に対するブルートフォース試行回数【午前2 解説】

要点まとめ

• 結論→ AES-256 の鍵長は 256 ビットで鍵空間は $2^{256}$、よって最大の試行回数は $2^{256}$ 回になります。
• 根拠→ 鍵長が n ビットなら鍵の総数は $2^n$、256 ビットなら総当たりで取りうる鍵は $2^{256}$ 通りです。
• 差がつくポイント→ ブロック長（AES はブロック 128 ビット）と鍵長を混同しないこと、平均試行は約 $2^{255}$、量子攻撃は平方根（Grover）に低減します。

正解の理由

よくある誤解

• AES の「ブロック長 128 ビット」と「鍵長 256 ビット」を混同し、$2^{128}$ を答えてしまう誤り。ブロック長は平文処理単位で鍵空間とは別概念です。
• 「最大」と「平均」を混同して $2^{255}$ を選ぶ誤り。平均試行回数は約半数ですが、問題は「最大値」を問うています。
• 量子アルゴリズム（Grover）の存在を理由に古典的な最大試行回数を $2^{128}$ と誤認する誤り。Grover は理想的な量子検索で平方根に減らすが、現実の制約や対策を考慮する必要があります。

解法ステップ

1. 問題文から「AES-256」とあるので鍵長が 256 ビットであることを確認する。
2. 鍵長 n ビットの鍵空間の総数は $2^n$ であることを使う。
3. n=256 を代入して鍵空間 = $2^{256}$。
4. ブルートフォースで鍵を見つけるまでの最大試行回数は鍵空間の総数（$2^{256}$）であるため、選択肢の中から該当するものを選ぶ。→ エ

選択肢別の誤答解説

• ア: 256
  • 誤り。256 は「ビット数」を表す単なる値であり、試行回数は 2 の累乗で表されます。256 回では鍵空間を表せません。
• イ: $2^{128}$
  • 誤り。$2^{128}$ は AES-128 の鍵空間に相当するか、量子攻撃で AES-256 の安全性が平方根に縮む理想値（$2^{128}$ 相当）と混同した結果の回答です。問題は古典的な最大試行回数を問うています。
• ウ: $2^{255}$
  • 誤り。$2^{255}$ は平均的に必要な試行回数の概算（$2^{256}/2$）に相当します。問題文は「最大値」を問うているため不適切です。
• エ: $2^{256}$
  • 正解。鍵長 256 ビットのすべての組み合わせを試す最悪ケースの回数に一致します。

補足コラム

• $2^{256}$ の大きさ感覚：$2^{256}\approx 1.1579\times 10^{77}$ であり、現代の計算力では事実上ブルートフォースは不可能です。
• 量子計算の影響：理想的な Grover のアルゴリズムを前提にすれば探索コストは平方根になり、AES-256 は概念上 $2^{128}$ 相当の安全性になりますが、現実的な量子マシンでの実現や実装上の制約があり実用段階では容易ではありません。
• 実務上の注意点：鍵が人間のパスワード由来であればエントロピーが低く実効的な鍵空間は小さくなるため、鍵管理や鍵生成（乱数源）に注意が必要です。

FAQ