Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
150
Help us understand the problem. What is going on with this article?
@jabba

公開鍵暗号とRSA暗号の仕組み

More than 3 years have passed since last update.

公開鍵暗号の仕組みをまとめることにした。
先日作成して公開したエンジニア向けのパズル8は公開鍵暗号の仕組みを使っている。RSA暗号のコード書いてデバッグして、暗号の仕組みをかなり理解したので、せっかくだからまとめた。

公開鍵暗号

金庫の中にに大事なモノを保管する時、まずは金庫を閉めて鍵をかける。すると鍵を持っている人にしか開けられなくなる。これが通常の鍵の仕組み。
ただネットを介した通信での暗号方式では少し事情が異なる。
まず送信者が金庫を閉めて鍵を使って鍵をかける。そしてそれを受信者に届ける際には金庫と鍵を送ってもらう必要がある。しかし金庫と鍵を同時に送るのは危険。途中でその鍵が見られたりコピーされたりしたら、金庫に入れる(暗号化すること)意味が無くなってしまうからだ。大事なモノに鍵をかけて送るのに、その鍵を送る方法が無防備だとまったく無意味になってしまう。

そこで数学者の叡智により編み出されたのが公開鍵暗号方式。それは金庫を閉めるための鍵と金庫を開けるための鍵があり、それらをペアで使う方式。ここで言う金庫を閉めるための鍵を「公開鍵」、金庫を開けるための鍵を「秘密鍵」という。

公開鍵と秘密鍵

公開鍵

平文(誰にでも読める文章データ)に暗号をかけるための鍵
"I love you"という平文があって、それを公開鍵を使って暗号をかけると"43048, 20523, 600.."というような数字の羅列になる。
ただし公開鍵があっても、暗号を元の平文に戻すことはできないので誰に見られても問題無い。

秘密鍵

暗号文を元の平文に戻すための鍵
先ほどの例で言うと"43048, 20523, 600.."を"I love you"に戻すための鍵。他人の手に渡ると危険なので、大切に保管する必要がある。ただし暗号の受信者は秘密鍵を自分で持っておくだけでよい。受信者は送信者へ秘密鍵を渡す必要はない。

RubyでRSA暗号

ここからはコードを使って実際にRSA暗号をかけて、それを復号してみる。

文字は数字に変換

まず暗号では基本的に全ての文字が数字に置き換えられる。
"Jabba the Hutt"と書かれた文字列の数字変換はRubyであれば.each_codepointを使えばできる。

$ irb
irbを起動

irb> text = "Jabba the Hutt"
=> "Jabba the Hutt"
irb> text_array= text.each_codepoint.to_a
=> [74, 97, 98, 98, 97, 32, 116, 104, 101, 32, 72, 117, 116, 116]

この74,97...となっている配列の数字は暗号化したのではなく、単に文字を数字(コードポイント)に置き換えただけ。コードポイントとは、1文字を表す整数のコード。
これは簡単に元の文字列に戻せる。

irb> 74.chr
=> "J"
irb> text_array.map{|i| i.chr}.join("")
=> "Jabba the Hutt"

暗号化をするにはこの数字の羅列を鍵を持っている人にしか分からない方法で変換すること。
そのためにはRSA暗号では乗数の表を使う。

乗数の表

横軸がかける数
縦軸が乗数
2の列を上から見ていけば一番分かりやすい。2,4,8,16,32,64とお馴染みの数字が縦に並んでいる。

1 2 3 4
1 1 2 3 4
2 1 4 9 16
3 1 8 27 64
4 1 16 81 256
5 1 32 243 1024
6 1 64 729 4096
7 1 128 2187 16384
8 1 256 6561 65536
9 1 512 19683 262144
10 1 1024 59049 1048576

10までしか載せていないのは、たくさん載せるとあまりに数が大きくなり過ぎてややこしいだけだから。

