3
$\begingroup$

I know it will not encrypt anything. But is $1$ valid as a public exponent in an RSA public key?

$\endgroup$
  • 2
    $\begingroup$ Are you talking about the public key or the public exponent? $\endgroup$ – MechMK1 Jul 4 at 8:04
  • $\begingroup$ The public exponent. Or choosing e to gcd(e, m) = 1. $\endgroup$ – Dũng Đào Xuân Jul 4 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$ – MechMK1 Jul 4 at 8:23
  • $\begingroup$ @MechMK1 Thank you very much! $\endgroup$ – Dũng Đào Xuân Jul 4 at 8:29
9
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\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$ – poncho Jul 4 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$ – Adrian Self Jul 5 at 16:53
  • 1
    $\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 at 16:59
  • $\begingroup$ Thanks, brainfart on d!=1, good to know that coprime just means gcd=1 $\endgroup$ – Adrian Self Jul 5 at 17:01

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.