前の記事
共役元探索問題とは？
共役元を探す問題は、ブレイド群などの一部の群では難しい問題ですが、置換群では行列表現できるので線形代数攻撃て簡単に解かれてしまいます。
これを難しくすることができるかどうか試すのがこの記事の目的です。
共役元を探す問題とは、ある群の元a,bがあって、$c=aba^{-1}$の時、$c,b$からaを求める問題です。そこで考えたのが置換群と、ベクトルの半直積を使うという方法です。
ここで、$Y=(B,\phi)$がわかっているので、置換群の共役は簡単に計算できるので、$\pi\phi\pi^{-1}$はわかりますが、問題はAです。Aは秘密のまま変形されてBを引いてもオリジナルのAはわからないままです。というわけで、半直積を使えば非可換群を使った鍵交換のように、置換群を使いながら共役源の半分だけを秘密に保てることがわかりました。
$(\pi(B),\pi\phi\pi^{-1})$これは計算できる。
$(-\pi\phi\pi^{-1}(A)+A)$ これからAを計算するのは不可能？
$\rightarrow$可能である。
というわけで半直積も使えないわけですね。悲しい。
やっぱり半直積でも難しい問題を使わないといけないみたいですね。
片方だけ秘密なんておかしいと思った。
あーつまんない。ｗ
ああ、やっぱりだめだった・・・（ファイアーエムブレム外伝）
共役元：$Z=X^{-1}YX=(A,\pi)(B,\phi)(-\pi(A)^{-1},\pi^{-1})=(\pi(B)+A,\pi\phi)(-\pi(A)^{-1},\pi^{-1})=(A-\pi\phi\pi^{-1}(A)+\pi(B),\pi\phi\pi^{-1})$
ところで$\phi\pi\phi^{-1}$は行列で、Aを未知のベクトル$(x,y,z)$と置きましょう。
$[121][212][312]=\phi\pi\phi^{-1}=P$とすると
$P(x,y,z)+(x,y,z)=(P+E)(x,y,z)=(1,2,3)$と書くことができます。
つまり解読できちゃいました。
残念。
（20230504:ちょっと間違えていたので直しました）
もう少し頑張ってみましょう。
整数ベクトルの代わりに多変数多項式$f,g,h \in Z[x1,x2,x3])$としましょう。
そして上にある解読方程式、
$(P+E)(f,g,h)=(f',g',h')$
に入れてみましょう。これも置換して足すだけなので、やはり駄目なようです。
楕円曲線の点の場合
次に楕円曲線の未知の点$(A,B,C)$を入れてみましょう。
$(P+E)(A,B,C)=(A',B',C')$
これはちょっとわかりにくいですね。なぜでしょう？
整数、多項式は環でしたが、楕円の点は加法群だからでしょうか。
今やっていることは、ただ点を入れ替えて足すだけでいいのです。
点ベクトルの場合、足したあとの位数の情報は店の中に吸収されてしまい取り出せません。
今の場合は置換行列ですが、これが普通の整数行列だとすると、多項式の係数に楕円の点が来るということになって、連立方程式さえできなくなります。
今やっている解法は連立方程式を解く方法なので、楕円の点には適用できないことがわかります。
なのでもう少し慎重に考える必要はありますが、ある程度の大きさの位数を持った楕円の点ならうまくいくかもしれません。
しかし今の場合、点の位置だけしか問題にならない（スカラーが０か１だけ）なので解読できる可能性が高いです。
これで少なくとも、置換の代わりに整数ベクトルを使えばうまく行きそうだということがわかりました。
点ベクトルと整数ベクトルの場合
こんどは置換をやめて整数ベクトルを使ってみましょう。
点ベクトルと整数ベクトルの対を(A,a),(B,b)とします。
共役元問題は
$CC=(A,a)(B,b)(-A,-a)=(aB+A,a+b)(-A,-a)=(aB+A-(a+b)A,b)$
として計算され、$(A,a)$は秘密です。
公開情報は$CC,(B,b)$です。これから$(A,a)$を計算できるかどうかが今の問題です。
ちなみにここでは、整数ベクトルは楕円と同じ加法軍しか使っていないことに気をつけましょう。
こうすることでなにか嬉しいことがあるかと期待しているのですが、一つには小さな楕円曲線の点を６４個を使って、６４バイトくらいの整数ベクトルを使えば難しくなるかもしれないという感じです。でもまあそれだったら最初から楕円を使えばいいだけの話で、あまり意味がないような気がします。小さいベクトルのほうが高速だとか言うなら別ですがｗ
わかったら書きます。
整数ベクトルと多項式の場合
20230506：追記（解読できるとはいえない）
楕円は珍しくなくてつまらないので、多項式と数ベクトルにしてみましょう。
多項式とベクトルの対を$(F,s)$として共役元問題を書くと、
１．スカラー版：
$F=(x,f)(v,g)(-x,-f^{-1}(x))=(f(v)+x,f+g)(-x,-f{-1}(x))=(-(f+g)(f^{-1}(),f+xg+f,v)=(-vfx^{-1}+xg,v)$
$G=(x,f)(v,g)(-xf^{-1},-f)=(vf+x,f+g)(-xf^{-1},-f)=((f+g)(-xf^{-1})+vf+x,g)
=(-xf^{-1}g+vf,g)$
２．代入版：（20230509:追記）
１．$(f,a)(f,a)^{-1}=(f,a)(-a^{-1}f,a^{-1})=(f(x)-f(x),aa^{-1})=(0,1)$
２．$(a,f)(a,f)^{-1}=(a,f)(-af^{-1}(a),f^{-1})=(a-a(f(a)f^{-1}(a)),ff^{-1})=(0,1)$
１の場合：
$(f,a)(g,b)(f,a)^{-1}=(f+ag,ab)(-a^{-1}f,a^{-1})=(-bf+f+ag,b)$
２の場合：
$(a,f)(b,g)(a,f)^{-1}=(f(b)+a,fg)(-af^{-1}(a),f^{-1})=(fg(-af^{-1}(a))+f(b)+a,g)$
多項式だけの場合
$(f,g)(s,t)(-g^{-1}f,g^{-1})=(sg+f,gt)(-g^{-1}f,g^{-1})=(-tf+sg+f,t)$
今$t,s$がわかっているので、左要素をtで剰余を取ると、$sg+f$が残る。
次にこれを$(sg+f)\bmod s=f$
で、解読。
まあ、たまたま自分が乗法軍だけの群を置換群しか知らなかったということで置換群にこだわっていたのですが、置換にこだわっていると暗号はいつまでも作れないことになりそうなのでもっといいネタを仕入れる必要がありますね。いつでも勉強ｗ
というわけで一番有望なのは、楕円と数ベクトルのようです。