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$ である。
[ 例題 ]
あなたは送信者である。平文 $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$ の計算は底をこまめに小さくしていくのがコツである。）
[問題]
あなたは送信者である。
平文 $x=$ を受信者から受け取った公開鍵を使って暗号化したい。
いま、受信者から公開鍵として $n=$ , $e=$ を受け取った。
このとき、受信者に送る暗号文 $y$ は である。