公開鍵の高速な生成

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

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

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

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

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

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

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

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

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

>>1
I don't know it.
Sorry

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>16

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

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

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

あげんなやぼけ
殺すぞ

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

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

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

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

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

>>21
>>11で既出

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

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

たすけてぇ〜

>>23

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

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

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

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

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

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

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

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

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

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

じゃあこんなのはどう？
　適当に２次式を２つ作る
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のテーブルだけ見て、係数を割り出すのは至難の業だろう

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

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

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

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

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

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

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

age

ぷり