(1002レス)上下前次1-新このスレッドは1000を超えました。完全に証明したと、米国とフランスの共同研究チームが8日、明らかにした。チームの一員で、仏国立科学研究センターのクリストフ・ブルイユ研究員(32)は朝日新聞の取材に「証明は終わっており、米数学会誌への論文掲載も決まっている」と話した。谷山・志村予想は、東京大の谷山豊・助教授(故人)と米プリンストン大の志村五郎名誉教授が1950年代半ばから60年代にかけて提示した。「だ円曲線」と呼ばれる曲線の仲間はすべて、数学的に極めて美しい「モジュラー形式」に支配されるという内容だ。予想が提示されて以来、新しい数の理論が生まれ、素粒子論や暗号理論に影響を与えた。数学者を350年余りも悩ませてきた「フェルマーの最終定理」は95年、米プリンストン大のアンドリュー・ワイルズ教授によって証明された。このとき、谷山・志村予想の一部は証明された。今回の研究チームはブルイユ研究員、米ハーバード大のリチャード・テーラー教授ら4人。予想の中でワイルズ教授が証明し残した部分をすべて解いたという。16:22:00「モジュラー形式」の数学的な意味は分からないけど、その形式にすることで解析に要する計算量が劇的に減るなら、多分脅威だろうね。楕円関数の数学的な性質を扱いやすくなるってだけの話なら、安全性に影響はないだろうね。19:23:00アイルランドの某社は実装にあと2年くれと言ってたな。段取り狂うから困るんだよな。化されたパスワードが全部出てくるんですけれども、ここに出てくるパスワードって総当りアタックでもネットワーク使って分散処理すれば何日かでわかっちゃうんでしょうかね?それともこんな学校のコンピュータ使わない方がいいのかな。18:42:00>>4あんまり詳しいことはわからないけど・・。辞書攻撃ならあっという間かもね。日とかで終わるんだろうなあ。アルゴリズムが公開されて、システム外で計算できる以上、これは仕方がないことだろう。そんな学校が悪いんじゃなくて、そんな簡単に解読できるユーザーがいるということの方が問題だと思う。passwdできる時点で、ローカルユーザにはパスワードだだ漏れだと思った方がいいです。察しの通り、そんな危険なホストはさっさとポイしましょう。ちなみに、谷山・志村は楕円曲線暗号には影響ないですよん。21:45:00ありがとうございます。谷村・志村をセールストークに使ってくる営業はスカだと判断しときます。22:22:00>>5-6パスワードはDESなんですけれども、一応パスワード制限として英語は大文字小文字混ぜて、数字も入れないと不可っつーことになってます。自分でしょぼいPerlスクリプトで総当りやってみたところ、8文字だと全部のパターンを解析するのに2〜3年かかりそうな感じなんすよ。)学校のマシーン30台でやっても結構かかる見込みで。そんなことしてたら目付けられそうだし、やりませんが。高度にプログラムしてけば、数時間で終わっちゃうもんなんですか?それにしても学校のアカウントを捨てるわけにもいかず、どうしたらいいものか。Johnで10時間くらい総あたりで頑張ってみたけど4文字のパターンまででしたね。00:22:00DESの総当りって、当然暗号化チップ使うんだよ。普通の店では買えないかもしれないが、PCで使えるボードもある。いまどき、本気でやって数時間もかからないと思うぞ。02:32:00>>16テーブルって、理論的に膨大だろ。やって検索するんだよ。03:46:00saltつけたって4096通りじゃん1台じゃ無理だが各自分散すればいいし。23:25:00>>9ほんとに技術な話じゃなくて,「新聞でご承知デショーが今のはヤヴァいんで我が社のをどぞー」というニューサイエンスが趣味です、私。いった営業さんを判断する話です。くだらない話ですいません。23:46:00FPGAならザイリンクスとか有名ですね。00:44:00>>13Johnは、辞書の単語。passwdファイルの本名、ユーザ名をすべて総当りしてくれるよ。大文字小文字の組み合わせ、語尾に適当な数字の追加と、あらたか一般人が考えそうな組み合わせをすべて試してくれたあと総当りモードにはいったような記憶がある。01:10:00解読チップなんてあるわけないだろ。21厨房、逝って良し。暗号化チップで総当たりするにきまってるだろ。ちなみに、ザイリンクスじゃなくて本物(?)も存在しますよ。電子商取引アクセラレータ。最近では個人で買える値段のNICに載っていることすらあります(想定されているのは大概IPsecですが)。03:12:00>>25ここくらい読んでおけよ。日がかりで解読したときのニュースだよ。characterに限定していいだろ。すると、かかる時間は100分の1くらいかな。チップから設計すると、本当に数時間のオーダーなんだな。アルファベットと数字に限定しても引っかかるユーザーはたくさんいるだろうから、現実はもっと厳しいな。秋葉原で売っているハードだけでやった場合はどのくらいまで速くできるんだろう。10:41:00>>26http://www.distributed.net/des/つーか公式ページにも書いてあったね。むかし読んだっきりだったから忘れてた。IIIになると、たったの22時間。カスタムチップまで作られちゃかなわんなぁ。12:52:00でも、どっちにしろ、まともなパスワードつけてたら、ふつうの一個人レベルではまだDES解読はむりですねEFF+dnetで一日未満なんで、NSAとかが専用チップ作ってやれば1分以下でできそうよくつかってるlinuxのshadowは、DES(旧マシンから移行ユーザー)とMD5(新ユーザーと)が混在してる状態。以上になったという話を、昔下条先生がしていた。18:34:00>>19宇宙誕生から現在まで何秒かかっているか考えてみよう。19:20:00x4096ででいいんだよ。03:23:00みなさん、NP完全性と近代暗号をちゃんと勉強しましょう。宇宙に存在する、陽子の幅を光子が横切る時間をワンクロックとした場合に、現在の宇宙存在する陽子の数の並列計算素子が、現在考えられている宇宙の寿命の長さだけ計算した場合に解けないような暗号体系は、計算量増大の指数性を考えれば合理的なビット数で容易に構成できます。実用的には、PKIのキーを生成する乱数プロセスの方がセキュリティーホールになるんだよね。01:25:00結局、現在の暗号技術なんてあと数十年の命なのよ。16:47:00>>35量子暗号は、「物理層」に依存するから、一般用途への適用は難しいよ。量子キーは、シード発生には使えるかもね。手法そのものが廃れることはないと思うね。06:34:00>量子計算機は、結局並列化による計算量のアップなんだけど、>並列化は、素子数を倍にすることによってせいぜい、倍の速度なんだけどおいおい、何トンチンカンなこと言ってんだ?重ね合わせとかテンソル積とかのキーワードくらい理解した上で発言しろよ。20:09:00>>39なんでいきなりテンソル積が出てくるんだい?量子力学は専門外だから詳しくはないけど。どこかでみたが疑似乱数のMersenneTwister(たしか)は宇宙の量子と同じ数のコンピュータをそろえても数え上げるのが難しいほどの周期だとか。2の一万乗ぐらいあったはず。暗号も桁数を増やせばそれぐらいの空間に出来るとおもうのだが。00:43:00暗号文に比較して鍵空間の方がでかいのは実用上問題ありそうですね。06:24:00量子コンピュータの状態を表すのに使う。量子計算のアルゴリズムについて述べている論文を読めばぞろぞろ出てくる。少なくとも素因数分解や離散対数問題を多項式時間で解く量子アルゴリズムが発見されているのだから、RSAやDSAといった暗号方式は量子コンピュータの前では無力。誤解しないで欲しいのは、量子コンピュータは従来のコンピュータとは全く別のロジックで動作するものであり、単純に計算が速くできるようになるわけじゃないってこと。NP完全やNP困難といったクラスの問題が量子アルゴリズムを使って多項式時間で解けるかどうかはまだわかっていない。従来のコンピュータでも未解決なんだけど。量子アルゴリズムまじですか。素因子分解は、”計算順序依存性”がないアルゴリズムで並列計算には向くわけですが、それにしても多項式時間で解くためには次の除数を求めるの様な処理を、数値の大きさにかかわらず一定で解かねばなりません。私の理解する量子計算機は、量子状態の重ね合わせにより、一度のオペレーションでn個の要素に対する処理を行えるものですが、本質的に超並列演算の域を出ません。DNA計算機や分子計算機の様に超並列性を持つにすぎません。ホントならば厳密に順序依存性のあるNP完全なアルゴリズム以外暗号に利用できなくなります。よろしければ、その論文に対するリンクを教えてください。俺なんかこれは強力な暗号です、ハイそうですかってなレベルで導入しちまってるよ。利用可能な並列素子が”無限”にあるとすると、素因数分解は多項式時間で解けます。次の因子を求めるための繰り返し演算を一度に並列化できるからです。ここに書いた宇宙最大の計算機、つまり素子数が宇宙全体の陽子の数と同じでも高々十の80乗個(エディントンの推定)の素子を持つにすぎませんから高度暗号の解読では、たちまち素子の数はつきてしまいます。数が大きくてもそれは”無限”ではなく高々有限だからです。23:04:00>>素因数分解や離散対数問題を多項式時間で解く量子アルゴリズム>まじですか。んー、衝撃的な話題だったんで結構多くの人が知ってると思ってたんだけど。量子コンピュータの計算能力の秘密は、量子力学の重ね合わせの原理により、n個の素子(キュービット)で2のn乗個の状態を表すことができ、しかもその2のn乗個の状態に対する並列演算ができるってこと。この状態を表すのにテンソル積が使われている。2のn乗個の重ね合わせ状態にある演算結果から目的の解を取り出すのは結構難しいので、実際に多項式時間での解法が見つかっているのは素因数分解や離散対数問題のような周期性のある問題だけ。量子コンピュータを使ってもNP完全問題は多項式時間では解けないんじゃないかっていう意見が多い。日本語のサマリーとしては、http://www.ipa.go.jp/security/enc/QuantumComputers/contents/contents.htmlが良くまとまってると思う。量子計算の詳しい原理については参考文献を当たってね。23:20:00んで、暗号を使う側の立場からすると、現在の1024ビットとかのRSA暗号を解読できるような量子コンピュータはあと2,30年で実現できるのではって予想があるのが恐ろしいところ。それを諜報活動に利用するなんて話も夢物語じゃなさそう。ネット上の商取引とかの信用にも係わることなんで、これはかなり重要な問題。00:09:00>(しかも通常の暗号化・復号化は従来のコンピュータでできるようなもの)量子コンピューティングが実用化できたとして、それを応用するにはこのあたりが一番難しそうですね。そのうち1-chip量子暗号デコードユニットなんてのが実用化されるのだろうか。00:40:00もう何が何やら・・・ロスアラモスにあるとかいう量子コンピュータはどんな姿なのでしょう?正真正銘の「電子マネー」は、実現出来るのでしょうか?個人的には実現してほしくないです。00:50:00>>46読みましたけど、やはり、並列度の仮定として、任意個の重ね合わせ状態がとれることが前提ですね。テンソル積は、状態空間上のユニタリ変換を表す際に用いられていますが本質的には重ね合わせられた2^nの状態に対して、一度の処理で超並列演算が行えるということにつきます。前述のように量子コンピュータを使わなくても、任意個、つまり無限の素子を仮定すれば、素因子分解は多項式時間で解けます。演算単位をビットで表さない多値コンピュータにおいて各単位に、たとえば、光の波長多重の記憶をさせるようなモデルをとっても、つまり、量子力学を持ち出さなくても全く同じ原理が適用できます。そもそも、波動の多重可能性に本質があるからです。(ちなみに、構成上全く同様に、テンソル積を用いてモデル化可能です)ただし、実際には多重可能な情報量に、現実的な限界があるのです。この範囲では、計算量理論に本質的な影響を与えると思えないのですがいかがですか?そもそも暗号の計算量理論では、構成可能なもっとも高速つまり、超並列性を尺度に考えているからです。計算量理論の観点からは並列度が”無限”でない限り、そこにブレークスルーはありません。ある大きさの問題までは、多項式時間なのですが、それ以上になると指数的な時間がかかってしまうからです。01:05:00量子情報については良く分かりませんが、ここのリンクは参考になりそうです。01:05:00ちなみに、”はやいコンピュータ”の可能性としての量子コンピュータを否定するものではありません。01:48:00難しい用語を用いるのは本意ではありませんので計算量の基本的な考え方の確認をさせてください。因数分解を例にとります。数値xの因数分解は、学校で習ったようにxにたいして、小さな数字から、x/2までの数字でわり算を試していきます。このときおおよそnビットの数字なら2^(n−1)回のわり算をすると考えられます。nビットのデータに対して、2^(n−1)の計算が必要なわけでデータ量すなわちビット数の増加に対して、指数的に計算回数が増えます。このとき、このアルゴリズムの”計算量は指数的”といいます。これにたいして、nビットの各ビットのorをとる計算はn回の計算で住むわけです。データ量nに対して、その多項式たとえばn^2+1,n^10+n^3+1などで計算回数が表せる場合、このアルゴリズムの”計算量は多項式的”といいます。”指数的計算量”のアルゴリズムの場合、たった数ビット増やしただけで飛躍的に多量の計算をしなければなりません。このため、暗号方式としては、キーが既知であれば、エンコード、デコードには”多項式時間”のみで、キーが既知でない場合、”指数的時間”が必要な方式が選択されます。単純に言えば8ビットの暗号が安全でない場合、16ビットにすると、キーを知っている人は、倍の時間がかかるのみですが、知らない人には256倍の時間がかるというようなことです。02:11:00失礼しました。128ビットの暗号がだめなら、256ビットにした場合、デコードには倍程度の時間がかかるのみだが、解読には3.403*10^38の時間がかかります。計算速度が有限である限り、同じアルゴリズムの鍵長を少し長くするだけで対処できてしまうのです。これが本質的なポイントになります。07:43:00んー、なんか注目する視点が違っているような気がしてきた。量子コンピュータの場合、その計算能力が素子数に応じて指数関数的に増えていくってのが重要な問題。1024ビットの暗号が解読されるようになってしまったから2048ビットにしようって考えても、倍の素子数を持つ量子コンピュータが開発されればあっさりと解読されてしまう。今までのように、何ビット増やすと解読にかかる時間は10の何乗倍になるから事実上解読不可能ですよ、ってなことが言えなくなるから暗号の安全性が保証できなくなる。実際、数千キュービット級の量子コンピュータを実現できるような素子についての研究や、ノイズに対処するための量子誤り訂正符号の研究などが活発に行なわれているから、実現可能な量子コンピュータの限界が見えるのはかなり先になると思う。今現在解読が無理でも近い将来解読が可能なるだろうって言われる暗号を実用にはできないでしょ。それに、通常の暗号化・復号化は多項式時間でできるからといって、いくらでも暗号のビット数を伸ばしてよいという訳にもいかない。電子マネーで決済しようとしてカードを入れたら、チェックが終わるのに30秒かかりました、では実用になるわけないでしょ。16:08:00なんか一部、暗号そのものが嫌いな人が必死になってる印象があるなぁ。16:57:00>>56いやいや、別に俺は暗号を否定しようなんて思ってないよ。量子計算でRSAが破れるっていうエキサイティングなネタを肴にいろいろ思考実験してるだけ。量子コンピュータの実現までは少なくとも10年以上かかるんだからゆっくりまったりやりましょ。21:06:00釈迦に説法かとは思いますが。>電子マネーで決済しようとしてカードを入れたら、チェックが終わるのに>30秒かかりました、では実用になるわけないでしょ。ポイントはデコードと、解読のアルゴリズム上本質的な速度差です。一方が多項式的で、他方が指数的なのが効いてくるのです。解読が速くなったから鍵を長くしたのであれば、そのときデコードは、”もっと比較にならないくらい”速くなってるから問題ないのでは?その際も、解読には大がかりな計算が必要で、デコードはICカードで可能なはずです。「ある期間に登場する電子計算機を仮定して、解読にかかる費用」を元に決めるのが通常です。宇宙が終わるまでに解かれない暗号も構成可能でが、一般的には解読に要する費用に、解読の結果の利益が見合わない水準に設定されます。”絶対安全”、”破られない”は古い考え方です。用性のバランスに着目するのが近代暗号の考え方です。40bitRSAを使っているシステムが、何十年か後にちょうど2000年問題のような陳腐化に直面することなどは否定できません。最後に、超並列計算機でも解けない、つまり、並列不能な暗号もあります。いまのところニーズがないために用いられていません。いう突っ込みはいいとして。使われている暗号の強度はどうなの?。話だけど、これは量子暗号の場合どのくらいの素子数に相当するの?。結局のところ、量子計算機時代に備えて、今の暗号技術の寿命を知っておかないとシステムの寿命が見えないからね。理論的な話よりもいつまで暗号化データの安全性を確保できるって方が興味あるなあ。14:15:00>>59量子コンピュータの計算能力を今までの尺度(MIPSとか)で計るのはあんまり意味が無いと思う。bitの数を素因数分解するのは今のコンピュータが何千倍も速くなったとしても事実上無理だねってのが従来の議論。多項式時間で素因数分解ができるようになる。bit数が2倍になっても高々数倍の時間で計算ができるってこと。bitの数を素因数分解できる量子コンピュータはいつ出来るんだって言われてちゃんと答えられる人は居ないと思う。あと10年で出来るなんて強気な意見の人もいれば、どう頑張ったって少なくとも21世紀中は無理でしょって言う人もいる。量子コンピュータの研究なんてほとんど歴史が無いからね。そのわずかな時間で数キュービットの量子コンピュータの実現に成功してるってのは注目すべき点。個人的にはUNIX最後の日(2038年1月)よりずっと近い未来の話になるような気がする。詳しくは、上のほうにあるリンクをたどってね。ちなみに、暗号関連で今のところ知られている量子アルゴリズムってのは素因数分解や離散対数問題ぐらいなので、秘密鍵暗号についてはまだ大丈夫。暗号化を行なう関数の構造によっては、あっさり破られるものが出てくる可能性は否定できない。14:19:00暗号の流通っていうと、すぐアメリカがしゃしゃり出てくるけど、ヤパ、こういうのは政府とかで囲ってコソ〜リと研究した方がいいのかもネ。論文発表するより、極秘でやる分野じゃない?本質的に、暗号は解けるものなんだから。明日、違うロジックが考案されて、あっさり解けるかもしれないし。暗号の利便って、考案から解読までの時間のギャップが作り出すものなんだから。考案している方が、解読研究してる方に時間をプレゼントするのはナンセンスだと思う。いえば、機能メモリってどうなったの?スレ違うけど。20:13:00>>63何故オープンな規格の暗号じゃないと信用できないかっていう事をわかっていないね。22:42:00>>64具体的に書かない知ったか糞レスは逝ってよし。00:14:00>>66しったか、というのは、65とか63のこと?たしかにAESやNESSIEで敗れ去った暗号を使おうとする人はあんまいないだろうね。03:15:00>>63>本質的に、暗号は解けるものなんだから。天文学的な時間が許されればね。05:22:00なんかfjっぽいスレだねぇ。いう話なんでしょうか?すんません厨房なもんで詳しいかた、教えてください。選ぶ側が日本の大学や企業の先生方だとすると、大変失礼だけど、ちょっと心配だなぁ。評価もさせて、ってのが一番の気がする。>>70fj歴も長いけど、やっぱでちゃうのかなぁ。00:23:00>71決して詳しくはないけど..日本では、学が産に利益を与えられるような話でないと未だに官がGOを出さない(プロジェクトが進まない)からでは?米だって、冷戦時代ではそれが当たり前だったのだし。Rijndahlが怪しいということでは無いと思います。評価もさせて、ってのが一番の気がする。09:52:00今のところ、楕円暗号が理論的に最強です。00:04:00息の長いスレやね......なんか、共通鍵暗号と公開鍵暗号の話がごっちゃになってる気がするけど...>>72いろいろ探しても、実際の暗号化に用いる「カオス」を生成させる数式を見つけられなかったんだけど、どこかに書いてる?具体的なアルゴリズムを示さない暗号なんて誰も使いたがらないから、それを隠している暗号なんて、トンデモって言われてもしょうがないと思う。ほとんど情報がないから、これはあくまで個人的な印象だけど弱鍵だらけで結局まともな暗号は作れなさそうな気はする。>>77「理論」上での強さだけなら量子暗号が最強でしょ。解読どころか傍受すら不可能なんだから。...ってのは冗談だけど。17:31:00>>80認証は、ハードなレベルにになると結局は生体認証とかいうお話になっちゃう。18:38:00>また、演算単位をビットで表さない多値コンピュータにおいて>各単位に、たとえば、光の波長多重の記憶をさせるようなモデル>をとっても、つまり、量子力学を持ち出さなくても全く同じ原理>が適用できます。そもそも、波動の多重可能性に本質があるからです。>(ちなみに、構成上全く同様に、テンソル積を用いてモデル化可能です)これは違うよ。01:26:00>>83現状を見る限りは大嘘。18:11:00侵入しました。00:47:00話が変わるけど、通常UNIXパスワードはDESによって暗号化されいますが、何故OpenBSDはDESではなくてblowfishを使っているのでしょう。02:06:00>>87暗号の自慢はいいから、大学全体のセキュリティを考えてよ。昨年の中国からの中央省庁Crackingは、あのノーベル賞が取れない東京大学が踏み台にされたんでしょ。最近だとあんまり『通常』ってのはありませんが。OpenBSDはDESではなくてblowfishを使っているのでしょう。比べて桁違いに長いというあたりが理由でしょう。後者のため、辞書攻撃もそう簡単じゃなくなります。回繰り返すという点を忘れてます。秋葉原で売ってるハードくらいで総当りかできる代物ではないでしょう。ID:8ooWoRTA(1)>>92素人の茶々なんですけど、「秋葉原で売っているハード」にはxilinxとかのPLDは含まれないんでしょうか。xilinxとかのPLDは含まれないんでしょうか。いえ、含んでも一向に構いません。