5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

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

公開鍵の高速な生成

1 :デフォルトの名無しさん:2001/06/08(金) 18:36
巨大な素数(因数分解問題にもとづく公開鍵暗号の1024-bitの公開鍵)をランダムに生成
する効率のよい方法を、どなたかご存知ないでしょうか。

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

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

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

2 :デフォルトの名無しさん:2001/06/08(金) 18:37
ごめん
しらないんだ
わるいね

3 :デフォルトの名無しさん:2001/06/08(金) 18:38
>>1
私も知りません
ごめんなさい

4 :デフォルトの名無しさん:2001/06/08(金) 18:38
>>4
私も存じません
ごめんあそばせ

5 :デフォルトの名無しさん:2001/06/08(金) 18:39
>>1
おいどんもしらんばい
すまんこってす

6 :デフォルトの名無しさん:2001/06/08(金) 18:39
>>1
しるかーい
そんなもん自分で考えんカーイ

7 :デフォルトの名無しさん:2001/06/08(金) 18:42
>>1
I don't know it.
Sorry

8 :デフォルトの名無しさん:2001/06/08(金) 18:43
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

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

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

9 :デフォルトの名無しさん :2001/06/08(金) 18:46
>>1
ヤァ1、僕マイク。
マッキーって呼んでくれ。

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

10 :名無しさん@LV2001:2001/06/08(金) 19:38
知っているので、下記の口座に2000兆円振り込んでください。

11 :デフォルトの名無しさん:2001/06/08(金) 20:02
>>1
マジレス。
あらかじめ公開鍵を作っておけばいい。
毎日サーバでしこしこ計算して作りだめしておくの。

12 :デフォルトの名無しさん:2001/06/08(金) 20:22
私もしっているので、下記の口座に1999兆円振り込んでください。
わたしの方がお得です。

13 :折れに聞けば激安:2001/06/08(金) 20:30
10と12はぼったくりだから注意!
うちならなんとたったの19万円でいいよっ!

14 :デフォルトの名無しさん:2001/06/08(金) 21:01
おれ18万9千8百円でいい。

15 :終了だっていってんだろ:2001/06/08(金) 21:03
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

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

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

16 :小泉じゅんタン:2001/06/09(土) 12:44
最近のIntelのチップセットには、チップセットに乱数生成機能が憑いてるから、
その機能をオンにしたlinuxカーネル使ったら、たいりょうの乱数を生成できるよ
あと、NTとかSolaris/SPARC、HP-UX/PA-RISCとかなら、乱数生成ボードを
購入すればいいよ

17 : :2001/06/09(土) 14:34
>>16

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

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

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

18 :デフォルトの名無しさん:2001/06/09(土) 15:20
あげんなやぼけ
殺すぞ

19 :悲惨な1(笑):2001/06/09(土) 18:01
皆さんResありがとう(T_T)

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

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

20 :デフォルトの名無しさん:2001/06/11(月) 00:58
ソロベイ・ソトラッセン っていうのと
ユーエン・レンストラ っていうのを
何処かで見かけたんだけど…
名前を見かけただけね

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

22 :デフォルトの名無しさん:2001/06/11(月) 04:03
>>21
>>11で既出

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

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

たすけてぇ〜

24 : :2001/06/11(月) 18:10
>>23

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

25 :デフォルトの名無しさん:2001/06/11(月) 18:22
>>24 一時メモリなんじゃないの?
おいら数学系もマイクロコントローラも知らないけど
バックグランドで計算できるならやっぱ裏でせっせと
作りつづけてある程度ため込むのがいいのではなかろうか。

26 :デフォルトの名無しさん:2001/06/11(月) 21:52
>>23
テーブルを圧縮したまえ。

27 :デフォルトの名無しさん:2001/06/28(木) 21:06
素朴な疑問なんですが、たとえば100万桁ぐらいのある整数が素数である確率ってどれくらいなんですか?

28 :素人考え:2001/06/28(木) 21:31
>>26
圧縮が利くようなキーの暗号強度はビット数が実質
減ってるのと同じような気がするんだけど。

29 :デフォルトの名無しさん:2001/06/28(木) 22:02
>27
1/ln(10^1000000) だいたい230万分の1です b=10^1000000+aとして
aを32ビット用意すれば bには 1800個程の素数が得られるでしょう

30 :デフォルトの名無しさん:2001/06/28(木) 22:31
という事は 512bitの素数はlog(2^512)=平均 355個飛びにあるということだし、
素数間の距離は必ず偶数だから 8bitで前の素数との差を記録しとけば
いいんじゃないの? 0なら512の間は素数が無いというマークにすればいいし
素数を330個も覚えておけば十分でしょ?

31 :デフォルトの名無しさん:2001/06/29(金) 01:19
>>27
素数の間隔を表す不等式があったような気がする。
直感的に予想されるほど開いていなかったような記憶がある。

32 :デフォルトの名無しさん:2001/06/29(金) 02:02
ROMをダンプしたら鍵がわかるようでは
暗号として意味ないと思われ。

33 :デフォルトの名無しさん:2001/06/29(金) 07:04
>32
なら、ROM上には暗号化して記録すればいいんじゃないの?

34 :デフォルトの名無しさん:2001/06/29(金) 09:29
じゃあこんなのはどう?
 適当に2次式を2つ作る
A(x)=+a2*x*x+a1*x+a0
B(x)=+b2*x*x+b1*x+b0

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

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

35 :デフォルトの名無しさん:2001/06/29(金) 09:41
あ、B(x)の段階で32bitのモジュラ計算 A(X)の段階で512bitのモジュラ計算のようにするのね

36 :デフォルトの名無しさん:2001/06/29(金) 10:56
>>プログラムが解析されたらダメだけど
こういうのは基本的にダメだと思う。

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

37 :デフォルトの名無しさん:2001/06/29(金) 11:16
でもさあ、この場合、このマイコンで秘密鍵も公開鍵も作っちゃう訳だろ?

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

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

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

39 ::2001/07/20(金) 08:20
age

40 :デフォルトの名無しさん:01/09/02 00:08 ID:75FMiF1Y
ぷり

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

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)