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.

  • $\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, 2015 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, 2015 at 18:04
  • $\begingroup$ What endianness does that use? $\;$ $\endgroup$
    – user991
    Jul 8, 2015 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, 2015 at 22:09


Browse other questions tagged or ask your own question.