kono@ie.u-ryukyu.ac.jp (Shinji KONO) writes:

> 河野真治 @ 琉球大学情報工学です。
> 
> In article <86zmdjdy80.fsf@bsd2.4bn.ne.jp>, Yoshitaka Ikeda <ikeda@4bn.ne.jp> writes
> > まあ、現実に使われているのはもっと大きいビット数なので今すぐとかれちゃう
> > わけじゃないですが。
> 
> じゃぁ、512bit が二カ月とかいうとだめかなぁって気にもなるか
> も知れませんがねぇ... 

ビット数に対して素因数分解の時間は準指数関数なのでまだもうちょっとは大丈夫だとは
思いますが、やはり、この状況だと512bitのRSA鍵はあまり使いたくない状況じゃないかな
と思います。最低1024bitかなぁ。
 
> > 典型的な使われ方だと、128bitとか256bitのセッション鍵を送る使いかただし、
> > ビット数ふやしても仕方がないような気もするので、楕円曲線ベースへの転換が
> > 起きるかもなぁ。
> > #そこら辺も含めた2010年問題ってのがあります。
> 
> もっとはっきりした一方向計算があれば、こんなに悩まないんでし
> ょうけど。あっさり決定番が出ないのは、P/NP とかとの関連です
> よね。

うまいものが見つかっても、効率性の問題が残ったりしますからねぇ。
というのもあってなかなか発展しないのかもしれません。
 
> 結局、順方向がP(っていうかlinear)が要求される以上、長さ固定
> の鍵は、NP で必ず解けるわけですよね。それ以上の強度は出ない。
> だから、P=NP っていう結果が出ると、どんな一方向関数をもって
> 来ようが、すべてが瓦壊してしまう。かといって、順方向がPでな
> い暗号が容認されるとも思えないし... 

準方向が多項式時間ってのもさることながら、逆方向も落とし戸では
多項式時間が要求されるあたりに難しいところがあると思います。
P=NPかどうかはなかなか難しい問題ですねぇ。
たぶん、そうなると公開鍵暗号は使い物になるものはまったく作れなくなるんじゃないかと
思います。
 
> そのあたり(P=NP)を放っておいて、がんがん研究を進めるのって危
> ないと思うんだが... あんまり、そんな風には考えないか。

難しいのは、P≠NPだったとしてもその問題が、量子計算において
QPになるか、ならないかというのが問題になってきそうな感じです。
P=NPかどうかは、あまり考えて無いなぁ。というのは、やはり暗号学って
理学じゃなく工学だからじゃないかなと思いますが。
 
> 実は神様が「自分が解けないような暗号はないようにする」という
> 感じで、「P=NP なんだけど、その方法は人間には見つけられない。
> ざまーみろ」みたいになっているのかもね。

面白い視点だなぁ。
ついつい神様には無限の計算量を仮定してしまいがちなので、
(計算量的安全性に基づいた)暗号は全て解けるような気がしてしまいがちです:-)


-- 
-- 
I LOVE SNOOPY!  でつ
Yoshitaka Ikeda mailto:ikeda@4bn.ne.jp
My Honeypot: honey@4bn.ne.jp  <-don't send this address