同じ1回限りのパッドで暗号化が良くないのはなぜですか？

Question

1回のパッドキー$ k $を使用してメッセージ$ m_1 $を暗号化するには、$ enc（m_1、k）= m_1 oplus k $を暗号化します。

同じ$ k $を使用して別のメッセージを暗号化する場合、$ m_2 $を暗号化すると、$ enc（m_2、k）= m_2 oplus k $を取得し、2つのciphertextのxorを実行すると、$$（m_1 oplus kが取得されます。 ） oplus（m_2 oplus k）= m_1 oplus m_2 $$

だから、OK、$ m_1 oplus m_2 $を学ぶので、いくつかの情報漏れがありますが、なぜ安全ではないのですか？ $ m_2 $を知らない限り、学ぶ方法はありません（たとえば）$ m_1 $。それで、なぜ$ k $を2回使用するのが間違っているのですか？

Answer 1

$ m_2 $を知らない限り、学ぶ方法はありません（たとえば）$ m_1 $。

それがまさに問題です - 同じキーを再利用し、誰かがプレーンテキストと暗号化されたフォームの両方で暗号化した1つのメッセージにアクセスできる場合、それを使用してキーを見つけることができます：$$（M_2 Oplus K） Oplus M_2 = K $$

別のシナリオとして、同じキーを何度も使用している場合、攻撃者はさまざまな暗号化されたメッセージの一部だけを推測できる可能性があり、それぞれの成功した推測はキー$ k $の一部を明らかにします。キーが明らかになりました。

暗号システムを破るためのこの一般的な戦略は、 既知のプレーンテキスト攻撃. 。 AESやRSAのような多くのシステムは、これらの攻撃に対して安全であると考えられています。しかし、すべての暗号化に新しいパッドが使用されない限り、1回限りのパッドはそれらに対して完全に不安定になります。そのため、「ワンタイムパッド」と名付けられています。

Answer 2

それはあなたが言及した理由のために正確に不安です - いくつかの情報漏れがあります。

基本的に、平文（英語のテキスト、既知の構造を持つファイルなど）についての仮定がある場合、簡単な統計分析につながります。おそらくそれを使用します 2回 攻撃の実用性を大幅に変更することはありませんが、非ランダムなプレーンテキストで何度も使用すると、最終的にキーを回復するのに十分な情報が明らかになります。

最後に、あなたがそれを使用する能力がある場合のみ 2回, 、あなたはそれを使用する能力も持っています 一度 - 制限は、これらの1回限りのパッドは、潜在的に不明で時間の経過とともに使用され、数回ダメージを与えることです。

極端な場合、$ m_1 $がパッドの長さのnull弦であることを知っている場合（既知のプレーンテキスト）、$ m_2 $を計算する前に攻撃者にキーを渡しました。

既知のプレーンテキスト攻撃はかなり一般的であり、暗号化メカニズムを強制して、あなたが知っている何かを暗号化するのは合理的に簡単です。そうでない場合は、通常、合理的な統計的仮定を行うことができます。

Answer 3

英語のテキスト付きの1回限りのパッドを使用し、2回使用するとします。これで、$（m_1 oplus k） oplus（m_2 oplus k）= m_1 oplus m_2 $を取得できます。

英語のテキストには、文字あたり1.3ビットのようなエントロピーがあります。 2つのメッセージのXORには、文字ごとに2.6ビットがあります。アルファベットには26文字があるため、文字ごとに$ log_2 26 = 4.7 $ビットが与えられます。これは、2つの英語のテキストのXORを取得したとしても、これらのテキストの両方をデコードするのに十分な情報がまだ理論的にあることを意味します。さらに、私は暗号化物が実際にそれを行うことができると読んだことをかなり確信しています。

1回限りのパッドを2回使用する場合は、最初にメッセージを圧縮する必要があります。そして、それでも、ほぼ完璧な圧縮アルゴリズムを使用していない場合、1回限りのパッドを複数回使用すると、メッセージを理論的に回復するのに十分なエントロピーが残ります。それが実際にどれほど難しいかわかりません。

Answer 4

問題は、$ m_1 $と$ m_2 $について何も知らないとしても、$ m_1 oplus m_2 $から両方を回復できるかもしれないということです。

実際、多くの場合、それは非常に簡単です。これがそうです 簡単な視覚化。

Answer 5

数学に頼ることなく、アプローチを表現する直感的な方法は次のとおりです。同じ1回のパッドで暗号化された2つの暗号化されたメッセージがあるとしましょう。

1. メッセージの1つに含まれる可能性のある単語またはフレーズで推測します。 「天気レポート」というフレーズを言ってみましょう
2. メッセージ1から始めて、「天気報告」が最初の文字位置で発生すると仮定します。
3. ワンタイムパッドの最初の14文字を後退させます。
4. 逆方向のOTPを使用して、メッセージ2の最初の14文字を復号化します。
5. プレーンテキストがGobble-di-Gookのように見える場合は、ステップ2に戻り、2番目の文字位置で繰り返します。ただし、意味のあるテキストを取得した場合（たとえば「おはよう私」とおめでとうございます。OTPの最初の14文字（および各文字の最初の14文字）を解決しました。
6. ランダムな文字以外に何も投げかけずにメッセージ1の最後に到達した場合、「天気レポート」というフレーズはメッセージ1で発生しないと結論付けることができます。 「