4
$\begingroup$

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$
$\endgroup$
0

2 Answers 2

5
$\begingroup$

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.
$\endgroup$
4
  • $\begingroup$ Increasing p and q helps to make e smaller. p - 19889; q - 11579; e - 23. But I still have big d - 214516652 $\endgroup$ Sep 26, 2020 at 22:15
  • $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Sep 26, 2020 at 22:21
  • $\begingroup$ Is there any way to do 1999^2001%347 in programming? $\endgroup$ Sep 26, 2020 at 22:45
  • $\begingroup$ $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. $\endgroup$
    – fgrieu
    Sep 27, 2020 at 7:13
-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Sep 26, 2020 at 22:04

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.