暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 96 名前：63 ◆oYI7WOcH/A [04/07/07 09:45] >>95 誤解のないように補足 Cの値が一定にならない確率暗号みたいな仕様を目指しているのかなと思ってた。 でも、際限なく増えていくので、これはあんまり良くないな。 97 名前：63 ◆oYI7WOcH/A mailto:sage [04/07/07 10:08] で、 >>94 、そんなのどこに書いてあったんだ？ もしかして、 >M→C'は問題ないと思いますので の一行に、>>94のような変換ぐらいがあるのは予測しろ！ って思いが込められてるのか？ それ以前に、 >>53の >(x,y,z,wは0以上の整数、Mの範囲は0<=M<Lとする) と >>94 >すると暗号化前の平文は >2^n〜2^(n+1)-1になります は、矛盾してるんだが、仕様としてこれでいいのか？ >大丈夫です心配要りません って、吊られてたのか！！！ 98 名前：白シャツ [04/07/07 12:06] >>93 >PCP…ゼロ知識系の、ブラックボックスやオラクルを使用した >計算やプロトコルのモデルがどーたらこーたら…とか？ アノ本そういうこと書いてあるんだ。買う。 暗号の応用にはあんまり意味無いんだけど、 ”バカ査読者のご機嫌伺い”には役に立つ。 などと愚痴ってみる。 >>95 「C=aX=bY=cZ=dW」 のもっとも自明な解がC=0じゃないのと思ったんだけど、 やっぱりそういうようになるのね、仕様では。 >でも、際限なく増えていくので、これはあんまり良くないな。 そうだったのか。ちゃんと読んでないんで R_Lで4次元の巡回シフトみたいなことするんだと 思ってたけど、ちゃんと読んでみないとだめですね。 99 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/07 14:57] >>97 すみませんです。 >>94見たいな事はどこにも書いてありません。 強いて言うなら私の脳内には書いてありました。 >それ以前に、 >>>53の >>(x,y,z,wは0以上の整数、Mの範囲は0<=M<Lとする) >と >>>94 >>すると暗号化前の平文は >>2^n〜2^(n+1)-1になります >は、矛盾してるんだが、仕様としてこれでいいのか？ んっとですね、 >>(x,y,z,wは0以上の整数、Mの範囲は0<=M<Lとする) は、アルゴリズムを数学的に考えた場合には 0<=M<Lの範囲で取れます。 M=0のときC=0になったり M=L-1のときC=L-1になったりするので 実装しようとしたら>>94のように 平文として使えるMの範囲を絞ってやるということです。 余りとかはこっちでは増加してるけど こっちでは0になったぞ見たいにぐちゃぐちゃなのが理想なんですが、 Mの値が最小の基数よか小さいときは a',b',c',d'が単調に増加のみをしてしまうってのがあったので すべての平文に2^nを加算することにしました。 >って、吊られてたのか！！！ 釣ってるつもりはありませんでした。 100 名前：63 ◆oYI7WOcH/A [04/07/07 16:36] >>99 分かった、じゃあ、ここは脳内仕様を採用しよう。 でも、さすがにこれ以上脳内仕様ですと言われたら考える気も起こらなくなるから、 今脳内にある仕様をまず提示してね。 まず、アルゴリズムとしては、かなり問題があるってことは、自分で認めてるからいいよね？ ある特定の値を与えたら、全然暗号にならないってのは、アルゴリズムとしてはダメだ。 まぁ、これは、DESなんかでも、特定の弱い鍵ってのがあってそれを排除せねばならんが、 こっちは、平文だから、さらに厳しいな。 だから、これは理論じゃなくて、実装ベースで考えるってことでいいよね？ つまり、アルゴリズムの欠陥を、実装する際の条件付加で補おうってこと。 それなら、以下のことは、最低限提案者が与えないと。 ・ｎの推奨パラメータ ・ｎが与えられたときのLを生成する確率的アルゴリズム ・推奨パラメータNにおける暗号化速度（Mbps） ・推奨パラメータNにおける使用するRAMメモリ量 Lが2^(n+2)の全てを取れるわけではないから、鍵生成アルゴリズムはとても重要だな。 後半の二つは、参考のため、2chではぼこぼこに言われている日本製の対称鍵暗号Camelliaで、 128bit鍵でPen3 650MHｚ で250〜300Mbpsで仕様RAMが32byte程度だね。 頑張れ〜 101 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/07 20:37] >>100 すいません、大幅な仕様変更があります。 ですが、これ以上の変更はありません。 んっと、今まで考えていて思いついたのですが、 Diffie-Hellman鍵交換プロトコルで二つの鍵A,Bを交換します。 そしてgcd(A,B)=Gを求めます。 A/G,B*Gをそれぞれa,bとしてL=a*bとなります。 このときはgcd(a,b)=1となります。 Lのビット数をNとするとき (N-2)/8バイト毎に暗号化して Mに2^(N-2)を加算してM'としてやります。 a,bの二つを使って M'=ax+a'=by+b' ・・・・・・以下略・・・・・ としていったらどうでしょうか？ AliceとBobはいちいちLを素因数分解をしなくてもよく A,Bの最大公約数をユークリッドの互除法で求めてやればいいわけです。 Lを素因数分解する必要もありません。 ですが、Eveは鍵候補L'を素因数分解していく必要があります。 そしてL'の基数の数がm個であるとき {Σ(k=1,m/2)　(mCk)}*2通りの組み合わせを考えなくてはなりません。 (*2の意味はa,bの順序をどうするかで2通りあるからです) これだと、仮にEveが鍵候補L'を素因数分解していって 基数全てを求めても簡単にはa,bを求めれません。 基数の数が少ない時、個々の素数の値が大きくなります。 基数の数が多いと{Σ(k=1,m/2)　(mCk)}*2の組み合わせが多くなります。 102 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/07 20:39] >>100 >・ｎの推奨パラメータ >・推奨パラメータNにおける暗号化速度（Mbps） >・推奨パラメータNにおける使用するRAMメモリ量 これは今から実際にプログラムを組んで考えて見ます。 a,bは小さい数で個数が多いほうより a,bはとても大きい数で個数は2つくらいのほうが 効率がいいとかまだ分かりませんので あと、一応イメージとしてはnは1024ビット超とか考えています。 処理速度が遅くなるかもしれませんが、 一度に暗号化できるビット数も増えるわけです。 色々実験してみます。 >・ｎが与えられたときのLを生成する確率的アルゴリズム これは改良した方法で大丈夫ではないでしょうか？ 103 名前：白シャツ [04/07/07 23:00] >>75 M→C'の写像ですが、一般のMの場合、 (a',b'c',d')→(a'+1,b'+1c'+1,d') ですね、やっぱり。ただし a',b',c',d'が０だったりするときは少々違うんですが。 詳細は考えてみて。 それで、a'とかがa-1とかだと途中でa'+1=0になるんで ややこしくなるんです。 　M ∈Z/LZ ↓ (a',b'c',d')∈Z/aZ×Z/bZ×Z/cZ×Z/dZ ただし、a'∈Z/aZ,b'∈Z/bZ,c'∈Z/cZ,d'∈Z/dZ で書いてることに注意してください。 言い方がウソと言われるかもしれんが。 今日は、次にC'→Cを考える予定。 104 名前：63 ◆oYI7WOcH/A [04/07/07 23:02] 今、気がついたんだが、63はどぶろくだなぁ…（ｗ ホントは62だが、まぁ、これから変えるのもなんなんで。 >>101 >Diffie-Hellman鍵交換プロトコルで二つの鍵A,Bを交換します。 >そしてgcd(A,B)=Gを求めます。 >A/G,B*Gをそれぞれa,bとしてL=a*bとなります。 これなんだが、あんまりよくないんじゃないかな。 まず、狙った範囲のLを出すのが難しいんじゃない？ DH鍵交換してみたはいいが、AとBがとても大きな因数を持ってたりどっちかが極端に小さかったりしたら、DHをやり直すの？ もしかして、鍵交換終えるまで、Nがいくつにならないか分かりません、とかいう新手の仕様か？ 少なくとも、これでは実装出来ないと思うよ。 特に凄まじく弱い鍵が排除しないという仕様なら、そういう風に判断するが。 例えば、1024bitで4つに分けたとしたら、DHで交換するのは、256bit程度でしょ？ これは、離散対数問題が困難とは言い切れない程度になるな。 もっと大きな値で交換して、ハッシュかなんかで変換して、っていうのなら、ちゃんとそう書かなきゃ。 もう脳内は勘弁してね。 なので、 >>・ｎが与えられたときのLを生成する確率的アルゴリズム >これは改良した方法で大丈夫ではないでしょうか？ は、全然大丈夫ではないと思います。 105 名前：白シャツ [04/07/07 23:07] >>101 >Diffie-Hellman鍵交換プロトコルで二つの鍵A,Bを交換します。 これ意味がわからない。どういうこと？ ていうか何がしたい？ >>103 >ただし、a'∈Z/aZ,b'∈Z/bZ,c'∈Z/cZ,d'∈Z/dZ これは方式で定義してありましたね。 106 名前：77 mailto:sage [04/07/07 23:48] >>98 いや、あの本にはPCPの暗号学的応用は何も載ってないです。 >>93はおいらの妄想。 107 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/08 00:18] >>104 >まず、狙った範囲のLを出すのが難しいんじゃない？ >DH鍵交換してみたはいいが、AとBがとても大きな因数を持ってたり >どっちかが極端に小さかったりしたら、DHをやり直すの？ 今実験中です。 どっちかが極端に小さければa'+1=0になる回数が多くなるわけです。 そうすれば解読するのに邪魔になると思うんですが、 なんだったらデフォルトで2,3は基数に含めるなどとしてもいいわけで >Diffie-Hellman鍵交換プロトコルで二つの鍵A,Bを交換します。 >これ意味がわからない。どういうこと？ >ていうか何がしたい？ D-H鍵交換プロトコルを二回繰り返すってことです。 省略した説明でごめんなさい。 >もっと大きな値で交換して、ハッシュかなんかで変換して、っていうのなら、ちゃんとそう書かなきゃ。 そこまで考えていませんでした。 >もう脳内は勘弁してね。 大丈夫です。もう脳内の考えは出しつくしました 新しい考えが出てくる可能性はありますけど 108 名前：白シャツ [04/07/08 00:32] >>106　とりあえず本屋でもう一回立ち読みします。 >>107 >D-H鍵交換プロトコルを二回繰り返すってことです。 L=abcdでa,b,c,dは素数の冪だったんでしょ。 A,Bを交換ってだからA,Bは何？ とりあれず出来たLの条件は最初のでOKなの？ 109 名前：63 ◆oYI7WOcH/A [04/07/08 01:49] ちなみに、DHは鍵交換ではなく、鍵共有だな。 だから、>>105,108のような疑問がわいてくる。 まぁ、とりあえず、仕様が固まったら教えてね。 上の推奨パラメータとそのパフォーマンスも。 既存の100倍ぐらいパフォーマンスと安全性が悪くても、考えてみるよ。 でも残念ながら一般的な解読法を適用した場合に、10^2倍ぐらい簡単に解けるし、 必要なメモリ量（ハードウェア実装したときは、基盤の規模に直結する）は、10^3倍ぐらいかかるし、 同じデータを暗号化するのに10^4倍ぐらい時間がかかると思う。 このめちゃくちゃな予想を、「よく」裏切るような実験データを期待してるよ。 110 名前：白シャツ [04/07/08 02:12] >>109 いや、DHで鍵共有するとして、 >そしてgcd(A,B)=Gを求めます。 >A/G,B*Gをそれぞれa,bとしてL=a*bとなります。 となってます。a,bが異なる素数の冪なるようにするなら p,qを素数として A=p^x*q^y, B=q^z かつ　y<=Z じゃないとダメですよね。 そうなるとp,qが最初から双方でわからないとダメでしょ。 意味わからん。 私も人のこと言えませんが、>>63　-1さんも奇特な人ですね。 あと>>77さんも。このスレ現状4人で回ってるような。 111 名前：63 ◆oYI7WOcH/A [04/07/08 03:11] >>110 例のアレだ。仕様変更。固まるまで待ってやれ。 奇特っていうか、暇なんだよね。トルネコ３のあいまに見てる。 何を血迷ったか、暗号解読コンテスト！とか銘打って、Certicomみたいに賞金かけたり何かしないかなぁ〜なんて。 もう少し人間的な生活をせねば。 >>どぶろく ちなみにやろうとしているのは、どぶろく暗号（勝手に命名）がいかに「ダメ」かってのを、 ・誰もがなっとく出来る理由付きで ・自分が苦労せず（計算したり査読したりせず） ・最終的にはどぶろく自身の手で 示そうってこと。 何の理由も示さず「そんなんダメだ」っていう嫌な大人は嫌いでしょ？ 悪気は…ある。楽しんでるからね。だから、指示に従う必要は全くないよ。 でも、どれも妥当（そうに見えるでしょ？）な指示・情報開示要求だから 「誰にも見向きもされないから絶対に安全な暗号」になりかねんが。 なはは、それはそれですごいかもしれん。 112 名前：白シャツ [04/07/08 03:38] >>111 仕様変更待ってたら暇つぶしができないじゃないですか(w 暇ってわりにはやけにお詳しいようですね。 ところで、 >>55　のC'→Cのアルゴリズムどおりにやると Cは0<=C<Lでおさまるのか気になるんですが、どうなってるの？ >>96 >Cの値が一定にならない確率暗号みたいな仕様を目指しているのかなと思ってた。 >でも、際限なく増えていくので、これはあんまり良くないな。 ってことなんで気になって。 これ解析する気はないし。どぶろく氏に宿題。 普通に考えたらCRTで終わりなんだけど。 113 名前：１３２人目の素数さん mailto:sage [04/07/08 03:51] 関連スレ 素数判定は「決定的」多項式時間で可能 science3.2ch.net/test/read.cgi/math/1028813059/l50 114 名前：63 ◆oYI7WOcH/A [04/07/08 04:37] >>112 >Cは0<=C<Lでおさまるのか気になるんですが、どうなってるの？ それは、mod Lで考えればいいんじゃない？ 一意性は保証されてるんだから影響を与えないでしょ。 ここは、数学家さんが考えることであって、暗号屋さんが考えることではない。 有名どころの対称鍵暗号アルゴリズムで確率暗号って聞いたことがない。 まぁ、実用上、データサイズが増えるのはよろしくないし、圧縮も効かないから扱いにくいんだろうなぁ。 公開鍵暗号系みたいに、扱うデータサイズが極小ならいいけど。 モードをECB以外にすれば、確率暗号が期待する効果を発揮出来るし。 サイズを大きくすることを上回るメリットが見えない。 折角、Mの取る範囲を制限してるんだから、完全性を判別出来るプロトコルもあれば面白いな。 今、暗号鍵とサブ鍵みたいなのがあって、 暗号鍵を知っていれば、勿論解読出来る。 サブ鍵を知っていれば、その暗号文が、（でたらめな値ではなく）正当な暗号文であるかどうかを判別出来る。 っていう系を作ることが出来れば面白いかなっと思ったが、一瞬で出来てしまった。 暇つぶしにはならんなぁ。 そもそもCRTがなぜChineseなのかが気になってしょうがない。 「昔の中国では、軍隊で人を綺麗に並べるときに使ったらしいよ」 と聞いて、そのときは、すごーいと思ったが、よく考えたら、CRTの言いたいことが、 なぜ、綺麗に並べるときに使えるのかがわからん・・・。 115 名前：梅どぶろく ◆rM4QWlepe6 mailto:sage [04/07/08 09:46] すいません、全くの別口ですが、 GCD(a, n) = G(G≠1) のとき ax-ny=1を満たす x,yを求めるのは難しいですか？ 116 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/08 09:46] ↑は私です。 トリップ間違えました。 すいません。 117 名前：１３２人目の素数さん mailto:sage [04/07/08 10:03] >>115 うん。ものすごーーーく難しい。万が一見つかったら 是非報告してくれ。 118 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/08 12:43] >>117 ・・・ 存在しないじゃないですか！！ ものすごーーーーく難しいっていったら 難しいけど、求めることはできると思って 考えていったら GCD(a,n)=G(G≠1)のとき G(Ax-Ny)=1とあらわせて Gは整数であるから x,yは存在しない・・・ やられました。 119 名前：63 ◆oYI7WOcH/A [04/07/08 14:07] >>115 とっても簡単。xに好きな値を入れて、y = (ax - 1)/nを入れればよい。 もとまったx,yがどぶろくが欲しい範囲に入ってるかどうかはしったこっちゃないが。 120 名前：白シャツ [04/07/08 22:13] 114>> >>Cは0<=C<Lでおさまるのか気になるんですが、どうなってるの？ >それは、mod Lで考えればいいんじゃない？ 脳内仕様の確認したかっただけです。 仕様はどうなった？＞どぶろく氏 L=abcdなの？　途中からL=abになってるけど。 検証の手間がかかるし後者の方が楽だけど。 零元の処理とか。 >一意性は保証されてるんだから影響を与えないでしょ。 >ここは、数学家さんが考えることであって、暗号屋さんが考えることではない。 数学家さんは最初から気にしないと思う。剰余類にはいってれば一緒だし。 ていうか、数学家さんって居なくなった？ >有名どころの対称鍵暗号アルゴリズムで確率暗号って聞いたことがない。 鍵共有で乱数つっこんで使い捨てにしたら 良いってことじゃないかな？ >そもそもCRTがなぜChineseなのかが気になってしょうがない。 孫子算経に載ってたらしい。孫子が考えたかどうかは謎だけど。 121 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/08 23:09] >>120>>114 すいませんです。 一人で実験してみたのですが、 大きな数a,bのとき やたら下位ビットが規則的に並んでいます。 これはあきらかな弱点です。 お恥ずかしい話ではありますが、 最初どおりa,b,c,dとして 基数は複数用いるということでお願いします。 >>112 問題なしです 0<=C<Lに収まります。 C=ax+a'=by+b'=cz+c'=dw+d' CはCをa,b,c,dで割った時の余りとして表現されています。 a,b,c,dの余りで表現できるのはabcd-1までです。 んんっとここが、最大の弱点であるわけです。 攻撃者は選択平文攻撃ででてきた Cの最大値より大きい値が鍵Lと予想できます。 122 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/08 23:24] >>115の発言についてですが、 公開鍵について考えていました。 C=E*M(mod　n) M=D*C(mod　n) M=E*D*M(mod　n)={E*D(mod　n)}+M(mod　n) 　=M(mod　n) とするにはE*D(mod　n)≡1にすればいい。 Eが求まるときにDを求めるのは簡単、 しかし、E,nの分かる解読者にとっても簡単 (E*D)^x≡(E^x)*(D^x)≡1　(mod　n)として、 e=E^x,d=D^x(mod　n)がgcd(e,n)≠1となるようにすれば 解読者はeの値からdの値を求めるのが難しい！ やった、新しい公開鍵暗号ができたんじゃないかしら とおもって、>>115>>118のような発言にいたりました。 まあ結局は>>118にあるように無理だったんですが・・・ 123 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/08 23:26] 私ごときが言うのもなんですが、 あらためてRSAのすごさを認識しました。 124 名前：白シャツ [04/07/08 23:46] >>121 >大きな数a,bのとき >やたら下位ビットが規則的に並んでいます。 >これはあきらかな弱点です。 Why? >問題なしです >0<=C<Lに収まります。 >C=ax+a'=by+b'=cz+c'=dw+d' >CはCをa,b,c,dで割った時の余りとして表現されています。 >a,b,c,dの余りで表現できるのはabcd-1までです。 0<=C<Lで一意に表現可能であるのは最初からわかっている。 C=ax+a'=by+b'=cz+c'=dw+d'を満たすCは無数に存在するけど。 >>55のアルゴリズムで0<=C<LなるCが求まるかが問題。 普通はCRTで計算するのはわかった？ >んんっとここが、最大の弱点であるわけです。 >攻撃者は選択平文攻撃ででてきた >Cの最大値より大きい値が鍵Lと予想できます。 どういうこと？ >>122 RSAの指数部みてみなよ。 125 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/09 00:21] >>124 >>>55のアルゴリズムで0<=C<LなるCが求まるかが問題。 求まらなかったらmod　Lすればいいので問題なし >>>122 >RSAの指数部みてみなよ。 いや、何百桁もある数を何百桁乗もしているのは分かっています。 仮に、おまえもどんなのでもいいから公開鍵暗号を作ってみろ といわれても、わたしにはできません。 それに、RSAは他の公開鍵についての情報がまったくなく 0から作り上げた暗号としてとてもすごいと思っています。 私が考える場合は既存の公開鍵暗号を参考にすることもできるわけです。 それでも、橋にも棒にもかからない不可能を証明できるような暗号しかできないのです。 >>んんっとここが、最大の弱点であるわけです。 >>攻撃者は選択平文攻撃ででてきた >>Cの最大値より大きい値が鍵Lと予想できます。 >どういうこと？ 0<=C<Lですから、適当にMを代入して出てきた Cより小さい値は絶対Lにならないってことです。 ランダムにMを代入してみてCを集めていくと・・・ Lの候補がすこし絞れてしまう・・・ なんてことになると思ってますがどうでしょうか？ 126 名前：白シャツ [04/07/09 00:48] >>125 >求まらなかったらmod　Lすればいいので問題なし えと、それは良いのだけど、CRTは調べた？ >いや、何百桁もある数を何百桁乗もしているのは分かっています。 >仮に、おまえもどんなのでもいいから公開鍵暗号を作ってみろ >といわれても、わたしにはできません。 そういうことではなく、RSAの指数部は>>122のアイデアと一緒。 RSAとてそういう単純なことなんで コロンブスの卵は偉大だが、がんがれってこと。 >それに、RSAは他の公開鍵についての情報がまったくなく >0から作り上げた暗号としてとてもすごいと思っています。 DHってかわいそうだと思いませんか？ 本来もっと評価されても良いはず。 >ランダムにMを代入してみてCを集めていくと・・・ >Lの候補がすこし絞れてしまう・・・ >なんてことになると思ってますがどうでしょうか？ その攻撃に意味があるのかどうかわからないんですが。 127 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/09 01:05] >>>121 >>大きな数a,bのとき >>やたら下位ビットが規則的に並んでいます。 >>これはあきらかな弱点です。 >Why? do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1088921677 に実験結果をupしてます 見てみてください。 以下一例 3e-3d =1631f819d3e2bfe8-1631f819898f0764 =4A53B884 3d-3c =1631f819898f0764-1631f8193f3b4ee0 =4A53B884 54e-54d =92dbb8db5c15831-92dbb8d6b6d9fad =4A53B884 ってなるんですがだめですよね？ 128 名前：白シャツ [04/07/09 01:21] >>127 聞き方がまずかった。 何がやりたくて何をやったかサッパリわからない。 結果だけ出されてもわからないでしょ。 それと、M→C'は平文に制限のあるカエサル暗号みたいだから、 この部分を真カエサル暗号にしてC'→Cでカエサル暗号を強化 しました、みたいなのを提案するとずっと受けは良いと思うんだがどうよ？ まぁ次回作のプランってことでよいか。 129 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/09 01:29] >>127 基数の数が2つの場合にどうなるかを調べたんです。 そしたらずっと規則的に差が一緒だったので やはり基数は複数個用意したほうが良いという結論に達しました。 130 名前：63 ◆oYI7WOcH/A [04/07/09 02:26] 少し現実世界に戻ろうとリハビリを始めていたら、 あまり面白くない方にスレが進んでるね。 >>127,129 いや>>124は、How?ではなく、Why?と聞いてるわけだが。 131 名前：白シャツ [04/07/09 02:41] >>130 Why?で埒が明かんのでHow?を聞きたかったんだけど、 >>129　の結論に達したみたいです。 Howも不明ですが、納得することにしました。 132 名前：１３２人目の素数さん [04/07/09 07:07] 数学も流行病に侵されるようになったんだね。 暗号の数理も、今のように大勢が群がってやらねばならないような 分野なんかじゃ無いはずだ。細く長く根気良く続けるのならともかく。 133 名前：63 ◆oYI7WOcH/A [04/07/09 16:59] >>132 数学者が群がっているわけではないのが、救いかな。 確かに、情報セキュリティのかけらも分かってない数学者が、 実用性のないイタい暗号系を作っているが、まぁ、もう、ブームは過ぎたと思うよ。 またすぐに流行とは無縁な世間から隔絶された数学の世界に戻るよ。 134 名前：白シャツ [04/07/09 20:10] >>133 >数学者が群がっているわけではないのが、救いかな。 「漏れは純粋数学者」てなプライドの壁を越えられない人が多い。 と一線を越えてしまった数学者に愚痴られました。 135 名前：１３２人目の素数さん mailto:sage [04/07/09 23:50] もうお嫁に行けない！ 136 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/10 15:46] >何がやりたくて何をやったかサッパリわからない。 >結果だけ出されてもわからないでしょ。 やりたかったのは 巨大な互いに素である数の積をLとした時に 平文と暗号文の間になんらかの関係があるか調べたかったのです。 そして実験をしてみて 暗号文には偏りが生じていると思いました。 >why? 暗号では雪崩効果が必要と読みました。 差が一定なのも問題だと思っています。 どこかで差が変わると思うのですが そこを攻撃されるとLの要素であるa,bが推測されやすくなると思います。 137 名前：１３２人目の素数さん mailto:sage [04/07/10 18:18] やっぱりある程度の数学的素養がないと辛いんでないかな。 遠回りのようだけど代数系の基礎から一通りやったほうがいいかも 138 名前：１３２人目の素数さん mailto:sage [04/07/10 19:06] どぶろくさんへ質問 >C'=(((dd+d")c+c")b+b")a+a" >となります。 >a,a",b,b",c,c",d,d"を用いて >C=aX+a"=bY+b"=cZ+c"=dW+d"(X,Y…同上) >となるCを求めます。 X, Y, Z,, Wの求め方が同上では分かりません ここもそこまでの部分と同じように文章にしてください 139 名前：１３２人目の素数さん mailto:sage [04/07/10 19:17] もう一個質問 >cZ+c"=dW+d"…壱 >となる最小の値を(cd)"とします。 最小となる「何の」値を(cd)''とするのですか？ 他の最小とかいてある部分も。 読み解く必要が無いような記述でお願いします。 140 名前：138=139 mailto:sage [04/07/10 20:05] >cZ+c"=dW+d"…壱 >となる最小の値を(cd)"とします これって 　等式 壱：cZ+c''=dW+d'' を満たすようなZ,Wを 　cZ+c'' （=dW+d'') が最小になるようにとり、 　またそのときの cZ+c'' (=dW+d'') の値を (cd)'' とする ということでいいかな？てことは >C=aX+a"=bY+b"=cZ+c"=dW+d" >となるCを求めます ってのは、これらの等式が成りたつようなX,Y,Z,Wを Cが最小になるようにとるってことでいい？ そうなら、a,a'',・・・,d,d''からC,X,Y,Z,Wを求めるということかい？ どちらにせよ「X,Y…同上」の何が同上か分からん・・・ 141 名前：138 mailto:sage [04/07/10 20:12] 連続ですまんが>140は違うみたいね 142 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/10 23:04] >X, Y, Z,, Wの求め方が同上では分かりません >ここもそこまでの部分と同じように文章にしてください ほんとすいません求め方が同じというわけではなく M=ax+a'=by+b'=cz+c'=dw+d' (豆数a,b,c,dの余りで表現できる数は0からL-1です) (x,y,z,wは0以上の整数、Mの範囲は0<=M<Lとする) C=aX+a"=bY+b"=cZ+c"=dW+d"(X,Y…同上) は、上にあるようにX,Y,Z,Wの範囲が同上(X,Y,Z,Wは0以上の整数) といいたかったのです。 レスをまたがってしまってすみません >最小となる「何の」値を(cd)''とするのですか？ 最小となる正の数を(cd)"とする です。 143 名前：138 mailto:sage [04/07/10 23:34] a,b,c,dは最初に用意しておく Mが与えられたとする a', b', c', d', x, y, z, w は M, a, b, c, d から計算で求まる C' は a, b, c, d, a', b', c', d' から計算で求まる aa, a'', bb, b'', cc, c'', dd, d'' は C', a, b, c, d, から 計算で求まる C は a, a'', b, b'', c, c'', d, d'', X, Y, Z, W, から計算で求まる けど X, Y, Z, W の求め方や条件が不明 X, Y, Z, Wの条件は0以上の整数というだけなら Cは一意に定まらないけどそれでもいいということ？ 144 名前：１３２人目の素数さん mailto:sage [04/07/10 23:46] >最小となる正の数を(cd)"とする です。 というか、最小となる正の数が Zのことなのか、Wのことなのか、cZ+c''のことなのかということです 例えば「等式※ 2*s+3=3*u+5となる最小の(1以上の)整数をRとします」といった場合、 この等式を満たすs,tの組は(4, 2), (7, 4), (10, 6), ・・・とありますが、 最小といっているので多分ペア(4, 2)に関係あるということまでは分かりますが、 Rがsである4なのか、tである2なのか、2*s+3(=3*u+5)である11なのか どれを指しているのかわからないということです Rが※となる最小のsなら4だし、最小のtなら2、最小の2*s+3なら11と分かります 145 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/10 23:50] C=aX+a"=bY+b"=cZ+c"=dW+d"(X,Y,Z,Wは0以上の整数) となる最小の正の数Cを求めます。 cZ+c"=dW+d" となる最小の正の数を(cd)"とすると (c*d)V+(cd)"=cZ+c"=dW+d" となります。今度は bY+b"=(c*d)V+(cd)" となる最小の正の数を(bcd)"とすると aX+a"=(b*c*d)U+(bcd)" ・・・以下同じ・・・ 拡張ユークリッドの互除法を繰り返していけばOK 146 名前：１３２人目の素数さん mailto:sage [04/07/10 23:53] >>145 前半了解 じゃあ後半も S=cZ+c"=dW+d" となる最小の正の数 S を (cd)'' とするで良いのかな？ 147 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/10 23:53] >例えば「等式※ 2*s+3=3*u+5となる最小の(1以上の)整数をRとします」といった場合、 >この等式を満たすs,tの組は(4, 2), (7, 4), (10, 6), ・・・とありますが、 この等式を満たす最小の正の数です。 等式※なら私が言っている最小の正の数は11となります。 148 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/10 23:54] >>146さん そうです、その通りです。 149 名前：138=144=146 mailto:sage [04/07/10 23:56] ども、読んでみます 150 名前：138 mailto:sage [04/07/11 00:06] およ？ S=cZ+c"=dW+d" となる最小の正の数 S を (cd)'' とする （つまりSが最小になるようにZ, Wをとったとする）と、結局 　　(cd)''=cZ+c''=dW+d'' だよね？　じゃあ 　　(c*d)V+(cd)"=cZ+c"=dZ+d'' の(c*d)Vは c, d not= 0 だからV=0じゃないの？ 151 名前：138 mailto:sage [04/07/11 00:09] Vは>145の記法ね >55の記法ではZ_W 152 名前：１３２人目の素数さん mailto:sage [04/07/11 00:18] 質問ばかりですまんですけど、 今度は細かいことではなくて大雑把に聞きたいんですけど、 a, b, c, dそれぞれでMを割り、式を比較してというような操作が繰り返されますよね？ なぜa〜dの４つであり、a, b, cの３つや、a〜eの5つではないのでしょうか？ 4で暗号として十分であるのか、また3では問題があるのか？等を聞いてみたいです。 153 名前：１３２人目の素数さん [04/07/11 00:43] 　ぶっちゃAが旅をした。 　最初に寄ったのはK町にいるぶっちゃBの家。そこでの賄いはキャベツ３つ。 　次に寄ったのはF市にいるぶっちゃIの家。そこではベッドを４つ借りて就寝。 　翌日になり、初めに寄ったのはL村のぶっちゃWの家。そこでは８台のテレビで映画鑑賞をした。 　 　この後、ぶっちゃAはどこへ行ってどんな事をするでしょうか? 154 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/11 00:48] そうですよ そこでは(cd)"を求めるのを何度も繰り返して Cを求めるのが目的ですから。 M=ax+a'=by+b'=cz+c'=dw+d' のとき、a,a',b,b',c,c',d,d'と 拡張ユークリッドを用いてMを求めた時に M=(a*b*c*d)*T+M となります。 このとき当然T=0となります。 だからV=0でも問題ありません。 155 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/11 00:50] 別に4つでなくてもかまいません。 ただの例示として示しただけですから。 深読みのしすぎでつ 156 名前：138 mailto:sage [04/07/11 01:22] う〜ん、次ステップで分からなくなりました。 　�@　bY+b"=(c*d)V+(cd)" となる最小の正の数 bY+b'' を (bcd)" とすると から始めて 　�C　bY+b"=(c*d)V+(cd)"=(b*c*d)U+(bcd)" (Uは0以上の整数) となる表示を求めるんでしょうけど出来ません。 55の場合Z, Wともこれから求める値であったのに対して、 今回はVは既に定まったあたいであり、欲しい値はUだけですよね？ この�@〜�C部分を>55形式で書いていただけませんか？ 157 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/11 01:43] いえ、Vは変わります。 たとえば、a=2,b=3,c=5のときabc-1=29 つまり、0-29をa',b',c'であらわせるわけです 23=2x+1=3y+2=5z+3です 3y+2=5z+3となる最小の正の数は8です。 8=15w+8でw=0ですが、 2x+1=15w+8となる最小の正の数を求めるときには w=1です。 これは23となり元に戻りました。 158 名前：１３２人目の素数さん mailto:sage [04/07/11 03:07] >>157　 すみませんが、157の例のa,b,c等が>156のb,c,dのどれに対応しているのでしょうか？ >55ではlabel間を繰り返すように書いてありますが、再帰処理を行う場合､ １ループ目で求めた値を２ループ目の初期値としてセットし、 ２ループ目で求めた値を３ループ目の初期値としてセットし、 と繰り返して最終値を求めていきますよね。 今回の場合まず最初に、cZ+c"=dW+d" となる最小のcZ+c''の値を(cd)''として cd*Z_W+(cd)"=cZ+c"=dW+d" という表示 （つまり整数Z_W） を求め、 次にこの表示 （つまりZ_W） を利用し、cd*Z_W+(cd)"=bY+b" となるような最小の値を(bcd)"として、 bY+b"=cd*Z_W+(cd)"=bcd*Y_Z_W+(bcd)" という表示 （つまり整数Y_Z_W)を求めて と繰り返していくのではないのですか？ あと、違うとは思いますが、 >55の「となる最小の値を(cd)"とします」は 「となる最小の値を(cd)"をこれから求めていきます」ではないですよね 159 名前：１３２人目の素数さん mailto:sage [04/07/11 03:15] あかん駄目だ、他力本願でいきますが、 63さん、白シャツさんは >55 のC'⇒C の手続きわかります？ お分かりでしたら教えていただけませんか？ 160 名前：白シャツ [04/07/11 07:15] >>159 何度も言ってますが中国人の剰余定理（CRT）でやってください。 ぐぐれば説明がたくさんありますので。 少なくとも私は>>55ではやりません。 161 名前：白シャツ [04/07/11 07:37] >>136　それは大きいかどうかではなくL=abだからだと思う。 a,bが小さくても一緒では？ ほんとに偽カエサル暗号になっってるんじゃない？ 162 名前：名無しさん＠そうだ選挙に行こう mailto:sage [04/07/11 08:17] 中国剰余定理だ。まあ意味は同じだが。 数学科なら群論の初歩で必ずやるから 絶対に知ってる 163 名前：63 ◆oYI7WOcH/A [04/07/11 12:54] >159 >>55は、おそらくプログラムを日本語に変換しようとしたみたいだけど、 プログラム2日本語がうまくいってないみたいだね。 だから、本質的なことを話すと、 C=aX+a"=bY+b"=cZ+c"=dW+d"となるCをどんな方法でもいいから(mod L)で適当に求めてやればいい。 a,b,c,dが互いに素なので、ちゃいにーずな剰余の定理からC→C'が1対1で置換されることが保証される。 その「どんな方法でも」のうちの一つが55だから、もっと自由に計算していい。 164 名前：名無しさん＠そうだ選挙に行こう mailto:sage [04/07/11 14:15] >160, >163 ありがとうございます、そういうことならOKです ただ>55を売りにしているように思ったので、 それなら>55を読み解く必要があるのかなと思ったので・・・ 165 名前：白シャツ [04/07/11 14:40] 「〜となるような〜を求めます」みたいな書き方があるんで、 >>163のように「Cをどんな方法でもいいから」 どんな方法で求めるかわからない。 ということで>>55はアルゴリズムとして読めない、読み解けない。 >>164と同様に読み解こうと試みましたがあきらめました。 CRT知っているなら>>55よりむしろ>>53,>>54の暗号方式を もっと売りになっている”数学的な”理解が できているはずなんじゃないかなと。 166 名前：名無しさん＠そうだ選挙に行こう mailto:sage [04/07/11 15:23] しかし>55に新規性がないとなると、この暗号って 仮に64bitを暗号化しても64bit以上になる可能性もありそうだし、 複雑度も豆数の数に依存してそうだし、 ループ発生と豆数選択の兼ね合いが難しそうなというか 面倒くさいのに割にあわないって感じがするんですが・・・ >53-54という本筋を特許化して公開せずに 出されたCだけをみて解けといわれれば何ですが 公開されると結局、平分をシフトして、CRTで分散化しているって感じしか・・・ ここイメージだけですので無視してください、多分理解できてないな。 167 名前：63 ◆oYI7WOcH/A [04/07/11 15:42] >>166 >面倒くさいのに割にあわないって感じがするんですが・・・ うん、それは分かってるんだよね。 でも、考案者はそれが分かってないみたいだから、 パフォーマンスを測定してごらん、って言ったら、実装している途中に、 なんかよくわからんが、理論的にも致命的な欠陥があるらしい、ってのが分かってきたってとこ。 （L=a,bにしたら、すごく値が偏ったんだっけ？） 理論的にどこが、ってのは、まだ仕様が固まってないので（固まっていたからどうということでもないけれど） 考える気も起こらんってのが現状かな。 168 名前：白シャツ [04/07/11 16:37] >>68で言ったようにL=abだと一般の場合に M→C'の写像が、(a',b')→(a'+1,b')になる。 さらにC'→Cの写像が、(a'+1,b')→(a'+1,b'-1)になる。 となるとM→Cは、(a',b')→(a'+1,b'-1)なので単なるカエサル暗号。 偏りがあるといいよりC-M const.は自明じゃない？ M→C'の写像ですが、一般のMの場合、 (a',b'c',d')→(a'+1,b'+1c'+1,d') 169 名前：白シャツ [04/07/11 16:45] L=abcdの場合にもM→C'はカエサル暗号だったけど、 C'→Cが剰余だけでなく商を用いていたので独自性があった。 L=abcdのときdd=0だったように、L=abの時にbb=0になるんで、 「商を用いていた」の独自性がなくなったんでしょう。 >>168も含めて詳細の検討はしてないので、 間違ってるかもしれないけど。 L=abcdのときのC'→Cがどういう写像か検討するのは 面白そうだけどまだよくわからない。 170 名前：白シャツ [04/07/11 16:46] >>168の下2行コピペのゴミです。 無視してください。スマソ 171 名前：138 mailto:sage [04/07/11 16:49] >>167 なるほどそういうことでしたか。 途中参加ではレス100以上は追いきれなくて・・・ >L=a,b 2つでは駄目でしょうね かといって最低いくつあればともいえないですね 増やせば自分の首も締めそうだし 暗号化されたCがいくら長くなろうが、公倍数でループしそうな・・・ 公約数（素因数）発見以上の何物でもないような・・・ 新しい暗号理論を既存理論の組み合わせで総当り的に見つけようとしているような 作っていったら上手い暗号理論が見つかったってのは、 結局のところ総当りで暗号解読しようかといってるような気がするなぁ 堅牢な概念を考えて、理論武装するために付け加えていく手法の方が・・・ と言葉濁してしばし静観 172 名前：63 ◆oYI7WOcH/A [04/07/11 17:19] >168 ごめん、そんな話もあったね。差がConstならConstなんじゃない？ どぶろくは、下位ビットが揃うって言ってたけど、 二つとも本当だとしたら、かなりだめだめかもね。 173 名前：白シャツ [04/07/11 20:12] >>172 >>136によると下位ビットが揃う＝差がConstみたいですね。 174 名前：白シャツ [04/07/13 14:20] 終了でつか? >>166 言い忘れてけど，>>55が正しく表記されていた場合， CRTの一解法ですね．新規性は無く，面倒そうだけども． 175 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/13 20:33] パフォーマンスを公開してみろといわれて 暗号化速度を測定してみたところ 18.6KB/sでした。 250Mbpsなんて無理です。 私の考えた暗号はだめだめでした。 仮に発表して実装してもらっても遅すぎて使い物になりません 2chの方たちに暇つぶしのネタを与えただけでした。 また色々と考えて出直してきます。 176 名前：63 ◆oYI7WOcH/A [04/07/13 21:25] > 18.6KB/sでした。 > 250Mbpsなんて無理です。 > 同じデータを暗号化するのに10^4倍ぐらい時間がかかると思う。 の予想が、かなりタイトに当たってるね。 まぁ、これは、ある程度予想されたことだからしょうがない。 ただ、遅いのを悲観するだけだと、従来の路線の後追いでしかなくなるから、 どうせこれだけ複雑な式変換をやるんだから、ただ暗号化だけではなく 何か別の要素を加えると、もうちょっといいのが出来るかも知れないよ。 例えば、対称鍵暗号なのに、完全には元に戻ってないとか。 （データに影響しない部分に、電子透かしが入ってるとか…） なんか面白いかもしれないねぇ。 やってみよ。 177 名前：白シャツ [04/07/13 23:38] 公開鍵暗号考えてみたら？ 今回のはアイデア的に どっちかというとそっちむきだと思いますが。 178 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/14 15:38] 公開鍵暗号ですか〜 憧れの暗号化方式です。 また色々と考えてきます。 179 名前：白シャツ [04/07/14 21:43] >>178 編入試験対策の方は順調？ 180 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/14 22:47] いえ、まったくしてません 私の専門学校からだと基本情報技術者の資格を取れば 専門学校から大学に推薦してもらえるそうなので 推薦してもらって入ろうかと思ってます。 181 名前：白シャツ [04/07/15 00:00] >>180 暗号とかやってる研究室のある大学に推薦してもらえるの？ 3年次編入ありでそんな大学ってあるのかなぁ。 182 名前：１３２人目の素数さん mailto:sage [04/07/15 08:56] >暗号とかやってる研究室のある大学に推薦してもらえるの？ 希望としては横浜国立なんですが やっぱ勉強して一般入試で入らないとだめですか・・・ 一応推薦では岐阜と思ってるんですが 大学院にすすんでそれから暗号の研究室ってのは 無理ですかねぇ・・・ 183 名前：77 mailto:sage [04/07/15 10:22] >>182 ＞大学院にすすんでそれから暗号の研究室 いや、それでも全然ＯＫだと思うよ。 ただ、ム板の暗号スレにもあったけど、暗号アルゴリズムの研究以外にも 情報セキュリティには色々な研究分野があるし、情報系の他の分野にも 数理的な分野はたくさんあるんで、学部のうちは代数系や計算機科学、ネットワーク等の 基礎知識を広く浅く勉強しつつ、いろんな分野に興味を持って覗いてみるのもいいと思う。 （院に進学する頃には違う分野のことが面白くなってるかも） 184 名前：１３２人目の素数さん mailto:sage [04/07/15 16:09] もし数学系に編入するならもうちょっと数学独自の言い回しに気を配ったほうがいいのでは？ >53 〜見る限り、必要なことを後出しにして書いているので、そういうのが訓練されていないと思う 数学の内容どうこうは別として、書き方・伝え方は殴り書きだとしてもこれではというレベル まず>137さんの言うように基礎をやりながらそういうのも覚えたほうがいいと思う 誤解を与えずに伝えるため、また自分の考えを伝えるための書き方や読み方も一種の訓練で、 凡才な人（ほとんどの人）は、1年目に基礎の授業の問題回答やレポートなど体で覚えるから 天才のことは知らない 編入して来て大学院とかも知り合いにもいるから、自分次第なんでしょうけど 専門学校からの編入は知らないし、いま学校でどんな勉強してるかもわからないので 185 名前：白シャツ [04/07/15 21:47] >>182 >希望としては横浜国立なんですが 松本先生のところ？ >一応推薦では岐阜と思ってるんですが >大学院にすすんでそれから暗号の研究室ってのは >無理ですかねぇ・・・ これは別の大学の院に行くこと前提ってことですか？ 186 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/15 22:27] >>185 >松本先生のところ？ そうです。松本先生のところで研究してみたいと思ってます。 >これは別の大学の院に行くこと前提ってことですか？ そうですが、編入試験があって推薦もあってとなると 編入可能の大学には暗号関係の院がなかったんです。 別の大学の院にいくって前提では受け悪いですか？ 187 名前：白シャツ [04/07/15 23:38] >>186 >そうです。松本先生のところで研究してみたいと思ってます。 まともに暗号やってるところってあんまりないし、 悪い選択ではないと思う。 >>183のような「暗号以外のセキュリティ分野」もやってるね。 >別の大学の院にいくって前提では受け悪いですか？ 誰に対する受け？　 問題があるとすると、暗号やってる院にすんなり 入れるかどうか、or院に入った後で暗号関係の研究室に 配属されるかどうかでしょうか。 188 名前：63 ◆oYI7WOcH/A [04/07/16 00:57] 岐阜大にも情報数学から暗号の研究をやっている集団はいるよ。 基礎研究というよりは、応用分野で提携して…っての方だけど。 ム板から来たってことは、基礎研究より、そういう方が向いてるんではないかと勝手に思ったんだが。 もし、本気で対称鍵暗号を設計しようと思ってるなら、絶対に回路設計の知識は持っておかないとだめかも。 特にユビキタスに向かっている今、小さいサイズでハードウェア実装出来るってのは必要条件になりつつある。 ただし、これで職に就くのは、ハードだよ。日本中探して一年に一人いるかいないかだろう。 189 名前：１３２人目の素数さん mailto:sage [04/07/16 01:12] 素数を求める回路を教えてください 190 名前：１３２人目の素数さん mailto:sage [04/07/16 02:55] 暗号もいいが認証もいい 191 名前：１３２人目の素数さん [04/07/16 10:53] >>189 求める素数の質による。 暗号で使うような素数ならMiller-Rabin法がNIST公認のアルゴリズムだけど、 これをそもそも回路で設計するべきものなのかどうかはしらない。 192 名前：白シャツ [04/07/16 11:01] >>189 素数を求めるってのがどんな問題かわからない． 素因数分解かもしれんし，素数判定かもしれない． >>191 と同意で回路でやるものじゃないとおもう． 193 名前：１３２人目の素数さん mailto:sage [04/07/16 20:45] 符号理論ってもう華がないですか？ 194 名前：１３２人目の素数さん mailto:sage [04/07/16 23:47] そもそも華あったの？ 195 名前：白シャツ [04/07/17 00:19] >>194 CDとか聞けるのは誰のおかげか考えてみな。 ていうか、データ通信できるのは誰のおかげなんだ。 196 名前：１３２人目の素数さん mailto:sage [04/07/17 05:47] マクスウェルのおかげです

---

---

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

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