/**
 * des.c - Implementation of DES Cipher Algorithm.
 **/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef char bit_t;
typedef	unsigned char byte_t;

/* Initial permutation table */
byte_t ip_table[64] = {
	58, 50, 42, 34, 26, 18, 10,  2, 
	60, 52, 44, 36, 28, 20, 12,  4,
	62, 54, 46, 38, 30, 22, 14,  6,
	64, 56, 48, 40, 32, 24, 16,  8,
	57, 49, 41, 33, 25, 17,  9,  1,
	59, 51, 43, 35, 27, 19, 11,  3,
	61, 53, 45, 37, 29, 21, 13,  5,
	63, 55, 47, 39, 31, 23, 15,  7
};

/* Inverse initial permutation table */
byte_t inv_ip_table[64] = {
	40,  8, 48, 16, 56, 24, 64, 32,
	39,  7, 47, 15, 55, 23, 63, 31,
	38,  6, 46, 14, 54, 22, 62, 30, 
	37,  5, 45, 13, 53, 21, 61, 29,
	36,  4, 44, 12, 52, 20, 60, 28,
	35,  3, 43, 11, 51, 19, 59, 27,
	34,  2, 42, 10, 50, 18, 58, 26,
	33,  1, 41,  9, 49, 17, 57, 25
};

/*
 * Tables used in F function:
 *	expand permutation table,
 *	S-Box compresstion table,
 *	P-Box permutation table.
 */

/* Expand permutation table */
byte_t expand_table[48] = {
	32,  1,  2,  3,  4,  5,  4,  5,
	 6,	 7,  8,  9,  8,  9, 10, 11, 
	12, 13, 12, 13, 14, 15, 16, 17,
	16, 17, 18, 19, 20, 21, 20, 21,
	22, 23, 24, 25, 24, 25, 26, 27, 
	28, 29, 28, 29, 30, 31, 32,  1
};

/* P-Box pemutation table */
byte_t pbox_table[32] = {
	16,  7, 20, 21, 29, 12, 28, 17,
	 1, 15, 23, 26,  5, 18, 31, 10,
	 2,  8, 24, 14, 32, 27,  3,  9,
	19, 13, 30,  6, 22, 11,  4, 25
};

/* S-Box table */
byte_t /*unsigned char */ sbox_table[8][4][16] = {
/* S1 */
	14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
	 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
	 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
	15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13,
/* S2 */
	15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
	 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
	 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
	13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9,
/* S3 */
	10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
	13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
	13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
	 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12,
/* S4 */
	 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
	13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
	10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
	 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14,
/* S5 */
	 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
	14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
	 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
	11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3,
/* S6 */
	12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
	10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
	 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
	 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13,
/* S7 */
	 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
	13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
	 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
	 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12,
/* S8 */
	13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
	 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
	 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
	 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
};

/*
 * Tables used in subkeys generation:
 *	PC-1 table,
 *	PC-2 table,
 *	Left-shift table.
 */

/* PC-1 table */
byte_t pc1_table[56]={
	57, 49, 41, 33, 25, 17,  9,  1,
	58, 50, 42, 34, 26, 18, 10,  2,
	59, 51, 43, 35, 27, 19, 11,  3,
	60, 52, 44, 36, 63, 55, 47, 39,
	31, 23, 15,  7, 62, 54, 46, 38,
	30, 22, 14,  6, 61, 53, 45, 37,
	29, 21, 13,  5, 28, 20, 12,  4
};

/* PC-2 table */
byte_t pc2_table[48] = {
	14, 17, 11, 24,  1,  5,  3, 28,
	15,  6, 21, 10, 23, 19, 12,  4,
	26,  8, 16,  7, 27, 20, 13,  2,
	41, 52, 31, 37, 47, 55, 30, 40,
	51, 45, 33, 48, 44, 49, 39, 56,
	34, 53, 46, 42, 50, 36, 29, 32
};

/* Left-shift table */
byte_t leftrotate_table[16] = {
	 1,  1,  2,  2,  2,  2,  2,  2,
	 1,  2,  2,  2,  2,  2,  2,  1
};

bit_t subkeys[16][48] = {0};

/* 
 * function declarations
 */
