$p=13,\,\,q=7$とする.$n=pq=13\times7=91$に対し,$\gcd(e,(p-1)(q-1))=\gcd(e,72)=1$を満たすように$e=29$とおく.この時,公開鍵$(n,e)=(91,29)$をもつRSA暗号に対して,次の問いに答えよ.


&&&
(1)$ed \equiv1 (\mathrm{mod}72)$となる秘密鍵$d \gt0$を求めよ。
(2)平文$x=2$を暗号化して得られる暗号文$y( \equiv x^e(\mathrm{mod}91))$を求めよ。
(3)平文$x(0 \lt x \lt 91)$の暗号文が$x^e \equiv30(\mathrm{mod}91)$の時、平文$x(\mathrm{mod}91)$を求めよ。

&&&


解答：
(1) 与えられたeから、
　$29d \equiv 1(\mathrm{mod}72)$
　を解けばよい。ここで、$d=5$を代入すると、
　$29\times5 \equiv 1(\mathrm{mod}72)$$ \Longleftrightarrow 144\equiv 1(\mathrm{mod}72)$
　となるので、求める答えは、
**$d=5$**

(2 暗号文$y \equiv 2^{29}(\mathrm{mod}91)$を求める。
$2y \equiv 2^{30}(\mathrm{mod}91) \Longleftrightarrow 2y \equiv (1024)^3(\mathrm{mod}91)$
 $(1024)^3 \equiv (23)^3 \equiv 12167 \equiv64(\mathrm{mod}91)$
これより、**$y \equiv 32(\mathrm{mod}91)$**

(3 $x^{29} \equiv 30(\mathrm{mod}91)$において
$x=1$のとき合同$1$
  $x=2$のとき合同$32$
  $x=3$のとき合同$61$
これより、$30=91-61$であるから
**$x \equiv -3 \equiv 88 (\mathrm{mod}91)$**


　



