CODEWITHSUNDEEP
calgorithmcryptographyreverse
Benjamin
Benjamin

Reputation: 617

Reversing AND Bitwise

Here's the following algorithm:

int encryption(int a, int b) {
    short int c;
    uint8_t d;

    c = a ^ b;
    
    d = 0;
    while(c) {
        c &= c - 1;
        d++;
    }
    
    return d;
}

How can I find which values a and b I should send to that function to decide the output value of d?

In other words, how can I reverse the algorithm if, let's say, I wanted d == 11?

Upvotes: 3

Views: 205

Answers (3)

IVlad
IVlad

Reputation: 43507

This:

while(c) {
    c &= c - 1;
    d++;
}

counts the number of 1-bits in c. So for example, if c = 10110, d will be 3.

This:

c = a ^ b;

Does an exclusive or between a and b. This means that all the 1-bits that share the same position in both a and b will be zeroes, and all the positions that have different values in a and b will become 1. For example:

101110 ^
011010
========
110100

So basically, the algorithm finds the number of 1-bits in a ^ b. To force it to output a certain value, just make a = 0 then b = number with d 1-bits.

To get a number with d 1-bits, consider b = (2 to the power of d) - 1.

So if you want d = 11, then a = 0 and b = (2 to the power of 11) - 1 = 2048 - 1 = 2047.

To efficiently compute 2 to a certain power programmatically, use this formula:

2 to the power of k == 1 << k

So, basically: encryption(a, b) == d if a = 0 and b = (1 << d) - 1.

Upvotes: 1

kennytm
kennytm

Reputation: 523634

d is just the number of "1" bits in c, see http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan.

Therefore, you just need to find a and b such that their bitwise-XOR value has exactly 11 bits, e.g. a = 0 and b = 2047.

(This is not encryption. This is a very weak one-way hashing. An encryption have to provide a way to get back the original value (decryption).)

Upvotes: 1

Pavel Radzivilovsky
Pavel Radzivilovsky

Reputation: 19114

I see it counts SET bits in a XOR b?

Ok, then let's say a==0, b==4095.

Upvotes: -1

Related Questions