転置暗号

暗号学において、転置暗号（または順列暗号）は、文字自体を変更せずに文字の位置をスクランブルする（転置）暗号化方式です。転置暗号は、平文の単位（通常は文字または文字のグループ）を規則的なシステムに従って並べ替え、平文の順列である暗号文を生成します。転置暗号は、平文の単位の位置を変更せずに単位自体を変更する置換暗号とは異なります。転置操作と置換操作には違いがありますが、 ADFGVX 暗号などの歴史的な暗号や、最新のAdvanced Encryption Standard (AES)などの複雑で高品質な暗号化方式のように、これらが組み合わされることがよくあります。

平文は、鍵を使って暗号文に並べ替えることができ、ジグソーパズルのピースをシャッフルするように文字の順序が混ぜられます。文字の並び方は無数にあるため、結果として得られるメッセージを鍵なしで解読するのは困難です。

たとえば、平文「THIS IS WIKIPEDIA」は「TWDIP SIHII IKASE」に暗号化できます。キーなしで暗号化されたメッセージを解読するために、攻撃者は DIATHESIS、DISSPATE、WIDTH などの可能性のある単語やフレーズを推測しようとしますが、文字と単語の組み合わせが多数あるため、平文を再構築するには時間がかかります。対照的に、キーを持っている人はメッセージを簡単に再構築できます。

暗号キー
1 4 5 3 2 6 シーケンス（キー文字はアルファベット順）
THISIS 平文
ウィキペ
日数 * * *

列ごとの暗号文:
  #1 TWD、#2 IP、#3 SI、#4 HII、#5 IKA、#6 SE
読みやすくするために 5 つのグループに分けられた暗号文:
  トゥディップ シヒ イカセ

実際には、このように短く、予測可能なキーワードを含むメッセージは、暗号解読技術によってほぼ即座に解読されます。転置暗号にはいくつかの脆弱性があり (以下の「検出と暗号解読」のセクションを参照)、暗号化プロセスでの小さなミスによって暗号文全体が無意味になる可能性があります。

しかし、長いメッセージ（100～200文字以上）、予測不可能な内容、メッセージごとに固有のキー、強力な転置法など、適切な条件が満たされると、さらなる情報なしに正しい単語を推測することは計算上不可能になる可能性があります。歴史的な暗号の解読に関する著書の中で、Elonka DuninとKlaus Schmehは、二重列転置（以下を参照）を「知られている中で最も優れた手動暗号の1つ」と説明しています。^[1]

レール フェンス暗号は、暗号化方法からその名前が付けられた転置暗号の一種です。レール フェンス暗号では、平文は架空のフェンスの連続する「レール」に下向きに斜めに書き込まれ、一番下まで来たら上に移動します。次に、メッセージは行ごとに読み取られます。たとえば、3 つの「レール」と「WE ARE DISCOVERED FLEE AT ONCE」というメッセージを使用すると、暗号化者は次のように書きます。

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .

そして次のように読み上げます。

ウェクルル ティールド ソエフ エアオカ イヴデン

(暗号では、エラーを回避するために暗号文を 5 つのブロックに分割しています。これは、暗号をより読みやすくするためによく使用される手法です。スペースは平文内のスペースとは関係がないため、平文に関する情報は伝達されません。)

レールフェンス暗号は、古代ギリシャ人が使用した転置暗号を生成する機械的システムであるスキュタレー（「スキタレー」と発音）のパターンに似ています。このシステムは、円筒と円筒に巻き付けられたリボンで構成されていました。暗号化するメッセージは、巻き付けられたリボンに書かれていました。リボンを円筒からほどくと、元のメッセージの文字が並べ替えられます。しかし、リボンが暗号化した円筒と同じ直径の円筒に巻き戻されると、メッセージは簡単に解読されました。^[2]前と同じ例を使用して、円筒の半径がその円周に3文字しか収まらない場合、暗号作成者は次のように書きます。

