RSA - Is $e = d$ a problem?

Question

I'm working on small RSA project in university. At this moment I have done this:

1. An array of prime numbers is generated from selected range.
2. $p$ and $q$ selected randomly from this array
3. $n$ calculated
4. $\phi(n)$ calculated
5. $e$ calculated
6. $d$ calculated

What do you think about $e$ and $d$ in that case?

• $p = 29$
• $q = 53$
• $n = 1537$
• $\phi(n) = 1456$
• $e = 545$
• $d = 545$

Answer 1

It would be disastrous if an RSA key generation procedure had a sizable probability to end with $e=d$, because in that case, the public key reveals the private key, which must be secret from a security perspective.

But $e=d$ is a symptom of a larger problem lying in steps 1 and 2 of the key generation procedure: RSA can only be secure if $p$ and $q$ are selected in a way such that factoring $n$ is hard, and that means $p$ and $q$ should be large primes. The modern baseline is $n$ of $2048$ bits, that is $617$ decimal digits, not $4$ decimal digits. For this, $p$ and $q$ are chosen randomly among a sizable subset of primes of about $309$ digits. There are over about $10^{305}$ such primes, thus generating them all then picking within that is infeasible. The right procedure is to directly generate $p$ and $q$.

With $p$ and $q$ random primes this large, and a random choice of $e$ such that $\gcd(e,\phi(n))=1$ (or a random choice of primes $p$ and $q$ with the only dependency on $e$ that $\gcd(e,p-1)=1$ and $\gcd(e,q-1)=1$, as is common practice), it's infinitesimally improbable that $d=e$, or more generally that one or a few re-encryption(s) lead to decryption. See these questions on the cycling attack.

---

There are RSA key generation procedures in FIPS 186-4 appendix B.3. Ignore the proposed $1024$-bit key size, which is obsolete. The proposed $2048$ is the baseline, $3072$ increasingly common, extending to $4096$-bit not unreasonable. These procedures differ from those used in the question by several points including:

• Generating large primes $p$ and $q$ unpredictably in a prescribed interval $[2^{(k-1)/2},2^{k/2}]$, where $k$ is the desired bit size of $n$ (e.g. $3072$)
• Requiring odd $e$ with $2^{16}<e<2^{256}$ (the lower because that acts as a safeguard against poor choices of RSA padding, the higher for interoperability and to make some other poor choices impossible)
• Using $d=e^{-1}\bmod\lambda(n)$ (where $\lambda$ is the Carmichael function) rather than $d=e^{-1}\bmod\phi(n)$. Both are mathematically fine, but using $\lambda$ insures generating the smallest positive private exponent $d$ working for a given $(n,e)$.
• Requiring a minimum size of $d$ (much larger than $2^{256}$, which incidentally insures $d>e$), more as a safeguard against errors than out of mathematical necessity.

Answer 2

Although we commonly use (p-1)*(q-1) to calculate d, you can actually use lcm(p-1, q-1) [least common multiple] and get smaller values for e and d that work. Now 545 squared mod 1456 = 1, so yes the calculations are correct (if a bit weird). Try a smaller value for e, and you should values that make more sense.