RSA 暗号の基本原理 (paizaランク B 相当)

ここまで学んできた mod や累乗の知識を利用して、今現在も活躍している暗号である RSA 暗号の基本的な原理を確かめてみましょう。
RSA 暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つです。
次の問題で RSA 暗号を解読するために、その暗号化・解読方法をこの問題で検証してみましょう。

＜準備＞
適当な素数 p , q を用意し、 n = pq , n' = (p-1)(q-1) とおく。
e は gcd(e , n') = 1 を満たす適当な整数とし、あらかじめ de ≡ 1 (mod n') を満たす自然数 d を用意する。

＜手順＞
1. 受信者は n と e を公開しておく。
2. 送信者は、数値 M を送信したい時は、代わりに数値 E = M^e mod n を送信する。
3. E を受け取った受信者が、自分だけが知っている自然数 d を用いて E^d mod n を求めると、元の数値 M が得られる。

整数 p,q,e,M が与えられるので、d = e^{-1} (mod n') を求めたのち、E = M^e mod n とすると E^d mod n は M になることを確かめてみましょう。