W . . E . . A . . R . . E . . D . . I . . S . . C
. O . . V . . E . . R . . E . . D . . F . . L . .
. . E . . E . . A . . T . . O . . N . . C . . E .

この例では、シリンダーは水平に走行し、リボンは垂直に巻き付けられています。したがって、暗号作成者は次のように読み取ります。

ようこそ！

ルート暗号では、まず平文が指定された次元のグリッドに書き出され、次にキーで指定されたパターンで読み取られます。たとえば、rail fenceに使用したのと同じ平文を使用すると、次のようになります。

ライター
イースヴェラン
アドセドエックス

キーは「右上から時計回りに内側に螺旋状に」指定するかもしれません。その場合、暗号文は次のようになります。

EJXCTEDEC DAEWRIORF EONALEVSE

ルート暗号には、柵よりも多くのキーがあります。実際、適度な長さのメッセージの場合、可能なキーの数は、現代の機械でも数え切れないほど多くなる可能性があります。ただし、すべてのキーが同じように優れているわけではありません。ルートの選択が適切でない場合は、平文のチャンクが多すぎたり、テキストが単純に逆になったりするため、暗号解読者にルートの手がかりを与えてしまいます。

ルート暗号のバリエーションとして、アメリカ南北戦争中に北軍が使用したユニオン ルート暗号があります。これは通常のルート暗号とほとんど同じように機能しますが、個々の文字ではなく単語全体を転置します。これにより、非常に機密性の高い単語が露出してしまうため、そのような単語は最初にコードで隠されます。暗号係は、暗号文を面白くするために、空語全体を追加することもあります。^[要出典]

17 世紀半ば、サミュエル・モーランドが初期の柱状転置法を考案しました。この転置法はその後さらに発展し、19 世紀後半から 20 世紀にかけて非常に普及し、フランス軍、日本の外交官、ソ連のスパイなどがこの原理を採用しました。

列転置では、メッセージは固定長の行に書き出され、次に列ごとに再度読み出され、列はランダムな順序で選択されます。行の幅と列の順列は、通常、キーワードによって定義されます。たとえば、キーワードZEBRASの長さは 6 (つまり行の長さは 6) で、順列はキーワード内の文字のアルファベット順によって定義されます。この場合、順序は「6 3 2 4 1 5」になります。

通常の列転置暗号では、余分なスペースはヌルで埋められます。一方、不規則な列転置暗号では、スペースは空白のままです。最後に、キーワードで指定された順序で、列ごとにメッセージが読み取られます。たとえば、キーワードZEBRASとメッセージWE ARE DISCOVERED. FLEE AT ONCE を使用するとします。通常の列転置暗号では、これを次のようにグリッドに書き込みます。

6 3 2 4 1 5
着用
イスコヴェ
レドゥル
イートン
EQKJEU

5 つのヌル文字 ( QKJEU ) を提供すると、これらの文字は不完全な列を埋めるだけでメッセージの一部ではないため、ランダムに選択できます。暗号文は次のように読み取られます。

EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

不規則なケースでは、列は null で完了しません。

6 3 2 4 1 5
着用
イスコヴェ
レドゥル
イートン
え

結果として、次の暗号文が生成されます。

EVLNA CDTES EAROF ODEEC WIREE

これを解読するには、受信者はメッセージの長さをキーの長さで割って、暗号化グリッドの形状を割り出し、グリッドの行数を見つけなければなりません。グリッドの最後の行の長さは、その余りで決まります。キーはグリッドの上に書かれ、暗号文はキーの文字で指定された順序でグリッドの列に書かれます。平文は行に表示されます。最初の列に書き込んだ後の上記の暗号文の部分的な解読は次のとおりです。

6 3 2 4 1 5
. . . . E .
. . . . V .
. . . . L .
. . . . N .
。

バリエーションとして、メッセージはキーの長さのセグメントにブロックされ、各セグメントに同じ順列（キーによって指定）が適用されます。これは、列ではなく行で読み取られる列転置に相当します。

