// Arup Guha
// 11/7/06
// Solution for CIS 3362 DES Project

// There are many weaknesses in this solution due to my laziness!
// All of the constants in the algorithm should be stored in final
// static variables, but I just wanted to read in the information
// from the files instead of hard-coding them.

// Also, the key should stay the same for encrypting one file, but
// the blocks must change. This hasn't been indicated clearly.

/*** Past Java Solution Ported to C, started on 10/19/2015, for 2015 Fall Semester CIS 3362 Homework #3 ***/

#include <stdio.h>

const int ENCRYPT = 1;
const int DECRYPT = 2;

#define NUM_ROUNDS 16
#define BLOCK_SIZE 64
#define KEY_SIZE 56
#define ROUND_KEY_SIZE 48
#define P_SIZE 32
#define NUM_SBOXES 8
#define NUM_S_ROWS 4
#define NUM_S_COLS 16

// Critical pieces - made global.
long long key;
long long roundkeys[NUM_ROUNDS];
long long block;
long long usekey;

int stables[NUM_SBOXES][NUM_S_ROWS][NUM_S_COLS];
int IP[BLOCK_SIZE];
int IPInv[BLOCK_SIZE];
int E[ROUND_KEY_SIZE];
int PC2[ROUND_KEY_SIZE];
int P[P_SIZE];
int PC1[KEY_SIZE];
int keyshifts[NUM_ROUNDS];

void initDES(long long thekey);
void setBlock(long long bits);
void print();
char convertToHex(int start);
void encrypt();
void decrypt();
void switchHalves();
long long Permute(long long input, int perm[], int n);
long long PermuteKey(long long input, int perm[], int n, int k);
long long leftShift(long long whole, int start, int end, int numbits, int size);
void doRound(int num);
long long EXPAND(long long bits);
long long Sboxes(long long input);
void setKeys();
long long toLongLong(char hex[]);

void printL(long long value);
char convertToHexL(long long value, int start);

int main(void) {

    // Set up the key.
    char charkey[BLOCK_SIZE/4+1];
    scanf("%s", charkey);
    long long mykey = toLongLong(charkey);
    initDES(mykey);
    setKeys();

    // Get number of blocks.
    int numBlocks;
    scanf("%d", &numBlocks);

    // Read in each block and process...
    int loop;
    for (loop=0; loop<numBlocks; loop++) {
        char temp[BLOCK_SIZE/4+1];
        scanf("%s", temp);
        block = toLongLong(temp);
        encrypt();
        print();
    }

    return 0;
}

// Reads all the information from the file I created based on the order
// the values were stored in the file.
void initDES(long long thekey) {

    key = thekey;

    FILE* ifp = fopen("destables.txt", "r");

    int i, j;

    // Reads in the initial permutation matrix.
    for (i=0; i<BLOCK_SIZE; i++)
        fscanf(ifp, "%d", IP+i);

    // Reads in the inverse of the initial permutation matrix.
    for (i=0; i<BLOCK_SIZE; i++)
        fscanf(ifp, "%d", IPInv+i);

    // Expansion matrix used in each round.
    for (i=0; i<ROUND_KEY_SIZE; i++)
        fscanf(ifp, "%d", E+i);

    // The permutation matrix P used in each round.
    for (i=0; i<P_SIZE; i++)
        fscanf(ifp, "%d", P+i);

    // Reads in the 8 S-boxes!
    for (i=0; i<NUM_SBOXES; i++)
        for (j=0; j<BLOCK_SIZE; j++)
            fscanf(ifp, "%d", &stables[i][j/NUM_S_COLS][j%NUM_S_COLS]);


    // Reads in PC1, used for the key schedule.
    for (i=0; i<KEY_SIZE; i++)
        fscanf(ifp, "%d", PC1+i);

    // Reads in PC2 used for the round keys.
    for (i=0; i<ROUND_KEY_SIZE; i++)
        fscanf(ifp, "%d", PC2+i);

    // Reads in the shifts used for the key between each round.
    for (i=0; i<16; i++)
		fscanf(ifp, "%d", keyshifts+i);

    fclose(ifp);
}

// Prints out a block in hex on a line by itself.
void print() {
    int i;
    for (i=60; i>=0; i-=4)
        printf("%c",convertToHex(i));
    printf("\n");
}

// Converts the four bits in block from bits start+4..start to a single hex character.
char convertToHex(int start) {
    int val = (block >> start) & 0x0f;
    return val < 10 ? (char)('0'+val) : (char)('a'+val-10);
}

// Prints out a block in hex on a line by itself.
void printL(long long value) {
    int i;
    for (i=60; i>=0; i-=4)
        printf("%c",convertToHexL(value, i));
    printf("\n");
}

// Converts the four bits in block from bits start+4..start to a single hex character.
char convertToHexL(long long value, int start) {
    int val = (value >> start) & 0x0f;
    return val < 10 ? (char)('0'+val) : (char)('a'+val-10);
}


// Encrypts the current block.
void encrypt() {

    // Permute the block with the initial permutation.
    block = Permute(block, IP, BLOCK_SIZE);

    // Run 16 rounds.
	int i;
    for (i=0; i<16; i++) {
        doRound(i);
    }

    // Supposed to switch halves at the end and invert the initial
    // permutation.
    switchHalves();
    block = Permute(block, IPInv, BLOCK_SIZE);
}

