RSA暗号（例題）

このページは再読み込みをしても新たな問題を生成しない。

Aを送信者、Bを受信者とするときのRSA暗号方式を以下に示す。

Step 1. Bは自身の公開鍵と秘密鍵を作る。 Step 2. Bは公開鍵($n$と$e$)をAに送る。
Step 3. Aは受け取った公開鍵を使って文章（平文）を暗号化。 Step 4. Aは暗号文$y$をBに送る。
Step 5. Bは自身の秘密鍵を使って復号化、ものの文章（平文）を得る。 以下の問に答えよ。

[1] あなたは送信者である。 平文$x=12$を受信者から受け取った公開鍵を使って暗号化したい。 いま、受信者から公開鍵として$n=15, e=3$を受け取った。 暗号文$y$を作れ。　
送信者が暗号文を作るのは Step 3 である。
Step 3 では$x^e$を$n$で割った余りを計算することで暗号文$y$を生成している。
したがって、合同式の法を$15$として \[ x^e = 12^3 \equiv (-3)^3 = -27 \equiv 3. \] よって暗号文は$y=3$。
（$x^e$の計算は底をできるだけ小さくするのがコツである。）

[2]あなたは受信者である。 あなたはふたつの素数として$p=3, q=5$を選び$(p-1)(q-1)=8$と互いに素な数として$e=3$を選んだ。次の問に答えよ。　
  1. あなたの秘密鍵$d$を求めよ。ただし$d$は秘密鍵として使える数のうち最小の自然数とする。
  2. 送信者から暗号文$y=3$が送られてきた。 送信者の暗号文$y$を復号し、送信者の平文$x$を求めよ。
(1) 受信者が$p,q,e$から秘密鍵$d$を作るのは Step 1 である。
$d$は「$ed \equiv 1 \pmod{(p-1)(q-1)}$」を満たすように取るので合同方程式$3d \equiv 1 \pmod{8}$を解けばよい。
これを満たす最小の自然数$d$は$d = 3$である。
(2) 受信者が暗号文を復号化するのは Step 5 である。
暗号文の復号は「$y^d$を$n$でわった余りを求める」ことで実現される。
$3^3 = 27$を$n = 15$でわった余りは$12$であるから、送信者の平文は$x = 12$である。

[3] あなたは盗聴者である。 あなたは受信者が送った公開鍵$n = 8633, e = 5$と送信者が送った暗号文$y = 6442$を盗んだ。 さらに受信者のPCをハッキングし秘密鍵$d = 5069$を手に入れることに成功した。 次を満たす整数$a,b,c$を答えよ。
　　　 「送信者が送った平文$x$は$a^b$を$c$で割った余りである。」　　
暗号文$y$と公開鍵$n$のほかに、受信者の秘密鍵$d$を持っているので Step 5 によって復号化できる。
送信者が送った平文$x$は$6442^{5069}$を$8633$で割った余りである。
つまり、$(a,b,c) = (6442, 5069, 8633)$である。

[4] あなたは盗聴者である。 あなたは受信者が送る公開鍵$n = 35, e = 5$と送信者が送った暗号文$y = 4$を盗んだ。 あなたは公開鍵に使われている整数$n$が十分小さい数であることに気付き、$35$は$5 \times 7$と素因数分解できることに気付いた。 次の問に答えよ。　
  1. 受信者の秘密鍵$d$を求めよ。ただし$d$は秘密鍵として使える数のうち最小の自然数とする。
  2. 送信者の暗号文$y$を復号し、送信者の平文$x$を求めよ。
素因数分解に成功し素数$p,q$が得られ、かつ盗聴した情報から$e$が得られているので盗聴者であるあなたは受信者と同じ情報を持っている（問題[2]と同じ状況である）。
(1) $35 = 5 \times 7$と素因数分解できるので$p = 5, q = 7$である。
そこで$ed \equiv 1 \pmod{(p-1)(q-1)}$、つまり$5d \equiv 1 \pmod{24}$となる$d$を求める。
これを満たす最小の自然数$d$は$d = 5$。
(2) $4^5$を$n = 35$でわった余りは$9$である。
よって送信者の平文は$x = 9$である。
（余りの計算は$4^5$が$1024$であることを計算してから$n=35$で割っても良いし、
$4^5 = 4^3 \cdot 4^2 = 64 \cdot 16 \equiv (-6) \cdot 16 = -96 \equiv 9$ のように計算してもよい。）