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

-

• 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?
@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