行列群を用いた公開鍵暗号（失敗作）

はじまり

行列で作られた暗号は弱いものが多い。
公開鍵を工夫することで、強い暗号は出来ないだろうか。
色々いじっているうちに面白いのが出来たので公開した。
ついでに、色々いじってみたら解読方法が見つかってしまった。
やはり関数が良くてもプラットホームがだめなのだろうか。
というわけで、行列を使った公開鍵暗号を作って攻撃してみた。

暗号化関数の構成１（共役元探索問題に還元可能）

$M_l$を$l=2,3$次正則行列とする。
以下のように、$s,t,S,T$は公開鍵、$a,b,n,m,x,d$は秘密鍵であるとする。

$$s,t,S,T,a,b \in M_l,n,m \in Z_p,x,d \in M_l$$

$$s=x^{-n+m}ax^{2n},t=x^{-n+m}bx^{2n}$$

$$S=dax^{n+m}d^{-1},T=dbx^{n+m}d^{-1}$$

未知変数の数え方：（k=2）の場合($x=(x_1,x_2,x_3,x_4)$とみなした場合)
$s=(gx+hI)(ia+jI)(kx+lI)$
$t=(gx+hI)(ob+pI)(kx+lI)$
$S=d(ia+jI)(qx+rI)d^{-1}$
$T=d(ob+pI)(qx+rI)d^{-1}$
$s/t=(ia+jI)/(ob+pI) \rightarrow s(ob+pI)=t(ia+jI)$
と書くことができるので、未知変数は、ケーリーハミルトンの定理より、

$$g,h,i,j,k,l,o,p,q,r,x_1,x_2,x_3,x_4,d_1,d_2,d_3,d_4,a_1,a_2,a_3,a_4,b_1,b_2,b_3,b_4$$

と合計36個になり、方程式の数20個より多く、未知変数を特定する事ができない。

さらに、$a,b$は暗号化に直接関係しない。
$a,b$は公開鍵の非対称な構造を実現するのに使われる。
公開鍵以外のパラメータは、単に公開鍵の代数的な構造を示しているだけに過ぎず、暗号化に必要な情報ではない。
というわけで、$s,t,S,T$は公開鍵、$a,b,n,m,x,d$は秘密鍵である。
この方式を使った暗号化と復号を以下に与える。

暗号化：$u=M \oplus H(stst),v=STST$
復号：$M=u \oplus H(x^{-2n}d^{-1}vdx^{n-m})$

行列を用いた離散対数問題は危険であるが、この方法なら安全かもしれない。

構成１に対する暗号解析

ここで復号に必要な鍵は、$w_1=d^{-1}x^{-2n},w_2=dx^{n-m}$である。
$z_1=STST$,$z_2=stst$と置く時、$z_2=w_1z_1w_2$であり、かつ$w_1,w_2$は秘密鍵として固定されている。
つまり、この問題は$z_2$から$z_1$を含む３つの元に分割する問題である。
いま$z_1,z_2$は好きなだけ取れるので、選択平文攻撃が可能である。

$$v_2=w_1v_1w_2,z_2=w_1z_1w_2$$

であるので、

$$v_2z_2^{-1}=w_1v_1z_1^{-1}w_1^{-1}$$

$q_1=v_2z_2^{-1},q_2=v_1z_1^{-1}$は既知であるので、

$$q_1=w_1q_2w_1^{-1}$$

となり、

$$q_1w_1=w_1q_2$$

これから、４つの連立方程式を解けば、秘密鍵$w_1$が求められ、同様にして残りの秘密鍵$w_2$も得ることができる。
よってこの暗号は完全に破られる。orz

さあー、残念でした。
自分としては自由群の語の問題を使った暗号のような気分でいたのですが、つまらない問題になってしまって残念です。

行列以外の非可換群

行列以外の置換群ならこの方法はうまく行くのだろうか？
あるいは、暗号化関数の設計に誤謬があったのだろうか？

この暗号では、公開鍵の構造より分割問題から共役元探索問題に変換ができる。
したがってこの暗号は、どのようなプラットホームに変えようとも、共役元探索が難しい問題を構成できなければ安全とは言えない。
この暗号系は、純粋には離散対数問題ではなく、元の分割や未知の元の算出方法が線形代数では計算できないプラットホームであることが望ましい。
楕円・スカラー半直積は、その１つではないだろうか。
楕円曲線暗号は離散対数問題を使うからいいのであって、それ以外の問題には転用する意味がないかもしれない。

結論

行列を使って公開鍵暗号が出来ないか挑戦してみた。
公開鍵を攻撃しても秘密がバレないように気を使ったが、意図せずして選択平文攻撃ができることを見つけた。
そしてこの暗号の本当の問題は、共役元探索問題であることが解った。
しかし、行列以外でこの問題が難しくなる代数系はあると思うので、それに注意すればまだ行けるかも。
とりあえず近い所で、楕円・スカラー半直積で作り直してみようと思い、その準備をしている。
本当は、語の問題を狙っていたのに残念である。
また頑張ろう。