列転置は、少なくとも 1950 年代までは、より複雑な暗号の構成要素として本格的な目的で使用され続けました。

単一の列転置は、列の長さを推測し、メッセージを列に書き出し（ただし、キーがまだわかっていないため、順序は間違っています）、次に可能性のあるアナグラムを探すことで攻撃できます。したがって、それをより強力にするために、二重転置がよく使用されました。これは、単に列転置を 2 回適用したものです。両方の転置に同じキーを使用することも、2 つの異なるキーを使用することもできます。

次の例では、キーJANEAUSTENとAEROPLANES を使用して、次のプレーンテキストを暗号化します。「転置暗号は、文字をパズルのピースのように混ぜ合わせて、解読不可能な配置を作成します。」

• 
  ステップ 1:プレーンテキスト メッセージが最初のグリッド (キー JANEAUSTEN を持つ) に書き込まれます。
• 
  列はキーに従ってアルファベット順に読み取られ、次のグリッドに進みます (手順 2 を参照)。
• 
  ステップ 2:ステップ 1 の列が 2 番目のグリッド (キー AEROPLANES を持つ) に書き込まれます。
• 
  列はキーに従ってアルファベット順に読み取られ、次のグリッドに送られます (手順 3 を参照)。
• 
  ステップ 3:暗号文は、多くの場合、RIAES NNELI EEIRPなどのように 5 つのブロックで書き出されます。

色は、各転置ステップで文字がどのようにスクランブルされるかを示しています。1 つのステップではわずかな再配置しか発生しませんが、グリッドの最後の行が不完全な場合、2 番目のステップでは大きなスクランブル効果が発生します。

例として、前のセクションの不規則な列転置の結果を取得し、別のキーワードSTRIPEを使用して 2 番目の暗号化を実行すると、順列「564231」が生成されます。

5 6 4 2 3 1
エヴルナック
DTESEA
ロフォデ
ECワイヤー
え

前と同様に、これを列ごとに読み取ると暗号文が得られます。

CAEEN SOIAE DRLEF WEDRE EVTOC

まったく同じ長さの複数のメッセージが同じキーを使用して暗号化されている場合、それらを同時にアナグラム化することができます。これにより、メッセージの復元とキーの復元の両方が可能になります (そのため、それらのキーを使用して送信された他のすべてのメッセージを読み取ることができます)。

第一次世界大戦中、ドイツ軍は二重列転置暗号を使用しており、鍵はめったに変更されなかった。この暗号はフランス人によって定期的に解読され、ユーブチと名付けられた。フランス人は同じ長さのメッセージを複数傍受すると、通常は数日で鍵を素早く見つけることができた。しかし、フランスの成功は広く知られるようになり、ル・マタン紙に掲載された後、ドイツは1914年11月18日に新しい暗号システムに変更した。^[3]

第二次世界大戦中、二重転置暗号はオランダのレジスタンス組織、フランスのマキ、ヨーロッパの地下活動の管理を担当していたイギリスの特殊作戦執行部（SOE）によって使用されました。 ^{[4]また、アメリカ}戦略諜報局のエージェントによっても使用され、 ^[5]ドイツ陸軍と海軍の緊急暗号としても使用されました。

VIC 暗号が発明されるまで、二重転置は、困難な現場状況下でエージェントが確実に操作できる最も複雑な暗号であると一般に考えられていました。

二重転置暗号は、2つの鍵の長さの積と同じ長さの鍵を持つ単一の転置として扱うことができる。^[6]

2013年後半、著者が解読不可能とみなしていた二重転置問題が、ジョージ・ラスリーによって分割統治法を用いて解読され、各転置が個別に攻撃された。^[7]

1902 年にエミール・ヴィクトル・テオドール・ミスコフスキーが提案した列転置の変形形式では、キーワードに繰り返し文字が必要です。通常、キーワード文字のその後の出現は、アルファベット順で次の文字として扱われます。たとえば、キーワード TOMATO は数値キー文字列「532164」を生成します。

