0
$\begingroup$

How can I show that $C' = 2^e·C^* \bmod N$ when it is decrypted will add zero bits in the least significant bit position of the key?

I am not sure if the cause is multiplying by a ciphertext which would lead the key to be multiplied by it as well.

$\endgroup$
  • $\begingroup$ Welcome to CSE, and kudos for now using MathJax (is not that wonderful?). What does the star in $C^*$ mean? Note: there might be some confusion about least significant bit position in key, when as far as I can see only least significant bit position in plaintext gets changed. $\endgroup$ – fgrieu Dec 12 '19 at 6:22
  • $\begingroup$ @fgrieu thank you. I'm asking for the least significant bit position of the key not the ciphertext. for C* it denotes that it is different than C' $\endgroup$ – mmm Dec 12 '19 at 6:24
  • 1
    $\begingroup$ In (textbook/unpadded) RSA, when modified ciphertext $C'$ gets decrypted, we get a mofied plaintext. We do not get any new key or key component, thus the ciphertext modification can not "add zero bits in the least significant bit position of the key". There is all signs that you are asking for the least significant bit position of the plaintext, not key or ciphertext. And that's the answer you got. $\endgroup$ – fgrieu Dec 12 '19 at 6:31
  • $\begingroup$ @fgrieu I think the key is actually the cipher text ( if the OP sends a key via RSA, as is common). $\endgroup$ – Henno Brandsma Dec 12 '19 at 18:09
1
$\begingroup$

Because (if $C=P^e$ where $P$ is the plain text): $2^e C= (2P)^c \pmod{N}$ so multiplying the ciphertext by $2^e$ modifies the plain text by a multiplication of $2$, which is a bitshift to the left of $1$, so we get 1 new zero bit at the end. To get $m$ zero bits, we need to multiply by $2^{em}$ (modulo $N$), of course.

| improve this answer | |
$\endgroup$
  • $\begingroup$ but I'm actually trying to figure it out for the key not the ciphertext. How is that possible? $\endgroup$ – mmm Dec 12 '19 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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