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!
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What does ⊕ mean? $\endgroup$– Chris EagleMar 16, 2013 at 14:31
-
$\begingroup$ It means XORing bit by bit, edited question $\endgroup$– Tomáš ŠímaMar 16, 2013 at 14:32
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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$.
answered Mar 16, 2013 at 14:35
-
$\begingroup$ 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? $\endgroup$ Mar 16, 2013 at 14:39
-
$\begingroup$ @Tomᚊíma: Have you tried checking any examples at all? $\endgroup$ Mar 16, 2013 at 14:44
-
$\begingroup$
$\endgroup$
1
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).
answered Mar 16, 2013 at 14:44
hmakholm left over Monicahmakholm left over Monica
286k24 gold badges427 silver badges689 bronze badges
-
$\begingroup$ I solve this in relation to cryptography. In my example n<=8, so the cipher can be bruteforced easily. Thanks a lot! $\endgroup$ Mar 16, 2013 at 14:51