Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|improve this question
up vote 2 down vote accepted

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?

share|improve this answer
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. – Yufei Ning Apr 19 '13 at 21:49
@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'$? – poncho Apr 19 '13 at 22:25
I forget the CCA! thank you very much! – Yufei Ning Apr 20 '13 at 2:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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