暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 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を挙げてください。 230 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/19 18:45] |(M1*e1)-(M2*e2)|>nが正しいとわかりました。 ですから、>>299さんの質問は L=(M1*e1)-(M2*e2) とするとき、 　１．　n <　|L | 　２．　0 <= |L |<=n について答えます。 1．については省略です。 2．については M1,M2の平文のビット数をNとおきます。 a,xのビット数はN+2とします。 nは2(N+2)+1=2N+5ビットとします。 Mの表す値は0〜(2^N)-1です。 M全てに2^Nを加算してやると Mの表す値が2^N〜(2^(N+1))-1になります。 e1,e2のビット数も大体2N+5ビットになります。 Lのビット数を計算してやると L(bit)=((N)+(2N+5))+1 　 　 =3N+6≒3N これらより、2．については考える必要はありません。 >「C=(M1*e1)-(M2*e2) (mod n)」は、次のどっちの意味？ >　１．　C と (M1*e1)-(M2*e2) は n を法として合同 1.の意味です。 Cが負の場合を考えたくなかったので、 >「X = 2 (mod 5)」なるXを挙げてください。 X=5k+2(kは整数、負でもOKです。) >「Y = 8 (mod 5)」なるYを挙げてください。 Y=5j+3(jは整数、負でもOK) 何か落とし穴でもあるのかな？ 231 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/19 18:52] 暗号化の演算回数は6回で間違いありません。 復号についてですが、6回の演算でした。 暗号化・復号ともに演算は6回ですみます。 e1,e2の値からa,x,E^Yいずれかの値を求めるのは困難である。 といってもいいと思いますが、みなさんはどうでしょうか？ 2chは公共の場として認められているのでしょうか？ 特許は放棄しようと思ってるんですが、 今から誰かが特許を申請しても無効になりますよね？ 232 名前：１３２人目の素数さん mailto:sage [04/07/19 19:18] >230 >2．については >・・・ >これらより、2．については考える必要はありません。 そのようなビット数の制限は>203以降公式な仕様として書かれてはいないと思いますが 制限しないといけないならそれは仕様として記述すべき事では？ 実際、M1*e1-M2*e2 < n となるような a, x, ・・・, M1, M2 ってとれますよね？ 例えば↓とか。 a=7, x=11, n=13, E=12, Y=2, e1=7, e2=11, M1=4, M2=2 233 名前：１３２人目の素数さん mailto:sage [04/07/19 19:19] >>232 正確には↓ 0 < M1*e1-M2*e2 < n 234 名前：１３２人目の素数さん mailto:sage [04/07/19 20:31] >>233 一応聞いておくと、>204にあるビット数云々は復号時のことで、暗号時には関係ないことで良いよね？ >232の例で M1=6, M2=2 とすると、M1*e1-M2*e2=20 > n で、C=20 (mod n)となる。 そこでこのM1, M2を、AさんはC=20で、BさんはC=33として、Kさんに送りつけたとして、 KさんはA, Bから送られてきたCの値は違うが、共に同じM1=6, M2=2って分かるの？ 今気付いたが、>232の例だと d=1 とできるな。けどビット数問題にひっかかるのかな。 235 名前：１３２人目の素数さん mailto:sage [04/07/19 20:43] 特許はこの間似たようなシチュエーションでの問題をＴＶでやっていて、 仮に>203-204どぶさんの暗号法を私が特許申請すると、 私の特許になるという話だったと思いますが・・・ はっきり覚えていないので、嘘言ってるかもしれません。 236 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/19 21:14] >>232の例で M1=6, M2=2 とすると、M1*e1-M2*e2=20 > n で、C=20 (mod n)となる。 >そこでこのM1, M2を、AさんはC=20で、BさんはC=33として、Kさんに送りつけたとして、 >KさんはA, Bから送られてきたCの値は違うが、共に同じM1=6, M2=2って分かるの？ nは一体いくつなんでしょうか？ nからeの値が変わるので大丈夫だとは思います。 237 名前：１３２人目の素数さん mailto:sage [04/07/19 21:23] >>236 「>232の例」なので、nは>232にあるようにn=13ですが・・・ ま、出来るのならいいです・・・ 238 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/19 21:33] >AさんはC=20で、BさんはC=33 ここのところが分かりませんでした。 nが一つであればCが二つにはならないと思います。 239 名前：１３２人目の素数さん mailto:sage [04/07/19 21:54] >>238 何故2つにならないの？ 2つになると思ったので、わざわざ>299の質問したのだけど・・・ M1*e1-M2*e2 > n のときは C = M1*e1-M2*e2 (mod n) である。 M1*e1-M2*e2 = 6*7-2*11 = 20 だから C = 20 (mon n) である。 >230で言われたように、これはCと20はnを法として合同という事であるから、 Cとしては、7, 20, 33, 46, 59, ・・・をとることができる。 ただC>nでないといけないとのことなので、Cは 20, 33, 46, 59, ・・・ としてよいことになる。 仮にこの暗号を使って、或るグループのリーダーKが、 メンバーA,Bが正式会員であることを調べるため、 そのメンバーの証拠 M1=6, M2=2 を送るように要請したとき、 Aはそのコードを C=20 で、Bは C=33 として送ってきた。 こういうストーリー。 240 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/19 22:07] >>239 最後にC (mod n)してないじゃん 20≡7 (mod 13) 33≡7 (mod 13) だから暗号文は7になります 241 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/19 22:10] C>nは間違いです。 正確には |(M1*e1)-(M2*e2)|>n です。 t=(M1*e1)-(M2*e2)とおくと |t|>n C=t (mod n) です。 242 名前：１３２人目の素数さん mailto:sage [04/07/19 22:17] >>241 そういうこと？もう情報が散らばりすぎだよ・・・ 243 名前：１３２人目の素数さん mailto:sage [04/07/19 22:31] >>242 ちょっとまった、C=t (mod n)なんでしょ？ だから C=20 (mod 13) だろうが、C=7 (mod 13)だろうが、C=33 (mod 13)だろうが、 >230でいってるように「C=L (mon n)」は、「CとLはnを法として合同」なんだから、 Cとして7でも20でも33でもいいのでは？ 合同だとC<nである必要はないよね。 >240で突然 「33≡7 (mod 13) 」な風に合同の記号「≡」をもってくるのは卑怯だなぁ ≡と＝がごちゃ混ぜになってると思って>229の質問したのにさ・・・ 結局>230の回答に間違いありでしょ？だって >>「X = 2 (mod 5)」なるXを挙げてください。 >X=5k+2(kは整数、負でもOKです。) って書いているし。 244 名前：１３２人目の素数さん mailto:sage [04/07/19 22:34] >>梅どぶろく 今までに指摘されたことを改善して、最初からまとめ直せ。 >>184とかも、ちゃんと読んだか？ 245 名前：１３２人目の素数さん mailto:sage [04/07/19 22:38] 分かると思うけど、>>243 内の >242 は >241 の間違いね 246 名前：１３２人目の素数さん mailto:sage [04/07/19 23:02] 誰かまとめてやれよ 訓練なしに一朝一夕で出来るようにはならんだろ 247 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/19 23:21] C = t mod n t=59,n=37のとき C=59 mod 37 = 22 で、Cは一つの値を取るといいたいんです。 248 名前：１３２人目の素数さん mailto:sage [04/07/19 23:22] といって>246がやらないのは面倒くさいのと、 根が深そうということが分かってるからでしょ？ ココ見てる人は皆同じ気持ちだと思うよ。 >184では数学に関して言ったけど、システム開発やプログラミング関連の仕事だと、 提出されてきた仕様がこれなら、その会社とは一切取引しないなぁ。 だって行き当たりばったりでバグ取りするの目に見えてるし、 テストしんどそうだし、発見したバグも認めてくれないさそうだし。 249 名前：１３２人目の素数さん mailto:sage [04/07/19 23:29] >>247 >232でn=13といってるんだけど・・・ >232, >239の設定のもとで話をしているのなら nをそんなコロコロとと変えたらダメでしょ？ >229の >「C=(M1*e1)-(M2*e2) (mod n)」は、次のどっちの意味？ >　１．　C と (M1*e1)-(M2*e2) は n を法として合同 >　２．　C は (M1*e1)-(M2*e2) を n で割った余り に対して、>230で１だと回答したけど２な訳ですよね？ １の合同だと一意に定まらない >Cは一つの値を取るといいたいんです にはどうすればいいのかまず考えないと・・・ 250 名前：１３２人目の素数さん mailto:sage [04/07/19 23:32] >>246 やろうとしない奴は一生出来ないよ。同じように失敗を繰り返して、 改善しようとする努力も見られないようではね・・・。 251 名前：１３２人目の素数さん [04/07/20 00:01] >>250 梅どぶにしてみればなんでこんな細かいところにみんなこだわっているんだ、 なんて粘着厨が多いんだろう2chは、ぐらいに思ってるんだろうな。 でも、いいやつ多いんだな、暗号界って。 252 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/20 00:11] ごめんなさい、数学の厳密ないいまわしはわかりません。 私の考えは2．だったようです。 大学の数学的な素養がぜんぜんありません。 まとめについては私でよければ明日行います。 253 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/20 00:16] >>251 暗号の本質と関係ねぇだろーが ねちねちうるせぇんだよ(#ﾟДﾟ)ｺﾞﾙｧ!! ってちょっぴり思ってた まあ、私の説明が分かりにくいから 色々と突っ込まれてるんだろう もっと人に分かりやすい説明を考えます。 あと、SICSにもメールしてみた。 254 名前：１３２人目の素数さん mailto:sage [04/07/20 00:25] 本質的な説明を後出しするのは数学的素養とかそういうこと以前の問題 255 名前：251 [04/07/20 00:39] おいまて、ホントにそう思ってるのか？ 暗号の本質って、まさにそのみみっちぃー所だぞ？ 細かいところを無視すれば、だいたい安全なものなんて誰でも作れる。 そういう細かいところを気にしなくていいんなら、セキュリティやってる人なんてみんな失業だろう。 256 名前：１３２人目の素数さん mailto:sage [04/07/20 00:51] >私の説明が分かりにくいから色々と突っ込まれてるんだろう 悪いけどそんなレベルでは・・・ >暗号の本質と関係ねぇだろーが ねちねちうるせぇんだよ(#ﾟДﾟ)ｺﾞﾙｧ!! 言いたいことは分かる・・・けど、それは数学してない人が数学語るときの言い訳です。 本質に入る前にこの程度のことを突っ込まれると、次からは相手にしてもらえない世界かも。 (↑読んでムカッとくるなら図星） >252 最低、合同、剰余、最小正剰余くらいは調べてからにしてください。 257 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/20 00:59] >>255 いや、分かっておくれよって感じです。 脳内仕様を人に伝えるのは難しいと思いました。 258 名前：１３２人目の素数さん [04/07/20 01:14] まとめる時に最低限気にして欲しいこと ・値を厳密に評価してから正確に書く。 数式の表現方法が分からないなら、文章でも構わないから、 絶対に、曖昧に適当に書くな。 ・細かい途中式はいらん。 途中式を見せられないと計算出来ない人はそんなレス読んでない。 どうしても気になるなら暗号的に重要な変換の部分だけ書く。 ・何かを適用するなら、ちゃんとその定義にあってるかどうかを確かめろ。 例えば、離散対数問題の困難性の定義からは、オレにはこの暗号の安全性は示せない。 むしろ、示せないことを証明出来そうな気がする。 259 名前：１３２人目の素数さん mailto:sage [04/07/20 01:44] 数学もそうだけど、細かいこと書けない（できない）と特許とれないよ 特許申請した人に聞いたが、この文書じゃ門前払いらしい。 特許とりたいのなら、そちらも調べたほうがいいと思う。 それ以前に特許とりたいのなら、ココで明かしたらダメかもね。 悪いがそんな心配する必要はないと思うけど。

---

---

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

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