RSA鍵生成

DES鍵の実装は終わっていて、現在RSAの鍵生成、暗号化、復号化の実装が完了。署名と検証はハッシュ関係がいるのでもう少し後。でもそれが一番重要だったりするのだが・・・

っで、とりあえずテストも通って(テストケースは単純なのを書いただけだが)、ちょっと長め(というか普通の長さ、実用的には短い)鍵を生成して時間を計ってみた。
生成するだけで20～30秒もかかりやがる！！！
Javaだと5秒位で終わるというのに・・・

鍵生成でボトルネックになるのは2つのでかい素数を探すところなのだが、こんなの何かいい方法があるのか？
素数判定にはミラーラビン法を使用。決定的じゃないからちと怖いがまあいいだろう。AKS法は時間がかかるとのことだったし、ミラーラビン法ならWikipediaにRubyによる実装もあったし。

やはり鍵は生成したあとどこかに保存して、使用時に読み込む方式にした方がいいな。まじめにASN.1を実装しようかな。バイナリが扱えれば何とかなるだろうし。
RSAとDSAが実装完了になるとSSLの実装ができるようになるはずなので、.derファイルとかのことを考えればあった方がいいか。
先は長い・・・