Bit manipulation of chars in Java or C?

I am a student trying to implement the DES algorithm. I have a choice of 2 languages: C & Java. I did understand the algorithm, but am stuck at the very beginning as to manipulation of the key.

Here's the problem. In DES, we have a 64-bit key (8 chars in C and 4 in Java, although I can cast the char to byte to get only the ASCII part), of which every 8th bit is a parity bit and needs to be stripped to make it a 56-bit key and do further processing. I have thought about this for long, but cannot find a way to strip every 8th bit and store the result in another char array (in Java as well as C). I tried using the java.util.BitSet class, but got confused.

Any suggestions as to how can I remove every 8th bit and concat adjacent bytes(J开发者_如何学JAVAava) or chars(C) to get the 56 bit key?

I am aware of the bit operations and shifting, but for the specific example:

Suppose I have an 16 bit key: 1100 1001 1101 1000.

I need to remove the 8th and 16th bit, making the key: 1100 100 1101 100.

If I declare 2 bytes, how do I truncate the 8th bit and append the 9th bit to it, making the first byte: 1100 1001

So, what I need help with is how do I, replace 8th bit with 9th bit, replace 16th bit with 17th bit and so on to derive a 56-bit key from 64-bit key?

If someone can explain it to me, I might probably be able to implement it regardless of language.

---

Be careful of 16-bit chars in Java. Many methods only convert the lower 8 bits. Read the documentation carefully. It is more usual to treat a cryptographic key as a a byte[] in Java due to the stronger typing than in C.

As to the parity bits, check through the DES algorithm carefully and see where they are used. That should give you a hint as to what you need to do with them.

---

In C, you can manipulate bits with the bitwise operators, such as & and |, as well as the bitshift operators << and >>.

For instance, to turn off the high bit of a given byte, you can do this.

char c = 0xBF;  // initial value is bit pattern 10111111
c &= 0x7F;      // perform AND against the bit pattern 01111111
                // final value is bit pattern 00111111 (0x3F)

Does that make sense? Obviously, you need to be able to convert from a bit pattern to hex, but that's not too hard.

You can use similar masking to extract the bits you want, and put them in an output buffer.

Update:

You have 64 bits (8 bytes) of input, and want 56 bits (7 bytes) of output.

Let's represent your input as the following, where each letter represents a single bit The 'x' bits are the ones you want to throw away.

xAAAAAAA xBBBBBBB xCCCCCCC xDDDDDDD xEEEEEEE xFFFFFFF xGGGGGGG xHHHHHHH

So you want your final answer to be:

AAAAAAAB BBBBBBCC CCCCCDDD DDDDEEEE EEEFFFFF FFGGGGGG GHHHHHHH

So in C, we might have code like this:

unsigned char data[8] = {/* put data here */};

// chop off the top bit of the first byte
data[0] <<= 1;

// the bottom bit of data[0] needs to come from the top data bit of data[1]
data[0] |= (data[1] >> 6) & 0x01;

// use similar transformations to fill in data[1], data[2], ... data[6]
// At the end, data[7] will be useless

Of course this is not optimized at all, but hopefully you get the idea.

---

I can briefly tell about a way....i will explain further if required...

Right shift all the 8 chars by 1 ie c1 = c1>>1 etc

Multiplyc1 with the total number of bytes (ie56) ie c1 * 0x0000000000 (not sure how many zeros)

Then, add 0x0000+ to next chars ie c2 = c2 + 0x0000; c3 = c3 + 0x000000 so on (Keep adding 2 0s for proceeding chars)

Now, start adding c1 + c2 + c3.......

The idea here is that, first fill in the number with zeros and start adding teh other chars so that they keep lying properly

00 00 00 00 00 00 00 00 00
34 00 00 00 00 00 00 00 00   (c1 = c1>>1) . Here c1=0x34, c2=0x67
00 67 00 00 00 00 00 00 00   (c2 = c2>>1)
so on...............

Add teh above; I hope this will help.

---

@jwd, @jscode Thanks a lot for your help. To jwd: I got the idea from your code. Seemed pretty simple logic after I read it.. :-) Wonder why I didnt think of that. Well, I did polish your idea a little bit and it works fine now in Java. If anyone has any suggestions, please let me know. THANKS.. P.S.: The testing part is very primitive. I print the bit values. I did it manually for a couple of examples and used the same as input and it works fine.

=============================================

public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter an 8 char key: ");
        String input;
        try {
            // get key, key.length()>=8 chars
            input = br.readLine();
            if (input.length() < 8) {
                System.out.println("Key < 8B. Exiting. . .");
                System.exit(1);
            }
            // java char has 16 bits instead of 8 bits as in C,
            // so convert it to 8 bit char by getting lower order byte &
            // discarding higher order byte
            char[] inputKey = input.toCharArray();
            byte[] key64 = new byte[8];
            byte[] key56 = new byte[7];

            // consider only first 8 chars even if input > 8
            for (int counter = 0; counter < 8; counter++)
                key64[counter] = (byte) inputKey[counter];

            System.out.print("\n$$ " + new String(key64) + "  $$\n");

            // converting 64bit key to 56 bit key
            for (int counter = 0; counter < KEY_LENGTH - 1; counter++) {
                key64[counter] = (byte) (key64[counter] >>> 1);
                key64[counter] = (byte) (key64[counter] << 1);
            }

            for (int counter = 0; counter < KEY_LENGTH - 1; counter++) {
                key56[counter] = (byte) (key64[counter] << counter);
                key56[counter] = (byte) (key56[counter] | (key64[counter + 1] >>> (KEY_LENGTH - 1 - counter)));
            }

            /*Conversion from 64 to 56 bit testing code
             System.out.println(new String(key56));

            System.out.println();
            for (int counter1 = 0; counter1 < 7; counter1++) {
                for (int counter2 = 7; counter2 >= 0; counter2--) {
                    System.out.println(key56[counter1] & (1 << counter2));
                }
                System.out.println();
            }*/

        } catch (IOException e) {
            e.printStackTrace();
        }
    }