#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
#include <memory.h>
#include <stdlib.h>

typedef unsigned char BYTE;
typedef unsigned short WORD;
typedef unsigned int DWORD;
typedef unsigned long long DDWORD;
typedef string Key;



class DES
{
public:
	DES(Key, bool);
	~DES() {}

	void Encrypt(BYTE[], int&);
	void Decrypt(BYTE[], int&);

private:
	
	static const int LEN = 8;
	static const int ROUND = 16;
	static const BYTE IP[64];
	static const BYTE IP_1[64];
	static const BYTE SBox[8][4][16];
	static const BYTE E[48];
	static const BYTE PBox[32];
	static const BYTE PC_1[56];
	static const BYTE PC_2[64];

	Key key;							
	DDWORD subkey[16];

	void SingleRound(DDWORD&, int);	//單輪結(jié)果

	DWORD SBoxS(DDWORD);				//S盒
	DWORD PBoxS( DWORD);				//P盒
	DDWORD Extend(DWORD);				//函數(shù)E擴展
	void StringToDDWORD(DDWORD&, BYTE[]);		//
	void SwapBits(DDWORD &in)	{in = ((in & 0xffffffff00000000ULL) >> 32) | ((in & 0x00000000ffffffffULL) << 32);}			//64位中32位互換
	void DDWORDToString(BYTE[], DDWORD);			//

	void KeyGenerator();

	void doIP(DDWORD&);				//初始置換
	void doIP_1(DDWORD&);				//初始逆置換
	void PC1(DDWORD&);					//密鑰生成的PC1

	DDWORD PC2(DDWORD);					//密鑰生成的PC2
	DDWORD GET(DDWORD x, int pos){return x & ((DDWORD)1 << pos);}			//取位
	DDWORD REV(DDWORD);					//反轉(zhuǎn)64位
};


DDWORD DES::REV(DDWORD x)
{
	x = ((x & 0x5555555555555555ULL) << 1 ) | ((x & 0xAAAAAAAAAAAAAAAAULL) >> 1 );
	x = ((x & 0x3333333333333333ULL) << 2 ) | ((x & 0xCCCCCCCCCCCCCCCCULL) >> 2 );
	x = ((x & 0x0F0F0F0F0F0F0F0FULL) << 4 ) | ((x & 0xF0F0F0F0F0F0F0F0ULL) >> 4 );
	x = ((x & 0x00FF00FF00FF00FFULL) << 8 ) | ((x & 0xFF00FF00FF00FF00ULL) >> 8 );
	x = ((x & 0x0000FFFF0000FFFFULL) << 16) | ((x & 0xFFFF0000FFFF0000ULL) >> 16);
	x = ((x & 0x00000000FFFFFFFFULL) << 32) | ((x & 0xFFFFFFFF00000000ULL) >> 32);
	return x;
}


void DES::Encrypt(BYTE m[], int& len)
{
	DDWORD ts;

	int addlen = 8 - (len % LEN);

	for(int i = 0; i < addlen; ++i)
		m[len++] = (BYTE) addlen;

	for(int i = 0; i < len; i += LEN)
	{
		StringToDDWORD(ts, m + i);
		doIP(ts);
		for(int j = 0; j < ROUND; ++j)
			SingleRound(ts, j);
		SwapBits(ts);
		doIP_1(ts);
		DDWORDToString(m + i, ts);
	}
}

void DES::Decrypt(BYTE e[], int &len)
{
	DDWORD ts;
	for(int i = 0; i < len; i += LEN)
	{
		StringToDDWORD(ts, e + i);
		doIP(ts);
		for(int j = ROUND - 1; j >= 0; --j)
			SingleRound(ts, j);
		SwapBits(ts);
		doIP_1(ts);
		DDWORDToString(e + i, ts);
	}
	
	len -= e[len - 1];

}


void DES::SingleRound(DDWORD & in, int r)
{
	DWORD L = (DWORD) ((in & 0xffffffff00000000ULL) >> 32), R = (DWORD) (in & 0x00000000ffffffffULL);
	DDWORD e;
	DWORD out;
	e =  Extend(R);
	e = e ^ subkey[r];	
	out = SBoxS(e);
	out = PBoxS(out);
	out ^= L;
	L = out;
	in = ((DDWORD)R << 32) | L;
}

void DES::doIP(DDWORD & in)
{
	DDWORD ret = 0L;
	for(int i = 0; i < 64; ++i)
	{
		ret <<= 1;
		ret |= (GET(in, IP[i] - 1) != 0);
	}
	in = ret;
}

void DES::doIP_1(DDWORD & in)
{
	DDWORD ret = 0L;
	for(int i = 0; i < 64; ++i)
	{
		ret <<= 1;
		ret |= (GET(in, IP_1[i] - 1) != 0);
	}
	in = ret;
}


DWORD DES::SBoxS(DDWORD in)
{
	DWORD ret = 0;
	BYTE res[8];
	for(int i = 0; i < 8; ++i, in >>= 6)
	{
		DWORD t1 = (DWORD) ((in & 0x1eULL) >> 1);
		DWORD c  = (DWORD) ((in & 0x01ULL) ^ ((in & 0x20ULL) >> 4));
		res[i] = SBox[i][c][t1];
		ret <<= 4;
		ret |= res[i] & 0x0f;
	}

	return ret;
}

