RSA暗号の秘密鍵は素数p,qで公開鍵はpとqの掛け算
コンピュータサイエンス的な修士号を持っているのに、RSA暗号の方式についてよく理解していないことをいまさらになって恥ずかしくなり、もう一度勉強し直した。
これまでの自分のRSA暗号の理解
だいたいどんな教科書でも、公開鍵暗号の一つであるRSA暗号の導入に入る前に共通鍵暗号の場合から考える。
■共通鍵暗号
共通鍵暗号は暗号化と復号化に同じ鍵を使う。送信者と受信者で同じ鍵を持つことで、送信者が暗号化したメッセージは、受信者本人によって復号化される。
ただし、送信先がたくさんあるとその数だけ鍵が必要になってしまうし、そもそも暗号化と復号化に使うこの共通鍵を送信者に安全に届ける方法がないという矛盾が生じるという欠点がある。
■公開鍵暗号（ここではRSA暗号の話しかしていません）
公開鍵暗号では、公開鍵で暗号化し、秘密鍵で復号化する。公開鍵は「開いた状態の南京錠」を、秘密鍵は「南京錠を開けるための鍵」をイメージすると良い。受信者が用意した「開いた状態の南京錠」を送信者に渡しておく。送信者はメッセージに南京錠をかけて第三者にはひらけないようにしてメッセージを送信してもらう。受信者は「南京錠を開けるための鍵」を持っているので安全にメッセージを見ることができる。このときの南京錠をかけることが公開鍵による暗号化を意味し、閉められた南京錠を開けることを秘密鍵による復号化を意味する。
この方法では同じ鍵で開く開いた状態の南京錠（公開鍵）をばらまいておき、自分だけが持っている南京錠を開けるための鍵（秘密鍵）を大切に持っておけば良いので鍵は2種類だけで良い。また、ばらまいた公開鍵だけでは復号化できないので安全に鍵を扱うことができる。
概念はわかっていたけれど、公開鍵と秘密鍵の実態とは
opensslで鍵のペアを作ってみる。秘密鍵himitsuを生成する。ここでは脆弱なのは承知の上で、みやすさのために32bitの鍵を生成する。
$ openssl genrsa 32 > himitsu
Generating RSA private key, 32 bit long modulus
.+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 65537 (0x10001)
himitsuの中身はこんな感じ。
$ cat himitsu
-----BEGIN RSA PRIVATE KEY-----
MC0CAQACBQC+icuhAgMBAAECBQCBayGRAgMA+gcCAwDDFwICGH8CAg1ZAgMAs5w=
-----END RSA PRIVATE KEY-----
himitsu から公開鍵kokaiを生成する。
公開鍵はこんな感じ
$ cat kokai
-----BEGIN PUBLIC KEY-----
MCAwDQYJKoZIhvcNAQEBBQADDwAwDAIFAL6Jy6ECAwEAAQ==
-----END PUBLIC KEY-----
これらのBase64でエンコードされたこの文字列は一体何者なのか。秘密鍵の中身を見てみると、こうなっている。
$ openssl rsa -in himitsu -text -noout
Private-Key: (32 bit)
modulus: 3196701601 (0xbe89cba1)
publicExponent: 65537 (0x10001)
privateExponent: 2171281809 (0x816b2191)
prime1: 64007 (0xfa07)
prime2: 49943 (0xc317)
exponent1: 6271 (0x187f)
exponent2: 3417 (0xd59)
coefficient: 45980 (0xb39c)
一方、公開鍵の中身はこれ。
$ openssl rsa -pubin -in kokai -text -noout
Modulus (32 bit): 3196701601 (0xbe89cba1)
Exponent: 65537 (0x10001)
秘密鍵は公開鍵の内容を包含していることがわかる。これらの鍵の中で重要な要素は3つmodulus, prime1, prime2である。
modulus = prime1 * prime2 という関係がある。64007*49943=3196701601 確かに成り立っている。prime1, prime2はその名から想像される通り素数である。公開鍵暗号は公開鍵で与えられたmodulusを素因数分解することでprime1, prime2を割り出すことが（計算時間の観点から）できないことを安全の根拠としている。もちろん今回は32bitという非常に桁数の少ない鍵なので、その気になれば3196701601が64007*49943の掛け算であることはすぐに計算できてしまう。しかし、これが非常に大きな素数同士の掛け算からなっている場合、その計算には膨大な時間を要する。
これらの公開鍵と秘密鍵のペアは2つの素数p, q、任意の正の整数nについて、以下式が成り立つことを利用して決められている。
この式は任意のXについて「(素数p,qと任意の正の整数nからなる式)乗」して、「p*qを法とする」とXに戻るということを表している。例えば、今回の例で言えば、X=11, p=64007, q=49943でnは任意の正の整数なので仮に1としておく。
確かに11に戻る。桁数が非常に大きな計算になるのでGMP*1を使った。
ここでこの「(p,qと任意の正の整数nからなる式)乗して」という部分を「公開鍵 乗」と「秘密鍵 乗」の2つの積と考えてみる。
つまり、これが成り立つ公開鍵と秘密鍵のペアを用意することで、以下式が成り立つ。
あるXを「公開鍵 乗して」「p*qを法とした」X'は、「秘密鍵 乗して」「p*qを法とする」ことでXに戻るのである。なんとも美しい。X'は秘密鍵がなければ中身がわからない。つまり暗号化されているのである。では上記の例で公開鍵と秘密鍵のペアを考えてみよう。
(1*(64007-1)*(49943-1)+1)=3196587653でこれを(公開鍵)*(秘密鍵)の積にしたいので素因数分解すると…。え、素因数分解…。鍵のペアを作るのに素因数分解が必要…なのか…？素因数分解が難しいことを根拠に暗号化をしようとしているのに、鍵のペアを作るのに素因数分解が必要とはこれいかに…？
少し悩んで色々調べてみたが、どうやらopensslでは鍵のペアを生成するときは、公開鍵を65537に決め打ちにする実装になっているらしい。鍵を生成したときのメッセージ「e is 65537 (0x10001)」は公開鍵を決め打ちしていることを表している。
公開鍵65537に加えて、素数p=64007, q=49943が決まれば、
ここでnは任意の正の整数なので65537で割り切れるようにn=44516とする。
これで公開鍵と秘密鍵の出来上がり。先ほどのファイルの中には、素数p,qから生成された公開鍵と秘密鍵が記述されている。
publicExponent: 65537 (0x10001)
privateExponent: 2171281809 (0x816b2191)
publicExponentが公開鍵、privateExponentが秘密鍵であり、これらは素数prime1,prime2から生成されていることがわかる。
改めてX=11というメッセージを公開鍵(65537)で暗号化し、秘密鍵(2171281809)で復号化してみる。
この暗号化されたX'=2182586379を受け取ったら、秘密鍵を使って復号化する。
確かにX=11に戻った。すっきり。
秘密鍵から素数p,qを隠したものが公開鍵
ここまで読んだ人ならすぐにピンとくると思う。要するに公開鍵と秘密鍵の関係は、素数p,qから秘密鍵を作り、そこからp,qの掛け算だけ残してp,qそのものを隠したのが公開鍵だということがよくわかった。
RSA暗号は秘密鍵で暗号化、公開鍵で復号化もできる
さらに言えば、勘の良い人ならこんなことにも気づいたかもしれない。
「公開鍵 乗」して暗号化して「秘密鍵 乗」して復号化できるのであれば、指数法則から考えて「秘密鍵 乗」して暗号化し、「公開 鍵」乗して復号化もできてしまう。
もちろん、公開鍵は世界中にばらまいているわけなので、暗号としての意味をなさないが、公開鍵で復号化することができるそれは、本当に私本人が秘密鍵で暗号化したものであるという証明になるため「電子署名」として利用することができるのである。この電子署名によって、確かに私が暗号化したものであるということを示すことができるのである。
