応用数学解説

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

暗号

183

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

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

・どちらかというと工学(情報工学)の内容かも
・実用性の無視
・誤りがあったり厳密じゃなかったりする場合があります

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

OCCOのアルゴリズム

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

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

わからないよ！

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

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

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

文字	a	b	c	d
数値	0	1	2	3

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

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

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

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

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

$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 , \space{} f_1(n) = n - 1 $$

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

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

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

6. 初期値を決める

この$p$に対する初期値$n_0$を決めます。
$C \leq n_0 \lt 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 \leq{}\lambda{}_{i}\leq{}C-1$を満たす自然数であり、
適当な乱数$r\in(0,1)$を振って、事前に決めていたしきい値$q$に対し
・$r \leq{} q$ならば、$|p - n_{i}| \geq{} |p - f_{\lambda{}_{i}}(n_{i}) |$を満たすような$\lambda{}_{i}$を選ぶ。
・$r \gt{} q$ならば、ランダムな$\lambda{}_{i}$を選ぶ。
という規則に従って決められます。
これを$p = n_i$となるまで繰り返します。

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

目標$p=0$, 初期値$n_{0}=2$

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

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

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

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

$r \leq{} 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 \rightarrow b$
$\lambda_1=1 \rightarrow b$
$n_0=2 \rightarrow c$

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

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

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

同様に平文$P=$"add"のそれぞれに同じことを繰り返すと、以下のような対応が得られます。
$a \longrightarrow bbc$
$d \longrightarrow bbabd$
$d \longrightarrow 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\geq1$のとき、$f_0(n)\gt{}n,f_1(n)\geq{}n$なので、どのように値をとっても増え続けてしまいます。もし$p=0$ならば$n_i\geq{}1$になった時点で到達不可能になるのでこれも不適切です。

解決策

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

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

オペレータ集合の網羅性

オペレータ集合$f=\{f_0(n),...,f_{C-1}(n)\}$が
任意の初期値$n_0\in\mathbb{N}$と鍵$s\in\mathbb{N}$および、ある集合$A$に対して
ある$\lambda{}=\{\lambda_0,\cdots{},\lambda_n\},\space{}\lambda_i\in\mathbb{N},0\leq{}\lambda_i\leq{}(C-1)$が存在して、

$A\subset{}F=\{n_m|n_m=f_{\lambda_m}\circ{}\cdots{}\circ{}f_{\lambda_0}(n_0)\}$

を満たすとき、$f$が$A$網羅的であると言う。

また、この$F=\{n_m|n_m=f_{\lambda_m}\circ{}\cdots{}\circ{}f_{\lambda_0}(n_0)\}$を$f$の像と呼ぶことにする。

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

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

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

ある$\lambda{}$があって、オペレータ集合$f$の像$F$が
$n+1, n-1\in{}F$
を満たすとき、$f$は$\mathbb{N}$網羅的である。

$n+1\in{}F$であるとき、ある$\lambda{}=\{\lambda_0,\cdots{},\lambda_m\}$があって
$n+1=f_{\lambda_m}\circ{}\cdots{}\circ{}f_{\lambda_0}(n)=:f_{+}(n)$
任意の$k\in{}\mathbb{N}$に対して$n+k=f_{+}^k(n)$が成り立つので、$\{m | m\gt{}n_0, m\in{}\mathbb{N}\}\subset{}F$
注) $f^k$は$f$の$k$回合成