楕円曲線暗号を調べたが、RSAより全然複雑。 [ソフトウェア]
どこかで楕円曲線暗号を見かけて興味を持った。
RSAは素数の性質を利用しているのは簡潔で分かりやすいものっだったが、楕円曲線暗号はどうなんだろうか。
でも、記事を見るには会員登録をしないといけないとかで、中に入るのが面倒だったので、ググって他の情報を見つけた。最近、会員登録＋αを要求する情報サイトも多い。ほんと面倒くさい。
http://researchmap.jp/?action=multidatabase_action_main_filedownload&download_flag=1&upload_id=21849&metadata_id=24198
初見から色々誤解していることがたくさんあって、読んでいくうちにそれが明らかになった。
まず楕円曲線は楕円ではない。楕円の曲線部分（全部曲線だけど…）ではないということだ。英語でははっきりと違うんだけどね。 elliptic curve と ellipseで似たようなものかもしれないが、日本語ほど混同されることも少ないだろう。いわゆる二点からの距離の合計が一定な点の集まり（だったっけ？）、という楕円ではない。
あと上のリンクの35ページにある、AliceとBobの話だけど、それって別に暗号の話だけじゃない。物理学などではよくあるみたいだが、登場人物が二人出てくると、一方がAさんで、もう片方がBくん、という典型的な構成の説明をするときに、AliceとBobという頭文字で適当な名前に当てはめたものが典型的になっているようだ。そんなに物理の勉強をしたわけではないけれども、度々出てくるので定番なのかも。たぶんAndrewとBlondyでも、JackとBettyでも、太郎くんと花子さんでも、なんでもいいはずだ。でも、個人的な怨恨を含まないように、Alice & Bobということに収まったのかもしれない。
さすがに3人目のCarolと攻撃者Eveは他の分野では見られないかもしれない。特に自然科学だと、実行する人と観測者とか、違う条件で動く人間同士の場合分けや関係を示すことは多いのだが、３人以上だと社会科学的な様相を呈してきがちなので、二人以上の場合は少ないかも。そもそも原理を示すのに無駄に複雑にする必要はないでしょうし。
名前を使われたeveさんも初めから悪人決定ってのもすごいな。神話かなにかであったね。聖書だっけ？ パラサイトイヴとかのEveだろうけど、人間の始祖なのにこの扱いはなぜ？ ミトコンドリオン！
数学的な素養は別にして、簡単な事情を書いておきますかね。
・RSAでは1024bit以上の長さがないと安全が確保できないけど、楕円曲線暗号だと160bit以上で大丈夫らしい。
・鍵の長さが短いので、リソースが少ない組込系ではありがたがられてる。
・クラックするアルゴリズムがあまり役に立たない。
・今の所、RSAと量子コンピュータのアルゴリズムみたいなのは無さそう。
・既存のDSAの仕組みを使って、RSAが出来たことと同じような仕組み（公開鍵暗号、署名）を作れる。
RSAは単純で強力だが、いささか仕組みが簡単すぎる。だから、量子コンピュータのブルートフォースで何とかなってしまう可能性が高いし、桁数が大きい計算が量子コンピュータが出来るのであれば、容易にRSAがクラックされてしまう。楕円曲線暗号がそういうふうに量子ビットで解けるアルゴリズムがあるかどうかはよくわからない。
56ページに書いてあることには、問題のサイズが112ビットのものまでが解かれているそうです。だけど、PS3が200台あまりを半年ぐらい動かしっぱなしでクラックできた数字なので、それ以上の桁数の堅牢さは言うまでもないのでしょう。コンピュータはプロセスルールも頭打ちで、メニーコアが主流になってきている世の中では、これ以上計算力を望むには、GPGPUぐらいしかないのでしょうが、PS3のCELLもSPEを使って動かしてないとは考えられないので、多くの量子ビットを持った量子コンピュータでなければ、解けないという状況はRSAと変わっていないのかも。
ただ、RSAよりも少ないビット数で堅牢性を確保しているので、RSAほど暗号鍵の大きさの伸びしろを比較的考えなくていいんでしょうね。ヨルムンガンドではRSAを物理学者などをさらってきて、量子コンピュータで暗号をクラックしているみたいだったが、解く暗号のメールとかをきちんと受け取らない限り、わりと無用の長物かもなぁと思ったり。仮にメールだとしてもPOP3とかだと手元に届いちゃえば終りだし、アーカイブが残るくらいなら、そもそもリソースを気にしたPOP3なんて使ってないだろうし。ただSSLとかも解読できるから、Webのやり取りの情報は駄々漏れる可能性は高い。とはいえ、インターネットの間の通路に介在できるサーバのやり取りを取ってくるっていうのは、国家権力に近い組織が動かないとダメだよね。あぁHCLI社は並の国家以上かｗ。
そもそも160bitとか、1024bitの鍵の長さってどんなもんだろ。PDFの資料にも書いてあるけど、イマイチよく分からん。
InteractiveなRubyを使って出力してみましたが、RSAの1024bitという数は十分に長すぎて、電卓や表計算ソフトではまともに扱えませんね。ここに貼り付けるのにも、改行を入れなくてはなりませんでした。確かにこの桁数では組込系ではとても無理だわ、と思いました。2の160乗でも決して短くはないですし。
そんなわけで、理論的な解説部分は数学科の人に任せて、周辺事項でもググっておこうかな。 Risa/Asirってのをインスコとかしておこうか。桁数の大きい計算だけならRubyで事足りるんだけどな。
http://www.math.kobe-u.ac.jp/Asir/asir-ja.html
まぁ使うかどうかは今後のツッコミ具合による。細かいところの話は今度元数学科にねっちりと聴きこむ予定なので、数週間先のエントリーで分かった気になってほしい（多分、自分が聞いても表面上しか分からない可能性大だけど）。ん〜今回は数理的な面が全然つっこめなかったなぁ。
RSAは素数の性質を利用しているのは簡潔で分かりやすいものっだったが、楕円曲線暗号はどうなんだろうか。
でも、記事を見るには会員登録をしないといけないとかで、中に入るのが面倒だったので、ググって他の情報を見つけた。最近、会員登録＋αを要求する情報サイトも多い。ほんと面倒くさい。
http://researchmap.jp/?action=multidatabase_action_main_filedownload&download_flag=1&upload_id=21849&metadata_id=24198
初見から色々誤解していることがたくさんあって、読んでいくうちにそれが明らかになった。
まず楕円曲線は楕円ではない。楕円の曲線部分（全部曲線だけど…）ではないということだ。英語でははっきりと違うんだけどね。 elliptic curve と ellipseで似たようなものかもしれないが、日本語ほど混同されることも少ないだろう。いわゆる二点からの距離の合計が一定な点の集まり（だったっけ？）、という楕円ではない。
あと上のリンクの35ページにある、AliceとBobの話だけど、それって別に暗号の話だけじゃない。物理学などではよくあるみたいだが、登場人物が二人出てくると、一方がAさんで、もう片方がBくん、という典型的な構成の説明をするときに、AliceとBobという頭文字で適当な名前に当てはめたものが典型的になっているようだ。そんなに物理の勉強をしたわけではないけれども、度々出てくるので定番なのかも。たぶんAndrewとBlondyでも、JackとBettyでも、太郎くんと花子さんでも、なんでもいいはずだ。でも、個人的な怨恨を含まないように、Alice & Bobということに収まったのかもしれない。
さすがに3人目のCarolと攻撃者Eveは他の分野では見られないかもしれない。特に自然科学だと、実行する人と観測者とか、違う条件で動く人間同士の場合分けや関係を示すことは多いのだが、３人以上だと社会科学的な様相を呈してきがちなので、二人以上の場合は少ないかも。そもそも原理を示すのに無駄に複雑にする必要はないでしょうし。
名前を使われたeveさんも初めから悪人決定ってのもすごいな。神話かなにかであったね。聖書だっけ？ パラサイトイヴとかのEveだろうけど、人間の始祖なのにこの扱いはなぜ？ ミトコンドリオン！
数学的な素養は別にして、簡単な事情を書いておきますかね。
・RSAでは1024bit以上の長さがないと安全が確保できないけど、楕円曲線暗号だと160bit以上で大丈夫らしい。
・鍵の長さが短いので、リソースが少ない組込系ではありがたがられてる。
・クラックするアルゴリズムがあまり役に立たない。
・今の所、RSAと量子コンピュータのアルゴリズムみたいなのは無さそう。
・既存のDSAの仕組みを使って、RSAが出来たことと同じような仕組み（公開鍵暗号、署名）を作れる。
RSAは単純で強力だが、いささか仕組みが簡単すぎる。だから、量子コンピュータのブルートフォースで何とかなってしまう可能性が高いし、桁数が大きい計算が量子コンピュータが出来るのであれば、容易にRSAがクラックされてしまう。楕円曲線暗号がそういうふうに量子ビットで解けるアルゴリズムがあるかどうかはよくわからない。
56ページに書いてあることには、問題のサイズが112ビットのものまでが解かれているそうです。だけど、PS3が200台あまりを半年ぐらい動かしっぱなしでクラックできた数字なので、それ以上の桁数の堅牢さは言うまでもないのでしょう。コンピュータはプロセスルールも頭打ちで、メニーコアが主流になってきている世の中では、これ以上計算力を望むには、GPGPUぐらいしかないのでしょうが、PS3のCELLもSPEを使って動かしてないとは考えられないので、多くの量子ビットを持った量子コンピュータでなければ、解けないという状況はRSAと変わっていないのかも。
ただ、RSAよりも少ないビット数で堅牢性を確保しているので、RSAほど暗号鍵の大きさの伸びしろを比較的考えなくていいんでしょうね。ヨルムンガンドではRSAを物理学者などをさらってきて、量子コンピュータで暗号をクラックしているみたいだったが、解く暗号のメールとかをきちんと受け取らない限り、わりと無用の長物かもなぁと思ったり。仮にメールだとしてもPOP3とかだと手元に届いちゃえば終りだし、アーカイブが残るくらいなら、そもそもリソースを気にしたPOP3なんて使ってないだろうし。ただSSLとかも解読できるから、Webのやり取りの情報は駄々漏れる可能性は高い。とはいえ、インターネットの間の通路に介在できるサーバのやり取りを取ってくるっていうのは、国家権力に近い組織が動かないとダメだよね。あぁHCLI社は並の国家以上かｗ。
そもそも160bitとか、1024bitの鍵の長さってどんなもんだろ。PDFの資料にも書いてあるけど、イマイチよく分からん。
$ irb irb(main):001:0> print 2**160 1461501637330902918203684832716283019655932542976 irb(main):002:0> print 2**1024 1797693134862315907729305190789024733617976978942306572734300 8115773267580550096313270847732240753602112011387987139335765 8789768814416622492847430639474124377767893424865485276302219 6012460941194530829520850057688381506823424628814739131105408 2723716335051068458629823994724593847971630483535632962422413 7216
InteractiveなRubyを使って出力してみましたが、RSAの1024bitという数は十分に長すぎて、電卓や表計算ソフトではまともに扱えませんね。ここに貼り付けるのにも、改行を入れなくてはなりませんでした。確かにこの桁数では組込系ではとても無理だわ、と思いました。2の160乗でも決して短くはないですし。
そんなわけで、理論的な解説部分は数学科の人に任せて、周辺事項でもググっておこうかな。 Risa/Asirってのをインスコとかしておこうか。桁数の大きい計算だけならRubyで事足りるんだけどな。
http://www.math.kobe-u.ac.jp/Asir/asir-ja.html
まぁ使うかどうかは今後のツッコミ具合による。細かいところの話は今度元数学科にねっちりと聴きこむ予定なので、数週間先のエントリーで分かった気になってほしい（多分、自分が聞いても表面上しか分からない可能性大だけど）。ん〜今回は数理的な面が全然つっこめなかったなぁ。
コメント 0