「理論上最短のRSA鍵の鍵長は何ビットなのか？」という疑問が湧いてきたので、RSA鍵の長さに関する制約について調べてみました。とにかく小さいRSA鍵ペアを作ろうと思ったらp=3,q=5の4bit RSA鍵というのが作れそうですが、本当にそんな鍵が作れるのでしょうか？
本稿ではRSA暗号およびRSA署名のパディングに関する仕組みを紹介し、最短の鍵長となるRSA鍵について検討します。
RSAES-PKCS1-v1_5 におけるパディング
鍵長最短となるRSA鍵ペアを作る上で障害になるのが、RSA暗号のパディングと呼ばれる仕組みです。
RSA暗号における暗号化および復号処理は整数の累乗演算ですから、仮に平文mが1だった場合、暗号文も1ということになってしまい暗号として機能しなくなってしまいます。このような問題への対策として、受け取った平文をそのまま使うのではなく、パディング文字列を付加して暗号化するのがRSA暗号では一般的です。復号時には、単にパディング文字列を無視すれば元の平文を取り出せます。
現在もっともよく用いられているRSA暗号の方式は RSAES-PKCS1-v1_5 と呼ばれるもので、与えられた平文にパディングとして固定の3バイトおよびランダムの8バイトを付加します。元の平文が1バイトだとしても計12バイトになってしまうので、RSA暗号が成立するには最低でも96bit必要ということになります。
実際に96bit RSA鍵を作って公開鍵で暗号化してみると、1バイトの平文は暗号化できますが、2バイトの平文を与えると「data too large for key size」と怒られてしまいます。
$ openssl genrsa 96 > private-key.pem
Generating RSA private key, 96 bit long modulus
.+++++++++++++++++++++++++++
..+++++++++++++++++++++++++++
e is 65537 (0x10001)
$ openssl rsa -in private-key.pem -pubout -out public-key.pem
writing RSA key
$ perl -e 'print "a"' | openssl rsautl -encrypt -pubin -inkey public-key.pem | base64
XQRoJI+EJRN73cs9
$ perl -e 'print "ab"' | openssl rsautl -encrypt -pubin -inkey public-key.pem | base64
RSA operation error
140735114489936:error:0406D06E:rsa routines:RSA_padding_add_PKCS1_type_2:data too large for key size:rsa_pk1.c:153:
$
RSA署名だと最短でも368bit鍵が必要
次にRSA署名について考えてみます。署名というのは、対象となる文書のハッシュ値を取り、ハッシュ値をRSA秘密鍵で暗号化するようなものです。今回は、ハッシュ関数としてSHA1を使うRSASSA-PKCS1-v1_5 with SHA1を考えてみます。
先ほど、RSA 96bit鍵では最長1バイトの平文しか暗号化できないことがわかりました。SHA1は160bitですので、SHA1値をRSAで暗号化するのに96bitでは全然足りません。いったいどれほどの長さが必要になるのでしょうか。
調べてみると46バイト（368bit）が最短だとわかりました。パディングの11バイトと、SHA1値の20バイトに加え、ASN.1のヘッダ類で15バイトを消費しますので、これらの合計である46バイトより短い鍵長では署名時にエラーが出てしまいます。実際、360bit鍵でRSA署名を試すとエラーが出ることが分かります。
$ echo foo > foo.txt
$ openssl genrsa 360 > private-key.pem
Generating RSA private key, 360 bit long modulus
.++++++++++++++++++
.....++++++++++++++++++
e is 65537 (0x10001)
$ openssl dgst -sha1 -sign private-key.pem foo.txt
Error Signing Data
140735114489936:error:04075070:rsa routines:RSA_sign:digest too big for rsa key:rsa_sign.c:122:
当然ですが、SHA256などサイズの大きいハッシュ関数を使う場合はより長いRSA鍵が必要になります。
パディング無しで最短のRSA鍵を作る
パディングの存在を考えると、現実の実装が取り扱ってくれそうなRSA鍵は案外長いということがわかりました。では、パディング無しの条件で短い鍵に対する制約があるのでしょうか？
実際にOpenSSLで実験してみることにします。以下はn=15,e=3の公開鍵です。
-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBDwIBAw==
-----END PUBLIC KEY-----
この鍵で「0x0d」1文字の暗号化を行います。パディング無しにするためopenssl rsautlに「-raw」オプションを指定しています。
$ perl -e 'print "\x0d"' | openssl rsautl -raw -encrypt -pubin -inkey shortest-public-key.pem | base64
Bw==
短すぎる暗号文ができました。今度はこれを復号してみます。秘密鍵は下記です。
-----BEGIN RSA PRIVATE KEY-----
MBsCAQACAQ8CAQMCAQMCAQUCAQMCAQMCAQECAQI=
-----END RSA PRIVATE KEY-----
$ echo "Bw==" | base64 -D | openssl rsautl -raw -decrypt -inkey shortest-private-key.pem | od -tx1 -Ax
0000000 0d
0000001
このように、特にトラブルもなく復号できました。4bit RSA鍵での暗号化および復号がOpenSSLで機能したわけです。
補足ですが、この鍵ペアはn=15であるので、15以上の平文・暗号文は扱えません。「0x0f」1文字を暗号化しようとするとエラーで死にます。
$ perl -e 'print "\x0f"' | openssl rsautl -raw -encrypt -pubin -inkey shortest-public-key.pem | base64
RSA operation error
140735114489936:error:04068084:rsa routines:RSA_EAY_PUBLIC_ENCRYPT:data too large for modulus:rsa_eay.c:221:
先ほど紹介したRSAES-PKCS1-v1_5でのパディングの1文字目は0x00になっているのですが、これはnを超える平文を作らせないための仕様なのでしょう。
鍵の強度に関する注意
念のため補足ですが、短いRSA鍵は素因数分解による解読の危険性があります。256bit以下であれば、家庭のPCで一瞬で素因数分解が完了します。512bit鍵も個人が十分解読できる時代です。
2048bit RSA鍵であれば2030年頃までは安全とされていますので、実際に使うのであれば2048bit以上の鍵を使ってください。本稿で紹介した4bit RSA鍵を実用するなどは論外です。
まとめ
- 世界最小の鍵ペアである4bit RSA鍵がOpenSSLで動作した（全く実用的ではない）
- 通常の条件であれば暗号化には96bit以上のRSA鍵が、署名には368bit以上のRSA鍵が必要
