ＲＳＡ暗号の仕組み

慶大環境情報学部2017年度入試「情報」より

　次の文章は、ある暗号方式の原理に関して説明したものである。空欄に入るもっとも適した数字をマークしなさい。

　整数から別の整数へ変換する暗号方式を考える。ここで説明する暗号方式では、次のようにして、元の整数 a から、暗号化された整数 b を計算する。ただし、x (mod y) は x を y で割った余りを表し、z ≡ x (mod y) は x を y で割った余りと z を y で割った余りが等しいことを表している。

(1)　２つの素数 p , q を選ぶ。
(2)　２つの素数の積、n＝pq を求める。
(3)　(p－1) と (q－1) の最小公倍数 L を求める。
(4)　L と互いに素な、e（3 ≦ e ≦ L－1）を選ぶ。
(5)　ed ≡ 1 (mod L) となる d を求める。
(6)　a^e (mod n) を求めて b とする。

b から a を得るには次のようにする。

(1)　b^d (mod n) を求める。

したがって、暗号化するには、n , e の組がわかっていればよく、復元するには、n , d の組がわかっていればよい。
　実際には非常に大きな素数を用いるが、ここでは小さな値、p＝13 および q＝17 を用いて具体例を示す。まず n＝221 が得られ、L＝48 が得られる。e＝5 とすると、積 ed を L で割ったときの余りが 1 になる d は（ア）である。e＝11 の場合は、d＝（イ）となる。ここでは、e＝5 を用いて暗号化する。a＝（ウ）とすると、a の e 乗（つまり5乗）を n で割った余りが b であり、b＝15 が得られる。復元するには、b の d 乗を n で割った余りを求めればよく、計算すると、（ウ）が得られて、a の値になることがわかる。
　a^e (mod n) の計算は桁数が多くなり計算量が多くなるようにみえる。しかしながら、指数部を2進数で表現し、下位ビットに相当する部分の余りから順番に計算していく高速に計算できるアルゴリズムが知られており、a^e をそのまま計算する必要はない。

---

《答え》
順に、　29　35　019