暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 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 333 名前：白シャツ [04/07/21 17:09] >>332 >>115-116で同一人物との申告があるけどこれ本当かな? 334 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 19:09] >>332>>333 本物です。typoしちゃったんです。 >>331 >e1 ≠ a * e >e2 ≠ x * e >であり、なおかつ、 >e*((a*M1)+(x*M2)) > n >から >(M1*e1)+(M2*e2)　> n >が言えると、主張するんだな？ 言えますよ。ビット数で考えてみてください。 e<nでe,nのビット数をNとします。 e1=a*e mod n e2=x*e mod n だから、e1,e2もNビットにできます。 というか、e1,e2がNビットになるようにeを調節する C=e*((a*M1)+(x*M2)) mod nと変形できる 　=(e mod n)*(((a*M1)+(x*M2)) mod n) ここで、(a*M1)+(x*M2) について考える (a*M1)+(x*M2)<nとなるようにnを選んでいる >>282の1-7行辺りより a,x,M1,M2 とnのビット数の比は約1：2 ∴a,x,M1,M2≒(1/2)Nビット (a*M1)+(x*M2) は約Nビットとなる e<n,(a*M1)+(x*M2)<nだから (e mod n)*(((a*M1)+(x*M2)) mod n) =e*((a*M1)+(x*M2)) eはNビット,(a*M1)+(x*M2)は約(1/2)Nビットだから e*((a*M1)+(x*M2))は約(3/2)Nビットとなる これはnのビット数Nより大きい ∴(M1*e1)+(M2*e2)　> n 335 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 19:11] (M1*e1)+(M2*e2)　> n (M1*e1)は(1/2)Nビット数とNビット数の積だから (3/2)Nビットになる 336 名前：１３２人目の素数さん mailto:sage [04/07/21 19:17] お願いだから、どっかにHTMLで成形してUPしておくれやっし 337 名前：１３２人目の素数さん mailto:sage [04/07/21 19:22] >>336 それするなら、訂正ごとに別バージョンとしてUP 旧バージョンも保存して公開しておいてほしい 338 名前：１３２人目の素数さん mailto:sage [04/07/21 19:38] 出たよ、脳内仕様変更 >>320にははっきりと > eの条件はgcd(e,n)=1だけですから と書いてある。 でも334では、 > だから、e1,e2もNビットにできます。 > というか、e1,e2がNビットになるようにeを調節する と書いてある。 こういうのをｅの条件って言うんだ、わからんのか。 ちなみにランダムにｅを取ったときに条件を満たすｅが取れる確率はちゃんと評価したか？ 限りなく1に近いなら、まだ許そう。ざっと見積もって1/16だぞ？ こんな特殊な条件を > 自分で考えてみて の一言ですませる気だったのか。 しかも、何事もなかったように「言えますよ」とはなぁ…。 さらに、脳内仕様変更をいつものこととしてそれを受け入れても、334の式変形は間違ってる。 C=e*((a*M1)+(x*M2)) mod nと変形できる 　=(e mod n)*(((a*M1)+(x*M2)) mod n) ではない。 C=e*((a*M1)+(x*M2)) mod nと変形できる 　=((e mod n)*(((a*M1)+(x*M2)) mod n) mod n) だ。だから、それ以降の証明も本質的なところで大嘘になっている。 お願いだから、誰かも言っていたが、せめて自分の使っている式の意味ぐらい理解してから書いてくれ。 339 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 19:42] openofficeの数式エディターでupしようと思います。 使い方勉強してくるのでupはしばしお待ちください。 340 名前：１３２人目の素数さん mailto:sage [04/07/21 19:47] eもそうだけど、Mはどうなんだ？ >>300 >平文M1, M2は、(a*M1)+(x*M2)<n となるようにとる >((a*M1)+(x*M2)>0は？　M1, M2 >0 は？不明） >(与えられたa,x,n に対して平文として取れるM1, M2はどのくらいあるのか不明←重要では？） 341 名前：１３２人目の素数さん [04/07/21 19:52] >>340 Mは、 0 < M1, M2 < min(a, x)で取れば問題ないっぽい。 少なくともどぶろくの提示した条件は満たす。 暗号学的に問題がないかどうかは、この際問題ではない( w 342 名前：１３２人目の素数さん [04/07/21 19:57] むしろ、>>63の > a*d1-x*d2=1となる > 自然数で最小のd1,d2を求めておく が、曖昧。 d1が最小になるのか、d1+d2の和が最小になるのか、d1*d2が最小になるのか、etc. どういう解釈も出来る。どれでもいいのか？ が気になる。これが分かれば、いまんところ、仕様を補完出来るんだが。 343 名前：１３２人目の素数さん mailto:sage [04/07/21 20:02] >>342 >295じゃないの？ 344 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 20:08] >>338 一応>>282の18行目に書いておりますが、 条件は一気に最初に書くようにしたほうがいいですね。 いきなり条件だけ書いても意味がわからないと思ったので 途中途中で条件書いてました。 今度からは条件を一気に最初に書いておいて この条件についてはどこそこに説明書いてます。 って表記するようにします。 >C=e*((a*M1)+(x*M2)) mod nと変形できる >　=((e mod n)*(((a*M1)+(x*M2)) mod n) mod n) >だ。だから、それ以降の証明も本質的なところで大嘘になっている。 すいません、式変形は>>388さんの式が正しいです。 でも、eがe<nでnと同じビット数を取るときは >(M1*e1)+(M2*e2)　> n >(M1*e1)は(1/2)Nビット数とNビット数の積だから >(3/2)Nビットになる つまり、(M1*e1)+(M2*e2)　> n で納得していただけますよね？ >>340>>341 >>281の「正確には・・・」 を見てやっておくんなまし 345 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/21 20:10] >>342 拡張ユークリッドの互除法により a*d1-x*d2=1となる 自然数で最小のd1とd2を求めておく 346 名前：１３２人目の素数さん mailto:sage [04/07/21 20:11] Mも(M1*e1)+(M2*e2)　> n じゃなきゃいかんから、 >320, >334, >338 で話題になってるeの条件によるんだよな 結局値のとる範囲が後出しされてるんだよな プログラミングなるんなら最初に宣言したり、どの範囲でOKか意識するはずなのに 上手く動いてから、後付けで仕様のほうをブツにあわせていくタイプか？ 347 名前：１３２人目の素数さん mailto:sage [04/07/21 20:13] >>345 って言っておられますぞよ・・・ 辞書式順序か？ 348 名前：１３２人目の素数さん [04/07/21 21:32] >>344 悪いが、まだおかしい。 > 一応>>282の18行目に書いておりますが、 っていうのは、 > eはビット数がnと同じでgcd(e,n)=1になるように選べばいいから のことだよな？ e1,e2がNビットになるようにeを調節するんであって、 eをnとビット数が同じになるようにしたからと言って、 e1とe2がNビットになるわけではないぞ。 だから、 > eがe<nでnと同じビット数を取るときは > >(M1*e1)+(M2*e2)　> n > >(M1*e1)は(1/2)Nビット数とNビット数の積だから > >(3/2)Nビットになる > つまり、(M1*e1)+(M2*e2)　> n > で納得していただけますよね？ は、納得出来ない。（と、いうより、間違っている） 明らかに、e,e1,e2を混同している。 自分で作った変数ぐらい面倒見て下さい。 349 名前：白シャツ [04/07/21 21:50] >>339 できればoooだけじゃなくてpdfもあるとうれしい。 oooでコンバートできるよね。TeXで作りやがれとまでは言わないし。 oooとか入れるの面倒くさい人多いでしょ。 ふつうはPS,PDFぐらいじゃないと読んでもらえないし。 350 名前：１３２人目の素数さん mailto:sage [04/07/21 21:56] TeXで書いた。pdfにもなってる。だれか、あげるところ用意して。 でも、やっぱり、 >>345の 拡張ユークリッドの互除法により a*d1-x*d2=1となる 自然数で最小のd1とd2を求めておく の意味が分からない。「自然数で最小の」はd1にかかってるの？d2はなんでもいいのか？？？ 351 名前：白シャツ [04/07/21 22:04] 商と剰余を混同してないかな？ それでサイズの押え方がおかしいとか 352 名前：１３２人目の素数さん mailto:sage [04/07/21 22:13] ところで拡張ユークリッドの互除法ってなーに？ 普通のユークリッドの互除法とどう違うの？ 353 名前：１３２人目の素数さん mailto:sage [04/07/21 22:37] >>352 (a,b)を求めるのがユークリッドの互助法。 a*m+b*n=(a,b)となるm,nも同時に求めるのが拡張ユークリッドの互助法。 354 名前：１３２人目の素数さん mailto:sage [04/07/21 22:51] >>349 >できればoooだけじゃなくてpdfもあるとうれしい。 oooってなに？ 355 名前：白シャツ [04/07/21 23:04] >>354 OpenOffice.org→oooと省略しろとooo開発者が言ってると小耳にはさみますた。 356 名前：白シャツ [04/07/22 01:12] 核融合に閃光花火投下するぐらいかもしれないけど >>334 後半部分から抜粋 >(a*M1)+(x*M2) は約Nビットとなる >e<n,(a*M1)+(x*M2)<nだから >(e mod n)*(((a*M1)+(x*M2)) mod n) >=e*((a*M1)+(x*M2)) >eはNビット,(a*M1)+(x*M2)は約(1/2)Nビットだから 一番上と一番下で言ってること違わない？ 357 名前：白シャツ [04/07/22 01:42] 計算しましょう。 >>320の表記にしたがって e*a=e1+n*p e*x=e2+n*q　　とする e*((a*M1)+(x*M2))=e*a*M1+e*x*M2 =(e1+n*p)*M1+(e2+n*q)*M2=(M1*e1+M2*e2)+(M1*p+M2*q)*n ではない？ >>334で >∴(M1*e1)+(M2*e2)　> n なのはn,e1,e2がNビット(ただしe1<n,e2<n)、 M1,M2がN/2ビットとの条件からでしょう。 358 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 05:47] >eはNビット,(a*M1)+(x*M2)は約(1/2)Nビットだから これはこっちが間違ってます。 (a*M1)+(x*M2)は約Nビットだから こっちが正しいです。 約(1/2)Nビットなのはa,x,M1,M2のビット数です。 359 名前：１３２人目の素数さん mailto:sage [04/07/22 06:30] ａ，ｂが互いに素な正の整数のとき 整数ｘ，ｙがａｘ−ｂｙ＝１を満たしているならｘが増えればｙも増えるので ０≦ｘ，０≦ｙ，ａｘ−ｂｙ＝１という条件を満たすもので ｘが最小になるものとｙが最小になるものとｘ＋ｙが最小になるものと ｘｙが最小になるものは全て同じ。 360 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 09:08] 具体例で説明します。 ここでは、e1,e2の大きさや (e1*M1)+(e2*M2)>nは考慮していません。 Aliceはまず、gcd(a,x)=1となるa,xを適当に決める ここでは a=113,x=167とします。 つぎに、 (a-1)*(a+x)<n　かつ　gcd(a,n)=1 gcd(x,n)=1 となるようにnを決めます。 ここでは、(113-1)*(113+167)=31360<nとなる nとしてn=58061にします。 gcd(e,n)=1となるようにeを決めます。 ここではeとしてe=37480を選びます。 次に公開鍵を作ります。 e1=a*e mod n =113*37480 mod 58061 =54848 e2=x*e mod n =167*37480 mod 58061 =46633 今度は秘密鍵を作ります。 e*d=1 mod n 37480*d = 1 mod 58061 となるdはd=30702となります。 a*d1-x*d2=1 113*d1-167*d2=1となる 自然数で最小のd1,d2のペアは (d1,d2)=(34,23)になります。 361 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 09:10] 公開鍵は n=58061 e1=54848 e2=46623 秘密鍵は a=113 x=167 d=30702 d1=34 d2=23 になります。 BobはAliceから公開鍵を聞きました。 平文として (M1,M2)=(104,76)を送ってみます。 暗号化の式は C=(e1*M1)+(e2*M2) mod n C=(54848*104)+(46623*76) mod 58061 =14214+2387 mod 58061 =16601 BobはAliceに暗号文16601を送ります。 復号の式は M'=C*d mod nだから 　=16601*30702 mod 58061 　=24444 M1=M'*d1 mod xより M1=24444*34 mod 167 　=104 M2=a-(M'*d2 mod a)より M2=113-(24444*23 mod 113) 　=113-(37) 　=76 ∴Aliceは 平文(M1,M2)=(104,76)を得ることができました。 362 名前：１３２人目の素数さん [04/07/22 11:13] >>359 うん、そうだね。 実際計算してて気が付いた。 363 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/22 12:44] 梅暗号の安全性の証明を 一般化するとこんな感じかな？ A=a*k mod n X=x*k mod n としてA,Xが与えられるときに gcd(a,x)=1,gcd(a,n)=1,gcd(x,n)=1 かつ a<x かつ (a-1)*(a+x)<nを満たす a,xを求めるのは困難か否か？ (a=1,2は除く) 梅暗号としては A=a*k mod n X=x*k mod n としてA,Xが与えられるときに gcd(a,x)=1,gcd(a,n)=1,gcd(x,n)=1 かつ a<x かつ M_min*(a+x)<n M_max*(a+x)<n かつ M_min<a,x M_max<a,x を満たす a,xを求めるのは困難か否か？ (※このレス中で出てくる数はすべて自然数です)

---

---

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

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