暗号理論の問題

素数 $p=29$ と、法 $29$ の原始根 $g=2$ を公開パラメータとして、アリスとボブがディフィー・ヘルマン鍵共有を行う。アリスは秘密の整数 $a=5$ を選んで $A\equiv g^a(\mathrm{mod}p)$ を、ボブは秘密の整数 $b=9$ を選んで $B\equiv g^b(\mathrm{mod}p)$ を計算し、互いに送る（$0\le A,B\le 28$）。このとき、2 人が共有する鍵 $K\equiv g^{ab}(\mathrm{mod}p)$（$0\le K\le 28$）を求めよ。

素数 $p=47$ と、法 $47$ の原始根 $g=5$ を公開パラメータとして、アリスとボブがディフィー・ヘルマン鍵共有を行う。

アリスは秘密の整数 $a=6$ を選び、$A\equiv g^a(\mathrm{mod}p)$（$0\le A\le 46$）をボブに送る。ボブは秘密の整数 $b=9$ を選び、$B\equiv g^b(\mathrm{mod}p)$（$0\le B\le 46$）をアリスに送る。その後、アリスは $B^a\mathrm{mod}p$ を、ボブは $A^b\mathrm{mod}p$ を計算し、これを共有鍵 $K$（$0\le K\le 46$）とする。

共有鍵 $K$ を求めよ。

素数 $p=29$ と、法 $29$ の原始根 $g=2$ を公開パラメータとして、アリスとボブがディフィー・ヘルマン鍵共有を行う。

アリスは秘密の整数 $a=5$ を選び、$A\equiv g^a(\mathrm{mod}p)$（$0\le A\le 28$）をボブに送る。ボブは秘密の整数 $b=9$ を選び、$B\equiv g^b(\mathrm{mod}p)$（$0\le B\le 28$）をアリスに送る。

このとき、2 人が共有する鍵 $K\equiv g^{ab}(\mathrm{mod}p)$（$0\le K\le 28$）を求めよ。

素数 $p=47$ と、法 $47$ の原始根 $g=5$ を公開パラメータとするエルガマル暗号を考える。受信者の秘密鍵は $x=6$ である。受信者は、ある平文 $m$（$1\le m\le 46$ の整数）を暗号化した暗号文
$$(c_1,c_2)=(31,40)$$
を受け取った。ただし、送信者は秘密の整数 $k$ を選び、$c_1\equiv g^k$, $c_2\equiv m{h}^k(\mathrm{mod}47)$（$h\equiv g^x(\mathrm{mod}47)$ は受信者の公開鍵）として暗号文を作ったものとする。復号の式 $m\equiv c_2(c_1^x{)}^{-1}(\mathrm{mod}47)$ を用いて、平文 $m$ を求めよ。

有限体 ${\mathbb{F}}_{31}$ 上の楕円曲線
$$E:y^2=x^3+2x+5$$
を考えます。$E$ の ${\mathbb{F}}_{31}$ 有理点全体は、無限遠点 $O$ を単位元とし、通常の加法（弦と接線による加法）で群になります。

この曲線と基点 $P=(0,6)\in E({\mathbb{F}}_{31})$ を公開パラメータとして、アリスとボブが楕円曲線ディフィー・ヘルマン鍵共有を行います。アリスは秘密鍵 $a=3$ を選んで公開鍵 $A=aP$ を送り、ボブは秘密鍵 $b=5$ を選んで公開鍵 $B=bP$ を送ります。二人が共有する点を $S=abP$ とします。

$S$ の座標 $(x_S,y_S)$ を、$0\le x_S\le 30,0\le y_S\le 30$ の整数の組で求めてください。