暗号技術は変わるのか？

**もと国公** · NG

朝日com２００１／２／９朝刊より
■数学の超難問「谷山・志村予想」を米仏チーム完全証明か
　【パリ８日＝大野博人】有名な「フェルマーの最終定理」を解くカギになった数学の超難問「谷山・志村予想」を完全に証明したと、米国とフランスの共同研究チームが８日、明らかにした。チームの一員で、仏国立科学研究センターのクリストフ・ブルイユ研究員（３２）は朝日新聞の取材に「証明は終わっており、米数学会誌への論文掲載も決まっている」と話した。
　谷山・志村予想は、東京大の谷山豊・助教授（故人）と米プリンストン大の志村五郎名誉教授が１９５０年代半ばから６０年代にかけて提示した。「だ円曲線」と呼ばれる曲線の仲間はすべて、数学的に極めて美しい「モジュラー形式」に支配されるという内容だ。予想が提示されて以来、新しい数の理論が生まれ、素粒子論や暗号理論に影響を与えた。
　数学者を３５０年余りも悩ませてきた「フェルマーの最終定理」は９５年、米プリンストン大のアンドリュー・ワイルズ教授によって証明された。このとき、谷山・志村予想の一部は証明された。
　今回の研究チームはブルイユ研究員、米ハーバード大のリチャード・テーラー教授ら４人。予想の中でワイルズ教授が証明し残した部分をすべて解いたという。

現行の楕円理論利用の暗号はどうなるのでしょうか？

**電動ナナシ** · NG

>>25
ここくらい読んでおけよ。EFF と Distributed.net の共同作業で DES を
3 日がかりで解読したときのニュースだよ。
http://www.eff.org/descracker/

**あのにます** · NG

総当たりといっても、passwdに限った場合はkey spaceはprintable characterに限定していいだろ。
そうすると、かかる時間は100分の1くらいかな。チップから設計すると、本当に数時間のオーダーなんだな。
アルファベットと数字に限定しても引っかかるユーザーはたくさんいるだろうから、現実はもっと厳しいな。

秋葉原で売っているハードだけでやった場合はどのくらいまで速くできるんだろう。

25 · NG

>>26
http://www.distributed.net/des/
つーか公式ページにも書いてあったね。
むかし読んだっきりだったから忘れてた。鬱だ。

DES Challenge IIIになると、たったの22時間。
カスタムチップまで作られちゃかなわんなぁ。

**rc64 1000block/day** · NG

でも、どっちにしろ、まともなパスワードつけてたら、
ふつうの一個人レベルではまだDES解読はむりですね
EFF+dnetで一日未満なんで、NSAとかが専用チップ作ってやれば1分以下でできそう
よくつかってるlinuxのshadowは、DES(旧マシンから移行ユーザー)と
MD5(新ユーザーと)が混在してる状態。混在可能なんて、さすがlinux
DESユーザーには矯正的にPW替えさせよっかな
>>27
アイドル辞書使えば一発撃沈
むかしは、あっちこちから辞書集めてきて、全部つなげて sort|uniq やってた
これをjohnに食わして撃沈

**名無しさん** · NG

パスワードはメモするなっていうけど、
メモらないで覚えられるパスワードも危険だよね
指が覚えるまではメモして手元に持っておいて、覚えたら処分する
というのがいいかな、、、

**電動ナナシ** · NG

>>29
昔阪大で jack the ripper か crack 使ったら 20% に満たない crack 率で
よしよしと思っていたが、誰かの意見で車辞書使ったら crack 率が 80% 以上に
なったという話を、昔下条先生がしていた。

**名無しさん@対数の歴史** · NG

>>19
宇宙誕生から現在まで何秒かかっているか考えてみよう。

**名無しさん** · NG

x4096ででいいんだよ。宇宙誕生からの経過時間は1直線だが
並行動作できる環境なら無関係だろ

**おこちゃま** · NG

みなさん、NP完全性と近代暗号をちゃんと勉強しましょう。

＞３３
近代暗号を考えるとき、
宇宙に存在する、陽子の幅を光子が横切る時間をワンクロックとした場合に、現在の宇宙存在する陽子の数の
並列計算素子が、現在考えられている宇宙の寿命の長さだけ計算した場合に

解けないような暗号体系は、計算量増大の指数性を考えれば合理的なビット数で容易に構成できます。

ただ、実用的には、PKIのキーを生成する乱数プロセスの方がセキュリティーホールになるんだよね。

**名無しさん** · NG

結局、現在の暗号技術なんてあと数十年の命なのよ。
http://www.mpt.go.jp/policyreports/japanese/group/tsusin/00623x01.html

**名無しさん** · NG

>>25-26
本になってる

Cracking DES
http://www.oreilly.com/catalog/crackdes/

**たまなし** · NG

>>36
それの翻訳
http://www.genpaku.org/crackdes/cracking-desj.html

**おこちゃま** · NG

>>35
量子暗号は、「物理層」に依存するから、一般用途への適用は難しいよ。
量子キーは、シード発生には使えるかもね。
あと、量子計算機は、結局並列化による計算量のアップなんだけど、
並列化は、素子数を倍にすることによってせいぜい、倍の速度なんだけど
暗号キーは長くすることによって解読時間は指数的に増加するから、
手法そのものが廃れることはないと思うね。

