ブロック暗号解読法

ビジュネル暗号の鍵空間の改良

ビジュネル暗号とは、中世フランスの外交官であったブレーズ・ド・ビジュネルが発表した手書きの多表式暗号である。
所謂コードブックといわれる変換表を秘密にするタイプのものであるが、ここではこのコードブックを公開する場合と秘密にする場合の２つのパターンについて考察する。

あとビジュネル方陣を多次元に一般化するという発想はなかったのでこれもやってみたい。
こうすれば秘密鍵も２次元キーワードになり、解析が難しくなりそうである。（幾何学的ビジュネル暗号？）
線形写像をどう構成するかという問題になりそうですね。

なんとなくイメージできるのは、行列、動的置換、S-Boxによる非線形置換の３つの要素です。
出来ればS-boxを除く線形写像がどのような行列として書けるのか知りたい。
もし行列表現できるなら、それはビジュネル暗号もヒル暗号と同じであるといえる。
どーなんだろ。

ビジュネル暗号の定義

文字を数値としてみれば (a = 0, b = 1, ..., z = 25)、次の式が成り立つ。
$K=X=C=(N_l)^m$（Nは自然数）であるとする。

今、$m=l=26$とする。すると、$0\leq i < k$なので
$x_{i} \in X$ は平文の i 文字目、
$k_{i} \in K$ は鍵の i 文字目、
$c_{i} \in C$ は暗号文の i 文字目である。

以下では、ブロック長k、及び鍵であるパスワードの長さmは３２とします。

鍵：$K=(k_1,k_2,...,k_m)$
暗号化：$e_K(x_1,x_2,x,...,x_m)=(x_1+k_1,x_2+k_2,...,x_m+k_m)=(c_1,c_2,...,c_m)$

鍵空間：$(N_l)^m:Z_{26}^m =1.1 \times 10^7,m=5$
これだけあれば手計算では安全だといえるが、計算機だと不可能ではない。
そこで鍵空間を広げることを考える。

ビジュネル暗号の解読

ここでは暗号文単独攻撃をやる。
ビジュネル暗号は多表式暗号であるが、この暗号の大元のアイデアはメアリの暗号と同一である。
メアリの暗号は文字の出現確率できまる。
例えば使われている文字の数が５０であれば、日本語のひらがなである可能性が高い。
更に日本語を前提として、文字の出現頻度が統計的に分かっているものとする。
するとメアリの暗号の変換表は１つだけので、ECBモードのように出現確率はひらがなと同じ確立である。
そこで頻度の多いものから文字を決定することができる。
鍵は要らない。

20240327（追記）

次に多表式のビジュネル暗号を解読する。
すると、まず鍵になるキーワードの長さを普通のパスワードの長さを８とすると、８文字ごとに同じ文字で暗号化されていることになる。つまりパスワードの長さが秘密鍵になる。
パスワードの長さを１から始めて、１字ずつ、２文字おき、...と増やしていき、出現頻度が日本語の統計結果と一致すればそれが鍵の長さになり、あとはメアリの暗号と同じやり方で平文が得られる。
以下では、これを回避するための改良案を試す。
例えば暗号化モード、CBCモードやCTRモードなどを使って難読化する。
CBC暗号モードは、例えるならオートキー（自動鍵）暗号化と似ている。
自分自身を暗号化のカギに使っているからだ。

さてここからが本題の解読である。
上でいっていた、鍵の文字数を増やすことで鍵空間そのものを大きくすることには殆ど意味はない。
というのも、ビジュネル暗号の秘密鍵はキーワードの長さにあるからだ。
今８文字のパスワードをビジュネル暗号に使っているとしよう。
すると、パスワードにどのような単語が使われているかにかかわらず、わずか８回の試行錯誤で暗号文単独攻撃ができることを以下に示す。

まず文字の長さを１として、文字の頻度解析を行う。なお、ここでは使用している言語が分かっているものとする。
ビジュネル暗号は多表式暗号だから、この８文字おきに出てくる文字を頻度解析にかけることで、
運が良ければ暗号文だけから秘密鍵を取り出したり、秘密鍵なしに平文を解読することになる。
という事はパスワードによるびじゅねーる暗号は極めて脆弱であるといえよう。

改良案

