暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 53 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:35] この暗号は数車(かずぐるま)といいます。 歯車が回っているのをイメージした時に思いついたので このような名前になりました。 わかりづらかったら質問してください。 暗号化 素数^n(nは自然数)となるような数をいくつか用意します。 個人的にこの数を勝手に豆数(まめかず)と読んでいます。 豆数は素数^nとなる数です。 L=abcd(Lはabcdの最小公倍数)とする (このときのLが秘密鍵です。) ここでは仮に豆数をa,b,c,dとします。 (a,b,c,dは互いに素でなければなりません) 平文Mをa,b,c,dでそれぞれ割っていきます。 このときの余りをそれぞれa',b',c',d'とすると、 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とする) という関係が成り立ちます。 a,a',b,b',c,c',d,d'を用いて C'=(((a')b+b')c+c')d+d' (Mの範囲が0<=M<abcdのとき0<=C'<L) となるようなC'を計算します。 54 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:36] 今度は C'をaで割りそのときの商をaa,余りをa" aaをbで割りそのときの商をbb,余りをb" bbをcで割りそのときの商をcc,余りをc" ccをdで割りそのときの商をdd,余りをd"(ddは常に0です) とすると、このとき 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を求めます。 このときのCが暗号文です。 55 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:37] M→C'は問題ないと思いますのでC'→Cの求め方 label1: cZ+c"=dW+d"…壱 となる最小の値を(cd)"とします。 壱を少し変形して cZ-dW=d"-c"…弐 拡張ユークリッドの互除法を用いて cZ'-dW'=1となるZ'またはW'を求めます。 両辺d"-c"倍してやって c(Z'*(d"-c"))-d(W'*(d"-c"))=d"-c"…参 弐と参を比較して Z=Z'*(d"-c")　W=W'*(d"-c") ∴壱は cd*Z_W+(cd)"=cZ+c"=dW+d"(Z_Wは0以上の整数) と表されます。 今度は cd*Z_W+(cd)"=bY+b" となるような最小の値(bcd)"を求めます。 goto label1; と、どんどん繰り返していってCが求めれます。 復号はこの逆を行えばいいわけです。 56 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:38] 豆数の並べ方に決まりがあります。 素数の小さい順に左から並べます。 つまり、 L=2800のとき Lを素因数分解して L=2^4*5^2*7^1 豆数を 2^4,5^2,7^1 とならべます。 今度はLを豆数の数で割ってやります。 ここでは3です。 豆数に右から順に0,1,2と割り振ってやって 2800%3≡1　2800/3=933 1番は5^2ですから 一番左は5^2になります 2^4,7^1と並びます 今度は933を2で割ります 933%2≡1 今度は1番目は2^4ですから 豆数は5^2,2^4とならび 最終的には 5^2,2^4,7^1と豆数は並びます。 そしてこの順に a,b,cに豆数を代入していきます。 以上で説明は終わりです。 何か質問ありましたらどうぞ〜 あと、わたしが公開すべきものを指定してくださいな。 57 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:39] P=ax+a'=by+b'=cz+c'=dw+d' a=2,b=3,c=5,d=7,e=11,f=13・・・・としていって P=2x+1=3y+2=5z+2=7w+6=11p+10=13q+6・・・ P<289となるようなPを求めれば 2・3・5・7・11・13で割り切れないのは保証されてるわけで、 素数生成に使えないかと思ってんですがいかがでしょうか？ まあ、この考えが science3.2ch.net/test/read.cgi/math/1084794080/876 みたいな勘違いにつながったわけですが・・・ 58 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:40] たとえばC'を暗号文として扱うと C'=(((a')b+b')c+c')d+d' 展開して C'=a'bcd+b'cd+c'd+d' a'はa周期ごとに0をとるから その時のC'の値は C'=b'cd+c'd+d'　となり、 選択平文攻撃を用いてMの値に1ずつ加算して それに対応したC'の値が何周期で 増減を繰り返しているかを見ればaの値がわかってしまいます。 さらに、 M2はbで割り切れ(b'=0)そのときのa'をA,c'をC,d'をDとし M1+1=M2とするとき C'1=A*bcd+(b-1)*cd+C*d+D C'2=(A+1)*bcd+0*cd+(C+1)*d+(D+1) C'2-C'1=bcd-(b-1)cd-d-1=cd-d-1 となり、差が極端に小さくなります。 (C+1,D+1が0になることは考慮していません) この性質もまた選択平文攻撃の餌食となり 何周期ごとにC'2-C'1の差が小さくなるのか調べると bの値がばれてしまいます。 59 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:40] (上のA,B,C,Dと以下のA,B,C,Dは関係ありません) C'→Cの方法を M→Cとして扱うと Mをaで割りそのときの商をx,余りをA Aをbで割りそのときの商をy,余りをB Bをcで割りそのときの商をz,余りをC Cをdで割りそのときの商をw,余りをD(wは常に0です) とする。つまり、 M=ax+A,x=by+B,y=cz+C,z=dw+D これを右から代入していって(wは常に0だから削除) M=(((D)c+C)b+B)a+A _=abcD+abC+aB+A となります。 a,A,b,B,c,C,d,Dを用いて C=ax+A=by+B=cz+C=dw+D となるCを拡張ユークリッドの互除法により求める。 このCを暗号文とするとこれまた選択平文攻撃の餌食となります。 60 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:41] 以下証明 by+B=cz+C=dw+D となる最小の値をVとする。このとき C=(b*c*d)*v+V=ax+A(x,vは0以上の整数) また、M0→C0,M0+1→C1,M0+2→C2とし、(M0を暗号化するとC0が得られるって事です) M0をaで割りその時の余りをA0,M0+1をaで割りその時の余りをA0+1, M0+2をaで割りその時の余りをA0+2, (A0,A0+1,A0+2はaで割り切れないとする。割り切れるときは下で書いています)とすると C0=bcd*v0+V=a*x0+A0 C1=bcd*v1+V=a*x1+(A0+1) C2=bcd*v2+V=a*x2+(A0+2) となります。 C1-C0=bcd(v1-v0)+V-V=a(x1-x0)+(A0+1)-A0 　 　=bcd(v1-v0)=a(x1-x0)+1 C1-C0-1=a(x1-x0) C2-C1=bcd(v2-v1)+V-V=a(x2-x1)+(A0+2)-(A0+1) 　 　=bcd(v2-v1)=a(x2-x1)+1 C2-C1-1=a(x2-x1) C1-C0,C2-C1の値にユークリッドの互除法・素因数分解を用いると bcdについての情報が分かります。 更に、C1-C0-1,C2-C1-1も同様に aについての情報を与えてしまいます。 61 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:42] 今度は (A0,A0+1,A0+2はaで割り切れないとする****の割り切れる時の場合です) M3をaで割りその時の余りをa-1とすると,M3+1をaで割った余りは0になります。 M3→C3,M3+1=M4→C4とする。 M3=a*x+(a-1),x=b*y+B,y=c*z+C,z=d*w+D M4=a*x+(a-1)+1=a*x+a=a(x+1) 　 x+1=b*y+(B+1),y=c*z+C,z=d*w+D (ここのx,y,z,wは同じ値です) この時C3,C4は C3=a*x3+(a-1)=b*y3+B=c*z3+C=d*w3+D C4=a*x4+(0)=b*y4+(B+1)=c*z3+C=d*w4+D C4-C3=a(x4-x3)-(a-1)=b(y4-y3)+1=c(z4-w4)=d(w4-w3) C4-C3-1=a(x4-x3-1)=b(y4-y3) ∴C1-C0とC4-C3,C4-C3についてユークリッドの互除法・素因数分解を用いると a*b,c*dについての情報が得られました。 上のような考慮事項があるので M→C'　C'→Cのように二段階の暗号化を行いました。 >>all 自分自身で読み返してみて分かりづらいと思っています。 もっと分かりやすく説明しろ！！！ ってとこがあると思いますので指摘をお願いします。 62 名前：１３２人目の素数さん [04/07/05 23:23] >>52-61 ざっと見た感じ、これは対称鍵暗号だよね？ んでもって、とてつもなく、暗号・復号にかかるコストが高いよね？ 質問としては、 ・これをどうして欲しいのか？ ってのが最初なんだけど…。 例えば、 これこれアルゴリズムを考えました。 既存のアルゴリズムに比べて、段違いに遅くて、いいところがありませんが、 誰か一緒に検討してください！って言うならそういえば、暇な人が手伝ってくれるかもよ？ 既存のアルゴリズムよりもこの点において優れてる！っていうところが一点でもなければ、 ちょっと僕は、手伝えません。すみません。 63 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 23:42] >>62 >・これをどうして欲しいのか？ んっと仮に実際に使った時に攻撃の対象となる 脆弱性があるのか知りたいのです。 >んでもって、とてつもなく、暗号・復号にかかるコストが高いよね？ そうなんですか、既存の対称鍵アルゴリズムについての コストとかは知らないんです。 >既存のアルゴリズムよりもこの点において優れてる！ 1・ 対称鍵暗号方式にしては数少ない 数学的アルゴリズムに基づいた暗号化方式である まーここがコストの増大を引き起こしていると思ってます。 2・ 対称鍵の長さ・暗号化毎のブロックが可変長である ってとこじゃないでしょうか ブロックをnビット毎に区切って暗号化する場合 対称鍵をn+2ビットとして選べばOKです。 64ビット毎に区切って暗号化してもいいし 極端な話71ビット毎や93ビット毎に区切って暗号化してもいいわけです。 64 名前：白シャツ [04/07/06 00:49] CRTって知ってる？ 中国人の剰余定理ってやつなんですけど。 それと、多次（高次？）剰余暗号とかそういう系とかもあるしなぁ。 とりあえず検討してみますか。 65 名前：白シャツ [04/07/06 01:20] 公開鍵暗号なんだが >>64　の多次（高次？）剰余暗号は指数部でこういうのやってるから ちょっと違った。積和型暗号とかそういう系か？ 離散対数を利用した公開鍵暗号系について 森井昌克、笠原正雄 電子情報通信学会論文誌 Ｊ71-D，2，pp.448-453 みたいなのがある。実用性無いけどね。 66 名前：１３２人目の素数さん [04/07/06 02:00] >>64 あなた、いい人だねぇ…。 64の気概とどぶろくさんの真剣さに感心して63にマジレスすると… >1・ >対称鍵暗号方式にしては数少ない >数学的アルゴリズムに基づいた暗号化方式である すまん、本当にわからない。 数学的アルゴリズムってどこのことを言ってるの？ もし、暗号文と平文が簡単な数式で表される関係を持つという意味なら、 申し訳ないが、これが一番の弱点じゃないかと思う。 公開鍵暗号の安全性証明と勘違いしてない？ Lの作り方から考えても、既存の公開鍵暗号よりもパフォーマンスが悪いと思うよ。 全く話は別で、 もし、何らかの命題を示して、それに証明を付けようと思っているなら、 ここの板の人はとても役に立つかもしれないよ。 >2・ >対称鍵の長さ・暗号化毎のブロックが可変長である >ってとこじゃないでしょうか ストリーム暗号というのを、調べてみてください。 まぁ、もし、可変長のアルゴリズムを実装しようとしたら、 鍵生成の部分だけで、投げるだろうな。 67 名前：１３２人目の素数さん [04/07/06 02:07] カオス力学系の離散モデルを使って、疑似乱数を発生させて、 それとの排他的論理和を平文との間で取ってからDESのような ブロック暗号化を施せば、十分に強いという。 両端でのカオス力学系は最初にだけ初期値を一致させておく 必要があるのが欠点だけども。 68 名前：白シャツ [04/07/06 03:23] >>65 >あなた、いい人だねぇ…。 新規参入者に優しくしないとタマが尽きます。 どぶろくさん、SCISとかで発表してみたら。 たぶんこれはダメだろうけど、ラインデールも 散々蹴られまくったけど、AES取れたことだし、 もうちょっとひねってがんがれ。 てことで詳細の検討はしてないけど、 とりあえず眠いのでインプレッションだけ書いて寝る。 Ｍ→Ｃ’の写像って単なるシフトじゃないかな。 議論を簡単にするためにL=abの場合で考えてみる。 それとこういう場合aやｂはbase(基数)という。 a,bが素数冪ならLCM(a,b)=abは自明だな。 M　mod L を２次元の平面上の点(a',b')で表しているんだと分かるわな。 C'=(a')b+b'だったら下の図みたいにならない？ 　　　　　b' 　 0----------→b 　｜ a'｜ .M＝(a',b') 　｜　　 .C'=(a'+1,b') ↓ 　 a 69 名前：白シャツ [04/07/06 03:36] >>68 しまった、専用エディタでやらんとダメだった。 でもだいたいわかるよね。 ついでに>>63 >1・ >対称鍵暗号方式にしては数少ない >数学的アルゴリズムに基づいた暗号化方式である 秘密鍵暗号もね、そうとう裏では数学考えてるらしいよ。 たとえばF_2の拡大体の性質を考慮して設計されているわけで、 だからこそM菱松井氏がDESの（ある意味意図的な）欠点を 叩く攻撃ができたりしたわけで、>>66さんも言ってることに 同意。松井さんみたいな神じゃなくても分かるからさ。 >2・ >対称鍵の長さ・暗号化毎のブロックが可変長である >ってとこじゃないでしょうか 普通の平文って大きいからハッシュ取って一定サイズに （小さく）するでしょ。それでも都合悪かったら（小さい場合は） パディングするし。 70 名前：白シャツ [04/07/06 03:47] >>68 あくまで見た感じのインプレッションなんで 詳細に検討した結果ではありません。 間違ってたらスマソ。 それと>>69の >普通の平文って大きいからハッシュ取って一定サイズに >（小さく）するでしょ。それでも都合悪かったら（小さい場合は） は間違い。最近署名とか認証に凝ってるんで非可逆が デフォになってました。スマソ 71 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/06 07:08] 対称鍵暗号です。 公開鍵ではありません 勘違いした方がおられましたら失礼しました 72 名前：白シャツ [04/07/06 13:12] >>71 いやいや，みんなわかっていると思う． ただ，アイデア的に公開鍵に近いというように思うから． それと，>>68で言ったことが正しい場合には， この暗号は高次化したカエサル暗号って感じになるんでは ないかと思うんですが．そのあたりどうなのかなと． 73 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/06 15:04] これは数車とは全くの別口の話です。 RSAへの攻撃についてです。(以下、すべてmod　n) C=M^e M=e^d C^d=(M^e)^d=M^(ed)=M^1=M こうですよね？ んで、最初にMの値として秘密鍵dを暗号化したら どうかってのを考えたんです。 すると、 M=d C=d^e C^d=(d^e)^d=d^(ed)=d^1=d これの意味するところは (d^e)^d=d (d^d)^e=d つまり、p,qの素因数を行わずに dの値を求めることができる！！！ もっと賢くやると、公開鍵eを暗号化してやります。 省略して書くと (e^e)^d=e^(ed)=e^1=e E=e^eとするとき Eの値は簡単に求めれますから E^d=e となるdについて求めればいいことになります。 もう既出でしょうか？ 私は聞いたことがなかったので書いてみたのですが・・・ 結構すごいことじゃないですか？ 74 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/06 15:07] M=e^d × M=C^d ○ 75 名前：１３２人目の素数さん mailto:sage [04/07/06 15:29] >>68 >Ｍ→Ｃ’の写像って単なるシフトじゃないかな。 ここはそうだと思います。 ただ、下の図の >C'=(a'+1,b') はどうでしょうか？ C'=(a'+X、b') (Xは整数) じゃないでしょうか？ 　　　　　b' 　 0----------→b 　｜ a'｜　 　.M＝(a',b') 　｜　　 .C'=(a'+1,b') ↓ 　 a >>72 >この暗号は高次化したカエサル暗号って感じになるんでは ここんとこはそうかなーと思いますが、もう少し考えてみます。 76 名前：梅どぶろく" ◆rM4QWlepe6 mailto:sage [04/07/06 15:38] たびたびすんません もっと賢くやると、公開鍵eを暗号化してやります。 省略して書くと (e^e)^d=e^(ed)=e^1=e E=e^eとするとき Eの値は簡単に求めれますから E^d(mod　n)=e となるdについて求めればいいことになります。 77 名前：暗号スレの55 mailto:sage [04/07/06 19:38] >>73 ＞最初にMの値として秘密鍵dを暗号化したら ＞つまり、p,qの素因数を行わずにdの値を求めることができる！！！ dを暗号化したんだから，復号したらdが出てくる． >>76 ＞E^d(mod　n)=e ＞となるdについて求めればいいことになります。 「なにを求めたい」のかいまいちわからないけど， N （秘密の2素数の積 ）と e が与えられたとき (A^e)^x = A (mod N) を満たす x を求めるのが難しいってのが RSA暗号方式の安全性の根拠です． 向こうのスレ見て思ったんだけど，暗号方式への攻撃モデルとか 一度本で読んどいた方がいいよ．例えば 岡本（龍明），山本「現代暗号」産業図書，1997 岡本栄司「暗号理論入門　第2版」共立，2002 78 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/06 21:42] >>77 ほんとごめんなさい マジで勘弁してください。 私がどう考えても悪いです。 まじごめんなさい 穴があったら入りたいってのは このときのことを言うと思います。 79 名前：77 mailto:sage [04/07/06 22:29] >>78 あーいやいや，実は漏れもRSA暗号を知ったばかりのときは そういう勘違いをよくしてました．マジでしょっちゅうやってた． 「駄目」ってことがわかるとがっくりくるんだよねｗ 80 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/06 22:47] >>79 ですね、 いける！と思いついてその考えがいかによく思えても 最低数時間はたってから もう一度その考えについて疑心的になって考えなければいけない ってことが教訓になりました。 いい薬になりました 81 名前：白シャツ [04/07/06 22:54] >77 >＞E^d(mod　n)=e >＞となるdについて求めればいいことになります。 > >「なにを求めたい」のかいまいちわからないけど， DLP解いたらRSA解けるっていいたいんだと思う。 漏れも昔似たいようなこと聞いて叩かれたことあったんですは。 DLPは解けないって怒られた。 認めたくないものだな、若さゆえの過ちとはって感じだった。 それと、>>80はもしかして高校生？ 82 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/06 23:02] いんや違います 二浪して大学いけなくて専門学校いって 三年次編入を狙っているものです。 拡張ユークリッドの互除法やフェルマーの小定理なんかを 好奇心に任せて勉強しています。 独学だからいまいち効率が悪い・・・ 今度夏休みになるんですが、 暗号関係で整数論に関するいい本を紹介していただけませんか？ 83 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/06 23:06] 現代暗号・確率的証明・擬似乱数 O. ゴールドライヒ (著), はアマゾンで注文して今届くのを待ってる途中です 乱数についても興味があったのでこの本を選びました 84 名前：白シャツ [04/07/06 23:20] >>82 >いんや違います >二浪して大学いけなくて専門学校いって >三年次編入を狙っているものです。 どこ受けるの？ まずはその対策のほうが先だと思う。 >独学だからいまいち効率が悪い・・・ 漏れもほぼ独学だったし、わかります。 4回生なってから某教科書よまされたしな。 その本がろくでもなかったから（翻訳が）。 >今度夏休みになるんですが、 >暗号関係で整数論に関するいい本を紹介していただけませんか？ まともな本は無い、と言いたい。 嘘書いてある本多いし、良い本あったら漏れも欲しいぐらい。 今までに何読んだかとりあえず教えてくださいな。 それと、>>68でいった >M　mod L を２次元の平面上の点(a',b')で表しているんだと分かるわな。 は言ってる（漏れの言いたい）意味わかる？ 数学の人には怒られるかもしれんけど（訂正よろしく） 85 名前：１３２人目の素数さん mailto:sage [04/07/06 23:34] >>83 その本って確か計算量理論の本のはずだけど。 整数論の方面を勉強したくて買ったんだとしたら、 まったく違う分野であることを覚悟しておいた方がいい。 ＞暗号関係で整数論に関するいい本を紹介していただけませんか？ Koblitz の "A Course in Number Theory" なんかどうだろう。 既読の可能性が高そうだけど。 86 名前：１３２人目の素数さん mailto:sage [04/07/06 23:35] ごめん。本のタイトルが途中で切れてる。 "A Course in Number Theory and Cryptography" 87 名前：白シャツ [04/07/06 23:45] >>85 >>84>その本がろくでもなかったから（翻訳が）。 原書は名著です。 88 名前：63 ◆oYI7WOcH/A [04/07/07 00:39] >>52-61 ここに書いてあることが全てなら、この暗号系、一瞬で解けちゃうんじゃない？ 選択平文攻撃に対する耐性の考察が書いてあるぐらいだから、この攻撃使ってもいいんでしょ？ まず、「Mの範囲は0<=M<Lとする」からMを0に取ろう。で、実際計算してみてちょうだいな。 「M=ax+a'=by+b'=cz+c'=dw+d'」だから、a',b',c',d'は、a,b,c,dの値に関係なく、全部0だ。 そしたら、C'=(((a')b+b')c+c')d+d'=0だ。 だんだん、きな臭くなってきたね。 C'=0ならば、それをなんで割っても商も余りも全部0だよね。 つまり、a'',b'',c'',d''はみんな0になるわけだ。 「C=aX+a"=bY+b"=cZ+c"=dW+d"」が「C=aX=bY=cZ=dW」こんなんになってしまう。 つまり、Cは、aの倍数でもありbの倍数でもありcの倍数でもありdの倍数でもある。 それって、つまり、対称鍵「L」のことだよね。 暗号文に鍵が出てきちゃまずいよね、さすがに。 これで、どっかで計算間違いしてたら恥ずかしいな(w 89 名前：77 mailto:sage [04/07/07 02:16] >>83の本は原著のダイジェスト版の方を訳したものなんだよね。 すでに一通りの知識を持っている人が、知らない分野を学ぶ取っ掛かりを掴むには いいかも知れないけど 、あれで乱数や計算複雑さの理論を勉強するのは無理だと思う。 数論の本…むしろ代数学の本から読んでいった方が進みやすいんでないかい？ 90 名前：白シャツ [04/07/07 02:16] >>88 >「C=aX+a"=bY+b"=cZ+c"=dW+d"」が「C=aX=bY=cZ=dW」こんなんになってしまう。 >つまり、Cは、aの倍数でもありbの倍数でもありcの倍数でもありdの倍数でもある。 >それって、つまり、対称鍵「L」のことだよね。 C=0は？ 91 名前：白シャツ [04/07/07 02:30] >>87 >その本がろくでもなかったから（翻訳が）。 って言ったのは誤解を招いたかも。コブリッツのほうね。 >>89 >　>>83の本は原著のダイジェスト版の方を訳したものなんだよね。 そうだったんですか。買おうどうか検討して止めた覚えがある。 それと、ひとつ思い出したが、以下の本は「工学」の人にはお勧めかも。 木田祐司・牧野潔夫　UBASICによるコンピュータ整数論 92 名前：37 [04/07/07 05:22] >>89 俺は暗号プロパーではないが概ね>>89さんの意見に同意だ． Goldreich本でも >現代暗号・確率的証明・擬似乱数 >O. ゴールドライヒ (著), はどう読んでも暗号初学者向けではない．そもそもPCPって暗号的な応用ってどんなんがあるんでしょ？ 計算量理論的な深い部分で関連があるとは思うが，直接的な応用ってあんまり思いつかないな． むしろ計算量的暗号理論（擬似乱数含む）の入門書としては Foundations of Cryptography: Basic Tools O. Goldreich をオススメする．最近続刊も出たことだし． 93 名前：77（ただの学生） mailto:sage [04/07/07 06:15] >>92 あーそれそれ、元になった本はそれです。 続編の原稿を自サイトで公開して修正意見を募ったという… （それでも売れるんだろな） PCP…ゼロ知識系の、ブラックボックスやオラクルを使用した 計算やプロトコルのモデルがどーたらこーたら…とか？ 94 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/07 06:52] >>88>>90 大丈夫です心配要りません nビット毎に暗号化するとして(対象鍵はn+2ビット) 0〜2^n-1の値すべてに 2^nの加算を行います。 すると暗号化前の平文は 2^n〜2^(n+1)-1になります。 復号する時は 復号して出てきた値から2^nを減算してやればOKです。 あと、 平文をnビットとするときに鍵長がn+1ビットだと 平文すべてに2^nを加算することができないわけで (そうすると平文が2^nの値近くの時に鍵の値を超えてしまうわけです) そういったことを考慮して鍵長はn+2ビットにしました。 平文の値としてL-1を与えてやると暗号文もL-1になります。 95 名前：63 ◆oYI7WOcH/A [04/07/07 09:33] >>90 >C=0は？ うん、それも考えたんだけど、MもC'も取りうる範囲が書いてあるのに、 Cは書いてないから、これもC = 0 mod Lで C=ｎLも仕様の範囲内じゃない？ と、言おうとしたんだが、 >M→C'は問題ないと思いますのでC'→Cの求め方 の中での計算方式に従うと、C=0しか取れないな。 計算方法例だと思って読んでなかったよ。しょぼーん。 まぁ、M=0を入れるとC=0が返ってくるってのは、かなり問題があるが。 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はどこへ行ってどんな事をするでしょうか?

---

---

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

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