35 · NG

>量子計算機は、結局並列化による計算量のアップなんだけど、
>並列化は、素子数を倍にすることによってせいぜい、倍の速度なんだけど
おいおい、何トンチンカンなこと言ってんだ?
重ね合わせとかテンソル積とかのキーワードくらい
理解した上で発言しろよ。

**ななし!=38** · NG

>>39
なんでいきなりテンソル積が出てくるんだい？
量子力学は専門外だから詳しくはないけど。

どこかでみたが疑似乱数のMersenneTwister（たしか）は
宇宙の量子と同じ数のコンピュータをそろえても数え上げるのが
難しいほどの周期だとか。たしか2の一万乗ぐらいあったはず。

暗号も桁数を増やせばそれぐらいの空間に出来るとおもうのだが。

**もと国公** · NG

暗号文に比較して鍵空間の方がでかいのは実用上問題ありそうですね。

35 · NG

量子コンピュータの状態を表すのに使う。<テンソル積
量子計算のアルゴリズムについて述べている論文を読めばぞろぞろ出てくる。

少なくとも素因数分解や離散対数問題を多項式時間で解く
量子アルゴリズムが発見されているのだから、
RSAやDSAといった暗号方式は量子コンピュータの前では無力。

ただ誤解しないで欲しいのは、量子コンピュータは従来のコンピュータとは
全く別のロジックで動作するものであり、単純に計算が速くできるようになる
わけじゃないってこと。
例えば、NP完全やNP困難といったクラスの問題が量子アルゴリズムを使って
多項式時間で解けるかどうかはまだわかっていない。
# 従来のコンピュータでも未解決なんだけど。

まあ俺も最近興味を持って勉強し始めた趣味の人なんで
偉そうなことは言えんのだが…

**おこちゃま** · NG

>>42
＞素因数分解や離散対数問題を多項式時間で解く量子アルゴリズム

まじですか。
素因子分解は、”計算順序依存性”がないアルゴリズムで並列計算には
向くわけですが、それにしても多項式時間で解くためには

次の除数を求める

の様な処理を、数値の大きさにかかわらず一定で解かねばなりません。
私の理解する量子計算機は、量子状態の重ね合わせにより、一度のオペレーションで
ｎ個の要素に対する処理を行えるものですが、本質的に超並列演算の域を出ません。
ちょうどＤＮＡ計算機や分子計算機の様に超並列性を持つにすぎません。

もし、ホントならば厳密に順序依存性のあるＮＰ完全なアルゴリズム以外暗号に利用できなくなります。

よろしければ、その論文に対するリンクを教えてください。

ちなみに、テンソル積は、大学程度のベクトル解析をやれば誰でも学ぶ概念ですが
どのように絡んでくるのですか？

**ななーしさん** · NG

うへぇ、、
ハイレベルだな、
俺なんかこれは強力な暗号です、ハイそうですか
ってなレベルで導入しちまってるよ。。とほほ

**おこちゃま** · NG

>>42
ちょっと考えてみたのですが、
利用可能な並列素子が”無限”にあるとすると、素因数分解は多項式時間で解けます。
次の因子を求めるための繰り返し演算を一度に並列化できるからです。

しかし、ここに書いた宇宙最大の計算機、つまり素子数が宇宙全体の陽子の数と同じ
でも高々十の８０乗個（エディントンの推定）の素子を持つにすぎませんから
高度暗号の解読では、たちまち素子の数はつきてしまいます。数が大きくても
それは”無限”ではなく高々有限だからです。

それで、つまり量子計算機では、”無限”の多重化ができるということなのでしょうか？

35 · NG

>>素因数分解や離散対数問題を多項式時間で解く量子アルゴリズム
>まじですか。
んー、衝撃的な話題だったんで結構多くの人が知ってると
思ってたんだけど。

で、量子コンピュータの計算能力の秘密は、量子力学の重ね合わせの原理により、
n個の素子(キュービット)で2のn乗個の状態を表すことができ、
しかもその2のn乗個の状態に対する並列演算ができるってこと。
# この状態を表すのにテンソル積が使われている。

ただし、2のn乗個の重ね合わせ状態にある演算結果から
目的の解を取り出すのは結構難しいので、実際に多項式時間での解法が
見つかっているのは素因数分解や離散対数問題のような周期性のある問題だけ。

例えばNP完全問題について、いわゆる総当り的な解法では2のn乗の平方根の
オーダまでしか高速化できないことが示されてるんで、
量子コンピュータを使ってもNP完全問題は多項式時間では解けないんじゃ
ないかっていう意見が多い。

とりあえず日本語のサマリーとしては、
http://www.ipa.go.jp/security/enc/QuantumComputers/contents/contents.html
が良くまとまってると思う。
量子計算の詳しい原理については参考文献を当たってね。

35 · NG

んで、暗号を使う側の立場からすると、現在の1024ビットとかのRSA暗号を
解読できるような量子コンピュータはあと2,30年で実現できるのでは
って予想があるのが恐ろしいところ。
# どこかの国が極秘に量子コンピュータの開発を成功させて
# それを諜報活動に利用するなんて話も夢物語じゃなさそう。

