さて第一の方法は次のようなものであった。
20220205追記：
「
https://arxiv.org/pdf/1210.8114.pdf
こんなこともあるので安心できない。
以下は私のに近いアプローチ。
Exploring platform (semi)groups for non-commutative keyexchange protocols
Ha Lam
Graduate Center, City University of New York
くそー先駆者がいたか！ｗ
http://shpilrain.ccny.cuny.edu/semidirect.pdf
半直積の離散対数が新しくないのであれば、半直積の３分割問題なら新型かもしれない。
」
20220206：追記
「
半直積の場合に関係のありそうな研究を発見。
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902138431024555
」
20220207:追記
「
攻撃法：https://eprint.iacr.org/2021/644.pdf
でも、楕円バージョンなら安全かもしれない。
」
１つは行列$A,B$は有限体の元が入る行列。
そしてもう一つの行列$X$は楕円曲線上の点を要素に持つ行列。
さらに行列Zを以下のように構成し、Xとともに公開する。
$Z=AXB$、$Y$
このようにした場合、$(Z、X)$から$A,B$を計算するのは簡単だろうか？
これを分解元探索問題という。
具体例を示そう。$G$を楕円曲線の任意の点として１つ固定する。
この時２×２の行列を、
P=
\begin{pmatrix}
1 & 2 \\
3 & 4
\end{pmatrix}
Q=
\begin{pmatrix}
G & G \\
G & G
\end{pmatrix}
R=
\begin{pmatrix}
5 & 6 \\
7 & 8
\end{pmatrix}
とすると、3つの行列の積$S=PQR$は
S=
\begin{pmatrix}
3G & 9G \\
7G & 10G
\end{pmatrix}
mod 11
となる。
これがスカラー行列と楕円の行列演算だ。
これを暗号に使う場合は、スカラー行列P,Rの離散対数が必要になるはずである。
追記:20220123
「
行列Qは全部同じ曲線からの点なので、同種写像を持つもう一つの曲線から1点Fを持ってきて行列Qを
Q=
\begin{pmatrix}
G \\
F
\end{pmatrix}
mod 11
のようにして、
PQ=
\begin{pmatrix}
G + 2F \\
3G + 4F
\end{pmatrix}
mod 11
のが正しいかもしれないがよくわからない。（汗；
ガウスの消去法を使うとしたらこちらなのだが、例を見てわかる通りどちらを消そうとしても何倍すればいいのかわからない。
」
この場合$S$と$Q$は公開されているものとする。
秘密鍵は$P$と$R$のスカラー行列だ。
このスカラー行列の未知係数を８個記号化して連立方程式を立てたとする。
いまRがPの逆行列だと仮定すれば、連立方程式の数はちょうど４つになり、解読できるはずである。
しかしここで問題になるのは、何倍すれば行列が体格化できるのかわからないという事だ。
これを解くためには通常ガウスの消去法を使う必要があるが、ガウスの消去法の楕円バージョンはうまくいかないのである。
これをもしときたければ、ECDLPを解かなければならないのではないか？
20220202：追記
「
この問題の場合加法に関する離散対数問題は構成できるが、これはECDLPと同じである。
なのであまり意味がない。
この問題は共役元探索か行列分解問題の楕円曲線バージョンにするのが適切かと思われる。
また両側から挟む行列の離散対数だが、ただ単に積をとるだけならXの位数によって周期が決まる。
」
ここで行列型楕円暗号の演算を半直積*で表すと、
W=
\begin{pmatrix}
\begin{pmatrix}
G & 2G \\
3G & 4G
\end{pmatrix}
,
\begin{pmatrix}
1 & 2 \\
3 & 4
\end{pmatrix}
\end{pmatrix}
Z=
\begin{pmatrix}
\begin{pmatrix}
G & G \\
G & G
\end{pmatrix}
,
\begin{pmatrix}
5 & 6 \\
7 & 8
\end{pmatrix}
\end{pmatrix}
\\
W*Z=
\begin{pmatrix}
\begin{pmatrix}
G & 2G \\
3G & 4G
\end{pmatrix}
\begin{pmatrix}
5 & 6 \\
7 & 8
\end{pmatrix}
+
\begin{pmatrix}
G & G \\
G & G
\end{pmatrix}
,
\begin{pmatrix}
1 & 2 \\
3 & 4
\end{pmatrix}
\begin{pmatrix}
5 & 6 \\
7 & 8
\end{pmatrix}
\end{pmatrix}
mod 11
と、これが提案する方式の一つである行列の半直積だ。（これはスカラーと楕円の半直積だが、スカラーの離散対数と行列型楕円など、ほかにも半直積の行列や、行列でない場合など色々バリエーションがあるがまだまとまっていない）
これは行列の半直積だが、無駄に鍵サイズが大きいので、このシリーズにおける最終回にある１つの元に対する半直積のほうが効率的だろう。
また、スカラー行列と行列型楕円の暗号については、最終回にある暗号方式にその６として付け加えた。
このことが本当にうまくいくかどうかを以下で調べていきたい。
（もう寝るｗ）
追記：20220124
「
ただ行列にするだけでは暗号として面白くない。
楕円型行列群の位数の場合のケーリーハミルトンの定理を理解していない。
どのような場合に行列群の位数が最大になるのか確かめてみる。
20220202追記：
「
単に行列群の位数を求めたいという問題を考える分には適切か？
」
予想としては(定義体のサイズ)^行列の次元-1。まあ高校数学レベル。
最大位数の行列群は存在するのだから、そのままでは楕円曲線の点を使う意味があまりない。
なんのために楕円曲線の点群を使うのか、楕円曲線の点群と行列群の位数にどんな関係があるのか説明できなければならない。
（20220202追記：点にしたら線形代数で解読できないので安全だと思っていたが、上の方法だとECDLPに還元されるので何も変わらない。アイデアがカオスｗ）
そのために行列バージョンの共役元探索問題が線形代数を使ってどのように破られるのか理解し、楕円曲線の点群を使うことでその攻撃を防ぐことができるかどうか確かめる必要がある。また点群の離散対数とその半直積バージョンのケーリーハミルトンの定理との関係を調べる。
ここに新しい材料を使う「なにか新しいこと」がありそう。（ホントに？）
」
・半直積再訪
もう一度半直積に戻ろう。その１で点とスカラーからできる元の半直積は非可換であることを示した。
それは以下のようなものだった。
半直積とは楕円曲線の点群と、有限体上の乗法群の２つの群の要素$(P,Q) \in E_p$（楕円）、
$(c,d) \in GF(p)$（有限体）があったとき、この２種類の異なる要素のペアに対する演算 $*$を
$(P,c)*(Q,d)=(dP+Q,cd)$ と定義したものである。この時演算の順序を変えると、
$(Q,d)(P.c)=(cQ+P,cd)$となり、半直積は非可換であることがわかる。
今度は行列でなく、3つの要素を使って分解元探索問題を作る。
1・ $ (P,c)(Q,d)(R,e)=(dP+Q.cd)(R,e)=(e(dP+Q)+R,cde)$
20220206:追記
「
ここで式１の右要素は公開しなくてもいいようだ。
つまり楕円曲線と同じサイズの離散対数を使っても、右要素から秘密指数を解読される危険がないという事になる。
」
非可換の性質から、この場合は分解元探索問題を作ってみる。
今秘密の元$(P,c),(R,e)$があったとき、その合成は式１となる。
これを式１と$(Q,d)$から計算しなければならない。
しかし式１の共役元探索のみを使った方式は、公開情報と秘密情報を併せ持つ変な構造を持っている。
暗号文の実態は楕円曲線の点なのでサイズはそんなに大きくなく、計算も簡単である。
この半直積の非可換バージョンを使った暗号化関数は以下の通りである。
システムパラメーター$A=(P,a),X=(Q,b),B=(R,c)$:点の半直積。
ここで、P,Q,Rは521ビットサイズの楕円曲線の点、a,b,cは8192ビットサイズの素体の元である。
アリスの秘密鍵：乱数$s,t$
ボブの秘密鍵：乱数$u,v$
１．鍵生成：
アリスはランダムにs,tをとり、$K_a=A^sXB^t$を公開鍵とする。
$K_a=(P,a)^s(Q,b)(R,c)^t=((a+1)^sP,a^s)(Q,b)((b+1)^tR,c^t)=
(b(a^{s-1}+...+a^2+a+1)P+Q,a^sb)((b^{t-1}+...+b^2+b+1)R,c^t)=(c^t b(a^{s-1}+...+a^2+a+1)P+Q+(b^{t-1}+...t^2+t+1)R,a^sbc^t)$
更に、ボブは
$x^uK_ay^v=((a+1)^uP,a^u)(c^t b(a+1)^sP+Q+(b+1)^tR,a^sbc^t)((b+1)^vQ,b^v)$
$=(a^sbc^t(a+1)^uP+c^t b(a+1)^sP+Q+(b+1)^tR,a^{s+u}bc^{t})((b+1)^vQ,b^v)$
$=(b^v(a^sbc^t(a+1)^uP+c^t b(a+1)^sP+Q+(b+1)^tR)+b^v(b+1)^vQ,a^{s+u}b^{v+ 1}c^{t})$
としてアリスとの共有カギを得る。
（式変形の間違い。）
２．暗号化：
ボブはランダムにu,vをとり、$K_b=A^uXB^v,c1=A^uK_aB^v ,c=m \oplus H(c1)$
を計算し、$K_b,c1,c$を暗号文としてアリスに送る。
３．復号化
アリスはボブから受け取った$c,K_b$から、$K=A^sK_bB^t$を計算し、$m=c \oplus H(K)$
として平文ｍを得る。ここにHはハッシュ関数。
この関数は、点とスカラーの行列に対しても使える。
20220202追記：
「
問題設定の間違い。（抹消済み。歴史修正主義ｗ）
この関数は普通の離散対数問題に還元されるが、関数が真ん中の要素が公開されていれば右成分の離散対数が計算できるし、共役元として定義するためには最初からなにも公開されてないのと同じなので間違い。
」
ここでゼロ知識証明をやってみよう。
アリスは秘密の元$(A,c),(B,d)$を持っていて、$Y=(P,c)(Q,d)(R,e)$を公開しているものとする。
１．アリスはランダムに点R,Sと乱数rを選び$A=(R,r)(P,a)(S,s)$をボブに送る。
２．ボブはランダムにチャレンジビットbを０か１に選び、アリスに送る。
３．アリスはボブのチャレンジビットに対して次のような計算をしてボブに送る
b=0:アリスは$(R,r), (S,s)$を送る。
b=1:アリスは$A=(P,c)*(R,r)^{-1},B=(R,r)^{-1}(S,s)$をボブに送る。
４．ボブの検証
$b=0:(R,r),(S,s)$を使ってアリスの最初の送信データと一致することを確認する。
$b=1:$ボブは$Y=AXB$を確認する。
もう一つ考えてみました。(20220123)
$P,Q \in E_p,a,b \in F_p$
としたとき、元 $x=(P,a),y=(Q,b)$として公開する。
アリスはランダムに整数$s,t \in F_p$をとり、
$K_a=x^sy^t=(P,a)^s(Q,b)^t=((a+1)^sP,a^s)((b+1)^tQ,b^t)=(b^t(a+1)^sP+(b+1)^tQ,a^sb^t)$
ボブも同様に整数$u,v \in F_p$をとり、
$K_b=(x^uy^v)=(b^v(a+1)^uP+(b+1)^vQ,a^ub^{v})$
二人の共有鍵は、
$x^sK_by^t=x^{s+u}y^{t+v}=x^uK_ay^v$
となるはずである。というのも、
$A=(P,a)(Q,b)=(bP+Q,ab)$
$B=(P,a)^2(Q,b)^2=((a+1)P,a^2)(Q,b)(Q,b)=(b(a+1)P+Q,a^2b)(Q,b)=$
$(b^2(a+1)P+(b+1)Q,a^2b^2)$
$xAy=(P,a)(bP+Q,ab)(Q,b)=(abP+bP+Q,a^2b)(Q,b)=(b(abP+bP+Q)+Q,a^2b^2)$
$(b^2(a+1)P+(b+1)Q,a^2b^2)$
$B=xAy$であることがわかる。（間違っているかもしれない。）
つまりボブも同じ鍵を共有できる。
$x^sK_by^t=((a+1)^sP,a^s)(b^v(a+1)^uP+(b+1)^vQ,a^ub^{v})((b+1)^tQ,b^t)=$
$(a^ub^v((a+1)^sP)+b^v(a+1)^uP+(b+1)^vQ,a^{s+u}b^{v})((b+1)^tQ,b^t)=$
$(b^t(a^ub^v((a+1)^sP)+b^v(a+1)^uP+(b+1)^vQ)+(b+1)^tQ,a^{s+u}b^{t+v})=$
$(a^ub^{t+v}(a+1)^s+b^{t+v}(a+1)^u)P+(b^t(b+1)^{v}+(b+1)^t)Q,a^{s+u}b^{t+v})=$
$(b^{t+v}[a^u(a+1)^s+(a+1)^u]P+[b^t(b+1)^{v}+(b+1)^t]Q,a^{s+u}b^{t+v})$ ??
複雑なので後でプログラムして確認します。
オリジナルの方法(Stickel)は行列を使ったもので、線形代数で解読できる。
https://www.researchgate.net/publication/220719747_Cryptanalysis_of_Stickel's_Key_Exchange_Scheme
これなら線形代数は使わないので、アリスとボブが送った離散対数、$s,t,u,v$がわからなければ解けないものと思われる。
解読者は$s,t,u,v$が個別に分からなければならない。
20220206：追記
「
右要素は公開する必要がない。
つまりアリスはボブに左成分だけ送ればいいので、ボブは右要素がわからなくてもよい。
なので右側の離散対数問題から秘密指数が解読されることはない。
」
以前これと同じ暗号化関数を置換群で構成してみたのだが、置換群の離散対数は弱く複数の方法で解読できるものだった。この関数は離散対数問題と非可換群の３元分解問題を使っているのだが、その複雑さが暗号解析を難しくしている可能性がある。
しかし今回は本物の非可換代数（群環？）なのでうまくいくことを期待する。（つづく）