古典的な暗号解読

何世紀もの間、人々は情報を隠す巧妙な方法-暗号を思いつきましたが、他の人々は情報を隠すさらに巧妙な方法-ハッキング方法を思いつきました。



このトピックでは、最も有名な古典的な暗号化方法を簡単に説明し、それぞれのハッキング技術について説明します。

シーザーのコード

最軽量かつ最も有名な古典暗号の1つ-シーザーの暗号は食前酒の役割に最適です。

Caesarの暗号は、いわゆる単一アルファベット置換暗号のグループに属します。 このグループの暗号を使用する場合、「平文の各文字は、同じアルファベットのこのキーに固定された文字に置き換えられます」 wiki 。



キーの選択方法は異なる場合があります。 Caesarの暗号のキーは、1〜25の範囲で選択された任意の数字kです。平文の各文字は、アルファベットよりもk文字長い文字に置き換えられます。 たとえば、キーを数字3とします。その後、英語のアルファベットの文字Aは文字Dに、文字Bは文字Eに、というように置き換えられます。



明確にするために、キーk = 7のCaesarの暗号でHABRAHABRという単語を暗号化します。 ルックアップテーブルを作成しましょう。

a

b

c

d

e

f

g

h

私は

j

k

l

m

n

o

p

q

r

s

t

あなたは

v

w

x

y

z

h

私は

j

k

l

m

n

o

p

q

r

s

t

あなたは

v

w

x

y

z

a

b

c

d

e

f

g

そして、テキスト内の各文字を置き換えると、C（ 'HABRAHABR'、7）= 'OHIYHOHIY'になります。



デコード時に、各文字はアルファベットのk文字前の文字に置き換えられます：D（ 'OHIYHOHIY'、7）= 'HABRAHABR'。



シーザーの暗号の暗号解読



小さなキースペース（25オプションのみ）により、ブルートフォースが最も効果的で最も簡単な攻撃オプションになります。

開くには、暗号文の各文字をアルファベットの左側の1文字の文字に置き換える必要があります。 この結果、読み取り可能なメッセージを取得できない場合、アクションを繰り返す必要がありますが、文字をすでに2文字左にシフトしています。 など、結果が読みやすいテキストになるまで。

アフィニティコード

アフィン暗号と呼ばれる、もう少し興味深い単一英数字の置換暗号を考えてみましょう。 また、単純な置換を実装しますが、Caesarの暗号に比べてわずかに大きなキースペースを提供します。 アフィンコードでは、サイズmのアルファベットの各文字に0〜m -1の範囲の番号が割り当てられます。 次に、特別な式を使用して、暗号文の古い数値を置き換える新しい数値が計算されます。



暗号化プロセスは、次の式で説明できます。



、



xはアルファベットの暗号化された文字の番号です。 mはアルファベットのサイズです。 a、bは暗号化キーです。



復号化のために、別の関数が計算されます：



、



ここで、a ^-1はモジュロmの逆数です。 これは、正しい復号化のために、数aはmと互いに素でなければならないことを意味します。



この制限を考慮して、例として英語のアルファベットを使用してアフィン暗号のキースペースを計算します。 英語のアルファベットには26文字が含まれているため、26の相互素数のみをとして選択できます。 このような数値は12個あります。1、3、5、7、9、11、15、17、19、21、23、25です。数値bは 、0〜25の範囲の任意の値を取ることができます。 12 * 26 =可能なキーの312オプション。



アフィニティ暗号化分析



明らかに、アフィン暗号の場合、破る最も簡単な方法は、可能なすべてのキーの列挙です。 しかし、検索の結果として、312の異なるテキストが取得されます。 このような多数のメッセージを手動で分析することは可能ですが、文字の出現頻度などの特性を使用してこのプロセスを自動化することをお勧めします。



自然言語の文字が均等に分布していないことは長い間知られています。 たとえば、テキスト内の英語の文字の出現頻度には次の意味があります。







つまり 英語のテキストでは、最も一般的な文字はE、T、Aになります。最もまれな文字はJ、Q、Zです。したがって、テキスト内の各文字の出現頻度を数えることにより、テキストの頻度応答が英語に対応する度合いを判断できます。



これを行うには、値を計算します。



、



ここで、 n _iは自然言語におけるアルファベットのi番目の文字の頻度です。 また、 f _iは暗号文のi番目の文字の頻度です。



χ値が大きいほど、テキストが自然言語で書かれている可能性が高くなります。



したがって、アフィン暗号を解読するには、312の可能なキーを整理し、復号化の結果として得られたテキストのχ値を計算するだけで十分です。 χの値が最大のテキストで、高い確率で暗号化されたメッセージです。



もちろん、周波数特性が自然言語の特性と大きく異なる可能性があるショートメッセージでは、この方法が常に機能するとは限らないことに注意してください。

簡単な交換暗号

単一アルファベット置換暗号のグループに属する別の暗号。 暗号鍵は、ランダムに混在したアルファベットです。 たとえば、キーは次の文字のシーケンスである可能性があります：XFQABOLYWJGPMRVIHUSDZKNTEC。



