続・世界最小のRSA鍵ペアは何bitか
前回の記事「世界最小のRSA鍵ペアは何bitか」でp=3, q=5（つまりn=15）の場合のRSA鍵ペアを紹介しましたが、kazuhookuさんからこんなブックマークコメントを頂きました。
面白い。n=4（あるいは2）はダメなのかな
もっと小さいnを採用できないのか？という指摘かと思います。前回記事では普段のRSA暗号のノリで「p,qは異なる奇素数」という前提を置いていましたが、既に非常識なくらい短い鍵長の話をしている中で常識にとらわれるのは無意味というものでしょう。
本稿では15未満のnでRSA暗号らしきものが構成できるのかどうかを探ります。
n=1の場合
RSA暗号の平文mに対して m^(e*d) = m (mod n)が成り立つ最小のnを考えると、n=p=q=e=d=1が見つかります。これは1bit RSA鍵ということになりますので、もし認められるなら世界最小なのは間違いありません。
n=1のRSA暗号というのは、平文も暗号文も0しか無い世界ということになります。文字が一種類しか無い世界での暗号とは何なのか？という哲学的な問いはいったん忘れて、まずはこのような鍵に対してopensslコマンドが動作するのかを調べることにしましょう。
$ cat /tmp/public-key-n1.pem
-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBAQIBAQ==
-----END PUBLIC KEY-----
$ openssl asn1parse -strparse 17 < /tmp/public-key-n1.pem
0:d=0 hl=2 l= 6 cons: SEQUENCE
2:d=1 hl=2 l= 1 prim: INTEGER :01
5:d=1 hl=2 l= 1 prim: INTEGER :01
$ perl -e 'print "\x00"' | openssl rsautl -raw -encrypt -pubin -inkey /tmp/public-key-n1.pem | base64
RSA operation error
140735149846608:error:04068065:rsa routines:RSA_EAY_PUBLIC_ENCRYPT:bad e value:rsa_eay.c:169:暗号化しようとすると「bad e value」と怒られてしまいました。OpenSSLのソースコードを確認したところ、n<=eだとエラーになるようです。これが必須のチェックだとは思いませんが、変な鍵なのは間違いないでしょう。
n=2の場合
次はn=2,e=1が候補になります。同様にOpenSSLで動作確認してみましょう。
$ cat /tmp/public-key-n2.pem -----BEGIN PUBLIC KEY----- MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBAgIBAQ== -----END PUBLIC KEY----- $ perl -e 'print "\x01"' | openssl rsautl -raw -encrypt -pubin -inkey /tmp/public-key-n2.pem | base64 RSA operation error 140735149846608:error:0306E06C:bignum routines:BN_mod_inverse:no inverse:bn_gcd.c:525:
今度は「no inverse」というエラーで怒られました。どうやら多倍長演算の前準備としてmod nで0x10000000000000000のモジュラ逆数を計算する処理が走るようで、nが偶数だと必ず死ぬようです。OpenSSLのバグといえばバグだと思いますが、仕方がないというものでしょう。
n=3の場合
n=3,e=1の場合はどうでしょうか。
$ cat /tmp/public-key-n3.pem -----BEGIN PUBLIC KEY----- MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBAwIBAQ== -----END PUBLIC KEY----- $ perl -e 'print "\x02"' | openssl rsautl -raw -encrypt -pubin -inkey /tmp/public-key-n3.pem | base64 Ag== $ cat /tmp/private-key-n3.pem -----BEGIN RSA PRIVATE KEY----- MBsCAQACAQMCAQECAQECAQMCAQECAQECAQECAQE= -----END RSA PRIVATE KEY----- $ echo "Ag==" | base64 -D | openssl rsautl -raw -decrypt -inkey /tmp/private-key-n3.pem | od -tx1 -Ax 0000000 02 0000001
何もトラブルなく動いてしまいました。なんと2bit鍵というわけです。
とはいえ、個人的にはこれをRSA暗号だと言うのには抵抗があります。e=1のときは平文と暗号文が完全に一致するので、そもそも暗号になっていません。
また、RSA暗号ではサイズの大きい合成数nの素因数分解が困難であるということが暗号強度の根拠になっています。しかし、nが素数だとこの前提が崩れてしまい、誰でも秘密鍵を復元できてしまいます。また、公開鍵に含まれるnが素数かどうかはミラー・ラビン素数判定法で高速に判定できるので、攻撃者は弱い鍵を容易に探すことができます。
逆に言うと、nが素数だったりe=1であったりする非常に弱い鍵ペアであってもOpenSSLで正常動作するというのは意外な結果かもしません。
