換字暗号

暗号学 において、置換暗号とは、キーを使用して、定義された方法で平文の単位を暗号文に置き換える暗号化方法です。「単位」は、単一の文字（最も一般的）、文字のペア、文字の3つ組、これらの組み合わせなどです。受信者は、逆置換プロセスを実行してテキストを解読し、元のメッセージを抽出します。

置換暗号は転置暗号と比較することができます。転置暗号では、平文の単位は異なる、通常は非常に複雑な順序で並べ替えられますが、単位自体は変更されません。対照的に、置換暗号では、平文の単位は暗号文内で同じ順序で保持されますが、単位自体は変更されます。

置換暗号にはさまざまな種類があります。暗号が単一の文字に対して機能する場合、それは単純置換暗号と呼ばれます。より大きな文字のグループに対して機能する暗号は、ポリグラフィック暗号と呼ばれます。モノアルファベット暗号は、メッセージ全体にわたって固定の置換を使用しますが、ポリアルファベット暗号は、メッセージ内のさまざまな位置で多数の置換を使用します。ポリアルファベット暗号では、平文の単位が暗号文の複数の可能性の 1 つにマッピングされ、その逆も同様です。

単純換字式暗号の解読法について初めて公表された説明は、アル・キンディーが西暦850年頃に書いた『暗号文解読に関する手稿』の中で述べられています。彼が説明した方法は現在、頻度分析として知られています。

単一の文字を個別に置き換えること (単純置換) は、アルファベットを何らかの順序で書き出して置換を表すことによって示されます。これは置換アルファベットと呼ばれます。暗号アルファベットは、シフトまたは反転 (それぞれシーザー暗号とアトバシュ暗号を作成) したり、より複雑な方法で混ぜ合わせたりすることができ、その場合は混合アルファベットまたは乱れたアルファベットと呼ばれます。伝統的に、混合アルファベットは、最初にキーワードを書き、その中の重複する文字を削除してから、残りのアルファベットの文字をすべて通常の順序で書き込むことによって作成できます。

このシステムを使用すると、キーワード「zebras」から次のアルファベットが得られます。

メッセージ

すぐに逃げてください。見つかりました！

暗号化する

SIAA ZQ LKBA。 VA ZOA RFPBLUAOAR!

通常、暗号文は固定長のブロックで書かれ、句読点やスペースは省略されます。これは、平文から単語の境界を隠し、送信エラーを回避するために行われます。これらのブロックは「グループ」と呼ばれ、追加のチェックとして「グループ数」(つまり、グループの数) が与えられることもあります。5 文字のグループがよく使用されますが、これはメッセージが電信で送信されていた時代から使われています。

SIAAZ QLKBA VAZOA RFPBL UAOAR

メッセージの長さが 5 で割り切れない場合は、末尾に「ヌル」が埋め込まれることがあります。これは、明らかに意味不明な文字に復号化される任意の文字であり、受信者が簡単に見つけて破棄できます。

暗号文のアルファベットは平文のアルファベットと異なる場合があります。たとえば、ピッグペン暗号では、暗号文はグリッドから派生した一連の記号で構成されます。次に例を示します。

ただし、このような機能はスキームのセキュリティにほとんど影響を与えません。少なくとも、奇妙な記号のセットは AZ アルファベットに書き直して通常どおり処理できます。

営業担当者向けのリストやカタログでは、数字を文字に置き換える非常に単純な暗号化が使用されることがあります。

例: 120 を表す場合は MAT、5256 を表す場合は PAPR、7803 を表す場合は OFTK が使用されます。

混合置換アルファベットを作成する従来のキーワード方式はシンプルですが、アルファベットの最後の文字 (ほとんどが低頻度) が最後に残る傾向があるという重大な欠点があります。混合アルファベットを構築するより強力な方法は、置換アルファベットを完全にランダムに生成することです。