鍵となるキーワードのサイズには上限があるとする。
つまり、
$|K|=256$bit
などである。
なので１文字を８ビットとすると２５６ビットにするためには３２文字(32byte)以下にする必要がある。
なので$m=32$である。
残るのはnの改良である。１バイトは２５６個の文字$l=256$であると考える。
$256^{32}=115792089237316195423570985008687907853269984665640564039457584007913129639936=10^{77}$

ここで、
$$n=_ {256}C_{26}$$
と置くことで鍵空間が増やせると更に良い。
例えば、$|K|=n*26^{32}$とかだったらいいのにｗ。

考え方としては次のようなイメージである。
１．$256^{32}$で考える（256個のマスのある公開ビジュネル方陣を32回使う）
２．ビジュネル方陣を秘密のコードブックとして使う場合
${} _ l C_k^m={} _ {256} C_{26}^{32}$で考える（${} _ {256} C_{26}$種類ある、26個のマスのあるビジュネル方陣の中から1つ選び、それを32回使う）
でそれぞれの出る目の組み合わせの総数が同じかどうかである。
２の場合はいわばコードブックまで秘密にしているのだから、鍵の総数が増えて当然である。

まず２の方を分析する。
$n$はまずビジュネル方陣の種類で、それぞれが区別できるものである。
この場合、アルファベットの組み合わせが違うので、上記の組み合わせの数だけビジュネル方陣ができる。
という事は、ビジュネル方陣はどのアルファベットにどのような数字を対応させるかで変わる。

また１の場合はビジュネル方陣自体が公開されていなければならないなら、これは秘密鍵に当たらないので議論する意味がない。
なので１では、秘密鍵はｍで何も変わらない。然しその場合でも２５６個の文字からなるビジュネル方陣を使えば計算機による全数探索でも鍵を総当たりで探索するのはほぼ不可能になるような強度を持つと考えられる。

さてここで、ビジュネル暗号が頻度解析に弱いことが分かった。
つまり、統計的な検査に捕まらないように、文字の分布をランダムにしなければならない。
このために暗号文ブロックに関して置換群を使って同じ文字にならないようにすることができると思われる。
DESなどのFeistel構造では、２分の１しかなかったデータの分割暗号化は、より多い１バイトサイズのデータ分割でベクトルとして扱うことができる（線形代数）。

数学的な性質を知りたい

問題は方陣を公開した場合秘密鍵はパスワードの長さｍだけになることである。
ｍは32より大きくなれない。
そこで有効なのは暗号文を置換することであり、もっと先に進むとS-Boxなどの変換表を間に挟むことでパスワードの推測を困難にすることができるらしい。
そしてキーワードの多次元化もｍを大きくするために有効であると予想する。
つまり線形写像をどう構成するかが問題になるので、これはビジュネル暗号の代数的な性質を調べることになると思う。
鍵がなければ逆写像が定義できないというのが暗号の肝である。

線形写像はどのように構成しても同じなのだろうか？

線形写像なら線形代数、つまり行列変換だけしかしてないことになり、写像をどのような行列として書くことができるかを調べることになります。
行列の列番号を文字の位置を、行番号が文字の種類を表すとする。
例えば、

\begin{pmatrix}
   1 & 0 & 0\\
   0 & 1 & 0 \\
   0 & 0 & 1
\end{pmatrix}

は、$(A,B,C)$を表すことになる。
ビジュネル方陣のサンプルを次のように決めます。

\begin{pmatrix}
   A & B & C\\
   B & C & A \\
   C & A & B
\end{pmatrix}

まずパスワードとして$(A,C)$を使う事にします。
これを行列表示すると、

\begin{pmatrix}
   1 & 0 & 0\\
   0 & 0 & 1
\end{pmatrix}

となるので、これをビジュネル方陣にかけると、

\begin{pmatrix}
   A & B & C\\
   C & A & B 
\end{pmatrix}

となります、そこで最初の一行を取り出して置換行列とみなすと、

(A,B,C)=
\begin{pmatrix}
   1 & 0 & 0\\
   0 & 1 & 0 \\
   0 & 0 & 1
\end{pmatrix}

同様に２列目も、

(C,A,B)=
\begin{pmatrix}
   0 & 1 & 0\\
   0 & 0 & 1 \\
   1 & 0 & 0
