RSA暗号（盗聴者）
試験のときはこの枠内の情報は与えられる。
Aを送信者、Bを受信者とするときのRSA暗号方式を以下に示す。
Step 1. Bは自身の公開鍵と秘密鍵を作る。
- 素数 $p,q$ を用意し、$n=pq$ とする。
- 自然数 $e$ を $(p-1)(q-1)$ と互いに素な数とする。
- 自然数 $d$ を $ed \equiv 1 \pmod{(p-1)(q-1)}$ を満たすようにとる。
Step 2. Bは公開鍵（$n$ と $e$）をAに送る。
Step 3. Aは受け取った公開鍵を使って文章（平文）を暗号化。
- 送りたいメッセージを $x$ とする（ただし $x$ は $n$ 未満の自然数とする）。
- $x^e$ を $n$ で割った余りを $y$ とする、つまり $y \equiv x^e \pmod{n}$ とする。
Step 4. Aは暗号文 $y$ をBに送る。
Step 5. Bは自身の秘密鍵を使って復号化、ものの文章（平文）を得る。
- $y^d$ を $n$ で割った余りを求める。これが平文 $x$ である。
[ 例題 ]
あなたは盗聴者である。
あなたは受信者が送る公開鍵 $n = 35, e = 5$ と送信者が送った暗号文 $y = 4$ を盗んだ。
あなたは公開鍵に使われている整数 $n$ が十分小さい数であることに気付き、$35$ は $5 \times 7$ と素因数分解できることに気付いた。
次の問に答えよ。
- 受信者の秘密鍵 $d$ を求めよ。ただし $d$ は秘密鍵として使える数のうち最小の自然数とする。
- 送信者の暗号文 $y$ を復号し、送信者の平文 $x$ を求めよ。
[ 解法 ]
素因数分解に成功し素数 $p,q$ が得られ、かつ盗聴した情報から $e$ が得られているので盗聴者であるあなたは受信者と同じ情報を持っている。以下の解法は「RSA暗号（受信者）」と本質的に同じである。
- $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$ である。
- $4^5$ を $n = 35$ でわった余りは $9$ である。
よって送信者の平文は $x = 9$ である。
[問題]
あなたは盗聴者である。
あなたは受信者が送信者に送った公開鍵 $n=$ , $e=$
と送信者が受信者に送った暗号文 $y=$ を盗んだ。
このとき、受信者の秘密鍵 $d$ は である。
ただし $d$ は秘密鍵として使える数のうち最小の自然数とする。
また、送信者の平文 $x$ は である。