置換可能なアルファベットの数は非常に多い（26! ≈ 2 ^88.4、つまり約88 ビット）が、この暗号はあまり強力ではなく、簡単に解読される。メッセージが妥当な長さであれば（下記参照）、暗号解読者は暗号文の頻度分布を解析することで、最も一般的な記号の意味を推測できる。これにより部分的な単語を形成し、それを暫定的に埋めていくことで、（部分的な）解を徐々に拡張することができる（このデモンストレーションについては頻度解析を参照）。場合によっては、文字のパターンから基になる単語を判別できることもある。たとえば、英語の単語tater、ninth、paper はすべてABACD というパターンを持っている。新聞の 暗号パズルのように、娯楽としてこのような暗号を解く人は多い。

英語の単一性距離によると、混合アルファベットの単純な置換を解読するには 27.6 文字の暗号文が必要です。実際には、通常約 50 文字が必要ですが、異常なパターンが見つかった場合は、それより少ない文字で解読できるメッセージもあります。他のケースでは、平文がほぼ平坦な頻度分布を持つように工夫することができ、その場合は暗号解読者ははるかに長い平文を必要とします。

かつて一般的だった換字式暗号の変種に、ノメンクレーターがある。来訪した高官の称号を発表する公務員にちなんで名付けられたこの暗号は、文字、音節、単語の換字表（同音異義語となることもある）を含む小さなコードシートを使用し、通常は記号を数字に変換する。当初、コード部分は重要人物の名前に限定されていたため、この暗号の名前の由来となったが、後年、一般的な単語や地名も数多くカバーするようになった。単語全体（現代の用語でコードワード）と文字（現代の用語で暗号）を表す記号は、暗号文では区別されなかった。フランスのルイ14世が使用したロシニョールの大暗号もその1つである。

ノメンクレーターは、15 世紀初頭から 18 世紀後半にかけて、外交文書、スパイ活動、高度な政治的陰謀の標準的な手段であった。陰謀者の多くは、当時も今も、それほど高度な暗号技術を持っていなかった。16 世紀半ばまでに政府 諜報部の 暗号解読者はノメンクレーターを体系的に解読し、1467 年以降はより優れたシステムが利用可能であったが、暗号解読に対する通常の対応は、単に表を大きくすることだった。18 世紀後半、システムが衰退し始めた頃には、50,000 個の記号を持つノメンクレーターもあった。^[要出典]

しかし、すべての命名法が解読されたわけではなく、今日でも、アーカイブされた暗号文の解読は歴史研究の有益な分野であり続けています。

置換暗号に対する頻度分析攻撃の難易度を高めるための初期の試みは、同音異義語によって平文の文字頻度を隠すことでした。これらの暗号では、平文の文字は複数の暗号文記号にマッピングされます。通常、最も頻度の高い平文記号には、頻度の低い文字よりも多くの同等の文字が与えられます。このようにして、頻度分布が平坦化され、分析が困難になります。

暗号文のアルファベットには 26 文字以上が必要になるため、より大きなアルファベットを発明するためにさまざまな解決策が採用されています。おそらく最も単純なのは、数字の置換「アルファベット」を使用することです。別の方法としては、既存のアルファベットを大文字、小文字、逆さまなどに変更する単純な方法があります。より芸術的ではありますが、必ずしもより安全というわけではありませんが、一部の同音異義語暗号では、完全に架空の記号で作られたアルファベットが採用されています。

ブック暗号はホモフォニック暗号の一種で、ビール暗号がその一例です。これは、1819年から1821年にかけて、独立宣言をキーとする暗号文を使って説明された埋蔵金の物語です。ここでは、暗号文の各文字が数字で表されていました。数字は、平文の文字を取得し、その文字で始まる独立宣言の単語を見つけ、独立宣言の中でのその単語の数字位置をその文字の暗号化形式として使用することで決定されました。独立宣言の単語の多くは同じ文字で始まっているため、その文字の暗号化は、独立宣言の中でその文字で始まる単語に関連付けられた数字のいずれかである可能性があります。暗号化されたテキスト文字X（数字）を解読するのは、独立宣言のX番目の単語を検索し、その単語の最初の文字を復号化文字として使用するのと同じくらい簡単です。

