楕円曲線の点を行列の要素に持つ公開鍵暗号を提案する。(snake oil)
実装はこちら
https://gist.github.com/anang0g0/feebf3127ef6ae3c144704a5626f9081
参考資料：https://mathematics-pdf.com/pdf/semiproduct.pdf
このシリーズのその１に基づく公開鍵暗号について説明する。
この暗号の安全性は、ガウスの消去法によって行列の体格化ができない問題にある。
もしときたければ、楕円曲線の離散対数問題を解かなければならないかもしれない。
・方式１
安全性の根拠：点群とスカラーを行列として持つ、行列の３元分割問題
アリス
秘密整数 $a,b,c,d$
A:楕円曲線上の点からなる２次行列
システムパラメーター
X:２次正則行列
暗号化
$Y=X^a(cA)X^{-a}$:楕円曲線の点
$Z=X^b(cdA)X^{-b}$：楕円曲線の点
$[X,Y,Z]$を公開鍵としてボブに送る
ボブ
乱数$s,r$
$C1=X^r sY*X^{-r}=X^{r+a}(scA)X^{-(r+a)}$
$C2=X^r sZ*X^{-r}=X^{r+b}(scdA)X^{-(r+b)}$
としてC1をアリスに送る。
アリス
C1からC2を計算する
$X^{b-a}(dC1)X^{-b+a}=C2$
この処理によってC2を共有できるので、これ使って鍵交換ができる。
安全性解析：
$Z=X^{b-a}dYX^{-b+a}.$ここで$e=b-a$と置くと$Z=X^edYX^{-e}$
更に、$ZX^e=X^{e}dY$と変形し、これをケーリーハミルトンの定理で書き直すと、
$Z(tX+uE)=(tX+uE)dY$と書ける。
しかし、ＺとＹは楕円曲線上の点なので一時従属のため、連立方程式が作れない。
・１の変形
安全性の根拠：点群を要素として持つ行列の連立方程式の不可解性
秘密情報:
$a,b \in Z_p$ 乱数:$m,r \in Z_p$
公開情報:
$A$（楕円曲線上の点E_pのなすGL(2,E_p)）
$X,Y（GL(2,Z_p )$
$Z=X^aAY^{b}$ （Yは楕円曲線上の点になる）
暗号化手順:
$C1 ＝X^r mZ X^{-r}$
$C'=H(C1) \oplus M$（Mは平文。ｍ，rは乱数、C'は暗号文）
$C2 ＝X^r mA X^{-r} $
C1,C2はともに楕円曲線上の点であるから、X*mはC1、C2をそれぞれスカラー倍すれば良い）
復号手順: 秘密鍵$X^{-a}$と$X^{-b}$をC2の両側からかけてC1を得ることで復号する。
脆弱性:
C1,C2はともに楕円曲線上の点を要素とする行列である。
つまり８要素の点の位数を決定する問題であり、これはECDLPであると思われる。
・方式２（GL(2,P)）
安全性の根拠：行列の離散対数問題
秘密情報:
$a,b,c,d \in Z_p$
ただし、 $b<a、d/c$
行列：A（行列）
公開情報:[行列]
$X$
$Y = X^a A^{c} X^{-a}$
$Z = X^b A^{cd} X^{-b}$
暗号化手順:
M: 平文、 r,s: 乱数
$C1 = X^r Y^s X^{-r}$
$C2 = X^r Z^s X^{-r}$
暗号文$C1, M*H(C2)$
復号手順:
$C1 = X^{(r+a)} A^{sc} X^{-(r+a)}$
$C2 = X^{(r+b)} A^{scd} X^{-(r+b)}$
より、
$C1'= X^{(b-a)} C1^{(d)} X^{-(b-a)}= C2$
M*C2 に、上で求めたC2の逆元を掛けて M を得る。
脆弱性：
まずAが秘密なので連立方程式による線形解読は不可能であるる。
次にケーリーハミルトンによる攻撃を考える。
$Z = X^{(b-a)} Y^{cd} X^{-(b-a)}$、ここで$e=b-a$と置くと$Z=X^eY^dX^{-e}$
更に、$ZX^e=X^eY^d$と変形し、これをケーリーハミルトンの定理を使って書くと
$Z(tX+uE)=(tX+uE)(vY+wE)$とかけ、連立方程式から$t,u,v,w$が決まる。
ゆえに、$X^e,Y^d$が得られる。
X,Y,Z は既知なので、ケーリーハミルトン攻撃で $X^{(b-a)}$ と $Y^d$ を入手できる
Y と $Y^d$ から d が求まれば、復号に必要なすべての情報が揃う
C1 の式をケーリーハミルトン攻撃して、 $Y^s$ を得る。
$Y^d$ と $Y^s$ から $Y^{ds}$ が求まれば、 $A^{scd}$ を入手できる
これは DHP (Diffie–Hellman problem) であり、一般に困難。
追記：20220218
「
https://project-euphoria.dev/blog/16-matrix/
このような方法があるために解読できる。
」
・その２の半直積の行列でないバージョン
安全性の根拠：半直積の３要素分解探索問題
20220218：追記
「
ここで、半直積の元(P,a)について考える。楕円曲線と有限体の半直積を考えて、Pを楕円曲線の任意の点、
aをGF(p)の任意の数とする。
半直積の演算より、
$(P,a)^n=((1+2+,...,+a^{n-1}P,a^n)$
となるので
$a^n$
がこの暗号のセキュリティパラメータである。
よって両側から元を掛けるタイプの暗号方式には、8192ビット程度の素体を使う必要がありあまり効率的でない。
片側離散対数問題のように片側からのみ積をとる場合にのみ効率がよくなるように思われる。
例えば次のような半直積ならセキュリティの改善になるかもしれない。
$I:Z_p$上既約な多項式
$f,g$:それぞれ2次元ベクトルの要素ｘ、ｙを決める多項式
$P=(a,b),Q=(c,d)：Z_p$ の任意の2次元ベクトル
ここで多項式環と2次元ベクトルとの半直積を考える。
半直積の元は$A=(P,(f,g)),B=(Q,(s,t))$
$AB=(P+(f(c),g(d)),((f+gs) \verb|% I ,gt % I|))$
$f,g,s,t$が2変数でなく、$Z_p$に係数を持つ1変数多項式でもいい。
このような時に半直積になるかどうか？
多項式間は既約な多項式の剰余環になるし、2次元ベクトルも加法については群になる。（ベクトルの掛け算は定義しない）
このように2つとも群の性質を持つので、この半直積も群になるはずである。
多変数多項式間とベクトルとの半直積の離散対数が難しくなるかどうかを調べなければならない。
」
アリス
秘密整数：a,b,c,d
A:(P,a)楕円曲線の点を含む半直積の元
システムパラメーター
X:(Q,b)半直積の元
$E:Z_p$上の楕円曲線
p:素数
n:楕円曲線の群位数
アリスの公開鍵
$Y=X^a(A^c)X^{−a}$:半直積の元
$Z=X^b(A^{cd})X^{−b}$：半直積の元
[X,Y,Z]を公開鍵としてボブに送る
ボブ
乱数：r,s
$C1=X^r∗Y^s∗X^{−r}=X^{r+a}(A^{sc})X^{−r−a}$
$C2=X^r∗Z^s∗X^{−r}=X^{r+b}(A^{scd})X^{−r−b}$
としてC1をアリスに送る。
アリス
C1からC2を計算する
$X^{b−a}(C1^d)X^{−b+a}=C2$
この処理によってC2を共有できるので、これ使って鍵交換ができる。
（ただし楕円の半直積を使った場合は通常の離散対数問題とECDLPのどちらか弱いほうの強度で安全性が決まる。そしてこの方法が今まで暗号とどのような意味で異なっているのかは、さらなる考察が必要である。）
・その４（行列でない１変数多項式の半直積のStickelバージョン）
まず１変数多項式環の元と、$Z_p$の要素を持つ2次元ベクトルとの半直積を考える。
n次１変数多項式環Xの2つの元を要素$(g,h)$に持つ2次元ベクトル$B,D \in X^2$ とする。
2次元ベクトルを$(e,f) \in Z_p × Z_p$として持つ元を$A,C \in Z_p × Z_p$とする。
この２つの半直積の元を$a=(A,B), b=(C,D)$とする。
この時、演算Θをベクトルの要素を１変数多項式に代入する操作とすると、半直積は
$ab=(({Θ_B}_g(C)+A,{Θ_B}_h(C)+A),BD \mod I)$
$a^n=(({Θ^n_A}_g(B)+...+{Θ_B}_g(A)+A,{Θ^n_A}_h(B)+...+{Θ_B}_h(A)+A),B^n \mod I)$
ここで$I$は3次2変数の既約多項式である。
公開情報は$a,b$である。
これだけで見ると非可換NTRUみたいだがとりあえずやってみよう。
１．アリスは乱数r,sをとり
$K_a=a^rb^s$
を計算して公開鍵として公開する。
２．ボブはランダムにu,vを選び
$K_b=a^uK_ab^v$
を計算して共有鍵を生成する。
・その４の変形（行列でない半直積の片側離散対数問題）
メリット：公開鍵サイズが半分になる
システムパラメータ：$(Q,a),(R,b)$ （stickelの特殊な場合）
アリスの秘密鍵：$u$
アリスの公開鍵：（等比数列より）
$P=R^u Q=((b^{u-1}+...+b^2+b+1)R,b^u)(Q,a)=(b^uQ+(b^{u-1}+...b^2+b+1)R,ab^u)$
$=(b^uQ+(1-b^{u-1})/(1-b)R,ab^u)$
として、Pの左側要素
$P_l=b^uQ+(1-b^{u-1})/(1-b)R$
を公開鍵とする。
暗号化：
ボブは秘密鍵vを所有して
$T=R^vQ=((1-b^{v-1})/(1-b)R,b^v)(Q,a)=(b^vQ+(1-b^{v-1})/(1-b)R,ab^v)$
に対する、ボブの公開鍵
$T_l=b^vQ+((1-b^{v-1})/(1-b))R$
を公開しているものとする。
そこでボブは
$K=R^vP=R^vR^uQ=((1-b^{u+v-1})/(1-b)R,b^{u+v})(Q,a)$
$=(b^{u+v}Q+(1-b^{u+v-1})/(1-b)R,ab^{u+v})$
の左側要素
$K_l=b^{u+v}Q+(1-b^{u+v-1})/(1-b)R$
をボブの共有鍵とする。
この時、
$K_l=K_{ba}=R^vP=R^{v+u}Q=R^uT=K_{ab}$
ここで
$R^v=((b^{v-1}+...+b^2+b+1)R,b^v)$
$R^u=((b^{u-1}+...+b^2+b+1)R,b^u)$
を計算しアリスの公開鍵$P$に左からかけて、
$R^uR^v=b^u(b^{v-1}+...+b^2+b+1)R+(b^{u-1}+...+b^2+b+1)R$
$=(b^{u+v-1}+...+b^u+b^{u-1}+...+b+1)R$
$R^vR^u=b^v(b^{u-1}+...+b^2+b+1)R+(b^{v-1}+...+b^2+b+1)R$
$=(b^{u+v-1}+...+b^v+b^{v-1}+...+b+1)R$
$R^uR^v=R^vR^u=((1-b^{u+v-1})/(1-b)R,b^{u+v})$
安全性解析：
アリスはボブの公開鍵$K_{ba}=R^vQ$に左から$R^u$をかける。そしてこの時、半直積の左側要素だけが公開されている。今攻撃者がアリスの公開鍵を解読しようとしているとする。
攻撃者はQの逆元をアリスの公開鍵Pの右からかけようとしても、公開鍵の右要素がないので積をとることができない。つまりこの暗号は単純な離散対数問題にはなりえない。（片側離散対数問題というべきか）
・その５（半直積の行列でない３要素分解問題）
公開パラメータ：$(P,a),(Q,b),(R,c)$
ここで、$a,b,c$は 8192ビットサイズの素体pの元、$P,Q,R$ は 521ビットサイズの素体q上の楕円曲線の点である。
また$s,t,u,v \in Z_p$ である。（楕円を計算するときだけ$Z_p$ の部分体として計算する）
アリスの秘密鍵：$s,t \in Z_p$
ボブの秘密鍵： $u,v \in Z_p$
$K_a$をアリスの公開鍵とすると、
$K_a=(P,a)^s(Q,b)(R,c)^t=( \sum_{i=0}^{s-1} a^{i}P,a^s)(Q,b)(\sum_0^{t-1}b^iR,c^t)=(b\sum_{i=0}^{s-1} a^{i}P+Q,a^sb)(\sum_0^{t-1}b^iR,c^t)=$
$(c^t b\sum_{i=0}^{s-1}a^iP+Q+\sum_0^{t-1}b^iR,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)$
$=((a^sb^{v+ 1}c^t(a+1)^uP+c^t b^{v+1}(a+1)^sP+Q+b^v(b+1)^tR)+b^v(b+1)^vQ,a^{s+u}b^{v+ 1}c^{t})$
（間違っている）
思い付き：「
ここで、
アリスの秘密鍵：$s,t \in Z_q,(P,R) \in E_p$
ボブの秘密鍵： $u,v \in Z_q,(A,B) \in E_p$
こうしたいところだが、異なる要素の積は非可換なのでうまくいかない。
（交換子のようにすればうまくいく方法があるのかもしれないが）
次のように考える。
この時アリスの公開鍵を$K_a$、ボブの公開鍵を$K_b$とすると、
$K_a=(P,a)+(Q,b)+(R,c)$
$K_b=(A,d)+(Q,b)+(B,e)$
として、アリスの共有鍵は
$K_{ab}=(P,a)+K_b+(R,c)$
ボブの共有鍵は
$K_{ba}=(A,d)+K_a+(B,e)=((A,d)+(P,a))+(Q,b)+((R,c)+(B,e ))$
であるが、これは離散対数問題ではない。
加法の可換性を用いたものである。
交換子バージョン
関数$Tr(K,x)$をビットストリングxの0,1に対応して鍵$K=(K_{x0},K_{x1})$をかけたものを表す関数とする。
更に、
システムパラメーター$(Q,b),(S,d)$
アリスの秘密鍵
$(P,a),(P,a)^{-1}$,長さ256のランダムビット列$x$
アリスの公開鍵
$K_{x0}=(P,a)(Q,b)(P,a)^{-1}$
$K_{x1}=(P,a)(S,d)(P,a)^{-1}$
$K_{x2}=Tr(K,x)$
ボブの秘密鍵
$(R,c),(R,c)^{-1}$,長さ256のランダムビット列$y$
ボブの公開鍵
$K_{y0}=(R,c)(Q,b)(R,c)^{-1}$
$K_{y1}=(R,c)(S,d)(R,c)^{-1}$
$K_{y2}=Tr(K,y)$
この時、
アリスはボブの公開鍵から自分の秘密のビットストリングxに対応させて
$K_{ab}=(P,a)^{-1}K_{y2}Tr(K_y,x)K_{y2}^{-1}Tr(K_y,x)^-1(P,a)$
を計算し共有カギとする。
ボブも同様に、
$K_{ba}=(R,c)^{-1}K_{x2}Tr(K_x,y)K_{x2}^{-1}Tr(K_x,y)^{-1}(R,c)$
$K_{ab}=K_{ba}^{-1}$
として鍵共有できる。
このように、その他もろもろの離散対数を使わない関数の組み合わせが可能であるが、どれが一番安全かは考察中である。
」
・その６ （その２の場合の３要素バージョン）
システムパラメーター
$P,R \in GL(2,Z_p)$
$Q$：ランダムに選んだ楕円曲線上の４つの点。
アリスの秘密鍵：$u,v$
アリスの公開鍵：$X=P^uQR^v$
ボブはランダムに$r,s$を選び、$Y=P^rXR^s$を計算し$c1=H(Y) \oplus M$として平文Mを暗号化する。
さらにQの両側から$c2=P^rQR^s$とし、暗号文を$C=(c1,c2)$としてアリスに返信する。
アリスは$c1=P^uc2R^v$を計算し$M=H(c1) \oplus C2$として平文Ｍを得る。
・その６の変形（行列でない半直積の元）
システムパラメーター：$P,R \in (E,Z_p)$
アリスの秘密鍵：$u,v \in Z_p,Q \in (E,Z_p)$
アリスの公開鍵：$X=P^uQR^v$
ボブはランダムに$r,s$を選び、$Y=P^rXR^s$を計算し$c1=H(Y) \oplus M$として平文Mを暗号化する。
さらにQの両側から$c2=P^rQR^s$とし、暗号文を$C=(c1,c2)$としてアリスに返信する。
アリスは$c1=P^uc2R^v$を計算し$M=H(c1) \oplus C2$として平文Ｍを得る。
・その７
（行列の共役元探索問題は絶望的に弱いので、３元分解問題に見せかける方法に変えてみた）
有限体上の２次正則半直積行列A,Bを考える。
システムパラメーター：$A$
アリスの秘密鍵：$B,D,AB \neq BA $（行列）$,m,n$（乱数）、$\ a|b ,a<b ,d=b/a$ （秘密指数）
アリスの公開鍵
$X=A^nBA^{-n},Y=D^{n}B D^{-n} ,\ a|b$
ボブの暗号化
メッセージをcとすると、ボブは乱数rを次のように使う。
$C=A^rX^cY^{-c}D^{-r}$
ここで暗号文はＣである。
アリスの復号
アリスはボブから暗号文Ｃを受け取ったものとする。
$Y^{-c}=D^{n}B^{-c}D^{-n}$
ここで、
$C=A^rX^cY^{-c}D^{-r}= A^{n+r}B^{c}A^nD^nB^{-c}D^{-(n+r)}$
$E=A^{-n}CD^n=A^rB^{c}A^nD^nB^{-c}D^{-r}$
である、
$P=D^rB^{c}$
$Q=A^rB^{c}$
と置くと、
$EP=QA^nD^n$
アリスは$n$を知っているので、アリスにだけ$R=A^nD^n$が計算できる。
$A^nD^n,B$はアリスにとって既知なので、ケーリーハミルトンの定理より、
$B^{c}=(uB+vI)$
ここで$\ a|b,a<b$より、$d=b/a$と置くと
$B^b=(B^{ac})^d=(uB+vI)^d$
$E(sD+tI)(uB+vI)=(xA+yI)(uB+vI)A^nD^m$
となる。
よって未知変数が4つになるので、左右の関係から連立方程式を解いて平文$c$を得る。
安全性解析：
もし$X,Y$をそのまま使えば、次のように解読される。
$C=X^cY^c$なので、$X,Y,C$は公開されている。
ケーリーハミルトンを使って、
$C=(sX+tI)(uY+vI)$
Cの要素は４なので、これらの４つの連立方程式を解けば解読できる。（瞬殺。 ちょっと実装してみたい）
公開鍵X、Y、Aはわかっている、
いま、公開鍵から$A^n,A^m$を得ようとする。すると、
$e=n-m$と置き、
$X=A^nB^aA^{-n},Y=A^mB^bA^{-m}$
より、
$A^eX^kA^{-e}=A^nB^bA^{-n}=Y$
$A^eX^k=YA^e$
ケーリーハミルトンの定理より、X,Y,Aは既知なので
$(aA+bI)(uX+vI)=Y(aA+bI)$
となり、$A^e=A^{n-m}$が解読できる。（瞬殺）
n,mを個別に計算できるかは未解決。
・その８（鍵交換）半直積の行列じゃない方
システムパラメータ：X,A
アリスの秘密鍵：a,b
アリスの公開鍵：$Y=X^aAX^b$
ボブの秘密鍵：n,m
ボブの公開鍵：$Z=X^mAX^n$
共有鍵：$K_{ba}=X^mYZX^n=X^aZYX^b=X^{a+m}AX^{b+m}AX^{n+b}=X^mYZX^b=K_{ab}$