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年末現在)