# How to learn the first bit of m in padded RSA

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

-

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?

-
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