OpenSSL と Ruby で RSA 暗号を体験する

cryptography

RSA について調べていて興味深いエントリを発見したので、自分でも少しいじってみました。

OpenSSLとPythonでRSA暗号の原理を知る - ももいろテクノロジー

このエントリでは OpenSSL をつかってキーを生成し、Python で暗号化、復号化を試しています。

通常、鍵長は 2048bit くらいにしますが、32bit とか小さな数を指定することもできるんですね。
その場合にキーが10進数表現されるというのも知りませんでした。

$ openssl genrsa 32 | openssl rsa -noout -text
Generating RSA private key, 32 bit long modulus
.+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++.+++++++++++++++++++++++++++
e is 65537 (0x10001) 
Private-Key: (32 bit)
modulus: 2991699001 (0xb251b439) # n = p*q
publicExponent: 65537 (0x10001) # e = 65537 (=0x10001)
privateExponent: 1014831585 (0x3c7d19e1) # d = e^(-1) mod (p-1)*(q-1)
prime1: 57287 (0xdfc7) # p
prime2: 52223 (0xcbff) # q
exponent1: 10095 (0x276f) # d mod (p-1)
exponent2: 1459 (0x5b3) # d mod (q-1)
coefficient: 35827 (0x8bf3) # q^(-1) mod p

OpenSSL の上記の出力を使うと RSA の下記のアルゴリズムに基づいて、暗号化や複合化を行う事ができます。

c = m^e mod n # 暗号化 ( m は平文, c は暗号文 )
m = c^d mod n # 復号化 ( m は平文, c は暗号文 )

元のエントリは Python だったので、僕は Ruby を使って実験してみました。

† Ruby の実装

RSA では暗号化、復号化共に x^y mod z という冪剰余を計算する必要があります。Ruby では冪剰余 x^y mod z は単純に x ** y % z と書くことができますが、これがとてつもなく遅いので、今回は「アルゴリズム | 冪剰余の計算 - tbpg’s programming memo」で紹介されているアルゴリズムを使いました。

実際に暗号化、復号化をしてみると下記のような感じになります。
こうやって実際に動かしてみると実に興味深いですね。

irb(main):001:0> class Integer
irb(main):002:1>   def pow_mod(pow, divide)
irb(main):003:2>     return 1 if pow == 0
irb(main):004:2>     result = self.pow_mod(pow / 2, divide)
irb(main):005:2>     result = result * result % divide
irb(main):006:2>     result = result * self % divide if pow % 2 == 1
irb(main):007:2>     return result
irb(main):008:2>   end
irb(main):009:1> end
=> nil
irb(main):010:0> m = "CAFE".unpack(">I").first # 平文 "CAFE" を数値表現に
=> 1162232131
irb(main):011:0> n = 2991699001
=> 2991699001
irb(main):012:0> e = 65537
=> 65537
irb(main):013:0> d = 1014831585
=> 1014831585
irb(main):014:0> c = m.pow_mod(e,n) # 暗号化 (単純に c = m ** e % n としようとすると時間がかかる)
=> 501140304
irb(main):015:0> m2 = c.pow_mod(d,n) # 復号化 (単純に m2 = c ** d % n としようとすると時間がかかる)
=> 1162232131
irb(main):016:0> [m2].pack('>I') # 数値表現を文字表現に変換
=> "CAFE"