換字式暗号

換字式暗号（かえじしきあんごう、Substitution cipher）、あるいは換字暗号（かえじあんごう）は、平文を、1文字または数文字単位で別の文字や記号等に変換することで暗号文を作成する暗号である。文字の変換ではなく並べ替えによって平文を読めない状態にする転置式暗号と共に、古典暗号の代表的な暗号の一つであり、16世紀頃には換字式・転置式という分類がなされている。

概要

最も古い暗号の一つであるシーザー暗号は、最も単純な換字式暗号の一つであり、文字から文字に1文字単位で変換する方式（単純換字暗号）である。シーザー暗号の変換ルールは「3文字シフト」であった。

しかし、9世紀頃にはこのような単純な暗号は、変換ルールが固定の1対1写像である限り、どのような変換であっても解読可能であることが知られていて、以来、暗号解読されないように、色々な改良が行われ、様々な換字式暗号が登場した。さらに近代のエニグマ他に代表される機械式暗号も、変換ルールを機械の利用により複雑にする技巧を凝らした、換字式暗号の一種と言える。

シーザー暗号は、1文字を別の1文字に変換する方式であるが、普通の文字に変換するのではなく単語や数字・記号・図形等に変換する暗号もあり、有名なものから無名なものまで数多くある。

単語 - コードブック、ニヒリストの暗号、
数字 - ポリュビオスの換字表、字変四八、ルイ14世の大暗号、ナポレオンの小暗号、ビール暗号、
記号 - 「黄金虫」（数字や記号の混合）、「二銭銅貨」（点字）、「フーガの技法」BACH主題（楽譜）、メアリーの暗号、ダビンチの鏡文字
図形 - メッシュ暗号あるいはピッグ・ペン（四角と点の図形）、「踊る人形」（人形の図形）、山窩文字、

などがある。

図形に変換する暗号として、アーサー・コナン・ドイルの「踊る人形」（1903年）がよく知られているが、類似の換字表は1874年にも発表されている。新聞のクイズ欄にて換字式の暗号文を掲載することもあった。換字表には、モールス符号、アスキーコード、JISコードなどのように秘匿用途ではないものもあるが、戦時に表を取り替えて暗号として使用した例もあった。

換字式暗号は初期には紙と鉛筆だけで暗号文を作成していた。変換ルールが複雑な場合や効率よく変換を行う目的で、変換表や円盤などが使われることもあった。ヴィジュネル方陣やアルベルティの暗号円盤などが知られている。

なお、"換字" はそのまま読むと"かんじ"となるが、"漢字"と同じ読みだと紛らわしいため、"かえじ"と読む慣わしがある。

分類

換字式暗号には、変換ルールの性質（1対1、1対多）や種類（単一固定、複数可変）、変換の単位（1文字か複数文字）などによって次のような分類がなされている。

具体的な暗号方式の一覧は、暗号理論を参照。

（文字単位の変換）

単表式換字 (monoalphabetic substitution cipher)：変換ルールが1つに固定。単アルファベット換字ともいう。
- 単純換字 (simple substitution cipher / uniliteral substitution cipher )：1対1の単純写像で平文の1文字を対応する1文字に変換する。内部状態はなく、前後の文字には影響されない。単一換字ともいう。
- 同音換字 (Homophonic substitution cipher)：平文の1文字に対応する文字が複数個あり、その中から一つを選択して変換する。写像は1種類であるが1対多の写像である点が異なる。単純換字では平文の統計的性質がそのまま暗号文に残るが、同音換字では文字の出現頻度を操作できる。暗号文に同じ文字が1度しか出現しない場合には解読できなくなる。異綴換字、ホモフォニック換字ともいう。なお単文字換字での同音暗号(uniliteral substitution cipher with variants)は理論的には可能だが実用性に乏しい。以下の例では平字のJとYをIにKをCまたはQにWをVVで代用する事でフランス語で高頻度の4字をvariantsに充てた。^[1]

(uiliteral substitution cipher / variants の例)

