/*
 * The FEAL cipher - Linear Cryptanalysis
 */

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

/* uncomment this next statement to activate linear cryptanalysis code... */

/* #define DEBUG */

#define WORD32 unsigned int
#define BYTE   unsigned char

#define ROT2(x) (((x)<<2) | ((x)>>6))

#define S0(a,b) (ROT2((BYTE)((a)+(b))))
#define S1(a,b) (ROT2((BYTE)((a)+(b)+1)))

static WORD32 pack32(BYTE *b)
{ /* pack 4 bytes into a 32-bit Word */
    return ((WORD32)b[3]<<24)|((WORD32)b[2]<<16)|((WORD32)b[1]<<8)|(WORD32)b[0];
}

static void unpack32(WORD32 a,BYTE *b)
{ /* unpack bytes from a 32-bit word */
    b[0]=(BYTE)a;
    b[1]=(BYTE)(a>>8);
    b[2]=(BYTE)(a>>16);
    b[3]=(BYTE)(a>>24);
}

WORD32 f(WORD32 x,WORD32 key)
{
    BYTE f[4];
    BYTE k[4];

    unpack32(x,f);
    unpack32(key,k);

    f[2]^=(f[3]^k[2]);
    f[1]^=(f[0]^k[1]);
    f[2]=S1(f[2],f[1]);
    f[1]=S0(f[1],f[2]);
    f[3]=S0(f[3]^k[3],f[2]);
    f[0]=S1(f[0]^k[0],f[1]); 

/* printf("%02x%02x%02x%02x\n",f[3],f[2],f[1],f[0]); */
    return pack32(f);
}

/* H for High, L for Low */

void feal_encrypt(BYTE data[8],WORD32 *key)
{
    int i;
    WORD32 H,L,T;
    
    H=pack32(&data[4]);
    L=H^pack32(&data[0]);

    T=L;
    L=H^f(L,key[0]);
    H=T;

    T=L;
    L=H^f(L,key[1]);
    H=T;

    L^=key[4];
    H^=key[5]; 

    T=L;
    L=H^f(L,key[2]);
    H=T;

    T=L;
    L=H^f(L,key[3]);
    H=T;

    H^=L;

    unpack32(L,&data[4]);
    unpack32(H,&data[0]);
}

void feal_decrypt(BYTE data[8],WORD32 *key)
{
    int i;
    WORD32 H,L,T;

    L=pack32(&data[4]);
    H=L^pack32(&data[0]);
          
    T=H;
    H=L^f(H,key[3]);
    L=T;
    T=H;
    H=L^f(H,key[2]);
    L=T;

    L^=key[4];
    H^=key[5]; 

    T=H;
    H=L^f(H,key[1]);
    L=T;

    T=H;
    H=L^f(H,key[0]);
    L=T;

    L^=H;

    unpack32(H,&data[4]);
    unpack32(L,&data[0]);
}

int main(int argc,char **argv)
{
    int i,j,lhs,rhs;
    int Ph10161826,Pl101826,Ch10161826,Cl16,Ch16;
    BYTE input[10];
    BYTE data[8],k[4];
    WORD32 key[6],ph,pl,ch,cl,k1;
	BYTE bits[4096];
	int first_time_in=1;

/* DELETED - Secret key generator. Sets keys key[0] ... key[5] */

    key[1]=key[2]=key[3]=key[4]=key[5]=0;  /* not the real key ! */

	key[0]=0x2E3500; /* !! This is the first sub-key we find!    */

#ifndef DEBUG
    argc--; argv++;
    if (argc!=8)
    {
        printf("command line error - input 8 bytes of plaintext in hex\n");
        printf("For example:-\n");
        printf("findkey 0 1 2 3 4e 5a f6 37\n");
        return 0;
    }
    for (i=0;i<8;i++)
        sscanf(argv[i],"%x",&input[i]);
 
    for (i=0;i<8;i++) data[i]=input[7-i];

    printf("Plaintext=  ");
    for (i=7;i>=0;i--) printf("%02x ",data[i]);
    printf("\n");


    feal_encrypt(data,key);
    printf("Ciphertext= ");

    for (i=7;i>=0;i--) printf("%02x ",data[i]);
    printf("\n");

    feal_decrypt(data,key);

    printf("Plaintext=  ");
    for (i=7;i>=0;i--) printf("%02x ",data[i]);
    printf("\n");


#else
	for (i=0;i<8;i++) data[i]=(BYTE)rand();
	
/*
   the debug code below searches through all k1[8~13] and k1[16~21],
   as described by Matsui. That's 4096 possibilities. It outputs a 
   0 or a 1 for each possible key.

   For all known plaintexts/ciphertexts the right key will always give the
   same fixed 0 or 1

   For each plaintext/ciphertext pair newly discovered wrong keys 
   are replaced with an X
*/

/* Now try for 60 random plaintexts... */

 for (j=0;j<60;j++)
 {
    for (i=0;i<8;i++) data[i]=(BYTE)rand(); /* random plaintexts */

    printf("\nPlaintext=  ");
    for (i=7;i>=0;i--) printf("%02x ",data[i]);
    printf("\n");

    pl=pack32(&data[0]);
    ph=pack32(&data[4]);

    Ph10161826=((ph>>10)^(ph>>16)^(ph>>18)^(ph>>26))&1;     
    Pl101826  =((pl>>10)^(pl>>18)^(pl>>26))&1;

    feal_encrypt(data,key);
    printf("Ciphertext= ");
    for (i=7;i>=0;i--) printf("%02x ",data[i]);
    printf("\n");

    cl=pack32(&data[0]);
    ch=pack32(&data[4]);

    Ch10161826=((ch>>10)^(ch>>16)^(ch>>18)^(ch>>26))&1;
    Cl16=((cl>>16)&1);
    Ch16=((ch>>16)&1);

    for (i=0;i<4096;i++)
    {
       k[0]=0; k[1]=i&0x3F; k[2]=(i>>6)&0x3F; k[3]=0;
       k1=pack32(k);

       lhs=(Ph10161826^Pl101826^Ch10161826^Cl16^(f(ph^pl,k1)>>16))&1;   
	   
       if (first_time_in) bits[i]=lhs;
       else if (lhs!=bits[i]) bits[i]=0xFF;

    }

/* print out the 4096 bit array */

    for (i=0;i<4096;i++)
    {
        if (bits[i]==0xFF) 
        {
            printf("X");
            continue;
        }
        printf("%d",bits[i]);
    }

    first_time_in=0;

 }

 printf("\nCandidates for bits 8-13, and 16-21 of key[0] are\n");

 for (i=0;i<4096;i++)
 {
     if (bits[i]==0xFF) continue;
     k[0]=0; k[1]=i&0x3F; k[2]=(i>>6)&0x3F; k[3]=0;
     k1=pack32(k);
     printf("%x\n",k1);
 }

 printf("Actual key[0] we were looking for = %x\n",key[0]); 

#endif

    return 0;
}