ネット上の商取引とかの信用にも係わることなんで、これはかなり重要な問題。

だから、量子コンピュータでも破られない公開鍵暗号(しかも通常の暗号化・
復号化は従来のコンピュータでできるようなもの)が発明されなきゃならないん
だろうけど、そんなもの実現できるのかなあ……

**anonymous@** · NG

>(しかも通常の暗号化・復号化は従来のコンピュータでできるようなもの)
量子コンピューティングが実用化できたとして、それを応用するには
このあたりが一番難しそうですね。

そのうち1-chip量子暗号デコードユニットなんてのが実用化されるのだろうか。

**anonymous** · NG

もう何が何やら・・・
ロスアラモスにあるとかいう量子コンピュータはどんな姿なのでしょう？

正真正銘の「電子マネー」は、実現出来るのでしょうか？
個人的には実現してほしくないです。なんか恐い。

**おこちゃま** · NG

>>46
読みましたけど、やはり、並列度の仮定として、任意個の重ね合わせ状態
がとれることが前提ですね。

また、テンソル積は、状態空間上のユニタリ変換を表す際に用いられていますが
本質的には重ね合わせられた2^nの状態に対して、一度の処理で超並列演算
が行えるということにつきます。

前述のように量子コンピュータを使わなくても、任意個、つまり無限
の素子を仮定すれば、素因子分解は多項式時間で解けます。

また、演算単位をビットで表さない多値コンピュータにおいて
各単位に、たとえば、光の波長多重の記憶をさせるようなモデル
をとっても、つまり、量子力学を持ち出さなくても全く同じ原理
が適用できます。そもそも、波動の多重可能性に本質があるからです。
（ちなみに、構成上全く同様に、テンソル積を用いてモデル化可能です）

ただし、実際には多重可能な情報量に、現実的な限界があるのです。

この範囲では、計算量理論に本質的な影響を与えると思えないのですがいかがですか？

そもそも暗号の計算量理論では、構成可能なもっとも高速つまり、超並列性を
尺度に考えているからです。計算量理論の観点からは並列度が”無限”でない
限り、そこにブレークスルーはありません。
すなわち、ある大きさの問題までは、多項式時間なのですが、それ以上になると
指数的な時間がかかってしまうからです。

その対比から、提示された量子コンピュータがブレークスルーを与えているとは
思えませんがいかがですか？

**Five** · NG

量子情報については良く分かりませんが、ここのリンクは参考になりそうです。

量子情報に関するリンク集（日本）at ETL
http://www.etl.go.jp/~shiro/link/Q-info-j.html

**おこちゃま** · NG

ちなみに、”はやいコンピュータ”の可能性としての量子コンピュータ
を否定するものではありません。

**おこちゃま** · NG

難しい用語を用いるのは本意ではありませんので計算量の基本的な
考え方の確認をさせてください。因数分解を例にとります。

数値ｘの因数分解は、学校で習ったようにｘにたいして、小さな数字
から、ｘ／２までの数字でわり算を試していきます。
このときおおよそｎビットの数字なら２＾（ｎ－１）回のわり算をすると
考えられます。
つまり、nビットのデータに対して、２＾（ｎ－１）の計算が必要なわけで
データ量すなわちビット数の増加に対して、指数的に計算回数が増えます。
このとき、このアルゴリズムの”計算量は指数的”といいます。
これにたいして、ｎビットの各ビットのｏｒをとる計算はｎ回の計算
で住むわけです。データ量ｎに対して、その多項式たとえば
ｎ＾２＋１，ｎ＾１０＋ｎ＾３＋１など
で計算回数が表せる場合、このアルゴリズムの”計算量は多項式的”
といいます。

”指数的計算量”のアルゴリズムの場合、たった数ビット増やしただけで
飛躍的に多量の計算をしなければなりません。このため、暗号方式
としては、キーが既知であれば、エンコード、デコードには”多項式時間”
のみで、キーが既知でない場合、”指数的時間”が必要な方式が選択されます。
単純に言えば
８ビットの暗号が安全でない場合、１６ビットにすると、キーを知っている人
は、倍の時間がかかるのみですが、知らない人には２５６倍の時間がかる
というようなことです。たとえば、１０２４ビット
の暗号にたいして、倍の

**おこちゃま** · NG

失礼しました。つづき。
１２８ビットの暗号がだめなら、２５６ビットにした場合、デコードには
倍程度の時間がかかるのみだが、解読には３．４０３＊１０＾３８
の時間がかかります。

どんなに高速な計算機があっても、並列度が”有限(どんなにおおきくても)”または、
計算速度が有限である限り、同じアルゴリズムの鍵長を少し長くするだけで対処できて
しまうのです。

これが本質的なポイントになります。

35 · NG

んー、なんか注目する視点が違っているような気がしてきた。

確かに、単なる並列演算じゃないかと言われればそうなんだが、
量子コンピュータの場合、その計算能力が素子数に応じて指数関数的に
増えていくってのが重要な問題。

1024ビットの暗号が解読されるようになってしまったから2048ビットにしようって
考えても、倍の素子数を持つ量子コンピュータが開発されればあっさりと
解読されてしまう。
今までのように、何ビット増やすと解読にかかる時間は10の何乗倍に
なるから事実上解読不可能ですよ、ってなことが言えなくなるから
暗号の安全性が保証できなくなる。

