ヴィジュネル暗号

1863年、フリードリヒ・カシスキーはヴィジュネル暗号に対する一般的な攻撃に成功した最初の人物となった。^{[ 19 ]}それまでの攻撃は平文の知識や認識可能な単語を鍵として使用することに依存していた。カシスキーの方法にはそのような依存はなかった。カシスキーが攻撃に関する記述を最初に発表したが、他の人々もそれを知っていたことは明らかである。1854年、ジョン・ホール・ブロック・スウェイトが「新しい」暗号を芸術協会誌に投稿したことで、チャールズ・バベッジはヴィジュネル暗号を解読するよう促された。^{[ 20 ] [ 21 ]}バベッジがスウェイトの暗号が本質的にはヴィジュネル暗号の別の再現に過ぎないことを示したとき、スウェイトはバベッジに挑戦状を突きつけた。シェイクスピアの『テンペスト』第1幕第2場からの原文と暗号化されたバージョンが与えられたとき、スウェイトが原文を暗号化するために使用したキーワードを見つけるようにと。バベッジはすぐにキーワード「two」と「combined」を見つけた。バベッジは次にシェイクスピアの同じ箇所を別のキーワードで暗号化し、スウェイトにバベッジのキーワードを見つけるように挑戦した。^{[ 22 ]}バベッジは自分が使用した方法を説明しなかった。バベッジのメモの研究によると、彼は後にカシスキーによって発表された方法を使用しており、1846年にはすでにその方法を使用していたことが示唆されている。^{[ 23 ]}

カシスキー検定（カシスキーテストとも呼ばれる）は、偶然にも同じ鍵文字で暗号化された単語が繰り返されることがあるという事実を利用し、暗号文に繰り返し出現するグループが生じることを利用する。例えば、キーワードを使用した次の暗号化を考えてみようABCD。

凡例: ABCDAB CDABCDABCD ABCDAB CDABCD 平文: cryptoはcryptographyの略です 暗号文: CSASTP KVSIQUTGQU CSASTP IUAQJB

暗号文には容易に気づくことができる繰り返しパターンが存在するため、カシスキー検定は有効である。

の繰り返し間の距離CSASTPは 16 です。繰り返しられたセグメントが同じ平文セグメントを表していると仮定すると、鍵の長さは 16、8、4、2、または 1 文字になります。（距離のすべての倍数が鍵の長さとして考えられます。長さ 1 の鍵は単純なシーザー暗号であり、その暗号解読ははるかに簡単です。）鍵の長さ 2 と 1 は非現実的に短いため、長さ 16、8、および 4 だけを試せばよいことになります。長いメッセージは通常、より多くの繰り返し暗号文セグメントを含むため、テストの精度が高くなります。次の暗号文には、繰り返されるセグメントが 2 つあります。

暗号文: VHVS SP QUCE MRVBVBBB VHVS URQGIBDUGRNICJ QUCE RVUAXSSR

の繰り返し間の距離はVHVS18 です。繰り返しセグメントが同じ平文セグメントを表していると仮定すると、鍵の長さは 18、9、6、3、2、または 1 文字になります。 の繰り返し間の距離はQUCE30 文字です。つまり、鍵の長さは 30、15、10、6、5、3、2、または 1 文字になります。これらの集合の共通部分を取ると、3、2、1 は非現実的に短いため、最も可能性の高い鍵の長さは 6 であると安全に結論付けることができます。

フリードマン検定（カッパ検定とも呼ばれる）は、1920年代にウィリアム・F・フリードマンによって考案されたもので、暗号文字の出現頻度の不均一性を測定する一致指数を用いて暗号を解読した。${\displaystyle \kappa _{\text{p}}}$ランダムに選択された2つのソース言語の文字が同じである確率（大文字小文字を区別しない英語では約0.067）と、アルファベットからの均一なランダム選択で一致する確率${\displaystyle \kappa _{\text{r}}}$（英語の場合は1/26 = 0.0385）キーの長さは次のように推定できます。

${\displaystyle {\frac {\kappa _{\text{p}}-\kappa _{\text{r}}}{\kappa _{\text{o}}-\kappa _{\text{r}}}}}$

観測された同時発生率から

${\displaystyle \kappa _{\text{o}}={\frac {\sum _{i=1}^{c}n_{i}(n_{i}-1)}{N(N-1)}}}$