^{別の同音異義語暗号はスタール[2] [3]}によって記述され、暗号化によってコンピュータ内のデータシステムのセキュリティを確保しようとする最初の^{[引用が必要]}試みの1つでした。スタールは、特定の文字の同音異義語の数が文字の頻度に比例するように暗号を構築し、頻度分析をはるかに困難にしました。

マントヴァ公フランチェスコ1世ゴンザーガは1401年にシモーネ・ド・クレマとの書簡に同音換字暗号の最古の例を使用した。^{[4] [5]}

スコットランド女王メアリーは、エリザベス1世によって投獄されていた1578年から1584年にかけて、ミシェル・ド・カステルノーを含む同盟者との通信に、頻出する接頭辞、接尾辞、固有名詞のための命名子を用いた追加の暗号化を加えた同音異義語暗号を使用していた。^[6]

アル＝カルカシャンディ（1355-1418）の著作は、イブン・アル＝ドゥライヒム（1312-1359）の初期の著作に基づいており、暗号の置換と転置に関する最初の公開された議論と、平文の各文字に複数の置換文字が割り当てられる多アルファベット暗号の最初の説明が含まれていました。^[7]多アルファベット置換暗号は、後に1467年にレオーネ・バッティスタ・アルベルティによってディスクの形で説明されました。ヨハネス・トリテミウスは、著書「ステガノグラフィア」（古代ギリシャ語で「隠された文字」）で、現在ではより標準的な形式のタブローを紹介しました（以下を参照。1500年頃ですが、出版はずっと後になってからでした）。混合アルファベットを使用するより洗練されたバージョンは、1563年にジョヴァンニ・バッティスタ・デッラ・ポルタの著書「デ・フルティビス・リテララム・ノティス」（ラテン語で「書面の隠された文字について」）で説明されました。

多アルファベット暗号では、複数の暗号アルファベットが使用されます。暗号化を容易にするために、通常、すべてのアルファベットは、伝統的にタブローと呼ばれる大きな表に書き出されます。タブローは通常 26×26 であるため、26 個の完全な暗号文アルファベットが使用可能です。タブローを埋める方法と、次に使用するアルファベットを選択する方法によって、特定の多アルファベット暗号が定義されます。このような暗号は、十分に大きな平文に対して置換アルファベットが繰り返されるため、かつて考えられていたよりも解読が容易です。

最も人気があった暗号の 1 つは、ブレーズ・ド・ヴィジュネルの暗号です。1585 年に初めて公開され、1863 年まで解読不可能とみなされ、実際に一般にle chiffre indéchiffrable (フランス語で「解読不可能な暗号」) と呼ばれていました。

ヴィジュネル暗号では、表の最初の行に平文のアルファベットのコピーが記入され、後続の行は単に左に 1 つずつシフトされます。(このような単純な表はタブラ・レクタと呼ばれ、数学的には平文と鍵の文字を 26 で割った値に相当します。 ) 次に、キーワードを使用して、使用する暗号文のアルファベットを選択します。キーワードの各文字が順番に使用され、その後、先頭から再び繰り返されます。したがって、キーワードが「CAT」の場合、平文の最初の文字はアルファベット「C」で暗号化され、2 番目は「A」、3 番目は「T」、4 番目は再び「C」で暗号化され、以下同様に続きます。また、キーワードが「RISE」の場合、平文の最初の文字はアルファベット「R」、2 番目は「I」、3 番目は「S」、4 番目は「E」で暗号化され、以下同様に続きます。実際には、ヴィジュネルのキーは数語からなるフレーズになることが多かった。

1863年、フリードリヒ・カシスキは、ヴィジュネル暗号メッセージのキーワードの長さを計算できる方法（おそらくはクリミア戦争前にチャールズ・バベッジが秘密裏に独自に発見したもの）を発表した。この方法が確立されると、同じアルファベットで暗号化された暗号文の文字を抜き出し、いくつかの半独立な単純な置換として個別に攻撃できるようになった。1つのアルファベット内で文字が分離されていて完全な単語を形成しないという点で複雑だったが、通常はタブラ・レクタが使用されていたという点で単純だった。

