自作した暗号を数学的に補強したい

こんにちは、Nappleです。
今回は自作した暗号の説明と、その背景で動く理論を数学的に検討していきます。

以降、今回扱う暗号をOCCO(Operators Chain COde)と呼ぶことにします。

余談: Mathlogのユーザは当然数学系の人が多い一方で、工学系や自然科学系の記事もある程度存在するように感じる。どれくらいの比率なんでしょう…

OCCOのアルゴリズム

厳密な実装とは少々異なりますが、大枠は同じです。

1. 文字と数値($0$以上$M$未満)を対応付ける変換表を用意する。
2. 入力として 平文$P$と鍵$s$を受け取る。
3. 鍵$s$から区切り値$C$を設定する
4. 平文$P$から1文字取り出して、対応する数字を$p$とする。
5. 鍵$s$に依存する$n$の関数$\{f_0,f_1,\cdots ,f_{C-1}\}$を用意する。
6. $p$に対して初期値$n_0$($C$以上$M$未満)をランダムに設定する。
7. $p$と$n_i$が等しくなるまで$n_{i+1}=f_{\lambda {}_i}(n_i)$を繰り返す。このとき、
   　・確率$q$で$|p-n_i|\ge |p-f_{\lambda {}_i}(n_i)|$を満たすように
   　・そうでなければランダムに
   $\lambda {}_i\in (0,1,\cdots ,C-1)$を選ぶ。
8. 各$\lambda {}_i$と初期値$n_0$を、変換表を使って文字に逆変換して並べる。
9. 平文$P$のすべての文字に対して4.から8.を繰り返す。
10. 9.を並べる。

わからないよ！

自分もよくわかってないです。説明が煩雑ですみません。
例をあげて考えていきましょう。

1. 文字と数値を対応付ける変換表を用意する

まず変換表を用意します。今回は4つの文字で考えます。($M=4$)

2. 入力として平文$P$と鍵$s$を受け取る。

平文： $P=$"add"
　鍵： $s=3$
としましょう。
注：平文というのは暗号化したい元の文字列のことです。

3. 区切り値$C$を決める

区切り値$C$は、使用する$M$個の文字のうち$C$個を関数（オペレータ）を指す記号に使うと決めるための値です。残りの$M-C$個は初期値を指す記号に使います。

今回は$C$を次の式で決めることとします。
$C=(s+1)\mathrm{\%}(M-2)+2$
$\ast a\mathrm{\%}bはaをbで割ったあまりを指す\ast$

$s=3,M=4$なので$C=2$になります。

4. オペレータ$f_j$を用意する

オペレータというのは$n$を変数として持つ関数$\{f_0(n),f_1(n),\cdots ,f_{C-1}(n)\}$のことです。
オペレータは予め決めておくもので、最大$C$種類設定できます。

今回の例では$C=2$なので、$\{f_0,f_1\}$を以下で定義します。
$$f_0(n)=n+s,f_1(n)=n-1$$

5. 文字を取り出して数値にする

事前の準備が済んだので、ここからは実際に暗号化する作業になります。

まずは平文$P=$"add"から最初の文字"a"を取り出しましょう。
さらに、変換表を使って平文を数値にします。
$a$に対応するのは$0$なので、$p=0$です。

6. 初期値を決める

この$p$に対する初期値$n_0$を決めます。
$C\le n_0<M$を満たす整数をランダムに取ればいいので、今回は仮に$n_0=2$だったとしましょう。

7.$p=n_i$になるまでオペレータを適用する

目標の値$p$に一致するように、規則に従って初期値$n_0$にオペレータ$f_{\lambda {}_i}$を適用していきます。

つまり以下が成り立ってほしいわけです。
$p=f_{\lambda {}_{K-1}}(\cdots (f_{\lambda {}_0}(n_0))\cdots )=f_{\lambda {}_{K-1}}\circ \cdots \circ f_{\lambda {}_0}(n_0)$

この$\lambda {}_i$は$0\le \lambda {}_i\le C-1$を満たす自然数であり、
適当な乱数$r\in (0,1)$を振って、事前に決めていたしきい値$q$に対し
・$r\le q$ならば、$|p-n_i|\ge |p-f_{\lambda {}_i}(n_i)|$を満たすような$\lambda {}_i$を選ぶ。
・$r>q$ならば、ランダムな$\lambda {}_i$を選ぶ。
という規則に従って決められます。
これを$p=n_i$となるまで繰り返します。

しきい値$q=0.5$として、実際にやってみましょう。

