置換暗号

最も単純な換字式暗号は、シーザー暗号とアトバシュ暗号です。これらの暗号では、文字が1文字ずつ置き換えられます（これを単純換字式と呼びます）。これは、アルファベットを2回書き出すことで実証できます。1回目は通常の順序で、2回目は文字を数ステップずらしたり、逆にして暗号文のアルファベット（または換字式アルファベット）を表します。

置換アルファベットは、より複雑な方法で並べ替えることも可能で、その場合は混合アルファベットまたは乱れたアルファベットと呼ばれます。従来、混合アルファベットは、まずキーワードを書き出し、重複する文字を削除し、残りのアルファベットの文字を通常の順序で書き出すことによって作成されます。

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

メッセージ

すぐに逃げろ！見つかってしまった！

暗号化して

SIAA ZQ LKBA。 VA ZOA RFPBLUAOAR!

そして、「 grandmather 」というキーワードから、以下のアルファベットが得られます。

同じメッセージ

すぐに逃げろ！見つかってしまった！

暗号化して

MCDD GS JIAD。 WD GPD NHQAJVDPDN!

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

SIAAZ QLKBA VAZOA RFPBL UAOAR

メッセージの長さが5で割り切れない場合、末尾に「ヌル文字」が挿入されることがあります。ヌル文字は、復号すると明らかに意味不明な文字になるため、受信者が容易に識別して破棄することができます。

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

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

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

例：MATは120を表すのに使用され、PAPRは5256を表すのに使用され、OFTKは7803を表すのに使用されます。

かつてよく使われた換字式暗号の変種の一つに、ノメンクラトールがあります。訪問する要人の称号を発表する役人にちなんで名付けられたこの暗号は、文字、音節、単語の換字表（同音異義語を含む場合もある）を記載した小さなコードシートを使用し、通常は記号を数字に変換します。当初、コード部分は重要な人物の名前に限定されていたため、この暗号の名前が付けられました。後年には、多くの一般的な単語や地名も対象となりました。暗号文では、単語全体（現代の用語ではコードワード）と文字（現代の用語では暗号）の記号は区別されませんでした。フランス国王ルイ14世が使用したロシニョールの大暗号もその一つです。

15世紀初頭から18世紀後半にかけて、暗号表は外交文書、諜報活動、高度な政治的陰謀において標準的な手段であった。ほとんどの陰謀家は当時も今も暗号技術にそれほど精通していない。16世紀半ばには政府の諜報機関の暗号解読者が体系的に暗号表を解読し始め、1467年からはより優れた暗号システムが利用可能であったにもかかわらず、暗号解読に対する一般的な対応は、単に表を大きくすることであった。18世紀後半、このシステムが衰退し始めた頃には、一部の暗号表には5万もの記号が含まれていた。

しかしながら、すべての暗号解読法が解読されたわけではなく、今日でも、アーカイブされた暗号文の暗号解読は、歴史研究において実り多い分野であり続けている。

換字式暗号に対する頻度分析攻撃の難易度を高めるための初期の試みの一つは、平文の文字頻度を同音異義語によって隠蔽することであった。これらの暗号では、平文の文字が複数の暗号文記号に対応する。通常、出現頻度の高い平文記号には、出現頻度の低い文字よりも多くの対応記号が割り当てられる。このようにして頻度分布が平坦化され、分析がより困難になる。

暗号文のアルファベットには26文字以上が必要となるため、より大きなアルファベットを考案するために様々な方法が用いられています。おそらく最も簡単な方法は、数字を代入した「アルファベット」を使用することでしょう。別の方法としては、既存のアルファベットに大文字、小文字、上下反転などの単純なバリエーションを加える方法があります。より芸術的な方法としては、必ずしも安全性が高いとは限りませんが、同音異義語暗号の中には、完全に創作された奇抜な記号のアルファベットを用いるものもあります。

ブック暗号は同音異義語暗号の一種で、ビール暗号はその一例です。これは、1819年から1821年にかけて、独立宣言を鍵とした暗号文を用いて記述された埋蔵金の物語です。ここでは、各暗号文の文字は数字で表されていました。数字は、平文の文字を取り、その文字で始まる独立宣言の単語を見つけ、その単語の独立宣言における番号上の位置をその文字の暗号化された形式として使用することによって決定されました。独立宣言には同じ文字で始まる単語が多数あるため、その文字の暗号化は、その文字で始まる独立宣言の単語に関連付けられた任意の数字になる可能性があります。暗号化されたテキスト文字X（これは数字です）を解読するのは、独立宣言のX番目の単語を探し、その単語の最初の文字を復号された文字として使用するのと同じくらい簡単です。

