転置暗号

二重列転置暗号のステップバイステップのプロセス。

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

一般原則

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

例えば、「THIS IS WIKIPEDIA」という平文は、「TWDIP SIHII IKASE」と暗号化できます。鍵なしで暗号化されたメッセージを解読するために、攻撃者は「DIATHESIS」「DISSPATE」「WIDTH」といった単語やフレーズを推測することができますが、文字と単語の組み合わせが多数存在するため、平文を復元するにはある程度の時間がかかります。一方、鍵を持っている人は、メッセージを簡単に復元できます。

暗号キー 1 4 5 3 2 6 シーケンス（キー文字はアルファベット順） これは平文です ウィキペ 直径 * * * 列ごとの暗号文: #1 TWD、#2 IP、#3 SI、#4 HII、#5 IKA、#6 SE 読みやすくするために 5 つのグループに分けられた暗号文: トゥディップ・シヒ・イカセ 

実際には、このように短く、予測可能なキーワードを含むメッセージは、暗号解読技術によってほぼ即座に解読されてしまいます。

転置暗号にはいくつかの脆弱性があり (以下の「検出と暗号解読」のセクションを参照)、暗号化プロセスでの小さな間違いによって暗号文全体が意味をなさなくなる可能性があります。

しかし、長いメッセージ（例えば100～200文字以上）、予測不可能な内容、メッセージごとに固有のキー、強力な転置法など、適切な条件が満たされると、追加情報なしに正しい単語を推測することは計算的に不可能になる可能性があります。エロンカ・ダニンとクラウス・シュメーは、歴史的暗号の解読に関する著書の中で、二重列転置法（下記参照）を「知られている中で最も優れた手動暗号の一つ」と評しています。^{[ 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 . . 

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

WECRL TEERD SOEEF EAOCA IVDEN 

(暗号文は、エラーを回避するために 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 . 

この例では、円筒は水平に回転し、リボンは垂直に巻き付けられています。したがって、暗号解読者は次のように読み取ります。

WOEEV EAEAR RTEEO DDNIF CSLEC 

ルート暗号

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

ライター イースヴェランジ ADCEDETCX 

鍵は「右上から時計回りに内側へ螺旋状に進む」と指定するとします。この場合、暗号文は次のようになります。

EJXCTEDEC DAEWRIORF EONALEVSE 

ルート暗号は、鉄道柵よりもはるかに多くの鍵を持ちます。実際、適度な長さのメッセージの場合、鍵の数は現代の機械でさえも数え切れないほど多くなる可能性があります。しかし、すべての鍵が同じように優れているわけではありません。ルートの選択を誤ると、平文が大量に残ったり、テキストが単純に反転されたりすることがあり、暗号解読者にルートの手がかりを与えてしまいます。

ルート暗号の派生形として、アメリカ南北戦争中に北軍が使用したユニオン・ルート暗号があります。これは通常のルート暗号とほぼ同じ仕組みですが、個々の文字ではなく単語全体を転置します。この方法では機密性の高い単語が露出してしまうため、まずそのような単語は暗号で隠蔽されます。暗号係は空語全体を追加することもあり、これは暗号文をユーモラスにするためによく選ばれました。

列方向の転置

暗号化

列転置では、メッセージは固定長の行に書き出され、その後列ごとに読み出されます。列はランダムな順序で選択されます。行の幅と列の順列は通常、キーワードによって定義されます。例えば、キーワード「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 着用済み イスコブ レッドフル イートン E 

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

EVLNA CDTES EAROF ODEEC WIREE 

復号化

これを解読するには、受信者は暗号化グリッドの形状を解明する必要があります。メッセージ長を鍵長で割ってグリッドの行数を求めます。グリッドの最終行の長さは、その余りで求められます。鍵はグリッドの上部に書き込まれ、暗号文は鍵の文字の順序に従ってグリッドの列に書き込まれます。平文は行に表示されます。上記の暗号文を最初の列に書き込んだ後の部分的な解読は以下の通りです。

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

バリエーションとして、メッセージはキー長のセグメントに分割され、各セグメントに同じ順列（キーによって指定）が適用されます。これは、列ではなく行単位で読み出す列転置と同等です。

歴史

17世紀半ば、サミュエル・モーランドは初期の柱状転置法を考案しました。この手法はその後2世紀にわたってさらに発展し、19世紀後半から20世紀にかけて、特にフランス軍、日本の外交官、ソ連の諜報機関などで広く利用されるようになりました。

ジョン・ファルコナーの『暗号解読法』（1685年）には、鍵付き列転置法に関する英語で書かれた最古の説明の一つが含まれている。ファルコナーはこの暗号の起源については何も述べていないが、平文を長方形の格子に書き、最終行を空文字で埋め、キーワードによって決まる秘密の順序で列を取り出す方法を説明している。^{[ 3 ]}

さらに重要なのは、ファルコナーが暗号解読の有効な手法を提示していることです。彼は、解読者が試行錯誤によってグリッドの高さを変え、列の順序を変更することで判読可能なテキストが出現することを示し、暗号が通常の文字頻度を維持するため、検出されやすいことを指摘しています。彼は、文字頻度は言語によって異なるため、テキストの内容を知らなくても、このような文字頻度を用いてテキストの言語を特定できる可能性があると指摘しています。ファルコナーは二重転置や、最終列にヌル文字が与えられない暗号の解読方法については言及していません。これは、これらの手法が当時は広く普及していなかったことを示唆しています。

列転置はその後、より複雑なシステム（最も有名なのは、フランス軍および外交機関、第一次世界大戦および第二次世界大戦中の日本とドイツの暗号、そしてソ連の諜報員によって使用された二重転置）に組み込まれ、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 EVLNAC DTESEA ロフォデ ECWIRE E 

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

CAEEN SOIAE DRLEF WEDRE EVTOC 

全く同じ長さの複数のメッセージが同一の鍵を用いて暗号化されている場合、それらを同時にアナグラム化することができます。これにより、メッセージと鍵の両方が復元される可能性があります（つまり、それらの鍵を用いて送信された他のすべてのメッセージも解読可能になります）。

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

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

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

暗号解読

二重転置暗号は、2つの鍵の長さの積に等しい長さの鍵を持つ単一の転置暗号として扱うことができる。^{[ 7 ]}

2013年後半、作成者自身が解読不可能とみなしていた二重転置問題が、ジョージ・ラスリーによって分割統治法を用いて解読された。この手法では、それぞれの転置を個別に攻撃する。^{[ 8 ]}

転置暗号で暗号化された古い実際の会話が公開されています。そのため、転置暗号の解読に興味のある人は、実際の会話で練習することができます。^{[ 9 ]}

ミシュコフスキー転置

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

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

4 3 2 1 4 3 着用済み イスコブ レッドフル イートン E 

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

ROFOA CDTED SEEEA CWEIV RLENE 

転座の阻害

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

コームアプローチ

この手法（ルイジ・サッコ将軍^{[ 11 ]}に帰属）では、平文がキー番号が現在の行番号と等しい列に到達すると、新しい行が開始されます。これにより、行の長さは不規則になります。例えば、

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

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

数値シーケンスアプローチ

もう一つのシンプルな選択肢^{[ 12 ]}は、数字の並びに従って空白を配置するパスワードを使用することです。例えば、「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年に初めて提案され、第一次世界大戦の最初の数か月間は軍事的に使用されていました。

検出と暗号解読

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

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

転置暗号を用いて暗号化されたメッセージを攻撃する方法はいくつかあります。具体的には以下のものがあります。

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

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

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

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

組み合わせ

転置は、評価法などの他の手法と組み合わせられることがよくあります。例えば、単純な換字暗号と列転置を組み合わせることで、両方の弱点を回避できます。暗号文で頻繁に使用される記号を平文で頻繁に使用される文字に置き換えても、転置があるため、平文の一部が明らかになることはありません。また、転置をアナグラム化しても、転置があるために機能しません。この手法は、分数化（下記参照）と組み合わせると特に強力になります。欠点は、このような暗号は、より単純な暗号に比べて、はるかに手間がかかり、エラーが発生しやすいことです。

分別

転置は、分数化、つまり平文の各記号を2つ以上の暗号文の記号に分割する前段階と組み合わせると特に効果的です。例えば、平文のアルファベットを格子状に書き出し、メッセージ内の各文字をその座標に置き換えることができます（ポリビウス方陣とストラドリングチェッカーボードを参照）。^{[ 18 ]} 分数化の別の方法として、メッセージをモールス信号に変換し、点とダッシュだけでなくスペースを表す記号も用いる方法があります。^{[ 19 ]}

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

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

参照

• 換字暗号
• 禁止（ユニット）
• 暗号学のトピック

注記

1. Elonka, Dunin; Schmeh, Klaus (2020). Codebreaking: A Practical Guide . Robinson. p. 247. ISBN 978-1-4721-4421-8. OCLC  1158165142 .
2. スミス、ローレンス・ドワイト（1955）[1943]、「暗号／秘密文書の科学」、ニューヨーク：ドーバー、pp.16、92–93
3. ファルコナー、ジョン（1685年）『暗号解読術：鍵なしで秘密情報を明かす技術』ロンドン：ダニエル・ブラウン。62ページ。
4. カーン、301-304ページ。
5. カーン、535ページと539ページ。
6. カーン、539ページ。
7. バーカー、ウェイン (1995). 『二重転置暗号の暗号解読：問題とコンピュータプログラムを含む』 エーゲアン・パーク・プレス.
8. Lasry, George (2014-06-13). 「分割統治法による二重転置問題の解決」Cryptologia . 38 (3): 197– 214. doi : 10.1080/01611194.2014.915269 . S2CID 7946904 . 
9. 「古典暗号による暗号化テキスト」Archive.org。
10. Mahalakshmi, B. (2016年6月). 「セキュリティ強化のための破壊的転置暗号の概要」(PDF) . International Journal of Computer Applications . 143 (13): 9– 12. doi : 10.5120/ijca2016910308 . 2018年6月4日時点のオリジナルよりアーカイブ(PDF) . 2021年1月7日閲覧。
11. サヴァード、ジョン. 「転置法」 .暗号大要. 2023年6月27日閲覧。
12. jdege (2014年11月11日). 「A simple disrupted transposition」 . 2021年1月7日閲覧。
13. マシューズ, ロバート AJ (1993年4月). 「暗号解読における遺伝的アルゴリズムの利用」. Cryptologia . 17 (2): 187– 201. doi : 10.1080/0161-119391867863 .
14. Lasry, George; Kopal, Nils; Wacker, Arno (2014-07-03). 「分割統治法による二重転置問題の解決」 . Cryptologia . 38 (3): 197– 214. doi : 10.1080/01611194.2014.915269 . ISSN 0161-1194 . S2CID 7946904 .  
15. Lasry, George; Kopal, Nils; Wacker, Arno (2016-07-03). 「長い鍵を持つ列転置暗号の暗号解読」 . Cryptologia . 40 (4): 374– 398. doi : 10.1080/01611194.2015.1087074 . ISSN 0161-1194 . S2CID 21179886 .  
16. 「[3.0] フィールド暗号の台頭」 vc.airvectors.net . 2024年1月11日閲覧。
17. 「ゾディアック・キラーの暗号、51年間も捜査官の手から逃れて解読される」 arstechnica.com 2020年12月12日2020年12月12日閲覧。
18. ダニエル・ロドリゲス＝クラーク 「分断暗号文の転置」
19. ジェームズ・ライオンズ 「分数モールス暗号」。

参考文献

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