1
$\begingroup$

So we have $q = 311$, $p = 163$, $e = 101$, I found $d = 39281$ using Euclidean Algorithm and checked by encrypting and decrypting a message.

Next it is asking if $e = 101$ was a good choice or would the value $e = 9131$ be better.

What I know:

  • $101$ = prime

  • $39281$ = not prime ( $23 x\times 397$)

Both options for $e$ are relatively prime to $(p - 1) \cdot (q - 1)$ and both options for $e$ satisfy $𝑒 < λ(n)$.

Are there any other things I need to consider for $e$ to answer the question? I have looked around the forum and web but I'm stuck right now.

Hints preferred not a full answer!

$\endgroup$
1
  • 1
    $\begingroup$ @fgrieu As hints are preferred over a full answer you might as well turn the hints into an answer :P Welcome to crypto, Mr.Mushy99... $\endgroup$
    – Maarten Bodewes
    May 9 '18 at 15:05
1
$\begingroup$

Hint: compute $d$ for the alternate value of $e$ considered. Isn't something rather remarkable? What is the probability that it occurs by chance?

While that is totally immaterial given that $p$ and $q$ are billions-n'-billions times too small to prevent factorization (gross understatement), what if we scaled things? Why would it matter (caution: there are several levels of answer to that later one)?

Facts relevant to this (and many other sensible RSA questions) can be found by combing Dan Boneh's classic Twenty Years of Attacks on the RSA Cryptosystem (in Notices of the AMS, Vol. 46, No. 2, pp. 203-213, 1999).
I might have properly cited that followup attempt if it had acknowledged what inspired it.

$\endgroup$

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.