古典暗号 - Beaufort暗号とAutokey暗号

Vigenere暗号は非常に強力な暗号だった。その強力さと汎用さから、いくつかの派生暗号が知られている。ここでは、その中から2つ取り出して書いてみようと思う。

Autokey暗号

Autokey暗号は、Vigenere暗号にストリーム暗号の要素を加えた暗号と言える。以下に暗号化/復号処理を示す。

暗号化

最初に、鍵を一つ決める。これは長さに特に制限は無い。ここではDJAUTOとする。 平文をここではAUTOKEY CIPHER IS VIGENEREという文字列にする。この時、次のようにして暗号化処理が行われる。

  • まずは普通にキーの長さと同じだけ暗号化する。DJAUTOは6文字なので、AUTOKEまでを暗号化してDDTIDSとなる。
  • 次に、ここで暗号化した平文を鍵として再利用する。ここでは、AUTOKEを鍵として利用し、次のY CIPHEを暗号化する。暗号化された結果はB LIJASとなる。
  • 同様に全ての暗号文に対して少し前の平文を使い、暗号化する。最終的な暗号文はDDTIDSB LIJASU RS PBUHWELX QLYHYKとなる。

復号

復号の処理を以下のように行う。

  • 最初にキーで復号する。
  • 出てきた平文を使って次を復号する。
  • 繰り返していくと、平文が出てくる。

安全性

ブロック暗号を触った方なら、動作モードを指定したブロック暗号のようだと思われただろう。実際そのとおりで、この暗号は平文を暗号文として使いまわすことでカシスキー・テスト等の攻撃手法からVigenere暗号を守っている。 しかし、Vigenere暗号と同じく既知平文攻撃に対しては脆弱なままで、少し解読しにくくなるだけである。楽にそれなりの安全性を手に入れるにはその当時としては良い方法だったのだろう。

Beaufort暗号

Beaufort暗号はVigenere暗号と似て少し違う暗号だが、Vigenere暗号に変換することで同様の攻撃手法を使えてしまう暗号だ。

暗号化

Vigenere暗号を解説した際にも掲載したVigenere方陣を再度見てみて欲しい。Vigenere暗号では、横列で平文、縦列で暗号化鍵を探し、それらの交点にある文字を暗号文とした。Beaufort暗号では、横列から平文を探し、そのままその列を下に行って鍵を探す。そして、そこから左に行った左側の列にある文字が暗号文となる。

例として、CTFという鍵でCRYPTOという文字列を暗号化する。鍵は伸長されてCTFCTFとなる。方陣の横列からCを探し、そこから下に行ってCを探す。左端を見ると、Aとなっている。次に、Rを探し、Tまで降りて左端を見るとCという暗号文が得られる。これを繰り返すとACHNARという暗号文が得られる。

復号

復号に関しても見るところが変わるだけでVigenere暗号と実質的なところは変わらない。実際に上の文字列を復号してみると良いだろう。

Vigenere暗号との関連性

同じ方陣を利用しているためか、少し手を加えるだけでVigenere暗号に変換することが出来る。Vigenere暗号の時と同じように、少し対応表を作ってみよう。

鍵をAとすると、

  • 平文 : 暗号文
  • A : A
  • B : Z
  • C : Y
  • D : X ...

Vigenere暗号の時とは少し違い、微妙に暗号文がずれていることに気づくだろうか。鍵がBの場合も見てみよう。

  • 平文 : 暗号文
  • A : B
  • B : A
  • C : Z
  • D : Y ...

これらの結果から数式に落としこんでみよう。Vigenere暗号では単純に \(\vec{p} + \vec{k}\) とするだけだった。今回の場合を数値としてみてみると、平文をA, 鍵をAとして便宜上暗号化処理を+で表すと、鍵をA(つまり0)として0+0 = 0になっていて、鍵がBの時は0+1 = 1つまりBになっている。ここで、D(つまり3)を見てみると3+0 = X(つまり23)となる。C(つまり2)は2+0 = Y(つまり24)。これらの結果から、Beaufortの場合は引き算に近いのではないか?というように考えることが出来る。

鍵がA(=0)の時を引き算とすると次のようになる。

  • \(0 - 0 \equiv 0\mod 26\)
  • \(0 - 1 \equiv -1 \equiv 25 \mod 26\)
  • \(0 - 2 \equiv -2 \equiv 24 \mod 26\) ...

鍵がB(=1)の時も見ておこう。

  • \(1 - 0 \equiv 1\mod 26\)
  • \(1 - 1 \equiv 0\mod 26\)
  • \(1 - 2 \equiv -1 \equiv 25 \mod 26\) ...

この方向で良さそうだ。式として定式化すると、次のようになる。

暗号化関数は、平文を\(\vec{p}\)、暗号化鍵を\(\vec{k}\)とした時、

\( Enc(\vec{p}) := \vec{k} - \vec{p} \mod 26 \)

復号関数は、暗号文を\(\vec{c}\)、暗号化鍵を\(\vec{k}\)とした時、

\( Dec(\vec{c}) := \vec{k} - \vec{c} \mod 26 \)

定式化ができた。ここで、Vigenere暗号の暗号化/復号関数をもう一度書いておくと、

\( Enc(\vec{p}) := \vec{p} + \vec{k} \mod 26 \)

\( Dec(\vec{c}) := \vec{c} - \vec{k} \mod 26 \)

である。Beaufort暗号で作られた暗号文をVigenere暗号にするために、次のように変形をする。

\( \begin{align} \vec{c} = Enc(\vec{p}) &= \vec{k} - \vec{p} \mod 26\cr -\vec{c} &= -\vec{k} + \vec{p} \mod 26\cr -\vec{c} &= \vec{p} - \vec{k} \mod 26\cr \end{align} \)

暗号文と鍵にそれぞれ-1を乗じることで、Vigenere暗号と同一視出来るようになった。ちゃんと書き直すと、

\( ToVigenere(\vec{c}) := -\vec{c} \mod 26 \)

である。こうして作られたVigenere暗号文に対してはカシスキー・テスト等のVigenere暗号に対する攻撃をそのまま使用することが出来る。

Beaufort暗号は何故か日本語の記事が少なく、wikipediaでも定式化までは取り上げて居なかったため取り上げた。

リファレンス