void get_key(byte_t key[8], byte_t keystr[16]);
void gen_subkeys(byte_t key[8]);
void s_func(bit_t out[32], bit_t in[48]);
void f_func(bit_t data[32], bit_t subkey[48]);
void left_rotate(bit_t *data, int len, int times);
void xor(bit_t *ina, bit_t *inb, int len);
void byte2bit(bit_t *out, byte_t *in, int bits);
void bit2byte(byte_t *out, bit_t *in, int bits);
void transform(bit_t *out, bit_t *in, byte_t *table, int len);

void des_encrypt(byte_t out[8], byte_t in[8]);
void des_decrypt(byte_t out[8], byte_t in[8]);

/*
 * Main function.
 */
int main(int argc, char *argv[])
{
	byte_t keystr[16+1], key[8+1];
	byte_t plain_in[8+1], plain_out[8+1], cipher[8+1];
	int i;
	
	keystr[16] = key[8] = '\0';
	plain_in[8] = plain_out[8] = cipher[8] = '\0';
	
	printf("Input Key: ");
	gets(keystr);
	printf("Input PlainText: ");
	gets(plain_in);

	get_key(key, keystr);
	gen_subkeys(key);
	
	des_encrypt(cipher, plain_in);
	printf("CipherText: ");
	for (i = 0; i < 8; ++i)
		printf("%02X", cipher[i]);
	printf("\n");
		
	des_decrypt(plain_out, cipher);
	printf("Decryption: %s\n", plain_out);

	return 0;
}

/* 
 * function implementation
 */

/* 
 * get_key: get key from hex keystr, and store it in 'key'.
 *
 * Parameters:
 *	key:	[out] the result key.
 *	keystr:	[in] key string in hex.
 *
 * Return value:
 *	void.
 */
void get_key(byte_t key[8], byte_t keystr[16])
{
	int i;
	byte_t hi, low;
	
	for (i = 0; i < 8; ++i)
	{
		if ('0' <= keystr[2*i] && keystr[2*i] <= '9')
			hi = keystr[2*i] - '0';
		else if ('A' <= keystr[2*i] && keystr[2*i] <= 'F')
			hi = keystr[2*i] - 'A' + 10;
		if ('0' <= keystr[2*i+1] && keystr[2*i+1] <= '9')
			low = keystr[2*i+1] - '0';
		else if ('A' <= keystr[2*i+1] && keystr[2*i+1] <= 'F')
			low = keystr[2*i+1] - 'A' + 10;
		key[i] = (hi << 4) + low;
	}
}

/*
 * gen_subkeys: generate 16 subkeys.
 *
 * Parameters:
 *	key:	[in] key, from which the subkeys are generated.
 *
 * Return value:
 *	void.
 */
void gen_subkeys(byte_t key[8])
{
	bit_t k[64], *left, *right;
	int i;
	
	left = &k[0];
	right = &k[28];
	
	byte2bit(k, key, 64);
	transform(k, k, pc1_table, 56);
	for (i = 0; i < 16; ++i)
	{
		left_rotate(left, 28, leftrotate_table[i]);
		left_rotate(right, 28, leftrotate_table[i]);
		transform(subkeys[i], k, pc2_table, 48);
	}
}

/*
 * f_func: F-function.
 *
 * Parameters:
 *	data:	[in/out] data to encrypt.
 *	subkey:	[in] the corresponding subkey.
 *
 * Return value:
 *	void.
 */
void f_func(bit_t data[32], bit_t subkey[48])
{
	bit_t temp[48] = {0};
	
	transform(temp, data, expand_table, 48);	/* Expansion */
	xor(temp, subkey, 48);                  	/* Xor */
	s_func(data, temp);                     	/* S-Box */
	transform(data, data, pbox_table, 32);  	/* P-Box */
}

/*
 * s_func: S-box substitution.
 *
 * Parameters:
 *	out:	[out] the output result of S-box.
 *	in: 	[in] the input data into the S-box.
 *
 * Return value:
 *	void.
 */
void s_func(bit_t out[32], bit_t in[48])
{
	int i, row, col;
	
	for (i = 0; i < 8; ++i, in += 6, out += 4)
	{
		row = (in[0] << 1) + in[5];
		col = (in[1] << 3) + (in[2] << 2) + (in[3] << 1) + in[4];
		byte2bit(out, &(sbox_table[i][row][col]), 4);
	}
}

/*
 * left_rotate: left rotation of half of subkey.
 *
 * Parameters:
 *	data: 	[in/out] data to left-rotate.
 *	len:	[in] length of data.
 *	times:	[in] rotation times.
 *
 * Return value:
 *	void.
 */
