第14回 公開鍵暗号 課題解答例

課題1

\(p=17\), \(q=13\) のRSA暗号で、\(e\) のすべての候補についてそれに対応する \(d\) を求めよ。 導出過程も書き、表1のような形にまとめること。


解答

与えられた \(p\), \(q\) より、
\(n=17\times13=221\)
\(L=lcm(17-1, 13-1)\) \(=lcm(16, 12)\) \(=lcm(2^4, 2^2\times3)\) \(=2^4\times3^1\) \(=48\) となる。
2~47 から \(L\) の素因数 2, 3 の倍数を取り除くと 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47 が残る。
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
このうちで \((de-1)/48\) が整数になるのは以下の組み合わせ (参考 : Excelによる導出) なので、
\((5\times29-1)/48=3\)
\((7\times7-1)/48=1\)
\((11\times35-1)/48=8\)
\((13\times37-1)/48=10\)
\((17\times17-1)/48=6\)
\((19\times43-1)/48=17\)
\((23\times23-1)/48=11\)
\((25\times25-1)/48=13\)
\((31\times31-1)/48=20\)
\((41\times41-1)/48=35\)
\((47\times47-1)/48=46\)

よって、対応する組み合わせは以下のようになる。
\(e\) 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47
\(d\) 29 7 35 37 17 43 23 25 5 31 11 13 41 19 47

課題2

以下のようなものを表示する Processing のプログラムを完成させよ。
(解答は7, 8行目のコメント文に対応するコード)
13を1乗して247で割った余り:13
13を2乗して247で割った余り:169
13を3乗して247で割った余り:221
13を4乗して247で割った余り:156
13を5乗して247で割った余り:52
13を6乗して247で割った余り:182
13を7乗して247で割った余り:143
13を8乗して247で割った余り:130
13を9乗して247で割った余り:208
13を10乗して247で割った余り:234
13を11乗して247で割った余り:78
13を12乗して247で割った余り:26
13を13乗して247で割った余り:91
13を14乗して247で割った余り:195
13を15乗して247で割った余り:65
13を16乗して247で割った余り:104
13を17乗して247で割った余り:117
13を18乗して247で割った余り:39
13を19乗して247で割った余り:13
13を20乗して247で割った余り:169
13を21乗して247で割った余り:221
13を22乗して247で割った余り:156
13を23乗して247で割った余り:52

解答

結果表示と「surplusに元の数をかけてnで割った余り」を surplus に入れるという処理をコードにすると以下のようになる。
int n = 247; // n
int d = 23; // d
int num = 13; // 元の数
int surplus = num; // 余り

for (int i=0; i<d; i++) {
  println(num + "を" + (i+1) + "乗して" + n + "で割った余り:" + surplus);
  surplus = surplus * num % n;
}