実際、数千キュービット級の量子コンピュータを実現できるような
素子についての研究や、ノイズに対処するための量子誤り訂正符号の研究
などが活発に行なわれているから、実現可能な量子コンピュータの限界が
見えるのはかなり先になると思う。

暗号のビット数なんてころころ変えるわけにはいかないから
(特に電子署名とかは何十年も残る可能性がある)、
今現在解読が無理でも近い将来解読が可能なるだろうって言われる
暗号を実用にはできないでしょ。

それに、通常の暗号化・復号化は多項式時間でできるからといって、
いくらでも暗号のビット数を伸ばしてよいという訳にもいかない。
電子マネーで決済しようとしてカードを入れたら、チェックが終わるのに
30秒かかりました、では実用になるわけないでしょ。

**nobody** · NG

なんか一部、暗号そのものが嫌いな人が必死になってる印象があるなぁ。

35 · NG

>>56
いやいや、別に俺は暗号を否定しようなんて思ってないよ。
むしろ暗号は大好き。
んで、量子計算でRSAが破れるっていうエキサイティングなネタを肴に
いろいろ思考実験してるだけ。
どうせ、量子コンピュータの実現までは少なくとも10年以上かかるんだから
ゆっくりまったりやりましょ。

**おこちゃま** · NG

釈迦に説法かとは思いますが。

>電子マネーで決済しようとしてカードを入れたら、チェックが終わるのに
>30秒かかりました、では実用になるわけないでしょ。
あくまでポイントはデコードと、解読のアルゴリズム上本質的な速度差
です。一方が多項式的で、他方が指数的なのが効いてくるのです。

解読が速くなったから鍵を長くしたのであれば、そのときデコード
は、”もっと比較にならないくらい”速くなってるから問題ないのでは？
その際も、解読には大がかりな計算が必要で、デコードはICカードで
可能なはずです。

あと、現在の暗号の鍵長は、
「ある期間に登場する電子計算機を仮定して、解読にかかる費用」
を元に決めるのが通常です。宇宙が終わるまでに解かれない暗号も
構成可能でが、一般的には解読に要する費用に、解読の結果の利益が
見合わない水準に設定されます。
”絶対安全”、”破られない”は古い考え方です。安全とコスト、実
用性のバランスに着目するのが近代暗号の考え方です。

ただ、４０ｂｉｔＲＳＡを使っているシステムが、何十年か後にちょうど
２０００年問題のような陳腐化に直面することなどは否定できません。

最後に、超並列計算機でも解けない、つまり、並列不能な暗号もあります。
ただ、いまのところニーズがないために用いられていません。

**anonymous** · NG

>>58
RSA なら 40bit じゃなくて 512bit だよね、という突っ込みはいいとして。

詳しい人がここにきているみたいだから聞きたいんだけど、実際のところ今現在
使われている暗号の強度はどうなの？。DES は風前のともし火だとしても、
RSA 1024bit や AES についてはどのくらいなの？

400bit の素因数分解に要する計算能力は 5000MIPS/year だって話だけど、
これは量子暗号の場合どのくらいの素子数に相当するの？。

結局のところ、量子計算機時代に備えて、今の暗号技術の寿命を知っておかないと
システムの寿命が見えないからね。理論的な話よりもいつまで暗号化データの
安全性を確保できるって方が興味あるなあ。

35 · NG

>>59
量子コンピュータの計算能力を今までの尺度(MIPSとか)で
計るのはあんまり意味が無いと思う。

2次ふるい法っていう方法で 400bit の数を素因数分解したときに要した
計算能力が 5000 MIPS・year だったってのは有名な話。
でも、N bitの数を2次ふるい法で素因数分解するときの計算量は
exp(a*(N log N)^(1/2))のオーダだそうだから、
1024 bitの数を素因数分解するのは今のコンピュータが何千倍も
速くなったとしても事実上無理だねってのが従来の議論。

でも量子計算なら、N の何倍個かのキュービットを持つ
量子コンピュータさえ用意できれば(といってもそれが一番難しいんだが…)、
N の多項式時間で素因数分解ができるようになる。
つまり、bit数が2倍になっても高々数倍の時間で計算ができるってこと。

じゃあ、実際に 1024 bitの数を素因数分解できる量子コンピュータは
いつ出来るんだって言われてちゃんと答えられる人は居ないと思う。
あと10年で出来るなんて強気な意見の人もいれば、
どう頑張ったって少なくとも21世紀中は無理でしょって言う人もいる。
なんせ、量子コンピュータの研究なんてほとんど歴史が無いからね。
でも、そのわずかな時間で数キュービットの量子コンピュータの実現に
成功してるってのは注目すべき点。
個人的にはUNIX最後の日(2038年1月)よりずっと近い未来の話になるような気がする。

詳しくは、上のほうにあるリンクをたどってね。

ちなみに、暗号関連で今のところ知られている量子アルゴリズムってのは
素因数分解や離散対数問題ぐらいなので、秘密鍵暗号についてはまだ大丈夫。
でも、暗号化を行なう関数の構造によっては、あっさり破られるものが
出てくる可能性は否定できない。

