Hatena::ブログ(Diary)

hnwの日記 このページをアンテナに追加 RSSフィード

[プロフィール]
 | 

2014年5月17日(土) RSA公開鍵から素数の積を取り出す方法 このエントリーを含むブックマーク このエントリーのブックマークコメント

RSA暗号HTTPSSSHの通信で利用されている暗号化方式です。公開鍵として巨大な素数の積を交換しあって暗号に利用しており、この素因数分解が困難であることにより安全性が担保されています。このことは教科書にも載っているような内容で、ご存じの方も多いかと思います。


ところで、その素数の積を実際に見たことってありますか?少なくとも僕は見たことがありませんでしたし、大抵の人は見たことが無いのではないでしょうか。本稿ではこの公開鍵の情報を見る方法を紹介します。


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素数判定法で「合成数だ」と言われたら確実に合成数です。


何で割り切れるかを求めるのは難しくても、何かで割り切れることは一瞬で分かるというのは面白いですよね。


参考リンク

*1:すでにプロジェクトは終了しており、素因数分解しても賞金はもらえません。念のため。

人はいずれ死ぬ人はいずれ死ぬ 2014/05/18 04:16 Miller-Rabin素数判定法は確率的判定法なので,「確実に合成数です」はちょっといい過ぎかと思います.

甕星亭主人甕星亭主人 2014/05/18 07:06  言い切ちゃう処が工学的かと。 Wikiを覗いたけど、元はFermatの定理なんだから素数候補を探すにゃ役に立ちそうな判定法ですね。尤も特定の型の素数しか興味は湧か無いけれど。 Hardyが識ったら絶望で自殺しそうな方法論だなあ。

hogehoge 2014/05/18 07:58 >人はいずれ死ぬ
Miller-Rabin素数判定法は片側誤りアルゴリズムですから「合成数だ」と言われたら確実に合成数のはずですよ

hnwhnw 2014/05/18 08:41 人はいずれ死ぬさん、甕星亭主人さん、hogeさん:
コメントありがとうございます。
内容についてはhogeさんのおっしゃる通りで、
アルゴリズムとして確実だと伝えたかったんですが、
僕の日本語力と知識が足りなかったようです。
乱択アルゴリズムの分類に片側誤りと両側誤りというのがあるんですね。
今後は「片側誤りなので」と書きたいと思います。

甕星亭主人甕星亭主人 2014/05/18 08:45  然うですね。 此のtestは素数候補の中から、赤裸様な合成数を除外する為の物ですから、必然的に撥ねられた物は合成数と成りますね。 因数の素性情報としては役立た無いにしても。 失礼しました。

Glass_sagaGlass_saga 2014/05/18 15:23 合成数である事の判定にはopenssl primeコマンドも便利です。

openssl prime -hex B0F977574AB8...
を実行すると
B0F977574AB8417... is not prime
と返ってきます。

hnwhnw 2014/05/18 16:26 Glass_sagaさん:
コメントありがとうございます。
こんなサブコマンドがあるんですね!知りませんでした。
やはり中身はMiller-Rabinのようで、
openssl prime -checks 1 3825123056546413051
など意地悪な例を試すと時々「is prime」と誤判定しますね。

 | 
ページビュー
2199513