暗号化する場合、テキスト内の各文字は次のルールに置き換えられます。 アルファベットの最初の文字はキーの最初の文字に、アルファベットの2番目の文字はキーの2番目の文字に、というように置き換えられます。 この例では、文字AはXに、文字BはFに置き換えられます。



デコード時には、文字が最初にキーで検索され、次に同じ位置のアルファベットの文字に置き換えられます。



暗号解析暗号の簡単な置き換え



単純な置換の暗号鍵スペースは巨大であり、使用されるアルファベットの順列の数に等しい。 したがって、英語の場合、この数は26です！ = 2 ⁸⁸ 。 もちろん、考えられるすべてのキーを単純に検索することは絶望的であり、ハッキングを行うには、トップに登って検索するなど、より高度な手法が必要になります。

1. ランダムな文字列が選択されます-メインキー。 暗号化テキストは、主キーを使用して解読されます。 結果のテキストについて、自然言語に属する確率を特徴付ける係数が計算されます。
2. メインキーは小さな変更（ランダムに選択された2つの文字の置換）を受けます。 復号化が実行され、受信したテキストの係数が計算されます。
3. 係数が保存された値よりも大きい場合、メインキーは修正されたバージョンに置き換えられます。
4. 係数が一定になるまで、手順2〜3を繰り返します。

係数を計算するために、自然言語の別の特性- トライグラムの発生頻度が使用されます。

テキストが英語に近いほど、THE、AND、INGなどのトライグラムに会う頻度が高くなります。 テキストで遭遇するすべてのトライグラムの自然言語での出現頻度を合計すると、自然言語で書かれたテキストを決定する可能性が最も高い係数が得られます。

暗号ポリビウス

別の代替暗号。 暗号キーは5 * 5の正方形（英語）で、Jを除くアルファベットのすべての文字が含まれています。







暗号化中に、ソーステキストの各文字は、置換された文字が配置されている行番号と列番号を表す文字のペアに置き換えられます。 暗号文では、文字aはペアBBに、文字bはペアEBに、というように置き換えられます。 キーには文字Jが含まれていないため、ソーステキストで暗号化する前に、JをIに置き換える必要があります。



たとえば、HABRAHABRという単語を暗号化します。 C（ 'HABRAHABR'）= 'AB BB EB DA BB AB BB EB DA'。



Polybius暗号の暗号解析



暗号には大きなキースペースがあります（英語の場合、25！= 2 ⁸³ ）。 ただし、Polybius squareと以前の暗号との唯一の違いは、ソーステキストの文字が2文字に置き換えられることです。



したがって、攻撃のために、単純な代替の暗号を解読するために使用される技術を使用することができます-トップに登って検索します。

サイズ5 * 5のランダムな正方形がメインキーとして選択されます。 各反復中に、キーは小さな変更を受け、復号化の結果として得られたテキスト内のトライグラムの分布が自然言語の分布に対応するかどうかをチェックします。

順列暗号

置換暗号に加えて、置換暗号も広く使用されています。 例として、 垂直置換の暗号を説明します。



暗号化の過程で、メッセージはテーブルに記録されます。 テーブルの列数は、キーサイズによって決まります。 たとえば、検出されたメッセージを暗号化します。 キー632415を使用して一度にフリー。



キーには6桁が含まれているので、ランダムに選択された文字QKJEUを使用してメッセージを6の倍数に補足し、左から右に6列のテーブルにメッセージを書き込みます。







暗号文を取得するために、キーによって決定された順序でテーブルの各列を書き出します：EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE。



デコードするとき、テキストはキーによって決定された順序で上から下の列にテーブルに書き込まれます。



順列暗号解析



垂直置換暗号を攻撃するための最良の方法は、可能なすべての短いキーを徹底的に検索することです（最大9を含む-約400,000オプション）。 検索で目的の結果が得られなかった場合は、検索を使用して最上部に登ることができます。



考えられる長さの値ごとに、もっともらしいキーが検索されます。 尤度を評価するには、トライグラムの発生頻度を使用することをお勧めします。 その結果、自然言語に最も近い復号化されたメッセージのテキストを提供するキーが返されます。

プレイファーコード

Playfer暗号は、バイグラムの置換を実装するワイルドカード暗号です。 暗号化には、キーが必要です。これは、サイズが5 * 5の文字（Jを除く）の表です。



暗号化プロセスは、テーブル内のバイグラムを見つけて、元のバイグラムと長方形を形成する2、3の文字に置き換えることで軽減されます。

例として、Playfer暗号キーを生成する次の表を考えてください。







ペア「WN」を暗号化します。 文字Wは、最初の行と最初の列にあります。 また、文字Nは2行3列にあります。 これらの文字は、WESNコーナーを持つ長方形を形成します。 したがって、暗号化中に、バイグラムWNはバイグラムESに変換されます。

