RSA鍵の生成時に確率的素数判定法を使って問題ないのか - hnwの日記

前回記事「RSA公開鍵から素数の積を取り出す方法」でも紹介しましたが、RSA鍵の生成には巨大な2つの素数p,qが必要です。近年一般的に使われている2048bit RSA鍵の場合、p,qの大きさは1024bit、10進で約308桁の数になります。 このRSAのアルゴリズム中ではpとqを法としたフェルマーの小定理（正確にはその拡張であるオイラーの定理）を利用しています。つまり、pとqが合成数だとRSA暗号の大前提が狂ってしまいますので、pとqには確実に素数を選ぶ必要があります。 ところで、OpenSSLのRSA鍵生成の実装では、pとqの素数判定にMiller-Rabin素数判定法が用いられています。Miller-Rabin素数判定法は片側誤りの確率的アルゴリズムで、「たぶん素数」「確実に合成数」の判定ができるようなものです。pとqの素数性が重要なのに、その判定に確率的アルゴリズムを使っても問題

[t_f_m]

"つまり、p,qのどちらか一方でも素数判定が間違う確率は1/2^79以下です。毎秒1000個の鍵ペアを生成できるマシン100万台で手分けして鍵生成し続けたとして、2000万年の間に壊れた鍵ペアが1つできるかどうか"

[UDONCHAN]

勉強になる