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

公開鍵暗号の仕組みをまとめることにした。
先日作成して公開した[エンジニア向けのパズル８](http://tango-ruby.hatenablog.com/entry/2016/03/11/130040)は公開鍵暗号の仕組みを使っている。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暗号ではとても大きい２つの素数をかけた数字を元にその数で割ったあまりだけを表に入れる。
ここでは例をカンタンにするためにそのとても大きな２つの素数を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の最小公倍数の倍数に１を足した数になる。
p-1とq-1の最小公倍数とはつまり１８。
ここでは１８の倍数に１を足した数。19, 37, 55....行目の数は１行目と同じ数字になるという法則がある。
この性質を暗号に使ったのがRSA暗号。
ある文字（数字）を何乗かして、予想のつかない数字にしてしまう。この乗数が公開鍵になる。
でまたその数字をきっちり19,37,55,のように元に戻るようにまた何乗かして元に戻す。この乗数が秘密鍵になる。

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


## 公開鍵の作成

まず(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との最大公約数は１であること、つまり互いに素であることが条件。
コードにすると以下のようになる。
ここでは公開鍵をpublicとする

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

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

## 秘密鍵の作成

秘密鍵の条件は
秘密鍵✕公開鍵＝L✕ｎ＋１となる数。
ここでは秘密鍵を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]
```
やってることは元の数字を５回かけて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"
```

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

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

このRSA暗号の技術をそのままパズルにしたのが[ほとんどのエンジニアには解けるパズル８](http://tango-ruby.hatenablog.com/entry/2016/03/11/130040)。もしご興味があれば、ぜひ挑戦してみてください。

http://tango-ruby.hatenablog.com/entry/2016/03/11/130040