Myszkowski 転置では、繰り返し使用されるキーワード文字に同じ番号が付けられ、TOMATO ではキー文字列は「432143」になります。

4 3 2 1 4 3
着用
イスコヴェ
レドゥル
イートン
え

一意の番号を持つプレーンテキスト列は下方向に転記され、繰り返し番号を持つプレーンテキスト列は左から右方向に転記されます。

ROFOA CDTED SEEEA CWEIV RLENE

破壊転置暗号^[8]は、行列の行を不規則に埋めることで転置パターンをさらに複雑にします。つまり、いくつかのスペースを意図的に空白のままにしたり（またはラスターシュルッセル44のように黒く塗りつぶしたり）、後で平文の別の部分やランダムな文字で埋めたりします。^[8]

この方法（ルイジ・サッコ将軍^[9]に由来）は、平文がキー番号が現在の行番号に等しい列に到達すると、新しい行を開始する。これにより、不規則な行の長さが生成される。例えば、

FOREVERJIGSAW < キー
4 8 9 2 12 3 10 7 6 5 11 1 13 番号の後の空欄:
最も複雑 * 1
ヘトル * * * * * * * * * 2
回答 * * * * * * * 3
私 * * * * * * * * * * * * 4
パターン * * * 5
NLIKEACOM * * * * 6
B _ _ _ _ _ _ _ * * * * * 7

次に、TPRPN、KISAA、CHAIT、NBERT、EMATO などの通常の列転置に従って列が削除されます。

もう一つのシンプルなオプション^[10]は、数字の順序に従って空白を配置するパスワードを使用することです。たとえば、「SECRET」は「5,2,1,4,3,6」のシーケンスにデコードされ、マトリックスの 5 番目のフィールドを消してから、もう一度数えて 2 番目のフィールドを消します。次の例は、列キー「CRYPTO」を使用して列転置用に設定されたマトリックスで、破壊キー「SECRET」(アスタリスクでマーク) に従って消されたフィールドで埋められ、その後、残りのスペースに「発見されたらすぐに逃げてください」というメッセージが配置されます。結果として得られる暗号文 (転置キーに従って列が読み取られる) は、「WCEEO ERET RIVFC EODN SELE ADA」です。

暗号
1 4 6 3 5 2
私たちは
* * 無効 *
カバー
ED * FLE
食べる
一度 *

転置暗号の別の形式は、グリル、つまり切り抜きのある物理的なマスクを使用する。これは、グリルのサイズで指定された期間にわたって非常に不規則な転置を生成できるが、通信者は物理的な鍵を秘密にしておく必要がある。グリルは 1550 年に初めて提案され、第一次世界大戦の最初の数か月間は軍隊で使用されていた。

転置は個々のシンボルの頻度には影響しないため、単純な転置は暗号解読者が頻度を数えることで簡単に検出できます。暗号文が平文と非常によく似た頻度分布を示す場合、それは転置である可能性が最も高くなります。

一般的に、転置法はアナグラムに対して脆弱である。アナグラムとは、暗号文の一部をスライドさせて、英語や平文が書かれた言語の単語のアナグラムに似た部分を探し、そのアナグラムを解くことである。このようなアナグラムが見つかると、転置パターンに関する情報が明らかになり、結果的に拡張できる。より単純な転置法は、正しいキーに非常に近いキーが、意味不明な文字が点在する判読可能な平文の長い部分を明らかにするという性質に悩まされることが多い。その結果、このような暗号は、遺伝的アルゴリズム^[11]や山登りアルゴリズム^[12]などの最適解探索アルゴリズムに対して脆弱である可能性がある。 [13 ^]

転置暗号を使用してエンコードされたメッセージを攻撃するための具体的な方法はいくつかあります。これには次のものが含まれます。