\end{pmatrix}

となります。以上を使ってビジュネル暗号化します。
細かい計算過程は省略しますが、暗号文は$(A,B,B)$となる。

もっといい説明方法がありそうだが、うまく行列を見つけられないのでちょっと放置する。
よく見ると方陣の各行が１つの置換群を成していることが分かる。
という事はビジュネル暗号もヒル暗号の特殊な場合で、古くからある暗号の歴史では文字をいかにして置き換えるかに工夫を凝らしてきたのだ。

資料が手元にないが、エニグマでは回転ローターというものが使われていたようである。
これはローターといわれる回転子、いわば巡回シフトに値するもので、行列として表現できる。

ローターはビジュネル方陣の各行に相当すると思われる。
文字ごとにローターが対応しているイメージです。
エニグマでは１つの文字を暗号化するために複数のローターが影響しながら暗号化をしているという点で優れている。
ある意味式の途中にたくさん行列を挟んで、その行列の取り方を秘密にしている感じだ。
大戦後に世界標準になったの暗号は知っている人も多いと思うがルシファーを民生用に調整したDESだった。
しかしそれでも解読されてしまったのだった。
そして現在使われているAESになる。

エニグマやAESの細かい評価はほかの記事に詳しく書いてありそうだが、自分にはよく理解できなかった。

以上で、大体ビジュネル暗号の正体が分かってきた。（ヒル暗号の一種か？）
次はエニグマをやろうか、DESをやろうかちょっと迷う。
エニグマは何故どのように解読されたのかすっきりわかる記事を探してみたい。

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%8B%E3%82%B0%E3%83%9E_(%E6%9A%97%E5%8F%B7%E6%A9%9F)
エニグマ解読には群論など暗号の代数的構造が利用されたらしい。
写像の線形性を排除するためにS-boxが導入された。

線形写像とは何かについて定義する。
1.$f(x+y)=f(x)+f(y)$
2.$f(ax)=af(x)$
この2つの性質を満たすような関数というか写像$f$を線形写像という。
例えば$f(x)=x^2$としよう。
これは非線形写像の簡単な例である。つまり、
$f(x+x)=f(2x)=4x^2$
$f(x)+f(x)=2x^2$
このように定義通りにやっても一致しないので非線形写像だと分かる。

暗号化の過程のどこにS-Boxを配置するのが効果的かはまだわからないが、AESの場合は平文を暗号化処理するラウンドの最初にS-Boxを使っているようだ。
DESやAESにはどのように影響しているのだろうか？
秘密鍵暗号の数理。

暗号文を置換し、その置換を秘密にする

ビジュネル方陣が公開されているものとする。
アルファベットが同じであり、かつアルファベットの順序が異なるとする。
またアルファベットにどのような値を割り振るかが秘密である場合も、更に暗号文の文字の順序を置換する。
アルファベットをビジュネル方陣で換字した後、暗号文を置換$\pi$で並べ替えると、それは次のように書ける。
$$\pi(C)=(c_{\pi(1)},c_{\pi(2)},...,c_{\pi(m)})$$

置換の方法を固定すると面白くないので、二つの置換$\pi,\phi$を選んで$\pi^{i+1}=\phi^i\pi^i \phi^{-i}$とすると面白いかもしれない。（ラウンド鍵のようなもの）
こうするとブロックをまたいだ長い周期の置換が得られて暗号文解析に対して強くなる可能性がある。
カシスキー検査に対してどのくらい強くなるかは、計算量的に検証する必要がある。
DESやAESがカシスキー検査をどのようにかわしているのか興味がある。
置換の巡回位数が秘密である。
1バイトずつ置換するかビット単位でやるかは未評価。

暗号文の膨張という問題（蛇足）

