古典暗号 - アフィン暗号

古典暗号

古典暗号のうち、シーザー暗号を始めとする多くの単一換字式暗号を一般化すると、アフィン暗号と呼ばれる暗号に帰着することができる。今回はアフィン暗号とその応用例、解読法について書く。

アフィン暗号

アフィン暗号の暗号化関数は、次の式で定義される。

\( Enc(m) := am + b \mod m \)

ここで、mは平文, a, b, mはパラメータを表す。

単一換字式暗号の定義として、「ある文字からある文字の変換が一対一であること」がある。例えば、1文字ずらすシーザー暗号は必ずaならb、bならcのように一対一の対応ができるため、単一換字式暗号と言える。

アフィン暗号の復号関数は、次の式で定義される。

\( Dec(c) := \frac{c - b}{a} \mod m \)

アフィン暗号の暗号化関数を見てみよう。この時、平文は数値として扱うと扱いやすい。つまり、A -> 0, B -> 1, ...のようにして数値化しておくことにする。 アフィン暗号の暗号化関数は、ある文字mが与えられた時、\( c = am+b \mod m \)を返す。これはmを固定すると必ず同じ値が出力されることから、全てのmに対して一対一にcが定まるため、単一換字式暗号といえる。

シーザー暗号

シーザー暗号は、アフィン暗号の一番簡単な例といえるだろう。シーザー暗号の暗号鍵をkとする時、これは\( a = 1, b = k, m = 26 \)としたアフィン暗号として書くことができる。

例えば、rot13(k=13のシーザー暗号)であれば

\( \begin{align} Enc(m) &:= m+13 \mod 26 \cr Dec(m) &:= m-13 \mod 26 \end{align} \)

と書ける。

Atbash暗号

Atbash暗号は、アルファベットを次のようなテーブルによって暗号化していく方式だ。

+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A | B | C | D | E | F | G | H | I | J | K | L | M |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Z | Y | X | W | V | U | T | S | R | Q | P | O | N |
+---+---+---+---+---+---+---+---+---+---+---+---+---+

例えば、CRYPTOGRAPHYを暗号化すると、C <=> X, R <=> I, Y <=> B, P <=> K, T <=> G, O <=> L, G <=> T, R <=> I, A <=> Z, P <=> K, H <=> S, Y <=> Bなので、暗号文はXIBKGLTIZKSBとなる。

これは、\( a = -1, b = -1, m = 25 \)としたアフィン暗号と同値である。

解読

既知平文攻撃

mはたいていの場合既知であるため、ここではa, bの特定に注目した既知平文攻撃を考える。(mについての場合はcryptography - Plaintext attacks: affine cipher - Mathematics Stack Exchangeを参照)

平文と暗号文のペア \((m_1, c_1), (m_2, c_2)\)は

\( \begin{align} c_1 &= am_1 + b \mod m\cr c_2 &= am_2 + b \mod m \end{align} \)

と書くことができる。この時、以下の式が成立する。

\( \begin{align} c_1 - c_2 &= (am_1 + b) - (am_2 + b) \mod m\cr &= am_1 - am_2 + b - b\cr &= a(m_1 - m_2) \end{align} \)

よって、aは \(a = \frac{c_1 - c_2}{m_1 - m_2}\)と書くことができる。 aが判明したので、bは\(b = c_1 - am_1 \mod m\)とすることで導出ができる。

頻度分析

単一換字式暗号は、全ての文字が平文と暗号文とで一対一に対応する。これは、頻度分析を使うことで文字の推測をすることができるという意味でもある。 英語、フランス語、イタリア語、ドイツ語等の言語では文字に一定の偏りがある。例えば英語ではe, t, a, ...の順で数が多いので、暗号文を頻度分析した結果の上から順にe, t, a, ...の確率が高いということになる。

リファレンス