$w_1,z_1,w_2$ が行列ならば、連立方程式を解くだけで簡単に答えを得ることができる。
したがって、このような連立方程式が得られないような代数系をこの関数に選ばなければならない。
例えば、楕円とスカラーの対からなる半直積である。
ここでは、この楕円・スカラー半直積を使って、この暗号を再構成し、暗号解読をしてみる。

楕円・スカラー半直積

半直積というのは、２つの群から新しい群を作るための方法である。
計算例を挙げる（あまり正しくない）と、

(a_1,b_1)(a_2,b_2)=(a_1b_2+a_2,b_1b_2)

のように書くことができる。
ここでは半直積の一例として群の演算にスカラー乗算と足し算を使ったが、半直積の演算はさらに柔軟である。
楕円曲線とスカラーから構成した半直積を考えると、

(P,a)(Q,b)=(bP+Q,ab)

乗算はこのような演算となる。

構成２に対する暗号解析

$w_1=z_1w_2z_1^{-1}$ である時、 $w_1,w_2$ から $z_1$ を計算する必要がある。

(R,d)=(P,a)^x(Q,c)^y(P,a)^{-x}=(P,a)^x(Q,c)^y(-a^{-1}P,-a^{-1})^{x}・・・（＊）

(Q,c),(R,d)

から、未知の半直積の元

(P,a),(P,a)^{-1}

を計算しなければならない。

構成１に置いて、複雑な鍵構造を定義したが、これは公開鍵から秘密鍵を計算できないようにするためだった。
そこで選択平分攻撃をするのだが、この関数が持っている真の問題は共役元探索問題なのだから、式＊が解けなければならない。
楕円の点を含むような連立方程式がたてられればいいが、代数的構造の異なる元が混ざる連立方程式を解くことはできるのだろうか。

一方、半直積は行列の演算としても表現できる。

\begin{pmatrix} v & P \\ 0 & 1 \end{pmatrix} \begin{pmatrix} w & Q \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} vw & vQ+P \\ 0 & 1 \end{pmatrix}

ここで、

Y= \begin{pmatrix} x & X \\ 0 & 1 \end{pmatrix}

が、求めるべき未知の元であるとすると、連立方程式は以下のようになる。

\begin{pmatrix} v & P \\ 0 & 1 \end{pmatrix} \begin{pmatrix} x & X \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} x & X \\ 0 & 1 \end{pmatrix} \begin{pmatrix} w & Q \\ 0 & 1 \end{pmatrix}

と書くことができ、

vX+P=xQ+X, vx=xw

という式を解かなければならい。

第２式は常に成り立つと解釈できるが、実際そんな事はありえない（ $x=0$ の場合のみ）ので何かがおかしい。
つまり、このような式を満たすような半直積の元 $Y$ は存在しないことになる。
存在しないものは計算できない。
というわけで、構成１の楕円・スカラー半直積バージョンは連立方程式では正しい答えを計算できないと結論したくなる。
あるいは、この半直積の演算の行列表現を間違って解釈している可能性があるので、実際に計算して確かめる必要がありそうだ。
（確かめてから書くべきだった）

で、第２式から $x$ が解ったとすると、

(v-1)X=xQ-P=R

がわかっているので、

X=(v-1)^{-1}R

であり解読できる。
この式の解釈が正しければ、楕円バージョンも解読できることになる。

半直積の構造が簡単だったので安全だと思っていたのに裏切られた。
それは今後もう少しこの関数をよく観察して見つけるべき問題であろう。

要するに行列の形でかける群は全部ダメと予想したくなる。（失敗の本質）
とりあえず次は、ベクトル・置換半直積をやる予定である。（やる前に調べる）
というかこの関数の本質が共役元探索問題なので、この関数は捨てるべきなのかもしれない。

選択平文攻撃恐るべし。

前回からの続き

暗号化関数の構成２（行列の代わりに半直積を使う）

共役元探索問題

解き方

楕円・スカラー半直積

構成２に対する暗号解析

Discussion