OpenSSLとPythonでRSA暗号の原理を知る
OpenSSLを使うと、次のようにして2048bitのRSA鍵が作成できる。
$ openssl genrsa 2048 Generating RSA private key, 2048 bit long modulus ......................+++ .................+++ e is 65537 (0x10001) -----BEGIN RSA PRIVATE KEY----- MIIEowIBAAKCAQEAui/OeOYeMrLv+U2w13hQkL204OQVlB05nksKa5LaNE6mT3WY (snip) -----END RSA PRIVATE KEY-----
ここで出力される内容は、ASN.1という構文規則で表現された情報をDERと呼ばれるバイナリ形式にし、それをさらにBase64エンコードしたものになっている。 このフォーマットはPEMと呼ばれる。
次のようにすると、生成した鍵に含まれる情報が見れる。
$ openssl genrsa 2048 | openssl rsa -noout -text
Generating RSA private key, 2048 bit long modulus
.................+++
.........+++
e is 65537 (0x10001)
Private-Key: (2048 bit)
modulus:
00:ab:b6:a0:55:95:3b:aa:2d:b7:65:fd:4f:56:5f:
(snip)
publicExponent: 65537 (0x10001)
privateExponent:
56:4f:af:fc:14:cd:2e:d7:57:ee:4e:0b:89:11:27:
(snip)
prime1:
00:df:8e:85:83:66:8c:2b:9b:74:7d:ce:76:e2:58:
(snip)
prime2:
00:c4:a2:0b:5d:2c:b9:4a:70:dc:72:eb:ea:e2:2b:
(snip)
exponent1:
27:2b:96:b3:36:55:9b:12:6a:ef:dc:2c:32:6e:97:
(snip)
exponent2:
36:4a:83:96:bb:55:81:af:3d:be:e1:52:9e:15:c9:
(snip)
coefficient:
68:6f:b4:c5:e8:09:16:9b:60:bb:a9:dc:de:3f:d1:
(snip)
68:6f:b4:c5は0x686fb4c5を表す。
つまり、modulusやprivateExponentに続く16進文字列は、それぞれ一つの大きな整数を表している。
鍵のbit数を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: 3243485389 (0xc153a8cd) publicExponent: 65537 (0x10001) privateExponent: 2834145457 (0xa8eda0b1) prime1: 59747 (0xe963) prime2: 54287 (0xd40f) exponent1: 34201 (0x8599) exponent2: 36255 (0x8d9f) coefficient: 58029 (0xe2ad)
このうち、modulusとpublicExponentが公開鍵、privateExponentが秘密鍵となる。 publicExponentは計算の効率化のため適度に小さく、かつ、1が立つビットが少ない数が使われ、ほとんどの場合 65537 (=0x10001) である。 残りの5つは計算の効率化のために残された数字であり、それぞれ下のような関係にある。
modulus INTEGER, -- n = p*q publicExponent INTEGER, -- e = 65537 (=0x10001) privateExponent INTEGER, -- d == e^(-1) mod (p-1)*(q-1) prime1 INTEGER, -- p prime2 INTEGER, -- q exponent1 INTEGER, -- d mod (p-1) exponent2 INTEGER, -- d mod (q-1) coefficient INTEGER, -- q^(-1) mod p
ここで、prime1とprime2はその名の通り素数である。 exponent1、exponent2、coefficientは、後述する復号処理を中国の剰余定理により効率的に行うために保存されている数字である。
上からもわかるように publicExponent、privateExponent は modulus よりも小さい数字であり、鍵のbit数はすなわち modulus が何bitで表される数字であるかを意味している。
この例では modulus: 3243485389 (0xc153a8cd) であり、確かに32bitの整数になっている。
Pythonを使ってメッセージを暗号化・復号してみる
ここで、暗号化したいメッセージを "BEEF" (=0x42454546) とし、上記の32bit鍵で暗号化してみる。 メッセージは、modulusより小さい値でなければならない。 つまり、32bit鍵の場合、暗号化できるメッセージの長さは一般に31bitとなる。
まずは、各数字を変数に代入する。
$ python
>>> import struct
>>> message = struct.unpack('>I', 'BEEF')[0]
>>> hex(message)
'0x42454546'
>>> modulus = 3243485389
>>> publicExponent = 65537
>>> privateExponent = 2834145457
Pythonのビルトイン関数 pow(x,y,m) で x^y mod m が計算できることを利用すると、暗号化処理は次のようになる。
>>> ciphertext = pow(message, publicExponent, modulus) >>> ciphertext 2545199955L
メッセージ（平文）と公開鍵を使って、暗号文 ciphertext が計算される。
ciphertextを受け取った受信者が、自分だけが知っている秘密鍵を使って元のmessageを求める復号処理は次のようになる。
>>> message2 = pow(ciphertext, privateExponent, modulus)
>>> hex(message2)
'0x42454546L'
>>> struct.pack('>I', message2)
'BEEF'
暗号文、秘密鍵、公開鍵を用いて、元のメッセージ "BEEF" (=0x42454546) が求まっている。
式の形からわかるように、暗号化処理・復号処理は対称的な関係にある。 誰でも知っている公開鍵で変換し、受信者しか知らない秘密鍵で元に戻すやり方は、暗号として用いられている。 一方、送信者しか知らない秘密鍵で変換し、誰でも知っている公開鍵で元に戻すやり方は、デジタル署名として用いられている。 デジタル署名は、データのハッシュ値を秘密鍵の所有者にしかできないやり方で変換しくっつけることで、
- データの作成者が公開鍵を配っている人物であることの確認（認証）
- データが署名された時点の内容から改ざんされていないことの確認（完全性）
を行う仕組みである。
RSA鍵を総当たりで破る
modulusを二つの素数prime1、prime2に素因数分解できれば、これらともう一つの公開鍵 publicExponent から秘密鍵 privateExponent が計算できる。 32bitのようにbit数が小さい場合、modulusの平方根から順番に割り切れる値を試していく総当たり法で簡単に素因数分解できる。
>>> modulus = 3243485389 >>> p = int(modulus**0.5) >>> p 56951 >>> while (modulus % p != 0): ... p -= 1 ... >>> p 54287 >>> q = modulus/p >>> q 59747
prime1: 59747 (0xe963), prime2: 54287 (0xd40f) と一致する値が求まっている。
これらがわかれば、鍵を生成するときと同じ手順により privateExponent が計算できる。 具体的には、拡張ユークリッド互除法を用いて mod (p-1)*(q-1) における publicExponent の逆元を求める。
>>> def egcd(a, b): ... x,y, u,v = 0,1, 1,0 ... while a != 0: ... q,r = b//a,b%a; m,n = x-u*q,y-v*q ... b,a, x,y, u,v = a,r, u,v, m,n ... return b, x, y ... >>> def modinv(a, m): ... g, x, y = egcd(a, m) ... if g != 1: ... return None # modular inverse does not exist ... else: ... return x % m ... >>> publicExponent = 65537 >>> modinv(publicExponent, (p-1)*(q-1)) 2834145457
最後の値が privateExponent: 2834145457 (0xa8eda0b1) と一致している。
この例ではmodulusが32bitと小さいのですぐに解けるが、modulusの値が1024倍になれば（＝modulusを表すbit数が10増えれば）、総当たりにかかる時間も1024倍になる。 RSAの安全性は、二つの大きな素数の積の素因数分解に大きな時間がかかる（bit数に対して多項式時間で解けるアルゴリズムが発見されていない）ことが根拠になっている。
mod (p-1)*(q-1) で privateExponent が計算される理由
privateExponentの計算は、mod p*q ではなく mod (p-1)*(q-1) で行われている。 これは、RSA暗号が正しく復号できる原理と大きく関係している。 上では説明しなかったが、実は publicExponent も (p-1)*(q-1) と互いに素な整数でなければならない。 ほとんどの場合に使われる 65537 (=0x10001) は素数なので、どのような p, q に対しても使うことができる。
RSA暗号が正しく復号できることは、次の「フェルマーの小定理」によって証明できる。
p を素数、a を p と互いに素な整数としたとき、a^(p-1) == 1 mod p
ここに (p-1) が出てくることが、(p-1)*(q-1) が用いられる背景である。
暗号文 ciphertext を c としたとき、フェルマーの小定理を利用すると、m が p と互いに素な場合と素でない場合のどちらについても
- c^d == m mod p
が成り立つことがわかる（計算の詳細）。 p と q は対称な関係にあるので、q についても同様に
- c^d == m mod q
が成り立つ。
上の2式は、ある整数 k, l を用いることで次の連立式に書き換えることができる。
- c^d - m = k*p
- c^d - m = l*q
p, q は素数なので、上の連立式が成り立つとき、k は q の倍数、l は p の倍数になっているはずである。 つまり、上の2式は K = k/q = l/p を使って次の式にまとめることができる。
- c^d - m = K*p*q
これを合同式の形に戻すと、n = p*q なので
- c^d == m mod n
となり、復号の式が完成する。
