1
$\begingroup$

This question already has an answer here:

Alice wants to share a symmetric key with Bob. She encrypts the small (64-bit) secret key $K$ with Bob’s public RSA key $(n,e)$ by padding it with zeroes to 2048 bits (the length of n) and computing $$C\gets(\text{0..0}\|K)^e\bmod n$$ Thereupon, she sends $C$ to Bob. Discuss either why this key exchange is secure or describe an efficient attack that can recover $K$ with far less than $2^{64}$ operations.

$\endgroup$

marked as duplicate by otus, rath, Gilles, yyyyyyy, cygnusv Jul 9 '15 at 7:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Hints: a) consider what happens when $e$ is small; say 3, 5, or 17, which are reasonable choices when proper padding is used. $\;$ b) regardless of $e$, consider odds that $K$ can be written as the product of two integers neither exceeding, say, $2^{40}$. $\endgroup$ – fgrieu Jul 8 '15 at 18:03
  • $\begingroup$ Hint: if they signify the RSA encryption operation of $M$ as $RSA(M)$, then we have $RSA(A) \times RSA(B) = RSA(A \times B)$ (where $\times$ is modulo $n$). How could you take advantage of that? $\endgroup$ – poncho Jul 8 '15 at 18:04
  • $\begingroup$ What endianness does that use? $\;$ $\endgroup$ – user991 Jul 8 '15 at 18:17
  • $\begingroup$ Why the heck would you have to left pad with zeros if the next operation turns the binary input into a big endian number? It would immediately remove all the zero bytes again. Then the question itself: that discussion if it is secure or not is completely irrelevant because of the next question. $\endgroup$ – Maarten Bodewes Jul 8 '15 at 22:09

Browse other questions tagged or ask your own question.