暗号技術の基礎と応用
鍵長がnビットの共通鍵暗号の鍵を、量子コンピュータのグローバーのアルゴリズムで探すと、必要な計算の回数は約 2^(n/2) 回になるとされる。この単純な目安で考えたときの、量子コンピュータに対するAES-128の安全性として、最も近いものはどれか。
- A約64ビット相当
- B約127ビット相当
- C約128ビット相当
答えと解説を見る
正解：A. 約64ビット相当
グローバーのアルゴリズムは、総当たりの回数を 2ⁿ から約 2^(n/2) へ、平方根にまで減らします。AES-128では 2^(128/2) = 2⁶⁴ 回となり、安全性は約64ビット相当になります。公開鍵暗号を多項式時間で破るショアのアルゴリズムと違い、鍵を長くすれば対応でき、AES-256なら約128ビット相当が残ります。ただし、グローバーのアルゴリズムは並列化の効果が小さく、長い計算を誤りなく続ける必要もあるため、これはあくまで単純な目安で、NISTの耐量子計算機暗号の評価でも、AES-128の鍵の探索と同じくらい難しいことが、最も低い安全性の区分の基準になっています。
- A. 正しい。2^(128/2) = 2⁶⁴ で、約64ビット相当です。
- B. 約127ビットは、古典のコンピュータの総当たりで、平均して半分の 2¹²⁷ 回で見つかることに対応する値です。
- C. 量子コンピュータの影響をまったく受けないと考えた値です。グローバーのアルゴリズムで、安全性のビット数はほぼ半分になります。