RSA(公開鍵方式)の暗号化と復号化
RSAでの暗号化/復号化には2つの素数を使用します。
実際に使用される2つの素数は、巨大な数値を使います。
説明を簡単にするため、使用する素数は5と11にします。
選んだ2つの素数を書けた値を法とする世界を考えます。
ここでの説明では、55(5*11)を法とする世界になります。
55を法とする世界とはどのような世界なのでしょうか?
それは、55以上の数値がない世界です。
55より大きな数値は、55で割った余りの数値を使います。
実世界の数値 |
55を法としたときの数値 |
理由 |
3 |
3 |
3 ÷ 55=0 余り 3 |
70 |
15 |
70 ÷ 55=1 余り 15 |
140 |
30 |
140 ÷ 55=2 余り 30 |
この55を法とする世界で、べき乗の表を作成します。
|
べき乗 |
1 |
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 |
元
の
値
・
平
文 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
2 |
4 |
8 |
16 |
32 |
9 |
18 |
36 |
17 |
34 |
13 |
26 |
52 |
49 |
43 |
31 |
7 |
14 |
28 |
1 |
2 |
4 |
8 |
16 |
32 |
9 |
3 |
3 |
9 |
27 |
26 |
23 |
14 |
42 |
16 |
48 |
34 |
47 |
31 |
38 |
4 |
12 |
36 |
53 |
49 |
37 |
1 |
3 |
9 |
27 |
26 |
23 |
14 |
4 |
4 |
16 |
9 |
36 |
34 |
26 |
49 |
31 |
14 |
1 |
4 |
16 |
9 |
36 |
34 |
26 |
49 |
31 |
14 |
1 |
4 |
16 |
9 |
36 |
34 |
26 |
5 |
5 |
25 |
15 |
20 |
45 |
5 |
25 |
15 |
20 |
45 |
5 |
25 |
15 |
20 |
45 |
5 |
25 |
15 |
20 |
45 |
5 |
25 |
15 |
20 |
45 |
5 |
6 |
6 |
36 |
51 |
31 |
21 |
16 |
41 |
26 |
46 |
1 |
6 |
36 |
51 |
31 |
21 |
16 |
41 |
26 |
46 |
1 |
6 |
36 |
51 |
31 |
21 |
16 |
7 |
7 |
49 |
13 |
36 |
32 |
4 |
28 |
31 |
52 |
34 |
18 |
16 |
2 |
14 |
43 |
26 |
17 |
9 |
8 |
1 |
7 |
49 |
13 |
36 |
32 |
4 |
8 |
8 |
9 |
17 |
26 |
43 |
14 |
2 |
16 |
18 |
34 |
52 |
31 |
28 |
4 |
32 |
36 |
13 |
49 |
7 |
1 |
8 |
9 |
17 |
26 |
43 |
14 |
9 |
9 |
26 |
14 |
16 |
34 |
31 |
4 |
36 |
49 |
1 |
9 |
26 |
14 |
16 |
34 |
31 |
4 |
36 |
49 |
1 |
9 |
26 |
14 |
16 |
34 |
31 |
10 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
10 |
45 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
11 |
12 |
12 |
34 |
23 |
1 |
12 |
34 |
23 |
1 |
12 |
34 |
23 |
1 |
12 |
34 |
23 |
1 |
12 |
34 |
23 |
1 |
12 |
34 |
23 |
1 |
12 |
34 |
13 |
13 |
4 |
52 |
16 |
43 |
9 |
7 |
36 |
28 |
34 |
2 |
26 |
8 |
49 |
32 |
31 |
18 |
14 |
17 |
1 |
13 |
4 |
52 |
16 |
43 |
9 |
14 |
14 |
31 |
49 |
26 |
34 |
36 |
9 |
16 |
4 |
1 |
14 |
31 |
49 |
26 |
34 |
36 |
9 |
16 |
4 |
1 |
14 |
31 |
49 |
26 |
34 |
36 |
15 |
15 |
5 |
20 |
25 |
45 |
15 |
5 |
20 |
25 |
45 |
15 |
5 |
20 |
25 |
45 |
15 |
5 |
20 |
25 |
45 |
15 |
5 |
20 |
25 |
45 |
15 |
16 |
16 |
36 |
26 |
31 |
1 |
16 |
36 |
26 |
31 |
1 |
16 |
36 |
26 |
31 |
1 |
16 |
36 |
26 |
31 |
1 |
16 |
36 |
26 |
31 |
1 |
16 |
17 |
17 |
14 |
18 |
31 |
32 |
49 |
8 |
26 |
2 |
34 |
28 |
36 |
7 |
9 |
43 |
16 |
52 |
4 |
13 |
1 |
17 |
14 |
18 |
31 |
32 |
49 |
18 |
18 |
49 |
2 |
36 |
43 |
4 |
17 |
31 |
8 |
34 |
7 |
16 |
13 |
14 |
32 |
26 |
28 |
9 |
52 |
1 |
18 |
49 |
2 |
36 |
43 |
4 |
19 |
19 |
31 |
39 |
26 |
54 |
36 |
24 |
16 |
29 |
1 |
19 |
31 |
39 |
26 |
54 |
36 |
24 |
16 |
29 |
1 |
19 |
31 |
39 |
26 |
54 |
36 |
20 |
20 |
15 |
25 |
5 |
45 |
20 |
15 |
25 |
5 |
45 |
20 |
15 |
25 |
5 |
45 |
20 |
15 |
25 |
5 |
45 |
20 |
15 |
25 |
5 |
45 |
20 |
21 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
21 |
1 |
22 |
22 |
44 |
33 |
11 |
22 |
44 |
33 |
11 |
22 |
44 |
33 |
11 |
22 |
44 |
33 |
11 |
22 |
44 |
33 |
11 |
22 |
44 |
33 |
11 |
22 |
44 |
23 |
23 |
34 |
12 |
1 |
23 |
34 |
12 |
1 |
23 |
34 |
12 |
1 |
23 |
34 |
12 |
1 |
23 |
34 |
12 |
1 |
23 |
34 |
12 |
1 |
23 |
34 |
24 |
24 |
26 |
19 |
16 |
54 |
31 |
29 |
36 |
39 |
1 |
24 |
26 |
19 |
16 |
54 |
31 |
29 |
36 |
39 |
1 |
24 |
26 |
19 |
16 |
54 |
31 |
25 |
25 |
20 |
5 |
15 |
45 |
25 |
20 |
5 |
15 |
45 |
25 |
20 |
5 |
15 |
45 |
25 |
20 |
5 |
15 |
45 |
25 |
20 |
5 |
15 |
45 |
25 |
26 |
26 |
16 |
31 |
36 |
1 |
26 |
16 |
31 |
36 |
1 |
26 |
16 |
31 |
36 |
1 |
26 |
16 |
31 |
36 |
1 |
26 |
16 |
31 |
36 |
1 |
26 |
21乗すると元の値が現れているのが分かるでしょう。
これを利用して暗号化と複合化を行います
公開鍵を7と55(法)とした場合を考えます
<暗号化>
公開鍵を受け取った人は、平文に対して、55を法とした7乗の結果を計算します
例えば2を暗号化した場合は18になります。
暗号値=18
<復号化>
復号化する人は公開鍵発行者です。
したがって、平文を21乗すれば元の値に戻ることを知っています。
暗号化された値は7乗されているので、その値を3乗すれば21乗になります。
18(暗号値)を3乗して複合化します。
18の3乗→2
元の値になっています
この場合、素数の値が 5 と 11 でした。
この2つの素数の値が分かると解読できます。
本当にこの方法での暗号化は安全なのでしょうか?
素因数分解
素数をそれぞれ pとq にした場合の公開鍵は p*q になります。
p*q の結果から pとq が分かってしまうと、暗号は解読されてしまいます。
これは、素因数分解の問題です。
例で挙げた、55 を素因数分解すると 5と11 であることは簡単に分かります。
しかし、なぜ 5と11 であることが分かったのでしょうか?
これは、人間の経験と勘によるところが大きいのです。
例えば、1159 を素因数分解できるでしょうか?
答えは 19と61 ですが、筆者は暗算で解くことはできません。
電卓を使っても、方法としては
3で割れ切れるか?
5で割れ切れるか?
7で割れ切れるか?
・・・と、素数で割り切れるかしらみつぶしに計算していくしかありません。
実は現在でも、効率の良い素因数分解の方法は見つかっていないのです。
素因数分解の桁数が上がれば、いくら高性能のコンピュータを使っても、困難なのです。
ちなみに、174桁の素因数分解を解くのに100
台の業務用コンピュータで協調計算させて 3
ヶ月かかっています(2003年末現在)
|