40コメント12KB

公開鍵の高速な生成

■ このスレッドは過去ログ倉庫に格納されています

0001デフォルトの名無しさん

NGNG

巨大な素数(因数分解問題にもとづく公開鍵暗号の1024-bitの公開鍵)をランダムに生成
する効率のよい方法を、どなたかご存知ないでしょうか。

当方、このようなアルゴリズムは、RSAで使用されている、

　　乱数生成 -> 前処理(小さな素数で割れるか試す) -> ラビン法を繰り返して
　　精度を高める

という方法しか知らないのですが、これより2000倍ぐらいパフォーマンスの高い方法を
探しています。ローパワー、ローコスト、ローパフォーマンスのマイクロコントローラ
に公開鍵暗号を実装したいのです。

0002デフォルトの名無しさん

NGNG

ごめん
しらないんだ
わるいね

0003デフォルトの名無しさん

NGNG

>>1
私も知りません
ごめんなさい

0004デフォルトの名無しさん

NGNG

>>4
私も存じません
ごめんあそばせ

0005デフォルトの名無しさん

NGNG

>>1
おいどんもしらんばい
すまんこってす

0006デフォルトの名無しさん

NGNG

>>1
しるかーい
そんなもん自分で考えんカーイ

0007デフォルトの名無しさん

NGNG

>>1
I don't know it.
Sorry

0008デフォルトの名無しさん

NGNG

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

ではこの辺でこのレスを終了させていただきます
すべて自作自演でした
本気で知りたいわけではないのでこれ以降レスを
付けないでください
短い間アリガトウございました

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

0009デフォルトの名無しさん

NGNG

>>1
ヤァ1、僕マイク。
マッキーって呼んでくれ。

件の件だけど僕も知らないんだ、
っていうかそんなアルゴリズムがあればそれだけで一儲けできちゃうよ
世の中そんなにスウィティーじゃないＹｏ！
じゃあね、Bye! Hahaha!

0010名無しさん＠ＬＶ2001

NGNG

知っているので、下記の口座に２０００兆円振り込んでください。

0011デフォルトの名無しさん

NGNG

>>1
マジレス。
あらかじめ公開鍵を作っておけばいい。
毎日サーバでしこしこ計算して作りだめしておくの。

0012デフォルトの名無しさん

NGNG

私もしっているので、下記の口座に１９９９兆円振り込んでください。
わたしの方がお得です。

0013折れに聞けば激安

NGNG

10と12はぼったくりだから注意！
うちならなんとたったの１９万円でいいよっ！

0014デフォルトの名無しさん

NGNG

おれ１８万９千８百円でいい。

0015終了だっていってんだろ

NGNG

0016小泉じゅんタン

NGNG

最近のIntelのチップセットには、チップセットに乱数生成機能が憑いてるから、
その機能をオンにしたlinuxカーネル使ったら、たいりょうの乱数を生成できるよ
あと、NTとかSolaris/SPARC、HP-UX/PA-RISCとかなら、乱数生成ボードを
購入すればいいよ

0017　

NGNG

>>16

1は大量の乱数を作るのが遅いんじゃなくて、

>前処理(小さな素数で割れるか試す) ->
>ラビン法を繰り返して精度を高める

が遅いから、どうにかしたいんじゃないか？

0018デフォルトの名無しさん

NGNG

あげんなやぼけ
殺すぞ

0019悲惨な1(笑)

NGNG

皆さんResありがとう(T_T)

>16
それは勉強になりました。ありがとう。でも、今回ターゲットに
するシステムはx86ではないんです。

>17
そうなんです。モジュロ演算プロセッサや乱数発生器が使えれば
いいんだけれど、そういうのが無いんです。

0020デフォルトの名無しさん

NGNG

ソロベイ・ソトラッセン　っていうのと
ユーエン・レンストラ　っていうのを
何処かで見かけたんだけど…
名前を見かけただけね

0021デフォルトの名無しさん

NGNG

重複しない鍵候補を予め作ってテーブルに格納し、擬似乱数をインデックスに
テーブル参照を行うといいよ。そのシステムに寿命に対する十分な数を格納して
おけば実用上十分さ。俺はマジでこのような実装をしようとして却下くらったけどな。

0022デフォルトの名無しさん

NGNG

>>21
>>11で既出

