アカウント名:
パスワード:
＃もちろん実際にはそんな単純な話では無いでしょうが。あくまで例として。 ＃なお、6Gflopsという値は「倍精度」の場合で、単精度ならこの倍になるそうです。
ハッシュ計算を1000回、10000回の浮動小数点に相当させる根拠はいったい何？
ハッシュ計算に浮動小数点演算はまったく関係ありません。
＃ただ、また勘違いがあるかも知れませんけど、普通は浮動小数点計算より整数の計算の方が速いでしょうから、 ＃小数点演算でないのならさらに問題が大きくなるかも、とも思います。
ピーク性能まんまで出るわけではないですよ。
＃要は本家の指摘にあったという「2^39は現実的」というのが、実際どの程度現実的なのか単純計算で試してみただけでして(^-^;;;
仮にSHA-1が1ハッシュ値あたり1000回浮動小数点演算を行っているとしても、 単純計算で549755813888÷((6×1000000000)÷1000)=約91626秒あればいいことになります。 ちなみに1日は86400秒ですので、91626秒=1日と1時間27分6秒です。 SHA-1が10000回浮動小数点演算を行うとしても、約916260秒=10日と14時間31分。 これを非現実的と感じますか?
「非現実的と感じますか?」に至るまでの展開は 「SHA-1が1ハッシュ値あたり1000回もしくは10000回の浮動小数点演算を行っている」 という仮定を前提にしているようですが、 まずその仮定がどこから出てきたのか、 もしくはどれだけの現実性があるのか示していただかないと困ります。
eJapanのために策定されたガイドラインCRYPTORECでは、既にSHA-1の寿命は折込でいてSHA-256にスライドできるようになっているので、これから先にSHA-1が寿命が尽きたとしても大丈夫なロードマップは仕様上きちんとできているはずです。あまり驚かないように。 [srad.jp]
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
クラックを法規制強化で止められると思ってる奴は頭がおかしい -- あるアレゲ人
あわてる必要は無い (スコア:-1, フレームのもと)
Re:あわてる必要は無い (スコア:2, すばらしい洞察)
今日明日どうなる問題でもありませんが、
移行の準備を始めるべきです。
ある本家コメント [slashdot.org]によると
2^69 はまだ天文学的な計算量ですが、2^39 なら現実的だそうです。
(電子的に) 署名したこともないものを署名したことになっても、
ふつうの人なら今のところ損することはあまりないはずですが、
ほんとにヤバいことになってからでは遅いので、さっさと代替案を決めなくては。
Re:あわてる必要は無い (スコア:1)
なんだかたいしたことない数字に見えるかも。
暗算できるかも。
＃暗算したところでこれと言った意味は見出せないけれども。
----- 愚者の万能薬本舗
Re:あわてる必要は無い (スコア:2, 興味深い)
ちなみに1日は86400秒ですので、91626秒=1日と1時間27分6秒です。
SHA-1が10000回浮動小数点演算を行うとしても、約916260秒=10日と14時間31分。
これを非現実的と感じますか?
＃もちろん実際にはそんな単純な話では無いでしょうが。あくまで例として。
＃なお、6Gflopsという値は「倍精度」の場合で、単精度ならこの倍になるそうです。
Re:あわてる必要は無い (スコア:2, すばらしい洞察)
仮定が不自然なら、以降の計算はどんなに厳密でも無意味。
そもそも浮動小数点演算と整数演算と論理演算と、演算の質が違うと思うのですけれども。
1から1,000,000,000までの整数を全て足しなさい、と言われて
1秒で5,000,000,005,000,000,000と答えたら999MIPS？
という例はちょっと違うか……。
うーん。
Re:あわてる必要は無い (スコア:1)
計算の精度と言うなら、そもそもSHAのハッシュ関数の内容を知らない時点で論外です。
Re:あわてる必要は無い (お詫び) (スコア:1)
お詫びして訂正いたします。
Re:あわてる必要は無い (スコア:1, すばらしい洞察)
Re:あわてる必要は無い (スコア:1)
＃ただ、また勘違いがあるかも知れませんけど、普通は浮動小数点計算より整数の計算の方が速いでしょうから、
＃小数点演算でないのならさらに問題が大きくなるかも、とも思います。
Re:あわてる必要は無い (スコア:0)
Re:あわてる必要は無い (スコア:0)
浮動小数点演算が関係ないなんて言い切れないでしょ。そもそも
「ハッシュ関数は整数演算のみかならるもの」なんて定義はどこにも
ないわけだし。
「有名どころのハッシュ関数では、浮動小数点演算は使用されていない」
なら別にいいけど (ほんとかどうかは知らんが)。
Re:あわてる必要は無い (スコア:0, フレームのもと)
浮動小数点では実装によって答が違ってくるだろ。
そんなものハッシュ関数になるか。
ハッシュ関数の意味を勉強してから出直してこい。
Re:あわてる必要は無い (スコア:0)
IEEE の規格しらないの?
別に知らなくてもいいけど。
Re:あわてる必要は無い (スコア:1)
ピーク性能まんまで出るわけではないですよ。
計算やによるでしょうが、単純なループじゃないのに一桁下くらいの性能だったらかなりチューニングできてるほうじゃないでしょうか。
# 雑談サイトなんだから脱線しよう
Re:あわてる必要は無い (スコア:1)
というか、厳密な計算かという話であれば、そもそもSHAのハッシュ関数の内容を知らないあたりで既に問題外ですから(^-^;
＃要は本家の指摘にあったという「2^39は現実的」というのが、実際どの程度現実的なのか単純計算で試してみただけでして(^-^;;;
Re:あわてる必要は無い (スコア:1, すばらしい洞察)
Re:あわてる必要は無い (スコア:1)
ただ、#695090 [srad.jp]でも書きましたけど、厳密な計算かと言われると、そもそもSHAのハッシュ関数の内容を知らない時点で、既に論外です。
調べてもよく判らなかったので、目安のつもりで「10回100回ってことは無いだろうし、1000回くらいしてるだろうなぁ」程度の感覚で仮定しています。
そのあたりのことも書いておくべきでした。
Re:あわてる必要は無い (スコア:2, 参考になる)
> 1000回くらいしてるだろうなぁ」程度の感覚で仮定しています。
SHA-1の実装例はRFC3174で公開されていますのでそれを見れば判ると思います。
フルスペックのSHA-1は1ブロックあたりの処理で、撹拌のような処理を80回繰り返してます。
RFC3174でいうところのSHA1ProcessMessageBlockの中です。
平均的に1回の撹拌で
テーブル引き 5回、 rotate 2回、 shift 2回、 and 7回、
or 3回、 xor 3回、 加算 4回、 減算 3回
およそこれくらいはこなさなければならず
これを80回繰り返して1000回に抑えるのは非現実的だと思います。
ただし、通常の実装はそれを整数演算でやっていますので
かかる時間を浮動小数点演算換算で1000回から10000回分の範囲に収めることは可能です。
単純に作っても3GHzのP4で毎秒百万回くらいは出せることから
うまくアセンブラで書いてさらにHTを利用して同時に複数スレッド処理をすれば
毎秒6百万回に近付けることが可能かもしれません。
しかしその速度を出す実装はまだ見たことがありません。あるかどうか分かりません。
結果的にsamayoiさんの結論は実際の速度と近くなるという偶然が起きてますが
その前提となる演算回数が1000回という仮定は間違いだと思います。
そもそも必要な計算が1000回で済むようなアルゴリズムならMD5と同レベルです。
> そのあたりのことも書いておくべきでした。
計算回数が分からないなら、余計なことは書かず、
計算回数の話を素っ飛ばして「毎秒6百万回のSHA1処理ができる」と仮定して
2^39回なら91626秒と結論付けてしまった方が良いのではないでしょうか。
「浮動小数点演算1000回」という記述は
せっかく巧く描けた蛇の絵に足を描き足すようなものです。
Re:あわてる必要は無い (スコア:0)
>うまくアセンブラで書いてさらにHTを利用して同時に複数スレッド処理をすれば
> 毎秒6百万回に近付けることが可能かもしれません。
強調部のところで躊躇してしまいました。
なんでこうなるのでしょうか？HTに意味があるとは思えないんですが。
Re:あわてる必要は無い (スコア:1, 参考になる)
前回のストーリーに付けられたコメントからですが、こういうことですよね。