3
$\begingroup$

As I understand it the proof that RSA-OAEP is secure in the random oracle model is much tighter for exponent 3. Does that mean that exponent 3 should be chosen?

$\endgroup$
5
$\begingroup$

For any reasonable RSA-based encryption (or signature) scheme, exponent $e = 3$ is a perfectly good choice and provides the best performance for the public-key operation short of qualitatively different Rabin-type schemes.

  • Don't use RSAES-PKCS1-v1_5.
  • RSAES-OAEP of PKCS#1 v2 is reasonable in this sense, though it is unnecessarily complicated.
  • RSA-KEM is even more reasonable and much simpler.

But there are people out there who have PTSD from decades of bad crypto engineering with horrible flaws that are sort of halfway patched over by using larger exponents like $e = 65537$. So some auditors might summarily reject $e = 3$ when they see the letters R, S, and A, without looking at the elephant in the room of what specific encryption or signature scheme you're using that involves RSA.

$\endgroup$
  • 1
    $\begingroup$ French rules forbid RSA with $e \le 2^{16}$ (RègleFact-4). The rationale only states “because of existing attacks”. I think this section has other flaws, including a probably erroneous requirement on $d$, and not mentioning padding at all (!). But if you're a French auditor, you have to reject $e=3$. $\endgroup$ – Gilles 'SO- stop being evil' Feb 21 at 21:52
  • $\begingroup$ Curiously, this rule only applies to RSA encryption, not to RSA signature—it is only a recommendation (RecomFact-2) for applications other than encryption. $\endgroup$ – Squeamish Ossifrage Feb 22 at 0:12
  • $\begingroup$ The document gives a rationale for tighter rules for encryption: if a new (variant of an) attack comes up, you can re-sign with a stronger method, whereas if encryption is broken, you can't unleak secrets. $\endgroup$ – Gilles 'SO- stop being evil' Feb 22 at 9:28
  • $\begingroup$ Why shouldn't PKCS#1v1.5 be used? As far as I know, while it has no proof of security, it's generally fine as long as the implementation doesn't open up side-channel attacks during padding errors. $\endgroup$ – forest Feb 23 at 10:12
  • 1
    $\begingroup$ @forest The task of auditing an application of RSAES-PKCS1-v1_5 is much costlier than the task of auditing an application of RSAES-OAEP or RSA-KEM. (For RSAES-OAEP vs. RSA-KEM it's a tossup because while RSA-KEM is obviously simpler and safer and overall a better design, RSAES-OAEP is more familiar to more auditors.) And RSAES-PKCS1-v1_5 is incompatible with the fastest exponent $e = 3$! $\endgroup$ – Squeamish Ossifrage Feb 23 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.