換字式暗号アルゴリズム
換字式暗号とは
換字式暗号 (Substitution cipher) は,平文の文字を他の文字に1文字単位あるいは数文字単位で置き換える暗号方式である.
変換ルールの性質 (1対1,1対多) や種類 (単一固定,複数可変),変換の単位(1文字か複数文字)などによって様々な方式がある.
換字式暗号
- シフト暗号 (Shift Cipher) / シーザー暗号 (Caesar Cipher)
アルファベットに数を対応させ (A = 0, B = 1, …, Z = 25),文字 M を以下の規則 (K を定数とし,M + K を 26 で割った余りを C とする)により C に暗号化するものである.
C = (M + K) mod 26 (K は定数)
古代ローマのシーザは,K を 3 とした暗号を使っていたと言われている. 例えば,
K = 1 とすれば,A は B に,B は C になどすべての文字を 1 文字ずらしたものが暗号文になる.
- 乗算剰余暗号
アルファベットに数を対応させ (A = 0, B = 1, …, Z = 25),文字 M を以下の規則 (Kを定数とし,M・K を 26 で割った余りを C とする)により C に暗号化するものである.
C = (M・K) mod 26 (K は暗号化鍵)
ここで,暗号化鍵 K の選択には制限がある. すなわち,暗号化鍵によりすべての文字が異なるように変換されなければならない.ある暗号化鍵 K と2つの整数 N1,N2 に対して,
N1≠ N2 ならば,N1・K ≠ N2・K (mod 26)
である必要がある.これには,K が 26 の約数でないことが必要である.
K を 2 から 25 までの範囲に限定すると,暗号化鍵 K は,
K = 3,5,7,9,11,15,17,19,21,23,25
の 11個になる.
乗算剰余暗号の暗号化鍵 K に対応する復号鍵 Y は,ある文字に割り当てられた数を N とすると,暗号化鍵によって変換された文字が復号鍵によって元の文字に変換されなければならないことから,次の剰余式が成り立つ.
(N・K)・Y = N・(K・Y) = N (mod 26)
これより,復号鍵は K・Y = 1 (mod 26) なる Y (= K-1 (mod 26))になる.
上記の暗号化鍵 K に対応する復号鍵 Y は次のようになる.
Y = 9,21,15,3,19,7,23,11,5,17,25
- アフィン暗号
アルファベットに数を対応させ (A = 0, B = 1, …, Z = 25),文字 M を以下の規則 (a, b は定数)により C に暗号化するものである.
C = (aM + b) mod 26
ここで, (a, 26) = 1 である必要があり,a は12個 (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25) のいずれかになる.これに b (0 から 25 の26通り) の数を掛けたものがアフィン暗号の鍵の種類数 (12 x 26 = 312)となる.
復号は,以下による.
M = a-1(C - b) mod 26
- ヴィジュネル暗号(Vigenere Cipher)
シーザ暗号と同様であるが,
m 文字ごとにずらす数を変える暗号である.
文字 Mi を Ci に暗号化するとき,
Ci = (Mi + Ki) mod 26
のようにする.
例えば,
m = 3 とし,K1 = 3, K2 = 5, K3 = 11, K4 = 3, K5 = 5, K6 = 11, ・・・とするとき,次のようになる (この場合,鍵は K = (3, 5, 11) である).
- エニグマ暗号 (Enigma Cipher)
エニグマ暗号は順変多表式と呼ばれる換字式暗号である.暗号文を同じ鍵で再暗号化すると平文が得られる.
複数の周期の違うギア(ローター)を使って機械制御で実現されている. 具体的にはアルファベットが振られたローターを組み合わせ,1番目のローターが1回転すると2番目のローターが1つ動く,2番目のローターが1回転すると3番目のローターが1つ動く. それぞれのローターにはアルファベットが振られており,各ローターの特定の位置にあるアルファベットの合計分だけ原文のアルファベットをずらすことにとって暗号化する.
鍵は,ローターの組み合わせやローターの目盛りの初期値等によって決まる.
- バーナム暗号(Vernam Cipher)
暗号化する対象 M と同じ長さの鍵 K を用意し,1文字毎に鍵と暗号化の対象をXOR(排他的論理和)演算して暗号文 C を生成する.
Ci = Mi XOR Ki (i = 1, 2, ・・・ )
鍵として規則性の無い乱数列(One-time pad)を用い,鍵の周期を無限大とすれば,この暗号は完全に安全な暗号となる.