平字	暗字	平字	暗字	平字	暗字	平字	暗字	平字	暗字	平字	暗字	平字	暗字
A	L	B	G	C	O	D	R	E	F,K,V	F	Q	G	A
H	H	I	C	L	M	M	B	N	T,X
O	I	P	D	Q	N	R	P	S	U,Z	T	S	U	Y
V	E	X	W	Z	J

多表式換字 (polyalphabetic substitution cipher)：1文字単位だが内部状態を保持し、変換ルールを切り替えながら変換を行う。多アルファベット換字ともいう。
- 周期換字 (periodic substitution cipher)：内部状態が周期的に変化して、変換ルールが周期的に切り替わる。周期が短いと解読されやすい。複数個の換字表を連動させて周期を長くしたのがロータマシンである。順変多表式換字ともいう。
- 非周期換字：
  - 連続鍵暗号/進行鍵暗号 (running key cipher)：平文と同じ長さの鍵を用いて非周期的に変換ルールを変化させる方式。書籍の頁数行数を指定してそこから始まる文章を鍵としたりした。文章を鍵とした場合には、鍵にした文章の出現頻度の偏りが解読の手がかりとなることがある。使い捨ての乱数を鍵として用いると情報理論的に安全な暗号（ワンタイムパッドと呼ばれる）となる。鍵としてランダムな文字列や数列を使ったものは、乱字式、乱数式ともいう。
  - 自己鍵暗号/自動鍵暗号 (autokey cipher)：平文や暗号文を内部状態に取り込み、次の状態を決める。暗号利用モードの一つ、サイファフィードバック (CFB) がこれにあたる。

（複数文字単位の変換）

綴字換字/多重音字換字 (polygraphic substitution cipher)：2文字以上で一定長さの平字群を同じ長さの暗字群で変換する。変換ルールは1文字単位の方式と同様である。2文字単位のものをダイグラフィック換字暗号 (digraphic cipher) という。複数文字単位で変換を行うと組合せ数が増えるため、統計的な解析が難しくなる。現代のブロック暗号は64bitや128bit単位で変換を行う綴字換字暗号の子孫ともいえる。

複文字換字 (multiliteral substitution cipher)：1文字の平字を２文字以上で一定長さの暗字群で変換する。暗字はアルファベットや数字が用いられる。元の平文の複数倍の文字数に変換される欠点がある。１つの平字に１つの暗字群を割り当てる"Single-equivalent"と1つの平字に複数の暗字群”Variants”を割り当てる２つの種類があり後者は冗字”Nulls”も利用できる。^[2]

single-equivalent の例1
	W	H	I	T	E
B	A	B	C	D	E
L	F	G	H	IJ	K
A	L	M	N	O	P
C	Q	R	S	T	U
K	V	W	X	Y	Z

single-equivalent の例2
	1	2	3	4	5	6	7	8	9	0
1	A	B	C	D	E	F	G	H	I	J
2	K	L	M	N	O	P	Q	R	S	T
3	U	V	W	X	Y	Z	.	,	:	?

variants の例(Uは冗字)
	V,Q	W,R	X,S	Y,T	E,Z
L,F,A	A	B	C	D	E
M,G,B	F	G	H	IJ	K
N,H,C	L	M	N	O	P
O,I,D	Q	R	S	T	U
P,K,E	V	W	X	Y	Z

構造

換字式暗号は、

CI : 平文の文字の集合
CO : 暗号文の文字の集合
ci : CIの1文字(or数文字)を表す数値
co : COの1文字(or数文字)を表す数値
reg : 内部状態を保持するレジスタ
KEY : 鍵の数値の集合
key : 鍵となる秘密の数列
ENC : 暗号化関数
DEC : 復号関数

として、

{co,reg} <= ENC(ci,key,reg)

{ci,reg} <= DEC(co,key,reg)

として表現できる。#CI,#COを集合のサイズ、#keyを鍵の長さ、key[i]を鍵のi+1番目とする。

