0
$\begingroup$

I have this cipher which is as follows :

Take 2 numbers : A=1011 and B=1010

if the ith bit of X is 1 then shift Y* i times to the left. So in the end you will get something like

   1010
  1010
1010

So now you Apply XOR on these numbers which results in :

00001010
00010100 (XOR)
01010000 (XOR)
---------
01001110

So you end up getting 2 4-bit numbers from 01001110: that is 0100 & 1110

So now given 0100 & 1110 how do I reverse this and find the initial X & Y

##Update

So for a given output B : 000073af 00000000

The possible Inputs are :

32
00000001 000073af

32
00000083 000000e5

32
000000e5 00000083

32
000073af 00000001
$\endgroup$
2
$\begingroup$

As I outlined in the same question you crossposted, this is essentially a factorization problem; you're given a polynomial over $GF(2)$, and you want to know the pairs of possible products that make up that polynomial.

This can be reduced to factoring the polynomial into the multiset of prime factors (in the case you listed, the factorization is $73af = 83 \times e5$, where both $83$ and $e5$ are prime polynomials) and then going through the various possible ways of separating out the multiset into two (and multiplying the two).

So, the question is now "how do you factor a polynomial?". A survey of some fast algorithms to do this is here; to start off with, you might want to start with trial division.

That is, to look for prime factors of a polynomial $P$, you scan through small polynomials $Q$ (and you need to scan through only the prime polynomials), and see if $Q$ is a divisor of $P$. You can do that by running the multiplication operation in reverse; you shift $Q$ so that the msbit of $Q$ is the same as the msbit of $P$, exclusive or them, and replace $P$ with that exclusive-or. You repeat until $P$ is smaller than $Q$ (and so you can't continue); if you end up with $P=0$, then $Q$ is a factor (and by keeping track of the shifts, that'll give you the polyonomial $P/Q$).

$\endgroup$
3
  • $\begingroup$ Okay Sir I understood what is GF and Polynomial factorization. The parer's you provide are too complicated fro my understanding. I found this question useful : math.stackexchange.com/questions/1105079/… $\endgroup$ Dec 27 '15 at 20:12
  • $\begingroup$ One Question still remains how do I generate prime polynomials in GF 2 upto a certain degree ? $\endgroup$ Dec 27 '15 at 20:12
  • $\begingroup$ @AkshayLAradhya: if your looking for prime polynomials to scan through for trial division, well, if you don't have them pregenerated, it'd probably be easier just to scan through all polynomials (and while you can save some time by skipping multiples of $x$ and $x+1$, I'm not sure if that's not too complicated for you at your stage) $\endgroup$
    – poncho
    Dec 29 '15 at 14:29
0
$\begingroup$

In general you can't. As soon as just one of $A, B$ is 0000 the end result will be 0000000. Also, the left most bit of the output is alway 0, hence you really get just 7 bits of output from 8 bits of input ...

$\endgroup$
2
  • $\begingroup$ Hmm I dont need to get the exact input, there could be many possible inputs that could lead to an given output.I just want to find all of them. $\endgroup$ Jul 7 '15 at 7:20
  • $\begingroup$ Updated the question :) $\endgroup$ Jul 7 '15 at 7:26

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.