ユニシティ距離 - 百科事典

暗号学において、ユニシティ距離とは、ブルートフォース攻撃により誤りのある鍵の数をゼロにすることで暗号を解読するために必要な元の暗号テキストの長さです。つまり、すべての可能性のある鍵を試した後、一つだけ解読可能な解が存在するべきであり、これは、基底的メッセージに冗長性があることを仮定すると、鍵を完全に決定するために必要な期待される暗号テキストの長さです。

クロード・シャノンは、1949年の論文「秘密通信システムの通信理論」でユニシティ距離を定義しました。例えば、ビジェネール暗号を使用して5文字の鍵で暗号化された「WNAIW」という暗号テキストに対する攻撃を考えると、この文字列は特定の鍵であればどんな他の文字列にも解読可能です。これは暗号解析の一般的なルールであり、追加の情報がない限り、このメッセージを解読することは不可能です。

もちろん、この場合でも、5文字の鍵のうち、英語の単語になる可能性のあるのは特定の数だけです。すべての可能性のある鍵を試しても、RIVERやWATERだけでなく、SXOOSやKHDOPも得られます。機能する鍵の数は、すべての可能性のある鍵の集合よりもはるかに少ないでしょう。問題は、これらの「機能する」鍵の中でどれが正しいかを知ることです。残りは誤りです。

鍵のサイズと可能な平文との関係
一般的に、鍵のサイズと可能なメッセージの数に関する特定の仮定がある場合、平均的な暗号テキストの長さがあり、その長さでは平均で一つの鍵しか読み取り可能なメッセージを生成しません。上記の例では、上記の英字のみを使用しており、プラテキストがこの形式であると仮定すると、文字列の各位置に26の可能な文字があります。同様に、5文字の大文字の鍵を仮定すると、K=265の可能な鍵があり、その多くは機能しません。

非常に多くの可能なメッセージ、Nが、この限られたキャラクターセットを使用して生成できます：N = 26L、ここでLはメッセージの長さです。しかし、言語の規則により読み取り可能なプラテキストの集合はより小さく、Mのものしかありません。MはNよりもはるかに小さくなる可能性が高く、Mは機能する鍵の数と一一対一の関係があります。したがって、Kの可能な鍵があると、そのうちのK × (M/N)が「機能する」鍵です。これらの一つが正しい鍵であり、残りは誤りです。

M/Nがメッセージの長さLが大きくなるにつれて任意に小さくなるため、最終的には誤り鍵の数がゼロになるようなLがあります。これはKM/N=1に相当するLであり、これはユニシティ距離です。

鍵のエントロピーとプラテキストの冗長性との関係
ユニシティ距離は、計算的な制約のない敵がユニークな暗号鍵を復旧できるように必要な最小の暗号テキストの量としても定義できます。

期待されるユニシティ距離は以下のように示せられます：



U
=
H
(
k
)

/

D


{\displaystyle U=H(k)/D}

ここで、Uはユニシティ距離、H(k)は鍵空間のエントロピー（例えば、2^128の等確率の鍵の場合、128、パスフレーズの場合はもっと少ない）です。Dはビット単位のプラテキストの冗長性です。

32のキャラクターのアルファベットは、キャラクターごとに5ビットの情報を持ちます（32 = 2^5）。一般的に、キャラクターごとの情報のビット数は log2(N)であり、Nはアルファベットのキャラクターの数であり、log2は二進数の対数です。したがって、英語では、各キャラクターは log2(26) = 4.7ビットの情報を伝達できます。

しかし、意味のある英語のテキストで、各キャラクターごとに実際に持つ平均情報の量は約1.5ビットです。したがって、プラテキストの冗長性は D = 4.7 − 1.5 = 3.2です。

基本的に、ユニシティ距離が大きいほど良いです。無制限のサイズのワンタイムパッドの場合、鍵空間の無限のエントロピーにより、U = ∞ となります。これはワンタイムパッドが解読不可能であることと一致します。

代換暗号のユニシティ距離
シンプルな代換暗号の場合、可能な鍵の数は 26! = 4.0329 × 10^26 = 288.4、アルファベットがどのように並べ替えられるかの方法の数です。すべての鍵が同様に確率であると仮定すると、H(k) = log2(26!) = 88.4ビットです。英語のテキストでは、D = 3.2ですので、U = 88.4/3.2 = 28です。したがって、28の暗号テキストがあれば、理論的には英語のプラテキストを推測し、その鍵を特定することができます。

実践的な応用
ユニシティ距離は理論的な有用な尺度ですが、実際のリソース（限られたリソース）を持つ敵に攻撃された場合のブロック暗号のセキュリティについて多くを語りません。ユニシティ距離が3つの暗号ブロックであるブロック暗号を考えると、計算的な制約のない敵が正しい鍵を見つけるのに十分な情報があることは明らかですが、実際には計算的に実現不可能かもしれません。

ユニシティ距離は、プラテキストの冗長性を減らすことで増やすことができます。これを実現する方法の一つは、暗号化の前にデータ圧縮技術を使用することです。例えば、読みやすさを維持しながら重複する母音を取り除くことができます。これは、暗号化するデータの量を減らすという点で良いアイデアです。

ユニシティ距離以上の長さの暗号テキストは、一つの意味のある解読だけが存在すると仮定できます。ユニシティ距離未満の暗号テキストは、複数の合理的な解読が存在する可能性があります。ユニシティ距離は、暗号解析にどれだけの暗号テキストが必要かの尺度ではなく、暗号解析に一つの合理的な解決策が存在するための暗号テキストの量の尺度です。

参考文献


外部リンク
Bruce Schneier: How to Recognize Plaintext (Crypto-Gram Newsletter December 15, 1998)
Common ciphersのユニシティ距離計算