そのため、今日でも、ヴィジュネル型暗号は、タブローに混合アルファベットが使用され、キーワードがランダムであり、暗号文の合計長がキーワードの長さの27.67倍未満である場合、理論的には解読が困難であるはずです。^[8]これらの要件は実際にはほとんど理解されていないため、ヴィジュネル暗号化メッセージのセキュリティは通常、期待されていたほど高くありません。

その他の注目すべき多アルファベット文字には以下のものがあります。

• Gronsfeld 暗号。これは Vigenère 暗号と同じですが、10 個のアルファベットのみが使用され、「キーワード」が数字になります。
• ボーフォート暗号。これは実質的にはヴィジュネル暗号と同じですが、タブラ・レクタが逆順に置き換えられており、数学的には暗号文 = 鍵 - 平文に相当します。この操作は自己逆であり、暗号化と復号化の両方に同じ表が使用されます。
• 周期性を避けるために平文と鍵を混合する自動鍵暗号。
• ランニングキー暗号。本や類似のテキストの一節を使用してキーを非常に長くします。

現代のストリーム暗号は、十分に抽象的な観点から見ると、キーストリームを可能な限り長く、予測不可能に することに全力を注いだ多アルファベット暗号の一種であるとも考えられます。

ポリグラフ置換暗号では、平文の文字を個別に置換するのではなく、より大きなグループで置換します。最初の利点は、頻度分布が個々の文字の分布よりもはるかに平坦であることです (ただし、実際の言語では実際には平坦ではありません。たとえば、スペイン語では「OS」は「RÑ」よりもはるかに一般的です)。2 番目に、記号の数が多いため、文字の頻度を効果的に分析するには、それに応じてより多くの暗号文が必要になります。

文字のペアを置換するには、676 個の記号からなる置換アルファベット ( ) が必要になります。前述の同じDe Furtivis Literarum Notisで、デッラ・ポルタは実際にそのようなシステムを提案しており、20 x 20 のタブロー (彼が使用していたイタリア語/ラテン語のアルファベットの 20 文字) に 400 個の固有のグリフが埋め込まれています。しかし、このシステムは非実用的で、実際には使用されなかったと思われます。 ${\displaystyle 26^{2}}$

最も古い実用的な二文字暗号（ペアワイズ・サブスティテューション）は、1854年にチャールズ・ホイートストン卿が発明した、いわゆるプレイフェア暗号である。この暗号では、5 x 5のグリッドに混合アルファベットの文字（通常はIとJの2つの文字が組み合わされている）が配置される。次に、文字のペアを長方形の2つの角として取り、他の2つの角を暗号文として使用することで、二文字のサブスティテューションをシミュレートする（図についてはプレイフェア暗号のメイン記事を参照）。重複した文字や同じ行または列にあるペアについては、特別なルールが適用される。プレイフェアは、ボーア戦争から第二次世界大戦まで軍事的に使用されていた。

1901 年にフェリックス・デラステッレによって、二分暗号と四分方暗号(どちらも二分法) および三分暗号(おそらく最初の実用的な三分法) を含む、他のいくつかの実用的なポリグラフィック暗号が導入されました。

ヒル暗号は、1929 年にレスター・S・ヒルによって発明され、線形代数を使用して同時にはるかに大きな文字のグループを組み合わせることができるポリグラフィック置換です。各文字は、 26 進数の数字として扱われます。つまり、A = 0、B = 1 などです。(バリエーションでは、基底を 素数にするために 3 つの記号が追加されます。 ) n 文字のブロックは、 n次元のベクトルと見なされ、26 を法とするanxn行列に掛けられます。行列の要素が鍵であり、行列が で逆行列可能である限りランダムである必要があります(復号が可能であることが保証されるため)。6 次元のヒル暗号の機械バージョンは、1929 年に特許を取得しました。^[9]${\displaystyle \mathbb {Z} _{26}^{n}}$

