DES Algorithm Java Implementation

In my next posts on java development I’m gonna share with you a series of encryption algorithms implemented in java(not quite fast but more clear and organized).

I’ll start with a good old one: DES algorithm.This is good for introduction, because it represent an old standard on which many new algorithms are built, and is quite easy to understand. It will naturally lead to another algorithm: Triple DES – as you’ll see later.

DES is a symmetric block cipher, operating on blocks of 64 bits of data and a key of 64 bits. Deciphering is done with the same key but in reverse order. Only 56 bits of the key are used actually in the process. Remaining 8 bits are used for parity check, therefore can be discarded.

Next is a brief description of the algorithm along with the code.

Encryption algorithm

The overall structure of encryption steps are as follows:

1. A block of 64 bits is permuted by an initial permutation called IP.
2. Resulting 64 bits are divided in two halves of 32 bits, left and right.
3. Right half goes through a function F(Feistel function)
4. Left half is XOR-ed with output from F function above.
5. Left and right are swapped(except last round).
6. If last round, apply an inverse permutation IP-1 on both halves and that’s the output else, goto step 3.

Steps 3-5 constitute a round. DES has 16 identical rounds. Note the two halves are processed alternately. This structure represents what is called a Feistel network.

Feistel function F is represented by the following operations:

1. Expansion – 32 bits to 48 bits based on an expansion table.
2. Key mixing – round key combined with 48 bits from previous step by XOR operation.
3. Substitution – previous result divided into 8x6bits blocks before processed by s-boxes(substitution boxes)
4. Permutation based on a fixed permutation table.

I’ll show in code the above steps. For more details about the theory behind this consult the official document. I highly advise to read it along with my explanation.

Function encrypt64Bloc

private static byte[] encrypt64Bloc(byte[] bloc,byte[][] subkeys, boolean isDecrypt) {
	byte[] tmp = new byte[bloc.length];
	byte[] R = new byte[bloc.length / 2];
	byte[] L = new byte[bloc.length / 2];

	tmp = permutFunc(bloc, IP);

	L = extractBits(tmp, 0, IP.length/2);
	R = extractBits(tmp, IP.length/2, IP.length/2);

	for (int i = 0; i < 16; i++) {
		byte[] tmpR = R;
		if(isDecrypt)
			R = f_func(R, subkeys[15-i]);
		else
			R = f_func(R,subkeys[i]);

		R = xor_func(L, R);
		L = tmpR;
	}

	tmp = concatBits(R, IP.length/2, L, IP.length/2);

	tmp = permutFunc(tmp, invIP);
	return tmp;
}

This is the main function. Is used for both encryption/decryption pointed out by the last param.
It requires a fixed length block of 64 bits of data and the subkeys from the key schedule.
You can see the overall structure: apply initial permutation, divide the block, run through 16 rounds with the corresponding operation, apply inverse permutation and return the result.

Utility functions

• Function setBit – given a vector of bytes, a position and a value(0 or 1) it sets the correpsonding bit in the vector to the given value. It calculates the byte position and bit position within that byte position which needs to be set.

private static void setBit(byte[] data, int pos, int val) {
     int posByte = pos / 8;
     int posBit = pos % 8;
     byte tmpB = data[posByte];
     tmpB = (byte) (((0xFF7F >> posBit) & tmpB) & 0x00FF);
     byte newByte = (byte) ((val << (8 - (posBit + 1))) | tmpB);
     data[posByte] = newByte;
}

• Function extractBit – similar to setBit – extract the bit from the given position.

private static int extractBit(byte[] data, int pos) {
     int posByte = pos / 8;
     int posBit = pos % 8;
     byte tmpB = data[posByte];
     int bit = tmpB >> (8 - (posBit + 1)) & 0x0001;
     return bit;
}

• Function extractBits – given a vector of bytes, extract a series of consecutive bits from a starting position and a given length. It uses the above helper functions

private static byte[] extractBits(byte[] input, int pos, int n) {
     int numOfBytes = (n - 1) / 8 + 1;
     byte[] out = new byte[numOfBytes];
     for (int i = 0; i < n; i++) {
           int val = extractBit(input, pos + i);
           setBit(out, i, val);
     }
     return out;

}

• Function rotLeft – given an input vector of bytes rotates bits to the left by given number of positions. For flexibility, there’s a param len indicating how many bits from the input vector to be rotated, allowing you to rotate just fragments of the input vector.

private static byte[] rotLeft(byte[] input, int len, int pas) {
     int nrBytes = (len - 1) / 8 + 1;
     byte[] out = new byte[nrBytes];
     for (int i = 0; i < len; i++) {
          int val = extractBit(input, (i + pas) % len);
          setBit(out, i, val);
     }
     return out;
}

• Function xor_func – as simple as it sounds – apply xor function on two vector of bytes.

private static byte[] xor_func(byte[] a, byte[] b) {
     byte[] out = new byte[a.length];
     for (int i = 0; i < a.length; i++) {
          out[i] = (byte) (a[i] ^ b[i]);
     }
     return out;
}

