暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 441 名前：77 mailto:sage [04/08/04 01:47] >>437 本人が冗談で書いたって言ってるし、大体暗号のことも、このスレで自分が 何を質問されているのか、何を要求されているのかってことも、まだよく わかってないように見えるから、自分的にはあんまり気にならなかったよ。 期限内に提出したとしても、記述の曖昧さは変わらなかっただろうし。 てかまたＤＬできねえ・・・（現在携帯からカキコ） 442 名前：１３２人目の素数さん mailto:sage [04/08/04 01:53] プログラムを使っていて正しく暗復号出来ない平文を発見しますた！ 443 名前：１３２人目の素数さん mailto:sage [04/08/04 02:22] ああいう場面で冗談を言う事自体が非常識かと。 ちゃんと謝罪したから反省してるのかと思いきや、 今度は名無しで荒らしてるし。真面目に数学の話を する気があるとはとてもとても。 444 名前：白シャツ [04/08/04 03:01] 32167976543216575761321303216489732401579451603031657576789812332665122546598798732132103214567 =3^3 *259956881 *862935673569527 *33505539576299688421735663 *158512538998972445625528303384598776196000541 PARI/GPでfactor()やって、 ７０分ぐらい待ってたらでました。 445 名前：１３２人目の素数さん mailto:sage [04/08/04 03:12] >>440 数体篩法は木田氏のサイトから落とせたが、ECMは見つからなかった。 あ、それからC93, C204はC94, C205の間違いですた。失礼。 >>444 ｷﾀ━━━━━(ﾟ∀ﾟ)━━━━━!!! 446 名前：白シャツ [04/08/04 03:14] >>443 その平文uPキボンヌ でもそれって、例によって一意復号できないことが 「（脳内）仕様」でわかってる平文とかなのかな？ 447 名前：白シャツ [04/08/04 03:20] >>445 ECMの部分のライセンスしらべてみます。 あるいはダウソできるところを探すか。 >>432はこんな方法では厳しいと思うので、 ECMか数体篩やらないとダメそうですね。 とりあえずECMやってダメっぽかったらあきらめるか。 それとも立教大チームに頼む？(w 448 名前：１３２人目の素数さん mailto:sage [04/08/04 03:23] mathematica使えば？ 449 名前：白シャツ [04/08/04 03:39] >>445 木田先生のサイトの 「一般的な応用プログラム」ubapl96.lzhに入ってました。 >>448 誰もが買えるという値段じゃないと思いますが。 個人だと２０マソとかするんじゃなかったっけ？ 450 名前：１３２人目の素数さん mailto:sage [04/08/04 03:44] >>439のC205の分解も終了 768755431457657534487763215469843243165987441478561569642434875434143347878097324326569324378708564215656976232126579077623670965314559775424356907765324354597234570867524323667074324587097956424254598795642434598780665243 =3^3*89*7867*16561*1251707 *6020414544349 *12198688540659043 *2671139064951542099966004054646162959839073916176596776854493343396709794565808 46895071862292626583677038451344216647471687661615162545270142712791901947647971 24165525116390887 451 名前：１３２人目の素数さん mailto:sage [04/08/04 08:44] 大学（に行ってる人）の端末に入ってないかなと 暫く行かない私は無理ですが 452 名前：１３２人目の素数さん mailto:sage [04/08/04 09:41] >>449 Mtlabとの互換モード搭載フリーソフト。 www.octave.org/ 453 名前：白シャツ [04/08/04 19:12] >>450 乙 えらい速くできちゃったんですね。 >>448　>>452 暗号関係の用途だと使い勝手が悪いと思われ。 やりことにもよるけど。 454 名前：452 mailto:sage [04/08/05 11:11] >>453 「16歳のセアラが挑んだ世界最強の暗号」（ノンフィクション） って本の中でセアラが実際にMathematica使ってるけど。 最終的な実用段階は別として、 試行錯誤の段階では手軽にできていいんじゃね？ 使いなれてないとかえって面倒かもしれんが、 選択肢としては不自然でもないだろ。 455 名前：１３２人目の素数さん mailto:sage [04/08/05 11:42] >>454 Mathematicaの素因数分解って、どういう方法が実装されてるの？ 関数一個で数体ふるいとかやってくれたら、便利だな。 でも、20万もライセンス料払って使ってるマシンなら、 こんな所に適当に書き込まれた数を素因数分解するより他にすることあるだろｗ 456 名前：白シャツ [04/08/05 18:43] >>454 Mathematica使える人は使えば良いし、選択肢として不自然でないというのはそのとおりです。 ただ、誰もが持っているor気軽に入手できるソフトでは無いと思う、高いし。 数値計算、数式処理、可視化みたいなところが強いって話らしい。 あくまで汎用数学用ソフトであって、何にでも使えるんだろうけど、 すべての数学分野で最高のパフォーマンスを発揮するというわけではない。 実際、数論関係に使うとなると自分でプログラムしないといけない部分が多いよ。 いろんなソフト使っておいしい所取りすれば良いと考えれば、 暗号てのはMathematicaの使用例としてオイシイところでは無いと思うだけです。 457 名前：１３２人目の素数さん mailto:sage [04/08/05 21:01] Mathematicaって昔からあんなに高いの？ 458 名前：１３２人目の素数さん mailto:sage [04/08/05 21:32] PARI-GPは数論関連の関数は豊富なので使える。 もっとも、素数に関連する研究がしたいなら、自分でアルゴリズムを理解して プログラミングできるくらいでないとだめだろ。 （最近は素数判定や素因数分解のツールが出回って、素人でも素数探しが できるようになってしまっているが…） 459 名前：450 [04/08/05 23:03] >>455 PARI-GPはC205@>>439の分解の速さから言って高速アルゴリズムを 実装しているっぽいけど、楕円曲線法を使ってるかどうかは不明。 460 名前：１３２人目の素数さん mailto:sage [04/08/05 23:28] >>459 factorint(n,{flag=0}): factors the integer n using a combination of the Pollard Rho method (with modifications due to Brent), Lenstra's ECM (with modifications by Montgomery), and MPQS (the latter adapted from the LiDIA code with the kind permission of the LiDIA maintainers), 461 名前：452 mailto:sage [04/08/06 15:50] >>456 そのへんは好みの問題もあるし、絶対いいとまでは言わないでおく。 私自身もMathematicaで数論的なものをいじったことはないので強く主張できなかったり。 Mathematicaがえらく高価だというのはその通りなので、octaveを紹介したつもり。 462 名前：白シャツ [04/08/08 19:58] >>378　見に行ってきた生スクーフみてきた。 漏れの語学力では何言ってるかわからなかった。 まぁ日本語で講演されててもわからないだろうがな(W >>461 わかっていると思うけどMathematicaの批判しているのではないので、 念のため。漏れも大学のサイトライセンスで使えたんだけど、 出ちゃったら使えなくなるのでちょっと遊んだだけでやめました。 まぁやる内容的にPARI/GPでやる方が楽だったりしたのもあるんだけど。 >>461は何に使ってるの？ 使い勝手とかの感想とかあったらキボンヌ。 463 名前：77 mailto:sage [04/08/09 02:39] >>462 ｷﾞｬｰ忘れてた ついでにzipも取り逃した 464 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/10 00:27] >>441さん 記述曖昧でしたか、 曖昧でないようによく考えたつもりでした。 ここのとこが分らないというのがあれば言ってください。 曖昧じゃないように書きますので。 >>442さん 存在しない暗号文というのがあります。 存在しない暗号文でも復号してしまうので 送信者には平文のハッシュ値を一緒に送ってもらう必要があります。 >>443さん すいません。 真面目に数学的な話をしたいと思っています。 荒らしてるつもりはありませんでした。 465 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/10 00:28] >>446さん 存在しない暗号文C'を復号→M,rを得る M,rを暗号化→Cを得る(C'にはならない) Cを復号→M,rを得る こんな流れだと一意復号できません。 ですが、復号しようにも存在しない暗号文C'の場合は 平文・乱数からC'にすることができないので 一意復号を考える場合には無視していてもいいと思います。 ただ、秘密鍵について知ろうとしたときに 存在しない暗号文C'を復号させることで 秘密鍵を知ることができてしまうので 暗号文と平文のハッシュ値をもらうようにして 復号文のハッシュ値と平文のハッシュ値が一致するか チェックするようにしないといけないです。 ↑についてはまたpdfにまとめてupします。 このあいだupしたものと同じですが 暇な方は↓を改造(M,rを7・8bitくらいで)して ttp://up.isp.2ch.net/up/f34a15cf39e7.zip 暗号文の初期値に対して1を加算した暗号文を 何個か復号して、平文Mの差とxについて比較してみてください。 そしたら上で言ったことが大体分かると思います。 >>463さん取れましたか？ 466 名前：１３２人目の素数さん mailto:sage [04/08/10 01:19] >>464 >存在しない暗号文 こび言い回しは変 467 名前：１３２人目の素数さん mailto:sage [04/08/10 10:54] >>465 選択暗号文攻撃に致命的に弱い、ということですな。 468 名前：白シャツ [04/08/10 20:26] >>464-465 >>442 では >プログラムを使っていて正しく暗復号出来ない平文を発見しますた！ とかいてある。「平文」を発見したそうなんだけど。 一意復号できない平文が存在することはないのですね。 469 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/10 21:56] >>466さん 意味合いは分かってもらえましたでしょうか？ どういう風に表現したらいいのかよくわかりません >>467さん その通りです。 >>468さん 公開鍵・秘密鍵と平文・乱数を聞いてみないと分かりません。 ですが、 平文・乱数の範囲をきちんと守れば 一意復号できない平文はないはずです。 470 名前：白シャツ [04/08/10 22:45] ところで前から気になっていたんだが、 署名、認証が出来ないと書いてあるけど何故？ 471 名前：１３２人目の素数さん [04/08/10 22:58] むしろ、署名・認証が出来ないからCCAの考察をする必要がない、の理由が分からん。 署名や認証って、RSAみたいな逆に使うって手法しかないと思ってるのかな。 472 名前：白シャツ [04/08/11 00:18] >>471 なるほどね。 メッセージ復元型署名を実現しようと思うと 梅署名公開鍵（梅暗号秘密鍵）から 梅署名秘密鍵（梅暗号公開鍵）が容易に求まるということか。 復号できなくてもよいからM1,M2の出来損ないから 正当性の検証を証明できればそれでよいんだから、 d1,d2とｎだけ公開する署名スキーム考えれば良いよね。 このまま適用しようするとだけだとダメだろうけど。 473 名前：１３２人目の素数さん [04/08/11 00:36] 「復号することなく」その暗号文が本当に正当な暗号文であることを確認出来る というのが出来れば、ちょっと面白そうだな。 そういうの他にあるっけ？ 復号する途中に正当性をチェックする暗号はいっぱいあるが、 誰にでも検証出来たり、もっと厳しくある鍵を知っていたら検証は、出来る（復号は出来ない）みたいなやつは 今、ぴんと思い浮かばない。 誰か教えて〜 474 名前：白シャツ [04/08/11 01:00] >>473 >「復号することなく」その暗号文が本当に正当な暗号文であることを確認出来る >というのが出来れば、ちょっと面白そうだな。 誤解招くような表現だったかな。 署名の話なんで（メッセージ、署名文）を送って、 検証できれば署名文からメッセージ出てこなくてもOKってことなんだけど。 たとえば、シュノア署名とか。 >誰にでも検証出来たり、もっと厳しくある鍵を知っていたら検証は、 >出来る（復号は出来ない）みたいなやつは今、ぴんと思い浮かばない。 似たようなのはISECかSCISだったかで聞いたことあるよ。 階層型暗号とかそういうやつだったと思うんだけど。 漏れは現在なんちゃって署名屋さんなんであんまり詳しくないです。 誰かエロい先生、教えて〜。 475 名前：白シャツ [04/08/11 09:49] 送信相手の公開鍵で暗号化したメッセージ ＋暗号文に対する自分の電子署名 でだいたい同じことが出来て、>>474で言ってたやつは 多少計算量や暗号文＋署名合計のサイズが良くなる程度のメリットしか無かったんで、 まじめに考えるの止めたんだった。 むしろマルチキャストでそういうことできる様に したいと検討するのが面白そうです。 476 名前：１３２人目の素数さん [04/08/11 11:58] あ、そうか。確かに、鍵が必要なら簡単にできるな。 むしろ、鍵情報を一切知らない人がその暗号の正当性（正しく平文を暗号化したものである） を検証出来る方が難しいんだな。 マルチキャストと公開鍵暗号は、逆の思想だから、一緒に使うのはちょっと厳しそうかな。 共有鍵を作って、RSA署名のように秘密鍵で暗号化して特定のフッターを付け、作った共有鍵でカプセルのように包む。 受け取った人は、公開鍵で復号して、フッターを確認すれば、それを取り除いて共有鍵でさらに復号する。 白シャツがいったことが正しく理解出来ていれば、これでうまくいくと思うんだが。 477 名前：白シャツ [04/08/11 18:28] >>476 >むしろ、鍵情報を一切知らない人がその暗号の正当性（正しく平文を暗号化したものである） >を検証出来る方が難しいんだな。 公開鍵使わずにとなると、何をもって正当かの定義によるよね。 単にメッセージダイジェストとかつけるというものから、 もっと厳しいものまで考えられるし。 >マルチキャストと公開鍵暗号は、逆の思想だから、一緒に使うのはちょっと厳しそうかな。 >共有鍵を作って、RSA署名のように秘密鍵で暗号化して特定のフッターを付け、作った共有鍵でカプセルのように包む。 >受け取った人は、公開鍵で復号して、フッターを確認すれば、それを取り除いて共有鍵でさらに復号する。 >白シャツがいったことが正しく理解出来ていれば、これでうまくいくと思うんだが。 残念ながら結託攻撃に対する耐性を考えないといけないのよ。 これが非常に厳しい。 478 名前：１３２人目の素数さん [04/08/11 19:28] >>477 メッセージダイジェストを付けるというのは、攻撃者が簡単に、それっぽい暗号文に偽装出来ちゃわない？ 整理すると、 ある検証者が、そのデータが、ある暗号スキームを用いて暗号化されたデータなのか、ただの乱数列なのかを判定出来るプロトコルを考える。 ・ みんなは、暗号化に使った鍵に関連する情報は知っている。 　　（例えば、鍵のダイジェストとか。直接、鍵の情報は知らない。） ・ みんなは、平文に関する情報は平文が取りうる範囲程度しか知らない。 ・ 検証者は、そのデータを復号出来るとは限らない。 ・ 適当に乱数を持ってきても暗号文だと判定される確率は限りなく低い。 こんな感じ。 攻撃者としては、鍵のダイジェストから元の鍵でなんらかの平文を暗号化した「暗号文」ってのを偽造したい。 誰か、うまい方法教えてくれ〜 >> 残念ながら結託攻撃に対する耐性を考えないといけないのよ。 そうだな、確かに結託するといろんなところが破綻する。 問題としてはどこを守るのかと、誰を信じるかだな。シナリオごとに違うんじゃない？ 例えば、全員が結託してもプロトコルが崩壊しない（全員が不正者であると見抜ける）、とかを考えれば凄いな（ｗ プロトコルvs参加者みたいな。むしろ、暗号の世界じゃなくて他でやってくれと（ｒｙ 479 名前：大学への名無しさん [04/08/11 20:21] 数学って解かなくても何度も読めば良いのでは？ school4.2ch.net/test/read.cgi/kouri/1092221749/l50 ご意見お待ちしております。 あくまでも大学受験レベルですが。 480 名前：白シャツ [04/08/11 22:46] >>478 >メッセージダイジェストを付けるというのは、攻撃者が簡単に、それっぽい暗号文に偽装出来ちゃわない？ 基本的にこれは安全という前提で議論している、プロトコル屋さんの場合は。 MDはメッセージのハッシュ値だからハッシュ関数がうまく出来ていることが前提です。 ハッシュ関数の研究だけでも1分野できるぐらい重いテーマなんですよね。 ただ、MDつけるというと復号できることが前提になるかもしれないので、 続きに議論されている内容とはちょっと違いますね。 481 名前：白シャツ [04/08/11 23:00] >>480の続き 暗号文を復号せずに暗号化されていることを示す問題ですね。 漏れは勉強不足なんで調べないとわからないけど、 従来無ければ面白いテーマかもしれない。 >・ みんなは、暗号化に使った鍵に関連する情報は知っている。 >　　（例えば、鍵のダイジェストとか。直接、鍵の情報は知らない。） 公開鍵暗号の場合だと鍵のダイジェストではなくむしろ 暗号化鍵そのもの、受信者の公開鍵を使うのが現実的じゃないかな。 受信者、送信者の（公開鍵、秘密鍵）組を (Pr,Sr),(Ps,Ss)として、メッセージをM,乱数をRとします。 暗号文C=enc(M,R,Pr)と署名sig(C,R,Pr,Ss)の関連を Pr,Psを使って検証できるようにするみたいな感じ？ 482 名前：１３２人目の素数さん [04/08/11 23:03] スマソ、議論がかみ合ってなかった。 復号しないのに、メッセージダイジェストが確認出来るって前提だったから、 （暗号文）＋（暗号文のダイジェスト）って送るのかと思った。そりゃ簡単に偽造できるわーというような。 （平文）＋（平文のダイジェスト）の全体を暗号化すれば、確かに、復号出来れば完全性は確認出来る。 でも、それが出来ないから、ちょっと難しいのかな、と。 ハッシュ関数が安全でなくなったら（一方向性が言えない、衝突困難性が言えない）、世の中困るんで、 勘弁して欲しいでつ。 483 名前：１３２人目の素数さん [04/08/11 23:11] >>481 > 公開鍵暗号の場合だと鍵のダイジェストではなくむしろ > 暗号化鍵そのもの、受信者の公開鍵を使うのが現実的じゃないかな。 これは、考えたんだけど、そうすると攻撃者の、「暗号文っぽい文の偽造」が極めて簡単になってしまわない？ > 暗号文C=enc(M,R,Pr)と署名sig(C,R,Pr,Ss)の関連を > Pr,Psを使って検証できるようにするみたいな感じ？ だと、やっぱり、攻撃者は、RとPrをしれるからC'= enc(M' , R, Pr)ってのを偽造出来てしまう。 M≠M'は復号出来ない以上、検証のしようがない。 484 名前：白シャツ [04/08/11 23:12] >>480　さらに続き >そうだな、確かに結託するといろんなところが破綻する。 >問題としてはどこを守るのかと、誰を信じるかだな。シナリオごとに違うんじゃない？ 同意。そこが社会的に信用できるかの問題。 最終的に自分以外信用できないという仮定で安全ってのが理想。 >例えば、全員が結託してもプロトコルが崩壊しない（全員が不正者であると見抜ける）、とかを考えれば凄いな（ｗ >プロトコルvs参加者みたいな。むしろ、暗号の世界じゃなくて他でやってくれと（ｒｙ Authorityは別にして参加者結託を数学的に難しくするのは 暗号の世界でも考えられてるんじゃない？ 結託不能は厳しいけど、結託閾値を上げてやるみたいなことは やってる人結構いるんじゃないかな。分野にもよるだろうけど。 485 名前：白シャツ [04/08/11 23:19] >>483 梅暗号だったら乱数が復号できるけど、 普通の確率暗号だと乱数がわからないものもあるので、 その場合はメッセージ差し替えは難しいと思う。 でも同様に目的の復号せずに検証ってのも難しいと 予想できるけどね。それと>>481でいってた奴だと、 送信者の秘密鍵が署名の方に入ってるんで、 問題の難しさがまたわからなくなります。 受信者が攻撃すると仮定するとさらにややこしいかも。 486 名前：白シャツ [04/08/11 23:33] 読み直すと、なんかいろいろな部分で 議論がかみあってないようなところがありますね。 ちゃんと整理してから書かないと。スマソ＞allとか言いながら約1名と予想してますが このテーマ面白いかもしれない。とりあえずサーヴェイしてみる価値ありそうですね。 でも、本気でやってSCISあたりで発表したら漏れが特定されかねないな(w >>479はいったいどうしてここに貼ったのかわからん。 スルーされるの見えてるだろうに、と釣られてしまった。 487 名前：１３２人目の素数さん mailto:sage [04/08/11 23:52] >>486 本気でやるなら、共同研究者にしておくれ（ｗ 所属はscience.2ch.net/mathでいいだろう？？？ というか、絶対リアルで顔を合わせたことがあると思う。 488 名前：白シャツ [04/08/12 00:10] >>487 暗号業界狭いので>>273で書いてますようにエロイ先生相手に 適当な事言ってる可能性があるのが怖いのですが、 会っている可能性は極めて高いかと思います。 でも漏れはペェペェですのでどうかなとは思いますけど(w 現状では共同研究ってところまで考える場合ではないので、 本気でやることになりそうな場合にはリアルで探りが入ることに なるかもしれないと考えておきます(w ただ、上が仲悪い可能性が.......... 489 名前：１３２人目の素数さん [04/08/12 06:09] Elgamal暗号について幾つか質問です｡ ・Elgamal暗号は単にDH鍵共有方式によって共有した鍵を使った共通鍵暗号による暗号方式である､という理解で正しいでしょうか？ ・Elgamal暗号による”認証”はありますか？ 490 名前：１３２人目の素数さん mailto:sage [04/08/12 06:14] >>489訂正 ”認証”じゃなくて”署名”でした｡ 491 名前：１３２人目の素数さん mailto:sage [04/08/12 12:07] > ・ElGamal暗号は単にDH鍵共有方式によって共有した鍵を使った共通鍵暗号による暗号方式である､という理解で正しいでしょうか？ 正しいです。だから、特許もDH鍵共有方式がそのまま使われたという話もあります。 > ・Elgamal暗号による”認証”はありますか？ 「暗号」による「認証」はありませんが、ElGamalによるElGamal署名はありますし、ちょっと改良したDSA署名などは、とてもよく使われています。 492 名前：１３２人目の素数さん [04/08/15 05:09] 質問です。 encrypt　は暗号化でいいんですが、 decrypt　は復号？復号化？ 復号化は日本語として変ですが、符号理論などでは符号化の反対として定着しているらしいです。 日本語で書かれた論文では、どうなっているのでしょうか？ 493 名前：１３２人目の素数さん mailto:sage [04/08/15 05:20] 復号する・復号時・復号処理 復号化する・復号化時・復号化処理 論文中で統一されていれば、どっちでもいいかな。 494 名前：493 mailto:sage [04/08/15 05:42] SCIS2004だとほとんど「復号」ですね。 495 名前：白シャツ [04/08/15 22:47] ちょっと違うがこんなのあった。 秘密鍵暗号の暗号文を復号せずに検証するってかんじかな？ アブストさらっと見てとりあえず落としただけなんでまだ読んでない。 ttp://eprint.iacr.org/2004/028.pdf 公開鍵暗号だと>>481で言ってたのでたぶんOKだと思う。 PKIの応用例とかにそういうかんじのが出てるみたい。 ただし、情報処理技術者試験SSの参考書に適当に 書いてある奴なんであんまり信用してないけどね。 496 名前：１３２人目の素数さん [04/08/16 02:30] >>495 ん？これって、public key encrypted messageの認証をしようとしてるんじゃない？ アブストラクトの一行目に「an asymmetrically encrypted ciphertext」って書いてあるんだが。 むしろ、ad hocのグループに対称鍵を共有させるkey agreementの方が難しそうだな。 497 名前：白シャツ [04/08/16 03:01] >>496 オオボケでした、スマソ。 >アブストラクトの一行目に「an asymmetrically encrypted ciphertext」って書いてあるんだが。 symmetrically encrypted ciphertext　とおもてたようだ。 というか、条件反射的にそう思い込んでたのかも。 >むしろ、ad hocのグループに対称鍵を共有させるkey agreementの方が難しそうだな。 ってどういうことでしょうか？ ID-Based encryptionとかの Trusted Authority無し版でしょうか？ それともDH鍵共有みたいなのをｎ人（n>2）でやるということ？ 498 名前：１３２人目の素数さん [04/08/16 11:45] >>497 ID-Basedってライセンス使うコンテンツ保護のやつだよね？ TAなしでどうやってやるんだろう。うぉー、勉強することで一杯だ。 想定しているのは、後のDH鍵共有をｎ人でやるっていうもの。 これも、内部不正者とか結託とかの問題が熱い。 考えれば考えるほど、対称鍵暗号使いながら、メッセージを認証するって難しい気がしてきた。 499 名前：白シャツ [04/08/16 17:49] >>497 >ID-Basedってライセンス使うコンテンツ保護のやつだよね？ 一概にそうとは言えないけれど、応用考えるとそっち方面にいくよね。 もともとは公開鍵取りに行ったりする予備通信を不要にして、 IPアドレスなりメアドなり既存の情報から鍵を作れないかってことだったと思う。 >TAなしでどうやってやるんだろう。うぉー、勉強することで一杯だ。 いまのところ出来てないよ。 実現する方法を提案、もしくは不可能なことを証明できれば神かも。 >想定しているのは、後のDH鍵共有をｎ人でやるっていうもの。 ad hocで鍵共有という状況を考えると、ワンタイムキーが効率よく共有できれば >これも、内部不正者とか結託とかの問題が熱い。 とか考えなくても使えるんじゃないかな。 今後はそういう「使い捨て前提簡易暗号」みたいなのが面白いかと個人的には思ってる。 >考えれば考えるほど、対称鍵暗号使いながら、メッセージを認証するって難しい気がしてきた。 結局ハイブリッド型暗号にならざるを得ないだろうけど、 トレードオフポイントを対称鍵の方にどこまで持っていけるかってことになるのかな。 これは面白そうだけど、本気でやると茨の道が見えてますね。 どうやったらよいのだろう。 500 名前：１３２人目の素数さん [04/08/16 18:45] > ワンタイムキーが効率よく共有できれば、 っていうのが難しいんだよな。効率よく共有と、安全に共有は、どっちもまだまだだかと。 ハイブリッド暗号にするのは、それでいいことにしよう。 おそらく、解読よりも圧倒的に検証の方が回数が多いから、検証が対称鍵の解読で出来ればいいのかな。 もしくは、それに準ずる計算速度で出来る演算で検証したいな。 たくさんのクライアントが、一台のサーバーにメッセージを送りつけ、 通常時は、サーバーは、メッセージの正当性を確認するだけにする。 なんか問題が起きたときに、クライアントは、サーバーに残されたデータと秘密鍵を検証者に送る。 信頼出来るサーバーログの生成とかに使えないかな。 いわゆるブラインド署名を、超高速に検証出来るようなモデルとかを考えると応用用途はいっぱいありそう。 501 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/16 20:55] あのう、今まで梅署名について考えていて、 きちんとしたのができたのですが、 ここに公開させてもらってもいいでしょうか？ スレの流れ的に怒られますか？ 502 名前：１３２人目の素数さん [04/08/16 21:23] >>501 問題なんじゃない？ただ、 > きちんとしたものができたのですが、 は、一つでもきちんとしたものを作ってから言った方がいいな。 503 名前：502 mailto:sage [04/08/16 21:31] すまん、 問題ないんじゃない？の誤字だ。 意味が逆になってしもた 504 名前：白シャツ [04/08/16 23:45] 　　　　　　　☆ ﾁﾝ　　　　　　　　 　　　　　　　　　　　　　　　　　　　　　 　☆　ﾁﾝ　　〃　∧＿∧ 　 ／￣￣￣￣￣￣￣￣￣￣￣￣ 　　ヽ　＿＿_＼（＼・∀・）＜　梅署名マダー？ 　 　 　 ＼＿／⊂　⊂＿)＿ ＼＿＿＿＿＿＿＿＿＿＿＿＿ 　 　 ／￣￣￣￣￣￣￣／| 　　 | ￣ ￣￣￣￣￣￣:|　 | 　　 |　５５５　蓬莱 　 .|／ 　　 ￣￣￣￣￣￣￣￣ 505 名前：白シャツ [04/08/16 23:58] コピペ改変ミス寒い、やるんじゃなかった >>500 >もしくは、それに準ずる計算速度で出来る演算で検証したいな。 つまり対称鍵暗号に匹敵するぐらい速い非対称鍵暗号が 出来ないかってことですか？ 506 名前：１３２人目の素数さん [04/08/17 00:39] >>505 >つまり対称鍵暗号に匹敵するぐらい速い非対称鍵暗号が >出来ないかってことですか？ ではないです。 検証が出来ればいいだけなので、復号が出来る必要はない。 例えばMACなんかは、対称鍵暗号や、ハッシュ関数で実現出来るわけで。 507 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/17 00:39] ttp://up.isp.2ch.net/up/bd323a52b2c3.zip ↑にアップしました。 明日くらいにどっかの無料HP借りて 今までアップしたものをまとめてアップします。 508 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/17 00:51] アップしたpdfですが下のほうでmod nが抜けていました。 全ての計算にmod nが必要ですので脳内補完お願いします。 509 名前：１３２人目の素数さん [04/08/17 02:28] 細かいことは全部抜きにして署名生成に必要なべき乗の回数が６回、検証で２回か。 ちょっと計算コストが大きすぎるな。既存の倍以上かかるだろう。 かといって、安全性があがっているわけでもなく。 あ、本当に書いてあることが全部正しいとするならば、 この署名は、簡単に偽造出来るな。 攻撃方法は、仕様がfixしてからにするわ。 510 名前：白シャツ [04/08/17 03:05] >>506 了解です。そういうことね。 ところで>>500の >おそらく、解読よりも圧倒的に検証の方が回数が多いから、検証が対称鍵の解読で出来ればいいのかな。 対称鍵の解読ってのがよくわからないのですが、 これはどういうことですか？ 漏れ的には（というか一般的に）鍵の解読＝鍵特定（すなわちアタック） 見たいな印象があるんですが。 対称鍵で何かを暗号化してチャレンジ＆レスポンスのやりとりで認証？ 511 名前：白シャツ [04/08/17 03:18] >>507 とりあえず、使ってる記号の定義は署名は署名で閉じてね。 梅暗号と同じ定義とか言われてもそれだけ見た人にはわからない。 ｎが何かとか書いてないと、即死の恐れあったりするし。 512 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/17 18:46] ttp://page.freett.com/umedoblock/index.html ↑に今までupしたものをまとめましたので 落としてください。 えっと、いいにくいんですが 初期の梅署名については簡単に偽造ができましたので、 新しく考えて全く違った署名方法になりました。 507を落とされた方はお手数ですが もう一度上記のurlから落としてください。 513 名前：白シャツ [04/08/18 00:00] nは本当に素数でよいんだな？ 514 名前：１３２人目の素数さん mailto:age [04/08/18 00:08] ここ素人ばっかだな。 515 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/18 13:56] 素数ということでお願いします。 516 名前：１３２人目の素数さん [04/08/18 15:56] japan.cnet.com/news/sec/story/0,2000050480,20070525,00.htm 517 名前：１３２人目の素数さん mailto:sage [04/08/18 18:05] >>515が>>513へのレスに見せかけて>>514へのレスだったら、 暗号屋としてのセンスはある方だと思う。 518 名前：１３２人目の素数さん mailto:sage [04/08/18 18:19] ψ【暗号アルゴリズム】重大な欠陥発見の報告相次ぐ pc5.2ch.net/test/read.cgi/pcnews/1092820402/ 519 名前：１３２人目の素数さん [04/08/18 21:42] >>518 コレ、続報期待してます。 520 名前：白シャツ [04/08/18 22:06] 正直言ってこういう言い方は悪いかもしれないけど、 デファクトスタンダードが氏んでくれると 新規参入者のチャンスが増えると思います。 でもハッシュの設計とかはあんまり興味なかったりする。 準同型が好き(w >>515 オイラーの定理って知ってるよね。三角形のやつじゃないよ(w 521 名前：白シャツ [04/08/18 22:12] Antoine Jouxといえば、3者間鍵共有の人ですよね。 >>498で話題になってたn人DH鍵共有のn=3の場合のやつ。 522 名前：１３２人目の素数さん [04/08/18 22:53] 衝突困難性は、結構危ないのは間違いない。MD5なんかは、前にも見つかってたしな。 でも、衝突させられて、さらに有意なものを作ろうとするとやっぱ難しいな。 >> 521 それ、最近読んだんだったｗ さらに、それを多人数に拡張して、やろうとしてたやつもあった。 523 名前：１３２人目の素数さん [04/08/18 23:04] >>522 前にも見つかっていたのはMD4の間違いじゃないか? 524 名前：１３２人目の素数さん mailto:sage [04/08/18 23:23] スマソ。MD5の圧縮関数を用いて衝突を起こすだな。これは、ずいぶん昔かも。 ちなみに今回のSHA-1も、関数そのものじゃないんでしょ？ 525 名前：１３２人目の素数さん mailto:sage [04/08/18 23:34] 度々スマソ SHA-1の低ラウンド版で衝突が起こせた、ってのがホントみたいだな。 526 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/19 00:01] >>520 ええ、家に戻るまでに気づきました。 まずいまずいと思っていました。 nは r^n mod n ≠ 1 を満たす自然数ということで・・・ 527 名前：１３２人目の素数さん mailto:sage [04/08/19 00:02] スラドでも話題になってたな．CRYPTOに参加してる人が現地からカキコしてたりしてた． ランプセッションは大盛り上がりだった様子． 528 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/19 00:03] r^n mod n ≠r でした、失礼しました。 529 名前：１３２人目の素数さん [04/08/19 19:10] slashdot.jp/article.pl?sid=04/08/18/0257220 への書き込みからすると、MD4、MD5はヤバイということのようですが、 MD5同様、広く利用されているSHA-1の方はどうなんでしょう？ SHA-1も安心は出来ないとなると、現時点では何があるのでしょうか？ 530 名前：１３２人目の素数さん [04/08/19 22:20] １年ぐらい前からMD5を破ることが出来るってのは示唆されてたんだがな。 まさか数分とは… 531 名前：白シャツ [04/08/19 22:36] 即座に偽造可能とかみたいに致命的というわけじゃないんだし、 だましだまし今あるの使ってその間に新しいの探すしかないわな。 規格やさんや実装やさんが大変になるかもしれないが。 実はホントにヤバいけど黙らされてるとかないよね。 532 名前：白シャツ [04/08/19 22:44] >>526 先にｎ決めないとダメなんじゃないの？ nが自然数とか言ってもこれが簡単に因数分解されると困る。 533 名前：１３２人目の素数さん [04/08/19 22:52] >>531 あるかもよ。 MD5の脆弱性が指摘されたのってアングラ発祥だもん。 534 名前：１３２人目の素数さん [04/08/19 23:29] ロシアとか中国とか、この辺凄そう！！ 535 名前：452 mailto:sage [04/08/20 09:18] >>531 私にはどう考えても致命的にしか思えないんだが。 536 名前：白シャツ [04/08/20 21:08] >>535 「ハッシュ関数」として致命的という意味ではそう思います。 ただ、アプリケーションにハッシュを使ってるような場合に すべて使用停止しないと危険というわけではなく、 より安全と思われるハッシュを探す時間稼ぎするぐらいは 大丈夫じゃないかという意味で言ってます。 逆関数が見つかったとかなら有意な電子署名の偽造とか簡単にできるでしょうけど。 ハッシュ関数でコリジョンが起こっても安全であることが証明可能な 電子署名方式とかそういうのあるのかな？ 537 名前：77 mailto:sage [04/08/20 23:24] いわゆる``Standard Model''での証明とかかな？ 538 名前：白シャツ mailto:sage [04/08/21 20:12] >>537 >いわゆる``Standard Model''での証明とかかな？ Standard Modelってどういうことですか？ 漏れが勉強してないのはわかってるんですが、 検索したらえらいことになっちゃいました。 539 名前：77 mailto:sage [04/08/21 23:38] >>538 「安全性の証明に、ランダムオラクルのような強い仮定を必要としない」 ということです。 が、その場合でもやっぱりコリジョンはまずいのかな？ 540 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/22 17:15] >>532 そうでふ、素因数分解されると困ります。 やはり、大きな素数を作らないといけないですか。 梅署名では、法とする数nとある数の平方根r(=R^1/2)が素である時に、 rを示すことなくRの平方根を知っていると証明できるのですが、 なにか暗号的に意味のあることですか？ あと、他の方法でRの平方根を知っていると証明できたりしますか？ 541 名前：白シャツ mailto:sage [04/08/23 19:21] >>539 サンクス。そういうことですか。 コリジョンが起こると仮定すると よりStandard Modelより弱い仮定？ >>540 大きくても素因数分解されやすい素数はある。 こういう場合はCo-Sophie Germain素数の積を使うのが一般的。 q=2p+1がともに素数のときpをSophie Germain素数、 q=をCo-Sophie Germain素数と言う。 ただし後者の呼称はあんまり一般的じゃないかもしれない。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef