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

課題1

\(p=19, q=13\) のRSA暗号で、\(e\) のすべての候補についてそれに対応する \(d\) を求めよ。 ただし、導出過程も書くこと。

\((5\times29-1)/36=4\)
\((7\times31-1)/36=6\)
\((11\times23-1)/36=7\)
\((13\times25-1)/36=9\)
\((17\times17-1)/36=8\)
\((19\times19-1)/36=10\)
\((35\times35-1)/36=34\)
なので、対応する組み合わせは以下のようになる。
\(e\) 5 7 11 13 17 19 23 25 29 31 35
\(d\) 29 31 23 25 17 19 11 13 5 7 35

課題2

\(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つは自動的にペアになる)
inserted by FC2 system