How to build a reverse bitwise operation

Question

Bitwise Reverse Operation

I have a group of encrypted bytes which I can decrypt with the following function:

        byte b = (byte) (encrypted & 0xFF);
        return b >> 5 & 0x7 | (b & 0x1F) << 3;
    }
      
    0x51 >> 5 & 0x7 | 0x51 & 0x1F << 3 = 0x98
    ^                 ^

At first glance, it precedes a complex operation, so I have decided to separate it into parts.

I need to get the reverse operation. I know how byte operations work; the displacements seem easy to reverse but the AND are not more difficult. Many thought in previous threads that you cannot but would like to know your opinions about it.

I have noticed that the operation (b & 0x1F) only returns numbers of 0x0 and 0x1F and when it reaches 0x20 restarts at 0x0, so successively until 0x39 that returns 0x20 and 0x40 naturally returns 0x0.

Thinking about a possible solution, I have to know of a function "x & y = z" that I know "y" and "z", for example "x + 0x1F = 0x1A" can determine that the original byte could be any of the next {0x1A, 0x3A, 0x5A, 0x7A, 0x9A, 0xBA, 0xDA, 0xFA}, but now the question is how do I select the correct one.

To try to answer this question 0xA1 & 0x1F = 0x1 , assuming that of "x & y = z", we only know y and "z" the possible x would only be {0x1, 0x21, 0x41, 0x61, 0x81, 0xA1, 0xC1, 0xE1}, as you can see the answer is between 8 possible bytes.

Maybe I am posing the problem badly but I cannot build a reverse operation. Can you give me your opinion or explain how to put together an operation of this type?

Overall it's a rotate, if you look at it like that then it's easy to reverse — user555045
– user555045, Commented Oct 12, 2019 at 20:17
If you do 1110 and 0100 you cannot reverse , from the resulting 0100, if the original was 1110 or 0100, or 0101, it's just impossible. It's not a biunique projection. — Holger
– Holger, Commented Oct 12, 2019 at 20:20

Sweeper · Accepted Answer · 2019-10-12 20:31:20Z

3

To find a reverse operation, you should try looking at what the code is doing on the whole, instead of the individual operations.

The left operand of | says,

Shift b 5 places to the right >> 5 then clear all the bits except the least significant three bits & 0x7. Note that 7 is 111 in binary.

The above gets the most significant 3 bits of b and moves them all the way to the right. 1010 1100 would become 0000 0101.

The right operand of | says,

Clear all the bits except b's least significant 5 bits, and then shift b 3 places to the left. Note that 1F is 0001 1111 in binary.

This gets the least significant 5 bits of b then moves all the way to the left. 1010 1100 would become 0110 0000.

And finally, the | combines the two results together.

So on a high level of abstraction, this code just switches the first 3 and last 5 bits in a byte. 1110 0000 would become 0000 0111.

To reverse this, just switch the first 5, and last 3 bits.

byte b = (byte) (decrypted & 0xFF);
return b >> 3 & 0x1F | (b & 0x7) << 5;

You might want to learn about Bit Masks if you find this answer confusing.

answered Oct 12, 2019 at 20:31

Sweeper

292k23 gold badges260 silver badges438 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Dimfred Over a year ago

the & 0x1F and & 0x7 are redundant, They are there to null the bits, but a shift should pull 0s in this case, so this just makes it more complicated.

Sweeper Over a year ago

@Dimfred IIRC Java does an arithmetic shift, not a logical shift, so it’s not necessarily 0s.

Dimfred Over a year ago

Ah okay, should have added C++ to my comment. But good to know that things work entirely different in java.

ALX23z · Accepted Answer · 2019-10-12 20:19:58Z

0

Just compute array of 256 bytes: m_encrypt; byte -> encrypted byte

If it is one-to-one then it is reversable, otherwise it isn't.

Compute decryption array m_decrypt via

for(int i=0; i< 256; i++)
  m_decrypt[m_encrypt[i]] = i;

answered Oct 12, 2019 at 20:19

ALX23z

4,7631 gold badge13 silver badges20 bronze badges

1 Comment

Martian Source Over a year ago

Naturally, in this way we can easily obtain all possible bytes, but this generates 8 possibilities, for example for a 0x1A byte, there are three 8 possible combinations that operating with 0x1F would generate 0x1A in response: { 0x1A, 0x3A, 0x5A, 0x7A, 0x9A, 0xBA, 0xDA, 0xFA } For example if I do 0x9A & 0x1F = 0x1A Is the question as if x & y = z select the correct one if I only know "y" and "z"? Maybe I am focusing the problem badly and I need to see it from another angle. Maybe I have to see the result of the complete function to deduce some mathematical operation.

Collectives™ on Stack Overflow

How to build a reverse bitwise operation

Bitwise Reverse Operation

2 Answers 2

3 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Bitwise Reverse Operation

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related