# RSA algorithm assignment [duplicate]

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.

• 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}$. – fgrieu Jul 8 '15 at 18:03
• 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? – poncho Jul 8 '15 at 18:04
• What endianness does that use? $\;$ – user991 Jul 8 '15 at 18:17
• 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. – Maarten Bodewes Jul 8 '15 at 22:09