RSA暗号ではとても大きい2つの素数をかけた数字を元にその数で割ったあまりだけを表に入れる。
ここでは例をカンタンにするためにそのとても大きな2つの素数をp= 7、q= 19とする。実際はコンピューターがカンタンに計算できないぐらいにデカい。
pとqを掛けた数字はpq = 7✕19 = 133となる。

先ほどの乗数表を133で割ったその余りを記載する。コードで言うなら%もしくはmodにあたる。つまりこれで表の中のどんなに大きな数字も全て0から132のどれかの数字になる。
するとちょっと不思議なことがあるのが分かる。

1 2 3 4 5 6 7 8 9 10 11 12 13 14
(1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14
2 1 4 9 16 25 36 49 64 81 100 121 11 36 63
3 1 8 27 64 125 83 77 113 64 69 1 132 69 84
4 1 16 81 123 93 99 7 106 44 25 11 121 99 112
5 1 32 110 93 66 62 49 50 130 117 121 122 90 105
6 1 64 64 106 64 106 77 1 106 106 1 1 106 7
7 1 128 59 25 54 104 7 8 23 129 11 12 48 98
8 1 123 44 100 4 92 49 64 74 93 121 11 92 42
9 1 113 132 1 20 20 77 113 1 132 1 132 132 56
10 1 93 130 4 100 120 7 106 9 123 11 121 120 119
11 1 53 124 16 101 55 49 50 81 33 121 122 97 70
12 1 106 106 64 106 64 77 1 64 64 1 1 64 49
13 1 79 52 123 131 118 7 8 44 108 11 12 34 21
14 1 25 23 93 123 43 49 64 130 16 121 11 43 28
15 1 50 69 106 83 125 77 113 106 27 1 132 27 126
16 1 100 74 25 16 85 7 106 23 4 11 121 85 35
17 1 67 89 100 80 111 49 50 74 40 121 122 41 91
18 1 1 1 1 1 1 77 1 1 1 1 1 1 77
(19) 1 2 3 4 5 6 7 8 9 10 11 12 13 14
20 1 4 9 16 25 36 49 64 81 100 121 11 36 63
21 1 8 27 64 125 83 77 113 64 69 1 132 69 84
22 1 16 81 123 93 99 7 106 44 25 11 121 99 112
23 1 32 110 93 66 62 49 50 130 117 121 122 90 105
24 1 64 64 106 64 106 77 1 106 106 1 1 106 7
25 1 128 59 25 54 104 7 8 23 129 11 12 48 98
26 1 123 44 100 4 92 49 64 74 93 121 11 92 42
27 1 113 132 1 20 20 77 113 1 132 1 132 132 56
28 1 93 130 4 100 120 7 106 9 123 11 121 120 119
29 1 53 124 16 101 55 49 50 81 33 121 122 97 70
30 1 106 106 64 106 64 77 1 64 64 1 1 64 49
31 1 79 52 123 131 118 7 8 44 108 11 12 34 21
32 1 25 23 93 123 43 49 64 130 16 121 11 43 28
33 1 50 69 106 83 125 77 113 106 27 1 132 27 126
34 1 100 74 25 16 85 7 106 23 4 11 121 85 35
35 1 67 89 100 80 111 49 50 74 40 121 122 41 91
36 1 1 1 1 1 1 77 1 1 1 1 1 1 77
(37) 1 2 3 4 5 6 7 8 9 10 11 12 13 14
38 1 4 9 16 25 36 49 64 81 100 121 11 36 63

全ての数字は予想不可能な変化を繰り返しているが、
1行目と同じ内容が繰り返えされている箇所がカッコを付けた19行目と37行目にある。

つまりこの表の中においてはどんな数でも19乗や37乗して133のmodをとれば元の数に戻るのだ。

元に戻る乗数

この19,37行目の数字の出し方はp-1とq-1の最小公倍数の倍数に1を足した数になる。
p-1とq-1の最小公倍数とはつまり18。
ここでは18の倍数に1を足した数。19, 37, 55....行目の数は1行目と同じ数字になるという法則がある。
この性質を暗号に使ったのがRSA暗号。
ある文字(数字)を何乗かして、予想のつかない数字にしてしまう。この乗数が公開鍵になる。
でまたその数字をきっちり19,37,55,のように元に戻るようにまた何乗かして元に戻す。この乗数が秘密鍵になる。

表で言えばまず1行目から10行目まで行って、訳の分からない数字にして暗号化する。その後19行目まで行って元に戻すイメージ。

公開鍵の作成

まず(p-1)と(q-1)の最小公倍数を出す。ここではLとする。

irb> p = 7
=> 7
irb> q = 19
=> 19
irb> L = (p-1).lcm(q-1)
=> 18

Lが18と出た。別にコード書かなくても6と18の最小公倍数は18で当たり前なんだけど。

公開鍵の条件は1より大きくL(=18)よりも小さい。
しかも公開鍵とLとの最大公約数は1であること、つまり互いに素であることが条件。
コードにすると以下のようになる。
ここでは公開鍵をpublicとする

irb> public = [*(2..18)].each {|i| break i if (i.gcd(18)==1) }
=> 5

公開鍵は「133で割ったの余りの表を使って5乗すること」になる。

秘密鍵の作成

秘密鍵の条件は
秘密鍵✕公開鍵=L✕n+1となる数。
ここでは秘密鍵をprivateとする。

irb> private = [*(2..18)].each { |i| break i if ((public * i) % 18 == 1) }
=> 11

秘密鍵は「133で割ったの余りの表を使って11乗すること」になる。

表を見ても分かるように、平文の数字を公開鍵で5乗するとよく分からない数字になって暗号化できる。
元に戻すにはその数字を11乗してしまえば5✕11=55で55乗、ということは18の倍数+1の55行目と同じく元の平文に戻る。

暗号化と復号化

まずは冒頭のJaba the Huttを公開鍵(public=5)で暗号化する。

irb> encrypted_array = text_array.map { |i| i ** 5 % 133 }
=> [44, 13, 91, 91, 13, 128, 51, 111, 5, 128, 116, 129, 51, 51]

やってることは元の数字を5回かけて133の余りを出しただけ。それだけでもう暗号化されて、元の数字とはまったく異なる数になる。

で、これを秘密鍵の11と133を使って復号する。

irb> decoded_array = encrypted_array.map { |i| i ** 11 % 133 }
=> [74, 97, 98, 98, 97, 32, 116, 104, 101, 32, 72, 117, 116, 116]
irb> decoded_array.map { |i| i.chr }.join
=> "Jabba the Hutt"

やってることは暗号の数字を11回かけて133の余りを出すだけ。それだけで、元どおり。

この例では小さな数の素数を使っているので解読できなくもない。これを100桁以上ある大きな素数を使えばもうコンピュータでもなかなか解読しにくくなる。この辺りのコンピュータでも解読しにくい理由については気が向いたら「公開鍵暗号とRSA暗号の仕組み - その2」でも書くつもり。
 
 
RSA暗号は気付いていてもいなくても誰もが毎日なにかの形で使っている。めちゃくちゃに頭のいい数学者達の叡智の結晶が、こんなにシンプルな形にまとめられていることに感心せずにはいられない。本当にすごい技術というのは究極的にはシンプルなのだな、と。

このRSA暗号の技術をそのままパズルにしたのがほとんどのエンジニアには解けるパズル8。もしご興味があれば、ぜひ挑戦してみてください。

150
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
jabba
ベルリンのスタートアップで働くソフトウェアエンジニア(イボ痔持ち)
admin-guild
「Webサービスの運営に必要なあらゆる知見」を共有できる場として作られた、運営者のためのコミュニティです。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
150
Help us understand the problem. What is going on with this article?