暗号理論の問題

$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$ の倍数に限る」ことは用いてよい。

$p,q$ を相異なる奇素数とし、$n=pq$、$\phi =(p-1)(q-1)$ とおく。正の整数 $e,d$ は $ed\equiv 1(\mathrm{mod}\phi )$ をみたすとする（RSA 暗号の公開鍵 $(n,e)$ と秘密鍵 $d$）。中国剰余定理を使った高速な復号（CRT-RSA）のために、次を定める。
- $d_p$ を $d$ を $p-1$ で割った余り、$d_q$ を $d$ を $q-1$ で割った余りとする（$0\le d_p\le p-2$、$0\le d_q\le q-2$）。
- 整数 $u$ を、$qu\equiv 1(\mathrm{mod}p)$ をみたす整数のうちの 1 つとする（$p,q$ は相異なる素数なので、このような $u$ は存在する）。

$0\le c<n$ をみたす整数 $c$（暗号文）に対して、
- $m_p$ を $c^{d_p}$ を $p$ で割った余り、$m_q$ を $c^{d_q}$ を $q$ で割った余り（$0\le m_p\le p-1$、$0\le m_q\le q-1$）、
- $h$ を $u(m_p-m_q)$ を $p$ で割った余り（$0\le h\le p-1$）、
- $m=m_q+qh$

とおく。ここで $c$ は $n$ と互いに素であるとは限らない（$c=0$ や、$c$ が $p$ または $q$ の倍数である場合も含む）。また、整数 $a$ に対して $a^0=1$ と定める（$a=0$ のときも含む）。このとき、$0\le m<n$ かつ $m\equiv c^d(\mathrm{mod}n)$ であることを証明せよ。

ただし、フェルマーの小定理と、「整数 $x$ が相異なる素数 $p,q$ のそれぞれで割り切れるならば $pq$ で割り切れる」ことは用いてよい。

$p$ を素数とし、${\mathbb{Z}}_p=\mathbb{Z}/p\mathbb{Z}$ を $p$ を法とする剰余類全体とする。整数 $a,b$ は $a\not\equiv 0(\mathrm{mod}p)$ かつ $a\not\equiv 1(\mathrm{mod}p)$ をみたすとし、アフィン暗号の暗号化写像 $f:{\mathbb{Z}}_p\to {\mathbb{Z}}_p$ を
$$f(x)=ax+b(\mathrm{mod}p)$$
で定める。正の整数 $r$ に対して、$f$ を $r$ 回合成した写像を $f^{(r)}=\underset{r\text{個}}{\underbrace{f\circ f\circ \cdots \circ f}}$ と書く。

正の整数 $r$ について、「すべての $x\in {\mathbb{Z}}_p$ に対して $f^{(r)}(x)=x$ が成り立つ（すなわち、同じ鍵で $r$ 回暗号化すると必ず平文に戻る）」ための必要十分条件は $a^r\equiv 1(\mathrm{mod}p)$ であること（とくにこの条件は $b$ によらないこと）を証明せよ。

ただし、$p$ が素数で $c\not\equiv 0(\mathrm{mod}p)$ ならば、$cy\equiv 0(\mathrm{mod}p)$ をみたす整数 $y$ は $y\equiv 0(\mathrm{mod}p)$ に限ることは用いてよい。

英字 $26$ 文字を $\mathrm{A}=0,\mathrm{B}=1,\dots ,\mathrm{Z}=25$ と数に対応させる。整数の組 $(a,b)$ を鍵とするアフィン暗号
$$E(x)\equiv ax+b(\mathrm{mod}26)(0\le E(x)\le 25)$$
で 1 文字ずつ暗号化する。ただし $a,b$ は $0\le a\le 25,0\le b\le 25$ を満たす整数で、$\gcd (a,26)=1$ とする。

このような鍵 $(a,b)$ のうち、暗号化を 2 回続けて行うと必ず元の文字に戻る、すなわち $0\le x\le 25$ を満たすすべての整数 $x$ について
$$E(E(x))\equiv x(\mathrm{mod}26)$$
が成り立つ鍵（暗号化と復号が同じ写像になる鍵）は何個あるか。ただし $E$ が恒等写像になる鍵 $(a,b)=(1,0)$ も数に含める。

素数 $p=59$ と、法 $59$ の原始根 $g=2$ を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は $h=40$ である。秘密鍵 $x$ は $h\equiv g^x(\mathrm{mod}59)$ を満たすが、公開されていない。

送信者は平文 $m$（$1\le m\le 58$ を満たす整数）を暗号化するとき、一時鍵 $k$ を選び、
$$c_1\equiv g^k(\mathrm{mod}59),c_2\equiv m{h}^k(\mathrm{mod}59)(0\le c_1,c_2\le 58)$$
として暗号文 $(c_1,c_2)$ を送る。

ある送信者が、本来は毎回取り替えるべき一時鍵 $k$ を、2 つの平文 $m_1$, $m_2$ の暗号化に同じ値のまま使ってしまった。その結果、送られた暗号文は次の 2 つである。
$$(c_1,c_2)=(28,56),(c_1^{\prime },c_2^{\prime })=(28,43)$$
攻撃者は、1 つ目の暗号文の平文が $m_1=23$ であることを知っている。このとき、2 つ目の暗号文の平文 $m_2$（$1\le m_2\le 58$）を求めよ。