### Reverse carry-less binary multiplication problem

Posted:

**Fri Nov 20, 2015 10:48 pm UTC**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?

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?