security - El Gamal は、同じモジュラス長の RSA よりも高速ですか?

Question

El Gamal が同じモジュラス長の RSA よりも速いのはなぜですか?

Answer 1

このPGPリンクを参照してこれについて言及していると思います。もしそうなら、その理由は、El Gamalが暗号化または復号化のために直接高速であるということではありませんが、全体としては高速です。FAQに記載されているように、解読は暗号化よりも頻繁に行われるため、ElGamalの操作の総コストは低くなります。そのため、ElGamalはより高速であると見なすことができます。

より強力であるという点では、離散対数の計算は少なくとも整数因数分解と同じくらい難しいため、ElGamalはRSAよりも少し強力であると考えられます。これを取り巻く文献については、これを確認してください。

私よりも暗号の知識が豊富な他の人は、私が間違っている場合は私を修正することができます。

Answer 2

指数が短いため、ElGamalの方が高速です。RSAでは、暗号化に非常に短い指数eを選択できますが、指数dの復号化はおそらく1024ビット長になります（1024ビットのモジュラスの場合）。El Gamalの場合、指数は両方とも独立して選択できます。PGPは、長さ160ビットの指数を提案します。これにより、べき乗の横で逆数が計算されている場合でも、ElGamalの復号化が高速になります。