ディフィー・ヘルマン鍵共有

素数 $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=29$ と、法 $29$ の原始根 $g=2$ を公開パラメータとして、アリスとボブがディフィー・ヘルマン鍵共有を行う。アリスは秘密の整数 $a=5$ を、ボブは秘密の整数 $b=9$ を選ぶ。

アリスは $A\equiv g^a(\mathrm{mod}p)$、ボブは $B\equiv g^b(\mathrm{mod}p)$ を計算して互いに送り、それぞれ共有鍵 $K\equiv B^a\equiv A^b(\mathrm{mod}p)$ を求める。ただし $A,B,K$ はいずれも $0$ 以上 $p-1$ 以下の整数とする。

$A,B,K$ の値を、組 $(A,B,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$ を公開パラメータとして、アリスとボブがディフィー・ヘルマン鍵共有を行う。

アリスは秘密の整数 $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$ を奇素数とする。$p$ と互いに素な整数 $b$ の $p$ を法とする位数とは、$b^m\equiv 1(\mathrm{mod}p)$ をみたす最小の正の整数 $m$ のことであり、位数が $p-1$ である整数を $p$ を法とする原始根という。$g$ を $p$ を法とする原始根とする。

ディフィー・ヘルマン鍵共有では、秘密の 0 以上の整数 $a$ に対して $A=g^a$ を $p$ で割った余りが公開される。このとき、すべての 0 以上の整数 $a$ に対して
$${\left(g^a\right)}^{\frac{p-1}{2}}\equiv (-1{)}^a(\mathrm{mod}p)$$
が成り立つこと（したがって公開された値から秘密 $a$ の偶奇がわかること）を証明せよ。

ただし、次の事実は用いてよい。
- $p$ と互いに素な整数 $b$ の位数を $e$ とすると、0 以上の整数 $m$ について $b^m\equiv 1(\mathrm{mod}p)$ となるのは $e\mid m$ のとき、かつそのときに限る
- 素数 $p$ が整数の積 $uv$ を割り切るならば、$p\mid u$ または $p\mid v$ である

有限体 ${\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$ の整数の組で求めてください。

$p$ を奇素数、$g$ を $p$ を法とする原始根とする。$p$ と互いに素な整数 $c$ について、$y^2\equiv c(\mathrm{mod}p)$ をみたす整数 $y$ が存在するとき $c$ を $p$ を法とする平方剰余、存在しないとき平方非剰余という。

アリスとボブが群 $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ 上でディフィー・ヘルマン鍵共有を行う。アリスは秘密の正の整数 $a$、ボブは秘密の正の整数 $b$ を選び、$A\equiv g^a(\mathrm{mod}p)$、$B\equiv g^b(\mathrm{mod}p)$ を公開し、共有鍵を $K\equiv g^{ab}(\mathrm{mod}p)$ とする。

このとき、「$K$ が $p$ を法とする平方非剰余であるための必要十分条件は、$A$ と $B$ がともに $p$ を法とする平方非剰余であることである」を証明せよ。ただし、原始根の定義（$g$ の位数が $p-1$ であり、$p$ と互いに素な任意の整数は $p$ を法としてある $g^t$（$0\le t\le p-2$）と合同になること）と、「$g^m\equiv 1(\mathrm{mod}p)$ となる整数 $m\ge 0$ は $p-1$ の倍数に限る」ことは用いてよい。