**名無しさん＠１周年** · NG

興味あるのでage

**ラーメン大好き＠名無しさん** · NG

**暗号ってナガーク使えてナンボでは？** · NG

暗号の流通っていうと、すぐアメリカがしゃしゃり出てくるけど、
ヤパ、こういうのは政府とかで囲ってコソ～リと研究した方がいいのかもネ。
論文発表するより、極秘でやる分野じゃない？

本質的に、暗号は解けるものなんだから。今は解読時間がとか費用がとかいってても、
明日、違うロジックが考案されて、あっさり解けるかもしれないし。

暗号の利便って、考案から解読までの時間のギャップが作り出すものなんだから。
考案している方が、解読研究してる方に時間をプレゼントするのはナンセンスだと思う。

そういえば、機能メモリってどうなったの？スレ違うけど。

**y^2=x^3+ax^2+b** · NG

>>63
何故オープンな規格の暗号じゃないと信用できないかっていう事を
わかっていないね。

**ちゅりん** · NG

>>63
共通鍵方式で、暗号/復号化鍵に本当の乱数を用いれば
解読は不可能なはずでは?

**知ったか追放週間** · NG

>>64
具体的に書かない知ったか糞レスは逝ってよし。

**rijndahl** · NG

>>66
しったか、というのは、65とか63のこと？
たしかにAESやNESSIEで敗れ去った暗号を使おうとする
人はあんまいないだろうね。

**名無しさん** · NG

>>67
実は、AESで採用した暗号は、NSAが裏口を見つけたやつだったりして

**y^2=x^3+ax+b** · NG

>>63
>本質的に、暗号は解けるものなんだから。
天文学的な時間が許されればね。

**tnn** · NG

なんかfjっぽいスレだねぇ。
そんだけ。

**リスク計算** · NG

IPAが募集してるのって、むむむ、AESなんぞ怪しいから
我が大日本帝国独自のを作るのだー　という話なんでしょうか？
すんません厨房なもんで詳しいかた、教えてください。

でも、選ぶ側が日本の大学や企業の先生方だとすると、大変失礼
だけど、ちょっと心配だなぁ。
やっぱ世界中の奇人変人にうまいものいっぱいくわせて作らせて、
評価もさせて、ってのが一番の気がする。

>>70
fj歴も長いけど、やっぱでちゃうのかなぁ。

**非決定性名無しさん** · NG

暗号素人なのですが、一度専門家に聞いてみたかった。
国際情報科学研究所のカオス暗号って、とんでも？
http://www.iisi.co.jp/jp/index.html

**チカンと天地** · NG

ﾊｧﾊｧ

**sage** · NG

パイコネ変カンﾊｧﾊｧ

**名無しさん＠1.544MHz** · NG

>71
決して詳しくはないけど．．

日本では、学が産に利益を与えられるような話でないと
未だに官がGOを出さない（プロジェクトが進まない）からでは？
米だって、冷戦時代ではそれが当たり前だったのだし。
Rijndahlが怪しいということでは無いと思います。

> やっぱ世界中の奇人変人にうまいものいっぱいくわせて作らせて、
> 評価もさせて、ってのが一番の気がする。
同感です。

**ラインダール** · NG

AESの最終決定って揺らいでいるの??

**anonymous@**f071086.ppp.asahi-net.or.jp · NG

今のところ、楕円暗号が理論的に最強です。

35 · NG

息の長いスレやね……
なんか、共通鍵暗号と公開鍵暗号の話がごっちゃになってる気がするけど…

>>72
いろいろ探しても、実際の暗号化に用いる「カオス」を生成させる数式を
見つけられなかったんだけど、どこかに書いてる?
具体的なアルゴリズムを示さない暗号なんて誰も使いたがらないから、
それを隠している暗号なんて、トンデモって言われてもしょうがないと思う。
まあ、ほとんど情報がないから、これはあくまで個人的な印象だけど
弱鍵だらけで結局まともな暗号は作れなさそうな気はする。