ヒル暗号は完全に線形であるため既知平文攻撃に対して脆弱であり、この攻撃を阻止するには何らかの非線形ステップと組み合わせる必要があります。ヒル暗号のような、ますます広くなる弱い線形拡散ステップと非線形置換ステップを組み合わせると、最終的には置換-順列ネットワーク（例：フェイステル暗号）につながるため、この極端な観点からは、現代のブロック暗号をポリグラフィック置換の一種と 見なすことが可能です。

第一次世界大戦の頃からコンピュータが広く普及するまでの間（政府によっては1950年代から1960年代頃、組織によっては10年以上後、個人の場合は1975年以降）、多字体換字式暗号の機械的な実装が広く使用されていました。同時期に同様のアイデアを思いついた発明者もおり、ローター式暗号機は1919年に4件の特許を取得しました。その結果生まれた暗号機の中で最も重要なのはエニグマで、特に1930年頃からドイツ軍が使用したバージョンが有名です。連合国もローター式暗号機（SIGABAやTypexなど）を開発し使用していました。

これらはすべて、複数の文字ディスクの回転から生じる膨大な数の組み合わせの中から、置換文字が電気的に選択されるという点で類似していた。 平文の文字が暗号化されるたびに 1 つ以上のディスクが機械的に回転するため、使用されるアルファベットの数は天文学的な数に達した。 ただし、これらのマシンの初期のバージョンは解読可能であった。米国陸軍のSISのWilliam F. Friedman は、 Hebern のローター マシンに早い段階で脆弱性を発見し、GC&CSのDillwyn Knoxは、第二次世界大戦が始まるかなり前に、エニグマ マシンのバージョン (「プラグボード」のないバージョン) を解読した。 ドイツ軍のエニグマによって保護されていたほぼすべてのトラフィックは、1930 年代初頭に使用されたドイツ軍のバージョンに始まり、連合国の暗号解読者、特にブレッチリー パークの暗号解読者によって解読された。 このバージョンは、ポーランドのMarian Rejewskiによる素晴らしい数学的洞察によって解読された。

公に知られている限りでは、SIGABAおよびTypexマシンによって保護されたメッセージは、これらのシステムが稼働していた期間中またはその前後に破られたことはありません。

換字式暗号の一種であるワンタイム パッドは独特である。これは、第一次世界大戦の終わりごろ、米国のギルバート バーナムとジョセフ モーボルニュによって発明された。これは、おそらく第二次世界大戦中に、クロード シャノンによって数学的に解読不可能であることが証明され、彼の研究は 1940 年代後半に初めて発表された。最も一般的な実装では、ワンタイム パッドは、珍しい観点からのみ換字式暗号と呼ぶことができる。通常、平文の文字は、何らかの方法 (例: XOR ) で、その位置にある鍵素材の文字と (置換されるのではなく) 結合される。

ワンタイム パッドは、ほとんどの場合、非実用的です。なぜなら、鍵素材が平文と同じ長さで、実際に ランダムで、一度だけ使用され、送信者と意図した受信者以外には完全に秘密にされなければならないからです。これらの条件が、たとえわずかでも破られると、ワンタイム パッドはもはや解読不可能ではなくなります。第二次世界大戦中に短期間、米国から送信されたソ連のワンタイム パッド メッセージは、ランダムでない鍵素材を使用していました。米国の暗号解読者は、40 年代後半から、数十万のメッセージのうち数千のメッセージを完全または部分的に解読することができました。(ヴェノナ プロジェクトを参照)

機械的な実装では、Rockex の機器と同様に、ワンタイム パッドは、キューバ危機後に確立されたモスクワ-ワシントン ホットラインで送信されるメッセージに使用されました。

