#include <stdio.h>
#include <math.h>

int minBias = 0;
int maxBias = 0;

unsigned int plainText[20000];
unsigned int cipherText[20000];
unsigned short realKey;

unsigned int _rotl(unsigned short value, int shift) {
    shift &= 7;

    return (value << shift) | (value >> (8 - shift));
}


long power(int a, int x)
{
    long r = 1;
    int c;

    for(c = 0; c < x; c++)
        r *= a;

    return r;
}

int grabBit(long input, int bit)
{
    return ((input >> bit) & 1);
}

int setBit(int input, int bit)
{
    return input + power(2, bit);
}

int sboxFunction(int k, int a)
{
    int out = 0;

    return ((k + a) % 256);
}

int express[256][256];

void findExpressions()
{
    int c = 0;
    int d = 0;
    int e = 0;
    int f = 0;
    int g = 0;
    
    for (c = 0; c < 256; c++)
        for (d = 0; d < 256; d++)
            express[c][d] = 0;
    
    for (c = 1; c < 256; c++)                                   //Key Mask
    {   
        for (d = 1; d < 256; d++)                               //Output Mask
        {
            
            for (e = 0; e < 256; e++)                           //Input
            {
                
                int inputXor = 0;
                
                for (f = 0; f < 8; f++)
                    inputXor ^= grabBit(e, f);
                        
               
                for (g = 0; g < 256; g++)                       //Key
                {
                    
                    int keyXor = 0;
                    
                    for (f = 0; f < 8; f++)
                        if (grabBit(c, f))
                            keyXor ^= grabBit(g, f); 
                    
                    int output = sboxFunction(g, e);
                    int outputXor = 0;
                    
                    for (f = 0; f < 8; f++)
                        if (grabBit(d, f))
                            outputXor ^= grabBit(output, f); 
                    
                    if (outputXor == (keyXor ^ inputXor))
                        express[c][d]++;
                    else
                        express[c][d]--;
                    
                }
                
            }  
            
            
        }
    }
}



void findMinMaxBias()
{
    minBias = 0;
    maxBias = 0;

    int c, d;

    for(c = 1; c < 256; c++)
        for(d = 1; d < 256; d++)
        {
            if (express[c][d] < minBias) minBias = express[c][d];
            if (express[c][d] > maxBias) maxBias = express[c][d];

        }
}

void showExpression(int x, int y)
{
    int c, d;

    int first = 1;
    
    printf("%i  ", express[x][y]);
    
    for(c = 0; c < 8; c++)
        if (grabBit(x, c))
        {
            if (!first)
                printf(" + ");
            first = 0;            
            printf("%i");
        }
    printf(" = ");

    first = 1;
    
    for(c = 0; c< 8; c++)
        if (grabBit(y, c))
        {
            if (!first)
                printf(" + ");
            first = 0;  
            
            printf("%i");
        }
        

    printf("\n");

}

unsigned short getXorSum(int keyMask, unsigned short key)
{
    
    unsigned short xorKey = 0;
    
    int c;
    for(c = 0; c < 8; c++)
    {
        if (grabBit(keyMask, c))
            xorKey ^= grabBit(key, c);
        
    }
    
    return xorKey;
}

unsigned short splitLeft(unsigned int plain)
{
    return plain / 256;
}

unsigned short splitRight(unsigned int plain)
{
    return plain % 256;
}

unsigned int rc5Round(unsigned int plain, unsigned short key)
{
    unsigned int cipher = 0;
    
    unsigned short left = splitLeft(plain);
    unsigned short right = splitRight(plain);
    
    left ^= right;
    left = _rotl(left, right);
    left = (left + key) % 256;
    
    unsigned short temp = left;
    left = right;
    right = temp;
    
    cipher = (left * 256) + right;
    
    return cipher;
}

void generateData(int num)
{
    int c;
    
    realKey = rand() % 256;
    
    for(c = 0; c < num; c++)
    {
        plainText[c] = rand() % 65536;
        cipherText[c] = rc5Round(plainText[c], realKey);
        //printf("%i\n", plainText[c]);
    }
}

int findRightSide(int num)
{
    int c;
    
    int totalOnes = 0;
    
    for(c = 0; c < num; c++)
    {
        if (getXorSum(255, splitRight(plainText[c])) ^ getXorSum(255, splitLeft(plainText[c])) ^ getXorSum(255, splitRight(cipherText[c])))
            totalOnes++;
    }
    
    return totalOnes;
}

unsigned long realKeysChecked = 0;
int keyFound = 0;

void checkKeys(int a, short keyMask, int numPlain)
{
    
    int c, d;
    
    int keysChecked = 0;
    
    for(c = 0; c < 256; c++)
    {
        if (getXorSum(keyMask, c) == a)
        {
            int crap = 0;
            
            for (d = 0; d < numPlain; d++)
            {
                if (rc5Round(plainText[d], c) != cipherText[d])
                {
                    crap = 1;
                    break;
                }
                
                if (crap == 0)
                {
                    /*
                    printf("Key Found!  %i\n", c);
                    printf("Real key:  %i\n", realKey);
                    printf("Keys checked (real):  %i\n", keysChecked);
                    */
                    
                    realKeysChecked += keysChecked;
                    keyFound++;
                    break;
                }
            }
            keysChecked++;
        }
    }
    
    //printf("Theoretical Keys Checked %i\n", keysChecked);
}

int main()
{

    
    srand(time(NULL));
    
    int c;
    
    for(c = 0; c < 10000; c++)
    {
    
    generateData(20);
    
    
    int a = findRightSide(20);
    
    //printf("Right Side Ones = %i\n", a);
    
    if (a > 10) 
        a = 1;
    else
        a = 0;
    
    checkKeys(a, 255, 20);
    }
    
    printf("Total Keys Found = %i%%\n", keyFound/100);
    printf("Keys Checked Average when Found = %i/255\n", (realKeysChecked / keyFound));
    
    
    /*
    
    findExpressions();
    findMinMaxBias();
        
    int c = 0;
    int d = 0;
    
    for(c = 0; c < 256; c++)
        for(d = 0; d < 256; d++)
            if ((express[c][d] == minBias) || (express[c][d] == maxBias))
                showExpression(c, d);
    */
    
    
                
    return 0;
}