0023悲惨な1(T_T)

NGNG

>20
ユーエン・レンストラというのは、はじめて聞きました。Thanks!!
Solovay-StrassenはRabin-Millerとあまり変わらないです。
判定が甘い(Rabinは3/4だがSolovayは1/2)ぶんRabinより不利か?

>21
メモリ100KBぐらいしかないんですう。

たすけてぇ～

0024　

NGNG

>>23

100KBありゃぁ、1024bitの鍵なんて、
結構置いておけるじゃん。問題ある？

0025デフォルトの名無しさん

NGNG

>>24 一時メモリなんじゃないの?
おいら数学系もマイクロコントローラも知らないけど
バックグランドで計算できるならやっぱ裏でせっせと
作りつづけてある程度ため込むのがいいのではなかろうか。

0026デフォルトの名無しさん

NGNG

>>23
テーブルを圧縮したまえ。

0027デフォルトの名無しさん

NGNG

素朴な疑問なんですが、たとえば100万桁ぐらいのある整数が素数である確率ってどれくらいなんですか？

0028素人考え

NGNG

>>26
圧縮が利くようなキーの暗号強度はビット数が実質
減ってるのと同じような気がするんだけど。

0029デフォルトの名無しさん

NGNG

>27
1/ln(10^1000000) だいたい230万分の１です　b=10^1000000+aとして
aを32ビット用意すれば bには 1800個程の素数が得られるでしょう

0030デフォルトの名無しさん

NGNG

という事は 512bitの素数はlog(2^512)=平均 355個飛びにあるということだし、
素数間の距離は必ず偶数だから 8bitで前の素数との差を記録しとけば
いいんじゃないの？ 0なら512の間は素数が無いというマークにすればいいし
素数を330個も覚えておけば十分でしょ？

0031デフォルトの名無しさん

NGNG

>>27
素数の間隔を表す不等式があったような気がする。
直感的に予想されるほど開いていなかったような記憶がある。

0032デフォルトの名無しさん

NGNG

ROMをダンプしたら鍵がわかるようでは
暗号として意味ないと思われ。

0033デフォルトの名無しさん

NGNG

>32
なら、ROM上には暗号化して記録すればいいんじゃないの？

0034デフォルトの名無しさん

NGNG

じゃあこんなのはどう？
　適当に２次式を２つ作る
A(x)=+a2*x*x+a1*x+a0
B(x)=+b2*x*x+b1*x+b0

xをx0～x1の範囲で１刻みに
　A(B(x))+Cが素数になる Cを予め計算してテーブルを作っておく
Cが8bitに収まらない場合はゼロでも入れておいて使えないフラグにしておけばいい

プログラムが解析されたらダメだけど
Cのテーブルだけ見て、係数を割り出すのは至難の業だろう

0035デフォルトの名無しさん

NGNG

あ、B(x)の段階で32bitのモジュラ計算 A(X)の段階で512bitのモジュラ計算のようにするのね

0036デフォルトの名無しさん

NGNG

>>プログラムが解析されたらダメだけど
こういうのは基本的にダメだと思う。

公開鍵・秘密鍵ペアが予測可能、っていうのは、
大抵の用途で致命的でしょう？

0037デフォルトの名無しさん

NGNG

でもさあ、この場合、このマイコンで秘密鍵も公開鍵も作っちゃう訳だろ？

乱数を使う方法だって、プログラム解析されたらヤバイように思う
電池で動くようなシステムだと普段は動いていないから、スクランブル
出来る範囲は限られてるだろうし

0038デフォルトの名無しさん

NGNG

>>37
はい大きな素数です、鍵ペアできました、でもコード見られたらすぐ破られます、
って感じで、あくまで形だけ「公開鍵暗号」なんて使うのはまずいだろう、
と言ってるわけよ。電池で動くシステムだってボタン（スイッチ）一つとか
NIC一枚(とpin先一つ)あればそれなりに優良な乱数は得られるんだし。

と思ったけど、暗号強度はどうでもよくって、単にSSLしたい、とかそういう
ことで形だけでもよい、ということなら確かにROMに入れとくんでも問題ないか。

0039厨

NGNG

age

0040デフォルトの名無しさん

01/09/02 00:08ID:75FMiF1Y

ぷり

■ このスレッドは過去ログ倉庫に格納されています