別の同音異義語暗号は、1973年にStahlによって記述されました^{[ 2 ] [ 3 ] [ 4 ]。}これは、暗号化によってコンピュータのデータシステムのコンピュータセキュリティを提供する最初の試みの1つでした。Stahlは、特定の文字の同音異義語の数が文字の頻度に比例するように暗号を構築したため、頻度分析が非常に困難になりました。

マントヴァ公フランチェスコ1世ゴンザーガは、1401年にシモーネ・ダ・クレマとの通信に、同音置換暗号の最も初期の例を使用した。^{[ 5 ] [ 6 ]}

メアリー・スチュアート女王は、1578年から1584年にかけてエリザベス1世によって投獄されていた間、ミシェル・ド・カステルノーを含む同盟者と連絡を取る際に、同音異義語暗号を使用し、頻繁に使用される接頭辞、接尾辞、固有名詞には命名規則を用いた追加の暗号化を行っていた。^{[ 7 ]}

アル・カルカシャンディ(1355–1418)の著作は、イブン・アル・ドゥライヒム(1312–1359)の以前の著作に基づいており、暗号の置換と転置に関する最初の公表された議論と、各平文文字に複数の置換文字が割り当てられる多表式暗号の最初の記述を含んでいた。^{[ 8 ]}多表式置換暗号は、後に 1467 年にレオーネ・バッティスタ・アルベルティによって円盤の形で記述された。ヨハネス・トリテミウスは、著書Steganographia (古代ギリシア語で「隠された文字」) で、現在ではより標準的な形式であるタブロー(下記参照、1500 年頃だが、出版はずっと後) を紹介した。混合アルファベットを使用したより洗練されたバージョンは、1563 年にジョヴァンニ・バッティスタ・デッラ・ポルタによって著書De Furtivis Literarum Notis (ラテン語で「隠された文字について」)で記述された。

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

最も有名なものの一つは、ブレーズ・ド・ヴィジュネルの暗号である。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年、フリードリヒ・カシスキーは、ヴィジュネル暗号で暗号化されたメッセージのキーワードの長さを計算できる方法を発表した（おそらくクリミア戦争以前にチャールズ・バベッジが秘密裏に独自に発見していた）。この計算が完了すれば、同じアルファベットで暗号化された暗号文の文字を、半独立的な単純な置換の集合として個別に選別し、攻撃することが可能になった。ただし、同じアルファベット内では文字が分離されていて完全な単語を形成しないため、この方法は複雑になる一方、通常は表形式の表が用いられていたため、簡略化されていた。

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

その他の注目すべき多表式文字には以下のようなものがある。

• グロンスフェルト暗号。これはヴィジュネル暗号とほぼ同じですが、使用するアルファベットが10種類しかないため、「キーワード」は数字になります。
• ボーフォート暗号。これは実質的にヴィジュネル暗号と同じですが、表が逆向きの表に置き換えられており、数学的には暗号文＝鍵－平文と等価です。この操作は自己逆であり、暗号化と復号化の両方に同じ表が使用されます。
• オートキー暗号は、平文と鍵を組み合わせて周期性を回避する。
• ランニングキー暗号とは、書籍や類似のテキストの一節を用いて鍵を非常に長くする暗号方式である。

現代のストリーム暗号は、十分に抽象的な観点から見れば、鍵ストリームをできるだけ長く、予測不可能にすることに全力を注いだ多表式暗号の一種と見なすこともできる。

多文字換字暗号では、平文の文字を個別に置き換えるのではなく、より大きなグループで置き換えます。第一の利点は、頻度分布が個々の文字の頻度分布よりもはるかに平坦になることです（ただし、実際の言語では必ずしも平坦ではありません。例えば、スペイン語では「OS」は「RÑ」よりもはるかに頻繁に使われます）。第二に、記号の数が増えるため、文字の頻度を効率的に分析するには、それに応じてより多くの暗号文が必要になります。