DWORD DES::PBoxS( DWORD so)
{
	DWORD ret = 0;
	for(int i = 0; i < 32; ++i)
	{
		ret <<= 1;
		ret |= (GET((DDWORD)so, PBox[i] - 1) != 0);
	}
	return ret;
}

DDWORD DES::Extend(DWORD r)
{
	DDWORD ret = 0L;
	for(int i = 0; i < 48; ++i)
	{
		ret <<= 1;
		ret |= (GET((DDWORD)r, E[i] - 1) != 0);
	}
	return ret;
}

void DES::PC1(DDWORD & in)
{
	DDWORD ret = 0;
	for(int i = 0; i < 56; ++i)
	{
		ret <<= 1;
		ret |= (GET(in, PC_1[i] - 1) != 0L);
	}
	in = ret;
}

DDWORD DES::PC2(DDWORD in)
{
	DDWORD ret = 0L;
	for(int i = 0; i < 48; ++i)
	{
		ret <<= 1;
		ret |= (GET(in, PC_2[i] - 1) != 0L);
	}
	return ret;
}

void DES::StringToDDWORD(DDWORD & result, BYTE in[])
{
	DDWORD ret = 0L;
	for(int i = 0; i < LEN; ++i)
	{
		ret <<= 8;
		ret |= in[i];
	}
	result = ret;
}

void DES::DDWORDToString(BYTE out[], DDWORD in)
{
	DDWORD offset = 0xff00000000000000ULL;
	for(int i = 0; i < LEN; ++i, offset >>= 8)
		out[i] = (BYTE) ((in & offset) >> (56 - 8 * i));
}


const BYTE DES::IP[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
};

const BYTE DES::IP_1[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
};

const BYTE DES::SBox[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}
	}
};

const BYTE DES::E[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
};

const BYTE DES::PBox[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
};

const BYTE DES::PC_1[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
};


const BYTE DES::PC_2[64] = 
{
	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
};


DES::DES(Key k, bool mode = false)
{
	
	if(mode)
	{
		while(k.length() < 16) k.append("0");
		Key e = "";
		for(int i = 0, l = 0; i < 16; ++i)
		{
			l <<= 4;
			l += k[i] >= 'A' && k[i] <= 'Z' ? k[i] - 'A' + 10 : k[i] - '0';
			if(i % 2)
			{
				e += (unsigned char) l;
				l = 0;
			}
		}
		k = e;
	}
	else
	{
		while(k.length() < 8) k.append(" ");
	}
	key = k; 
	KeyGenerator();
}

void DES::KeyGenerator()
{
	DDWORD inkey = 0L;

	for(int i = 0; i < 8; ++i)
	{
		inkey <<= 8; 
		inkey ^= (DDWORD)key[i] & 0xff;
	}

	inkey = REV(inkey);
	PC1(inkey);

	const DDWORD of1 = 0x0fffffffULL, of2 = 0xfffffff0000000ULL;
	DDWORD afL[17];				//after left shift
	
	afL[0] = inkey;

	for(int i = 1; i <= 16; ++i)
	{
		if(i == 1 || i == 2 || i == 10 || i == 16)
		{
			DDWORD a1 = afL[i-1] & of1;
			DDWORD h1 = (afL[i-1] & 0x08000000ULL) >> 27;
			a1 = (a1 << 1) ^ h1;
			a1 &= of1;
			
			DDWORD a2 = afL[i-1] & of2;
			DDWORD h2 = (afL[i-1] & 0x80000000000000ULL) >> 27;
			a2 = (a2 << 1) ^ h2;
			a2 &= of2;

			afL[i] = 0L;
			afL[i] |= a2; 
			afL[i] |= a1;
		}
		else
		{
			DDWORD a1 = afL[i-1] & of1;
			DDWORD h1 = (afL[i-1] & 0x0C000000ULL) >> 26;
			a1 = (a1 << 2) ^ h1;
			a1 &= of1;
			
			DDWORD a2 = afL[i-1] & of2;
			DDWORD h2 = (afL[i-1] & 0xC0000000000000ULL) >> 26;
			a2 = (a2 << 2) ^ h2;
			a2 &= of2;

			afL[i] = 0L;
			afL[i] |= a2;
			afL[i] |= a1;
		}
	}

	for(int i = 0; i < 16; ++i)
		subkey[i] = PC2(REV(afL[i+1]) >> 8);
}

char encode(BYTE x)
{
	if(x >= 0 && x <= 9)
		return x + '0';
	return x + 'A' - 10;
}

string stringToHex(BYTE x[])
{
	string ret = "";
	for(int i = 0; i < 8; ++i)
	{
		ret += encode((x[i] >> 4) & 0x0f);
		ret += encode((x[i] & 0x0f));
	}
	return ret;
}

string byteToString(BYTE x[])
{
	string ret = "";
	for(int i = 0; i < 8; ++i)
	{
		ret += (char) x[i];
	}
	return ret;
}

int main()
{
	cout << "Input Key:";
	string key;
	int len = 8;
	BYTE ciphertext[16];
	cin >> key;
	cout << "Input PlainText:";
	for(int i = 0; i < 8; ++i)
	{
		char x;
		cin >> x;
		ciphertext[i] = (BYTE) x;
	}
	DES des(key, true);
	des.Encrypt(ciphertext, len);
	cout << "CipherText:" << stringToHex(ciphertext) << endl;
	des.Decrypt(ciphertext, len);
	cout << "Decryption:" << byteToString(ciphertext) << endl;
	return 0;
}