暗号理論の問題

素数 $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=101$ と法 $101$ の原始根 $g$ を用いるエルガマル暗号を考える。受信者の秘密鍵を $a$、公開鍵を $h\equiv g^a(\mathrm{mod}p)$ とする。平文 $m$（$1\le m\le 100$ の整数）は、送信者が整数 $k$（$1\le k\le 99$）を選び
$$c_1\equiv g^k,c_2\equiv m{h}^k(\mathrm{mod}p)(0\le c_1,c_2\le 100)$$
として暗号文 $(c_1,c_2)$ に暗号化される。

送信者は、誤って同じ $k$ を使い回して 2 つの平文 $m_1,m_2$ を暗号化し、暗号文 $(14,19)$ と $(14,45)$ をこの順に送った。盗聴者は $1$ つ目の平文が $m_1=20$ であることを知っている。$2$ つ目の平文 $m_2$ を求めよ。

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

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

ある送信者が、2 つの平文 $m_1,m_2$ を暗号化する際に、誤って同じ乱数 $k$ を使ってしまい、暗号文はそれぞれ
$$(c_1,c_2)=(11,32),(c_1^{\prime },c_2^{\prime })=(11,38)$$
となった。攻撃者は、1 つ目の平文が $m_1=20$ であることを知っている。このとき、2 つ目の平文 $m_2$ を求めよ。

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

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

ある送信者が、2 つの平文 $m_1$, $m_2$ を暗号化する際に、誤って同じ乱数 $k$ を使ってしまった。その結果、暗号文はそれぞれ
$$(c_1,c_2)=(6,11),(c_1^{\prime },c_2^{\prime })=(6,42)$$
となった。攻撃者は何らかの方法で $m_1=25$ であることを知った。このとき、秘密鍵 $x$ や乱数 $k$ を求めずに得られる $m_2$（$1\le m_2\le 60$ の整数）を求めよ。