行列を用いた離散対数問題は何故解けるのか？

予感

解けると言われているけどよく知らないのでやってみました。

鍵生成

平文を$Z_p$の２次正則行列とし、それを$M$とする。
システムパラメータとして、$Z_p$の元からなる２次正則行列$x,A$を公開する。
さらに、$r_0,r_1$はアリスが使う秘密の乱数、$a,y$はボブの秘密鍵である。
この暗号の特徴は非可換群における異なる２つの問題の合体である。
つまり、共役元探索問題と離散対数問題を同時に使っている。

公開鍵

アリスはボブに秘密のメッセージを送りたい。
ボブはパラメータ$x,A$と、秘密鍵$a,y$を使って以下のように公開鍵を生成する。
ボブの公開鍵は、

$$K_b=x^aA^{y}x^{-a}$$

である。

暗号化

アリスはまず、乱数$r_0,r_1$をとって、公開されている行列$x,A$を使って次のような行列を生成する。

$$R=x^{r_1}A^{r_0}x^{-r_1}$$

次にボブの公開鍵と、行列$x$を使って平文行列$M$を次のように暗号化する。

$$C=Mx^{r_1}K_b^{r_0}x^{r_1}=Mx^{(r_1+a)}A^{yr_0}x^{-(r_1+b)}$$

生成された行列のペア$(R,C)$を暗号文としてボブに送る。

$$C'=(R,C)$$

復号

$$Z=x^aR^yx^{-a}=x^{(r_1+a)}A^{r_0y}x^{-(r_1+a)}$$

$$M=CZ^{-1}$$

問題

$K_b,x,A$から指数$a,y,r_0,r_1$を求めよ。

攻撃（ケーリーハミルトン）

公開鍵を攻撃する。

注意：この方法は他の人から教わったものです。鵜呑みにしただけで具体的に計算して確かめたものではないのでなにか間違っているかもしれません。ケーリーハミルトンというのはこういう意味で使うのですよという感じでした。

$$K_b=x^aA^yx^{-a}$$

これを、

$$K_bx^a=x^aA^y$$

と変形する。
ここで$x,A$は公開されているので、ケーリーハミルトンの定理より、

$$K_b(sx+tI)=(sx+tI)(uA+vI)$$

よってこれらの4本の連立方程式から、$s,t,u,v$が全て求まり$x^a$と$A^y$が求められる。

$x,A$を原始元として、CRTもしくはジョルダン標準形に対するPoligh-Hellman攻撃から秘密のパラメータ$a$を計算することができてしまう。

同様に、$R$から$r_1,r_0$がわかり、最終的には$C$から平文が計算できてしまう。
よってこの暗号は危険である！

まとめ

私はまだ具体的に確認してないので、線形代数の教科書で勉強したら具体例を解いて、納得したら解答例をまた書きます。固有多項式が何だかワカンネ。