暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 321 名前：白シャツ [04/07/21 15:18] >>320 >＞eの条件って、a*e>n、x*e>n　以外ないの？ >gcd(e,n)=1です。 それは>>276に書いてあるんでそういうこと聞いてるのではない． >e1=a*e-n*p >e2=x*e-n*q >とできます。 >p≠qですからちがうと思います。 a<n,x<n,e<nでe1,e2をそのようにとれるようなeって どうやって決めるの? 322 名前：白シャツ [04/07/21 15:21] >>321 >a<n,x<n,e<nでe1,e2をそのようにとれるようなeって e<nは無かった，失礼 323 名前：白シャツ [04/07/21 15:47] >>397 で言った >GCD(e1+k*n,e2+k*n)=e は誤爆ですね．もともと考えていたのは >>320 でどぶろく氏がいってるやつを叩く方法． GCD(e1+p*n,e2+q*n)=e になるような(p,q)が簡単に決まらないのかなと． これが安全になるようなeの条件が知りたい． とか思ってるうちにp=qじゃねーのと勘違いしました．スマソ． 324 名前：白シャツ [04/07/21 15:57] 漏れもどぶろく並にダメ書き込み連発してるな(w 投稿前に入念な査読をせねば． 325 名前：白シャツ [04/07/21 16:07] >>323 GCD(Π_p(e1+p*n)，Π_q(e2+q*n))もやってみる価値はありそうじゃない? 326 名前：１３２人目の素数さん mailto:sage [04/07/21 16:08] >>325 ない。 おまえら逝けよ 327 名前：１３２人目の素数さん mailto:sageうぜえ消えろ [04/07/21 16:20] 316=318の夏厨 誰も構ってくれないんで一人で壊れだすの図>>326 328 名前：１３２人目の素数さん [04/07/21 16:27] だああああああ。 >>320 > eのビット数をnと同じくらいのビットにすれば > e*((a*M1)+(x*M2)) > n　はいえます。 だから、それは、296で言ってるっつーの。 e*((a*M1)+(x*M2)) > nが言えて何が嬉しい？ そりゃ、おまえ、暗号化するやつが、秘密鍵まで知ってるぞ。 どぶろくが言いたかったのは、(M1*e1)+(M2*e2)　> n　だろ？ 話にならん。 こんなん考えてるより ・数式を正しく理解出来ない。 ・数式を正しく表現出来ない。 ・人の話をそもそも聞いていない。 の三拍子揃った人でも受け入れてくれる暗号のえらい先生を捜す方がいいんじゃないか？ むかつくと思うが、それなら余計、もうちょっと基礎からなんとかしろ。 言っておくが、これは些細な問題じゃない。 きちんと数式を評価出来てないために起こる、暗号系の穴を指摘しているんだ。 329 名前：素人な達人 [04/07/21 16:30] ってかわかんねぇ。 330 名前：梅どぶろく ◆rM4QWlepe6 mailto:sage [04/07/21 16:31] >>328 >e*((a*M1)+(x*M2)) > nが言えて何が嬉しい？ (M1*e1)+(M2*e2)　> nが言えるからうれしい だってさeはnと同じビット数としてとるんだよ？ a,xはnの半分くらいのビット数だから 問題ないよ 自分で考えてみて 331 名前：１３２人目の素数さん [04/07/21 16:37] もう一度だけ言う。 e1 ≠ a * e e2 ≠ x * e であり、なおかつ、 e*((a*M1)+(x*M2)) > n から (M1*e1)+(M2*e2)　> n が言えると、主張するんだな？ 332 名前：331 [04/07/21 16:54] と、思ったら、330のトリップ変わってるじゃないか。 すまん、どぶろく、別人だったら誤爆した。 328と今までの流れを読んでも間違いに気が付いていないなら、諦めるところだったが、 別人なら、しょうがない。すまんかった。 釣られちまったよ。。。orz 333 名前：白シャツ [04/07/21 17:09] >>332 >>115-116で同一人物との申告があるけどこれ本当かな? 334 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 19:09] >>332>>333 本物です。typoしちゃったんです。 >>331 >e1 ≠ a * e >e2 ≠ x * e >であり、なおかつ、 >e*((a*M1)+(x*M2)) > n >から >(M1*e1)+(M2*e2)　> n >が言えると、主張するんだな？ 言えますよ。ビット数で考えてみてください。 e<nでe,nのビット数をNとします。 e1=a*e mod n e2=x*e mod n だから、e1,e2もNビットにできます。 というか、e1,e2がNビットになるようにeを調節する C=e*((a*M1)+(x*M2)) mod nと変形できる 　=(e mod n)*(((a*M1)+(x*M2)) mod n) ここで、(a*M1)+(x*M2) について考える (a*M1)+(x*M2)<nとなるようにnを選んでいる >>282の1-7行辺りより a,x,M1,M2 とnのビット数の比は約1：2 ∴a,x,M1,M2≒(1/2)Nビット (a*M1)+(x*M2) は約Nビットとなる e<n,(a*M1)+(x*M2)<nだから (e mod n)*(((a*M1)+(x*M2)) mod n) =e*((a*M1)+(x*M2)) eはNビット,(a*M1)+(x*M2)は約(1/2)Nビットだから e*((a*M1)+(x*M2))は約(3/2)Nビットとなる これはnのビット数Nより大きい ∴(M1*e1)+(M2*e2)　> n 335 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 19:11] (M1*e1)+(M2*e2)　> n (M1*e1)は(1/2)Nビット数とNビット数の積だから (3/2)Nビットになる 336 名前：１３２人目の素数さん mailto:sage [04/07/21 19:17] お願いだから、どっかにHTMLで成形してUPしておくれやっし 337 名前：１３２人目の素数さん mailto:sage [04/07/21 19:22] >>336 それするなら、訂正ごとに別バージョンとしてUP 旧バージョンも保存して公開しておいてほしい 338 名前：１３２人目の素数さん mailto:sage [04/07/21 19:38] 出たよ、脳内仕様変更 >>320にははっきりと > eの条件はgcd(e,n)=1だけですから と書いてある。 でも334では、 > だから、e1,e2もNビットにできます。 > というか、e1,e2がNビットになるようにeを調節する と書いてある。 こういうのをｅの条件って言うんだ、わからんのか。 ちなみにランダムにｅを取ったときに条件を満たすｅが取れる確率はちゃんと評価したか？ 限りなく1に近いなら、まだ許そう。ざっと見積もって1/16だぞ？ こんな特殊な条件を > 自分で考えてみて の一言ですませる気だったのか。 しかも、何事もなかったように「言えますよ」とはなぁ…。 さらに、脳内仕様変更をいつものこととしてそれを受け入れても、334の式変形は間違ってる。 C=e*((a*M1)+(x*M2)) mod nと変形できる 　=(e mod n)*(((a*M1)+(x*M2)) mod n) ではない。 C=e*((a*M1)+(x*M2)) mod nと変形できる 　=((e mod n)*(((a*M1)+(x*M2)) mod n) mod n) だ。だから、それ以降の証明も本質的なところで大嘘になっている。 お願いだから、誰かも言っていたが、せめて自分の使っている式の意味ぐらい理解してから書いてくれ。 339 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 19:42] openofficeの数式エディターでupしようと思います。 使い方勉強してくるのでupはしばしお待ちください。 340 名前：１３２人目の素数さん mailto:sage [04/07/21 19:47] eもそうだけど、Mはどうなんだ？ >>300 >平文M1, M2は、(a*M1)+(x*M2)<n となるようにとる >((a*M1)+(x*M2)>0は？　M1, M2 >0 は？不明） >(与えられたa,x,n に対して平文として取れるM1, M2はどのくらいあるのか不明←重要では？） 341 名前：１３２人目の素数さん [04/07/21 19:52] >>340 Mは、 0 < M1, M2 < min(a, x)で取れば問題ないっぽい。 少なくともどぶろくの提示した条件は満たす。 暗号学的に問題がないかどうかは、この際問題ではない( w 342 名前：１３２人目の素数さん [04/07/21 19:57] むしろ、>>63の > a*d1-x*d2=1となる > 自然数で最小のd1,d2を求めておく が、曖昧。 d1が最小になるのか、d1+d2の和が最小になるのか、d1*d2が最小になるのか、etc. どういう解釈も出来る。どれでもいいのか？ が気になる。これが分かれば、いまんところ、仕様を補完出来るんだが。 343 名前：１３２人目の素数さん mailto:sage [04/07/21 20:02] >>342 >295じゃないの？ 344 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 20:08] >>338 一応>>282の18行目に書いておりますが、 条件は一気に最初に書くようにしたほうがいいですね。 いきなり条件だけ書いても意味がわからないと思ったので 途中途中で条件書いてました。 今度からは条件を一気に最初に書いておいて この条件についてはどこそこに説明書いてます。 って表記するようにします。 >C=e*((a*M1)+(x*M2)) mod nと変形できる >　=((e mod n)*(((a*M1)+(x*M2)) mod n) mod n) >だ。だから、それ以降の証明も本質的なところで大嘘になっている。 すいません、式変形は>>388さんの式が正しいです。 でも、eがe<nでnと同じビット数を取るときは >(M1*e1)+(M2*e2)　> n >(M1*e1)は(1/2)Nビット数とNビット数の積だから >(3/2)Nビットになる つまり、(M1*e1)+(M2*e2)　> n で納得していただけますよね？ >>340>>341 >>281の「正確には・・・」 を見てやっておくんなまし 345 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 20:10] >>342 拡張ユークリッドの互除法により a*d1-x*d2=1となる 自然数で最小のd1とd2を求めておく 346 名前：１３２人目の素数さん mailto:sage [04/07/21 20:11] Mも(M1*e1)+(M2*e2)　> n じゃなきゃいかんから、 >320, >334, >338 で話題になってるeの条件によるんだよな 結局値のとる範囲が後出しされてるんだよな プログラミングなるんなら最初に宣言したり、どの範囲でOKか意識するはずなのに 上手く動いてから、後付けで仕様のほうをブツにあわせていくタイプか？ 347 名前：１３２人目の素数さん mailto:sage [04/07/21 20:13] >>345 って言っておられますぞよ・・・ 辞書式順序か？ 348 名前：１３２人目の素数さん [04/07/21 21:32] >>344 悪いが、まだおかしい。 > 一応>>282の18行目に書いておりますが、 っていうのは、 > eはビット数がnと同じでgcd(e,n)=1になるように選べばいいから のことだよな？ e1,e2がNビットになるようにeを調節するんであって、 eをnとビット数が同じになるようにしたからと言って、 e1とe2がNビットになるわけではないぞ。 だから、 > eがe<nでnと同じビット数を取るときは > >(M1*e1)+(M2*e2)　> n > >(M1*e1)は(1/2)Nビット数とNビット数の積だから > >(3/2)Nビットになる > つまり、(M1*e1)+(M2*e2)　> n > で納得していただけますよね？ は、納得出来ない。（と、いうより、間違っている） 明らかに、e,e1,e2を混同している。 自分で作った変数ぐらい面倒見て下さい。 349 名前：白シャツ [04/07/21 21:50] >>339 できればoooだけじゃなくてpdfもあるとうれしい。 oooでコンバートできるよね。TeXで作りやがれとまでは言わないし。 oooとか入れるの面倒くさい人多いでしょ。 ふつうはPS,PDFぐらいじゃないと読んでもらえないし。 350 名前：１３２人目の素数さん mailto:sage [04/07/21 21:56] TeXで書いた。pdfにもなってる。だれか、あげるところ用意して。 でも、やっぱり、 >>345の 拡張ユークリッドの互除法により a*d1-x*d2=1となる 自然数で最小のd1とd2を求めておく の意味が分からない。「自然数で最小の」はd1にかかってるの？d2はなんでもいいのか？？？ 351 名前：白シャツ [04/07/21 22:04] 商と剰余を混同してないかな？ それでサイズの押え方がおかしいとか 352 名前：１３２人目の素数さん mailto:sage [04/07/21 22:13] ところで拡張ユークリッドの互除法ってなーに？ 普通のユークリッドの互除法とどう違うの？ 353 名前：１３２人目の素数さん mailto:sage [04/07/21 22:37] >>352 (a,b)を求めるのがユークリッドの互助法。 a*m+b*n=(a,b)となるm,nも同時に求めるのが拡張ユークリッドの互助法。 354 名前：１３２人目の素数さん mailto:sage [04/07/21 22:51] >>349 >できればoooだけじゃなくてpdfもあるとうれしい。 oooってなに？ 355 名前：白シャツ [04/07/21 23:04] >>354 OpenOffice.org→oooと省略しろとooo開発者が言ってると小耳にはさみますた。 356 名前：白シャツ [04/07/22 01:12] 核融合に閃光花火投下するぐらいかもしれないけど >>334 後半部分から抜粋 >(a*M1)+(x*M2) は約Nビットとなる >e<n,(a*M1)+(x*M2)<nだから >(e mod n)*(((a*M1)+(x*M2)) mod n) >=e*((a*M1)+(x*M2)) >eはNビット,(a*M1)+(x*M2)は約(1/2)Nビットだから 一番上と一番下で言ってること違わない？ 357 名前：白シャツ [04/07/22 01:42] 計算しましょう。 >>320の表記にしたがって e*a=e1+n*p e*x=e2+n*q　　とする e*((a*M1)+(x*M2))=e*a*M1+e*x*M2 =(e1+n*p)*M1+(e2+n*q)*M2=(M1*e1+M2*e2)+(M1*p+M2*q)*n ではない？ >>334で >∴(M1*e1)+(M2*e2)　> n なのはn,e1,e2がNビット(ただしe1<n,e2<n)、 M1,M2がN/2ビットとの条件からでしょう。 358 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 05:47] >eはNビット,(a*M1)+(x*M2)は約(1/2)Nビットだから これはこっちが間違ってます。 (a*M1)+(x*M2)は約Nビットだから こっちが正しいです。 約(1/2)Nビットなのはa,x,M1,M2のビット数です。 359 名前：１３２人目の素数さん mailto:sage [04/07/22 06:30] ａ，ｂが互いに素な正の整数のとき 整数ｘ，ｙがａｘ−ｂｙ＝１を満たしているならｘが増えればｙも増えるので ０≦ｘ，０≦ｙ，ａｘ−ｂｙ＝１という条件を満たすもので ｘが最小になるものとｙが最小になるものとｘ＋ｙが最小になるものと ｘｙが最小になるものは全て同じ。 360 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 09:08] 具体例で説明します。 ここでは、e1,e2の大きさや (e1*M1)+(e2*M2)>nは考慮していません。 Aliceはまず、gcd(a,x)=1となるa,xを適当に決める ここでは a=113,x=167とします。 つぎに、 (a-1)*(a+x)<n　かつ　gcd(a,n)=1 gcd(x,n)=1 となるようにnを決めます。 ここでは、(113-1)*(113+167)=31360<nとなる nとしてn=58061にします。 gcd(e,n)=1となるようにeを決めます。 ここではeとしてe=37480を選びます。 次に公開鍵を作ります。 e1=a*e mod n =113*37480 mod 58061 =54848 e2=x*e mod n =167*37480 mod 58061 =46633 今度は秘密鍵を作ります。 e*d=1 mod n 37480*d = 1 mod 58061 となるdはd=30702となります。 a*d1-x*d2=1 113*d1-167*d2=1となる 自然数で最小のd1,d2のペアは (d1,d2)=(34,23)になります。 361 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 09:10] 公開鍵は n=58061 e1=54848 e2=46623 秘密鍵は a=113 x=167 d=30702 d1=34 d2=23 になります。 BobはAliceから公開鍵を聞きました。 平文として (M1,M2)=(104,76)を送ってみます。 暗号化の式は C=(e1*M1)+(e2*M2) mod n C=(54848*104)+(46623*76) mod 58061 =14214+2387 mod 58061 =16601 BobはAliceに暗号文16601を送ります。 復号の式は M'=C*d mod nだから 　=16601*30702 mod 58061 　=24444 M1=M'*d1 mod xより M1=24444*34 mod 167 　=104 M2=a-(M'*d2 mod a)より M2=113-(24444*23 mod 113) 　=113-(37) 　=76 ∴Aliceは 平文(M1,M2)=(104,76)を得ることができました。 362 名前：１３２人目の素数さん [04/07/22 11:13] >>359 うん、そうだね。 実際計算してて気が付いた。 363 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 12:44] 梅暗号の安全性の証明を 一般化するとこんな感じかな？ A=a*k mod n X=x*k mod n としてA,Xが与えられるときに gcd(a,x)=1,gcd(a,n)=1,gcd(x,n)=1 かつ a<x かつ (a-1)*(a+x)<nを満たす a,xを求めるのは困難か否か？ (a=1,2は除く) 梅暗号としては A=a*k mod n X=x*k mod n としてA,Xが与えられるときに gcd(a,x)=1,gcd(a,n)=1,gcd(x,n)=1 かつ a<x かつ M_min*(a+x)<n M_max*(a+x)<n かつ M_min<a,x M_max<a,x を満たす a,xを求めるのは困難か否か？ (※このレス中で出てくる数はすべて自然数です) 364 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 12:48] >>348 ううう、>>334の12-16行目辺りを見て下さい。 >e<nでe,nのビット数をNとします。 >e1=a*e mod n >e2=x*e mod n >だから、e1,e2もNビットにできます。 >というか、e1,e2がNビットになるようにeを調節する 　 　 　 　 　~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 365 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 12:53] なんどもすいません。 >というか、e1,e2がNビットになるようにeを調節する これは、eの値を調節するのであってビット数を調節するわけではありません。 あくまでも、eのビット数はNのままで2^(N-1)〜(2^N)-1の間の値を e1,e2がNビットとなるようにとるってことです。 366 名前：１３２人目の素数さん mailto:sage [04/07/22 13:03] ホント何度も何度もすいません。 >>363の >A=a*k mod n >X=x*k mod n >としてA,Xが与えられるときに これは A=a*k mod n X=x*k mod n としてA,X,nが与えられるときに こっちに修正です。 367 名前：１３２人目の素数さん mailto:sage [04/07/22 13:25] 最初に与えたeを後で調整し直すのは感心せん 数学的にも実用的にも 368 名前：１３２人目の素数さん mailto:sage [04/07/22 18:21] そろそろこのアルゴリズムに対する攻撃をしてもいい？ 369 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 18:22] >>368 じゃんじゃんお願いします。 370 名前：１３２人目の素数さん [04/07/22 18:39] まず、どこかに言って発表しようって言うぐらいなら、当然先行研究に、目を通すぐらいのことはしてるって仮定する。 だから、公開鍵暗号に対するチャレンジについて一つずつ見ていこう。 参考文献として、 M.Bellare A,Desai D.Pointcheval P.Rogway Relations Among Notions of Security for Public-key Encryption Schemes 2001. をあげておく。ちょっと古いけど、まぁ、いいだろう。 定義についておかしいなと思ったときは、随時上を参照してくれ。 まず、 Semantic Secureについて。わかりやすく言うと、平文の一部がばれたことが、全体がばれることにつながらないかって感じ。 これは、どぶろく暗号CPAに対しても、弱い。 具体的には、M1がばれるとM2がばれる。これは、まずい。 例えば、 M1="私の名前は" M2="梅どぶろくです" となるということが、何らかの形で分かれば、 同じように流れている暗号文に対して、M1="私の名前は"を当てはめればM2が分かってしまう。 「そんなこと滅多に起こるもんじゃない！」 なんて考えない方がいい。実際、ヘッダーデータのように決まり文句が付いていないデータを探す方が困難だ。 だから、ヘッダーデータは分かっている(=M1がばれている)という状況はしょっちゅう起こる。 また、これをアプリケーションの実装でなんとかするのは無理だ。 もしあったら申告して下さい。それを打ち破れる反例を出します。 SS-CPA, SS-CCA1, SS-CCA2に関しては、安全でないことが示された。 この参考文献の定義ではSSとNMが同値のようだから、 NM-CPA, NM-CCA1, NM-CCA2に関しても安全でないことが示されたみたいだな。 371 名前：１３２人目の素数さん [04/07/22 18:51] 次に、Indistinguishabilityについて。 これは、二つの都合の良い平文を用意して、そのうちのどちらかを暗号化したデータをもらい、そのデータの復号文は 最初に用意した平文のうちどちらかを当てるってチャレンジ。 当たる確率が1/2に限りなく近いのが、いい暗号といえる。 これもCPAに対して弱いことが言える。 M1=a,M2=bのペアとM1=a,M2=b+1のペアを暗号化させれば、 Cの差がe2 < nなのでe2 か n - e2になり、どちらか特定出来る。 よって、 IND-CPA,　IND-CCA1, IND-CCA2に対しても弱いことが示された。 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を書き直して

---

---

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

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