暗号数学について語ろう

1 名前：１３２人目の素数さん [04/06/25 15:52] 必要な基礎教養・教科書・就職・将来性等。 何でも語ってくだしゃれ。 2 名前：１３２人目の素数さん [04/06/25 16:01] 2 3 名前：１３２人目の素数さん [04/06/25 16:34] 楕円離散対数（翻訳書が沢山出ている） 4 名前：１３２人目の素数さん [04/06/25 17:37] 有限体の理論 素因数分解のアルゴリズム 5 名前：１３２人目の素数さん mailto:sage [04/06/25 21:29] 5 6 名前：１３２人目の素数さん mailto:sage [04/06/25 22:16] 形を変えた数論スレになる予感 7 名前：１３２人目の素数さん mailto:sage [04/06/25 23:12] 7 8 名前：１３２人目の素数さん mailto:sage [04/06/26 08:07] 8 9 名前：１３２人目の素数さん [04/06/26 08:39] 近い将来、誤り訂正符号や隠し署名技術と融合するであろう。 10 名前：１３２人目の素数さん [04/06/26 10:00] 公開鍵暗号のしくみとは？ 11 名前：１３２人目の素数さん [04/06/26 18:07] 数論スレ賛成。 12 名前：１３２人目の素数さん [04/06/26 22:14] >> 10 解を計算して得るのにかかる時間が、 暗号化とある情報を知っている場合の復号の場合は、現実的な時間で、 正面から復号したときには、非現実的な時間になる。 13 名前：１３２人目の素数さん mailto:sage [04/06/27 00:23] 9 14 名前：１３２人目の素数さん [04/06/27 17:27] >>10>>12 具体的に、有名な例を3つ挙げると、 RSA暗号：素数p, qを取り、M=pqとし、sをφ(M)=(p-1)(q-1)と互いに素な整数とする。 このとき、s*t≡1(mod φ(M))となる整数tが存在する。そして、 m=n^sならばm^t≡n^{st}≡n(mod M)が成り立つが、Mとsからtを計算するのは難しい （Mを素因数分解すればφ(M)が計算できるが、これが難しい為）。 そこで(M, s)を公開しておけば、誰でもm=n^sによってn(mod M)を暗号化できるが、 tを知らなければ復号するのは難しくなるという仕組み。 離散対数暗号：素数pと(g, p)となる整数g, および任意の整数xをとる。外部には pおよび(g, g^x)(mod p)を公開する。g, g^xをそれぞれs乗することでg^s, g^{sx}を 得ることができ、これから任意の整数n≠0に対して(n*g^{sx}, g^s)(mod p)を簡単に得ることが できる。これを送信する。xを知っていれば、n*g^{sx}*(g^s)^{-x}=nなので簡単にnを得ることが出来るし、 sを知っていればn*g^{sx}*(g^x)^{-s}=nなのでやはり簡単にnを得ることが出来るが、 公開された情報(p, g, g^x)および送信された情報(n*g^{sx}, g^s)からsやxを得るのは 難しいので、復号が難しいという仕組み。 一般に(g, g^s)(mod p)から、sを求める問題を離散対数問題という。 もっとも最近は準指数時間でこの問題を解くアルゴリズムが出来ている。 Elgamal暗号：上記の離散対数暗号がZ/pZの乗法群を用いたのに対し、 有限体上の楕円曲線の点のなす群を用いる暗号。特殊な曲線を除いては、 この暗号を破る効率的なアルゴリズムは知られていない。 15 名前：１３２人目の素数さん [04/06/27 19:51] >>14 この説明だと 離散対数暗号→離散対数暗号＝Elgamal暗号 Elgamaｌ暗号→楕円Elgamal暗号 じゃないの。 なんかの本でこの説明（ていうか誤植？）みたことあるんですよね。 調べてみます。 16 名前：15 [04/06/27 21:55] >>15 スマソ、ソースわかりませんでした。 多分立ち読みして買わなかった本と思われ。 >>9 近い将来といわず、既にあると思うが。 McEliece暗号なんかは符号関係あるらしいと聞きましたけど どうなんでしょうか？ 17 名前：１３２人目の素数さん [04/06/28 00:24] 素体上の離散対数暗号 = ElGamal暗号でしょう。 でも、ElGamal暗号って、Diffie-Hellman鍵交換方式と本質的に全く同じことをやってるよね。 18 名前：15 [04/06/28 00:34] >>17 同意。 Elgamal暗号は（ワンタイム鍵共有＋暗号文送信）を 同時にするってのがポイントだと思う。 暗号化効率が１/2だけど、乱数が毎回入るんで RSAとは安全性のモデルが本質的に違うんですよね。 そういう意味でRSA-OAEPみたいなのが話が出てくるんでしょうけど。 19 名前：１３２人目の素数さん mailto:sage [04/06/28 13:26] 10 20 名前：１３２人目の素数さん [04/06/28 18:28] 楕円曲線が使えるなら、アーベル多様体も使えそうだ。 decode 長くなりそう。 21 名前：15 [04/06/28 22:37] >>20 コブリッツが超楕円曲線での暗号ってのを提案してます。 それでやるとCantorのアルゴリズムで加算するんで遅かったんですが、 ハーレー（つづりがわからん）の改良方式でやると結構速くできます。 さらに種数３や１１でやったらそれぞれ法が59ビット、30ビットで 楕円曲線の場合と安全性が同等になるといわれてます。 59だと64ビットレジスタに、30だと32ビットレジスタに乗るので、 多倍長演算無しで計算可能なんで楕円曲線とタメはれるくらい 速くなってるらしいです。　　　 長文失礼 22 名前：１３２人目の素数さん [04/06/28 22:51] 量子コンピュータ時代に生き残る公開鍵方式は なんだろう 23 名前：１３２人目の素数さん [04/06/28 22:52] >>21 それぐらいは長文のうちに入らん。気にすんな。 24 名前：15 [04/06/28 23:14] >>22 みかかの量子公開鍵暗号ってのがあります。 あれは量子コンピュータでしかCodecができないんですが。 基本的には積和型の暗号系が耐性あると言われてるが......疑問です。 >>23 サンクス 25 名前：１３２人目の素数さん mailto:sage [04/06/28 23:30] >>22 とりあえずMcElice暗号とLattice系(Ajitai-Dwork暗号やRegev暗号)はまだ今のところ破れてない． けど，そのうち破れる可能性は無きにしも非ず． 26 名前：１３２人目の素数さん [04/06/28 23:59] NP完全な問題を解くのは、量子計算機でも難しい（はず）。 だから、ナップザック問題を、綺麗に暗号に出来れば生き残れる（はず）。 そもそも、死んでいるというつっこみはなしの方向で。 27 名前：１３２人目の素数さん mailto:sage [04/06/29 00:08] 将来のコンピュータはnapzak()とかいう関数が標準装備されたりするのかな。 ちょと楽しみだ。 28 名前：１３２人目の素数さん mailto:sage [04/06/29 00:09] そして暗号化することをナップザックに詰める（napzaking）というようになるのだ。 29 名前：１３２人目の素数さん mailto:sage [04/06/29 00:12] >>26 解読問題がNP完全になるような暗号はあんまり実用的じゃないという話があるらしい． 30 名前：１３２人目の素数さん [04/06/29 00:36] >>29 「解読問題がNP完全の暗号」でひとくくりに出来るようなものなの？ もし、論文あったら教えてくらさい。 たいていは、解読するために付けた裏口の作り方が悪いんだと思ってた。 31 名前：15 [04/06/29 00:37] >>26 死んでるのは自称ナップザック暗号であって、 実際にはSubset Sum問題の部分問題に基づく暗号ってことで、 真ナップザック暗号提案してくれる人キボンヌ。 32 名前：15（以下「白シャツ」となのる） [04/06/29 00:44] ところでみなさんは数学科の人？ 漏れは本来電電板or情報システム板に居るべきなんですが。 33 名前：１３２人目の素数さん mailto:sage [04/06/29 00:49] 俺は本来シャア専用板or半角二次元板にいるべき人間 34 名前：１３２人目の素数さん mailto:sage [04/06/29 00:55] >>30 元々の論文は G. Brassard, "Relativized Cryptography", FOCS'79 なんだけども， O. Goldreich and S. Goldwasser, "On the possibility of basing Cryptography on the assumption that P neq NP" にそれに関する議論が載ってる．ちなみにこの論文はGoldreichのホームページから手に入るよ． 35 名前：白シャツ [04/06/29 01:01] >>33 そういう意味なら漏れも旧シャア板か喪板かもな。 ところでPとかNPとかってチューリングマシンで考えてって ことなんで、NPが量子チューリングマシンではPで解けるぜ ってのがショアーのアルゴリズムなんだと思うんだがどうよ。 36 名前：33 mailto:sage [04/06/29 01:02] そうか今は新旧わかれてるんだったな。 ここ数年いってないな。久しぶりに旧シャアいってみるかな。 スレ違いsage 37 名前：１３２人目の素数さん mailto:sage [04/06/29 01:34] >>35 違う．Shorのアルゴリズムが解けるのは素因数分解と離散対数問題であり， 一般のNP問題が多項式時間で解けるかどうかは知られていない，というか否定的な見解が多いと思う． 38 名前：白シャツ [04/06/29 02:31] >>37 はしょりすぎました、すまそ。 35で言いたかったのは 素因数分解はチューリングマシンを前提としたモデルの上では 準指数時間アルゴリズムしか知られていないが、量子チューリン グマシン上では多項式時間で解けるアルゴリズムがあるってのが Shorの主張かと思うということ。 それとShorのアルゴリズムは素因数分解アルゴリズムで 離散対数問題がShorのアルゴリズムに帰着できると 証明されているってことでよろしいか？ 実際に量子コンピュータが出来たとして Shorアルゴリズムは出来ませんでしたなんて オチはないだろうな、なんて期待してるんですが。 39 名前：37 mailto:sage [04/06/29 04:10] >素因数分解はチューリングマシンを前提としたモデルの上では >準指数時間アルゴリズムしか知られていないが、量子チューリン >グマシン上では多項式時間で解けるアルゴリズムがあるってのが >Shorの主張かと思うということ。 これはその通り． >それとShorのアルゴリズムは素因数分解アルゴリズムで >離散対数問題がShorのアルゴリズムに帰着できると >証明されているってことでよろしいか？ これはちょっと言い方が気持ち悪いんだが，大筋で正しい． >実際に量子コンピュータが出来たとして >Shorアルゴリズムは出来ませんでしたなんて >オチはないだろうな、なんて期待してるんですが。 これについては同じ意見を持ってる計算機科学者，物理学者が多くいるらしく， S. Aaronson, "Multilinear Formulas and Skepticism of Quantum Computing" ttp://jp.arxiv.org/abs/quant-ph/0311039 に面白いことが書いてある． 40 名前：１３２人目の素数さん mailto:sage [04/06/29 04:15] 量子コン使ってShorのアルゴリズムで15が 素因数分解できたって話が何年か前に 無かったっけ？ 41 名前：白シャツ [04/06/29 13:58] >>39 フォローさんくす >これはちょっと言い方が気持ち悪いんだが，大筋で正しい． スマソ 漏れは>>32 で言ってるように「工」の人なんで それに関しては勘弁or訂正をきぼんぬ >>40 IBMかどこかが「15が因数分解できる量子コンピュータ」を造った って話だったと思う 今はまだ物理やさん，素子やさんの玩具だと漏れは思っている 42 名前：１３２人目の素数さん [04/06/30 18:20] >>16 既にあるの？ 知らなかった。 43 名前：白シャツ [04/07/01 01:28] >>42 ネタに困った符号やさんが暗号に飛びついて いろいろと提案なさってたりします。 ところで>>9の 「隠し署名技術」ってのはいわゆる「ブラインド署名」のこと？ そうなら公開鍵暗号の応用なんだけど。 それともステガノグラフィーとか電子透かしとかそっち系ですか？ 44 名前：１３２人目の素数さん [04/07/01 02:44] >>43 誤り訂正符号と一緒に出てきてるんだから、電子透かしの方じゃない？ 冗長と秘匿が融合すると言いたいと思われる。 むしろ、ブラインド署名の使い道がわからん。 実用面で何に使えるの？ 45 名前：１３２人目の素数さん mailto:sage [04/07/01 09:51] >44電子投票、電子現金 46 名前：１３２人目の素数さん [04/07/01 13:58] ブラインド署名って、署名する人が署名する内容を知ることが出来ないってやつだよね？ いわゆる、「公証」に使えるのかな？ 電子投票や電子マネーにどうやって使うんだ？？？ もっと都合いいアルゴリズムありそうに思うんだが…。 47 名前：白シャツ [04/07/01 21:56] >>44 >誤り訂正符号と一緒に出てきてるんだから、電子透かしの方じゃない？ そうですね、たしかに。 電子透かしで暗号関係の話題だと、 「結託攻撃」に対する耐性があるかどうかってことが一番ホットかな？ 48 名前：白シャツ [04/07/01 22:06] >>45>>46 おっしゃるとおりです。 電子署名や電子マネーは複数の暗号方式や署名方式の組み合わせで 実現するんで、ブラインド署名はその要素のひとつになります。 他には多重署名だとか、検証者指定署名とか、わけわからなくなってしまう。 そういうのの組み合わせでいろいろやるんですよ。 ちなみにそうとうややこしい応用署名方式とおもわれるのが、 グループ署名、リング署名だと思う。 それでこういうのの組み合わせのフレームワークが 公開鍵基盤（PKI）てことになるんです。 詳しくは検索してみてね。 49 名前：１３２人目の素数さん [04/07/02 07:28] >>48 PKIはもう一つ下のレイヤじゃないかな。 「この公開鍵は本当に○○のものである」と社会的に保証するためのインフラだよね。 50 名前：白シャツ [04/07/02 23:09] >>49 >PKIはもう一つ下のレイヤじゃないかな。 そうかもしれない。でも漏れには正直言ってどこで レイヤ切れてるのかわからない。まだ策定中って感じかな？ >「この公開鍵は本当に○○のものである」と社会的に保証するためのインフラだよね。 そうですね。ある公開鍵で暗号化したものを復号できるのは 「対になる秘密鍵を知っている」人でしかないからね。 このあたりを社会的にでなく担保するような技術として ID-Based暗号とか、バイオメトリクスとかあるけど、 実用上はどうなのかなぁと思う。 51 名前：１３２人目の素数さん [04/07/05 12:28] age 52 名前：梅どぶろく ◆21Da3ggG3M mailto:sage [04/07/05 22:35] ■暗号技術【ROUND2】■ pc5.2ch.net/test/read.cgi/tech/1088530204/44 ↑からやってきました 私が考えた暗号なのですが検証してみてもらえませんか？ do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/readres.cgi?bo=lounge&vi=1088921677&res=2&fi=no にプログラムをアップしています。 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を生成する確率的アルゴリズム これは改良した方法で大丈夫ではないでしょうか？

---

---

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

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