暗号理論の問題

一般に楕円曲線 $y^2=x^3+cx+d$ 上の加法公式を使います（この問題の曲線では $c=2,d=5$ です。秘密鍵の $a,b$ とは別の記号にしています）。すべての計算は $\mathrm{mod}31$ で行います。

• $P_1=(x_1,y_1),P_2=(x_2,y_2)$ で $x_1\ne x_2$ のとき：$\lambda =\frac{y_2-y_1}{x_2-x_1}$
• $P_1=P_2$ で $y_1\ne 0$ のとき：$\lambda =\frac{3x_1^2+c}{2y_1}=\frac{3x_1^2+2}{2y_1}$

どちらの場合も
$$x_3={\lambda }^2-x_1-x_2,y_3=\lambda (x_1-x_3)-y_1$$
です。割り算は法 $31$ での逆元を掛けて計算します。

共有点は $S=abP=b(aP)=5A$ なので、まず $A=3P$ を求め、次に $5A$ を求めます。

1. アリスの公開鍵 $A=3P$ を求める

$2P$：$\lambda =\frac{3\cdot 0^2+2}{2\cdot 6}=\frac{2}{12}$ です。$12^{-1}\equiv 13$（$12\cdot 13=156=5\cdot 31+1$）なので $\lambda \equiv 26$ です。
$x_3=26^2-0-0=676\equiv 25$、$y_3=26(0-25)-6=-656\equiv 26$ です。
よって $2P=(25,26)$ です。

$3P=2P+P$：$\lambda =\frac{6-26}{0-25}=\frac{20}{25}$ です。$25^{-1}\equiv 5$（$25\cdot 5=125=4\cdot 31+1$）なので $\lambda \equiv 100\equiv 7$ です。
$x_3=49-25-0=24$、$y_3=7(0-24)-6=-174\equiv 12$ です。
よって $A=3P=(24,12)$ です。検算すると $24^3+2\cdot 24+5\equiv 20$、$12^2=144\equiv 20$ となり、$A$ は確かに $E$ 上にあります。

2. $S=5A$ を求める（$5A=4A+A$）

$2A$：$24^2=576\equiv 18$ なので、分子は $3\cdot 18+2=56\equiv 25$、分母は $2\cdot 12=24$ です。$24^{-1}\equiv 22$（$24\cdot 22=528=17\cdot 31+1$）なので $\lambda \equiv 25\cdot 22=550\equiv 23$ です。
$x_3=23^2-48=481\equiv 16$、$y_3=23(24-16)-12=172\equiv 17$ です。
よって $2A=(16,17)$ です。

$4A=2(2A)$：$16^2=256\equiv 8$ なので、分子は $3\cdot 8+2=26$、分母は $2\cdot 17=34\equiv 3$ です。$3^{-1}\equiv 21$ なので $\lambda \equiv 26\cdot 21=546\equiv 19$ です。
$x_3=19^2-32=329\equiv 19$、$y_3=19(16-19)-17=-74\equiv 19$ です。
よって $4A=(19,19)$ です。

$5A=4A+A$：$\lambda =\frac{12-19}{24-19}=\frac{-7}{5}$ です。$5^{-1}\equiv 25$ なので $\lambda \equiv -175\equiv 11$ です。
$x_3=121-19-24=78\equiv 16$、$y_3=11(19-16)-19=14$ です。
よって $S=5A=(16,14)$ です。検算すると $16^3+2\cdot 16+5\equiv 4+32+5=41\equiv 10$、$14^2=196\equiv 10$ となります。

3. ボブ側の計算による確認

ボブの公開鍵 $B=5P$ を求めます。

$4P=2(2P)$：$\lambda =\frac{3\cdot 25^2+2}{52}\equiv \frac{17}{21}\equiv 17\cdot 3=51\equiv 20$ です（$21^{-1}\equiv 3$）。$x_3=400-50\equiv 9$、$y_3=20(25-9)-26=294\equiv 15$ なので、$4P=(9,15)$ です。

$5P=4P+P$：$\lambda =\frac{6-15}{0-9}=1$ です。$x_3=1-9-0\equiv 23$、$y_3=(0-23)-6\equiv 2$ なので、$B=(23,2)$ です。

次に $S=aB=3B$ を求めます。

$2B$：$\lambda =\frac{3\cdot 23^2+2}{4}\equiv \frac{8}{4}=2$ です。$x_3=4-46\equiv 20$、$y_3=2(23-20)-2=4$ なので、$2B=(20,4)$ です。

$3B=2B+B$：$\lambda =\frac{2-4}{23-20}=\frac{-2}{3}\equiv -42\equiv 20$ です。$x_3=400-43=357\equiv 16$、$y_3=20(20-16)-4=76\equiv 14$ なので、$3B=(16,14)$ です。

アリス側の $5A$ と一致します。

したがって $S=(16,14)$ です。

$S=15P$ を二倍と加算で求める。計算はすべて $\mathrm{mod}31$ で行う。

まず $P=(0,6)$ が $E$ 上にあることを確かめる。$6^2=36\equiv 5$ で、右辺は $0+0+5=5$ なので $P\in E$。

1. $2P$ を求める。$\lambda =(3\cdot 0+2)/(2\cdot 6)=1/6=26$ とする（$6\cdot 26=156\equiv 1$ より $6^{-1}=26$）。$x=26^2-0=676-0\equiv 25$、$y=26(0-25)-6\equiv 26$。よって $2P=(25,26)$。
2. $4P$ を求める。$\lambda =(3\cdot 25^2+2)/(2\cdot 26)=17/21=17\cdot 3=51\equiv 20$ とする。$x=400-50\equiv 9$、$y=20(25-9)-26\equiv 15$。よって $4P=(9,15)$。
3. $8P$ を求める。$\lambda =(3\cdot 81+2)/30=28/(-1)\equiv 3$ とする。$x=9-18\equiv 22$、$y=3(9-22)-15\equiv 8$。よって $8P=(22,8)$。
4. $12P=8P+4P$ を求める。$\lambda =(15-8)/(9-22)=7/18=7\cdot 19\equiv 9$ とする。$x=81-22-9\equiv 19$、$y=9(22-19)-8=19$。よって $12P=(19,19)$。
5. $14P=12P+2P$ を求める。$\lambda =(26-19)/(25-19)=7/6=7\cdot 26\equiv 27$ とする。$x=729-19-25\equiv 3$、$y=27(19-3)-19\equiv 10$。よって $14P=(3,10)$。
6. $15P=14P+P$ を求める。$\lambda =(6-10)/(0-3)=4/3=4\cdot 21\equiv 22$ とする。$x=484-3-0\equiv 16$、$y=22(3-16)-10\equiv -17\equiv 14$。よって $15P=(16,14)$。

検算として、各点が曲線上にあることを確かめた。$(16,14)$ では、$16^3=4096\equiv 4$、$2\cdot 16=32\equiv 1$ より右辺は $4+1+5=10$。左辺は $14^2=196\equiv 10$ で一致する。また $P$ を通る直線 $y=22x+6$ の $x=16$ での値は $17$ で、その符号を反転した $-17\equiv 14$ が $y_S$ に一致する。

したがって $S=abP=15P=(16,14)$。