暗号理論の問題

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

素数 $p=43$ と、法 $43$ の原始根 $g=3$ を公開パラメータとするエルガマル暗号を考える。受信者の秘密鍵は $x=5$ であり、公開鍵 $h\equiv g^x(\mathrm{mod}43)$ を公開している。送信者は平文 $m$（$1\le m\le 42$ の整数）を、ある整数 $k$ を用いて
$$c_1\equiv g^k,c_2\equiv m{h}^k(\mathrm{mod}43)(0\le c_1,c_2\le 42)$$
と暗号化し、暗号文 $(c_1,c_2)=(38,22)$ を受信者に送った。受信者が秘密鍵 $x=5$ を用いて復号して得る平文 $m$ を求めよ。

素数 $p=31$ と、法 $31$ の原始根 $g=3$ を公開パラメータとするエルガマル暗号を考える。受信者は秘密鍵 $x=7$ を選び、公開鍵 $h\equiv g^x(\mathrm{mod}31)$（$0\le h\le 30$）を公開している。

送信者は平文 $m$（$1\le m\le 30$ の整数）を、整数 $k$ を選んで
$$c_1\equiv g^k,c_2\equiv m{h}^k(\mathrm{mod}31)$$
により暗号文 $(c_1,c_2)$ に変換して送る。受信者が受け取った暗号文が $(c_1,c_2)=(19,22)$ であるとき、平文 $m$ を求めよ。

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

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

ある送信者が、本来は毎回選び直すべき $k$ を使い回して、2 つの平文 $m_1,m_2$ を同じ $k$ で暗号化した。得られた暗号文は
$$m_1\text{の暗号文}:(51,11),m_2\text{の暗号文}:(51,7)$$
である。攻撃者は何らかの方法で $m_1=20$ であることを知った。秘密鍵 $x$ を求めずに、平文 $m_2$（$1\le m_2\le 88$ の整数）を求めよ。

素数 $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$）を求めよ。