上で説明した置換暗号、特に古い鉛筆と紙による手書き暗号は、現在では本格的には使用されていません。しかし、暗号における置換の概念は今日でも生き続けています。抽象的な観点から見ると、現代のビット指向のブロック暗号( DESやAESなど) は、大きなバイナリアルファベット上の置換暗号と見なすことができます。さらに、ブロック暗号にはS ボックスと呼ばれる小さな置換テーブルが含まれることがよくあります。置換–順列ネットワークも参照してください。

• シャーロック ホームズは『踊る男』の中で換字式暗号を解読します。この暗号は、難解だったからではなく、誰もそれを暗号だとは思わず、子供の落書きだと考えたため、何十年もの間解読されませんでした。
• 標準 銀河アルファベットは、ビデオゲーム「コマンダーキーン」や「Minecraft」で使用されている表記体系です。
• 『ファイナルファンタジーX』のアルベド語は、実際には換字暗号ですが、音声的に発音されます（つまり、英語の「you」はアルベド語では「oui」と翻訳されますが、フランス語の「oui」と同じように発音されます）。
• バビロン5シリーズのミンバリのアルファベットは、英語からの換字暗号です。
• 『スターフォックス アドベンチャーズ: ダイナソー プラネット』で原住民のソーリアンとクリスタルが話す言語も、英語のアルファベットの換字式暗号です。
• テレビ番組「フューチュラマ」には、26文字すべてを記号に置き換えた置換暗号が含まれていて、「エイリアン言語」と呼ばれていました。これは、2022-12-25にWayback Machineでアーカイブされました。これは、熱心な視聴者によって、「Slurm」の広告に「Drink」という単語を平易な英語とエイリアン言語の両方で表示することで、かなり早く解読され、鍵が与えられました。後に、プロデューサーは置換暗号と数学的暗号を組み合わせた2番目のエイリアン言語を作成しました。エイリアン言語の英語の文字が解読されると、その文字の数値（それぞれ「A」の場合は0から「Z」の場合は25）が前の文字の値に加算（26を法として）され、実際に意図された文字が表示されます。これらのメッセージは、シリーズのすべてのエピソードとその後の映画で見ることができます。
• アニメシリーズ『怪奇ゾーン グラビティフォールズ』のシーズン 1 の各エピソードのエンドロール中に、3 つの単純換字暗号のうちの 1 つが使用される。3 つの単純換字暗号は、-3シーザー暗号(オープニング シーケンスの最後に「3 文字前」と表示される)、アトバッシュ暗号、または文字から数字への単純換字暗号である。シーズン 1 の最終回では、3 つすべてを使用してメッセージが暗号化される。シーズン 2 では、さまざまなモノアルファベット暗号の代わりにヴィジュネル暗号が使用され、各暗号ではエピソード内に隠された鍵が使用される。
• エオイン・コルファーの『アルテミス・ファウル』シリーズには、ノーム語、ケンタウリア語、エテルネアン語の 3 つの換字暗号があり、ページの下部または本内の別の場所に記載されています。
• クリスティン・カショアの3作目の小説『ビターブルー』では、換字式暗号が暗号化通信の重要な形態として機能しています。
• 2013 年のビデオゲーム「バイオショック インフィニット」では、ゲーム全体に隠された置換暗号があり、プレイヤーは暗号書を見つけて解読し、余剰物資にアクセスする必要があります。
• アニメ『はたらく魔王さま!』では、エンテ・イスラの言語であるエンテ語が、暗号文のアルファベットがAZYXEWVTISRLPNOMQKJHUGFDCBの換字式暗号を使用しており、A、E、I、O、U、L、N、Q のみが元の位置のままになっている。

• バン（ユニット）とセンティバンテーブル
• コピアレ暗号
• 辞書コーダ – 圧縮するテキストとエンコーダが保持する文字列セット（「辞書」）との一致を探すことで動作するロスレスデータ圧縮アルゴリズム。一致した場合は、セット内の文字列の位置への参照に置き換えられます。Pages displaying wikidata descriptions as a fallback
• リート
• ヴィジュネル暗号
• 暗号に関するトピック
• 音楽置換暗号

• 単一アルファベット置換 既知平文攻撃を使用した単一アルファベット暗号化システムの解読