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:１３２人目の素数さん
04/06/25 21:29
5
6:１３２人目の素数さん
04/06/25 22:16
形を変えた数論スレになる予感
7:１３２人目の素数さん
04/06/25 23:12
7
8:１３２人目の素数さん
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:１３２人目の素数さん
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:１３２人目の素数さん
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:１３２人目の素数さん
04/06/28 23:30
>>22
とりあえずMcElice暗号とLattice系(Ajitai-Dwork暗号やRegev暗号)はまだ今のところ破れてない．
けど，そのうち破れる可能性は無きにしも非ず．
26:１３２人目の素数さん
04/06/28 23:59
NP完全な問題を解くのは、量子計算機でも難しい（はず）。
だから、ナップザック問題を、綺麗に暗号に出来れば生き残れる（はず）。
そもそも、死んでいるというつっこみはなしの方向で。
27:１３２人目の素数さん
04/06/29 00:08
将来のコンピュータはnapzak()とかいう関数が標準装備されたりするのかな。
ちょと楽しみだ。
28:１３２人目の素数さん
04/06/29 00:09
そして暗号化することをナップザックに詰める（napzaking）というようになるのだ。
29:１３２人目の素数さん
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:１３２人目の素数さん
04/06/29 00:49
俺は本来シャア専用板or半角二次元板にいるべき人間
34:１３２人目の素数さん
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
04/06/29 01:02
そうか今は新旧わかれてるんだったな。
ここ数年いってないな。久しぶりに旧シャアいってみるかな。
スレ違いsage
37:１３２人目の素数さん
04/06/29 01:34
>>35
違う．Shorのアルゴリズムが解けるのは素因数分解と離散対数問題であり，
一般のNP問題が多項式時間で解けるかどうかは知られていない，というか否定的な見解が多いと思う．
38:白シャツ
04/06/29 02:31
>>37
はしょりすぎました、すまそ。
35で言いたかったのは
素因数分解はチューリングマシンを前提としたモデルの上では
準指数時間アルゴリズムしか知られていないが、量子チューリン
グマシン上では多項式時間で解けるアルゴリズムがあるってのが
Shorの主張かと思うということ。
それとShorのアルゴリズムは素因数分解アルゴリズムで
離散対数問題がShorのアルゴリズムに帰着できると
証明されているってことでよろしいか？
実際に量子コンピュータが出来たとして
Shorアルゴリズムは出来ませんでしたなんて
オチはないだろうな、なんて期待してるんですが。
39:37
04/06/29 04:10
>素因数分解はチューリングマシンを前提としたモデルの上では
>準指数時間アルゴリズムしか知られていないが、量子チューリン
>グマシン上では多項式時間で解けるアルゴリズムがあるってのが
>Shorの主張かと思うということ。
これはその通り．
>それとShorのアルゴリズムは素因数分解アルゴリズムで
>離散対数問題がShorのアルゴリズムに帰着できると
>証明されているってことでよろしいか？
これはちょっと言い方が気持ち悪いんだが，大筋で正しい．
>実際に量子コンピュータが出来たとして
>Shorアルゴリズムは出来ませんでしたなんて
>オチはないだろうな、なんて期待してるんですが。
これについては同じ意見を持ってる計算機科学者，物理学者が多くいるらしく，
S. Aaronson, "Multilinear Formulas and Skepticism of Quantum Computing"
URLﾘﾝｸ(jp.arxiv.org)
に面白いことが書いてある．
40:１３２人目の素数さん
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:１３２人目の素数さん
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
04/07/05 22:35
■暗号技術【ROUND2】■
ｽﾚﾘﾝｸ(tech板:44番)
↑からやってきました
私が考えた暗号なのですが検証してみてもらえませんか？
URLﾘﾝｸ(do.sakura.ne.jp)
にプログラムをアップしています。
53:梅どぶろく ◆21Da3ggG3M
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
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
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
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
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で割り切れないのは保証されてるわけで、
素数生成に使えないかと思ってんですがいかがでしょうか？
まあ、この考えが
ｽﾚﾘﾝｸ(math板:876番)
みたいな勘違いにつながったわけですが・・・
58:梅どぶろく ◆21Da3ggG3M
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
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
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
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
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
04/07/06 07:08
対称鍵暗号です。
公開鍵ではありません
勘違いした方がおられましたら失礼しました
72:白シャツ
04/07/06 13:12
>>71
いやいや，みんなわかっていると思う．
ただ，アイデア的に公開鍵に近いというように思うから．
それと，>>68で言ったことが正しい場合には，
この暗号は高次化したカエサル暗号って感じになるんでは
ないかと思うんですが．そのあたりどうなのかなと．
73:梅どぶろく ◆21Da3ggG3M
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
04/07/06 15:07
M=e^d ×
M=C^d ○
75:１３２人目の素数さん
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
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
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
04/07/06 21:42
>>77
ほんとごめんなさい
マジで勘弁してください。
私がどう考えても悪いです。
まじごめんなさい
穴があったら入りたいってのは
このときのことを言うと思います。
79:77
04/07/06 22:29
>>78
あーいやいや，実は漏れもRSA暗号を知ったばかりのときは
そういう勘違いをよくしてました．マジでしょっちゅうやってた．
「駄目」ってことがわかるとがっくりくるんだよねｗ
80:梅どぶろく ◆21Da3ggG3M
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
04/07/06 23:02
いんや違います
二浪して大学いけなくて専門学校いって
三年次編入を狙っているものです。
拡張ユークリッドの互除法やフェルマーの小定理なんかを
好奇心に任せて勉強しています。
独学だからいまいち効率が悪い・・・
今度夏休みになるんですが、
暗号関係で整数論に関するいい本を紹介していただけませんか？
83:梅どぶろく ◆21Da3ggG3M
04/07/06 23:06
現代暗号・確率的証明・擬似乱数
O. ゴールドライヒ (著),
はアマゾンで注文して今届くのを待ってる途中です
乱数についても興味があったのでこの本を選びました
84:白シャツ
04/07/06 23:20
>>82
>いんや違います
>二浪して大学いけなくて専門学校いって
>三年次編入を狙っているものです。
どこ受けるの？
まずはその対策のほうが先だと思う。
>独学だからいまいち効率が悪い・・・
漏れもほぼ独学だったし、わかります。
4回生なってから某教科書よまされたしな。
その本がろくでもなかったから（翻訳が）。
>今度夏休みになるんですが、
>暗号関係で整数論に関するいい本を紹介していただけませんか？
まともな本は無い、と言いたい。
嘘書いてある本多いし、良い本あったら漏れも欲しいぐらい。
今までに何読んだかとりあえず教えてくださいな。
それと、>>68でいった
>M mod L を２次元の平面上の点(a',b')で表しているんだと分かるわな。
は言ってる（漏れの言いたい）意味わかる？
数学の人には怒られるかもしれんけど（訂正よろしく）
85:１３２人目の素数さん
04/07/06 23:34
>>83
その本って確か計算量理論の本のはずだけど。
整数論の方面を勉強したくて買ったんだとしたら、
まったく違う分野であることを覚悟しておいた方がいい。
＞暗号関係で整数論に関するいい本を紹介していただけませんか？
Koblitz の "A Course in Number Theory" なんかどうだろう。
既読の可能性が高そうだけど。
86:１３２人目の素数さん
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
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（ただの学生）
04/07/07 06:15
>>92
あーそれそれ、元になった本はそれです。
続編の原稿を自サイトで公開して修正意見を募ったという…
（それでも売れるんだろな）
PCP…ゼロ知識系の、ブラックボックスやオラクルを使用した
計算やプロトコルのモデルがどーたらこーたら…とか？
94:梅どぶろく ◆21Da3ggG3M
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
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
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
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
04/07/07 20:39
>>100
>・ｎの推奨パラメータ
>・推奨パラメータNにおける暗号化速度（Mbps）
>・推奨パラメータNにおける使用するRAMメモリ量
これは今から実際にプログラムを組んで考えて見ます。
a,bは小さい数で個数が多いほうより
a,bはとても大きい数で個数は2つくらいのほうが
効率がいいとかまだ分かりませんので
あと、一応イメージとしてはnは1024ビット超とか考えています。
処理速度が遅くなるかもしれませんが、
一度に暗号化できるビット数も増えるわけです。
色々実験してみます。
>・ｎが与えられたときのLを生成する確率的アルゴリズム
これは改良した方法で大丈夫ではないでしょうか？
103:白シャツ
04/07/07 23:00
>>75
M→C'の写像ですが、一般のMの場合、
(a',b'c',d')→(a'+1,b'+1c'+1,d')
ですね、やっぱり。ただし
a',b',c',d'が０だったりするときは少々違うんですが。
詳細は考えてみて。
それで、a'とかがa-1とかだと途中でa'+1=0になるんで
ややこしくなるんです。
M ∈Z/LZ
↓
(a',b'c',d')∈Z/aZ×Z/bZ×Z/cZ×Z/dZ
ただし、a'∈Z/aZ,b'∈Z/bZ,c'∈Z/cZ,d'∈Z/dZ
で書いてることに注意してください。
言い方がウソと言われるかもしれんが。
今日は、次にC'→Cを考える予定。
104:63 ◆oYI7WOcH/A
04/07/07 23:02
今、気がついたんだが、63はどぶろくだなぁ…（ｗ
ホントは62だが、まぁ、これから変えるのもなんなんで。
>>101
>Diffie-Hellman鍵交換プロトコルで二つの鍵A,Bを交換します。
>そしてgcd(A,B)=Gを求めます。
>A/G,B*Gをそれぞれa,bとしてL=a*bとなります。
これなんだが、あんまりよくないんじゃないかな。
まず、狙った範囲のLを出すのが難しいんじゃない？
DH鍵交換してみたはいいが、AとBがとても大きな因数を持ってたりどっちかが極端に小さかったりしたら、DHをやり直すの？
もしかして、鍵交換終えるまで、Nがいくつにならないか分かりません、とかいう新手の仕様か？
少なくとも、これでは実装出来ないと思うよ。
特に凄まじく弱い鍵が排除しないという仕様なら、そういう風に判断するが。
例えば、1024bitで4つに分けたとしたら、DHで交換するのは、256bit程度でしょ？
これは、離散対数問題が困難とは言い切れない程度になるな。
もっと大きな値で交換して、ハッシュかなんかで変換して、っていうのなら、ちゃんとそう書かなきゃ。
もう脳内は勘弁してね。
なので、
>>・ｎが与えられたときのLを生成する確率的アルゴリズム
>これは改良した方法で大丈夫ではないでしょうか？
は、全然大丈夫ではないと思います。
105:白シャツ
04/07/07 23:07
>>101
>Diffie-Hellman鍵交換プロトコルで二つの鍵A,Bを交換します。
これ意味がわからない。どういうこと？
ていうか何がしたい？
>>103
>ただし、a'∈Z/aZ,b'∈Z/bZ,c'∈Z/cZ,d'∈Z/dZ
これは方式で定義してありましたね。
106:77
04/07/07 23:48
>>98
いや、あの本にはPCPの暗号学的応用は何も載ってないです。
>>93はおいらの妄想。
107:梅どぶろく ◆21Da3ggG3M
04/07/08 00:18
>>104
>まず、狙った範囲のLを出すのが難しいんじゃない？
>DH鍵交換してみたはいいが、AとBがとても大きな因数を持ってたり
>どっちかが極端に小さかったりしたら、DHをやり直すの？
今実験中です。
どっちかが極端に小さければa'+1=0になる回数が多くなるわけです。
そうすれば解読するのに邪魔になると思うんですが、
なんだったらデフォルトで2,3は基数に含めるなどとしてもいいわけで
>Diffie-Hellman鍵交換プロトコルで二つの鍵A,Bを交換します。
>これ意味がわからない。どういうこと？
>ていうか何がしたい？
D-H鍵交換プロトコルを二回繰り返すってことです。
省略した説明でごめんなさい。
>もっと大きな値で交換して、ハッシュかなんかで変換して、っていうのなら、ちゃんとそう書かなきゃ。
そこまで考えていませんでした。
>もう脳内は勘弁してね。
大丈夫です。もう脳内の考えは出しつくしました
新しい考えが出てくる可能性はありますけど
108:白シャツ
04/07/08 00:32
>>106 とりあえず本屋でもう一回立ち読みします。
>>107
>D-H鍵交換プロトコルを二回繰り返すってことです。
L=abcdでa,b,c,dは素数の冪だったんでしょ。
A,Bを交換ってだからA,Bは何？
とりあれず出来たLの条件は最初のでOKなの？
109:63 ◆oYI7WOcH/A
04/07/08 01:49
ちなみに、DHは鍵交換ではなく、鍵共有だな。
だから、>>105,108のような疑問がわいてくる。
まぁ、とりあえず、仕様が固まったら教えてね。
上の推奨パラメータとそのパフォーマンスも。
既存の100倍ぐらいパフォーマンスと安全性が悪くても、考えてみるよ。
でも残念ながら一般的な解読法を適用した場合に、10^2倍ぐらい簡単に解けるし、
必要なメモリ量（ハードウェア実装したときは、基盤の規模に直結する）は、10^3倍ぐらいかかるし、
同じデータを暗号化するのに10^4倍ぐらい時間がかかると思う。
このめちゃくちゃな予想を、「よく」裏切るような実験データを期待してるよ。
110:白シャツ
04/07/08 02:12
>>109
いや、DHで鍵共有するとして、
>そしてgcd(A,B)=Gを求めます。
>A/G,B*Gをそれぞれa,bとしてL=a*bとなります。
となってます。a,bが異なる素数の冪なるようにするなら
p,qを素数として
A=p^x*q^y, B=q^z かつ y<=Z じゃないとダメですよね。
そうなるとp,qが最初から双方でわからないとダメでしょ。
意味わからん。
私も人のこと言えませんが、>>63 -1さんも奇特な人ですね。
あと>>77さんも。このスレ現状4人で回ってるような。
111:63 ◆oYI7WOcH/A
04/07/08 03:11
>>110
例のアレだ。仕様変更。固まるまで待ってやれ。
奇特っていうか、暇なんだよね。トルネコ３のあいまに見てる。
何を血迷ったか、暗号解読コンテスト！とか銘打って、Certicomみたいに賞金かけたり何かしないかなぁ～なんて。
もう少し人間的な生活をせねば。
>>どぶろく
ちなみにやろうとしているのは、どぶろく暗号（勝手に命名）がいかに「ダメ」かってのを、
・誰もがなっとく出来る理由付きで
・自分が苦労せず（計算したり査読したりせず）
・最終的にはどぶろく自身の手で
示そうってこと。
何の理由も示さず「そんなんダメだ」っていう嫌な大人は嫌いでしょ？
悪気は…ある。楽しんでるからね。だから、指示に従う必要は全くないよ。
でも、どれも妥当（そうに見えるでしょ？）な指示・情報開示要求だから
「誰にも見向きもされないから絶対に安全な暗号」になりかねんが。
なはは、それはそれですごいかもしれん。
112:白シャツ
04/07/08 03:38
>>111
仕様変更待ってたら暇つぶしができないじゃないですか(w
暇ってわりにはやけにお詳しいようですね。
ところで、
>>55 のC'→Cのアルゴリズムどおりにやると
Cは0<=C<Lでおさまるのか気になるんですが、どうなってるの？
>>96
>Cの値が一定にならない確率暗号みたいな仕様を目指しているのかなと思ってた。
>でも、際限なく増えていくので、これはあんまり良くないな。
ってことなんで気になって。
これ解析する気はないし。どぶろく氏に宿題。
普通に考えたらCRTで終わりなんだけど。
113:１３２人目の素数さん
04/07/08 03:51
関連スレ
素数判定は「決定的」多項式時間で可能
ｽﾚﾘﾝｸ(math板)l50
114:63 ◆oYI7WOcH/A
04/07/08 04:37
>>112
>Cは0<=C<Lでおさまるのか気になるんですが、どうなってるの？
それは、mod Lで考えればいいんじゃない？
一意性は保証されてるんだから影響を与えないでしょ。
ここは、数学家さんが考えることであって、暗号屋さんが考えることではない。
有名どころの対称鍵暗号アルゴリズムで確率暗号って聞いたことがない。
まぁ、実用上、データサイズが増えるのはよろしくないし、圧縮も効かないから扱いにくいんだろうなぁ。
公開鍵暗号系みたいに、扱うデータサイズが極小ならいいけど。
モードをECB以外にすれば、確率暗号が期待する効果を発揮出来るし。
サイズを大きくすることを上回るメリットが見えない。
折角、Mの取る範囲を制限してるんだから、完全性を判別出来るプロトコルもあれば面白いな。
今、暗号鍵とサブ鍵みたいなのがあって、
暗号鍵を知っていれば、勿論解読出来る。
サブ鍵を知っていれば、その暗号文が、（でたらめな値ではなく）正当な暗号文であるかどうかを判別出来る。
っていう系を作ることが出来れば面白いかなっと思ったが、一瞬で出来てしまった。
暇つぶしにはならんなぁ。
そもそもCRTがなぜChineseなのかが気になってしょうがない。
「昔の中国では、軍隊で人を綺麗に並べるときに使ったらしいよ」
と聞いて、そのときは、すごーいと思ったが、よく考えたら、CRTの言いたいことが、
なぜ、綺麗に並べるときに使えるのかがわからん・・・。
115:梅どぶろく ◆rM4QWlepe6
04/07/08 09:46
すいません、全くの別口ですが、
GCD(a, n) = G(G≠1)
のとき
ax-ny=1を満たす
x,yを求めるのは難しいですか？
116:梅どぶろく ◆21Da3ggG3M
04/07/08 09:46
↑は私です。
トリップ間違えました。
すいません。
117:１３２人目の素数さん
04/07/08 10:03
>>115
うん。ものすごーーーく難しい。万が一見つかったら
是非報告してくれ。
118:梅どぶろく ◆21Da3ggG3M
04/07/08 12:43
>>117
・・・
存在しないじゃないですか！！
ものすごーーーーく難しいっていったら
難しいけど、求めることはできると思って
考えていったら
GCD(a,n)=G(G≠1)のとき
G(Ax-Ny)=1とあらわせて
Gは整数であるから
x,yは存在しない・・・
やられました。
119:63 ◆oYI7WOcH/A
04/07/08 14:07
>>115
とっても簡単。xに好きな値を入れて、y = (ax - 1)/nを入れればよい。
もとまったx,yがどぶろくが欲しい範囲に入ってるかどうかはしったこっちゃないが。
120:白シャツ
04/07/08 22:13
114>>
>>Cは0<=C<Lでおさまるのか気になるんですが、どうなってるの？
>それは、mod Lで考えればいいんじゃない？
脳内仕様の確認したかっただけです。
仕様はどうなった？＞どぶろく氏
L=abcdなの？ 途中からL=abになってるけど。
検証の手間がかかるし後者の方が楽だけど。
零元の処理とか。
>一意性は保証されてるんだから影響を与えないでしょ。
>ここは、数学家さんが考えることであって、暗号屋さんが考えることではない。
数学家さんは最初から気にしないと思う。剰余類にはいってれば一緒だし。
ていうか、数学家さんって居なくなった？
>有名どころの対称鍵暗号アルゴリズムで確率暗号って聞いたことがない。
鍵共有で乱数つっこんで使い捨てにしたら
良いってことじゃないかな？
>そもそもCRTがなぜChineseなのかが気になってしょうがない。
孫子算経に載ってたらしい。孫子が考えたかどうかは謎だけど。
121:梅どぶろく ◆21Da3ggG3M
04/07/08 23:09
>>120>>114
すいませんです。
一人で実験してみたのですが、
大きな数a,bのとき
やたら下位ビットが規則的に並んでいます。
これはあきらかな弱点です。
お恥ずかしい話ではありますが、
最初どおりa,b,c,dとして
基数は複数用いるということでお願いします。
>>112
問題なしです
0<=C<Lに収まります。
C=ax+a'=by+b'=cz+c'=dw+d'
CはCをa,b,c,dで割った時の余りとして表現されています。
a,b,c,dの余りで表現できるのはabcd-1までです。
んんっとここが、最大の弱点であるわけです。
攻撃者は選択平文攻撃ででてきた
Cの最大値より大きい値が鍵Lと予想できます。
122:梅どぶろく ◆21Da3ggG3M
04/07/08 23:24
>>115の発言についてですが、
公開鍵について考えていました。
C=E*M(mod n)
M=D*C(mod n)
M=E*D*M(mod n)={E*D(mod n)}+M(mod n)
=M(mod n)
とするにはE*D(mod n)≡1にすればいい。
Eが求まるときにDを求めるのは簡単、
しかし、E,nの分かる解読者にとっても簡単
(E*D)^x≡(E^x)*(D^x)≡1 (mod n)として、
e=E^x,d=D^x(mod n)がgcd(e,n)≠1となるようにすれば
解読者はeの値からdの値を求めるのが難しい！
やった、新しい公開鍵暗号ができたんじゃないかしら
とおもって、>>115>>118のような発言にいたりました。
まあ結局は>>118にあるように無理だったんですが・・・
123:梅どぶろく ◆21Da3ggG3M
04/07/08 23:26
私ごときが言うのもなんですが、
あらためてRSAのすごさを認識しました。
124:白シャツ
04/07/08 23:46
>>121
>大きな数a,bのとき
>やたら下位ビットが規則的に並んでいます。
>これはあきらかな弱点です。
Why?
>問題なしです
>0<=C<Lに収まります。
>C=ax+a'=by+b'=cz+c'=dw+d'
>CはCをa,b,c,dで割った時の余りとして表現されています。
>a,b,c,dの余りで表現できるのはabcd-1までです。
0<=C<Lで一意に表現可能であるのは最初からわかっている。
C=ax+a'=by+b'=cz+c'=dw+d'を満たすCは無数に存在するけど。
>>55のアルゴリズムで0<=C<LなるCが求まるかが問題。
普通はCRTで計算するのはわかった？
>んんっとここが、最大の弱点であるわけです。
>攻撃者は選択平文攻撃ででてきた
>Cの最大値より大きい値が鍵Lと予想できます。
どういうこと？
>>122
RSAの指数部みてみなよ。
125:梅どぶろく ◆21Da3ggG3M
04/07/09 00:21
>>124
>>>55のアルゴリズムで0<=C<LなるCが求まるかが問題。
求まらなかったらmod Lすればいいので問題なし
>>>122
>RSAの指数部みてみなよ。
いや、何百桁もある数を何百桁乗もしているのは分かっています。
仮に、おまえもどんなのでもいいから公開鍵暗号を作ってみろ
といわれても、わたしにはできません。
それに、RSAは他の公開鍵についての情報がまったくなく
0から作り上げた暗号としてとてもすごいと思っています。
私が考える場合は既存の公開鍵暗号を参考にすることもできるわけです。
それでも、橋にも棒にもかからない不可能を証明できるような暗号しかできないのです。
>>んんっとここが、最大の弱点であるわけです。
>>攻撃者は選択平文攻撃ででてきた
>>Cの最大値より大きい値が鍵Lと予想できます。
>どういうこと？
0<=C<Lですから、適当にMを代入して出てきた
Cより小さい値は絶対Lにならないってことです。
ランダムにMを代入してみてCを集めていくと・・・
Lの候補がすこし絞れてしまう・・・
なんてことになると思ってますがどうでしょうか？
126:白シャツ
04/07/09 00:48
>>125
>求まらなかったらmod Lすればいいので問題なし
えと、それは良いのだけど、CRTは調べた？
>いや、何百桁もある数を何百桁乗もしているのは分かっています。
>仮に、おまえもどんなのでもいいから公開鍵暗号を作ってみろ
>といわれても、わたしにはできません。
そういうことではなく、RSAの指数部は>>122のアイデアと一緒。
RSAとてそういう単純なことなんで
コロンブスの卵は偉大だが、がんがれってこと。
>それに、RSAは他の公開鍵についての情報がまったくなく
>0から作り上げた暗号としてとてもすごいと思っています。
DHってかわいそうだと思いませんか？
本来もっと評価されても良いはず。
>ランダムにMを代入してみてCを集めていくと・・・
>Lの候補がすこし絞れてしまう・・・
>なんてことになると思ってますがどうでしょうか？
その攻撃に意味があるのかどうかわからないんですが。
127:梅どぶろく ◆21Da3ggG3M
04/07/09 01:05
>>>121
>>大きな数a,bのとき
>>やたら下位ビットが規則的に並んでいます。
>>これはあきらかな弱点です。
>Why?
URLﾘﾝｸ(do.sakura.ne.jp)
に実験結果をupしてます
見てみてください。
以下一例
3e-3d
=1631f819d3e2bfe8-1631f819898f0764
=4A53B884
3d-3c
=1631f819898f0764-1631f8193f3b4ee0
=4A53B884
54e-54d
=92dbb8db5c15831-92dbb8d6b6d9fad
=4A53B884
ってなるんですがだめですよね？
128:白シャツ
04/07/09 01:21
>>127
聞き方がまずかった。
何がやりたくて何をやったかサッパリわからない。
結果だけ出されてもわからないでしょ。
それと、M→C'は平文に制限のあるカエサル暗号みたいだから、
この部分を真カエサル暗号にしてC'→Cでカエサル暗号を強化
しました、みたいなのを提案するとずっと受けは良いと思うんだがどうよ？
まぁ次回作のプランってことでよいか。
129:梅どぶろく ◆21Da3ggG3M
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:１３２人目の素数さん
04/07/09 23:50
もうお嫁に行けない！
136:梅どぶろく ◆21Da3ggG3M
04/07/10 15:46
>何がやりたくて何をやったかサッパリわからない。
>結果だけ出されてもわからないでしょ。
やりたかったのは
巨大な互いに素である数の積をLとした時に
平文と暗号文の間になんらかの関係があるか調べたかったのです。
そして実験をしてみて
暗号文には偏りが生じていると思いました。
>why?
暗号では雪崩効果が必要と読みました。
差が一定なのも問題だと思っています。
どこかで差が変わると思うのですが
そこを攻撃されるとLの要素であるa,bが推測されやすくなると思います。
137:１３２人目の素数さん
04/07/10 18:18
やっぱりある程度の数学的素養がないと辛いんでないかな。
遠回りのようだけど代数系の基礎から一通りやったほうがいいかも
138:１３２人目の素数さん
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:１３２人目の素数さん
04/07/10 19:17
もう一個質問
>cZ+c"=dW+d"…壱
>となる最小の値を(cd)"とします。
最小となる「何の」値を(cd)''とするのですか？
他の最小とかいてある部分も。
読み解く必要が無いような記述でお願いします。
140:138=139
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
04/07/10 20:12
連続ですまんが>140は違うみたいね
142:梅どぶろく ◆21Da3ggG3M
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
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:１３２人目の素数さん
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
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:１３２人目の素数さん
04/07/10 23:53
>>145
前半了解
じゃあ後半も
S=cZ+c"=dW+d" となる最小の正の数 S を (cd)'' とするで良いのかな？
147:梅どぶろく ◆21Da3ggG3M
04/07/10 23:53
>例えば「等式※ 2*s+3=3*u+5となる最小の(1以上の)整数をRとします」といった場合、
>この等式を満たすs,tの組は(4, 2), (7, 4), (10, 6), ・・・とありますが、
この等式を満たす最小の正の数です。
等式※なら私が言っている最小の正の数は11となります。
148:梅どぶろく ◆21Da3ggG3M
04/07/10 23:54
>>146さん
そうです、その通りです。
149:138=144=146
04/07/10 23:56
ども、読んでみます
150:138
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
04/07/11 00:09
Vは>145の記法ね
>55の記法ではZ_W
152:１３２人目の素数さん
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
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
04/07/11 00:50
別に4つでなくてもかまいません。
ただの例示として示しただけですから。
深読みのしすぎでつ
156:138
04/07/11 01:22
う～ん、次ステップで分からなくなりました。
① bY+b"=(c*d)V+(cd)" となる最小の正の数 bY+b'' を (bcd)" とすると
から始めて
④ bY+b"=(c*d)V+(cd)"=(b*c*d)U+(bcd)" (Uは0以上の整数)
となる表示を求めるんでしょうけど出来ません。
55の場合Z, Wともこれから求める値であったのに対して、
今回はVは既に定まったあたいであり、欲しい値はUだけですよね？
この①～④部分を>55形式で書いていただけませんか？
157:梅どぶろく ◆21Da3ggG3M
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:１３２人目の素数さん
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:１３２人目の素数さん
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:名無しさん＠そうだ選挙に行こう
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:名無しさん＠そうだ選挙に行こう
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:名無しさん＠そうだ選挙に行こう
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
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
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
04/07/14 15:38
公開鍵暗号ですか～
憧れの暗号化方式です。
また色々と考えてきます。
179:白シャツ
04/07/14 21:43
>>178
編入試験対策の方は順調？
180:梅どぶろく ◆21Da3ggG3M
04/07/14 22:47
いえ、まったくしてません
私の専門学校からだと基本情報技術者の資格を取れば
専門学校から大学に推薦してもらえるそうなので
推薦してもらって入ろうかと思ってます。
181:白シャツ
04/07/15 00:00
>>180
暗号とかやってる研究室のある大学に推薦してもらえるの？
3年次編入ありでそんな大学ってあるのかなぁ。
182:１３２人目の素数さん
04/07/15 08:56
>暗号とかやってる研究室のある大学に推薦してもらえるの？
希望としては横浜国立なんですが
やっぱ勉強して一般入試で入らないとだめですか・・・
一応推薦では岐阜と思ってるんですが
大学院にすすんでそれから暗号の研究室ってのは
無理ですかねぇ・・・
183:77
04/07/15 10:22
>>182
＞大学院にすすんでそれから暗号の研究室
いや、それでも全然ＯＫだと思うよ。
ただ、ム板の暗号スレにもあったけど、暗号アルゴリズムの研究以外にも
情報セキュリティには色々な研究分野があるし、情報系の他の分野にも
数理的な分野はたくさんあるんで、学部のうちは代数系や計算機科学、ネットワーク等の
基礎知識を広く浅く勉強しつつ、いろんな分野に興味を持って覗いてみるのもいいと思う。
（院に進学する頃には違う分野のことが面白くなってるかも）
184:１３２人目の素数さん
04/07/15 16:09
もし数学系に編入するならもうちょっと数学独自の言い回しに気を配ったほうがいいのでは？
>53 ～見る限り、必要なことを後出しにして書いているので、そういうのが訓練されていないと思う
数学の内容どうこうは別として、書き方・伝え方は殴り書きだとしてもこれではというレベル
まず>137さんの言うように基礎をやりながらそういうのも覚えたほうがいいと思う
誤解を与えずに伝えるため、また自分の考えを伝えるための書き方や読み方も一種の訓練で、
凡才な人（ほとんどの人）は、1年目に基礎の授業の問題回答やレポートなど体で覚えるから
天才のことは知らない
編入して来て大学院とかも知り合いにもいるから、自分次第なんでしょうけど
専門学校からの編入は知らないし、いま学校でどんな勉強してるかもわからないので
185:白シャツ
04/07/15 21:47
>>182
>希望としては横浜国立なんですが
松本先生のところ？
>一応推薦では岐阜と思ってるんですが
>大学院にすすんでそれから暗号の研究室ってのは
>無理ですかねぇ・・・
これは別の大学の院に行くこと前提ってことですか？
186:梅どぶろく ◆21Da3ggG3M
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:１３２人目の素数さん
04/07/16 01:12
素数を求める回路を教えてください
190:１３２人目の素数さん
04/07/16 02:55
暗号もいいが認証もいい
191:１３２人目の素数さん
04/07/16 10:53
>>189
求める素数の質による。
暗号で使うような素数ならMiller-Rabin法がNIST公認のアルゴリズムだけど、
これをそもそも回路で設計するべきものなのかどうかはしらない。
192:白シャツ
04/07/16 11:01
>>189
素数を求めるってのがどんな問題かわからない．
素因数分解かもしれんし，素数判定かもしれない．
>>191 と同意で回路でやるものじゃないとおもう．
193:１３２人目の素数さん
04/07/16 20:45
符号理論ってもう華がないですか？
194:１３２人目の素数さん
04/07/16 23:47
そもそも華あったの？
195:白シャツ
04/07/17 00:19
>>194
CDとか聞けるのは誰のおかげか考えてみな。
ていうか、データ通信できるのは誰のおかげなんだ。
196:１３２人目の素数さん
04/07/17 05:47
マクスウェルのおかげです
197:１３２人目の素数さん
04/07/17 08:52
47氏のおかげだったり？
198:白シャツ
04/07/17 15:23
漏れの指導教官は符号→セキュリティと鞍替えしてきた。
符号教えてくれと頼んだんだけど教えてくれなかったので
ピーターソンの教科書借りて勝手に勉強中。
全然わからないんすけど。
199:１３２人目の素数さん
04/07/17 17:05
>>195
役に立つけど華はないな、それだと。
200:白シャツ
04/07/17 17:17
>>197
あの人って専門符号だったんでつか？
>>195
そうか、じゃぁ、超高雑音通信路で誤り訂正符号を用いて
無人宇宙探査機を遠隔制御とかだと華あるか？
201:KingOfMathKingdom ◆NlBVr1vWAA
04/07/17 17:19
チューリングとナッシュだったらどっちが暗号解読力があっただろうか？
202:１３２人目の素数さん
04/07/18 05:58
>>200
自分のレスにレス付けてるよ
203:梅どぶろく ◆21Da3ggG3M
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
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
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
04/07/18 16:47
>>187
>>別の大学の院にいくって前提では受け悪いですか？
>誰に対する受け？
大学の教授です。
207:梅どぶろく ◆21Da3ggG3M
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
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
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
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
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:１３２人目の素数さん
04/07/18 21:17
どぶさんへ
nは素数じゃなくてもいいの？
218:63 ◆oYI7WOcH/A
04/07/18 21:18
ん？そうだとすると、やはり、取れない平文がたくさん出てくるよ。
例えば、e1<e2なら、M1より大きなM2は絶対に取れない。
凄くゆるゆるの評価をしていてもこんな感じだけど。
219:梅どぶろく ◆21Da3ggG3M
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
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
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:１３２人目の素数さん
04/07/18 22:57
相手をすることが必ずしも親切なことにはならないという好例
225:１３２人目の素数さん
04/07/18 23:46
まさしく >184 だな
226:梅どぶろく ◆21Da3ggG3M
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
04/07/19 07:05
|(M1*e1)-(M2*e2)|>nは消してはいけません
絶対値(M1*e1)-(M2*e2)絶対値>nは消してはいけません
が正確です。
228:１３２人目の素数さん
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:１３２人目の素数さん
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
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
04/07/19 18:52
暗号化の演算回数は6回で間違いありません。
復号についてですが、6回の演算でした。
暗号化・復号ともに演算は6回ですみます。
e1,e2の値からa,x,E^Yいずれかの値を求めるのは困難である。
といってもいいと思いますが、みなさんはどうでしょうか？
2chは公共の場として認められているのでしょうか？
特許は放棄しようと思ってるんですが、
今から誰かが特許を申請しても無効になりますよね？