RSA鍵の生成時に確率的素数判定法を使って問題ないのか
前回記事「RSA公開鍵から素数の積を取り出す方法」でも紹介しましたが、RSA鍵の生成には巨大な2つの素数p,qが必要です。近年一般的に使われている2048bit RSA鍵の場合、p,qの大きさは1024bit、10進で約308桁の数になります。
このRSAのアルゴリズム中ではpとqを法としたフェルマーの小定理（正確にはその拡張であるオイラーの定理）を利用しています。つまり、pとqが合成数だとRSA暗号の大前提が狂ってしまいますので、pとqには確実に素数を選ぶ必要があります。
ところで、OpenSSLのRSA鍵生成の実装では、pとqの素数判定にMiller-Rabin素数判定法が用いられています。Miller-Rabin素数判定法は片側誤りの確率的アルゴリズムで、「たぶん素数」「確実に合成数」の判定ができるようなものです。pとqの素数性が重要なのに、その判定に確率的アルゴリズムを使っても問題ないのでしょうか？
合成数のp,qでRSA鍵を作ってみる
ものは試しで、合成数のp,qでRSA鍵を作ってみましょう。OpenSSLのRSA鍵生成の実体はbn_prime.cのBN_generate_prime_ex関数にあります。
*** openssl-1.0.1h-orig/crypto/bn/bn_prime.c 2014-06-05 16:22:48.000000000 +0900
--- openssl-1.0.1h/crypto/bn/bn_prime.c 2014-06-09 09:08:35.000000000 +0900
***************
*** 196,201 ****
--- 196,202 ----
if (!safe)
{
+ checks=-1;
i=BN_is_prime_fasttest_ex(ret,checks,ctx,0,cb);
if (i == -1) goto err;
if (i == 0) goto loop;上記のように1行追加することで、p,qが素数かどうか確認する際のMiller-Rabin素数判定法をスキップさせて、p,qが合成数になる確率を高めることができます。この修正を加えたOpenSSLとssh-keygenを用いてパスフレーズなしのSSH鍵を生成してみました。
$ ./ssh-keygen -f /tmp/broken_id_rsa Generating public/private rsa key pair. Enter passphrase (empty for no passphrase): Enter same passphrase again: Your identification has been saved in /tmp/broken_id_rsa. Your public key has been saved in /tmp/broken_id_rsa.pub. The key fingerprint is: 88:91:2d:63:fd:b9:5f:41:a5:74:39:4a:97:ee:e7:26 hnw@macalon.local The key's randomart image is: +--[ RSA 2048]----+ | . oo | | + ..+= | | * o .o+ . | | . = o . .. . | | . . S .. | | . .. .| | . . o | | . . E o| | . o | +-----------------+
生成した秘密鍵の中のp,qを確認してみましょう。
$ openssl asn1parse -in /tmp/broken_id_rsa
0:d=0 hl=4 l=1188 cons: SEQUENCE
4:d=1 hl=2 l= 1 prim: INTEGER :00
7:d=1 hl=4 l= 257 prim: INTEGER :BD7235019F70FD2FA112B89F7A9B049615169C03AE01C69F6D6A49451A65C010D916AEE8F6BED3EF47B507234A9572F545657C86F2E927F5C1DAD7956D1E897663FA35A4D582C721C58E586E8C0FCE8A6788CDBDB5915C0C7D8455F3D2DA5921C388A3C6C6180FE0358977D8D3AC8C0F41E0ED08BB72E1BADEE887E1CF5611B286BD8C199DD093FECEB0C5B8B02EDCD3077FE3267D66FACAB40C65A8C76A08F6D28B617C8BF0F226E49265C07728A8CA2BB17C86AD1813B898B6D2878B2FC37543CDFA23A8C15179234440D14216F3D43E9578A3500ADE27086FF733F31B56FC7DC0263176DCC0B2F2414CCE23D54EF41736AC3D8E052CF4B2972574E12639B3
268:d=1 hl=2 l= 3 prim: INTEGER :010001
273:d=1 hl=4 l= 257 prim: INTEGER :9A1369A2E13EEEDC2EDF60026C9FE931FB02C16E88B5EF09B8DE49AB07161C0857D707F876BDAAF69FD64E70D87705E10F48C3E7A9661156E20C0F6BFB2C6BD63AE7C37B451F30BF79C214900C1FCAF66BD02AAC912020C213CF6E6C785F97404B9C34BF345B5B861964AD714E6EB616AE98B58F758CB0A3E029346265D3755DDB9B0FEBE1DECD027D718734B24E8D3F0568A3AA7B599A76824DB7A5DB47D54E643A81FEC0B4F23FCF20C9DFA1259533692D3524E9B52DF2C37626A6EDDE477B432A76CEEDF82E63A8A6DB7D71B8335338650107F17A657E8675DE06C001C49A13A68E3BFE591481CE0EB3CB53430206A79CA9A5DA5C6ECB44D0DB8AE2FBC281
534:d=1 hl=3 l= 129 prim: INTEGER :E489D4B72A4EEE27550F6FA1ECFE04504EBC830E4DB689A807CD1CD1399F3018BA5A28EC54842BEFC01477AB822A31842EEAD02ABD2211E61C433DD927712F62BE3E392D3EEFB78BD1C0A6CFCE901EEC82E1B1718CA247B7909D3D6CBF9F7AC85E9F195245415FB6043C2EC0E756BBF6AD85D232215F7BDDBD03E41A500DD641
666:d=1 hl=3 l= 129 prim: INTEGER :D435D76CD11F1B67EE1C3FD1158B8E413ECB7CB470787218719A41B8A971B8B38D7377687F73684588F9BE87F1840395EF532F8B97B14ED3DB98FB02FC514A90E4907F92E5E93AD96F254319AF8E2087A34D695EA892B31FA39AC76F44ECEEA4898EFFC451959A05EC43B5AB7DF268CFF5B7DBA1C518A61184FADDE574715AF3
798:d=1 hl=3 l= 129 prim: INTEGER :AE5579FFB3757C74628DA0E18BD085E7E0F82A9D19A91A3F249C51D444B96B4E21B1AF300094C6936019FCE3C72A7A9553D8E9AD0093E1C5805FC6E9450E315088C11C8AA84CE2DDF4C69A3941606D468BDCB0A866D8500EF6710C2F4DC9D136D1FF59A8898E01FDEE231EA32695E2529D31CD1352A3ECF04C44909785E3D841
930:d=1 hl=3 l= 128 prim: INTEGER :2FC7BFAD7C98686F4A298A24E598FA7AAE4CDAD335CFA8C0E0333F40F8C5E6346750EC3DD7148111C6F99470BF6C5DF25064867C03B7A46C0731B6B2C164FC490B6D8D8BE1C055C3C746B888FC022048E9F7F015A41703C5C7EC7DA30BFDDCEDA71B4F73407B52A6AABFC413CCD3DBCD9721C28DF5F6CACD7F078D16B0D52509
1061:d=1 hl=3 l= 128 prim: INTEGER :5FD2EFBAF7CAC160391E92557D6102D3C26607B75BBF72D5F8A20CD30772FE90915DF1AF18389A227C1C48D17D76A1A9881EE74657838FCF83263D49C3927BA1E6C1D7AAD6532DF860C9912E6B5DFEF2F7826B0210BE3E120F39EE1EC4BE2FA4BF5396B191F51D982673B6CBDCEDB9668CC6F887D37F0574185B2571C3F397B3このうち、5番目と6番目がp,qです（参照：RFC3447 Appendix A.1.2）。これは下記の通り素数ではありません。
$ openssl prime -hex E489D4B72A4EEE27550F6FA1ECFE04504EBC830E4DB689A807CD1CD1399F3018BA5A28EC54842BEFC01477AB822A31842EEAD02ABD2211E61C433DD927712F62BE3E392D3EEFB78BD1C0A6CFCE901EEC82E1B1718CA247B7909D3D6CBF9F7AC85E9F195245415FB6043C2EC0E756BBF6AD85D232215F7BDDBD03E41A500DD641 E489D4B72A4EEE27550F6FA1ECFE04504EBC830E4DB689A807CD1CD1399F3018BA5A28EC54842BEFC01477AB822A31842EEAD02ABD2211E61C433DD927712F62BE3E392D3EEFB78BD1C0A6CFCE901EEC82E1B1718CA247B7909D3D6CBF9F7AC85E9F195245415FB6043C2EC0E756BBF6AD85D232215F7BDDBD03E41A500DD641 is not prime $ openssl prime -hex D435D76CD11F1B67EE1C3FD1158B8E413ECB7CB470787218719A41B8A971B8B38D7377687F73684588F9BE87F1840395EF532F8B97B14ED3DB98FB02FC514A90E4907F92E5E93AD96F254319AF8E2087A34D695EA892B31FA39AC76F44ECEEA4898EFFC451959A05EC43B5AB7DF268CFF5B7DBA1C518A61184FADDE574715AF3 D435D76CD11F1B67EE1C3FD1158B8E413ECB7CB470787218719A41B8A971B8B38D7377687F73684588F9BE87F1840395EF532F8B97B14ED3DB98FB02FC514A90E4907F92E5E93AD96F254319AF8E2087A34D695EA892B31FA39AC76F44ECEEA4898EFFC451959A05EC43B5AB7DF268CFF5B7DBA1C518A61184FADDE574715AF3 is not prime
このRSA鍵ペアでSSH通信できるのでしょうか？作った公開鍵を別のマシンに登録した上でログインしようとすると、下記のようにログインに失敗してしまいます。
$ ssh -v -i /tmp/broken_id_rsa 192.168.56.64 OpenSSH_6.6, OpenSSL 1.0.1h 5 Jun 2014 debug1: Reading configuration data /Users/hnw/.ssh/config debug1: /Users/hnw/.ssh/config line 86: Applying options for * debug1: Reading configuration data /usr/local/etc/ssh/ssh_config debug1: Connecting to 192.168.56.64 [192.168.56.64] port 22. debug1: Connection established. debug1: identity file /tmp/broken_id_rsa type 1 debug1: identity file /tmp/broken_id_rsa-cert type -1 debug1: Enabling compatibility mode for protocol 2.0 debug1: Local version string SSH-2.0-OpenSSH_6.6 debug1: Remote protocol version 2.0, remote software version OpenSSH_6.6.1p1 Ubuntu-2ubuntu2 debug1: match: OpenSSH_6.6.1p1 Ubuntu-2ubuntu2 pat OpenSSH* compat 0x04000000 debug1: SSH2_MSG_KEXINIT sent debug1: SSH2_MSG_KEXINIT received debug1: kex: server->client aes128-ctr hmac-md5-etm@openssh.com none debug1: kex: client->server aes128-ctr hmac-md5-etm@openssh.com none debug1: sending SSH2_MSG_KEX_ECDH_INIT debug1: expecting SSH2_MSG_KEX_ECDH_REPLY debug1: Server host key: RSA 78:b6:（以下略） debug1: Host '192.168.56.64' is known and matches the RSA host key. debug1: Found key in /Users/hnw/.ssh/known_hosts:79 debug1: ssh_rsa_verify: signature correct debug1: SSH2_MSG_NEWKEYS sent debug1: expecting SSH2_MSG_NEWKEYS debug1: SSH2_MSG_NEWKEYS received debug1: Roaming not allowed by server debug1: SSH2_MSG_SERVICE_REQUEST sent debug1: SSH2_MSG_SERVICE_ACCEPT received debug1: Authentications that can continue: publickey debug1: Next authentication method: publickey debug1: Offering RSA public key: /Users/hnw/.ssh/id_rsa debug1: Authentications that can continue: publickey debug1: Offering RSA public key: /tmp/broken_id_rsa debug1: Server accepts key: pkalg ssh-rsa blen 279 debug1: key_parse_private2: missing begin marker debug1: read PEM private key done: type RSA debug1: Authentications that can continue: publickey debug1: No more authentication methods to try. Permission denied (publickey).
RSA鍵のp,qが合成数だと何が起こるか
上の実験で何が起きたのでしょうか。それを知るために、まずはRSA暗号の仕組みを復習してみましょう。RSA鍵生成のタイミングで、素数p,qの他にeとdというパラメータが計算されます。このe,dは下記(1)式が成り立つように計算します。
- n=p*q（p≠q, p,qは素数）とする
- 任意のxに対して x^(e*d)=x (mod n) … (1)
このe,d,nを使うと、RSAの暗号化処理・復号処理は次のように表せます。
- 暗号化
- 平文をiとする、ただしi<n
- 暗号文 c = i^e (mod n)
- 復号
- 暗号文 c に対して c^d (mod n)で平文が得られる
このように、秘密鍵に含まれるdがバレなければ、暗号化に必要なeは公開することができるという仕組みになっています。
ところで、オイラーの定理を利用すれば、次の(2)式を満たすdが(1)式を満たすことがわかります。
- φ(n) = (p-1)*(q-1)
- e*d = 1 (mod φ(n)) … (2)
つまり、eのモジュラ逆数を取ればdが計算できるというわけです。
ただし、上記の前提はpとqが素数であることです。p,qいずれかが合成数の場合、このように求めたdが式(1)を満たさなくなるはずです*1。
上の実験でもp,qが合成数だったためにe,dの組が(1)式を満たせず、復号処理に失敗したと考えられます。
RSA鍵生成時にp,qいずれかが合成数になる確率
RSA鍵生成時にp,qいずれかが合成数だとRSAの復号処理に失敗してしまい、鍵ペアとして機能しないことがわかりました。一方で、p,qが素数かどうかはMiller-Rabin素数判定法という確率的アルゴリズムで行われますから、一定の確率で壊れた鍵ペアを生成してしまうことになります。
では、p,qの素数判定に失敗して壊れた鍵ペアを生成する確率はどれくらいなのでしょうか。その答えがOpenSSLのcrypto/bn/bn.hに書いてあります。
/* number of Miller-Rabin iterations for an error rate of less than 2^-80 * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996]; * original paper: Damgaard, Landrock, Pomerance: Average case error estimates * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */ #define BN_prime_checks_for_size(b) ((b) >= 1300 ? 2 : \ (b) >= 850 ? 3 : \ (b) >= 650 ? 4 : \ (b) >= 550 ? 5 : \ (b) >= 450 ? 6 : \ (b) >= 400 ? 7 : \ (b) >= 350 ? 8 : \ (b) >= 300 ? 9 : \ (b) >= 250 ? 12 : \ (b) >= 200 ? 15 : \ (b) >= 150 ? 18 : \ /* b >= 100 */ 27)
このマクロは、素数判定する数のビット数からMiller-Rabinのイテレーション数を返すマクロです。これは上記コメント部にある1993年の論文が元ネタで、素数を誤判定する確率が1/2^80以下になるようにイテレーション数を決定しています。
つまり、先ほどのp,qのどちらか一方でも素数判定を間違う確率は1/2^79以下になります。これは毎秒1000個の鍵ペアを生成できるマシン100万台で手分けして鍵生成し続けたとして、2000万年の間に壊れた鍵ペアが1つできるかどうかですから、他のバグを踏む確率の方がよほど大きそうな気がします。
決定的な素数判定アルゴリズムが使われない理由
いくら確率が低くても、確実性が必要なのに確率的アルゴリズムを使うのは気持ちが悪いと感じる人もいるでしょう。決定的な素数判定アルゴリズムを使うわけにはいかないのでしょうか？
決定的アルゴリズムが使われていない理由は性能の問題でしょう。IPAによる資料「素数生成アルゴリズムの調査・開発 調査報告書」(PDF)の5.2章によれば、1024bit素数の判定に決定的アルゴリズムを使うとMiller-Rabinの1000倍程度遅いようです。
得られる結果の精度と速度のバランスを考えるとMiller-Rabinの採用が妥当ということなのでしょう。
