ジャバ・ザ・ハットリ
Published on

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

Authors
  • avatar
    ジャバ・ザ・ハットリ

公開鍵暗号の仕組みをまとめることにした。
先日作成して公開したエンジニア向けのパズル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 とお馴染みの数字が縦に並んでいる。

1234
11234
214916
3182764
411681256
51322431024
61647294096
71128218716384
81256656165536
9151219683262144
1011024590491048576

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

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

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

1234567891011121314
(1)1234567891011121314
2149162536496481100121113663
31827641258377113646911326984
4116811239399710644251112199112
5132110936662495013011712112290105
61646410664106771106106111067
71128592554104782312911124898
811234410049249647493121119242
9111313212020771131132113213256
1019313041001207106912311121120119
111531241610155495081331211229770
12110610664106647716464116449
1317952123131118784410811123421
14125239312343496413016121114328
1515069106831257711310627113227126
161100742516857106234111218535
171678910080111495074401211224191
181111117711111177
(19)1234567891011121314
20149162536496481100121113663
211827641258377113646911326984
22116811239399710644251112199112
23132110936662495013011712112290105
241646410664106771106106111067
251128592554104782312911124898
2611234410049249647493121119242
27111313212020771131132113213256
2819313041001207106912311121120119
291531241610155495081331211229770
30110610664106647716464116449
3117952123131118784410811123421
32125239312343496413016121114328
3315069106831257711310627113227126
341100742516857106234111218535
351678910080111495074401211224191
361111117711111177
(37)1234567891011121314
38149162536496481100121113663

全ての数字は予想不可能な変化を繰り返しているが、
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。もしご興味があれば、ぜひ挑戦してみてください。

暗号技術入門 第3版
暗号技術入門 第 3 版
作者: 結城浩
出版社/メーカー: SB クリエイティブ
発売日: 2015/08/26
メディア: 単行本

ちょっと暗号のことネットで調べたらすぐにこの本がヒットする定番の中の定番の本。いちいち書評書いても意味が無いほどの定番の暗号本。

関連記事