[ CHALLENGE ]: bit manipulation / arrays / strings

Question

A poorly encryped message from our nemesis has been intercepted, it is up to you to use your bitmanipulation, array and string skills to decypher it.
The data: 98EF122CB2193031C3799231BA643A7D5269435CB021C22CD0139044C10803392087BA68522799295A76D06C43783A78426CE020B270D000905D0318887420049032B00982087878E261427A5243F0540221905A606CB864B879C334E95A6344

We have found out that the data consists of 16 bit unsigned values.
Each of those 16 bit values only have 8 valid data bits in them, the rest is noise.

Note: bit numbers count from the least significant bit, meaning that bit 0 is the right-most bit and bit 15 is the left-most bit.

What you must do to decypher this message is move all 'real' bits to the correct position in a byte:
- invert bit 4 and move it to position 0 in your byte
- move bits 11-13 to bits 1-3 in your byte
- move bit 1 to bit 4 in your byte
- invert bits 7 and 8 and move them to bits 5-6 in your byte
- move bit 10 to bit 7 in your byte

If you do this for every 16 bit value and make a proper ascii string using the created bytes you will get a message. I think you'll know when you've got it right :)

Answer 1

@Freddy, I have a few uncertainties:

- To do this, we read the string two bytes at a time, convert the two bytes read into 16bit integer, then start working on it. Am I getting this right this far?

- When we move bit 4 to 0, do we swap the bits 4 & 0? or bit 4 overwrites bit 0?

Answer 2

@Freddy
Here is a new version I have developed for this challenge. It does not use bitset at all and relies only on &,>>,<< and ^ to get/set the bits. Kindly review.

https://code.sololearn.com/cRd5jpaRFpYv/#cpp

Answer 3

"Well done mate! You've nailed bitmanipulation :)".

https://code.sololearn.com/cCPY4BDy0pnx/#cpp

Edit - Here is an encoder for the same: https://code.sololearn.com/cfW9kFYzDDxy/#cpp

Answer 4

@Freddy
I thought you could use C++ as well, but if that is what you want to be used, then Ill post another code in pure C tomorrow.

Answer 5

A bit later than promised, but here it is:
https://code.sololearn.com/chBya2XD2Z0d/#c

Answer 6

Is moving a byte same as copying it for this challenge? Or in a move operation, we are to change the original bit being copied to zero?

Answer 7

Also, 16 bits will form 2 ASCII characters, right?

Answer 8

I have developed a program that performed the following steps :
0) From the data, separate 16 bits
(4 Hex digits).
Eg - 98EF.
1) Convert this substring to binary form.
Eg - 98EF -> 1001100011101111
2) Apply decryption algorithm :
Eg - 1001100011101111 ->
1001100000010111
3) Convert data to characters :
Eg - 1001100000010111 ->
- and char(152).

Now, is this what we need to do? I don't understand how to do the last step, as char(152) isn't part of the standard ASCII set. If there is anything wrong in the above implementation please let me know.

Answer 9

Oops, there was a small bug in the description, that is now corrected (the line that now says: "invert bits 7 and 8 and move them to bits 5-6 in your byte").

You will indeed have to copy the data into a 16 bit unsigned array. From there you can copy each indicated bit to a new char array, where you have to be sure to move the bits to the correct position and in 3 cases: invert the bit.

16 bits are indeed as big as 2 ASCII characters, but that information shouldn't help you solve the problem :)

0) From the data, separate 16 bits (4 Hex digits). Eg - 98EF.
1) Convert this substring to binary form. Eg - 98EF -> 1001 1000 1110 1111
2) Apply decryption algorithm
- invert bit 4 and move it to position 0 in your byte:
--> bit 4 is 0, so bit 0 will become 1: 0000 0001
- move bits 11-13 to bits 1-3 in your byte
--> bits 13-11 are 011, so bits 3-1 will become 011: 0000 0111
- move bit 1 to bit 4 in your byte
--> bit 1 is 1, so bit 4 will become 1: 0001 0111
- invert bits 7 and 8 and move them to bits 5-6 in your byte
--> bits 7 and 8 are 01, so bits 6-5 will become 10: 0101 0111
- move bit 10 to bit 7 in your byte
--> bit 10 is 0, so bit 8 will become 0: 0101 0111
The first character is thus 0x57, which is a 'W'.

Does this help?

Answer 10

@Freddy
Thats what I got wrong. I thought I need to apply the change to the original 16 bits, but it was to be done on a new bit array.

Answer 11

@Kinshuk: a new byte array :)

Answer 12

@Kinshuk: great that it works, but you didn't use bitmanipulation. Try it using this definition (include <stdint.h> for uint16_t type):
uint16_t data[] =
{
0x98EF, 0x122C, 0xB219, 0x3031, 0xC379, 0x9231, 0xBA64, 0x3A7D, 0x5269, 0x435C,
0xB021, 0xC22C, 0xD013, 0x9044, 0xC108, 0x0339, 0x2087, 0xBA68, 0x5227, 0x9929,
0x5A76, 0xD06C, 0x4378, 0x3A78, 0x426C, 0xE020, 0xB270, 0xD000, 0x905D, 0x0318,
0x8874, 0x2004, 0x9032, 0xB009, 0x8208, 0x7878, 0xE261, 0x427A, 0x5243, 0xF054,
0x0221, 0x905A, 0x606C, 0xB864, 0xB879, 0xC334, 0xE95A, 0x6344
};

Answer 13

C++ is fine, but use bitwise operations &, | and ^.

Answer 14

I'll post my version in a few days, then you can compare :)

Answer 15

By the way: for those who want to learn more about bitwise operators, take a look at the following video:
https://www.youtube.com/watch?v=7PNG-6B8Vuk&index=6&list=PLULj7scb8cHgDLDHcRcJ1osiOORic86wR