Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have numbers A,B,C.D.

(⊕ is XOR)

C = A⊕B

D = A⊕(B+1)

Is there any way to get D from C, when I do not know A and B? How?

Thanks for help!

share|improve this question
    
What does ⊕ mean? –  Chris Eagle Mar 16 '13 at 14:31
    
It means XORing bit by bit, edited question –  Tomáš Šíma Mar 16 '13 at 14:32
add comment

2 Answers

up vote 2 down vote accepted

This is not possible. For example, suppose $A=B=0$. Then $C=0\oplus 0=0$, while $D=0 \oplus 1=1$. But if $A=B=1$, then we still have $C=0$, but now $D=1 \oplus 10=11$. Since one value of $C$ can correspond to two different values of $D$, $D$ cannot be deduced from $C$.

share|improve this answer
    
Ahh, I see. Thanks! Are two different values the maximum I can get? Can I get three(or more) different values of D for one C? –  Tomáš Šíma Mar 16 '13 at 14:39
    
@Tomᚊíma: Have you tried checking any examples at all? –  Chris Eagle Mar 16 '13 at 14:44
    
That was stupid comment, I see now. –  Tomáš Šíma Mar 16 '13 at 14:45
add comment

As Chris explains, you cannot find $D$ exactly.

However, you can narrow down the possible values for $D$ considerably, which can be important in some contexts (such as cryptography).

$B+1$ always differs from $B$ in that a number of least significant bits have been flipped. No bit that is flipped is to the left of any bit that is preserved. This description carries over when you xor with the unknown $A$. So you can say that $D$ must be $C\oplus(2^n-1)$ for some $n\ge 1$.

(It is also easy to see that each of these values is in fact a possible value for $D$, given appropriate choice of $A$, no matter what $C$ is).

share|improve this answer
    
I solve this in relation to cryptography. In my example n<=8, so the cipher can be bruteforced easily. Thanks a lot! –  Tomáš Šíma Mar 16 '13 at 14:51
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.