シフト暗号は、CO=CI, KEY=[0..(#CI-1)], ci∈CI, co∈CO, key∈KEY, #key=1として、

ENC_s := {mod(ci+key[0],#CI),0}

DEC_s := {mod(co-key[0],#CI),0}

となる。シーザー暗号はシフト暗号の鍵が3の場合なので、

ENC_c := {mod(ci+3,#CI),0}

DEC_c := {mod(co-3,#CI),0}

である。アフィン暗号は、key={a,b}, aは#CIと互いに素な整数, bは任意の整数として、

ENC_a := {mod(ci*key[0]+key[1],#CI),0}

DEC_a := {mod((co-key[1])/key[0],#CI),0}

ヴィジュネル暗号は、key∈KEY^i, #key=i, reg=0 として、

ENC_v0 := {mod(ci+key[reg],#CI),mod(reg+1,#key)}

となる。ヴィジュネル暗号で#key=1の場合は、シフト暗号と同じになる。ボーフォート暗号 (Beaufort cipher) は、アルファベットを逆順に並べてからシフトする暗号で、

ENC_b := {mod(key[reg]-ci,#CI),mod(reg+1,#key)}

DEC_b := {mod(key[reg]-co,#CI),mod(reg+1,#key)}

となり、ENC_bとDEC_bは同じ手順で行えるという特徴がある。アフィン暗号をベースとした多表式暗号は、key={a,b}^i として、

ENC_b := {mod(ci*key[0,reg]+key[1,reg],#CI),mod(reg+1,#key)}

となり、シーザー暗号からボーフォート暗号までを含む暗号となる。ヴィジネルが考案した自己鍵暗号は2種あり、key∈KEY,#key=1,reg=keyとして、

ENC_v1 := {mod(ci+reg,#CI),ci} --- ciを次の鍵とする

ENC_v2 := {mod(ci+reg,#CI),mod(ci+reg,#CI)} --- coを次の鍵とする

となる暗号である。ENC_v2は暗号文から鍵が直接判明するので暗号としては全く安全ではないが、鍵の生成方法としては過去のciの全てを次の鍵に影響させるという点で新しいアイデアであった。

(stub)

歴史

歴史については暗号史も参照。

換字式暗号は、暗号文を平文に戻すには変換を逆に行えばよいため、変換ルールが特定されると暗号文も解読されてしまう。文字のシフトのような単純な変換ルールでは、ルール自体が容易に推測されてしまうため、より複雑なルールが作られた。数文字おきに文字を対応させた上でシフトしたり（アフィン変換）、鍵語を使った変換（鍵の重複文字を除いて並べ、他の文字をその後に並べる）などが考案された。しかし、固定の変換ルールでは平文の統計的性質が暗号文に残ってしまうため、頻度分析に対する安全性という点では無力であった。そこで、変換ルール自体を切り替えて使用することが考案された。それがヴィジュネル暗号などの多表式と呼ばれる方式である。その他、1文字単位ではなく、複数文字単位で変換したり、平文や暗号文自体を変換ルールにフィードバックすることも考案された。

現代の暗号では、もっぱら数理的にデータを扱うため、ある程度の関連は言えなくもないものの、基本的には古典的な分類である換字式といった分類を当てはめて考えることはない。単純な換字式暗号はROT13など、暗号というよりも、ネタバレの記述を一読ではわからない程度に難読化する、「ひねりを加える」程度の用途などに見られる。

安全性

一般的にアルゴリズムが公開された古典暗号は、安全ではないと考えるべきである。

単純換字は、頻度分析によって解読可能である。同音換字は、文字単位の出現頻度を平均化できるため、単一文字での頻度分析は難しくなるが、2重音字 (digram) や3重音字 (trigram) での頻度分析で解読できる可能性がある。

多表式であっても周期換字で、周期が短い場合には、一致反復率やカシスキー・テスト（頻度分析）などにより周期を特定した上で、頻度分析を行うと解読できる場合がある。

脚注

[脚注の使い方]

^ "Elements de Cryptographie", Roger Baudouin,Paris, 1939
^ "Military cryptanalytics Part 1", W.F.Friedman, L.D.Calllimahos, Aegean Park Press, 1985

参考文献

Horst Feistel, "Cryptographic Coding for Data-Bank Privacy", IBM Research Report RC-2827, T.J.Watson Research Center, Yorkton Heights, N.Y., March 1970.
加藤正隆、「乱数と暗号」、数理科学、1977年4月号、1977.

換字式暗号

目次

概要

分類

構造

歴史

安全性

脚注

参考文献

関連項目