ここで問題なのは、もし2の場合なら暗号文が膨らむことになる。
また、26個のアルファベットは2のべき乗で表せないので効率的でない。
$m$はキーワードの長さであるが、キーワードの長さは物理的な制限があるのでこれ以上伸ばせない。
従って、ビジュネル暗号の鍵空間を大きくしたいのであれば、暗号文が膨らむことは避けられない。
アルファベットをの種類$l=256$を維持しつつ、ビジュネル方陣を置換する方法は置換をn次の対称群$|S_n|=n!$だけあるので、膨らまないように鍵を増やすことも可能かもしれない。
つまり、この改良後のビジュネル暗号の鍵の総数は、
$$|K|= {} _ {256} C_{128}*128^{32}+32!>10^{145}>256^{32}$$
となるだろうか？だとすると鍵空間は480bitより多くなる？？
多くなると格納できるメモリに上限がある場合、実装は不可能になるので、各鍵を生成するためにシードをハッシュして得られる独立した鍵を用いる。ここでは鍵生成用の単純で高速なハッシュ関数（Asconとか）などを用いて生成すればいい。
ここで、Asconを使ったハッシュ関数は考察に値する。
つまり、SHA3とどちらが高速に動作するか。或いはどちらが安全だといえるのか？

しかし、シードを使っても鍵の内部空間が広がってしまっては、メモリのサイズが増えてしまうので実現できないかもしれない。

ここで、AESなどの秘密鍵暗号は、128ビットブロックごとに処理できる、つまり暗号文を膨らませないようにしつつ、鍵のサイズを最大にできるという素晴らしい方法であると言える。

方式２の場合の結論

ビジュネル暗号は多表式暗号で、パスワードの長さが分かると簡単に文字の対応で平文が得られてしまう。
そこで暗号化モードを使って難読化する必要がある。
線形写像しか使っていないので、いずれにしても１対１の写像では弱すぎる。
この対応関係を乱数化する必要がある。
例えばエニグマのローターに相当する部分を置換群で置き換えるとかである。
秘密鍵暗号では平文と鍵をかき混ぜているだけなので、情報理論的な安全性、つまり暗号文が乱数と識別できないことが重要になるはずである。
また秘密鍵暗号は秘密鍵というブラックボックスだけを使って乱数化しなければならない。

方式２はビジュネル方陣が秘密の多標識暗号であると仮定した時の場合である。
この時、ビジュネル方陣の種類を最大にしつつ処理の効率を最適にするためには、$l=256, k=128$であればよい。

これは暗号文の膨らみを最小にすることでもある。
処理の方法としては、56ビット(7byte)読み込んで7ビットごとに処理をすることに相当するが、実装上の問題である。
ここでは、ビジュネル暗号の鍵空間を大きくすることが目的だったので、その方法の一つを提示した。
更に、暗号文を置換することで暗号文のパターンを見つけにくくできるというのは、ある意味自明な事であろう。
ビジュネル暗号はヒル暗号の一部なので、簡単な攻撃で解読できると予想できる。
具体的には、暗号化したい文字の位置に相当するビジュネル表が１つの置換群を成すことから、平文と暗号文の対応表を使って置換パターンを決定することができるはずである。
暗号文だけを使った攻撃は難しくても、選択平文攻撃には全く強くないと思われる。

予定

線形解読法や差分攻撃に対しては安全でないことが多分わかるだろう。
しかし、アリスの日記用に使う分には十分かもしれない。
なぜならアリスが一生をかけて日記を書き続けたとしても、暗号解析に必要な暗号文を得ることは不可能であるからである。
このような選択暗号文攻撃や基地平文攻撃に対して、鍵1ビット当たり（アルファベット１文字当たり）どのくらい攻撃が難しくなるかなどは面白そうなので次回に考えてみたい。

秘密鍵暗号の哲学（もしくは数理）

まだかなり先ではあるが、数理論理学におけるカリーハワード対応に関係する問題を提起する。
つまり、秘密鍵暗号は何を証明していることになるのか？という疑問である。
数理論理学では、

計算＝証明
プログラム＝証明の書き換え
データ型＝論理式

などが対応しているといわれている。

また、カオス理論との関係も期待できる。
例えば、秘密鍵暗号とは秘密鍵を予測できない誤差と考えて、結果として生成される暗号文がカオスの性質をどの程度持っているのか？という問題である。
エネルギーのやり取りがない力学系の問題になるかもしれない。

以下暗号攻撃シリーズ

Part II：カシスキー検査（煩雑な割にあまり強い攻撃でないのでつまらない。）ビジュネル暗号は選択平文攻撃に弱い。
Part III：差分攻撃法。
Part IV：線形攻撃法。

色々書いて長くなってきたので記事を分けます。

$f_u^{m_u \times m_u}(e)$