RSA暗号はHTTPSやSSHの通信で利用されている暗号化方式です。公開鍵として巨大な素数の積を交換しあって暗号に利用しており、この素因数分解が困難であることにより安全性が担保されています。このことは教科書にも載っているような内容で、ご存じの方も多いかと思います。
ところで、その素数の積を実際に見たことってありますか？少なくとも僕は見たことがありませんでしたし、大抵の人は見たことが無いのではないでしょうか。本稿ではこの公開鍵の情報を見る方法を紹介します。
OpenSSH公開鍵の中身を見る
まずはOpenSSHの公開鍵の情報を取り出してみます。OpenSSHの公開鍵は次のようなものです。
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCw+XdXSrhBcDFAXPcisrc8im4y8ytC46HEQ0GsWOph9OPK1elTQmBD5LATGfp4JG4pui1gyLC5Gd8NOdEuwQaeppfHL8vD0RKiZHfYaDp172k141SKeiUyJxUWy5bfwJfPMOZv+aBpFnZNE6oIR+ak41W5TqYPp6miGIfKg8su/kepwvI1Tm4MQYBmdSBAhlvV4p0GocrSvMrQDWRj9+P6lavDUv+wsH2omY27+mnFh+qxNJnk06ION0n4j/Kkd+qyYQxwflGxfmScIj/Zqr04InxuBVpyW2pIIHmH2SFNESmp2ztkkUjroOV8hzI+QDVgBBG0h9thAL4hndr20XiJ hnw@localhost
次のようなコマンドで公開鍵の中身を確認できます。（ただし、MacOSX Mavericks標準のOpenSSHでは動作しません。HomebrewでOpenSSHを作り直す必要があります。）
$ ssh-keygen -f .ssh/id_rsa.pub -e -m pem | openssl asn1parse
0:d=0 hl=4 l= 266 cons: SEQUENCE
4:d=1 hl=4 l= 257 prim: INTEGER :B0F977574AB8417031405CF722B2B73C8A6E32F32B42E3A1C44341AC58EA61F4E3CAD5E953426043E4B01319FA78246E29BA2D60C8B0B919DF0D39D12EC1069EA697C72FCBC3D112A26477D8683A75EF6935E3548A7A2532271516CB96DFC097CF30E66FF9A06916764D13AA0847E6A4E355B94EA60FA7A9A21887CA83CB2EFE47A9C2F2354E6E0C418066752040865BD5E29D06A1CAD2BCCAD00D6463F7E3FA95ABC352FFB0B07DA8998DBBFA69C587EAB13499E4D3A20E3749F88FF2A477EAB2610C707E51B17E649C223FD9AABD38227C6E055A725B6A48207987D9214D1129A9DB3B649148EBA0E57C87323E4035600411B487DB6100BE219DDAF6D17889
265:d=1 hl=2 l= 3 prim: INTEGER :010001
このように、RSA公開鍵の中身は整数2個です。今回興味がある合成数はB0F9…から始まる512桁の16進数で、10進表記すると617桁になります。
2つめの整数は0x010001=65537で、これはRSA暗号で言うところのeになります。RSA公開鍵・秘密鍵に含まれる内容はRFC 2313で定義されています。
SSL公開鍵の中身を見る
同じように、SSLの公開鍵の情報も取り出してみましょう。https://www.google.com/ で利用されているRSA公開鍵の情報は次のように確認できます。
$ echo -n | openssl s_client -connect www.google.com:443 | openssl x509 -pubkey -noout | openssl asn1parse -strparse 19
depth=3 /C=IE/O=Baltimore/OU=CyberTrust/CN=Baltimore CyberTrust Root
verify error:num=19:self signed certificate in certificate chain
verify return:0
DONE
0:d=0 hl=4 l= 266 cons: SEQUENCE
4:d=1 hl=4 l= 257 prim: INTEGER :9FA1E1B43B3A570ED0CF54BCCD18D8B2121331A44C373D093EEF73DD6423618E951FE46C8D4052626EDE0E82BF4C2ACF86FD413E81757484F9603150CFF293899FD4786426D6D2C2E71B01002D82AD220B5BBA9830D71F6B25FCD501E152921ABC8861875154776E6651640079B1C1C9B1C90B7A050CA45E5EC63647ED88966D55C8BF6513DA06B1679198D909B247F9C6A9C74BFD8660532CF5401B2205E53C05D5A95D5D3DFAED2EFA4061A7E949C8D0EE42B9AEC65352435666CFBACD248114DACEFC96E20D7B8C616D3494F2E3752A957ED367C07BE8E642B2AA15C496E5561EC8D160DC0C5C08AD25A250415CF62D39835838F712BC63BB6987CB5BC2FF
265:d=1 hl=2 l= 3 prim: INTEGER :010001
OpenSSHのときと同じように2048bitの合成数が取り出せました。もしもこの素因数分解ができれば、理屈上はGoogleの検索ワードが見放題というわけです（途中経路でパケットキャプチャできる権限など、他にも色々必要ですが…）。
素因数分解についての補足
この記事を読んで「よーしGoogleの公開鍵の素因数分解がんばっちゃうかー」と思われた方がいらっしゃるかもしれませんが、あまりオススメしません。現時点では2048bitの素因数分解は極めて困難な問題です。もし簡単にできるようなら世界中がオロオロするレベルの大事件と言えるでしょう。
ちなみに、以前はRSAセキュリティ社が「RSA Factoring Challenge」というプロジェクトを開催しており、さまざまな大きさの合成数の素因数分解に賞金がかかっていました*1。このうち、現時点で破られている一番大きな数は768bitの数です。それも、2007年頃から2年半近く多数のCPUを使って実現した成果のようで、我々一般人にとっては今でも十分難しいと考えられます。また、1024bitの素因数分解は768bitの約1000倍の計算が必要だそうで、2048bitの素因数分解は相当遠い目標のように感じます。
2048bitの数が素数でないことは一瞬で判定できる
こうした2048bitの数の素因数分解は難しいわけですが、これが合成数であることはすぐに判定できます。
PHPのGMP関数gmp_prob_primeを使って確かめてみましょう。これはGNU MPの関数mpz_probab_prime_pを呼び出すもので、中身はMIller-Rabin素数判定法です。
<?php $n1 = gmp_init("0xB0F977574AB8417031405CF722B2B73C8A6E32F32B42E3A1C44341AC58EA61F4E3CAD5E953426043E4B01319FA78246E29BA2D60C8B0B919DF0D39D12EC1069EA697C72FCBC3D112A26477D8683A75EF6935E3548A7A2532271516CB96DFC097CF30E66FF9A06916764D13AA0847E6A4E355B94EA60FA7A9A21887CA83CB2EFE47A9C2F2354E6E0C418066752040865BD5E29D06A1CAD2BCCAD00D6463F7E3FA95ABC352FFB0B07DA8998DBBFA69C587EAB13499E4D3A20E3749F88FF2A477EAB2610C707E51B17E649C223FD9AABD38227C6E055A725B6A48207987D9214D1129A9DB3B649148EBA0E57C87323E4035600411B487DB6100BE219DDAF6D17889"); $n2 = gmp_init("0x9FA1E1B43B3A570ED0CF54BCCD18D8B2121331A44C373D093EEF73DD6423618E951FE46C8D4052626EDE0E82BF4C2ACF86FD413E81757484F9603150CFF293899FD4786426D6D2C2E71B01002D82AD220B5BBA9830D71F6B25FCD501E152921ABC8861875154776E6651640079B1C1C9B1C90B7A050CA45E5EC63647ED88966D55C8BF6513DA06B1679198D909B247F9C6A9C74BFD8660532CF5401B2205E53C05D5A95D5D3DFAED2EFA4061A7E949C8D0EE42B9AEC65352435666CFBACD248114DACEFC96E20D7B8C616D3494F2E3752A957ED367C07BE8E642B2AA15C496E5561EC8D160DC0C5C08AD25A250415CF62D39835838F712BC63BB6987CB5BC2FF"); var_dump(gmp_prob_prime($n1), gmp_prob_prime($n2));
これを実行すると約0.3秒で結果が返ってきます。
$ /usr/bin/time -p php /tmp/prob-prime-n.php int(0) int(0) real 0.29 user 0.19 sys 0.08
どちらも0ということで、上で紹介した2048bitの数はどちらも合成数だとわかります。以前の記事「PHPで素数を数えて落ち着いてみた」でも紹介したとおり、Miller-Rabin素数判定法で「合成数だ」と言われたら確実に合成数です。
何で割り切れるかを求めるのは難しくても、何かで割り切れることは一瞬で分かるというのは面白いですよね。
