# RSA - Is $e = d$ a problem?

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$$

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} (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.
• Increasing p and q helps to make e smaller. p - 19889; q - 11579; e - 23. But I still have big d - 214516652 Sep 26, 2020 at 22:15
• See this for a recent history of record factorizations and convince you that RSA with $n$ not at least in the hundred digits is pointless in any project putting RSA to use. $d$ must be large enough, otherwise it can be found from $n$ and $e$ (see Boneh and Durfee). Practice is $d$ about as large as $n$, and $e=65537$, which is extremely small compared to $d$.
– fgrieu
Sep 26, 2020 at 22:21
• Is there any way to do 1999^2001%347 in programming? Sep 26, 2020 at 22:45
• $1999^{2001}\bmod347$ is amenable to "programming" in all common languages. In python, that can be pow(1999,2001,347). Try it online!. It uses standard techniques in modular exponentiation to neither compute $1999^{2001}$ explicitly as the working 1999**2001%347 would do, nor perform $2000$ multiplications. Both would be feasible with this small example, but not with the much larger numbers in actual use of RSA.
– fgrieu
Sep 27, 2020 at 7:13

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.

• I do not see that this answers the part of the question about $e=d$, which indeed is a disaster from a security standpoint. And what does not make sense is choosing 2-digit $p$ and $q$ in any project putting RSA to use.
– fgrieu
Sep 26, 2020 at 22:04