ここで、cはアルファベットのサイズ (英語の場合は 26)、Nはテキストの長さ、n ₁からn _cは観測された暗号文の文字頻度(整数) です。

しかし、これはあくまで近似値であり、テキストの長さに応じて精度が向上します。実際には、推定値に近いさまざまな鍵長を試す必要があります。^{[ 24 ]}繰り返し鍵暗号のより良いアプローチは、想定される鍵長と同じ数の列を持つ行列の行に暗号文をコピーし、各列を個別に考慮して平均一致指数を計算することです。可能なすべての鍵長に対してこれを実行すると、最も高い平均一致指数が最も可能性の高い鍵長に対応します。^{[ 25 ]}このようなテストは、カシスキ調査からの情報で補完することができます。

鍵の長さが分かれば、暗号文をその長さの列に書き換えることができ、各列は鍵の1文字に対応します。各列は、1つのシーザー暗号で暗号化された平文で構成されます。シーザー鍵（シフト）は、その列に使用されたヴィジュネル鍵の文字です。シーザー暗号を解読する際に用いられる方法と同様の方法を用いることで、暗号文中の文字を解読することができます。

カシスキ検査の改良版であるケルクホフス法は、各列の文字頻度をシフトされた平文頻度と照合して、その列の鍵文字（シーザーシフト）を発見します。鍵のすべての文字がわかれば、暗号解読者は暗号文を復号して平文を明らかにするだけで済みます。^{[ 26 ]}ヴィジュネル表が通常のアルファベット順ではなくスクランブルされている場合、ケルクホフス法は適用できませんが、カシスキ検査と一致テストを使用して鍵の長さを決定することは可能です。

通常のアルファベットを用いたヴィジュネル暗号は、本質的に可換な剰余演算を使用します。したがって、鍵の長さが既知（または推測）であれば、暗号文から鍵の長さだけオフセットした値を差し引くと、平文から鍵の長さだけオフセットした値を差し引いたものが得られます。平文中の「可能性のある単語」が既知または推測できる場合、その自己減算を認識できるため、既知の平文を暗号文から差し引くことで鍵を復元できます。鍵の消去は、短いメッセージに対して特に有効です。例えば、LION以下のものを鍵として使用する場合：

次に、 の鍵長 4 だけシフトして、暗号文からそれ自身を減算しますLION。

これは、平文から同じシフト量だけ平文を差し引くこととほぼ同等です。

これは代数的に表すと次のようになります。${\displaystyle i\in [1,n-m]}$として：

${\displaystyle {\begin{aligned}(C_{i}-C_{(i+m)}){\bmod {\ell }}&=(E_{K}(M_{i})-E_{K}(M_{(i+m)})){\bmod {\ell }}\\&=((M_{i}+K_{(i{\bmod {m}})}){\bmod {\ell }}-(M_{(i+m)}+K_{((i+m){\bmod {m}})}){\bmod {\ell }}){\bmod {\ell }}\\&=((M_{i}+K_{(i{\bmod {m}})})-(M_{(i+m)}+K_{((i+m){\bmod {m}})})){\bmod {\ell }}\\&=(M_{i}+K_{(i{\bmod {m}})}-M_{(i+m)}-K_{((i+m){\bmod {m}})}){\bmod {\ell }}\\&=(M_{i}-M_{(i+m)}+K_{(i{\bmod {m}})}-K_{((i+m){\bmod {m}})}){\bmod {\ell }}\\&=(M_{i}-M_{(i+m)}+K_{(i{\bmod {m}})}-K_{(i{\bmod {m}})}){\bmod {\ell }}\\&=(M_{i}-M_{(i+m)}){\bmod {\ell }}\\\end{aligned}}}$

この例では、単語はbrownfox既知です。

この結果は、omaz上記のより大きな例の結果における9番目から12番目の文字に相当します。既知のセクションとその位置が確認されました。

brow暗号文のその範囲から減算します。

これにより最終結果、つまり鍵の開示がもたらされるLION。

ヴィジュネル暗号のランニングキー方式も、かつては解読不可能と考えられていた。この方式では、鍵として平文と同じ長さのテキストブロックが使用される。鍵がメッセージと同じ長さであるため、鍵が繰り返されないことから、フリードマン検定やカシスキー検定はもはや有効ではない。