>>77
「理論」上での強さだけなら量子暗号が最強でしょ。
なんせ解読どころか傍受すら不可能なんだから。
…ってのは冗談だけど。(笑

**anonymous** · NG

表情を使った暗号通信
http://ununununu.hoops.ne.jp/other/tm.jpg

**名無しさん** · NG

認証技術の方はどうなっているの？

例えば、最近は高速道路に乗るときに電波飛ばせばいいみたいだけど、
あういうのは偽電波で簡単に騙せるもの？

**ななし** · NG

>>80
認証は、ハードなレベルにになると結局は生体認証
とかいうお話になっちゃう。

って、そういうんじゃなくて CA 方面のお話?

**anonymous@**research02.gate.nec.co.jp · NG

＞また、演算単位をビットで表さない多値コンピュータにおいて
＞各単位に、たとえば、光の波長多重の記憶をさせるようなモデル
＞をとっても、つまり、量子力学を持ち出さなくても全く同じ原理
＞が適用できます。そもそも、波動の多重可能性に本質があるからです。
＞（ちなみに、構成上全く同様に、テンソル積を用いてモデル化可能です）

これは違うよ。

**暗号の権威って？** · NG

>>63
何かの教科書に、暗号に関する本当のトップレベルの研究はNSA
の中で行われていて、一般には公開されない、と書いてあったんだけど、
これって本当？

**ななし** · NG

>>83
現状を見る限りは大嘘。

**暗号の権威って？** · NG

>>84
現状って、どういう意味？

**ななし** · NG

AES の選定過程とか。

東大 · NG

ＩＤ・・・教えない
パス
1233422-006067-AZEtypeRoop-C-0558621356-circleMAX-UniveTokyo
侵入してみろ
まずはゲートから探せますか？
貴方の実力が試せます

**侵入者** · NG

侵入しました。

**age** · NG

**ちょっとした素朴な疑問** · NG

話が変わるけど､通常UNIXパスワードはDESによって暗号化されいますが､何故OpenBSDは
DESではなくてblowfishを使っているのでしょう。

**あのにます。** · NG

>>87
暗号の自慢はいいから、大学全体のセキュリティを考えてよ。
昨年の中国からの中央省庁Crackingは、あのノーベル賞が取
れない東京大学が踏み台にされたんでしょ。

**名無しさん＠ＸＥｍａｃｓ** · NG

>>90
> 話が変わるけど､通常UNIXパスワードはDESによって暗号化されいますが､

最近だとあんまり『通常』ってのはありませんが。

『伝統的』のが正確かな？

> 何故OpenBSDはDESではなくてblowfishを使っているのでしょう。

詳しくは OpenBSD の Site で拾える USENIX paper でも少し触れら
れてますが、

1. アルゴリズム的に見て DES よりはるかに強力
2. 一つの鍵をセットアップするのに必要な時間が DES (に限らずた
ぶん既存のあらゆる共通鍵アルゴリズム) と比べて桁違いに長い

というあたりが理由でしょう。後者のため、辞書攻撃もそう簡単じゃ
なくなります。

ついでに、昔の書き込みで DES password の cracking に関して

『key space を printable character に限定できるからまともな
DES を破るより速いだろう』

てな議論がありましたが、しょせん、(96/128)^8 ではざっと 1/10
程度になるだけだし、何より伝統的な UNIX password は DES 処理を
25 回繰り返すという点を忘れてます。

とてもとてもそこらの PC や秋葉原で売ってるハードくらいで総当り
かできる代物ではないでしょう。

**age** · 2001/07/08(日) 09:23

上げます

**anonymous** · 2001/07/10(火) 09:16

>>92
素人の茶々なんですけど、「秋葉原で売っているハード」には
xilinxとかのPLDは含まれないんでしょうか。

**名無しさん＠ＸＥｍａｃｓ** · 2001/07/11(水) 14:17

>>94
> 素人の茶々なんですけど、「秋葉原で売っているハード」には
> xilinxとかのPLDは含まれないんでしょうか。

いえ、含んでも一向に構いません。

どの程度のクロックの PLD がいま秋葉原で買えるか知りませんが、思
いっきり高めに見積もって 1GHz としましょうか。

で、PLD だとうまいこと logic を組めばたぶん 17～8 step で DES
algorithm が実装できるでしょう。

あとは単純な計算で

$ bc
bc 1.05
Copyright 1991, 1992, 1993, 1994, 1997, 1998 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
96^8 * 25 / 2 / 10^9 * 18
1623126546

つまり、一つの PLD で一つの伝統的 UNIX password を総当りするの
にかかる期待値がざっと 16 億秒ってことです。

もちろん大量に PLD を使えばスピードアップできますが、EFF の DES
Cracker のレベル (平均 4.5 日で一つの鍵を破れる) に達するだけで
もかなりの難事でしょう。

**anonymous** · 2001/07/12(木) 06:17

なるほど。その仮定でも、ざっと4000個並列しないといけない計算になりますね。
現状では注意深く管理された特定のアカウントに対する総当り攻撃は、
「秋葉原で買ったパーツでも不可能ではないが、組織的にやらないと難しい」
という認識でよさそうです。

しかし現実には、ひとつのアカウントがクラックされるだけですべてのアカウントが危険にさらされるケースがありますよね。
その場合、たまたまalphanumericなpasswordをつけている人物がいれば、上の仮定では128個並列で十分なようです。
これならの私怨の範囲でもクラックできるかもしれません。

個人レベルの攻撃というのを、秋葉原で調達可能なハードを用いて平均的な個人の収入と作業時間で
実現可能な攻撃手段と定義します。DESによるパスワードハッシュがもれた状況は、現状で
「組織的な解読者を想定した場合、安全と言えるアカウントはひとつもない」
「もしも全員が注意深くパスワードを管理していれば個人レベルでは安全」
「ひとつでもalphanumericなアカウントがある場合は、個人レベルで解読を許す可能性がある」
「ひとつでも辞書攻撃を許すアカウントがある場合は、直ちに危険である」
という認識でよいですかね。
＃残念ながら現実には一番最後のケースが妥当かもしれません。

**名無しさん** · 2001/07/12(木) 06:44

まず /etc/passwd を手に入れる。
１人位アカウント名とパスワードが同じのドキュソがいるもんだから
順番に試す。
ログインに成功したらセキュリティホールのあるプログラムを
探して実行しroot権限を得る。
めでたしめでたし。

**97はバカ** · 2001/07/12(木) 06:54

はぁ？
そんな古典的なﾊｸを実行するなんて、相当な幼児だね。ﾌﾟﾌﾟﾌﾟ

**ななし** · 2001/07/12(木) 21:02

>>97
最近は、password crack なんぞをせずに、各 daemon の buffer overflow
等による穴を直接ついて root 権限を得るという crack が普通です。

**名無しさん＠ＸＥｍａｃｓ** · 2001/07/16(月) 13:43

>>96
> なるほど。その仮定でも、ざっと4000個並列しないといけない計算になりますね。
> 現状では注意深く管理された特定のアカウントに対する総当り攻撃は、
> 「秋葉原で買ったパーツでも不可能ではないが、組織的にやらないと難しい」
> という認識でよさそうです。

まぁ、そんなところでしょう。

ただ、Password cracking みたいに変換後の結果そのものが分かって
いる場合ならともかく、そこそこ汎用な暗号破りを実現しようと思う
と、上の規模で並列させたチップにうまく仕事を割り振る (特に false
positive を効率的に排除する) のが結構難しい問題になります。

なので、現実に PLD で EFF DES Cracker なみの性能を持つシステム
を作ってみせられたとすれば、それはいまでもそこそこ評価できる研
究成果と言える気はします。

♯ご存じかもしれませんが、 EFF DES Cracker は PLD や FPGA では
♯なく custom IC で作られてます。

> という認識でよいですかね。

でしょう。

まぁ、いまどき password crack は流行らないというのも事実でしょ
うが、だからと言って password などどうでもいいというわけでもな
いでしょうし、さっさと MD5 なり Blowfish なり、より大きいエント
ロピーを扱える password system に移行するべきでしょうね。

**age** · 2001/08/01(水) 12:23

age

**ななし** · 2001/08/24(金) 07:20

01/09/19 14:45

東大とかにある円周率計算の世界記録を作れるような
スーパーコンピューターだったら、暗号の解読、たとえば
パスワード８文字をやぶるのなんて一瞬ではないだろうか？
ハッシュされたパスワードを入れると、元の文字列の
候補が出力されるようなWebページを作ってサービス
すればよいだろう。

**anonymous@** TCN-DHCP2.tcn-catv.ne.jp · 01/09/19 16:23

ガラスの中の液体に色とりどりのゲルが浮いていて、それに光を当てて
反射した光の模様をもとに暗号を生成するっていう話は、今回のテロ事件で
破綻したの？
でも解読できない暗号を作るのを禁止しようってのは、誰がはじめに実践するかが
むつかしそうだね。

01/09/25 16:54

>>103
> 東大とかにある円周率計算の世界記録を作れるような
> スーパーコンピューターだったら、暗号の解読、たとえば
> パスワード８文字をやぶるのなんて一瞬ではないだろうか？

んなわきゃーないって。スーパーコンピュータゆーてもハイエンド機
でようやく二桁 TFLOPS に手が届こうか、って程度なんだから、一瞬
(を 1 分以内とかに拡大解釈したとしても) なんてとてもとても。

>>104
> ガラスの中の液体に色とりどりのゲルが浮いていて、それに光を当てて
> 反射した光の模様をもとに暗号を生成するっていう話は、今回のテロ事件で
> 破綻したの？

この『ゲルで云々』という話は不勉強で聞いたことがないんですが、

> でも解読できない暗号を作るのを禁止しようってのは、誰がはじめに実践するかが
> むつかしそうだね。

現状ですでに

・絶対解読できない (でもちょっと使い難い)
・特性がかなり理解されており十分使い易い

という二種類の暗号があるので (共通鍵系の話ね)、理論面/実践面ど
ちらの意味から見ても、新しい原理に基づく暗号を作るというのは、
(研究的興味を除けば) あんまり意味のある話ではなくなってるとも言
えます。

もちろん、公開鍵系に関しては選択肢の少なさという不安があるので、
もっと多彩な alternatives が欲しいところではありますが。

**nanasi** · 01/09/25 21:38

>>105
んじゃ、量子コンピュータ向けの暗号理論って意味ないの?

**名無しさん＠ＸＥｍａｃｓ** · 01/09/26 13:34

>>106
> んじゃ、量子コンピュータ向けの暗号理論って意味ないの?

意味ないです (と言い切ってしまおう)。

万一いま研究されてる量子コンピュータが実用化されることがあった
としても、それでダメージを受けるのは素因数分解/離散対数の困難性
に基づく公開鍵暗号系だけだから共通鍵系にはなんら影響ないし、よ
しんば共通鍵系の安全性にまで影響を与えるような量子コンピュータ
(これはもう非決定的テューリングマシンそのものなのだが) の原理が
発明されたとしても、最後の砦は残るわけだし。

きょうび、ほんとに大事な通信を行ないたい相手毎に数 GB とかのサ
イズの onetime pad を共有しておくというのは、それほど難しい話で
もなくなっちゃってるからね。

**anonymous@** h143-246.tokyu-net.catv.ne.jp · 01/09/29 01:36

そもそも量子コンピュータって、O(N)のNP問題をP時間で解くのに、
O(2^N)のハード使ってない？

**名無しさん＠ＸＥｍａｃｓ** · 01/10/04 13:31

量子コンピュータって実は良く知らないんだけど、1 qubit で 0 と
1 の 2 状態の重ね合わせを表せるってことだから、N qubit あれば
N bit の素因数分解ができるということではないの？

**名無しさん** · 01/10/14 01:06

>>107
>> んじゃ、量子コンピュータ向けの暗号理論って意味ないの?
> 意味ないです (と言い切ってしまおう)。

他の人に誤解されるかもしれないから「共通鍵暗号については意味ないです」って言ってちょ。
(もちろん、後の文を読めば >>107 さんが共通鍵暗号のことを言ってるのは明らかなんだけど。)

で、量子コンピュータができても共通鍵暗号は破れないって意見には同意。
量子コンピュータは素因数分解や離散対数問題は解けても
NP完全問題は解けないって意見が支配的だしね。
だから、ナップサック問題(これもNP完全問題)を利用した公開鍵暗号に
再び注目が集まっているわけで。(量子公開鍵暗号ってやつね)

>>109
あまり詳しくないんだけど、Shorのアルゴリズムって計算途中の情報を格納する
必要があるから、全部で3N qubitぐらい必要じゃなかったっけ?
どっちにしろ、Nの定数倍ってのは間違いないけど。

**名無しさん＠ＸＥｍａｃｓ** · 01/10/19 15:38

>>110
> >> んじゃ、量子コンピュータ向けの暗号理論って意味ないの?
> > 意味ないです (と言い切ってしまおう)。
> 他の人に誤解されるかもしれないから「共通鍵暗号については意味ないです」って言ってちょ。

んー、誤解されるのは実は望むところ、というか。

いや、だって、量子コンピュータなんてまず実用化されないでしょ。
NP 完全問題を多項式時間で解くよな化物は当然として、いま研究され
てるやつですら。

♯ただ、>>109 でみずから
> 量子コンピュータって実は良く知らないんだけど、
♯と言ってる通り別に確固とした根拠がある訳じゃないからここ突っ
♯込まれても困るんだが。

もちろん研究としての意味合いは十分あると思うし、それを否定して
るわけじゃないんだけど、研究的トピックがすべて実用化できるとい
うものならば、今ごろハイエンドなコンピュータは液体窒素 (だったっ
けか?) の中で CPU が動く醍醐世代機になってなきゃおかしいわけで。B-)