文字が同じ行または列にある場合、暗号化の結果は、右/下の1つの位置にあるバイグラムになります。 たとえば、バイグラムNGはバイグラムGPに変換されます。



Playfer暗号の暗号解析



Playfer暗号キーは25文字の英語のアルファベットを含むテーブルであるため、この暗号を解読するには、最上部に登る検索方法が最善の方法であると誤解される可能性があります。 残念ながら、この方法は機能しません。 一定レベルのテキストマッチングに達すると、アルゴリズムは極大点で停止し、検索を続行できなくなります。

Playfer暗号を正常に解読するには、アニーリングシミュレーションアルゴリズムを使用することをお勧めします 。



シミュレーテッドアニーリングアルゴリズムとトップサーチへの上昇の違いは、後者が正しい決定に向かう途中で、可能な解決策としてより弱いオプションを決してとらないという事実にあります。 シミュレーテッドアニーリングアルゴリズムは、可能性の低いソリューションに定期的にロールバックしますが、最終的に成功する可能性が高くなります。



アルゴリズムの本質は、次のアクションに限定されます。

1. ランダムな文字列が選択されます-メインキー。 暗号化テキストは、主キーを使用して解読されます。 結果のテキストについて、自然言語に属する確率を特徴付ける係数が計算されます。
2. メインキーは小さな変更（2つのランダムに選択された文字の順列、列または行の順列）を受けます。 復号化が実行され、受信したテキストの係数が計算されます。
3. 係数が保存された値よりも大きい場合、メインキーは修正されたバージョンに置き換えられます。
4. そうでない場合、主キーと変更されたキーの置換は、主キーと変更されたキーの係数の差に直接依存する確率で発生します。
5. 手順2〜4は約50,000回繰り返されます。

このアルゴリズムは、メインキーを定期的に最悪のパフォーマンスのキーに置き換えます。 さらに、置換の確率は特性の違いに依存するため、アルゴリズムが不適切なオプションを頻繁に受け入れることはありません。



テキストが自然言語に属するかどうかを決定する係数を計算するには、トライグラムの発生頻度を使用するのが最善です。

Vigenere Cipher

Vigenere暗号は、多アルファベット置換暗号のグループに属します。 これは、キーに応じて、平文の同じ文字を異なる文字で暗号化できることを意味します。 この暗号化技術は、テキストのすべての周波数特性を隠し、暗号化分析を困難にします。



Vigenere暗号は、異なるキーを持ついくつかのシーザー暗号のシーケンスです。



例として、キー123を使用した単語HABRAHABRの暗号化を示します。ソーステキストの下にキーを書き込み、必要な回数繰り返します。







キー番号は、暗号文を取得するためにアルファベットの文字をシフトするのに必要な位置の数を決定します。 文字Hは1桁シフトする必要があります-結果は文字I、文字Aは2ポジション-文字Cなどとなります。 すべての置換が完了すると、結果として暗号文ICESCKBDUが得られます。



Vigenere暗号分析



Vigenere暗号の暗号解析に直面する最初のタスクは、キーの暗号化に使用される長さを見つけることです。



これを行うには、一致インデックスを使用できます。



一致指数-テキストからランダムに選択された2つの文字が同じになる確率を特徴付ける数値。

テキストの場合、一致インデックスは次の式で計算されます。



、



ここで、 f _iはテキスト内のアルファベットのi番目の文字の出現回数であり、 nはテキスト内の文字数です。



英語の場合、一致インデックスは0.0667ですが、ランダムな文字セットの場合、このインジケーターは0.038です。

さらに、単一アルファベットの置換を使用して暗号化されたテキストの場合、一致インデックスも0.0667に等しくなります。 これは、テキスト内の異なる文字の数が変わらないためです。



このプロパティは、Vigenere暗号キーの長さを見つけるために使用されます。 暗号文から2文字ごとに順番に選択され、受信したテキストの一致インデックスが考慮されます。 結果が自然言語の一致インデックスにほぼ一致する場合、キーの長さは2です。 それ以外の場合、暗号文から3文字ごとに選択され、一致のインデックスが再度カウントされます。 高い一致インデックス値がキーの長さを示すまで、プロセスが繰り返されます。



この方法の成功は、キーの長さが正しく推測された場合、選択された文字が単純なシーザー暗号で暗号化された暗号文を形成するという事実によって説明されます。 また、一致インデックスは自然言語の一致インデックスとほぼ同じである必要があります。

キーの長さが見つかると、ハックはシーザーの暗号をいくつか開くことになります。 これを行うには、このトピックの最初のセクションで説明した方法を使用できます。

PS

上記のすべての暗号のソースとそれらに対する攻撃は、 GitHubで見ることができます。

参照資料

1.racticalcryptography.comでの古典的な暗号の暗号解読。

2.racticalcryptography.comの英語の周波数特性

3. ウィキペディアでのシミュレーテッドアニーリングアルゴリズムの説明

4. ウィキペディアのトップへの上昇の説明