暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 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] 数学もそうだけど、細かいこと書けない（できない）と特許とれないよ 特許申請した人に聞いたが、この文書じゃ門前払いらしい。 特許とりたいのなら、そちらも調べたほうがいいと思う。 それ以前に特許とりたいのなら、ココで明かしたらダメかもね。 悪いがそんな心配する必要はないと思うけど。 260 名前：77 mailto:sage [04/07/20 03:15] >>257 工学部の実験レポートで叩き込まれるのは、まさにその 「○○を曖昧さ無く記述して他人に伝える能力」だったりします。 数式＋文章で説明するのが不得意なら、Experimentというか プログラムコードっぽく記述してみたら？ 261 名前：白シャツ [04/07/20 17:03] 盛り上がってますね >>258 離散対数問題に最初から帰着していないので， 証明も何も 「C=(M1*e1)-(M2*e2) (mod n)」 なる不定方程式が解ければ終わりといえば良いのでは? この議論がありませんよね． 秘密鍵を求めろというのならば離散対数云々になるけれど， 暗号攻撃という観点からは秘密鍵がわからなくても 平文が求まればOKなのです． ディオファントス不定方程式だたっけ? LLLアルゴリズム等の既定縮小アルゴリズムで 平文の候補がしぼりこめるので，あとはその中から 全数探索で平文みつかりました， みたいな感じで終わった暗号がたくさんあります． この暗号もそういうのに似た系統だと思うよ． 正直言って前作の方がオリジナリティあっておもしろかったかも． 262 名前：白シャツ [04/07/20 17:14] >>202 ほんとだ．>>199の間違い． スマソ． ついでに訂正 >>261 誤>LLLアルゴリズム等の既定縮小アルゴリズムで 正>LLLアルゴリズム等の基底縮小アルゴリズムで 263 名前：258 [04/07/20 17:25] いや、その > 「C=(M1*e1)-(M2*e2) (mod n)」 > なる不定方程式が解ければ終わり っていうのが、どれぐらい難しい問題なのかが分からないだろ？ もしかすると、なんらかの形の離散対数問題を解くのと同値だったり、それ以上に難しいかも知れない。 離散対数問題に帰着しているようにはどうやっても見えないが、 正確に分かりやすく書けっていう流れになっている時に適当なことを書くとまずいんじゃないか？ 適当じゃないっていうなら、この問題が簡単に解けるってことを示してやれよ。それが、この暗号の解法になる。 多分、法e2（ただしe2 < e1）のもとでCを考えるんだな。 C+ｋｎ = (M1*e1)-(M2*e2)のｋがどれぐらいか一つずつ変えていけば線形に変化するから分かる気がする。 勿論、後ろ三行は独り言で、正確じゃないかもしれない。 264 名前：１３２人目の素数さん [04/07/20 17:27] 数学なんて虚無の世界...... 数字なんて所詮人が作ったもの........ 人間か作ったものに人間が研究を重ねたって 所詮人間を超えられないよ....... aa..... 空しい。。。。。 265 名前：１３２人目の素数さん [04/07/20 17:28] 超える必要など無い。 限りなく近づく。そう、極限を目指すのだ。 266 名前：１３２人目の素数さん [04/07/20 17:31] 数学って極めれば人間になるんだ・・・。 頑張ってみよう。 267 名前：１３２人目の素数さん [04/07/20 17:34] 極限を目指せば目指すほど 現実社会との剥離が激しくなるのです 268 名前：白シャツ [04/07/20 17:56] >>263 確かに適当なこといってますね． あなたの言うことは正しい． 仕様がまとまってないので解析しにくいので あくまで感想です．まぁそういう本質的な部分に 行く前に穴が見つかるかもしれませんが． >> 「C=(M1*e1)-(M2*e2) (mod n)」 >> なる不定方程式が解ければ終わり >っていうのが、どれぐらい難しい問題なのかが分からないだろ？ >もしかすると、なんらかの形の離散対数問題を解くのと同値だったり、 >それ以上に難しいかも知れない。 ということを議論していませんよという指摘です． 一般の不定方程式を解くことと，離散対数問題が どちらが難しいかの議論は困難です．なんせ解が不定なんで 解の空間から当たり(平文)を特定するのが難しくなります． ただし，解の空間に平文が一様に存在するならという仮定があればですが． ただし，暗号なんで一意に復号する必要があるので 平文が存在する空間になんらかの制限，というか偏りがあって， あっさり出ちゃうことが多い．ナップザック系の暗号の敗因は そこです． 269 名前：白シャツ [04/07/20 17:56] >>268 の続き ということで，ナップザック系というか積和系の暗号の場合， 数学的にその議論を行うのは困難なので計算機回して攻撃してみました というような論文が結構あります．ということで，解法を示せとなると， 実際計算機を回すことになるんですぐにはできませんし，あんまり やる気もないです．まず理論的に方式に穴がないことが確認されて， どぶろく氏が本気で研究会などで発表する気があるなら そういう議論が必要になるので多少は手伝ってもよいと思うが． 関連するような文献さがしてさらしたらたら納得ですか? 例えば，東芝の清水氏が昔そういうことをやってられました． ダウソできるやつがあるかしらべてみませう． 270 名前：１３２人目の素数さん mailto:sage [04/07/20 18:07] >>263 今の段階では、何をしなければいけないかが分かっていないようだし、とりあえず 　・Xは〜を満たす値とする、　ただし、そのようなXが存在するかは証明が必要 　・〜するには〜なX, Yを求めれば良い、ただし、そのようなXが求められるかは証明が必要 のような感じで証明や説明は別途するあればもいいのじゃないかな。示すこと以前に、 　１．記号の意味 (mod) 　２．X=Y などの記述が、定義なのか方程式なのか 　３．値のとり得る範囲 ( C>n ) 　４．値の満たすべき条件 ( a:素数、gcd(a,n)=1 ) 　５．一意性、存在性、アルゴリズムなど、何を証明し何を具体的に求める必要があるかの提示 を順番にはっきりさせる段階だと思うんだけど そうしないと、話進める前に完全に「と」化してしまい、元も子もなくなる 271 名前：白シャツ [04/07/20 18:09] とりあえずこんなのがあった． 多分，日本応用数理学会の研究会でのOHPだと思うので 概要がわかるぐらいのものと思うけど． ttp://ntw.e-one.uec.ac.jp/jant/006-shimizu.pdf 272 名前：白シャツ [04/07/20 18:15] >>270 うん，同意．安全性の詳細な検討などは どぶろく氏にまとめてもらったやつを 「聞いてもらえる書き方」にブラッシュアップさせてから あということでよろしいか? 個人的には前作のC'→Cをもうちょっとつっこんで考えたい ところだったし，そっちやってます．ああいう発想の写像って あんまりないと思うので，どうなってるのか気になるんです． 273 名前：白シャツ [04/07/20 18:25] >>253 ところで，SICSに連絡って何? ぐぐったら岡山のセキュリティやさんみたいな会社でてきたけど， そういうこと? それともSCIS事務局か? それと本気で発表する気なら暗号学者っぽい人に連絡して 弟子入りするのがよいかもしれないよ． 正直言ってここだと実は「エライ先生」あいてに 失礼なこといってるかもしれないと密かに恐れてるんだけど(w 274 名前：１３２人目の素数さん [04/07/20 18:52] LLLって基底縮小アルゴリズムのことだったのか。 全然、意味が通じてなかった >>271のは綺麗にまとまってるね。 最後のスライドに、意地を感じるｗ 275 名前：白シャツ [04/07/20 23:50] >>274 いったん持ち上げて、LLLかけてみたら 探索空間がもとより小さくなりました で死んでいった暗号がけっこうあったらしいです。 276 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:47] 全部で12レスあります。 1/12 気になることがみつかったので 安全性のところで気になることを書いています。 C+kn = (M1*e1)+(M2*e2) についても私なりの考えを書いています。 公開鍵暗号です。 以下説明 a<n,x<n かつ gcd(a,x)=1 gcd(a,n)=1 gcd(x,n)=1 gcd(e,n)=1 かつ a*e>n x*e>n となるように適当にeを決める 最初の説明ではe=(ax)^Y mod n と書いていましたがeは別にaxのべき乗でなくても gcd(e,n)=1を満たせばいいと分かりました。 これにより余計に、a,x,eのどれかを求めるのが 難しくなっていると思います 277 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:47] 2/12 Aliceは公開鍵をつくるために 以下の計算をする e1=a*e mod n e2=x*e mod n 公開鍵は e1,e2,n 3Nビット Aliceは秘密鍵dをつくるために 以下の計算をする d*e=1 (mod n) つまり、 d=e^-1 (mod n) また、a,xより a*d1-x*d2=1となる 自然数で最小のd1,d2を求めておく 秘密鍵は a,x,d,d1,d2 4Nビット 278 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:48] 3/12 復号する際に (a*M1)+(x*M2)<nでないと 平文・暗号文が一意に決まらないので (a*M1)+(x*M2)<nである必要がある。 a<xのとき 暗号化できる平文の範囲は 0<=M<=a-1だから、 (a*(a-1))+(x*(a-1))<n ⇔(a+x)*(a-1)<nを満たすようにnを求めればよい (Bobはa,xの大きさが分からないので 暗号化できる平文Mの大きさをAliceに聞いておく) 暗号化 C=(M1*e1)+(M2*e2) _=e*((a*M1)+(x*M2)) (mod n) (-から+に変更) ((M1*e1)+(M2*e2)>nとなるようにする) この条件については補足で書いてます。 279 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:48] 4/12 最初は-にしていましたが復号して M'=(M1*a)-(M2*x)が -n<(M1*a)-(M2*x)<0のときに t=(M1*a)-(M2*x)とすると 当然tは負の値ですが、 常に正になるようにt+nすると M'=t+nで復号してもM1,M2の値がきちんと戻りませんでした。 tのままで復号すれば平文を得ることができましたが、 tの値が負の場合も考えると Aliceはどの時にM'=t-nとして、 どのときにM'=tのままで復号するか判断できません。 tの値を負のままで伝えるということも考えましたが、 Eveに余計な情報を与えるだけなので、止めにしました。 C=(M1*e1)+(M2*e2)ならM'=(M1*a)+(M2*x)は 常に0<=M'<nとなる((a*M1)+(x*M2)<nとなるようにnの値を決めていることに注意)ので 復号した際にもきちんと平文を求めることができました 280 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:49] 5/12 復号 M'=C*d (mod n) 　=e*((a*M1)+(x*M2))*d (mod n) 　=ed*((M1*a)+(M2*x)) (mod n) 　=(a*M1)+(x*M2) (ここでmod nは必要ない) (a*M1)+(x*M2)>nとなるときは きちんとM'が求めれないから、 上のほうで(a*M1)+(x*M2)<nとなるようにnの値を求めた M1=(M'*d1) mod x M2=a-((M'*d2) mod a) ∴平文M1,M2が求められた 281 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:49] 6/12 補足 復号した時 M'=(M1*a)+(M2*x) < n でないとまずいので nのビット数をNとすると a,xのビット数はN/2より小さくなければならない。 M1,M2個々のビット数はN/2より小さいけれど、 一度に二つ平文を送れるので 大体一度に送れる平文はNビット位になる 正確には・・・ M1,M2のビット数をbとする。 M1,M2が小さな値の時に e*((a*M1)+(x*M2))<nとなるのを防ぎたいので a,xのビット数を(b+2ビット)として、 M1,M2で表現できる値は 0<=M1,M2<=(2^b)-1だから ↑のときM1,M2に2^bを加算してやって 2^b<=M1,M2<=(2^(b+1))-1としてやれば e*((a*M1)+(x*M2))<nとなる心配はなくなる 復号する時は出てきたM1,M2から2^bを減算してやればよい 282 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:50] 7/12 M1,M2はb+1ビット、a,xはb+2ビットだから M1*aのビットは(b+1)+(b+2) これと、M2*xもあるから (M1*a)+(M2*x)のビットは(2b+3)+1=2b+4ビット つまり、(M1*a)+(M2*x)は最大で2b+4ビットになる ∴n>2^(2b+5)であればよい これらより、nは2b+5ビットになる 一度に送れる平文は2bビットだから 2bビット毎に平文を暗号化する場合暗号文は2b+5ビットになる 例　M1,M2それぞれが64ビット(一度に送れる平文は128ビット)だとすると 暗号文は2*64+5=133ビットになります。 e*((a*M1)+(x*M2))<nについて 上の方法により (a*M1)+(x*M2)<nのとき 左辺は2b+4ビット eはビット数がnと同じでgcd(e,n)=1になるように選べばいいから e*((a*M1)+(x*M2))のビット数は (2b+5)+(2b+4)=4b+9≒4b だから、e*((a*M1)+(x*M2))<nの心配をする必要はない 283 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:50] 8/12 安全性 解読する時の鍵の候補はa,xのビット数に基づく e1,e2からa,x,eを求めようとする時は 離散対数問題に基づいている(んだと思う) 盗聴者Eveがわかるのは e1,e2,n e1*e2=(a*e)*(x*e) 　 　=(a*x)*(e^2) (全てmod n) e2/e1=(a*e)/(x*e) 　 　=x*(a^-1) (全てmod n) e1,e2からe,a,xのどれかを求めるのは困難 284 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:51] 9/12 今日思いついたのですが、 Eveは e1=a'*e' (mod n)となる任意の数a'を決める。 それに対応するe'も e'=e1*(a')^-1 (mod n) で求まる。 e2=x'*e'だから x'=e2*(e')^-1 e'*d'=1 (mod n) となるd'は d'=(e')^-1 (mod n) 整理すると e1=a'*e' (mod n) e2=x'*e' (mod n) e'*d'=1 (mod n) C=(e1*M1)+(e2*M2) =e'*((a'*M1)+(x'*M2)) (mod n) m=d*C =(a'*M1)+(x'*M2) (mod n) Eveはa',x'が分かるからM1,M2も求めれる・・・ ここの所はすごく重要だと思います。 (a'+x')*(a'-1)<nを満たすa',x'が存在することは確かです。 ですが、↑を満たすa',x'のペアは非常に少ないです。 また、Mの取れる範囲が非常に小さいので、 M1,M2に2^bを加算すれば問題ないと思っています。 285 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:52] 10/12 例 a=113,x=167,n=58061 e=37480,e1=54848,e2=46623 とするとき (a'+x')*(a'-1)<nを満たすa',x'のペアは 2<=a'<=58060 a≠a',x≠x'のときに (a',x',M_max)= (2,52412,1)(3,20557,2)(7,9259,6)(9,3610,8) (20,1571,19)(51,1103,50)(370,33,32) (740,66,65)(26425,3,2)(28162,1,0) 10個ありました。 a=113でaは7ビットだから使用されるM(=M1,M2+64)の値は 0+2^6<M<48+2^6⇔64<M<112(0<=M1,M2<=48) (740,66,65)のみ平文が0,1のとききちんと復号できる。 これはあくまでもa,xが小さいときの値です。 実際に使うとしたら128ビットぐらいにはなると思いますから、 (a'+x')*(a'-1)<nを満たす a',x'を求めるのは困難です。 M1,M2が上の例では0,1だったら一応復号できますが、 M1,M2についてEveは知らないので M1,M2が10や25だった時、間違った値を復号してしまっても その間違った平文が間違っているのかあっているのか判断がつきません。 ∴仮に(a'+x')*(a'-1)<nを満たすa',x'を求めたとしても 復号文が本当に平文と一致するのか分からない。 実際はa,xの値として同じくらいのビット数を使用するので 鍵は、そこから正しい鍵か判断できると思います。 286 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:52] 11/12 C+kn = (M1*e1)+(M2*e2)　について これについては私も分かっていました。 ですが、kの値が分からなければどうしようもありません。 たとえばt=k-100のとき C+(k-100)n = (M1'*e1)+(M2'*e2) ↑となるM1',M2'が求めれてしまいます。 ↑にn加算していって その都度M1',M2'を求めていったとしても 毎回毎回M1',M2'が求めれてしまうのですから どのM1',M2'が本当のM1,M2か判断がつきません。 ∴C+kn = (M1*e1)+(M2*e2)から M1,M2を求めるのは不可能だと判断しました。 平文→暗号文の膨らみ具合 一度に送れる平文をNとすると 暗号文はN+5ビットになる 287 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 00:53] 12/12 長所 暗号化速度が超高速 modを毎回するとしても演算がたったの6回ですむ 復号は a*d1-x*d2=1となる d1,d2をあらかじめ求めておけば 7回の演算ですみます。(4回から7回に訂正です) 短所 署名ができない 暗号文はNビット 送れる平文は約Nビットなのに 公開鍵が3Nビットと長い 秘密鍵も4Nビットと長い 288 名前：１３２人目の素数さん [04/07/21 00:56] さて、可燃物が投下されました。 正直どこがわかりやすくなったのかがいまいちわからんのだが。 289 名前：１３２人目の素数さん mailto:sage [04/07/21 01:02] これが大学のレポートなら読まれずに捨てられても文句言えない 290 名前：１３２人目の素数さん mailto:sage [04/07/21 01:07] まず、a,x,nの定義が再帰的になってる。 291 名前：白シャツ [04/07/21 01:08] とりあえず読んでみようかと思えるようにはなったかもしんない。 といいながら質問なんですが、 M1,M2は何？ 平文なんだろうけど、２つの平文を送るってことなのか、 ある平文MからM1とM2を作るってことなのか？ まぁそれぐらいは分かれって言われるかもしれないけど、 特にコメントあります？ それと、計算量評価に関しては言いたいことはあるんだけど、 先送りにします。 短所の >暗号文はNビット >送れる平文は約Nビットなのに >公開鍵が3Nビットと長い >秘密鍵も4Nビットと長い は気にするほどでない（というか悪いわけではないと思う）。 もっと驚異的(w なものでも信学論に採録されてる論文はある。 292 名前：白シャツ [04/07/21 01:11] >>289-290 印刷するのもうちょっと待つほうが良いかな？ 293 名前：１３２人目の素数さん [04/07/21 01:15] 自分がこれなら読めるって判断したのなら印刷すればいいんじゃない？ 少なくとも私には無理なので、まとまるのを待ちます。 294 名前：白シャツ [04/07/21 01:22] >>293 ダメ出ししないと直らなさそうだから結局すらないとダメかな。 とりあえず「零　赤い腸」が大詰めなんでクリアしたら刷ろう(w 295 名前：63 ◆oYI7WOcH/A [04/07/21 02:00] > a*d1-x*d2=1となる > 自然数で最小のd1,d2を求めておく が、曖昧。 d1が最小になるのか、d1+d2の和が最小になるのか、d1*d2が最小になるのか、etc. どういう解釈も出来る。どれでもいいのか？ 296 名前：１３２人目の素数さん mailto:sage [04/07/21 02:31] また見つかった。今度は致命的かな。 >>282 > e*((a*M1)+(x*M2))<nについて > 上の方法により > (a*M1)+(x*M2)<nのとき > 左辺は2b+4ビット > eはビット数がnと同じでgcd(e,n)=1になるように選べばいいから > e*((a*M1)+(x*M2))のビット数は > (2b+5)+(2b+4)=4b+9≒4b > だから、e*((a*M1)+(x*M2))<nの心配をする必要はない とあるが、これは、まったく意味のない議論をしている。 確かに、最後の一行は正しいが、そんなの誰も心配してない。 本当に心配をしなくてはいけないのは、 (M1*e1)+(M2*e2) < nのはずだ。 ≡と=の違いをさんざん言われてるのにな。。。 297 名前：１３２人目の素数さん mailto:sage [04/07/21 02:33] >>279 >tのままで復号すれば平文を得ることができましたが この一文がすごく引っかかる（他もだけど） これを読む限りmoduloってコンピュータのmod演算に任せきりで 自分で理解できていないと思いませんか？>ALL 298 名前：１３２人目の素数さん mailto:sage [04/07/21 02:35] だから群論の基礎からやったほうがいいって 299 名前：白シャツ [04/07/21 02:44] >>297 mpz_mod(M+t,M,n); とか意味わからないでやってるのかな。 300 名前：１３２人目の素数さん mailto:sage [04/07/21 05:30] 一応まとめてみたが・・・ a, x, n e は>276とし、以下「s mod t」は「sをtで割った余りv、但し0<=v<t」としてみる e1 は a*e mod n とする e2 は x*e mod n とする d は d*e=1 (mod n) を満たすdで 0<=d<n なるものとする d1, d2 は a*d1-x*d2=1となる自然数で最小のd1,d2とする （d1, d2の最小の意味が不明、d1, d2をどのように求めるか不明←私だけ？） 平文M1, M2は、(a*M1)+(x*M2)<n となるようにとる ((a*M1)+(x*M2)>0は？　M1, M2 >0 は？不明） (与えられたa,x,n に対して平文として取れるM1, M2はどのくらいあるのか不明←重要では？） MはM1, M2を文字列と見たときのそれらの連結？ （定義不明、しかし↑だとM=10010のとき、M1=110、M2=010と出来ないよね） 301 名前：300の続き mailto:sage [04/07/21 05:31] M1, M2の暗号文Cは 　・(M1*e1)+(M2*e2) mod n ？ 　・C≡(M1*e1)+(M2*e2) mod n を満たすC ？ （補足と(M1*e1)+(M2*e2)>n がポイントらしいが不明、前者でも後者でM'の定義から問題ないはず） （当然一意性等も不明） Cの復号文M'は C*d (mod n) とする M'=(a*M1)+(x*M2)となるので、 M'から平文は次のようにして得られる （未確認） M1=(M'*d1) mod x M2=a-((M'*d2) mod a) 302 名前：そして例１ mailto:sage [04/07/21 05:32] a=7, x=11, n=13, e=12^2=144 とすると、 e1=7, e2=11, d=1, d1=8, d2=5 となる M1*e1+M2*e2>n となる M1, M2>0 は (M1, M2)=(0, 0), (1, 0), (0, 1) のみ 仮にM1=1, M2=0とすると、M1*e1+M2*e2=7 よってCの候補は7, 20, 33, 46, ・・・ Cとしてどれを用いても、M'=7 このとき、 　(M'*d1 mod x)=(56 mod 11)=1 ＝ M1 　(a-(M'*d2 mod a))=(7-(7 mod 7))=(7-0)=7 ≠ M2 ？？ 303 名前：続けて例２ mailto:sage [04/07/21 05:35] nを変えてみた a=7, x=11, n=31, e=12^2=144とすると、e1=16, e2=3, d=14, d1=8, d2=5 M1=1, M2=3とすると、M1*e1+M2*e2=25 このときCの候補は25, 56, 87, 118, ・・・ Cとしてどれを用いても、M'=9 このとき、 　(M'*d1 mod x)=(72 mod 11)=6 ≠ M1 ？？ 　(a-(M'*d2 mod a))=(7-(45 mod 7))=(7-3)=4 ≠ M2 ？？ 例１，２共に M1, M2 が元通りにならない・・・計算間違えてるかなぁ、間違えてるかも・・・ 304 名前：１３２人目の素数さん mailto:sage [04/07/21 05:39] >>299 訳分からなくなってきたので とりあえず突っ走って自分用（スミマセン）に とりあえず>300-303と纏め＋例を書いてみました。 がっ、もとに〜戻らないのは〜何故〜 確認はしてみましたが計算間違いの可能性有り・・・かな 305 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 07:33] >>291 M1,M2と分けているのは たとえば平文が 01101011 01000111のとき M1=01101011 M2=01000111 として分割して送ります。 一度に違った任意の平文を二つ送れます。 >>295 a*d1-x*d2=1となる自然数で最小のd1,d2とする d1,d2は拡張ユークリッドで求めます。 >>296 e1=a*e e2=x*eより (M1*e1)+(M2*e2) =(M1*a*e)+(M2*x*e) =e*((M1*a)+(M2*x)) e*((a*M1)+(x*M2))<n の心配がなければ (M1*e1)+(M2*e2) < n の心配もいらない 306 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 07:33] >>301 M1, M2の暗号文Cは 　・(M1*e1)+(M2*e2) mod n です。 割った余りです。 合同というわけではありません。 >>302>>303 nが下の説明の (a+x)*(a-1)<nを満たしていません。 a<xのとき 平文M1,M2の取れる最大値はa-1 M'=(M1*a)+(M2*x) a,xともM1はa<M1<xのときもOKだけど Bobはa,xについて知るわけないから 0<=M1,M2<aが保証されるようにすればよい M'=(M1*a)+(M2*x) M1,M2の最大値はa-1だから M'_max=((a-1)*a)+((a-1)*x) 　 　 　 =(a+x)*(a-1) ∴(a+x)*(a-1)<n を満たすようにnを決めればよい 307 名前：白シャツ [04/07/21 10:14] 疑問を羅列してみる。 ｎって何？ eの条件って、a*e>n、x*e>n　以外ないの？ 整数kを適当に選らんで当たりのkを引きあてたら GCD(e1+k*n,e2+k*n)=e じゃないの？ 308 名前：１３２人目の素数さん mailto:sage [04/07/21 11:03] >306 なんでnの条件がe1やらdを計算したあとの >278 3/12になってから出てくるんだよ・・・ 309 名前：296 [04/07/21 12:33] >>304 > e1=a*e > e2=x*eより どこにそんなの書いてあるんだよ。 e1=a*e mod n e2=x*e mod n だろ？ その上で、e*((a*M1)+(x*M2)) < n ならば (M1*e1)+(M2*e2) < nが本当に言えるか考えてみろ。 復号しても元に戻らないか、あっさりと平文が出てくる暗号文続出だがいいんだな？ 310 名前：１３２人目の素数さん mailto:sage [04/07/21 13:23] >>309 一応>304⇒>305 だよね 311 名前：白シャツ [04/07/21 13:37] >>309 >その上で、e*((a*M1)+(x*M2)) < n ならば (M1*e1)+(M2*e2) < n >が本当に言えるか考えてみろ。 >>276 に a*e>n、x*e>n　とある． a<n,x<nともかいてある．ここではa,xあるいはM1,M2がすべて正整数と仮定する． e*((a*M1)+(x*M2))=a*e*M1+x*e*M2>(M1+M2)*n>=n 故にe*((a*M1)+(x*M2)) < nは偽． a,xあるいはM1,M2がすべて正整数(ていうか自然数か?)だったら， 「e*((a*M1)+(x*M2)) < n ならば (M1*e1)+(M2*e2) < n」 は常に真? 312 名前：１３２人目の素数さん mailto:sage [04/07/21 13:37] >>310 そうです、ありがとう＾＾ 313 名前：白シャツ [04/07/21 13:46] >>311 自己ダメ出し．「あるいは」とか「常に」とか変なこと書いてますね． スマソ，脳内で訂正してくだちぃ． 314 名前：１３２人目の素数さん mailto:sage [04/07/21 13:47] >>311 なんで、そんな意味不明な議論をしてるの？って言おうと思ったら、自分が間違えてた。 >その上で、e*((a*M1)+(x*M2)) < n ならば (M1*e1)+(M2*e2) < n じゃなくて、どぶろくの言い方を引用するなら >その上で、e*((a*M1)+(x*M2)) < n の心配がないならば (M1*e1)+(M2*e2) < n　の心配がない だな。そして、これは真偽不定。 ちなみに、311は、「AならばB」は、そもそもAでないから、全体がTrueっていう意味のない議論だな。 315 名前：白シャツ [04/07/21 13:52] >>314 そういうことでしたか． >ちなみに、311は、「AならばB」は、そもそもAでないから、 >全体がTrueっていう意味のない議論だな。 この部分はネタよ．お約束じゃないの? 316 名前：梅どぶろく ■21Da3ggG3M mailto:sage [04/07/21 14:02] いやー、大量大量。爆釣だこりゃ 317 名前：１３２人目の素数さん mailto:sage [04/07/21 14:10] >>305 > たとえば平文が > 01101011 01000111のとき > M1=01101011 > M2=01000111 > として分割して送ります。 いや、だから、M2の頭の「0」が消えるのでは？ M1, M2共に8ビットだって分かっていれば良いけど、けどM1, M2って本来ただの数字なんでしょ？ 分割の仕方は規定されていないから、別の人は M1=0110101101 M2=000111 で送るかもしれない >一度に違った任意の平文を二つ送れます ここはメリットのようにかいてるけど、2つに分けて暗号化するよう定義しただけで、 それに1つしか送らなくても良い場合でも2つ送らないといけないし、 3つ以上のの文は同時に送れないから強調しないほうが良い（してはいけない）。 そこを強調すると、自分では計算高く言ったつもりでも、他人からは浅はかと思われるよ。 318 名前：１３２人目の素数さん mailto:sage [04/07/21 14:11] >>316 だそうです。 もう逝かれてるですが、皆さんどうします？ 319 名前：１３２人目の素数さん mailto:sage [04/07/21 14:22] ■と◆ 320 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 15:02] >>307 >eの条件って、a*e>n、x*e>n　以外ないの？ gcd(e,n)=1です。 >整数kを適当に選らんで当たりのkを引きあてたら >GCD(e1+k*n,e2+k*n)=e >じゃないの？ e1=a*e-n*p e2=x*e-n*q とできます。 p≠qですからちがうと思います。 >>309 すいません、mod nが抜けてました。 eの条件はgcd(e,n)=1だけですから eのビット数をnと同じくらいのビットにすれば e*((a*M1)+(x*M2)) > n　はいえます。 321 名前：白シャツ [04/07/21 15:18] >>320 >＞eの条件って、a*e>n、x*e>n　以外ないの？ >gcd(e,n)=1です。 それは>>276に書いてあるんでそういうこと聞いてるのではない． >e1=a*e-n*p >e2=x*e-n*q >とできます。 >p≠qですからちがうと思います。 a<n,x<n,e<nでe1,e2をそのようにとれるようなeって どうやって決めるの? 322 名前：白シャツ [04/07/21 15:21] >>321 >a<n,x<n,e<nでe1,e2をそのようにとれるようなeって e<nは無かった，失礼 323 名前：白シャツ [04/07/21 15:47] >>397 で言った >GCD(e1+k*n,e2+k*n)=e は誤爆ですね．もともと考えていたのは >>320 でどぶろく氏がいってるやつを叩く方法． GCD(e1+p*n,e2+q*n)=e になるような(p,q)が簡単に決まらないのかなと． これが安全になるようなeの条件が知りたい． とか思ってるうちにp=qじゃねーのと勘違いしました．スマソ． 324 名前：白シャツ [04/07/21 15:57] 漏れもどぶろく並にダメ書き込み連発してるな(w 投稿前に入念な査読をせねば． 325 名前：白シャツ [04/07/21 16:07] >>323 GCD(Π_p(e1+p*n)，Π_q(e2+q*n))もやってみる価値はありそうじゃない? 326 名前：１３２人目の素数さん mailto:sage [04/07/21 16:08] >>325 ない。 おまえら逝けよ 327 名前：１３２人目の素数さん mailto:sageうぜえ消えろ [04/07/21 16:20] 316=318の夏厨 誰も構ってくれないんで一人で壊れだすの図>>326 328 名前：１３２人目の素数さん [04/07/21 16:27] だああああああ。 >>320 > eのビット数をnと同じくらいのビットにすれば > e*((a*M1)+(x*M2)) > n　はいえます。 だから、それは、296で言ってるっつーの。 e*((a*M1)+(x*M2)) > nが言えて何が嬉しい？ そりゃ、おまえ、暗号化するやつが、秘密鍵まで知ってるぞ。 どぶろくが言いたかったのは、(M1*e1)+(M2*e2)　> n　だろ？ 話にならん。 こんなん考えてるより ・数式を正しく理解出来ない。 ・数式を正しく表現出来ない。 ・人の話をそもそも聞いていない。 の三拍子揃った人でも受け入れてくれる暗号のえらい先生を捜す方がいいんじゃないか？ むかつくと思うが、それなら余計、もうちょっと基礎からなんとかしろ。 言っておくが、これは些細な問題じゃない。 きちんと数式を評価出来てないために起こる、暗号系の穴を指摘しているんだ。 329 名前：素人な達人 [04/07/21 16:30] ってかわかんねぇ。 330 名前：梅どぶろく ◆rM4QWlepe6 mailto:sage [04/07/21 16:31] >>328 >e*((a*M1)+(x*M2)) > nが言えて何が嬉しい？ (M1*e1)+(M2*e2)　> nが言えるからうれしい だってさeはnと同じビット数としてとるんだよ？ a,xはnの半分くらいのビット数だから 問題ないよ 自分で考えてみて 331 名前：１３２人目の素数さん [04/07/21 16:37] もう一度だけ言う。 e1 ≠ a * e e2 ≠ x * e であり、なおかつ、 e*((a*M1)+(x*M2)) > n から (M1*e1)+(M2*e2)　> n が言えると、主張するんだな？ 332 名前：331 [04/07/21 16:54] と、思ったら、330のトリップ変わってるじゃないか。 すまん、どぶろく、別人だったら誤爆した。 328と今までの流れを読んでも間違いに気が付いていないなら、諦めるところだったが、 別人なら、しょうがない。すまんかった。 釣られちまったよ。。。orz

---

---

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

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