んで、特に暗号の場合には使えてなんぼ、という感が強いので (なに
せ、これほど綺麗に理論が実践に繋がってる分野って他にあんまりな
さげだし)、実用化できない = 意味がない、という印象が (個人的に
は) 強いんでしょうね。

> だから、ナップサック問題(これもNP完全問題)を利用した公開鍵暗号に
> 再び注目が集まっているわけで。(量子公開鍵暗号ってやつね)

えーと、でも knapsack って LLL アルゴリズムとかいうやつのために
非現実的なサイズの鍵を使わない限り破られてしまうということが一
般に示されてるんじゃなかったでしたっけ。

この辺も聞きかじりなもんであれですが。

あ、量子コンピュータを使えばいま非現実的サイズな鍵が現実的に使
えるようになる、という線はあり得るのか。

**anonymous@** Ctcur7DS16.iba.mesh.ad.jp · 01/10/30 08:18

あげ

**MSDRM破られる** · 01/10/30 08:51

http://cryptome.org/ms-drm.htm

**unknown** · 02/01/11 05:45

スレ存在証明age

◆RUwjICBI · 02/01/16 17:31

誰がために心をなやまし、
http://pc.2ch.net/test/read.cgi/sec/994847789/203

＿ · 02/01/19 02:28

なにやっとんねん。

