Consider the following version of padded RSA encryption, where encryption of $m$ is done by setting $m′ = (0^k~||~r~||~00000000~||~m)$ for a random $r$ (of length 8 btyes = 64 bits) and then computing the ciphertext $c = (m′)^e$ (mod $N$). For concreteness, further assume that $N$ is a 1024-bit RSA modulus, and that the scheme only handles 512-bit messages. For the rest of the problem, assume you are given some ciphertext $c$ that is the encryption of some 512-bit message. Suppose you learn that $(2^e)c$ (mod $N$) is a valid ciphertext. What does this tell you about the first bit of $m$?


1 Answer 1


I assume that this is a homework problem, and so I won't give you the answer. However, here are a few hints:

  • What does 'it is a valid ciphertext' mean?

  • If $c$ decrypts to the value $m'$ (not counting the depad operation; that is, if $m' = c^{1/e} \bmod N\ $), what does $2^ec \bmod N\ $ decrypt to? What is the relationship to those two values?

  • $\begingroup$ Thank you. I think (0^k||r||00000000) is like a head tag of any message, so when I decrypt m', the head is fixed. I think 2^e c modN=(2m')^e mod N, but I don't know what the connect with m. $\endgroup$
    – Yufei Ning
    Apr 19, 2013 at 21:49
  • 1
    $\begingroup$ @YufeiNing: If $2^e c = (2m')^e \bmod N\ $, and $2^e c \bmod N$ is a valid ciphertext, what does that say about $2m'$? $\endgroup$
    – poncho
    Apr 19, 2013 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.