暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 372 名前：１３２人目の素数さん [04/07/22 18:56] ちなみに、Indistinguishabilityは、どういう状況を想定しているかというと、 例えば信任選挙のようなもの。 ある人が、賛成に入れたか反対に入れたかを暗号用公開鍵を知ることなく知りたい、というような状況。 （有権者でない人（外国人スパイ）が、誰が、賛成したのか、反対したのかを知りたいというような状況？） まぁ、どぶろく暗号の場合、確率暗号じゃないから、取りうる値の範囲が狭かったら一瞬でCPAの餌食だけどな。 373 名前：１３２人目の素数さん [04/07/22 19:05] 最後に、OneWayness 暗号文から平文が分からないっていう最も基本的な所で、 これが、あっさり言えないなんてなったらつまらんから、普通は最後に評価する。 多分、上でどぶろくがやっていた安全性評価ってのはここのことだろう。 これの安全性を示す前に、確認しておきたいことがある。 CCA（選択暗号文攻撃）を行なっているときに、あるCに対して与えたM1,M2の範囲を満たさないM1とM2が出てきた場合、 復号oracleはなんて答えるんだ？ この仕様を見ると、無理矢理範囲を満たさないM1,M2を平文として返すようにしか見えないんだが。 374 名前：白シャツ [04/07/22 21:48] ところでまとめてUPするという話はどうなった？ 375 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 22:14] >>370 >だから、ヘッダーデータは分かっている(=M1がばれている)という状況はしょっちゅう起こる。 だったら、ヘッダーを暗号化しなけりゃ良いじゃん　と思った。 つーか、受信者もどの公開鍵暗号方式・鍵で暗号化しているのか知ってなきゃいかんから ヘッダーを暗号化されても困ると思う。 どの公開鍵暗号方式・鍵で暗号化しているのかわかっていればヘッダーをつける必要もない >Semantic Secureについて。 >わかりやすく言うと、平文の一部がばれたことが、 >全体がばれることにつながらないかって感じ。 >これは、どぶろく暗号CPAに対しても、弱い。 >具体的には、M1がばれるとM2がばれる。これは、まずい。 たしかにそうなんですよね。M1全てがばれればM2もばれます。 これは、ある値を暗号化したいときに 奇数番目にあるビットはM1に、 偶数番目にあるビットはM2に、 という風に割り振れば解決できます。 こっちの方が本質の問題 M1,M2の一部は共に半分以上分かっているときに平文M1,M2がばれるかどうか ↑のときはどうでしょうか？ 376 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 22:14] >>371>>372 >また、これをアプリケーションの実装でなんとかするのは無理だ。 >もしあったら申告して下さい。それを打ち破れる反例を出します。 これは平文をいくらか乱数で埋めることで解決できませんか？ というか、梅暗号の場合そうしないといけないんです。 一度に送れる平文は少なくなりますが・・・ 平文→暗号文は平文に対して乱数を64ビット程度埋める予定です。 つまり、一度に暗号化する平文の量が多ければ多いほど、膨らみ率は小さくなります。 >ある人が、賛成に入れたか反対に入れたかを暗号用公開鍵を知ることなく知りたい、というような状況。 矛盾してますよ。下のほうでは暗号用公開鍵を知らないといっているのに 上のほうではM1,M2を暗号化できるといっている。 暗号用公開鍵を知っているのかしらないのかどっちなんですか？ >CCA（選択暗号文攻撃）を行なっているときに、 >あるCに対して与えたM1,M2の範囲を満たさないM1とM2が出てきた場合、 >復号oracleはなんて答えるんだ？ C>nとなるCを与えても、 C mod n の値を復号するのと同じことになるので 考慮する必要ないと思います。 C<nならM1,M2の範囲を満たすM1,M2がでてきますので・・・ >M1,M2の範囲を満たさないM1とM2が出てきた場合、 これは絶対にありません。100％です。断言します。 M1=M'*d1 mod x M2=a-(M'*d2 mod a) です。 mod a,xがあるので大丈夫です。 377 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 22:19] >>374 まだ、勉強してます。 あと、今度東京に行くので もしどなたかが8/6に都合のいい場所と時間を指定してくれれば そこで説明しようとも思ってんですけど 378 名前：白シャツ [04/07/22 22:34] >>377 そもそもここ見てる人が東京の人とは限らんが、 良い日を選んだな。 ここへ行け ttp://www.21coe.chuo-u.ac.jp/security/event/20040806-0808/200408.htm 379 名前：白シャツ [04/07/22 22:39] >>378 念のために言っておくけど、漏れが行くかどうかは未定。 だれか聞いてくれる暇な人がいるかもしれないと言う事。 「読める状態の何か」を作って配らせてもらうことぐらいは 頼めるんじゃない？ 許可されるかどうかは聞いてみないとわからんけどね。 380 名前：１３２人目の素数さん [04/07/22 23:09] >>375 > だったら、ヘッダーを暗号化しなけりゃ良いじゃん　と思った。 なんか、大きな勘違いをしているとおもうんだが…。 どぶろくの中のヘッダーデータというのは、暗号方式を規定したものだけでしかないようだが、 もっと一般的なものであることは、文章を読めば分かると思うんだが…。むしろ、暗号方式を規定したヘッダなんてどこにもかいとらん。 Macバイナリにしかり、Bitmapのヘッダにしかり、TCPのコネクションをはる初期化プロトコルにしかり。 それとも、決まり文句が入っている平文は、暗号化しないで下さい、って暗号なの？ それって、実用として全く使えないな。 381 名前：１３２人目の素数さん mailto:sage [04/07/22 23:15] 「あいつは必ずメールの末尾に署名いれてくるから、他のところに出してるメールも同じだろう。」 ということですな。 確かに、それが弱点となってしまうようでは実用として使えないな。 382 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 23:16] >>380 ヘッダーについては勘違いしてた。 暗号の種類を記したものだけだと思ってた。 ヘッダーについては、 ヘッダーをM1,M2に交互に割り振れば大丈夫でしょう。 M1,M2の平文が共に半分以上分かっている時に M1,M2が求められるのか？ ヘッダーの問題については↑の問題を考える必要があります。 考えてみてください。 383 名前：１３２人目の素数さん [04/07/22 23:29] >>376 >また、これをアプリケーションの実装でなんとかするのは無理だ。 >もしあったら申告して下さい。それを打ち破れる反例を出します。 これは平文をいくらか乱数で埋めることで解決できませんか？ というか、梅暗号の場合そうしないといけないんです。 こういう仕様変更は、弱点を指摘される前に言ってね。 そんなのばっかりで、ちょっとうんざりしてるんで。 で、具体的には、どういう乱数で埋めるの？ 384 名前：白シャツ [04/07/22 23:30] >>377 ところで、 >>350　の偉い人に >>127　でアップしたところを使ってもらうことはできるんですか？ >>350の書いて下さったの見たい。 385 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 23:39] >>383 仕様変更というか実装を考慮した時には 乱数で埋めなきゃいけないってことなんですけど。 数学的な問題と実装についての問題は分けて考えてもらえませんか？ M1全てが分かればM2が分かる これはM1,M2に平文のビットを交互に割り振ればいい ↑のようなやり取りはあくまで、実装についてです。 数学的な問題ではありません。 ここでは、実装についても考慮する必要があるんでしょうか？ 実装についての問題ならどうとでもなります。 それに対応する解決方法もたくさん考えられているわけですから 実装ならプログラム板向けだと思いますが？ >で、具体的には、どういう乱数で埋めるの？ M1,M2の先頭に乱数をつけてやればいいと思います。 何度も書いてますが、 M1,M2の平文が共に半分以上分かっている時に M1,M2が求められるのか？ これについて答えてください。 386 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 23:46] >>384さん ttp://up.isp.2ch.net/upload/c=01owarai/index.cgi というのがあります。 5MBまでのようですが。 387 名前：１３２人目の素数さん [04/07/22 23:50] うん、だから、M1とかM2のビットを交互とか全く関係なく M1が分かればM2が分かる ってのは暗号数学的に致命的なんじゃないの？ と、指摘している。 もし、数学的にこの問題を解決するなら、Cの構造を変えるしかないんじゃない？ > M1,M2の平文が共に半分以上分かっている時に > M1,M2が求められるのか？ これが、ビットを割り振った実装上の問題でしょ？ ちなみに、これが求まるかどうかには私は興味はありません。 他の所から攻撃するんで。 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とｎだけ公開する署名スキーム考えれば良いよね。 このまま適用しようするとだけだとダメだろうけど。

---

---

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

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