パスワードを忘れた? アカウント作成
15036574 journal
プログラミング

iidaの日記: ROCA脆弱鍵検出アルゴリズム

日記 by iida

ありきたりのROCA脆弱鍵検出アルゴリズムでは、小さい素数から割っていって65537の冪乗の剰余と比べるのだが、ハズレになる確率の高い素数から割っていけば、より速くハズレを見付けられることに気付き順序を変えてみたら、2倍ほど速くなった。
139、149、163、167では割り切れるばあいだけハズレなのだが、それらはやめて227、229、233、239で割れば誤報が数百分の1〜数千分の1になることも判明。
239のばあい0x108000008000048000000110000002000000888000801100040042で比べればよいので、93%くらいハネることができる。
PS
21-01-02
ハズレとアタリの間違いを1か所訂正

typodupeerror

目玉の数さえ十分あれば、どんなバグも深刻ではない -- Eric Raymond

読み込み中...