その２：元の分割問題を用いた公開鍵暗号
基礎となる問題：u=x^mvx^n=x_1vx_2,vを公開鍵とした時、u,vからx_1,x_2を求める問題である。
秘密鍵：
z,n,m,l,x,aが秘密鍵とする。
公開鍵：
y=x^{-2n+m}zx^{3n}, w=x^{-n+l}zx^{2n}, X=x^{-2a}zx^{n+m}x^a, Y=x^{-a}zx^{n+l}x^a、
が公開鍵であるとする。
暗号化：まず、s,tをランダムにとり
W=y^sw^t=x^{-2n+m}zx^{m+n}...zx^{n+l}zx^{n+l}...zx^{2n}=x^{m-n}x^aX^{s-1}Y^{t+1}x^{-a}zx^{2n}
（が、xは分からない）とする。
暗号化は鍵
y^sw^tを使うものとする。
次に乱数rをとり、
と置く。更に
W'=RW=x^{(m-l)r}x^{-n+m}x^aX^{s-1}Y^{t+1}x^{-a}zx^{2n}
として乱数化する。
ここで
Z=x^{(m-l)r}X^{s-1}Y^{t+1}=RX^{s-1}Y^{t+1}とする。つまり、
W'=x^{-n+m}x^aZx^{-a}zx^{2n}である。
平文を
Mとし、ハッシュ関数を
Hと置くと、暗号化は
C=(H(Ry^sw^t) \oplus M,Z)=(C_0,C_1)である。
復号：
W'=x^{n-m}x^aC_1x^{-2n}x^{-a}z^{-1}である。ここから
H(W')を計算し、
M=C_0 \oplus H(W')となり平文Mが求まる。
攻撃：共役元探索問題が解けると仮定する。
X=x^{-a}zx^{n+m}x^a,y=x^{-a}x^{-n+m}zx^{2n}x^aの場合
(z^{-1}X)^{-1}y=z^{-1}zx^{-n-m}x^{-n+m}zx^{2n}=x^{-2n}zx^{2n}となり、共役元探索問題が解ければ
x^{2n}がわかる。しかし、
xが未知のため
nの計算ができない。
ごちゃごちゃ書いてしまいましたが、これが一番危ういです。
追試
(z^{-1}X)^{-1}y=z^{-1}zx^{-n-m}x^{-n+m}zx^{2n}=x^{-2n}zx^{2n}
に対してケーリーハミルトン攻撃をかける。
A=x^{-2n}zx^{2n}
x^{2n}A=zx^{2n}
(ex+fI)A=z(ex+fI)
よって、４本の式に対して６個の未知変数が存在するので、式の数が足りない。
ケーリーハミルトンの定理より公開鍵への攻撃
公開鍵：
y=x^{-n+m}zx^{2n}, w=x^{-n+l}zx^{2n}, X=x^{-a}zx^{n+m}x^a, Y=x^{-a}zx^{n+l}x^a、
が公開鍵であるとする。
ケーリーハミルトンの定理より、
y=(sx+tI)z(ux+vI)
w=(ox+pI)z(ux+vI)
(gx+hI)X=z(qx+rI)(gx+hI)
(gx+hI)Y=z(ex+fI)(gx+hI)
よって、未知変数は１６本の式に対して、
s,t,u,v,o,p,g,h,q,r,e,f,x0,x1,x2,x3,z0,z1,z2,z3
の２０個である。更に、
wy^{-1}=x^{-n+l}zx^{2n}x^{-2n}z^{-1}x^{n-m}=x^{l-m}
となり、
Y^{-1}a^{-1}aX=x^{-n-l}z^{-1}zx^{n+m}
であるから、
最終的に
z,aが消える。さらに、
wy^{-1}=x^{l-m}
Y^{-1}X=x^{m-l}
から、
wy^{-1}=XY^{-1}となり、全部消えてしまい、肝心の秘密鍵である指数などの値が計算できない。
つまるところ、これは攻撃すると消える暗号？なのかもしれないがちょっと考えます。
暗号文をケーリーハミルトンで解読する
W'をケーリーハミルトンで変形すると、
W'=RX^{s-1}Y^{t+1}=x^{(m-l)r}X^{s-1}Y^{t+1}=(ax+bI)(cX+dI)(eY+fI)
となる。この時未知定数は、
x_0,x_1,x_2,x_3,a,b,c,d,e,f,a_0,a_1,a_2,a_3
の１０個であり、方程式の数は４つなので解読できそうにない。
結論
ケーリーハミルトン攻撃に対抗できる行列を使った公開鍵暗号を作ったのだろうか？
この暗号は、公開鍵にケーリーハミルトン攻撃をかけると必要な秘密鍵が全部消えてしまう。
そんなにうまい話はそうないので、後日数値例で確認する。
他にもっと有効な解読法がないか考える。
Discussion