DES Implementation ***EXPERIMENTAL**

myDes.c

/*
 * Assumptions/Limitations:
 *  1. gcc compiler is used.
 *  2. byte is 8 bits long.(sizeof(char)==1)
 *  3. word is 32 bits long.(sizeof(int)==4)
 *  4. dword is 64 bits long.
 */
#include "assert.h"
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
typedef unsigned int word;
typedef unsigned char byte;
typedef struct
{
    word l;
    word r;
}dword;

/*
 * IP - Initial Permutation maps [0..63] bit positions in the input to [1..64]
 * Usage: outbits[pos] = inbits[IP[pos]-1];
 */
int IP[] = {
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
};

/*
 * FP - Final Permutation (Initial Permutation's Inverse)
 */
int FP[] = {
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
};

/*
 * E - Expansion Function
 */
int E[] = {
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 - Permutation Function
 */
int P[] = {
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
};

/*
 * PC1 - Permuted Choice 1
 */
int PC1[] = {
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
};

/*
 * PC2 - Permuted Choice 2
 */
int PC2[] = {
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
};

/*
 * S - Substitution Box
 */
int S[8][4][16] = {
    // S1 ( s_ix=0 )
    {
        { 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 ( s_ix=1 )
    {
        { 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 ( s_ix=2 )
    {
        { 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 ( s_ix=3 )
    {
        {  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 ( s_ix=4 )
    {
        {  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 ( s_ix=5 )
    {
        { 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 ( s_ix=6 )
    {
        {  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 ( s_ix=7 )
    {
        { 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}
    }    
};

/*
 * ROTATIONS - Number of left rotations in the key-schedule
 */
int ROTATIONS[] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};

// Bit-level Operation Functions
int get_byte_bit(byte b, int ix);
void set_byte_bit(byte *b, int ix);
void reset_byte_bit(byte *b, int ix);
int get_word_bit(word w, int ix);
void set_word_bit(word *w, int ix);
void reset_word_bit(word *w, int ix);
int get_dword_bit(dword dw, int ix);
void set_dword_bit(dword *dw, int ix);
void reset_dword_bit(dword *dw, int ix);

// Transformation Functions
dword expansion(int *EV, int e_len, word in);
dword permutate(int *PV, int p_len, dword in);
byte s_box(int s_ix, byte in);
word substitute(dword in);
dword left_rotate_28_28(dword key56, int nor);

// DES functions
dword *gen_subkeys(dword key);
word feistel(word in, dword subkey);
dword encrypt_dword(dword pt, dword *subkeys);
char *encrypt(char *pt, dword key);

void test();

int main(int argc, char **argv)
{
    test();
}
int get_byte_bit(byte b, int ix)
{
    assert(ix >= 0 && ix < 8);
    if(b & (1<<(7-ix)))
        return 1;
    else
        return 0;    
}
void set_byte_bit(byte *b, int ix)
{
    assert(ix >= 0 && ix < 8);
    *b = *b | (1<<(7-ix));
}
void reset_byte_bit(byte *b, int ix)
{
    assert(ix >= 0 && ix < 8);
    *b = *b & (~(1<<(7-ix)));
}
int get_word_bit(word w, int ix)
{
    assert(ix >= 0 && ix < 32);
    if(w & (1<<(31-ix)))
        return 1;
    else
        return 0;
}
void set_word_bit(word *w, int ix)
{
    assert(ix >= 0 && ix < 32);
    *w = *w | (1<<(31-ix));
}
void reset_word_bit(word *w, int ix)
{
    assert(ix >= 0 && ix < 32);
    *w = *w & (~(1<<(31-ix)));
}

int get_dword_bit(dword dw, int ix)
{
    assert(ix >= 0 && ix < 64);
    if(ix < 32)
    {
        if(dw.l & (1<<(31-ix)))
            return 1;
        else
            return 0;
    }
    else
    {
        if(dw.r & (1<<(63-ix)))
            return 1;
        else
            return 0;
    }
}
void set_dword_bit(dword *dw, int ix)
{
    assert(ix >= 0 && ix < 64);
    if(ix < 32)
    {
        dw->l = dw->l | (1<<(31-ix));
    }
    else
    {
        dw->r = dw->r | (1<<(63-ix));
    }
}
void reset_dword_bit(dword *dw, int ix)
{
    assert(ix >= 0 && ix < 64);
    if(ix < 32)
    {
        dw->l = dw->l & (~(1<<(31-ix)));
    }
    else
    {
        dw->r = dw->r & (~(1<<(63-ix)));
    }
}
dword expansion(int *EV, int e_len, word in)
{
    dword out;
    out.l = 0;
    out.r = 0;
    int i;
    for(i = 0; i < e_len; i++)
    {
        if(get_word_bit(in, EV[i] - 1))
        {
            set_dword_bit(&out, i);
        }
        else
        {
            reset_dword_bit(&out, i);
        }
    }
    return out;
}
dword permutate(int *PV, int p_len, dword in)
{
    dword out;
    out.l = 0;
    out.r = 0;
    int i;
    for(i = 0; i < p_len; i++)
    {
        if(get_dword_bit(in, PV[i] - 1))
        {
            set_dword_bit(&out, i);
        }
        else
        {
            reset_dword_bit( &out, i);
        }
    }
    return out;
}
byte s_box(int s_ix, byte in)
{
    byte out;
    int row = 0, col = 0;
    row |= get_byte_bit(in, 0);
    row = row << 1;
    row |= get_byte_bit(in, 5);
    col = in;
    col &= 0x78; // bit mask: 0111 1000
    col = col >> 3;
    out = S[s_ix][row][col];
    out = out << 4;
    return out;
}
word substitute(dword in)
{
    word out = 0x00000000;
    byte b, sout;
    int i,j;
    for(i = 0; i < 8; i++)
    {
        b = 0x00;
        for(j = 0; j < 6; j++)
        {
            b = b << 1;
            b |= get_dword_bit(in, 6 * i + j);
        }
        b = b << 2;
        sout = s_box(i, b);
        //printf("In Substitute: s_box(%d, %02X)=%02X\n", i, b, sout);
        sout = sout >> 4;
        out = out << 4;
        out |= sout;
    }
    return out;
}
dword left_rotate_28_28(dword key56, int nor)
{
    assert(nor >= 0 && nor <= 4);
    dword out;
    out.l = 0;
    out.r = 0;
    word l28, r28;
    byte l04 = 0x00, r04 = 0x00;
    l28 = key56.l;
    l28 &= 0xFFFFFFF0;
    l04 = l28 >> 28;
    l28 |= l04;
    l28 = l28 << nor;
    l28 &= 0xFFFFFFF0;
    out.l = l28;
    r04 = key56.l & 0x0000000F;
    r28 = r04;
    r28 = r28 << 28;
    r28 |= key56.r >> 4;
    r28 |= r04;
    r28 = r28 << nor;
    r28 &= 0xFFFFFFF0;
    out.l |= r28 >> 28;
    out.r = r28 << 4;
    return out;
}
dword *gen_subkeys(dword key)
{
    dword *subkeys = (dword *)malloc(sizeof(dword)*16);
    dword key_PC1, iter_key;
    int i, nor;
    key_PC1 = permutate(PC1, 56, key);
    iter_key = key_PC1;
    for(i=0;i<16;i++)
    {
        nor = ROTATIONS[i];
        iter_key = left_rotate_28_28(iter_key, nor);
        subkeys[i] = permutate(PC2, 48, iter_key);
    }
    return subkeys;
}
word feistel(word in, dword subkey)
{
    dword in_E, in_E_xor_subkey, after_S_dword, dout;
    word after_S, out;
    in_E = expansion(E, 48, in);
    in_E_xor_subkey.l = in_E.l ^ subkey.l;
    in_E_xor_subkey.r = in_E.r ^ subkey.r;
    after_S = substitute(in_E_xor_subkey);
    after_S_dword.l = after_S;
    after_S_dword.r = 0;
    dout = permutate(P, 32, after_S_dword);
    out = dout.l;
    return out;
}
dword encrypt_dword(dword in, dword *subkeys)
{
    dword in_IP;
    dword out;
    word temp, ft;
    int i;
    in_IP = permutate(IP, 64, in);
    out.l = in_IP.r;
    out.r = in_IP.l;
    for(i = 0; i < 16; i++)
    {
        temp = out.l;
        out.l = out.r;
        out.r = temp;
        ft = feistel(out.r, subkeys[i]);
        out.l = out.l ^ ft;
    }
    out = permutate(FP, 64, out);
    return out;
}
char *encrypt(char *pt, dword key)
{
    unsigned char *ct, *curr_pt, temp[9], *curr_ct;
    dword *subkeys;
    dword pt_unit, ct_unit;
    int i;
    subkeys = gen_subkeys(key);
    ct = (char *)malloc(sizeof(pt)+1);
    curr_ct = ct;
    curr_pt = pt;
    while(*curr_pt != '\0')
    {
        if(strlen(curr_pt) >= 8)
        {
            pt_unit.l = 0;
            for(i = 0; i < 4; i++)
            {
                pt_unit.l = pt_unit.l << 8;
                pt_unit.l |= *curr_pt;
                curr_pt++;
            }
            pt_unit.r = 0;
            for(i = 0; i < 4; i++)
            {
                pt_unit.r = pt_unit.r << 8;
                pt_unit.r |= *curr_pt;
                curr_pt++;
            }
        }
        else
        {
            pt_unit.l = 0;
            for(i = 0; i < 4; i++)
            {
                if(*curr_pt == '\0')
                {
                    pt_unit.l = pt_unit.l << (8 * (4 - i));
                    break;
                }
                pt_unit.l = pt_unit.l << 8;
                pt_unit.l |= *curr_pt;
                curr_pt++;
            }
            for(i = 0; i < 4; i++)
            {
                if(*curr_pt == '\0')
                {
                    pt_unit.r = pt_unit.r << (8 * (4 - i));
                    break;
                }
                pt_unit.r = pt_unit.r << 8;
                pt_unit.r |= *curr_pt;
                curr_pt++;
            }
        }
        ct_unit = encrypt_dword(pt_unit, subkeys);
        *curr_ct = (ct_unit.l & 0xFF000000) >> 24;
        curr_ct++;
        *curr_ct = (ct_unit.l & 0x00FF0000)>>16;
        curr_ct++;
        *curr_ct = (ct_unit.l & 0x0000FF00)>>8;
        curr_ct++;
        *curr_ct = ct_unit.l & 0x000000FF;
        curr_ct++;
        *curr_ct = (ct_unit.r & 0xFF000000)>>24;
        curr_ct++;
        *curr_ct = (ct_unit.r & 0x00FF0000)>>16;
        curr_ct++;
        *curr_ct = (ct_unit.r & 0x0000FF00)>>8;
        curr_ct++;
        *curr_ct = ct_unit.r & 0x000000FF;
        curr_ct++;
    }
    curr_ct = '\0';
    return ct;
}
void test()
{
    int i;
    byte b = 0xFF;
    dword in, out, got_out, got_inv, subkey, key, *subkeys;
    unsigned char *ptext, *ctext;
    word win, wout, wout2;
    dword pt,ct;
    in.l = in.r = out.l = out.r = 0;
    set_dword_bit(&in, 1);
    assert(b == 0xFF);
    assert(in.l == 0x40000000);
    set_dword_bit(&in, 45);
    set_dword_bit(&in, 46);
    assert(in.l == 0x40000000 && in.r == 0x00060000);
    reset_dword_bit(&in, 45);
    assert(in.l == 0x40000000 && in.r == 0x00020000);
    
    set_dword_bit(&out, 7);
    set_dword_bit(&out, 58);
    got_out = permutate(IP, 64, in);
    /*
    printf("got_out: %016X - %016X\n", got_out.l, got_out.r);
    printf("out:     %016X - %016X\n", out.l, out.r);
    */
    assert(got_out.l == out.l && got_out.r == out.r);
    
    got_inv = permutate(FP, 64, got_out);
    assert(got_inv.l == in.l && got_inv.r == in.r);
    /*
    for(i = 0; i < 31; i++)
    {
        assert(get_dword_bit(in,i) == 0);
    }
    for(i = 32; i < 64; i++)
    {
        assert(get_dword_bit(in,i) == 0);
    }
    */
    /*
    // Testing substitute function
    in.l = 0x01234567;
    in.r = 0x89AB0000;
    assert(substitute(in)==0xE76B31DA);
    assert(s_box( 0, 0x54)==0xC0); //in: 0101 0100
    */
    /*
    // Testing left_rotate_28_28 function
    in.l = 0x01234567;
    in.r = 0x89ABCD00;
    out.l = 0x048D158E;
    out.r = 0x26AF3500;
    got_out = left_rotate_28_28(in,2);
    assert(got_out.l == out.l && got_out.r == out.r);
    */
    /*
    // Testing feistel function
    win = 0x12345678;
    subkey.l = 0x9ABCDEF0;
    subkey.r = 0x12340000;
    wout = 0x7AFDB75C;
    wout2 = feistel(win, subkey);
    printf("wout: %08X\nwout2: %08X", wout, wout2);
    assert(wout == wout2);
    printf("Passed all tests!!!\n");
    */
    /*
    // Testing gen_subkeys function
    key.l = 0x31323334;
    key.r = 0x35363738;
    gen_subkeys(key);
    */
    
    // Testing encrypt_dword function
    key.l = 0x31323334;
    key.r = 0x35363738;
    pt.l = 0x61626364;
    pt.r = 0x65666768;
    ct = encrypt_dword(pt, gen_subkeys(key));
    printf("Ciphertext: %08X%08X\n", ct.l, ct.r);

    // Testing encrypt function
    key.l = 0x31323334;
    key.r = 0x35363738;
    ptext = "abcdefghijklmn"; 
    ctext = encrypt(ptext, key);
    printf("Ciphertext: ");
    for(i = 0; i < strlen(ctext); i++)
        printf("%02X", ctext[i]);
    printf("\n");
    printf("Passed all tests!!!\n");
}