| どるこむ仲間の掲示板! 過去ログ倉庫 | LOG:2002/08: | |
|
●2002年08月インデックス
●過去ログ検索トップ
■どるこむ仲間の掲示板へ
| ||
| [931] 公開鍵暗号の危機？ (6 レス) 2002/08/10(Sat) 03:24:37 |
ペンチアム さん |
| Web: (none) | |
|
ソースが2chで何なのですが、インド工科大学の学者が素数判定を多項式時間で行うアルゴリズムを発見したそうです。 私が学生の頃は、NP完全問題ではないかと言われていたような気がしますが… http://news2.2ch.net/test/read.cgi/newsplus/1028876818/l50 RSA暗号って言うのは、巨大な素数2つの積でできた数を素因数分解するのは困難である（≒指数関数時間かかる）ということを前提にしているだけに、今後の成り行き次第では暗号関係がすごいことになるかもしれないです。 ＃こんなこと勉強していたの、もう6年前か…（遠い目） 1. ９８ 2002/08/10(Sat) 08:48:44
量子計算機の存在を仮定した上でShorのアルゴリズムを適用すれば、大きな素数の積を多項式時間で素因数分解できる、というのは業界では有名な話ですが、如何せんその肝心な量子計算機がまだ「おもちゃ」のレベルでしか実現されていません。確かまだ6bit程度？このあたりの話で言うと、量子公開鍵暗号なんてのも出てきてますが、さていつ頃実用になるのかな。
この量子ってのはまだ非現実的であるため、鍵長が伸び伸びになって計算量が増えていく（1024〜2048bit）RSAに代えて、160〜256bit程度の鍵長でRSAの1024〜2048bit鍵長と同じような安全性を確保できる、楕円曲線暗号を利用するのが最近増えていますね。かの住基ネットで使われる、ICカードのデジタル署名なんかは事前計算方式の楕円署名だったような？（あやふや）こっちは安全性の根拠が楕円曲線上の離散対数問題であるため、素因数分解が容易に行えるアルゴリズムができたとしても、別段影響はありません。 楕円曲線上の点演算のμsレベルの高速化を必死になってやってたのが懐かしいな・・・（遠い目） ともかくこの論文はかなり興味あるんで、ちょっと読んでみますか。 ＃ってこんな修士時代の知識、今いる工場じゃ全然役にたたねえや（笑） 日本以上のIT大国であるインドにはそれを支える素地があった、と言うことでしょうか。
米国政府はこのアルゴリズムを知らなかったのでしょうか。 暗号解読規制をしているようですしね。 そのアルゴリズムで本当に判定できるならとんでもないことになりそうですね
まあ米国政府はすでに極秘で解読アルゴリズムを発見しているとかぃぅウワサはありましたけど(笑) ちなみにRijndaelも素因数分解が困難という前提でしたっけ？ 6. ぽん 2002/08/10(Sat) 19:06:04
＞「Apache 2.0に深刻な脆弱性」も気になりますねぇ(;￣▽￣)
｜httpd.confファイルに1行ディレクティブを追加するだけで、この脆弱性をなくすことができる。 至って自己解決できる模様(ほっ) |
|