RSA as defined by PKCS#1v2.2 allows public exponent $e=n-2$. And textbook RSA was born with $e=n$ (see second bullet here).

Are these variants essentially as secure as (textbook) RSA with fixed $e$? With random $e$? Can we reduce the security of one to the security of the other, or of another variant of RSA?

Note: as in RSA with fixed $e$, we choose $p$ and $q$ large random distinct secret primes. And further:

  • for $e=n-2$, it must hold $\gcd[q-2,p-1]=1$ and $\gcd[p-2,q-1]=1$ ;
  • for $e=n$, if must hold $\min(p,q)$ does not divide $\max(p,q)-1$.

Rather obvious, but does answer one of the questions: both can be reduced to the security of RSA with $e' = a_n n (n-2)$ for any (reasonably sized) public integer $a$ which can be a function of $n$. For example, given $c \equiv m^n$ for a random unknown $m$, we solve $c^{n-2} \equiv m^{n(n-2)}$ for $m$. With probability at least $1/gcd(e,\lambda(n))$ the answer will be $m$.


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.