1. 既知平文攻撃:平文の既知または推測された部分 (名前、場所、日付、数字、フレーズなど) を使用して、転置を実行するために使用される列の順序や平文のトピックの可能性をリバース エンジニアリングします。
2. ブルートフォース攻撃:キーが辞書の単語や書籍またはその他の公開ソースのフレーズから派生している場合、数十億の可能性のある単語、単語の組み合わせ、フレーズをキーとして試行することで、ブルートフォース攻撃によって解決できる可能性があります。
3. 深度攻撃:同じ長さの 2 つ以上のメッセージが同じキーでエンコードされている場合、行われた転置手順を知る必要なく、メッセージの同じ場所に意味のあるテキストが表示されるまで、メッセージを整列させてアナグラム化できます。
4. 統計的攻撃:言語における 2 文字、3 文字などの組み合わせの頻度に関する統計は、どの変更が最も可能性の高い組み合わせを生み出すかに基づいて、可能な転置を徐々に元に戻すアルゴリズムのスコアリング関数に情報を提供するために使用できます。たとえば、2 文字のペア QU は英語のテキストでは QT よりも一般的であるため、暗号解読者は QU を一緒に配置する転置を試みます。

3番目の方法は1878年に数学者のエドワード・S・ホールデンとニューヨーク・トリビューンのジャーナリスト、ジョン・RG・ハサードとウィリアム・M・グロブナーによって開発され、彼らは1876年の大統領選挙中に民主党と南部諸州の工作員との間で交わされた電報を解読し、1878年から1879年の議会選挙に影響を与えた買収の事実を証明した。^[14]

ドイツの転置暗号の解読に関する詳細な説明は、ハーバート・ヤードリーの「アメリカのブラック・チェンバー」の第 7 章に記載されています。

ゾディアック・キラーが使用した「Z-340」と呼ばれる暗号は、文字の代わりに63の異なる記号を使用し、斜めの「ナイトムーブ」転置を施した三角形のセクションに構成されており、2020年12月5日に民間の国際チームが特殊なソフトウェアを使用して解読するまで、51年以上も解読されていませんでした。^[15]

転置は、評価方法などの他の技術と組み合わせられることがよくあります。たとえば、単純な置換暗号と列転置を組み合わせると、両方の弱点を回避できます。高頻度の暗号文シンボルを高頻度の平文文字に置き換えても、転置があるため平文のチャンクは明らかになりません。転置のアナグラム化は、置換があるため機能しません。この技術は、分数化と組み合わせると特に強力になります (以下を参照)。欠点は、このような暗号は、より単純な暗号よりもかなり手間がかかり、エラーが発生しやすいことです。

転置は、分数化、つまり各平文記号を2つ以上の暗号文記号に分割する準備段階と併用すると特に効果的です。たとえば、平文のアルファベットをグリッドに書き出し、メッセージ内のすべての文字をその座標に置き換えることができます（ポリビウス方陣とストラドリングチェッカーボードを参照）。^[16] 分数化の別の方法は、メッセージをモールス信号に変換するだけで、ドットとダッシュだけでなくスペースの記号も使用できます。^[17]

このように分割されたメッセージを転置すると、個々の文字の構成要素はメッセージ内で広く分離され、クロード・E・シャノンの拡散が達成されます。分割と転置を組み合わせた暗号の例には、二分暗号、三分暗号、ADFGVX暗号、VIC暗号などがあります。

もう 1 つの選択肢は、各文字をバイナリ表現に置き換え、それを転置し、新しいバイナリ文字列を対応する ASCII 文字に変換することです。バイナリ文字列を ASCII 文字に変換する前に、スクランブル処理を複数回ループすると、解読が難しくなる可能性があります。多くの最新のブロック暗号では、この単純なアイデアに関連する、より複雑な形式の転置が使用されています。

• 換字暗号
• バン（ユニット）
• 暗号に関するトピック

• カーン、デイビッド。『暗号解読者：秘密文書の物語』改訂改訂版。スクリブナー社、1996年。
• ヤードリー、ハーバート。アメリカ黒人商工会議所。ボブズ・メリル社、1931年。