文字のペアを置き換えるには、676 記号からなる置換アルファベットが必要になります ($26^2$前述の『 De Furtivis Literarum Notis』の中で、デッラ・ポルタは実際にそのようなシステムを提案しており、彼が使用していたイタリア語/ラテン語アルファベットの20文字に対応する20×20の表に400個の固有のグリフを配置していた。しかし、このシステムは実用的ではなく、おそらく実際に使用されることはなかっただろう。

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

1901年には、フェリックス・デラステルによって、二分暗号と四角暗号（いずれも二分暗号）や三分暗号（おそらく最初の実用的な三分暗号）など、他にもいくつかの実用的な多分暗号が導入された。

1929年にレスター・S・ヒルによって発明されたヒル暗号は、線形代数を用いてはるかに大きな文字群を同時に組み合わせることができる多文字置換暗号です。各文字は26進数の数字として扱われます。A=0、B=1、といった具合です。（バリエーションとして、基底を素数にするために3つの追加記号が加えられます。）n個の文字のブロックはn次元のベクトルとみなされ、26を法とするanxn行列と乗算されます。行列の要素が鍵であり、行列が可逆であればランダムである必要があります。${\displaystyle \mathbb {Z} _{26}^{n}}$（復号化が可能であることを確認するため）。次元6のヒル暗号の機械式バージョンは1929年に特許を取得した。^{[ 10 ]}

ヒル暗号は完全に線形であるため、既知平文​​攻撃に対して脆弱であり、この攻撃を阻止するには何らかの非線形ステップと組み合わせる必要があります。ヒル暗号のような、より広範囲にわたる弱い線形拡散ステップと非線形置換ステップを組み合わせることで、最終的には置換・順列ネットワーク（例えば、フェイステル暗号）が構築されます。したがって、この極端な観点から見ると、現代のブロック暗号は一種の多文字置換暗号とみなすことができます。

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

これらすべてに共通していたのは、置換文字が複数の文字ディスクの回転によって生じる膨大な数の組み合わせの中から電気的に選択される点である。平文の文字が暗号化されるたびに1つ以上のディスクが機械的に回転するため、使用されるアルファベットの数は天文学的な数になる。しかし、これらの機械の初期バージョンは解読可能であった。米陸軍SISのウィリアム・F・フリードマンは、ヘーベルンの回転式暗号機に早くから脆弱性を発見し、政府暗号学校のディルウィン・ノックスは、第二次世界大戦が始まるずっと前にエニグマ暗号機（「プラグボード」のないバージョン）を解読した。ドイツ軍のエニグマ暗号機で保護されていた通信は、1930年代初頭に使用されたドイツ軍バージョンから始まり、特にブレッチリー・パークの連合国暗号解読者によって解読された。このバージョンは、ポーランドのマリアン・レジェフスキによる数学的な洞察によって解読された。

公に知られている限りでは、SIGABAおよびTypexマシンによって保護されたメッセージが、これらのシステムが運用されていた期間中またはその前後に解読されたことは一度もない。

換字式暗号の一種であるワンタイムパッドは独特な暗号方式です。これは第一次世界大戦末期にアメリカのギルバート・ヴァーナムとジョセフ・モーボルニュによって考案されました。数学的に解読不可能であることがクロード・シャノンによって証明されたのはおそらく第二次世界大戦中のことで、彼の研究成果は1940年代後半に初めて発表されました。最も一般的な実装では、ワンタイムパッドは特殊な観点からのみ換字式暗号と呼べます。通常、平文の文字は、その位置にある鍵となる文字と何らかの方法（例えばXOR演算）で結合（置換ではなく）されます。

ワンタイムパッドは、ほとんどの場合、実用的ではありません。なぜなら、鍵となる素材が平文と同じ長さで、実際にランダムであり、一度だけ使用され、送信者と受信者以外には完全に秘密にしておく必要があるからです。これらの条件が少しでも満たされないと、ワンタイムパッドは解読不可能ではなくなります。第二次世界大戦中、米国から短期間送信されたソ連のワンタイムパッドメッセージは、ランダムではない鍵素材を使用していました。1940年代後半から、米国の暗号解読者たちは、数十万通のメッセージのうち、数千通を完全に、あるいは部分的に解読することに成功しました。（ヴェノナ計画を参照）

機械的な実装では、ロックエックスの機器によく似た方法で、ワンタイムパッドはキューバ危機後に開設されたモスクワ・ワシントン間のホットラインで送信されるメッセージに使用されました。