Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
add comment

1 Answer 1

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
1  
@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
add comment

Your Answer

 
discard

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.