void left_rotate(bit_t *data, int len, int times)
{
	bit_t temp[256];
	
	memcpy(temp, data, sizeof(bit_t) * times);
	memcpy(data, data+times, sizeof(bit_t) * (len-times));
	memcpy(data+len-times, temp, sizeof(bit_t) * times);
}

/*
 * xor: do Xor operation, the result is in  ina.
 *
 * Parameters:
 *	ina:	[in/out] the first operand, and also the result.
 *	inb:	[in] the second operand.
 *	len:	[in] the number of bits in the calculation.
 *
 * Return value:
 *	void.
 */
void xor(bit_t *ina, bit_t *inb, int len)
{
	int i;
	
	for (i = 0; i < len; ++i)
		ina[i] ^= inb[i];
}

/*
 * byte2bit: convert bytes into bits.
 *
 * Parameters:
 *	out:	[out] result bits.
 *	in: 	[in] bytes to convert.
 *	bits:	[in] number of bits in the result.
 *
 * Return value:
 *	void.
 */
void byte2bit(bit_t *out, byte_t *in, int bits)
{
	int i;
	
	for (i = 0; i < bits; ++i)
		out[i] = (in[i/8] >> (i%8)) & 1;
}

/*
 * bit2byte: convert bits into bytes.
 *
 * Parameters:
 *	out:	[out] result bytes.
 *	in: 	[in] bits to convert.
 *	bits:	[in] the number bits in the in.
 *
 * Return value:
 *	void.
 */
void bit2byte(byte_t *out, bit_t *in, int bits)
{
	int i;
	
	memset(out, 0, (bits+7) / 8);
	for (i = 0; i < bits; ++i)
		out[i/8] |= in[i] << (i%8);
}

/*
 * transform: transform data of the length 'len' from 'in' to 'out' 
 *            according to the table.
 *
 * Parameters:
 *	in: 	[in] the data to transform.
 *	out:	[out] the result data.
 *	len:	[in] the length of data to transform.
 *
 * Return value:
 *	void.
 */
void transform(bit_t *out, bit_t *in, byte_t *table, int len)
{
	bit_t temp[256] = {0};
	int i;
	
	for (i = 0; i < len; ++i)
		temp[i] = in[table[i]-1];
	memcpy(out, temp, sizeof(bit_t) * len);
}

/*
 * des_encrypt: DES encryption(64 bits).
 *
 * Parameters:
 *	out:	[out] encrypted data, ciphertext.
 *	in: 	[in] data to encrypt, plaintext.
 *
 * Return value:
 *	void.
 */
void des_encrypt(byte_t out[8], byte_t in[8])
{
	bit_t data[64], temp[32], *left, *right;
	int i;
	
	left = &data[0];
	right = &data[32];
	
	byte2bit(data, in, 64);
	transform(data, data, ip_table, 64);		/* initial permutation */
	for (i = 0; i < 16; ++i)            		/* 16 rounds */
	{
		memcpy(temp, right, 32);
		f_func(right, subkeys[i]);
		xor(right, left, 32);
		memcpy(left, temp, 32);
	}
	memcpy(temp, right, 32);            		/* last round doesn't exchange */
	memcpy(right, left, 32);
	memcpy(left, temp, 32);
	transform(data, data, inv_ip_table, 64);	/* inverse initial permutation */
	
	bit2byte(out, data, 64);
}

/*
 * des_decrypt: DES decryption(64 bits).
 *
 * Parameters:
 *	in: 	[in] data to decrypt, ciphertext.
 *	out:	[out] decrypted data, plaintext.
 *
 * Return value:
 *	void.
 */
void des_decrypt(byte_t out[8], byte_t in[8])
{
	bit_t data[64], temp[32], *left, *right;
	int i;
	
	left = &data[0], right = &data[32];
	
	byte2bit(data, in, 64);
	
	transform(data, data, ip_table, 64);		/* initial permutation */
	for (i = 15; i >= 0; --i)       			/* 16 rounds */
	{
		memcpy(temp, right, 32);
		f_func(right, subkeys[i]);
		xor(right, left, 32);
		memcpy(left, temp, 32);
	}
	memcpy(temp, right, 32);       				/* last round doesn't exchange */
	memcpy(right, left, 32);
	memcpy(left, temp, 32);
	transform(data, data, inv_ip_table, 64);	/* inverse initial permutation */
	
	bit2byte(out, data, 64);
}