• Function separateBytes – this will help separating block of bytes in chunks of variable number of bits. Given a vector of bytes it will extract groups of bits of the given length, putting them in separate bytes.

private static byte[] separateBytes(byte[] in, int len) {
     int numOfBytes = (8 * in.length - 1) / len + 1;
     byte[] out = new byte[numOfBytes];
     for (int i = 0; i < numOfBytes; i++) {
          for (int j = 0; j < len; j++) {
               int val = extractBit(in, len * i + j);
               setBit(out, 8 * i + j, val);
          }
     }
     return out;
}

• Function concatBits – concatenate bits from 2 input vector of bytes, given, for each vector, how many bits to take from them.

private static byte[] concatBits(byte[] a, int aLen, byte[] b, int bLen) {
     int numOfBytes = (aLen + bLen - 1) / 8 + 1;
     byte[] out = new byte[numOfBytes];
     int j = 0;
     for (int i = 0; i < aLen; i++) {
          int val = extractBit(a, i);
          setBit(out, j, val);
          j++;
     }
     for (int i = 0; i < bLen; i++) {
          int val = extractBit(b, i);
          setBit(out, j, val);
          j++;
     }
      return out;
}

DES Specific functions

• Function permutFunc – is a generalized function for applying a permutation on a vector of bytes. It requires also as param the table of permutation. Permutations are performed bitwise. Bits are permuted based on the elements of the table. For example if first element of table is 57 then bit 57 will be bit 1 in the permuted block of bytes. Expansion permutation is similar except in its table, some values repeat, that’s why it will result a larger number of bits.

private static byte[] permutFunc(byte[] input, int[] table) {
     int nrBytes = (table.length - 1) / 8 + 1;
     byte[] out = new byte[nrBytes];
     for (int i = 0; i < table.length; i++) {
          int val = extractBit(input, table[i] - 1);
          setBit(out, i, val);
     }
     return out;
}

• Function f_func – is the Feistel function. It consist of other function calls, resembling steps described earlier.

private static byte[] f_func(byte[] R, byte[] K) {
     byte[] tmp;
     tmp = permutFunc(R, expandTbl);
     tmp = xor_func(tmp, K);
     tmp = s_func(tmp);
     tmp = permutFunc(tmp, P);
     return tmp;
}

• Function s_func – apply the 8 s-boxes to the 48bits of data resulting 32 bits of output. The 48 bits are divided in groups of 6 bits. First and last bit of each group will indicate a row in s-box.Middle 4 will indicate a column. corresponding value of 4 bits from the s-box will substitute the input of 6 bits.

private static byte[] s_func(byte[] in) {
     in = separateBytes(in, 6);
     byte[] out = new byte[in.length / 2];
     int halfByte = 0;
     for (int b = 0; b > 7 & 0x0001) + (valByte >> 2 & 0x0001);
          int c = valByte >> 3 & 0x000F;
          int val = sboxes[b][r][c];
          if (b % 2 == 0)
               halfByte = val;
          else
               out[b / 2] = (byte) (16 * halfByte + val);
     }
     return out;
}

This are all the functions necessary to encrypt a single block of 64 bits. For extending this to variable length of clear text, there’s another function in the code called encrypt which is actually public, representing the interface with the user. You can call this with any data. It will add padding to data, for making it a multiple of 64(8 bytes).Padding is in the format: first bit ‘1’, rest of them ‘0’. This way, padding can be easily removed from the decrypted cipher text.

For more details about this function and decrypt function and also tables of permutation values, check out the entire source code to see how it comes together.

Key Schedule

1. 64 bits goes through a permutation called PC-1(permuted choice) resulting 56 bits.
2. 56 bits are divided into two halves
3. Each half will be rotated left by 1 or 2 bits depending on the round
4. Both sides go through permutet choice 2 (PC-2) which selects 24 bits from left and right resulting a 48 bit round key.

Following is the method for generating subkeys

private static byte[][] generateSubKeys(byte[] key) {
     byte[][] tmp = new byte[16][];
     byte[] tmpK = permutFunc(key, PC1);

     byte[] C = extractBits(tmpK, 0, PC1.length/2);
     byte[] D = extractBits(tmpK, PC1.length/2, PC1.length/2);

     for (int i = 0; i < 16; i++) {

          C = rotLeft(C, 28, keyShift[i]);
          D = rotLeft(D, 28, keyShift[i]);

          byte[] cd = concatBits(C, 28, D, 28);

          tmp[i] = permutFunc(cd, PC2);
     }

     return tmp;
}

Source code contains also a variation of Triple DES(see mode of operation for cryptographic algorithms). 3DES is a much stronger algorithm. Uses three 64 bit keys and blocks are encrypted with one key, then decrypted with second key, and again encrypted with the last key. Decryption process is similar but in reverse order.
DES is no more secure, mainly because its short key length, being breakable by brute force attack in a convenient time.

DES source code for this tutorial: Download DES.java file