void decrypt() {

    // This reverses the inverse permutation at the end.
    block = Permute(block, IP, BLOCK_SIZE);

    // Since the halves are stored on their opposite sides, we just have to
    // run our rounds in reverse order, pretty cool!!!
    int i;
    for (i=15; i>=0; i--) doRound(i);

    // When we're done, we have to switch halves because we were keeping everything
    // on the wrong half in the decryption process...
    switchHalves();

    // We have to undo this as well.
    block = Permute(block, IPInv, BLOCK_SIZE);
}

// Switches the left half of the current block with the right half.
void switchHalves() {
    long long newright = (block >> 32) & ((1LL << 32) - 1LL);
    long long temp = (block << 32);
    block = (block << 32) | newright;
}

// Permutes the bits in original according to perm and
// returns this permutation of the original bits.
long long Permute(long long input, int perm[], int n) {

    long long ans  = 0;
    int i;

    // Note: We subtract 1 from perm[i] because in the tables, the
    // permutations are 1-based, instead of 0-based.
    for (i=0; i<n; i++) {
        ans |= ( ((input >> (n-perm[i])) & 0x1LL) << (n-1-i) );
    }
    return ans;
}

// perm is size k, input stores n bits. returns the appropriate permutation.
long long PermuteKey(long long input, int perm[], int n, int k) {

    long long ans  = 0;
    int i;

    // Note: We subtract 1 from perm[i] because in the tables, the
    // permutations are 1-based, instead of 0-based.
    for (i=0; i<k; i++)
        ans |= ( ((input >> (n-perm[i])) & 0x1LL) << (k-1-i) );
    return ans;
}

// Takes the block of bits in whole from index start to index end,
// inclusive and cyclicly left-shifts them by numbits number of bits.
long long leftShift(long long whole, int start, int end, int numbits, int size) {
    long long mask = (1LL << (end-start+1)) - 1LL;
    long long lsbits = ((1LL << (size-end-1)) - 1LL) & whole;
    long long msbits = whole & (-(1LL<<(size-start)));
    long long temp = (whole >> (size-end-1)) & mask;
    temp = ((temp << numbits) & mask) | (temp >> (end-start+1-numbits));
    return msbits | lsbits | (temp << (size-end-1));
}

	// Runs round num of DES.
void doRound(int num) {

    long long left = ((block & 0xffffffff00000000LL) >> 32);
    long long right = block & 0x00000000ffffffffLL;

    long long expanded = EXPAND(right);
    long long xorans = expanded ^ roundkeys[num];

    // Run the s-boxes on all the appropriate "blocks".
    long long sboxout = Sboxes(xorans);

    // Permute the S-box output.
    long long fout = Permute(sboxout, P, P_SIZE);

    // Then do the necessary XOR.
    fout = fout ^ left;
    block = (right << 32) | fout;
}

// Expand the 32 bits and return the corresponding 48 bits.
long long EXPAND(long long bits) {

    long long ans = 0LL;
    int i;

    // Our permutation function doesn't work for this, so it's coded here.
    for (i=0; i<48; i++)
        ans |= ( ( (bits >> (32 - E[i])) & 0x1LL ) << (47-i)) ;
    return ans;
}

// Returns the output of putting the 48 bit input through the 8 S-boxes.
long long Sboxes(long long input) {

    long long ans = 0;
    int i;

    for (i=0; i<8; i++) {
        int row = ( ((input >> (47-6*i)) & 0x1) << 1) | ((input >> (42 - 6*i)) & 0x1);
        int col = ( input >> (6*(7-i) + 1) ) & 0xf;
        int temp = stables[i][row][col];
        ans |= (temp << (28-4*i));
    }

    return ans;
}

	// Set up the keys for each round.
void setKeys() {

    int i, j;

    // Set the original key with PC1.
    usekey = PermuteKey(key, PC1, BLOCK_SIZE, KEY_SIZE);

    // Go through and set the round keys using the process by which they
    // are supposed to be computed.
    for (i=0; i<16; i++) {

        // Supposed to left-shift both halves by the appropriate amount, based on the round.
        usekey = leftShift(usekey, 0, 27, keyshifts[i], KEY_SIZE);
        usekey = leftShift(usekey, 28, 55, keyshifts[i], KEY_SIZE);

        roundkeys[i] = 0LL;

        // Now, just copy in the (i+1)th round key.
        for (j=0; j<48; j++)
			roundkeys[i] |= ( ( usekey >> (56-PC2[j]) ) & 1LL ) << (47-j);
    }
}

	// Converts the string version of the key in HEX to binary which is
	// stored in an integer array of size 64...thus, the check bits are
	// included here.
long long toLongLong(char hex[]) {

    long long ans = 0;
	int i;

    // Go through all 16 characters.
    for (i=0; i<16; i++) {
        long long val = (long long)(hex[i]);

        // We need to assign value separately if it is a digit or a letter.
        if ('0' <= val && val <= '9')
            val = val - '0';
        else
            val = val - 'a' + 10;

        ans |= (val << (60-4*i));
    }

    return ans;
}