第35問配点 ３点
RSA 暗号は、現在のインターネットにおいてよく用いられている暗号化方式である。この暗号は、桁数の大きい素数を掛け合わせた自然数の素因数分解が困難であることを安全性の根拠としている。
暗号化、復号化の手順は、以下のとおりである。
[準備１] 2つの素数 p, q をとり、m = pq とおく。
[準備２] p − 1 と q − 1 の最小公倍数を計算し、それを L とおく。
[準備３] [準備２]で定めた L と互いに素である自然数 k1（すなわち、L との最大公約数が１となるような自然数 k1）を用意する。ただし、k1 は１ではないものとする。[準備１]のm、及び今求めた k1 を公開鍵とする。
[準備４] [準備２]で定めた L、[準備３]で定めた k1 に対して、k1k2 を L で割った余りが１になる自然数 k2 を求める。この k2 を秘密鍵とする。
以上の準備の下で、受信者は、公開鍵（m 及び k1）を送信者に公開する。
送信者は、送信したい整数 n (0 ≦ n ＜ m) に対して nk₁ を m で割った余り c を計算し、これを受信者に送信する。
受信者は、受信データ c に対して、秘密鍵k2 を用いて ck₂ を m で割った余りを計算し、n の値を復元する。
一般に用いられている RSA 暗号は、公開鍵の桁数が極めて大きく、これを短時間で解読することは困難であるが、公開鍵の桁数が小さい場合には、秘密鍵を比較的容易に計算することができる。
公開鍵が m = 187、k1 = 23 であるとき、秘密鍵 k2 の値として適切なものを次の１から５までの中から選びなさい。（解答欄は、[№35]）
１. ３
２. ５
３. ７
４. １１
５. １３