公開鍵暗号アルゴリズム RSA を使って実際に暗号化してみる
はじめに
- 作者: 結城浩
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2008/11/22
- メディア: 単行本
- 購入: 46人 クリック: 720回
- この商品を含むブログ (82件) を見る
引き続き「暗号技術入門」を読んでいます。 昨晩 公開鍵暗号 について読んだので、その復習がてら、実際に公開鍵暗号を使った暗号化にチャレンジしたいと思います。
そもそも公開鍵暗号とは何かという説明ついては、この記事では触れません。
RSA を使った暗号化について
RSA とは
RSA は公開鍵暗号アルゴリズムのひとつです。現在、公開鍵暗号アルゴリズムの中では最も広く使われています。RSA でプライベート鍵*1を作る際に id_rsa というファイルを作ることが多いので、見覚えがあるという方も少なくないのではないでしょうか。
RSA による暗号化・復号化のアルゴリズムについて
RSA のアルゴリズムはべき乗と余剰のみで表すことのできる、非常にシンプルなものです。
暗号化は次の式で表せます。
ここでの { E, N } のペアが公開鍵に相当します。
復号化は次の式で表せます。
ここでの { D, N } のペアがプライベート鍵に相当します。
また、E, N, D という値は以下の手順で求めます。
(1) N を求める
p, q はそれぞれランダムで十分に大きい素数です。
(2) L を求める
L は前述の式には登場しない値ですが、残りの値を求めるために利用します。
lcm とは最小公倍数 (Least Common Multiple) のことです。
(3) E を求める
gcd とは最大公約数 (Greatest Common Divisor) のことです。 つまり E は L と互いに素な任意の整数です。
(4) D を求める
つまり D は E との積の余剰が 1 となる任意の整数です。
実際にやってみる
杏子とさやかは相思相愛♥
この文字列を平文として使って、実際に RSA を用いた暗号化・復号化を試してみます。 計算は面倒なのでお馴染みの Ruby 先生の手を借ります。
(1) 文字列を整数に変換する
平文を整数に変換します。ここでの整数にはそれぞれの文字の Unicode コードポイント を利用します。
plain_text = '杏子とさやかは相思相愛♥' plain_integers = plain_text.each_codepoint.to_a #=> [26447, 23376, 12392, 12373, 12420, 12363, 12399, 30456, 24605, 30456, 24859, 9829]
(2) N, L, E, D を求める
最初に N を求めます。p, q の整数はそれぞれ僕が勝手に選んだ素数です。 本来は安全性のために十分に大きい素数である必要がありますが、そうすると計算が大変なので意図的に小さめの数を選んでいます。
p = 227 q = 4099 n = p * q #=> 930473
次に L を求めます。
l = (p - 1).lcm(q - 1) #=> 463074
それから E を求めます。
e = (2...l).find { |i| i.gcd(l) == 1 } #=> 5
最後に D を求めます。
d = (2...l).find { |i| (e * i) % l == 1 } #=> 92615
これで公開鍵 {E, N} とプライベート鍵 {D, N} が用意出来ました。
(3) 公開鍵を使って暗号化する
plain_integers #=> [26447, 23376, 12392, 12373, 12420, 12363, 12399, 30456, 24605, 30456, 24859, 9829] encrypted_integers = plain_integers.map { |i| i ** e % n } #=> [64809, 281306, 590262, 572608, 645260, 329917, 458957, 630062, 616040, 630062, 679686, 614873]
encrypted_integers
が暗号文です。
これを文字列に無理やり変換しようとしても、わけのわからない文字列になってしまいます。
cipher_text = encrypted_integers.map { |i| i.chr(Encoding::UTF_8) }.join #=> "ﴩ\u{44ADA}\u{901B6}\u{8BCC0}\u{9D88C}\u{508BD}\u{700CD}\u{99D2E}\u{96668}\u{99D2E}\u{A5F06}\u{961D9}"
(4) プライベート鍵を使って復号化する
decrypted_intergers = encrypted_integers.map { |i| i ** d % n } #=> [26447, 23376, 12392, 12373, 12420, 12363, 12399, 30456, 24605, 30456, 24859, 9829] decrypted_intergers.map { |i| i.chr(Encoding::UTF_8) }.join #=> "杏子とさやかは相思相愛♥"
杏子とさやかは相思相愛♥
という平文が無事に復号化できました!
感想
プログラマとして日頃よくお世話になっている公開鍵暗号がこれほどシンプルなアルゴリズムだとは思っていなかったので、目からうろこでした。 公開鍵暗号は非常に画期的な発明だったそうで、画期的なものほど意外とシンプルだったりするんですね。 対称暗号の章で出てきた、絶対に破られない無敵の暗号 使い捨てパッド も (画期的ではないかもしれないけど) すごく単純なアルゴリズムでしたし。
暗号の世界っておもしろ!