鍵空間 (暗号理論)

暗号理論において、あるアルゴリズムの鍵空間とは、ある鍵の考え得るすべての転置の集合のこと[1][2]。

説明

メッセージの暗号化に使用した鍵がアドバーサリからの総当たり攻撃で発見されないようにするため、鍵空間は通常そのような探索が実現不可能となる程度に大きく設計される。平均的には解を発見するまでに鍵空間の半分を探索する必要がある[3]。

もう1つの望ましい性質は、鍵を考え得るすべての鍵の転置から真にランダムに選択する必要があることである。もしそうでなく、しかも鍵の選択方法に影響を与え得る要因を攻撃者が特定することができるなら、探索空間 (および探索時間) は著しく縮小する。人間はパスワードをランダムに選択しないので、攻撃者は総当たり攻撃の前に辞書攻撃を行うことが多い。この手法では、すべての実現可能な文字の組み合わせをシステマティックに総当たり探索する場合の半分未満の時間で正解を導き出すことができる。

例

鍵が8ビット (1バイト) 長であれば、鍵空間は2^8つまり256個の鍵の候補で構成される。AESでは256ビットの対称鍵が使用されるので、2^256 (つまり1.1579 × 10^77) 個の鍵候補を含んだ鍵空間が得られる。

DESブロック暗号では56ビットの鍵が使用されるので、2^56 (つまり7.2058 x 10^16) という比較的小さな鍵空間が得られるが、これは1998年にデスクトップ型コンピューターで56時間で探索し尽くすことができた[4]。

出典

1. “CISSP Exam Preparation”. Flashcard machine. 2010年3月11日閲覧。 “All possible values that can be set to generate a key.”
2. “Q: What is a "keyspace"?”. experts123. 2011年3月11日閲覧。 “A "keyspace" is the theoretical set of all possible permutations of a key, given a set key size.”
3. “Flash Card Machine”. 2017年8月4日閲覧。 “Question: Why do the statistics measure estimate time to having 50% of the keyspace searched? Answer: Because we don't know where in the keyspace of 72,000,000,000,000,000 the right answer is. On the average, only 50% of the keyspace needs to be searched before a solution is found.”
4. Congressional Record. 17. 144. United States Senate. (October 7–9, 1998). p. 25124. https://books.google.com/books?id=m5wLgC546hMC&pg=PA25124