Page 1 of 1

Reverse carry-less binary multiplication problem

Posted: Fri Nov 20, 2015 10:48 pm UTC
by deskjethp
Rule the fifth declaration: This is not homework, but probably looks like it. It's just an interesting thing I ran across the other day on a coding website.

So I found this decryption challenge where an obfuscated encryption algorithm is provided and the challenge is to code up a decryption program. When simplified (It's all presented in hex and whatnot in the beginning), I found the encryption takes two given inputs and does the equivalent of longhand binary multiplication on them up to the point where all the addends would be added together, but does an XOR operation on them instead of adding them, producing the output. This XOR step would be the same as just doing the adding but never carrying. The goal of the challenge is to provide the possible original factors, having been given the result.

Example encryption:


Given the inputs 11111 and 11111, they get almost-multiplied together giving the addends 11111, 111110, 1111100, 11111000, and 111110000. These are XOR'd together producing 101010101. So given something like 101010101, the goal is to produce (11111 , 11111) as output. Or whatever other factors might happen to produce it.

Another example with multiple inputs that produce the same output:


In this case, the goal is to produce (011, 110) and (101, 10). I've noted that for outputs that end in 0, 2 (10) is a possible input. Some inputs (there might be a pattern here that will help) also produce the same output as when they are multiplied (101 and 10 produces 1010, 101 and 11 produce 1111, etc).

So far, I've figured out the following:

1) It is not feasible to brute force this beyond a low number of digits in the output.
2) Factors of x digits and y digits produce an output of x+y-1 digits.
2b) Therefore any amount of addends may be produced from 1-n where n=output digits
2c) Obviously, multiplying a 6 digit by a 2 digit number longhand will either produce 6 addends or 2 addends for example. They will XOR together to the same result and
must therefore share some property, but I don't know what.
3) Whatever addends are produced are going to all be the topmost one shifted to the left some number of times.
4) If the output ends in 1, both factors must also end in 1.
5) The leftmost digit of the largest is always going to be a (You wouldn't have leading 0s)

All of this is sort of helpful in figuring out an efficient way of solving this, most particularly #3 probably, but I don't know how to calculate this efficiently for a set of two 128 bit inputs as the problem states. I know there's a way to do it, since a number of folks have solved it, but working in a deductive brute force fashion isn't going to cut it. On top of that, I don't know if there's a direct correlation between the factors and the answer, if the addends need to be calculated, and I don't have a good way of getting the factors from the given addends. The addends->factors part is easy enough to deal with for one of the inputs since it's all left shifts and one of them can be deduced from the topmost non-zero addend, but given that there are multiple sets of input factors for each given output, figuring them all out is proving to be a challenge.

Insights anyone?

Re: Reverse carry-less binary multiplication problem

Posted: Fri Nov 20, 2015 11:04 pm UTC
by Thesh
Ask yourself this: under what conditions would the least significant bit of the output be "1" - you should be able to figure it out from there.

Re: Reverse carry-less binary multiplication problem

Posted: Fri Nov 20, 2015 11:20 pm UTC
by deskjethp
If both inputs end in 1, then the output ends in 1. I have stated this in 4). However, beyond only the rightmost digit, I haven't yet been able to determine a pattern.

Am I missing something obvious?

Re: Reverse carry-less binary multiplication problem

Posted: Sat Nov 21, 2015 6:08 pm UTC
by Cauchy
If we treat the binary string a_na_{n-1}...a_0 as the polynomial a_nx^n + a_{n-1}x^{n-1} + ... + a_0x^0, then your multiplication is multiplication of these polynomials in the polynomial ring over Z/2Z, that is, the integers modulo 2. Since Z/2Z is a field, Z/2Z[x] is a unique factorization domain, which means that every polynomial factors uniquely into prime polynomials. In your original multi-factor example, for instance, x^3 + x = x(x+1)^2 modulo 2, so 1010 can be written as [x(x+1)^2]*1 = 1010 * 1, [x(x+1)]*(x+1) = 110*11, or [(x+1)^2]*x = 101*10.

Re: Reverse carry-less binary multiplication problem

Posted: Mon Nov 23, 2015 9:59 am UTC
by jestingrabbit
So, to add to what Cauchy is saying, you can build up a big bag of "prime" polynomials, say, all the polynomials of degree less than n, then you can try to divide each polynomial of length n by each polynomial with degree less than floor(n/2) to get the primes of degree n. And you don't have to test all of them, you know the one's with a 0 in the least significant bit are divisible by x, and the ones with an even number of bits set to 1 are divisible by x+1, and there's a somewhat trickier rule for x^2 +x +1, so you don't need to deal with all the polynomials, and given an input of length m, you only need to get the primes up to m/2, and you only have to build as many as you need till you get factors of the input.

So, still computationally pretty heavy, but a little more tractable.

Re: Reverse carry-less binary multiplication problem

Posted: Tue Feb 14, 2017 3:45 pm UTC
by SecMunic
The inverse operation is super simple:

write the number in base 4. You will get a number with only 0 and 1

interpret the number as written in base 2 (common binary). That's the answer.