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

公開鍵暗号の仕組みをまとめることにした。
先日作成して公開したエンジニア向けのパズル８は公開鍵暗号の仕組みを使っている。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暗号の技術をそのままパズルにしたのがほとんどのエンジニアには解けるパズル８。もしご興味があれば、ぜひ挑戦してみてください。