暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 388 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 23:57] >>387 >M1が分かればM2が分かる >ってのは暗号数学的に致命的なんじゃないの？ これは RSA暗号は巨大な素数の合成数p*qが簡単に素因数分解できれば問題だ ってのは暗号学的に問題なんじゃないの？ と言っていることと似ていると思います。 これも確かに問題ですが、 じゃあ具体的にどうやって簡単に素因数分解するの？ と聞きたくなります M1が分かればM2が分かります。 確かにこれは致命的です。 具体的にはどうやってM1がわかるのでしょうか？ 教えてください。 389 名前：１３２人目の素数さん [04/07/22 23:58] >>376 > 矛盾してますよ。下のほうでは暗号用公開鍵を知らないといっているのに > 上のほうではM1,M2を暗号化できるといっている。 > 暗号用公開鍵を知っているのかしらないのかどっちなんですか？ これは、残念ながら矛盾してません。 > これは、二つの都合の良い平文を用意して、そのうちのどちらかを暗号化したデータをもらい、 > そのデータの復号文は最初に用意した平文のうちどちらかを当てるってチャレンジ。 上の方ってこれのことだと思うけど、「暗号化したデータをもらい」であって、 攻撃者が暗号化するとはどこにも書いてません。 そもそも、自分が暗号化したなら、どっちがもとの文かなんて分かるに決まってるだろ（ｗ もうちょっと、参考文献を書いている学者さんたちを信じてあげて下さい。 390 名前：白シャツ [04/07/22 23:59] >>386 私じゃなく>>350の偉い人に言ってください。 それと、 > M1,M2の平文が共に半分以上分かっている時に > M1,M2が求められるのか？ は>>387に同意で興味なし。でも半分もわかってるなら 「全数探索」とか「有意な情報からの残り部分の推測」 で逝ってしまうと悲しい。 391 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/23 00:02] >>390 >でも半分もわかってるなら >「全数探索」とか「有意な情報からの残り部分の推測」 >で逝ってしまうと悲しい。 これは全ての公開鍵暗号について言えることであって 梅暗号だけに言えることではないので なんとも返答のしようがありません。 梅暗号だけの欠点について言って下さい。 梅暗号だけに欠点があればそれについて知りたいんです。 お願いします。 392 名前：１３２人目の素数さん [04/07/23 00:19] ちょっと、冷静になって考えてみよう。 なぜ、どぶろくは、半分のビットが分かったときの仮定を考えたの？ それは、M1がパターン化されている文章で分かってしまったときでも、 ビットを分散して割り振っているから半分しか分からないぞ！っていう思考じゃなかったの？ もし、違うかったら、数学的になぜ半分わかったという仮定をしたのかを教えて下さい。 でも、一般的な最近の公開鍵暗号は、ビットの半分がばれるなんてことはない。 SSが言えるように設計されてるから、ビットの一部分でも分かるのは、全体を解読するのと同様に設計されてる。 だから、 >>390の >でも半分もわかってるなら >「全数探索」とか「有意な情報からの残り部分の推測」 >で逝ってしまうと悲しい。 は、この暗号特有の弱点と言えると思うよ。 393 名前：白シャツ [04/07/23 00:28] >>391 暗号理論といってもいろいろな分野やレイアがある。 実用段階に近いほうではINDだとかSSを議論する必要は当然ある。 規格化とか標準化とかそういう場合ね。 プリミティブの部分でやってる、数学よりの人にとっては、 SSやINDの耐性を示せればベターだけど、それが無いと世に出しては いけないというわけではない。そもそもIND-CCA2耐性を持つ新しい 公開鍵暗号なんて出来ればCRYPTOでも簡単にアクセプトだろう。 これは個人的な意見であって、異論は必ずあることはわかって言ってる。 新しい暗号考えました→暗号解析の人に攻撃される→改良する みたいになるよ。現状はまだそういうレベルに達していない。 そこで、「暗号数学」的には数学的に議論をしたいところだけど、 梅暗号の最大の欠点は考案者が自分の暗号方式を他人に伝えられないこと。 方式がきっちりフィックスしてすべての情報がそろわないと議論できない。 試験問題を解いてたら途中で変更されたら嫌でしょ。 394 名前：１３２人目の素数さん [04/07/23 00:37] >>385 あ、そうだったのか。すまん。 >>63で言ってた > んっと仮に実際に使った時に攻撃の対象となる > 脆弱性があるのか知りたいのです。 と、同じだと思ってた。 実際に使うことのないつもりのない自慰暗号だったら大丈夫、安全だよ。 僕にはM1も求まらない。攻撃しないから。 395 名前：白シャツ [04/07/23 00:47] >>394 >実際に使うことのないつもりのない自慰暗号だったら大丈夫、安全だよ。 みんなで叩いてるんだから少なくとも自慰じゃないよ。 自虐暗号か？ 396 名前：１３２人目の素数さん mailto:sage [04/07/23 01:16] >376　 これは平文をいくらか乱数で埋めることで解決できませんか？ >382　 ヘッダーをM1,M2に交互に割り振れば大丈夫でしょう。 について、 >382 > ↑のようなやり取りはあくまで、実装についてです。 > 数学的な問題ではありません。 > ここでは、実装についても考慮する必要があるんでしょうか？ って、乱数を組み込むという操作（暗号化）や入れ替えると操作（暗号化）を入れなければ 解読されやすいなら、その時点でその暗号はダメじゃんか それって実装段階でなく、理論段階での仕様だと思うが 君のほうが実装段階と理論段階を混ぜて逃げていないか？ 大体乱数入った文をどうやって解読するんだ？ 397 名前：１３２人目の素数さん [04/07/23 10:27] > 275 白シャツがLLLを適用してくれる期待age 398 名前：白シャツ [04/07/23 11:15] >>397 それ以前にこの暗号がちゃんと動くかもわからんし、 仕様をフィックスしてほしい。 正直言って適当に言ってるんで適用可能かどうか考えてないよん。 ただ、LLLをやって評価されている暗号ってのが梅暗号とアイデア的に 似てたりするんで、そういった。どぶろくは離散対数問題に帰着すると 主張しているが、それは秘密鍵特定の困難さと思われる。 平文は秘密鍵がわからなくても求まる可能性があるということを まずどぶろくに認識してもらいたいんだな。 ある意味これはナップザック系の暗号だよと。 PARI/GPかRISA/ASIRなんかで出来るはずなんで ちょっとLLL勉強しようかなと思ったりしてる。 基本的にはグラムシュミット正規直交化のすごい版だと思うんだけど、 難しそうね。詳しい人に聞いてみる予定。 とか言いながらも昨日買ったLEI代数の入門本が気になる。 399 名前：白シャツ [04/07/23 15:07] 放置するのも無責任なんだが, 現状では梅暗号のアタックはできないので 似たのが無いか調べてみた. >>65と同じグループの Title:A New Product-Sum Public-Key Cryptosystem Using Message Extension Author:Kiyoko KATAYANAGI,Yasuyuki MURAKAMI,Masao KASAHARA ttp://search.ieice.org/2001/files/e000a10.htm#e84-a,10,2482 なんだけど梅暗号が完成するとこれになるのか? 自称「八重桜暗号」なんで丁度良いかと(w ちなみ三青水さんもこれの解析してたような気がする. こういう系統すきなところとなると他には, 小木木先生のところと, 木木木杉先生のところぐらい. 三青水さんは木木先生グループのはずだし. 木公本先生のところより, 木木先生のところとか 目指した方がよいんじゃない? ＞どぶろく 400 名前：１３２人目の素数さん mailto:sage [04/07/23 15:59] なんか角の三等分家に対して議論してるみたいな状態だな 401 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/24 01:35] ttp://up.isp.2ch.net/up/02f997132edc.pdf にpdf形式のファイルをアップしました。 もし、ダウンロードできなかった人がいたら言ってください。 またupします。 上のほうにある返答については明日になってからです。 ファイル作っててくたびれました。 402 名前：１３２人目の素数さん mailto:sage [04/07/24 03:01] >>401 乙カレー 403 名前：１３２人目の素数さん mailto:sage [04/07/24 11:54] 余計なお世話だが、本名は書かないほうが・・・ 404 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/26 19:47] >>403 わかりました。 今度から本名はやめときます。 7/25に返答するといっておきながら 今まで放置ですいませんでした 7/27には必ず書きますんで さいなら〜 405 名前：１３２人目の素数さん mailto:sage [04/07/27 22:37] > 梅どぶろくさんへ あなたは、暗号の仕様というのを何か勘違いなさっていると思います。 仕様とは、曖昧なところがあってはいけません。 上の書き込みを拝見したところ、乱数を入れたり、 平文を並べ替えたりというのが暗号の仕様ではなく、 実装上の仕様だとおっしゃっているように、見えますが、 もし、そうだとすると、実装の数だけ暗号文が出来る、 互換性の全くない暗号ツール群が出来てしまいます。 仕様とは、同じ仕様を使って同じ入力が与えられれば、同じ出力が出るように書かれるべきです。 実装上の仕様というのは、途中で使う関数をどう設計するのかであるとか、 いつの段階で、乱数を生成したり破棄したりするのか等を規定するものであって、 勝手に入力値を入れ替えたり、乱数を付けたりするものではありません。 老婆心ながら、一言申し上げさせて頂きました。失礼します。 406 名前：１３２人目の素数さん mailto:sage [04/07/28 16:29] >>405 通りすがりです。 見当違いなこと言ってたらｽﾏｿ。 RSAとかも数学的な部分は同じでもいろいろな実装がある。 規格としての仕様ではなく、数学的な論理部分を固めたいということなんでは？ 407 名前：１３２人目の素数さん mailto:sage [04/07/28 17:08] 哲厨うぜ 408 名前：77 mailto:sage [04/07/28 18:24] PDFファイル取り逃したー 409 名前：１３２人目の素数さん mailto:sage [04/07/28 18:33] 27日は過ぎ去ったわけだが 410 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/28 23:53] >>392 >なぜ、どぶろくは、半分のビットが分かったときの仮定を考えたの？ >それは、M1がパターン化されている文章で分かってしまったときでも、 >ビットを分散して割り振っているから半分しか分からないぞ！っていう思考じゃなかったの？ そげです。 >だから、 >>>390の >>でも半分もわかってるなら >>「全数探索」とか「有意な情報からの残り部分の推測」 >>で逝ってしまうと悲しい。 >は、この暗号特有の弱点と言えると思うよ。 ここはM2を乱数rにしたら解決できると思います。 暗号の弱点を実装で補うと・・・ 適応的選択暗号文攻撃（CCA） むむう、↑についても考える必要はあるんですよね？ 梅暗号は公開鍵暗号といっても署名・認証が行えないので 考えなくても良いんじゃないかと思ってるんですが、 >>396 >って、乱数を組み込むという操作（暗号化）や入れ替えると操作（暗号化）を入れなければ >解読されやすいなら、その時点でその暗号はダメじゃんか >それって実装段階でなく、理論段階での仕様だと思うが >君のほうが実装段階と理論段階を混ぜて逃げていないか？ これは理論ですね。理論の欠点を実装で補っていました。 >大体乱数入った文をどうやって解読するんだ？ いや、解読できなければ問題ありません。 復号の時は上位〜ビットは乱数だから と教えておいてもらえば乱数を取り除いて平文を得ることができます。 411 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/28 23:53] >>399白シャツさん このレスを見て逃げていました。 紹介されたurlの簡単な説明文みたいなとこで Chinese remainder theoremの文字があって 梅暗号が完成すると八重桜になるといっている もしかして、二つはかぶってるというか、私のほうがぱくり？ ↑のように考えていて怖くて紹介されたとこは読めませんでした。 勇気を出してみてみたら 似てるけど公開鍵の数とかなんか違うし、まあ大丈夫か という感じで元気が出てきましたのでまた出てきました。 >>455 いま、仕様を固めています。 梅暗号の概要を実装したプログラムをupする予定です。 CUIなので使いづらいですが、 大体こんな感じの暗号なのかと感じることはできると思います。 >>409 私の脳内ではずっと26日なので問題ありません。 412 名前：１３２人目の素数さん mailto:sage [04/07/29 00:21] >>410 >大体乱数入った文をどうやって解読するんだ？ >いや、解読できなければ問題ありません。 >復号の時は上位〜ビットは乱数だから >と教えておいてもらえば乱数を取り除いて平文を得ることができます。 そうあれは、前者の解読≠アタックではなく、後者の解読＝復号の意味で書いたのです で復号者に対して、その「上位＊ビットは乱数だよ」はどうやって送るの？ １．梅暗号？　２．それとも平文のＥメール？ １だとそれが解読されにくくするため、「上位〜」を知らせるのに乱数入り梅暗号を使うと堂々巡りする ２だと、乱数を使っている意味がまったくない 413 名前：１３２人目の素数さん mailto:sage [04/07/29 00:21] >私の脳内ではずっと26日なので問題ありません。 駄目だ。こいつとはもう関わりたくない。数学的な不備なら とことんまで指摘するけど、自分から言い出した期限を 破っておいてこの言い草は人間的にどうよ？俺はもう降りるよ。 相手にするのが馬鹿馬鹿しい。 414 名前：白シャツ [04/07/29 00:38] >>411 八重桜の公開鍵ベクトルの次元が２の場合を書き下して検討してみた？ 上位互換だったら即氏。だれもパクリとかは思わないでしょう。 わざわざあんなのパクっても（以下自主規制） >>413 自分の信用をもっとも簡単に失う方法だね。 匿名掲示板ではナンデモありかもしれんが、 彼は>>401で本名さらしてしまった。 本名かどうかは検証不可能だけどね。 415 名前：１３２人目の素数さん mailto:sage [04/07/29 00:58] >私の脳内ではずっと26日なので問題ありません。 お前は糞以下だ。 416 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/29 15:55] みなさんすいませんでした。 >私の脳内ではずっと26日なので問題ありません。 これは冗談で言ったつもりでした。 気分を害された方失礼しました。 今度からはこのような不謹慎なことは言いませんので 許してください。 すいませんでした。 417 名前：77 mailto:sage [04/07/30 21:09] PDFファイルの再うｐはないのかな？ 418 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/30 22:55] ttp://49uper.com:8080/img-s/1539.zip へ再アップしました。 419 名前：77 mailto:sage [04/07/30 23:25] 受け取りました．というか名前は別に書かなくてもいいですよ． フリーメールのアカウントとって，メールアドレスだけ書いておけばいいのでは？ パッと身しか出来ないけど，セキュリティパラメータ（通常kで表す）が どれで，各処理の中身とどう関連するのかがいまいちわからないや． 420 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/02 13:27] 完成した！ いままで梅暗号を作っていました。 プログラムとソースを公開します。 使ってみてください。 あくまで、実際に暗号化・復号が行える ということが分かる程度です。 乱数の生成なんかは乱暴です。 落とせなかった人はいってください。 再アップします。 ttp://up.isp.2ch.net/up/bf2d15cf4ca5.zip 421 名前：１３２人目の素数さん [04/08/02 16:34] orz 420にあうように誰かエロい人、418を書き直して 422 名前：白シャツ [04/08/02 23:23] >>421 ソースみたけど、鍵とかのサイズが決まっただけであんまり欲しい情報入ってないよね。 平文の入れ替えとか乱数入れるとか、ここで書き込まれていたそういう仕様はどうなりました？ それと、仕様が決まれば実装して実験するぐらいはここ読んでる人だたら 出来ると思うんだけど。あ、それとアルゴリズムのチェック用には 数学用のスクリプト言語みたいなのでやっちゃう方が良くない？ 高速化とか気にしない段階だったらあんまり意味ないと思う。 mpz_で書いてるからそういうの考えてないでしょ。 本気でやるならmpn_で書かないとダメといわれたことがある。 漏れもmpz_しか使ったこと無いからあんまり言えないんだけどね。 UBASICとかPARI/GPとかRISA/ASIRとかいろいろあるでしょ。 数学家さんでもそういうのだと使ってる人多いと思うよ。 Mapleとか使えなんていわないからさぁ。 423 名前：白シャツ [04/08/02 23:29] >>422 >高速化とか気にしない段階だったらあんまり意味ないと思う。 >mpz_で書いてるからそういうの考えてないでしょ。 スマソ、GMPのことね。 鍵とかのサイズが決まってるけど、あれはどうやって決まったわけ？ とりあえず適当に選びましたってことでしょうか。 424 名前：１３２人目の素数さん mailto:sage [04/08/02 23:45] 32167976543216575761321303216489732401579451603031657576789812332665122546598798732132103214567 は素数ですか？ 425 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/02 23:59] >>442 すいません。 平文の入れ替えは無しです。 乱数を入れるのは M1,M2としていたのを 平文Mと乱数rにしました。 既存の対称鍵暗号で64bitごとに暗号化しているので rは64bitもあれば十分と思いました。 M2を乱数rにかえてaとxのビット差を大きくし、 平文・暗号文のふくらみ率を小さくしました 1088/1024≒1.0625 暗号化は C=(e1*M)+(e2*r) mod n です。 復号は M'=d*C mod n 　=d*e*(a*M+x*r) mod n M=(M'*d1) mod x です。 復号が4回の演算で行えるようになりました。 一度に暗号化する平文を8192bitとか16384bitにすれば 暗号化速度がもっともっと速くなると思います。 とりあえず1024bitもあれば十分かと。 426 名前：白シャツ [04/08/03 00:10] >>425 >平文の入れ替えは無しです。 >乱数を入れるのは >M1,M2としていたのを >平文Mと乱数rにしました。 >既存の対称鍵暗号で64bitごとに暗号化しているので >rは64bitもあれば十分と思いました。 では>>421さんのおっしゃるように仕様をPDFに反映してね >一度に暗号化する平文を8192bitとか16384bitにすれば >暗号化速度がもっともっと速くなると思います。 >とりあえず1024bitもあれば十分かと。 速度というのはそういうことでは無いと思うのだけど。 やったとしてもたぶん遅くなると思う。 427 名前：１３２人目の素数さん mailto:sage [04/08/03 01:03] >>424 321679765432165757613213032164897324015794516030316 57576789812332665122546598798732132103214567　mod 3 = 0 428 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/03 01:19] pdfファイルとソースをセットで圧縮しました。 落とせなかった人はいってください。 再アップします。 ttp://up.isp.2ch.net/up/c8dc605bbda3.zip 429 名前：１３２人目の素数さん mailto:sage [04/08/03 08:33] 仕様書とプログラムって、相違点がある場合はどちらを優先するものなのですか？ 430 名前：１３２人目の素数さん mailto:sage [04/08/03 08:49] >>429 実装が唯一無二の仕様。 仕様書は理解を助けるための補助。 431 名前：１３２人目の素数さん mailto:sage [04/08/03 09:52] >>429 自分が使う側になって考えてみるべき 一般的には最初に仕様書ありきで、 実装中の仕様不備発見や改良案が浮かべば仕様検討、 改定した仕様に従って実装を続ける 商用大規模開発をＡ社発注、Ｂ社受注でおこなうとき、 要求はＡ社、仕様書はＢ社、実装はＢ社からアウトソーシングする アウトソーシング先から「仕様がおかしかったので、不備部分はうまい具合に実装しておきました」 と言われたらおかしいでしょ >430をやって許されるのは、非商用（大学とか）の場合 小規模開発や自社開発の場合も外にはバレないだろうが良くはない つくりたい物がはっきりしてるなら仕様書くらい書けるはず 「書かない」と「書けない」は違う 432 名前：１３２人目の素数さん [04/08/03 19:28] 768755431457657534487763215469843243165987441478561569642434875434143347878097324326569324378708564215656976232126579077623670965314559775424356907765324354597234570867524323667074324587097956424254598795642434598780665243 433 名前：１３２人目の素数さん mailto:sage [04/08/03 20:09] 特定の数のならびが多すぎ 一本指で叩いてるのか？ｗ つまらん 434 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/03 22:55] 76875543145765753448776321546984324 31659874414785615696424348754341433 47878097324326569324378708564215656 97623212657907762367096531455977542 43569077653243545972345708675243236 67074324587097956424254598795642434 598780665243 mod 97 = 0 435 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/08/03 22:58] Janeの馬鹿 >>427>>434は適当に書いただけなんで ほんとに割り切れるか知りません。 8/4-7は出かけるのでここにはきません。 それではさようなら〜 436 名前：１３２人目の素数さん mailto:sage [04/08/03 23:35] 一人しかいなかったのか？ 437 名前：１３２人目の素数さん [04/08/03 23:43] >> 435 > 自分の信用をもっとも簡単に失う方法だね。 あれが実名なら、編入先の教授は嫌だろうねぇ。 もし、漏れが受け入れる立場ならこいつの発言見てたら絶対に断るよ。 ちなみに二つとも素数ではないことだけは確か。 具体的な素因数は2chレベルではもとまらんだろう。 438 名前：１３２人目の素数さん mailto:sage [04/08/03 23:44] > >>427>>434は適当に書いただけなんで > ほんとに割り切れるか知りません。 は > 26日なので問題ありません より酷いぞ、数学以前だな 439 名前：１３２人目の素数さん mailto:sage [04/08/04 00:32] UBASICで計算した結果 32167976543216575761321303216489732401579451603031657576789812332665122546598798732132103214567 =3^3*C93 768755431457657534487763215469843243165987441478561569642434875434143347878097324326569324378708564215656976232126579077623670965314559775424356907765324354597234570867524323667074324587097956424254598795642434598780665243 =3^3*89*7867*16561*1251707*C204 （C93, C204は10^7までの範囲に素因数なし） 440 名前：白シャツ [04/08/04 01:35] >>439 10^7までっていうことはテーブル使って試行割り算してるんですよね。 UBASICだったらECMが実装されてませんでしたか？ >>91の本についてたのにはECMあるんだけど、あれは特別なのかな。 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 ただ、上が仲悪い可能性が..........

---

---

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

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