目標$p=0$, 初期値$n_0=2$

(1)乱数を振って$r=0.7$が出た。

$r>q$なので適当に$\lambda {}_0$を選びます。
${\lambda }_0=1$: $n_1=f_{\lambda {}_0}(n_0)=n_0-1=1$

$p\ne n_1$なので続けます。

(2)乱数を振って$r=0.2$が出た。

$r\le q$なので差が小さくなるような$\lambda {}_1$を選びます。
${\lambda }_1=1$: $n_2=f_{\lambda {}_1}(n_1)=n_1-1=0$

$p=n_2$なのでここで終わりです。
このようにして数列$\lambda =({\lambda }_0,{\lambda }_1)=(1,1)$が得られました。

8. オペレータと初期値を文字に戻す

求めた$\lambda$と$n_0$を変換表を使って文字に戻します。
${\lambda }_0=1\to b$
${\lambda }_1=1\to b$
$n_0=2\to c$

なので、並べると"bbc"が得られます。これが入力の"a"に対応してるというわけですね。

ちなみに、これはただの決めごとなのですが$\lambda$は逆順に並べます。

9. すべての文字に対して繰り返す。

同様に平文$P=$"add"のそれぞれに同じことを繰り返すと、以下のような対応が得られます。
$a⟶bbc$
$d⟶bbabd$
$d⟶bbbabac$

最終的にこれらを並べた"$bbcbbabdbbbabac$"が平文$P$に対する暗号文として得られます。
やったー！

※復号のアルゴリズムは解説しませんが、(多分)一般に一意な復号が可能です。

ざっくりした利点と欠点

利点

・乱数を含んでいるので必ずしも1対1にならない
・自由度が高い

欠点

・オペレータの適切な設定方法が不明
・暗号文の長さ(符号化率)が一定でない
・区切り値の適切な設定方法が不明 (実装で解決可能)
・文字の出現確率に偏りがあり解読が容易 (実装で解決可能)

ここから本当の本題

前置きが非常に長くなりましたが、ここからが本題で、欠点の1つ目に上げた「オペレータの適切な設定方法が不明」という問題についてです。

今回の例では有限回のオペレータの適用で必ず暗号化できるようなオペレータを取りました。しかし、オペレータはある程度複雑であるほうが好ましいですし、どのような変換表でもどのような鍵でも動く必要があります。
どのような条件をつければオペレータは適切になるのでしょうか。

うまく行かない例を見てみましょう。

うまくいかない例

(1)有限回の試行で$p$にたどり着けない場合

$f_0(n)=n$
$f_1(n)=sn$

これはどのように$s$を取ったとしても、初期値$n_0$の$s^k$倍しか取ることができません。もし$p=n_0(s-1)$のような場合、一般にはたどり着くことができないのでこれは不適切です。

(2)発散して$p$にたどり着けなくなる場合

$f_0(n)=n+1$
$f_1(n)=2n-1$

これは$n\ge 1$のとき、$f_0(n)>n,f_1(n)\ge n$なので、どのように値をとっても増え続けてしまいます。もし$p=0$ならば$n_i\ge 1$になった時点で到達不可能になるのでこれも不適切です。

解決策

以上のような問題を解決する、オペレータ設定方法を考えましょう。

と、その前に、新たな用語を定義しておきます。

これを使うと、今求めているのは$\mathbb{N}$網羅的な$f$ということになります。

うまくいかない例で示した2つのオペレータ集合の像はそれぞれ、
(1) $F=\{sn|n\in \mathbb{N}\}$
(2) $F=\{n|n_0\le n,n\in \mathbb{N}\}$
となるので$\mathbb{N}$網羅的ではありません。

$f$が$\mathbb{N}$網羅的であるための十分条件

考えてみれば当たり前ですが、こういうことが成り立ちます。

最適な$f$の例

(1)$f_1(n)=n+1,f_2(n)=n-1$ : 最小の$\mathbb{N}$網羅的オペレータ集合
(2)$f_1(n)=2n,f_2(n)=n-1$
(3)$f_1(n)=n^2,f_2(n)=2n-1,f_3(n)=n-3$

でも、待って

最適な$f$はその像が$n+1,n-1$を持つことがわかりましたが、まだ問題は解決しません。

・任意の$C$や$s$に対して最適な$f$を設定する方法は？
・$f$が$\mathbb{N}$網羅的であるための必要条件は？

でも疲れたので続きは次回以降の記事に。
それではまた(突然の別れ)