解読に数十万年かかるとされた暗号、148日で解読される 77
ストーリー by hylom
暗号は破られるものですが 部門より
暗号は破られるものですが 部門より
Wingard 曰く、
解読に数十万年かかるとされた278桁の暗号「ペアリング暗号」の解読に、情報通信研究機構や九州大、富士通研究所のチームが成功した（MSN産経ニュース）。
コンピュータ21台を使用し、148日で解読に成功したとのことだ。チームは「ペアリング暗号はもろく、情報通信でデータを暗号化する鍵として使うには、より大きな桁数が必要と分かった。安全な暗号や適切な鍵の交換時期を見極めるのに役立つ」としている。
より詳細な情報 (スコア:2, 興味深い)
ＮＩＣＴ・九大・富士通研究所、次世代標準の「ペアリング暗号」で２７８桁長の解読に成功：ITpro Active
http://itpro.nikkeibp.co.jp/article/ActiveR/20120618/403386/ [nikkeibp.co.jp]
根本的な問題のようで、大々的に使われる前に発覚したのは幸いだったということなんでしょう。
詳しい人教えて？ (スコア:1)
これはペアリング暗号に使われている（特殊な形式の）離散対数問題を高速で解くことに成功したのか、あるいは一般的な離散対数問題を高速で解いてしまったのか、どっちなの？
後者だったらペアリング暗号だけの脆弱性の問題ではなくなってくるのでは？
Re:詳しい人教えて？ (スコア:5, 参考になる)
資料を見る限り、前者で合っていると思います。
ちなみに離散対数問題は、一定の式においては解読可能であることが既に明らかになっています。PS3が不適切な実装を行ったECDSAを解読され、えらい目にあったのは記憶に新しい所。
Re:詳しい人教えて？ (スコア:2)
いっぽうロシアは？ (スコア:1)
Re:いっぽうロシアは？ (スコア:4, すばらしい洞察)
278桁のベアリング暗号については145日毎に強制変更する運用を開始した？
145日以内に秘匿する意味がなくなる情報しか流してはいけないという
運用にしなくてはダメなんじゃないですかね？
Re:いっぽうロシアは？ (スコア:2)
紙に鉛筆で記載するよう指示した。
では、ないでしょうか。
Re:いっぽうロシアは？ (スコア:1)
暗号を279桁にしたのでは。
Re:いっぽうロシアは？ (スコア:1)
ベアリングか...潤滑油を入れるんじゃないかな?
M-FalconSky (暑いか寒い)
Re:いっぽうロシアは？ (スコア:1)
Re: (スコア:0)
ロシアは寒いから、油でいいと思う。グリスだと固まってしまいそう。
Re:いっぽうロシアは？ (スコア:1)
＃今は大丈夫かな、モービル1とかいった自動車用の潤滑油の宣伝を思い出した
Re: (スコア:0)
シーザー暗号に移行し、「解読したら粛正するぞ」と言っておけばそれでいい。
Re:いっぽうロシアは？ (スコア:1)
それをツァーリ暗号と呼ぶ、わけない
なぜ解読できたのでしょうか？ (スコア:1)
解読に必要な時間の期待値は、予測できそうなものですが。
期待値としてはやはり数十万年で、今回すぐに解読できたのは偶然なのでしょうか？
（もしそうするなら、どんな勝算があって解読に着手したのかということになりますが）。
それとも、平均しても100日程度で解読できてしまうものなのでしょうか。
あるいは、すぐに解読できてしまうということを証明したのだけど学界の大御所が受け入れて
くれないので、仕方なく実際にやって実証することにしたとか？
Re:なぜ解読できたのでしょうか？ (スコア:5, 興味深い)
NICTのプレスリリースによる概要の説明
http://www.nict.go.jp/press/2012/06/18-2.html [nict.go.jp]
1. 初期値最適化手法の開発。
書いてないけど、まあ数倍ぐらい早くなる？
2. 探索方の改良
数十倍に
3. 繰り返し解くことになる方程式の処理部分の最適化
数倍に
4. 並列化の改善
数倍に
全部合わせると、数倍×数十倍×数倍×数倍で1000倍ぐらいは行く？
で、かかったCPU時間が100年だから、1000倍ぐらいの高速化と考えると10万年でまあ桁はあってる感じ？
#実際には、「数十万年かかる」と言われてた頃のCPUに比べ今の方が速かったりとかそういうのもかかるんだろうけど。
Re:なぜ解読できたのでしょうか？ (スコア:5, おもしろおかしい)
新手のウォーズマン理論かと思った。
Re: (スコア:0)
さらに友情がミックスされてのこの演算速度と考えれば最初からゆで理論
Re:なぜ解読できたのでしょうか？ (スコア:1)
> 利用した計算機はNICT、九州大学、富士通研究所のサーバ21台、252コアで、トータル148.2日間で解読に成功しました。これは、Intel Xeonプロセッサ1コアで、およそ102年の計算時間に相当します。
(http://www.nict.go.jp/press/2012/06/18-2.html)
から来ていると思わるので, 親コメの計算式は実時間でよく, 親コメも"(実時間で)１０万年でまあ桁はあってる感じ？"と言っているんじゃないでしょうか...
#CPU時間という言葉を使ってしまって, あるプログラムがCPUを専有した時間という意味の方で捉えさせてしまった親コメのミスかな。
Re:なぜ解読できたのでしょうか？ (スコア:1)
http://scan.netsecurity.ne.jp/article/2012/06/18/29280.html [netsecurity.ne.jp]
こっちの記事によると解読を大幅に高速化する攻撃方法が発見されて、それを実証したということみたい。
> 期待値としてはやはり数十万年で、今回すぐに解読できたのは偶然なのでしょうか？
偶然でそんなことが起きる可能性は確かにゼロではないが、本気で心配してるなら二度と放射脳の連中を笑えないな。
Re: (スコア:0)
なぜ放射脳の話に飛躍するのか分からないけど、小さな確率のことでも、起こるときは起こりますよ。
Re:なぜ解読できたのでしょうか？ (スコア:1)
小さな確率のことでも、起こるときは起こりますよ。
そういう考え方をすると統計学の意味がなくなってしまいます。
男女の生まれる確率は男性の方が若干高いことが統計的に示されていますが、来年から逆になる可能性もゼロではありません。
解読に数十万年かかるとされた暗号が148日で解読されたら、偶然ではあり得ない、と考えるのが正しい科学のスタンスなわけです。
Re: (スコア:0)
「・」を出そうとサイコロを振って「・」が1回目ででっちゃたのという話です。
Re: (スコア:0)
違う。
「・」を連続で２７８回出そうとして出ちゃったくらいにあり得ない確率。
Re: (スコア:0)
> 「・」を連続で２７８回出そうとして出ちゃったくらいにあり得ない確率。
全然違う。
サイコロの「・」が278回連続して出る確率は、(1/6)^278≒5e-217。
一方、解読に数十万年（例えば25万年）かかるとされた暗号が148日（約1/2年）で解読される確率は、
約50万分の1 = 2e-6。
200桁以上も違います。いいかげんなことを言うものではありません。
Re:なぜ解読できたのでしょうか？ (スコア:1)
>一方、解読に数十万年（例えば25万年）かかるとされた暗号が148日（約1/2年）で解読される確率は、
>約50万分の1 = 2e-6。
解読できるかできないかの確立だから50%じゃないの？
Re:なぜ解読できたのでしょうか？ (スコア:1)
> > >一方、解読に数十万年（例えば25万年）かかるとされた暗号が148日（約1/2年）で解読される確率は、
> > >約50万分の1 = 2e-6。
> > ここ、笑うところ？
> 計算が違ってるのは気付いてたけど面倒だし桁の話をしているときにそんな重箱の隅をつついてくる奴もいないだろうと思ってた。
なんかよくわかりませんが、
・「解読に２５万年かかる暗号」の解読に要する日数は、最小０日から最大２５万年の一様分布である
という仮定に基づいて2e-6という数を算出したのだと思いますが、もし
・「解読に２５万年かかる暗号」とは、答え（かぎ）の標本空間をブルートフォースで全部チェックするのに要する時間が２５万年という意味である。
・１個のチェック（ある候補をトライしてあってるかどうか調べる）にかかる時間はどれも同じである。
なのであれば、
・無作為に選ればれた答え（かぎ）をブルートフォースでチェックして探すのに要する時間が１４８日でおわる確率は2e-6である。
と計算したのは、笑いどころではなくて、あってると思います。
Re: (スコア:0)
1000年に一度の地震が起こる確率はどれくらい？
巨大隕石が地球に落下する確率はどれくらい？
いずれも、過去に起こってますよね。
確率が小さいのと、確率がゼロなのとは、まったく違います。
小さい確率を無視するのが科学ではありません。
あることが起こる確率が小さいとき、そこには何か理由（法則）があるに違いないと考え、それを解明するのが科学的な考え方です。
もうすこし踏み込むなら、「確率が小さい」という表現は定量的ではないので、科学的な考え方に立てば、あまり良い表現ではありません。
解読に数十万年かかるとされた暗号が148日で解読されることがありうるかどうかは、そもそも科学とは関係ありません。
Re:なぜ解読できたのでしょうか？ (スコア:1)
そりゃ起こるでしょうよ。
期間を無視するのはやめようよ...
Re: (スコア:0)
確率が0でなくとも、狙って出せるほど高い確率でもありません。
「・」を連続278回狙って出せたなら、そこには確率以外の何かがあるはずだとするのが統計です。
確率が低いから無視するのではなく、より確率の高そうなほうへ着目するだけのことです。
Re: (スコア:0)
読売新聞の記事 [yomiuri.co.jp]では、
> 研究チームはペアリング暗号を解読する新しい「攻撃法」を開発した
とありますので、（恐らくは理論的に）脆弱だと思われる部分を突くことで、短時間での解読に至ったんだと思います。
これまでの記録 (スコア:1)
676ビット長（10進数で204桁に相当）において、汎用コンピュータ18台で33日
http://www2.nict.go.jp/pub/whatsnew/press/h21/100223/100223.html [nict.go.jp]
これの数百倍の演算能力相当
http://www.nikkei.com/article/DGXNASFK1803N_Y2A610C1000000/?uda=DGXZZO... [nikkei.com]
だとすれば、数十年かければ可能になっていたわけで
「解読に数十万年かかる」というのは、考案時の
ものでしょうか。
Re:これまでの記録 (スコア:1)
コア数で比較すると
676ビット長 汎用コンピュータ18台(12-24コア)で33日
923ビット長 252コア で 148日
コア数で10倍、期間で4倍なので
計算手法・プログラミングでの高速化は
5から10倍程度の高速化ということでは。
Re: (スコア:0)
京なら数分でできそうな感じですね。
独法もなかなかよくやっているじゃないか (スコア:1)
こういうニュースは嬉しいね。
普段から「暗号なんて日本人に解けるわけないだろ」とかそういう先入観持たれているしね。
俺は持っていないけれども。
Re:独法もなかなかよくやっているじゃないか (スコア:1)
これが「楕円曲線上のペアリングを用いた暗号方式」のことであれば考案者も日本人
#境・大岸・笠原
Re: (スコア:0)
離散対数のはず
Re:独法もなかなかよくやっているじゃないか (スコア:2)
Re: (スコア:0)
>独法もなかなかよくやっているじゃないか
自分が興味のある内容に関連したプレスリリースがたまたま出ただけで、
よくやっていると評価するのもなんだかなーと。思いますがね。
「メディア受けする記事に踊る市民」
ってのを感じました。
Re: (スコア:0)
>よくやっていると評価するのもなんだかなーと。思いますがね。
捻くれてるというよりは、普通に頭悪い子がいるな。
目覚しい成果が出たらしいから、よくやってるて感想でいいんだよ。
他者の評価基準が自分より低いからて、いちいち絡むのってそれこそなんだかな～。
Re:邪推をしてみる (スコア:-100 荒らし) (スコア:1)
> 普段から「暗号なんて日本人に解けるわけないだろ」とかそういう先入観持たれているしね。
言い訳します。
これを言っていたのは私の同僚です。
彼が自信満々で貶すので、世間一般ではそう思われていると思い込んでいました。
私自身はそうは思っていないというのは、本当です。
なんか、卑屈なレス申し訳ない。
素人計算 (スコア:0)
タレコみのリンク元の記事ではどの程度の計算をしたのかわからないので適当に予想してみた。
仮定
・今回の暗号はPen4やCoreDuoクラスのCPUでブルートフォースで計算すると50万年で全空間の計算が可能と仮定
・Pen4やCoreDuoの計算能力を仮に5GFLOPSと改定
・各チームが使ったコンピューターをハイエンドGPU(１枚あたり5TFLOPS)を３枚挿ししたPCと仮定
かなりいい加減な仮定だけどまあいいや(藁)
21台のPCの総計算能力は元のPen4クラスのPCの計算能力の63000倍。
これを使って暗号の全空間を計算するのに必要な日数はおそよ2900日。
つまり148日あればざっと全体の5%の空間を計算したって話。
暗号の計算で浮動小数点演算の速度で比較する無意味さとか突っ込みところは満載だけど
オーダー的に考えればGPU複数挿しのハイエンドPC(といっても個人購入可能なレベル)数十台で
数百日計算すれば全空間の数10%ぐらいの計算が出来てしまう可能性は十分にあります。
つまり*たまたま*148日目で解けたとしても別に驚くほどの話ではないような気が。
Re: (スコア:0)
次はソロバンで何年掛かるか計算してみて下さい。
Re: (スコア:0)
よし、それでAmazonEC2使ってどれぐらい金がかかるか計算してくれ。
なんてこったい (スコア:0)
結婚する予定の彼女とお揃いのペアリングにしようと思ったのだが・・・・
Re: (スコア:0)
いちおう148日ももつんだからいいじゃないか
＃成田離婚は避けられるわけだし
Re:なんてこったい (スコア:2, 参考になる)
神戸のお京さんなら、単純な計算量でい言うと約１３分で解けるらしい。
http://sankei.jp.msn.com/west/west_life/news/120618/wlf12061815220009-n1.htm [msn.com]
成田離婚どころか、式場から出る前に破局になりそうです。
Re: (スコア:0)
暗号が無効になるだけだから大丈夫。
Re: (スコア:0)
暗号を解読したとき、そこに書いてある真実は、破局になるに十分な内容です。
秘密は墓場まで持って行く覚悟でないと。
# どんな内容？
Re:なんてこったい (スコア:1)
二人はそれぞれ理想のパートナーに出会い、素敵な一夜を過ごしましたとさ。めでたしめでたし。