\(p=13, q=31\) のRSA暗号で、\(e\) のすべての候補についてそれに対応する \(d\) を求めよ。
ただし、導出過程も書くこと。
\(L=60=2^2\times3\times5\) なので 2～59から2, 3, 5の倍数を取り除くと 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53,
59 が残る。
|
|
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 |
48 |
49 |
| 50 |
51 |
52 |
53 |
54 |
55 |
56 |
57 |
58 |
59 |
このうちで \((de-1)/60\) が整数になるのは
\((7\times43-1)/60=5\)
\((11\times11-1)/60=2\)
\((13\times37-1)/60=8\)
\((17\times53-1)/60=15\)
\((19\times19-1)/60=6\)
\((23\times47-1)/60=18\)
\((29\times29-1)/60=14\)
\((31\times31-1)/60=16\)
\((41\times41-1)/60=28\)
\((49\times49-1)/60=40\)
\((59\times59-1)/60=58\)
なので、対応する組み合わせは以下のようになる。
| \(e\) |
7 |
11 |
13 |
17 |
19 |
23 |
29 |
31 |
37 |
41 |
43 |
47 |
49 |
53 |
59 |
| \(d\) |
43 |
11 |
37 |
53 |
19 |
47 |
29 |
31 |
13 |
41 |
7 |
23 |
49 |
17 |
59 |
候補が15個もあるのでペアを見つけるのが大変に見えるが、計算の順番を工夫すれば試行回数をかなり減らせる。
\(L=60\) の場合は、\(e, d\) の組み合わせには以下の性質がある。
- 下1桁が1か9なら自分自身とペア (\(e=d\)) になることが多い
- 下1桁が1か9でなければ自分自身とは絶対にペアにならない
下1桁が1の数は \(10n+1\), 下1桁が9の数は \(10n+9\) と表わせる (\(n\) は整数)。
これらを2乗すると \((10n+1)^2=100n^2+20n+1\), \((10n+9)^2=100n^2+180n+81\)
となり、いずれも第1項と第2項は10の倍数なので、これらの下1桁も1であることがわかる。
つまり、「下1桁が1か9の数を2乗して1を引いた数」は10で割り切れる。
これは60で割り切れることの十分条件ではない (例えば 21, 39 を2乗して1を引いても60で割り切れない) が、必要条件のひとつである。
逆に、下1桁が 0, 2, 3, 4, 5, 6, 7, 8 なら、2乗したものの下1桁は 0, 4, 9, 6, 5, 6, 9, 4 になり、1を引いたものは10で割り切れない。
当然60でも割り切れないので、これらが自分自身とペアになることはない。
これを踏まえて、まず \(e\) の候補のうち 11, 19, 29, 31, 41, 49, 59 が自分自身とペアになるかどうかを試すと、実際そうなることが確かめられる。
それらが確定すれば、残りの 7, 13, 17, 23, 37, 43, 47, 53 の8個だけについて考えればよい。
これらは自分自身とペアにならないので、計算回数は最大でも 15回で済む。
(最初のペアの探索に最大7回、候補が6個に減って次の探索に最大5回、候補が4個に減って次の探索に最大3回。残った2つは自動的にペアになる)