自作した暗号を数学的に補強したい
こんにちは、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$回合成
$n-1\in{}F$のときも同様にして、$\{m | m\lt{}n_0, m\in{}\mathbb{N}\}\subset{}F$がわかる。
また、$n_0\in{}F$
ゆえに、$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}$網羅的であるための必要条件は？
でも疲れたので続きは次回以降の記事に。
それではまた(突然の別れ)