I know it will not encrypt anything. But is $1$ valid as a public exponent in an RSA public key?
-
2$\begingroup$ Are you talking about the public key or the public exponent? $\endgroup$– MechMK1Jul 4, 2020 at 8:04
-
$\begingroup$ The public exponent. Or choosing e to gcd(e, m) = 1. $\endgroup$– Dũng Đào XuânJul 4, 2020 at 8:19
-
2$\begingroup$ Yes you can, the math will still check out, but you will not get any security. There was even a software that did this by accident because developers didn't know what the public exponent was supposed to be. $\endgroup$– MechMK1Jul 4, 2020 at 8:23
-
$\begingroup$ @MechMK1 Thank you very much! $\endgroup$– Dũng Đào XuânJul 4, 2020 at 8:29
-
1$\begingroup$ Piece of trivia: actual deployed code, by people who really ought to know better, actually used 1 as public exponent github.com/saltstack/salt/commit/…; and someone actually tried to use a misunderstood Thomas Pornin answer to justify it security.stackexchange.com/a/2339/1898 $\endgroup$– Bruno RohéeJun 30, 2022 at 8:43
1 Answer
TL;DR: it is a matter of conventions and context that $e=1$ is allowed or not.
Definitions of RSA vary:
- The original RSA article asks to first choose the private exponent $d$ as « a large, random integer which is relatively prime to $(p−1)\cdot(q−1)$ », then to compute $e$ as « the “multiplicative inverse” of $d$, modulo $(p−1)\cdot(q−1)$ ». This makes it extremely improbable that $e=1$, but allows it. Later descriptions of RSA tend to choose $e$ first.
- PKCS#1 v1.5 / RFC 2313 asks to « select a positive integer $e$ as its public exponent ». That allows $e=1$.
- PKCS#1 v2.0 / RFC 2437 states « the public exponent $e$ is an integer between $3$ and $n-1$ satisfying $\gcd(e,\lambda(n))=1$, where $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ ». That does not allow $e=1$, but still allows $e=\lambda(n)+1$ and $e=(p−1)\cdot(q−1)+1$, and perhaps a few other values of $e$ that are such that $x\mapsto x^e\bmod n$ is the identity function over $[0,n)$ just as it is for $e=1$. PKCS#1 v2.2 has the same prescription for $e$.
- FIPS 186-4 states « the exponent $e$ shall be an odd positive integer such that $2^{16}<e<2^{256}$ », and that forbids $e=1$. Combined with $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$ and a minimum for $d$, that makes it impossible $x\mapsto x^e\bmod n$ is the identity function.
For computer implementations, that depends on if an explicit test against $e=1$ is present or not. Both exist.
Sometime, public keys with $e=1$ or $e=\lambda(n)+1$ (which is more rarely disallowed by software) are used in test keys, or in reverse-engineering, in order to allow easy analysis of padding. Of course, such keys must not be used for encryption or signature of valuable data.
-
1$\begingroup$ "$e=\lambda(n)+1$ (which is more rarely disallowed by software)"; actually, some software assumes that $e$ fits in a 32 bit variable; obviously, that would disallow $e=\lambda(n)+1$ (unless $n$ is truly tiny...) $\endgroup$– ponchoJul 4, 2020 at 13:07
-
$\begingroup$ e=1 means d=1 which is not relatively prime to euler's totient (impossible). (Nor is d then a large integer, 1 is small) Why do you say this allows e=1? "The original RSA article asks to first choose the private exponent d as « a large, random integer which is relatively prime to (p−1)⋅(q−1) », then to compute e as « the “multiplicative inverse” of d, modulo (p−1)⋅(q−1) ». This makes it extremely improbable that e=1, but allows it." $\endgroup$ Jul 5, 2020 at 16:53
-
2$\begingroup$ @Adrian Self: by the usual definition of that, two integers are relatively prime if their Greatest Common Divisor is $1$. Thus $e=1$ is coprime to Euler's totient $\varphi(n)$. Also, $e=1$ implies $d=1$ only per some definitions of RSA (those that ask $d=e^{-1}\bmodλ(n)$ or $d=e^{-1}\bmod\varphi(n)$ ). It implies $d\equiv1\bmodλ(n)$ per all definitions of RSA, and $d\equiv1\bmod\varphi(n)$ per some definition of RSA, but that may not imply $d=1$, and does not under a most usual restriction for $d$, which is $0<d<n$, which thus allows at least $d=\varphi(n)+1$. $\endgroup$– fgrieu ♦Jul 5, 2020 at 16:59
-
$\begingroup$ Thanks, brainfart on d!=1, good to know that coprime just means gcd=1 $\endgroup$ Jul 5, 2020 at 17:01
-
$\begingroup$ @poncho: your comment below the answer (made like 30 months ago) led to a question asking an $(n,e)$ pair making textbook RSA encryption the identity over $[0,n)$, yet accepted by a cryptoAPI that checks $e<2^{32}$ (in addition to PKCS#1 conditions), with the less tiny $n$ possible. So far my best is a 244-bit $n$ (that factors in a snap, no contest). Update: this promptly got hugely improved! $\endgroup$– fgrieu ♦Jan 12, 2023 at 7:16