**unknown** · 02/01/29 21:12

SCIS2002あげ

**名無しさん＠crypt** · 02/02/18 01:05

あげ

**anonymous@** p803258.kyotac00.ap.so-net.ne.jp · 02/02/21 04:35

age

b · 02/04/13 20:52

なんか0101100とかに暗号化して日本語に解読できサイトありませんでした？
知ってる方はリンクキボンヌですー。

**anonymous@** nttkyo065056.adsl.ppp.infoweb.ne.jp · 02/07/05 01:38

カオスって製品化されてるんですね。売ってました。
エシュロンでも解読不可能だと言ってました。

**名無しさん＠ＸＥｍａｃｓ** · 02/07/05 10:38

> カオスって製品化されてるんですね。売ってました。

IISI の？

だったらずいぶん前から売ってると思うけど。

> エシュロンでも解読不可能だと言ってました。

いま使われているたいていの暗号は『エシュロンでも解読不可能』な
んだけどなぁ。

まぁ、ブロック暗号の CBC モードすら知らなかったという話もあるん
で、IISI ならしょうがないか。

あの · 02/08/16 15:15

イイ

**ひよこ名無しさん** · 02/08/16 15:22

そんなことより　聞いてくれよおっちゃん
このサイト面白いぞ　小一時間ワラタ
http://www.ogaki-tv.ne.jp/~zeus/

**演技師（へっぽこ** ◆enGI/www · 02/08/16 16:43

そんなことより

確実な素数判定のアルゴリズムができたらしいじゃないですか。
インドってすごい。