複数のキーを使用する場合、実効キー長は個々のキーの長さの最小公倍数になります。例えば、長さが2と3の2つのキーとを使用するとGO、CAT実効キー長は6（2と3の最小公倍数）になります。これは、両方のキーが一致する点として理解できます。

2回暗号化する、つまり最初に鍵で暗号化しGO、次に別の鍵でCAT暗号化することは、一方の鍵をもう一方の鍵で暗号化して生成された鍵で1回暗号化することと同じです。

これは、attackatdawnで暗号化することでIOZQGH、元の例と同じ暗号文を生成することによって実証されます。

鍵の長さが互いに素である場合、実効鍵長は鍵の長さの積となるため、個々の鍵の長さが増加するにつれて実効鍵長も急速に増加します。例えば、鍵の長さが10、12、15文字の場合、実効鍵長はわずか60（2×2×3×5）ですが、8、11、15文字の場合は1320（8×11×15）になります。この実効鍵長が暗号文よりも長い場合、フリードマン検定およびカシスキー検定に対する耐性は、ランニングキー方式と同等になります。

真にランダムな鍵を使用し、その鍵の長さが暗号化されたメッセージの長さ以上で、かつ一度だけ使用される場合、ヴィジュネル暗号は理論的には解読不可能である。しかし、その場合、暗号の強度を左右するのは暗号自体ではなく鍵であり、このようなシステムは、使用される暗号の種類に関わらず、総称してワンタイムパッドシステムと呼ばれるのが適切である。

簡単なバリエーションとして、ヴィジュネル暗号方式で暗号化し、ヴィジュネル暗号方式で復号する方法があります。この方法は「バリアント・ボーフォート」と呼ばれることもあります。これは、フランシス・ボーフォートによって考案されたボーフォート暗号とは異なります。ボーフォート暗号はヴィジュネル暗号に似ていますが、暗号化メカニズムとタブローがわずかに変更されています。ボーフォート暗号は相互暗号です。

ヴィジュネル暗号は一見強力に見えたが、ヨーロッパ全土で広く使われることはなかった。グロンスフェルト暗号は、ガスパール・ショットがグロンスフェルト伯爵（ヨッセ・マクシミラン・ファン・グロンスフェルト、旧姓ファン・ブロンクホルスト）に帰属させた変種だが、実際には1560年代から1570年代にかけてマントヴァ公の使節によってずっと以前に使用されていた。これはヴィジュネル暗号と同一だが、0から9までの数字に対応する10文字の暗号アルファベットのみを使用する。グロンスフェルト暗号の鍵0123は、ヴィジュネル暗号の鍵ABCDと同じである。グロンスフェルト暗号は、鍵が単語ではないため強力だが、暗号アルファベットが10文字しかないため弱くなっている。弱点があるにもかかわらず、ドイツやヨーロッパ全土で広く使われるようになったのはグロンスフェルト暗号である。

ヴィジュネルは実際にはより強力な暗号、オートキー暗号を発明した。「ヴィジュネル暗号」という名称は、より単純な多表式暗号と結び付けられるようになった。実際、この2つの暗号はしばしば混同され、どちらも「解読不能な暗号（le chiffre indéchiffrable ）」と呼ばれることもあった。バベッジは実際に、はるかに強力なオートキー暗号を解読したが、固定鍵多表式暗号の最初の解法を公表したのは一般的にカシスキーであるとされている。

• ボイテルスパッハー、アルブレヒト（1994）。「第2章」。暗号学。J. クリス・フィッシャーによるドイツ語からの翻訳。ワシントンD.C.：アメリカ数学協会。pp . 27–41。ISBN  0-883-85504-6。
• シン、サイモン（1999）。「第2章：解読不能な数字」。『暗号ブック』。アンカーブック、ランダムハウス。ISBN 0-385-49532-3。
• ヘレン・F・ゲインズ（2014年11月18日）。暗号解読：暗号とその解法の研究 。クーリエ・コーポレーション。117ページ。ISBN 978-0-486-80059-2。
• メンデルゾーン、チャールズ・J（1940）。「ブレーズ・ド・ヴィジュネルと『シッフル・カレ』」アメリカ哲学会紀要82 ( 2)