カシスキ検査

暗号解読において、カシスキ試験（カシスキテスト、カシスキ法とも呼ばれる）は、ヴィジュネル暗号などの多アルファベット換字式暗号を解読する方法である。^{[1] [2]}フリードリヒ・カシスキによって1863年に初めて発表されたが、^[3]チャールズ・バベッジによって1846年には早くも独立して発見されていたようである。 ^{[4] [5]}

キーワードを使用して置換アルファベットを選択する多アルファベット置換暗号では、カシスキ試験により暗号解読者はキーワードの長さを推測することができます。キーワードの長さが判明したら、暗号解読者は暗号文をn列に並べます。ここでnはキーワードの長さです。次に、各列を単アルファベット置換暗号の暗号文として扱うことができます。このようにして、各列を頻度分析で攻撃することができます。^[6]同様に、ローターストリーム暗号機が使用されている場合、この方法により個々のローターの長さを推測することができます。

カシスキ検査では、暗号文で繰り返される文字列を探します。検査が成功するには、文字列の長さは 3 文字以上である必要があります。その後、文字列の連続出現間の距離は、キーワードの長さの倍数になる可能性があります。したがって、より多くの繰り返し文字列を見つけると、すべての距離の最大公約数を取ることができるため、キーワードの可能な長さが絞り込まれます。 ^[7]

このテストが機能する理由は、プレーンテキスト内に繰り返し文字列が発生し、対応する文字間の距離がキーワードの長さの倍数である場合、キーワード文字は文字列の両方の出現で同じように整列するためです。たとえば、プレーンテキストを考えてみましょう。

男と女は郵便局から手紙を受け取った

「 the 」という単語は繰り返し文字列であり、複数回出現します。プレーンテキストを 5 文字のキーワード「beads」と並べると次のようになります。

bea dsb ead sbe adsbeadsb ead sbeads bead sbe adsb eadsbe
男と女は郵便局
から手紙を受け取った

「the」という単語は、「bea」にマッピングされることもあれば、「sbe」にマッピングされることもあれば、「ead」にマッピングされることもある。しかし、「sbe」には2回マッピングされており、十分に長いテキストでは、これらの可能性のそれぞれに複数回マッピングされる可能性が高い。カシスキは、このような繰り返し出現間の距離は暗号化期間の倍数でなければならないと指摘した。^[7]

この例では、周期は 5 で、2 つの「sbe」間の距離は 30 で、周期の 6 倍です。したがって、繰り返されるシーケンス間の距離の最大公約数から、キーの長さまたはその倍数がわかります。

カシスキ検査を使用する際の難しさは、繰り返される文字列を見つけることです。これは手動で実行するには非常に難しい作業ですが、コンピューターを使用するとはるかに簡単になります。ただし、一部の繰り返される文字列は単なる偶然である可能性があり、その場合、繰り返し距離の一部が誤解を招く可能性があるため、注意が必要です。暗号解読者は、正しい長さを見つけるために偶然を除外する必要があります。その後、当然のことながら、結果として得られる単一アルファベットの暗号文を暗号解読する必要があります。

1. 暗号解読者は、繰り返される文字のグループを探し、各繰り返しグループの先頭間の文字数を数えます。たとえば、暗号文がFGX THJAQWN FGX Qの場合、FGXグループ間の距離は 10 です。暗号解読者は、テキスト内のすべての繰り返しグループの距離を記録します。
2. 次に、アナリストはこれらの数字をそれぞれ因数分解します。これらの因数分解の大半で数字が繰り返される場合、それはキーワードの長さである可能性が高いです。これは、同じ文字が同じキー文字を使用して暗号化されている場合、単なる偶然よりも、繰り返されるグループが発生する可能性が高いためです。これは、長い一致文字列の場合に特に当てはまります。キー文字はキーの長さの倍数で繰り返されるため、ステップ 1 で見つかった距離のほとんどは、キーの長さの倍数である可能性があります。通常、共通の因数は明らかです。
3. キーワードの長さがわかれば、バベッジとカシスキの次の観察が役に立ちます。キーワードがN文字の長さである場合、N番目の文字ごとにキーテキストの同じ文字を使用して暗号化されている必要があります。N番目の文字ごとにグループ化すると、アナリストはN 個の「メッセージ」を取得できます。各メッセージは 1 つのアルファベットの置換を使用して暗号化され、各部分は頻度分析を使用して攻撃できます。
4. 解析されたメッセージを使用して、アナリストはキーワードが何であったかをすぐに判断できます。または、断片を解析する過程で、アナリストはキーワードに関する推測を使用してメッセージを解読することもあります。
5. インターセプターがキーワードを認識すると、その知識を使用して同じキーを使用する他のメッセージを読み取ることができます。

カシスキは実際に「重ね合わせ」を使ってヴィジュネル暗号を解読しました。彼は上記のように鍵の長さを見つけることから始めました。次に、メッセージを複数コピーして、それぞれを鍵の長さだけ左にずらしながら重ねました。するとカシスキは、各列が1 つのアルファベットで暗号化された文字で構成されていることに気づきました。彼の方法は上記の方法と同等ですが、おそらくイメージしやすいでしょう。

多アルファベット暗号に対する現代の攻撃は、基本的に上記の攻撃と同じですが、一致カウントという唯一の改良点があります。 繰り返しグループを探す代わりに、現代のアナリストはメッセージのコピーを 2 つ取り、一方をもう一方の上に重ねます。

現代のアナリストはコンピュータを使用しますが、この説明はコンピュータ アルゴリズムが実装する原理を示しています。

一般化された方法:

1. アナリストは、一番下のメッセージを 1 文字左にシフトし、次にさらに 1 文字左にシフトするなどして、そのたびにメッセージ全体を調べ、一番上のメッセージと一番下のメッセージに同じ文字が出現する回数を数えます。
2. 一番下のメッセージがキーの長さの倍数だけシフトされると、「一致」の数は急激に増加します。これは、隣接する文字が同じアルファベットを使用する同じ言語であるためです。
3. 鍵の長さがわかったら、頻度分析を使用して上記のように暗号解読を進めます。

• 暗号解読: YouTubeのカシスキ試験によるヴィジュネル暗号文の解読- カシスキ試験を使用してヴィジュネル暗号文を解読する方法を示すビデオ