はじめに

作者: 結城浩
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2008/11/22
メディア: 単行本
購入: 46人クリック: 720回
この商品を含むブログ (82件) を見る

引き続き「暗号技術入門」を読んでいます。昨晩公開鍵暗号について読んだので、その復習がてら、実際に公開鍵暗号を使った暗号化にチャレンジしたいと思います。

そもそも公開鍵暗号とは何かという説明ついては、この記事では触れません。

RSA を使った暗号化について

RSA とは

RSA は公開鍵暗号アルゴリズムのひとつです。現在、公開鍵暗号アルゴリズムの中では最も広く使われています。RSA でプライベート鍵*1を作る際に id_rsa というファイルを作ることが多いので、見覚えがあるという方も少なくないのではないでしょうか。

RSA による暗号化・復号化のアルゴリズムについて

RSA のアルゴリズムはべき乗と余剰のみで表すことのできる、非常にシンプルなものです。

暗号化は次の式で表せます。

${ \displaystyle 暗号文 = {平文}^{E} \bmod N }$

ここでの { E, N } のペアが公開鍵に相当します。

復号化は次の式で表せます。

${ \displaystyle 平文 = {暗号文}^{D} \bmod N }$

ここでの { D, N } のペアがプライベート鍵に相当します。

また、E, N, D という値は以下の手順で求めます。

(1) N を求める

${ \displaystyle N = p \times q }$

p, q はそれぞれランダムで十分に大きい素数です。

(2) L を求める

L は前述の式には登場しない値ですが、残りの値を求めるために利用します。

${ \displaystyle L = lcm (p - 1, q - 1) }$

lcm とは最小公倍数 (Least Common Multiple) のことです。

(3) E を求める

${ \displaystyle 1 \lt E \lt L }$

${ \displaystyle gcd (E, L) = 1 }$

gcd とは最大公約数 (Greatest Common Divisor) のことです。つまり E は L と互いに素な任意の整数です。

(4) D を求める

${ \displaystyle 1 \lt D \lt L }$

${ \displaystyle (E \times D) \bmod L = 1 }$

つまり 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
#=> "杏子とさやかは相思相愛♥"

杏子とさやかは相思相愛♥ という平文が無事に復号化できました！

感想

プログラマとして日頃よくお世話になっている公開鍵暗号がこれほどシンプルなアルゴリズムだとは思っていなかったので、目からうろこでした。公開鍵暗号は非常に画期的な発明だったそうで、画期的なものほど意外とシンプルだったりするんですね。対称暗号の章で出てきた、絶対に破られない無敵の暗号使い捨てパッドも (画期的ではないかもしれないけど) すごく単純なアルゴリズムでしたし。

暗号の世界っておもしろ！

*1:「秘密鍵」という呼び方も一般的ですが、「秘密鍵」は対称暗号の鍵の意味でも使われるため、それと区別するために書中では「プライベート鍵」という呼称が採用されています。

✲ﾟ｡.ヾ(⌒(ﾉ'ω')ﾉ☆.｡

変色系男子の日常。

公開鍵暗号アルゴリズム RSA を使って実際に暗号化してみる