暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 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を書き直して 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使えば？

---

---

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

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