暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 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] マクスウェルのおかげです 197 名前：１３２人目の素数さん mailto:sage [04/07/17 08:52] 47氏のおかげだったり？ 198 名前：白シャツ [04/07/17 15:23] 漏れの指導教官は符号→セキュリティと鞍替えしてきた。 符号教えてくれと頼んだんだけど教えてくれなかったので ピーターソンの教科書借りて勝手に勉強中。 全然わからないんすけど。 199 名前：１３２人目の素数さん mailto:sage [04/07/17 17:05] >>195 役に立つけど華はないな、それだと。 200 名前：白シャツ [04/07/17 17:17] >>197 あの人って専門符号だったんでつか？ >>195 そうか、じゃぁ、超高雑音通信路で誤り訂正符号を用いて 無人宇宙探査機を遠隔制御とかだと華あるか？ 201 名前：KingOfMathKingdom ◆NlBVr1vWAA [04/07/17 17:19] チューリングとナッシュだったらどっちが暗号解読力があっただろうか？ 202 名前：１３２人目の素数さん mailto:sage [04/07/18 05:58] >>200 自分のレスにレス付けてるよ 203 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 16:41] 新しい暗号を考えました。 今回は公開鍵暗号です。 a<n,x<n E=a*x mod n とする gcd(a,n)=1,gcd(x,n)=1 かつ a*(E^Y)>n,x*(E^Y)>n となるように適当にYを決めておく Aliceは公開鍵eをつくるために 以下の計算をする e1=a*(E^Y) mod n e2=x*(E^Y) mod n 公開鍵は e1,e2,n Aliceは秘密鍵dをつくるために 以下の計算をする d*(E^Y)=1 (mod n) つまり、 d=E^(-Y) (mod n) 秘密鍵は a,x,d 204 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 16:42] M1,M2<a かつM1,M2<xとなるように M1,M2を決める (Bobはa,xの大きさが分からないので 暗号化できる平文Mの大きさをAliceに聞いておく) 暗号化 C=(M1*e1)-(M2*e2) (mod n) (C>nとなるようにする) 復号 M'=C*d 　=(M1*e1-M2*e2)*(E^(-Y)) 　=(M1*(a*(E^Y))-M2*(x*(E^Y))*(E^(-Y)) 　=(E^Y)*((M1*a)-(M2*x))*(E^(-Y)) 　=(E^Y)*(E^(-Y))*((M1*a)-(M2*x)) 　=1*((M1*a)-(M2*x)) 　=(M1*a)-(M2*x) (全てmod n) CRTより M'=(M1*a)-(M2*x) を満たすM1,M2を求める ∴平文M1,M2が求められた 補足 復号した時 (M1*a)-(M2*x) < n でないとまずいので nのビット数をNとすると a,xのビット数はN/2より小さくなければならない。 M1,M2個々のビット数はN/2より小さいけれど、 一度に二つ平文を送れるので 大体一度に送れる平文はNビット位になる 205 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 16:44] 安全性 離散対数問題に基づいている(んだと思う) 盗聴者Eveがわかるのは e1,e2,n e1*e2=(a*(E^Y)*)(x*(E^Y)) 　 　=(a*x)*((E^Y)*(E^Y)) 　 　=E*(E^(2Y)) 　 　=E^(2Y+1) (全てmod n) e1,e2からE^Y,E,a,xのどれかを求めるのは困難(だと思う) 長所 暗号化速度が超高速 modを毎回するとしても演算がたったの6回ですむ 復号速度も速いとは思いますが、 どれくらいの演算で復号できるかは知りません。 短所 署名ができない 暗号文はNビット 送れる平文は約Nビットなのに 公開鍵が2Nビットと長い 秘密鍵も3Nビットと長い これで説明は終わりです。 結構いいと自分では思っていますが、 前科があるのでいまいち自信がもてません。 どうでしょうか？ 206 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 16:47] >>187 >>別の大学の院にいくって前提では受け悪いですか？ >誰に対する受け？ 大学の教授です。 207 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 17:17] すいません >>203は gcd(a,n)=1,gcd(x,n)=1 かつ a*(E^Y)>n,x*(E^Y)>n となるように適当にYを決めておく に gcd(((E^Y)mod n),n)=1 を追加させてください。 208 名前：63 ◆oYI7WOcH/A [04/07/18 18:10] 楽しいから付き合うけど、もう少し、伝え方を練習した方がいいね。 で、いきなり、いちゃもん。 > CRTより > M'=(M1*a)-(M2*x) > を満たすM1,M2を求める とあるけど、CRTが適用出来るかどうか分からない。 具体的には、a,xが互いに素か分からない。 （a,xが保証されているのは、nと互いに素なだけじゃないかな？） それとも、復号したものが元の平文に戻らないかも知れないって暗号ですか？ 209 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 18:34] >>208 あう、すいません a,xは素数で M1,M2<a　M1,M2<x ということにしてください。 これでCRTを適用できるはずです。 210 名前：63 ◆oYI7WOcH/A [04/07/18 18:53] 一般性を失うことなく a < x と出来る。 その上で、 M1*M2 < a^2 < nでなくてはならない。 ∵ C=(M1*e1)-(M2*e2) (mod n)より、 暗号として表現出来るのは最大n通りだから、 一対一の暗号文である以上、平文（の組み合わせ）も最大n通り。 しかも、最後の方を見ると、だいたいa,xが同じ桁程度の数を取るみたいだから、 E = a * x mod nってのが、限りなくmodを使っている意味がなくなると思うんだけど。 ん？それ以前にe1とe2が近い値になったときに、暗号化出来ない平文が飛躍的に増えるんじゃないか？ 今の段階では、平文の約半分が暗号化出来ないと思うが。 まず、e1とe2の選び方を工夫しなきゃ、こういう状況がもっと増える。 例えば、E_1 = max(e1,e2), E_2 = min(e1,e2)にした方が、取れない平文の数は減るだろう。 んんん？もっと大きな穴がある気がするぞ。 211 名前：63 ◆oYI7WOcH/A [04/07/18 19:26] 凄く概略を言うね。 まず、拡張ユークリッドの互除法でe1^{-1} \pmod nを求める。 これは、（a * E^y）^{-1}でそれぞれnと互いに素だから、a^{-1} * (E^y)^{-1} \pmod nとなる。 これをCにかけると、 C=(M1 * a - M2 * x) * E^y \pmod n　だから、 C*e1^{-1} = M1 - M2 * x * a^{-1} \pmod nになるんじゃない？ 公開鍵暗号なんだから、選択平文攻撃は誰にでも出来る。 M2を少しずつずらせば、x,aが求まると思うんだけど。 全然違ってたらごめん。 212 名前：63 ◆oYI7WOcH/A [04/07/18 19:36] うーん、逆元が必ず存在するとは限らないね。 nは素数だとは書いてないのね。 連続書き込みすんまそん。 213 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 19:45] >>210 >E = a * x mod nってのが、限りなくmodを使っている意味がなくなると思うんだけど。 説明する時に(ax)のタイプはめんどくさかったのでEにまとめました。 あと、公開鍵生成の説明の時分かりやすいと思いました。 >ん？それ以前にe1とe2が近い値になったときに、暗号化出来ない平文が飛躍的に増えるんじゃないか？ これは増えません。 e1,e2が同じならだめですが異なれば問題ありません。 細かいことですが、 >短所 >署名ができない >暗号文はNビット >送れる平文は約Nビットなのに >公開鍵が2Nビットと長い >秘密鍵も3Nビットと長い 短所 署名ができない 暗号文はNビット 送れる平文は約Nビットなのに 公開鍵が3Nビットと長い ←ここ修正 秘密鍵も3Nビットと長い 復号は a*d1-x*d2=1となる d1,d2をあらかじめ求めておけば 4回の演算ですみます。 214 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 19:55] >>212 nが素数でも問題ないと思います x * a^{-1}は e1=a*(E^Y) mod n e2=x*(E^Y) mod n ですから、 e2/e1=(x*(E^Y))*(a*(E^-Y)) 　 　 　=x*(a^-1)*(E^Y)*(E^-Y) 　 　 　=x*(a^-1)*1 　 　 　=x*(a^-1) で簡単に求まりますが、 これからE,a,x,E^Yのどれかを求めるのは難しいはずです。 215 名前：63 ◆oYI7WOcH/A [04/07/18 20:13] ん〜外したか。 > C=(M1*e1)-(M2*e2) (mod n) > (C>nとなるようにする) の両方が正しいなら、そんなCは存在しないよね？ 拡大解釈して、右辺のmod nを取る前にC'>nにして、それをmod nをしたものをCとすると どぶろく脳内を推測して読んだんだけど、どうやら外したらしい。 216 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 20:58] >>215 > C=(M1*e1)-(M2*e2) (mod n) > (C>nとなるようにする) (M1*e1)-(M2*e2)>nとなるようにする です。 ほんとすいません ばれては困るのは E^Y,a,xでした。 Eがばれても (E^Y)^2がわかるだけで E^Yにはたどり着けません。 (Yを適当に大きな数にする) 217 名前：１３２人目の素数さん mailto:sage [04/07/18 21:17] どぶさんへ nは素数じゃなくてもいいの？ 218 名前：63 ◆oYI7WOcH/A [04/07/18 21:18] ん？そうだとすると、やはり、取れない平文がたくさん出てくるよ。 例えば、e1<e2なら、M1より大きなM2は絶対に取れない。 凄くゆるゆるの評価をしていてもこんな感じだけど。 219 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 21:21] >>217 gcd(a,x)=1 gcd(a,n)=1 gcd(x,n)=1 gcd(((E^Y)mod n),n)=1 ↑全てを満たせば a,x,nが素数でなくても OKです。 220 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 21:25] >>218 >例えば、e1<e2なら、M1より大きなM2は絶対に取れない。 これはC<0の時のことを言っておられるのでしょうか？ そのときはC+nをするので問題ないです。 221 名前：63 ◆oYI7WOcH/A [04/07/18 21:31] だから、それが脳内仕様なんだって、、、 問題ないです、ってありまくりだよ？ C<0だと、C+nをしても、C>nにはならないと思う。 お願いだから、そのときはさらにnを足しますとか言わないでね…。 222 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 21:51] > C=(M1*e1)-(M2*e2) (mod n) > (C>nとなるようにする) (M1*e1)-(M2*e2)>nとなるようにする です。 ほんとすいません (M1*e1)-(M2*e2)>n のときに C=(M1*e1)-(M2*e2) (mod n) (M1*e1)-(M2*e2)をmod nして C<0なら C+nをします。 (M1*e1)-(M2*e2) (mod n) をしたあとにC<0であっても、 -n<C<0 Cの範囲は↑ですから、 C+nをすると -n+n<C+n<0+n⇔0<C+n<n 一回nを加算すればOK 223 名前：63 ◆oYI7WOcH/A [04/07/18 22:47] 余計、意味が通じなくなった。 必死に説明しているところ悪いけど、 (M1*e1)-(M2*e2)>nとなるようにする (C>nとなるようにする) の二行を消すだけでいいんじゃないの？ 少なくとも上の説明だと、C>nにはなってないよ。 全然OKじゃない。 224 名前：１３２人目の素数さん mailto:sage [04/07/18 22:57] 相手をすることが必ずしも親切なことにはならないという好例 225 名前：１３２人目の素数さん mailto:sage [04/07/18 23:46] まさしく >184 だな 226 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/18 23:46] >(M1*e1)-(M2*e2)>nとなるようにする >(C>nとなるようにする) > >の二行を消すだけでいいんじゃないの？ いえ、Cは(M1*e1)-(M2*e2)>nをmod nした結果です。 (M1*e1)-(M2*e2)>nは消してはいけません (M1*e1)-(M2*e2)<nだと 仮に、e1<e2とするとき mod e2で (M1*e1)-(M2*e2) (mod e2) =(M1*e1) (mod e2) - (M2*e2)mod e2 =(M1*e1) (mod e2) e1,e2が分かっているので M1も求めれてしまいます。 M1が分かればM2が分かります。 ∴(M1*e1)-(M2*e2)>n の必要があります。 e1,e2のビット数は大体nと同じくらいになるので M1*a>nとなるようにM1の下限を決めてやれば大丈夫 もし、どうしても C=(M1*e1)-(M2*e2) mod nが嫌なら C=(M1*e1)+(M2*e2) mod nにすればよいです。 ただ、 M'=(M1*a)+(M2*x) (全てmod n) となり、M2が負数として符号が反転した状態で出てきて、 気持ち悪いので C=(M1*e1)-(M2*e2) mod n としてマイナスにしただけです。 (これは仕様変更ではありません。) (あくまでも説明のために書いただけです。) 227 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/19 07:05] |(M1*e1)-(M2*e2)|>nは消してはいけません 絶対値(M1*e1)-(M2*e2)絶対値>nは消してはいけません が正確です。 228 名前：１３２人目の素数さん mailto:sage [04/07/19 12:42] >222,226 ：意味不明 L=(M1*e1)-(M2*e2) とするとき、 　１．　n <　L 　２．　0 <= L <=n 　３．　L < 0 のそれぞれの場合におけるその暗号化Cを提示してください １は C=L mod n だとして、２と３は？ >(M1*e1)-(M2*e2)>nとなるようにする (C>nとなるようにする) > Cは(M1*e1)-(M2*e2)>nをmod nした結果です。 「C=(M1*e1)-(M2*e2) mod n」は、次のどっちの意味？ 　１．　C と (M1*e1)-(M2*e2) は n を法として合同 　２．　C は (M1*e1)-(M2*e2) を n で割った余り 229 名前：１３２人目の素数さん mailto:sage [04/07/19 12:48] >228 の後半書き直し＋α >(M1*e1)-(M2*e2)>nとなるようにする (C>nとなるようにする) > Cは(M1*e1)-(M2*e2)>nをmod nした結果です。 「C=(M1*e1)-(M2*e2) (mod n)」は、次のどっちの意味？ 　１．　C と (M1*e1)-(M2*e2) は n を法として合同 　２．　C は (M1*e1)-(M2*e2) を n で割った余り あと 　「X = 2 (mod 5)」なるXを挙げてください。 　「Y = 8 (mod 5)」なるYを挙げてください。

---

---

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

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