hnwの日記

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 [email protected]
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 [email protected] none
debug1: kex: client->server aes128-ctr [email protected] 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の採用が妥当ということなのでしょう。

まとめ

  • OpenSSLではRSA鍵生成の途中で確率的素数判定アルゴリズムを使っているため、壊れた鍵ペアが作られる可能性がある
    • 他のSSL実装でも同様だろう（未調査）
    • 万一壊れた鍵ペアが生成されるとRSAの復号処理に失敗して通信自体が成立しない
    • 鍵生成時に素数判定を間違う確率は天文学的に小さいので心配しなくて良さそう

この記事を書く前は、RSA鍵生成のタイミングでx^(e*d)=x (mod n)の検算をして「ごめん、壊れた鍵が出来たよ」エラーを出してくれると予想していましたが、そんな処理は無いみたいです。

*1:p,qが合成数にもかかわらず求めたdが式(1)を満たすこともありそうですが、どういう条件でそうなるか筆者にはわかりません。理論的背景などご存じの方は教えてください。少なくとも今回実験した範囲では必ずRSA通信に失敗していました

'); $entries_chunk.insertBefore(sections[0]); } else { chunk_id += 1; var $prev_entries_chunk = $entries_chunk; var $read_more_link = $('

これ以前の記事を表示する

'); $read_more_link.on('click', {chunk_id: chunk_id}, function(e){ $(e.target).hide(); $(this).remove(); $('#entries-chunk-' + e.data.chunk_id).fadeIn("slow"); }); $prev_entries_chunk.append($read_more_link); var $entries_chunk = $('
'); $entries_chunk.hide(); $entries_chunk.insertAfter($prev_entries_chunk); } } $(sections[i]).appendTo($entries_chunk); } });