/**************************************************
* sBoxGenerate.c - Generates DES-like S-boxes      
*                                                  
* Jason Friedman (jason@wisdom.weizmann.ac.il)     
* 8.9.00                                           
***************************************************/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

/* Macro to convert from DES input number to array entry number */
/* A macro was used rather than a function for efficiency */
#define lookup(x)  current[(((x&32)>>5)*2+(x&1))*16+((x&30)>>1)]

/* Forward function declarations */

/* Creates a (random) permutation that is an S-box row that satisfies 
S-3, S-4 and S-5 */
char* makeRandomRow();		

/* Builds a pair of rows (could be used as rows 1 and 3, or 2 and 4, that 
satisfy S-6 (as well as S-4 and S-5), and S9 and S10 depending on the 
arguments */
char* buildPair(int checkS9, int checkS10); 

/* Generates a difference distribution table */
int generateDiffTable(char sbox[]); 

/* Prints the difference distribution table in LaTex format */
void printDiffTable();      

/* Checks if a row satisfies S-4 */
int checkS4row(int set, char current[]);	

/* Checks if the S-box satisfies S4*/
int checkS4(char current[]);  

/* Checks if a row satisfies S-5 */
int checkS5row(int set, char current[]);	

/* Checks if a DDT satisfies S-6 */
int checkS6table(void);	     

/* Checks that the second row in a pair (of row 1&3 or 2&4) satisfy S6 */
int checkS6secondRow(int set, char pair[]);     

/* Checks if a DDT satisfies S-7 */
int checkS7table(void);	     

/* Checks if a DDT satisfies S-8 */
int checkS8table(void);	     

/* Checks if a DDT satisfies S-9 */
int checkS9table(void);	     

/* Checks that the second row in a pair (of row 1&3 or 2&4) satisfy S-9 */
int checkS9secondRow(int set, char pair[]);     

/* Checks if a DDT satisfies S-10 */
int checkS10table(void);
 
/* Checks that the second row in a pair (of row 1&3 or 2&4) satisfy S-10 */
int checkS10secondRow(int set, char pair[]);    

/* Converts the value from array to DES number */
int findval(int input);	     

/* Tests for the patter 0110 */
int pattern0110(int test1,int test2); 	

/* Checks that 70% of the DDT is non-zero entries */
int checkNonZero(void);		

char table[64][16]; // DDT globally defined (to save it being passed around)


int main(int argc, char *argv[]) {

int selected, selected2;
char *result,*result2;
char **results;
char *pair;
char test[64];
long int count;
int i,j;
int found,giveup;
long int checked=0;
int laststage=0;
long int size;
int checkS9=0, checkS10=0;
int numberToGenerate;
int generated=0;
char *temp;

/* Check / assign the command line arguments */
if(argc<3) {
	printf("usage: %s <size of database> <number to generate> [9] [10]\n",argv[0]);
	exit(1);
	}
else {
	size = atoi(argv[1]);
	numberToGenerate = atoi(argv[2]);
	if(atoi(argv[3])==9) checkS9=1;
	if(atoi(argv[3])==10||atoi(argv[4])==10) checkS10=1; 
	}

printf("Building a database of size %ld\n",size);
if(checkS9) printf("Checking S-9\n");
if(checkS10) printf("Checking S-10\n");

/* Pick a random seed */
srand((unsigned int)time((time_t *)NULL));

/* Allocate (lots) of memory */
results = (char**)malloc(sizeof(char*)*size);
pair = (char*)malloc(sizeof(char)*32);
count=0;

STEP1: /* Create a database of pairs that satisfy S3-S6 
	  (and possible S9-10) */
do {
	result = buildPair(checkS9, checkS10);
	results[count]=result;
	count++;
	if(count%1000==0) 
		printf("Finished %d of %d\n",count,size);
	} while(count<size);

STEP2: /* Combine the pairs, checking if the full S-box satisfies (S-4) */
if(checked%100==0) printf("Checked %d pairs, laststage = %d\n",checked,laststage);
found=0;
do {
	selected=rand()%size;
	selected2=rand()%size;

	for(i=0;i<16;i++) {
		test[i]=results[selected][i];
		test[16+i]=results[selected2][i];
		test[32+i]=results[selected][i+16];
		test[48+i]=results[selected2][i+16];
		}
	if(checkS4(test))
		found=1;
} while(!found);
		if(laststage<2) laststage=2;


STEP3: /* Generate a difference distribution table */
if(generateDiffTable(test))  {
	if(laststage<3) laststage=3;}
else {checked++;goto STEP2;}


STEP4: /* Now check S7. If it fails, return to Step 2 */
 if(!checkS7table()) { checked++; goto STEP2; }
	else {
		if(laststage<4) laststage=4;
		printf("Passed S7\n"); } 

STEP5: /* Check s2. If it fails return to step 2 */
if(!checkS2(test)) { checked++; goto STEP2; }
	else {
		if(laststage<5) laststage=5;
//		printf("Passed S2\n"); 
		}

STEP6: /* Check s8. If it fails return to step 2 */
if(!checkS8table()) { checked++; goto STEP2; }
	else {
		if(laststage<6) laststage=6;
		printf("Passed S8\n"); }


/* If it passes all the tests, it is a valid S-box, so print it out */

 	for(i=0;i<64;i++) {
		printf("%d ",test[i]);
		if(i%16==15) printf("\n"); }
	printf("\n");  

printf("This S-box satisfies S-1\n");
printf("This S-box %s S-2 (maximum NS value = %d)\n",(checkS2(test)?"satisfies":"does not satisfy"),checkS2(test)); 
printf("This S-box satisfies S-3\n");
printf("This S-box %s S-4\n",(checkS4table()?"satisfies":"does not satisfy")); 
printf("This S-box %s S-5\n",(checkS5table()?"satisfies":"does not satisfy")); 
printf("This S-box %s S-6\n",(checkS6table()?"satisfies":"does not satisfy")); 
printf("This S-box %s S-7\n",(checkS7table()?"satisfies":"does not satisfy")); 
printf("This S-box %s S-8\n",(checkS8table()?"satisfies":"does not satisfy")); 
printf("This S-box %s S-9\n",(checkS9table()?"satisfies":"does not satisfy")); 
printf("This S-box %s S-10\n",(checkS10table()?"satisfies":"does not satisfy"));
printf("Non-zero percentage is %d\n",findNonZero());
printf("Maximum difference between 0s/1s for a fixed bit = %d\n",findMaxDiff(test));

generated++;

if(generated<numberToGenerate) goto STEP2;

END: 
/* Free the memory used */
for(count=0;count<size;count++) {
	free(results[i]); }
free(results);
return 0;
}

/*************************************************
* char* buildPair(int checks9, int checkS10)      
* Builds a pair of rows (could be used as rows    
* 1 and 3, or 2 and 4, that satisfy S-6 (as well  
* as S-4 and S-5) and depending on the arguments  
* S9 and S10                                      
*                                                 
* inputs - checkS9, checkS10 - flags as to whether
*          to check for these                     
* output - pointer to array of char[32]           
**************************************************/

char* buildPair(int checkS9, int checkS10) {

char unused[16];
char* result;
char* returnValue; 
char* temp;
int i;
int set;
int giveup;
int position;

returnValue = (char*)malloc(sizeof(char)*32); // Allocate memory

VERYSTART:
/* Create the first row */
result = makeRandomRow();

/* Copy the data and free the memory */
for(i=0;i<16;i++) returnValue[i]=result[i];
free(result);

START:	
	for(i=0;i<16;i++)
		unused[i]=i;
	set=0; giveup=0;

	/* Add numbers one by one such that it is a permutation, and that S4, S5 and S6
       are satisfied */
	do{	
		if(giveup>=200) goto START;
		position=rand()%(16-set);
		returnValue[set+16]=unused[position];
		temp = &returnValue[16];
		if(checkS4row(set,temp)&&
		   checkS5row(set,temp)&&
           checkS6secondrow(set,returnValue)&&
		   (!checkS9||checkS9secondrow(set,returnValue))&&
		   (!checkS10||checkS10secondrow(set,returnValue))) {
		unused[position]=unused[15-set];
		set++;
		}
	else giveup++;
	}while(set<16);
	if(generatePartDiffTable(returnValue))
		return returnValue;
	else 
		goto VERYSTART;
}	

/*************************************************
* char* makeRandomRow()                           
* Builds a pair of rows (could be used as rows    
* 1 and 3, or 2 and 4, that satisfy S-6 (as well  
* as S-4 and S-5                                  
*                                                 
* output - pointer to array of char[16]           
**************************************************/

char* makeRandomRow() {
	char unused[16];
	char *result;
	int i;
	int set;
	int giveup;
	int position;
	result = (char*)malloc(sizeof(char)*16);
START:	
	for(i=0;i<16;i++)
		unused[i]=i;
	set=0; giveup=0;
	
   /* Add numbers one by one such that it is a permutation, and that S4 and S5
      are satisfied. If no number can be added, it gives up, and starts from
      scratch */

	do{	
	if(giveup>=40) goto START;
	position=rand()%(16-set);
	result[set]=unused[position];
	if(checkS4row(set,result)&&checkS5row(set,result)) {
		unused[position]=unused[15-set];
		set++;
		giveup=0;
		}
	else giveup++;
	}while(set<16);
return result;
}

/*************************************************
* int checkS2(char current[])                     
*                                                 
* This checks design criteria (S-2) for the entire
* s-box, by checking NS_a(\alpha,\beta) for the   
* table as per Matsui                             
*                                                 
* current = array of s-box data                   
* return max NS value if satisfies / 0 otherwise  
**************************************************/

int checkS2(char current[]) {
	int currentmax = 0;
	int LHS, RHS;
	int alpha, beta,x;
	int count;

	for(alpha=1;alpha<=63;alpha++) {	
		for(beta=1;beta<=15;beta++) {	
			count=0;
			for(x=0;x<=63;x++) {	
				LHS = ((x&alpha&1)?1:0) + 
				      ((x&alpha&2)?1:0) +
				      ((x&alpha&4)?1:0) +
				      ((x&alpha&8)?1:0) + 
				      ((x&alpha&16)?1:0) + 
				      ((x&alpha&32)?1:0); 
				RHS = ((current[x]&beta&1)?1:0) + 
				      ((current[x]&beta&2)?1:0) +
				      ((current[x]&beta&4)?1:0) +
				      ((current[x]&beta&8)?1:0); 

				/* Check if the parity is the same */
				if (LHS%2 == RHS%2) {
					count++; }
				}
			if (abs(count-32)>currentmax) 
				{currentmax=count-32;}
			}
		}
// printf("Maximum value is %d ", currentmax);
	
	if(currentmax>20)
		return 0;
else
	return currentmax;
}

/*************************************************
* int differ(int bits, int input1, int input2)     
*                                                  
* This calculates the number of bits in which two 
* numbers differ                                  
*                                                  
* bit = number of bits to compare,                
* input[1,2] = inputs                              
* return the next of bits different                
**************************************************/

int differ(int bits, int input1, int input2) {
	int result;
	int diff=0;
	int i;

	result = input1^input2;
	for(i=0;i<bits;i++) {
	   	diff += ((result - ((result >> 1)<<1))?1:0);
		result = result >> 1;
	}
	return diff;
}

/*************************************************
* int checkS4extrarow(int row, char current[])    
*                                                   
* This checks design criteria (S-4) by            
* checking that the extra row satisfies the rule  
* with the current rows. As only bit bit is diff  
* then this bit can only be the first or last, so 
* it is enough to just check that those in the    
* same column are not the same                    
*                                                   
* row = row number(1-3) (0 would be useless)        
* current = array with s-box data                   
* return 1 if satisfies / 0 if not                
**************************************************/
			
int checkS4extrarow(int row, char current[]) {
	int i;
	char new;

	for(i=0;i<16;i++) {
		new= current[row*16+i]; 
		switch(row) {
			case 1:	if(differ(4,current[i],new)<=2)
					return 0;
				break;
			case 2: if(differ(4,current[i],new)<=2)
					return 0;
				break;
			case 3: if((differ(4,current[16+i],new)<=2)||
				   (differ(4,current[32+i],new)<=2))
					return 0;
				break;
			}
			
	}
	return 1;
}

/*************************************************
* int checkS4row(int set, char current[])         
*                                                   
* This checks design criteria (S-4) by            
* ensuring that if the two inputs have a one      
* bit input difference, the output difference     
* will be at least 2 bits                         
*                                                   
* set = last set bit in array                       
* current = array with s-box data                   
* return 1 if satisfies / 0 if not                
**************************************************/
			
int checkS4row(int set, char current[]) {
	int i;
	int input1, input2, output1, output2;

		input1=set;
		output1=current[set];

	for(i=0;i<set;i++) {
		input2=i;
		output2=current[i];

    // check if  ! ((input diff = 1) => (output differ >=2))

	if((differ(4,input1,input2)==1)&&!(differ(4,output1,output2)>=2))
		 return 0;	
	}
	return 1;
}

/*************************************************
* int checkS4(char current[])                     
*                                                 
* This checks design criteria (S-4) for           
* the entire S-box                                
*                                                 
* current = array of sbox data                    
* return 1 is satisfies / 0 if not                
**************************************************/

int checkS4(char current[]) {
	int i;

	for(i=0;i<63;i++) {
		if( 
		!(differ(4,current[findval(i^32)],current[findval(i)])>=2)||
		!(differ(4,current[findval(i^16)],current[findval(i)])>=2)||
		!(differ(4,current[findval(i^8)],current[findval(i)])>=2)||
		!(differ(4,current[findval(i^4)],current[findval(i)])>=2)||
		!(differ(4,current[findval(i^2)],current[findval(i)])>=2)||
		!(differ(4,current[findval(i^1)],current[findval(i)])>=2))
				 return 0;	
	}
	return 1;
}

/*************************************************
* int checkS4table()                              
*                                                 
* This checks design criteria (S-4) by            
* looking at the appropriate locations in the     
* difference distribution table                   
**************************************************/

int checkS4table() {
        int onebitin[6] = {1,2,4,8,16,32};
        int onebitout[5] = {0,1,2,4,8};
		int i,j;

        for(i=0;i<6;i++) {
			for(j=0;j<5;j++) {
            	if (table[onebitin[i]][onebitout[j]]>0) {
                         return 0; }
                }
            }
        return 1;
}

/*************************************************
* int checkS5row(int set, char current[])         * 
*                                                 
* This checks design criteria (S-5) for (parts of)
* a row, checking the last added element with     
* those already present                           
*                                                 
* set = last element added,                       
* current = array of s-box data                   
* return 1 if satisfies / 0 if not                
**************************************************/

int checkS5row(int set, char current[]) {
	int i;
	int input1, input2, output1, output2;

		input1=set;
		output1=current[set];

	for(i=0;i<set;i++) {
		input2=i;
		output2=current[i];

	    //check if  ! ((input diff = 0110 ) => (output differ >=2))
		if((pattern0110(input1, input2))&&!(differ(4,output1,output2)>=2))
		 return 0;	
	}
	return 1;
}


/*************************************************
* int checkS5table()                              
*                                                 
* This checks design criteria (S-5) by            
* looking at the appropriate locations in the     
* difference distribution table                   
**************************************************/

int checkS5table() {
        int diffin = 12;
        int onebitout[5] = {0,1,2,4,8};
		int i;

        for(i=0;i<5;i++) {
                if (table[diffin][onebitout[i]]>0) {
                        return 0; }
                }
        return 1;
        }

/*************************************************
* int checkS6table()                              
*                                                 
* This checks design criteria (S-6) by            
* looking at the appropriate locations in the     
* difference distribution table                   
**************************************************/

int checkS6table() { 

		if (table[48][0]>0||table[52][0]>0||table[56][0]>0||table[60][0]>0) 
			return 0; 
		else 
			return 1;
}

/*************************************************
* int checkS6secondRow(int set, char pair[])      
*                                                 
* This checks design criteria (S-6) for a full row
* and part of a second row (that could be 1 and 3,
* or 2 and 4)                                     
**************************************************/

int checkS6secondrow(int set, char pair[]) {
	int i;
	int diff;
	for(i=0;i<15;i++) {
		diff=set^i;
		if((diff==8||diff==10||diff==12||diff==14)&&(pair[i]==pair[set+16]))
			return 0; 
		}
	return 1;	
}	

/*************************************************
* int checkS7table(void)                          
*                                                 
* This checks design criteria (S-7) by            
* looking at the appropriate locations in the     
* difference distribution table                   
**************************************************/

int checkS7table(void) {
	int input, output;

	for(input=1;input<=63;input++) {
		for(output=0;output<=15;output++) {
			if (table[input][output]>20) {
				return 0;
				}
		}
	}
	return 1;
}

/*************************************************
* int checkS8table(void)                          
*                                                 
* This checks design criteria (S-8) by            
* looking at the appropriate locations in the     
* difference distribution table                   
**************************************************/

int checkS8table(void) {

/* for the inputs that make up the 3-active S-box iterative pattern
   (ie 00xy11, 11xy10, 10xy00) make sure that probability of zero 
   output is not too high */

	if (table[ 3][0]>14||table[ 7][0]>14||
	    table[11][0]>14||table[15][0]>14||

	    table[50][0]>14||table[54][0]>14||
	    table[58][0]>14||table[62][0]>14||

	    table[32][0]>14||table[36][0]>14||
	    table[40][0]>14||table[44][0]>14) 
		return 0;
	else
		return 1;
}

/*************************************************
* int checkS9table()                              
*                                                 
* This checks design criteria (S-9) by            
* looking at the appropriate locations in the     
* difference distribution table                   
**************************************************/

int checkS9table() { 

		if (table[50][0]>0||table[54][0]>0||table[58][0]>0||table[62][0]>0) 
			return 0; 
		else 
			return 1;
}

/*************************************************
* int checkS9secondRow(int set, char pair[])      
*                                                 
* This checks design criteria (S-9) for a full row
* and part of a second row (that could be 1 and 3,
* or 2 and 4)                                     
**************************************************/

int checkS9secondrow(int set, char pair[]) {
	int i;
	int diff;
	for(i=0;i<15;i++) {
		diff=set^i;
		if((diff==9||diff==11||diff==13||diff==15)&&(pair[i]==pair[set+16]))
			return 0; 
		}
	return 1;	
}

/*************************************************
* int checkS10table()                             
*                                                 
* This checks design criteria (S-10) by           
* looking at the appropriate locations in the     
* difference distribution table                   
**************************************************/

int checkS10table() { 

		if (table[34][0]>0||table[38][0]>0||table[42][0]>0||table[46][0]>0) 
			return 0; 
		else 
			return 1;
}

/**************************************************
* int checkS10secondRow(int set, char pair[])      
*                                                  
* This checks design criteria (S-10) for a full row
* and part of a second row (that could be 1 and 3, 
* or 2 and 4)                                      
***************************************************/

int checkS10secondrow(int set, char pair[]) {
	int i;
	int diff;
	for(i=0;i<15;i++) {
		diff=set^i;
		if((diff==1||diff==3||diff==5||diff==7)&&(pair[i]==pair[set+16]))
			return 0; 
		}
	return 1;	
}		

/*************************************************
* int findval(int input)                          
*                                                    
* This converts a number from the array entry     
* into the number used by DES to access that       
* element                                         
*                                                    
* input = array entry                                
* return the number used by DES                      
**************************************************/

int findval(int input) {

	int row, col;

	row = input/16;
	col = input%16;

	return	((col << 1) | (row&1) | ((row&2)<<4));

	}

/*************************************************
* int pattern0110(int test1,int test2)            
*                                                    
* Tests if the difference between the inputs has  
* the pattern 0110                                   
* test1, test2 = inputs                           
* return 1 if the pattern holds, 0 otherwise      
**************************************************/

int pattern0110(int test1,int test2) {

	int test;
	test = test1^test2;
	if(test&2 && test&4 && !(test&1) && !(test&8)) 
		return 1; 
	else
		return 0;
	}

/*************************************************
* void generatePartDiffTable(char current[])       
*                                                 
* This generates part of a difference distribution
* table from the S-box data                       
*                                                 
* current = array of sbox data                     
**************************************************/

int generatePartDiffTable(char current[]) {

int i,j;
int input,output;

/* Clear the table */
for(i=0;i<64;i++) { 
  for(j=0;j<16;j++) {
		table[i][j]=0; }}

for(i=0;i<32;i++) { 
  for(j=i+1;j<32;j++) {
  	input = findval(i)^findval(j);
	output= current[i]^current[j];
    table[input][output]+=2;
	if(table[input][output]>14) {
//		printf("failed with [%d][%d]=%d\n",input,output,table[input][output]); 
	return 0;}
    } 
  }
//	table[0][0]=64;
	return 1;
}
/*************************************************
* void generateDiffTable(char current[])           
*                                                 
* This generates a difference distribution table  
* from the S-box data                             
*                                                 
* sbox = array of sbox data                  
**************************************************/

int generateDiffTable(char current[]) {

int i,j;
int input,output;

/* Clear the table */
for(i=0;i<64;i++) { 
  for(j=0;j<16;j++) {
		table[i][j]=0; }}

for(i=0;i<64;i++) { 
  for(j=i+1;j<64;j++) {
  	input = findval(i)^findval(j);
	output= current[i]^current[j];
    table[input][output]+=2;
	if(table[input][output]>20) return 0;
    }			  
  }
	table[0][0]=64;
	return 1;
}

/*************************************************
* void printDiffTable()                           
*                                                 
* This prints the difference distribution table   
* in LaTex format                                 
**************************************************/
void printDiffTable () {
	int i,j;
	printf("\\begin{table}\n\\begin{tiny}\n\\begin{tabular}{|c|cccccccccccccccc|}\n");
	printf("\\hline\n");
	printf(" &  $0_x$  &  $1_x$  &  $2_x$  &  $3_x$  &  $4_x$  &  $5_x$  &
$6_x$  &  $7_x$  &  $8_x$  &  $9_x$  &  $a_x$  &  $b_x$  &  $c_x$  &  $d_x$  &
$e_x$  &  $f_x$\\\\\n");
	printf("\\hline\n");
	for(j=0;j<64;j++) {
              printf("$%hx_x$ &",j);
              for(i=0;i<15;i++)
                      printf("%d & ",table[j][i]);
              printf("%d",table[j][15]);
              printf("\\\\\n"); }
	printf("\\hline\n\\end{tabular}\n\\caption{The difference Distribution Table}\n\\end{tiny}\n\\end{table}\n");

}

/***********************************************
* int findNonZero(void)                         
*                                               
* Finds the  non-zero entry percentage          
************************************************/

int findNonZero(void) {
	int input, output, count=0;

	for(input=1;input<=63;input++) {
		for(output=0;output<=15;output++) {
			if (table[input][output]>0) 
				count++;
				
		}
	}
	return (count*100)/(63*16);
}

int findMaxDiff(char current[]) {
	int i,j;
	int currentBit;
	int a;
	int val,result;
	int count0,count1;
	int max=-100, min=100;

	for(currentBit=0;currentBit<6;currentBit++) {
		for(a=0;a<=1;a++) {
		for(j=0;j<32;j++) {
			switch(currentBit) {
			case 0: val=(a<<5)|(j&31);break;
			case 1:	val=((j&16)<<1)|(a<<4)|(j&15);break;
			case 2:	val=((j&24)<<1)|(a<<3)|(j&7);break;
			case 3:	val=((j&28)<<1)|(a<<2)|(j&3);break;
			case 4:	val=((j&30)<<1)|(a<<1)|(j&1);break;
			case 5:	val=(j<<1)|a;break;
			}
//		printf("currentBit=%d,a=%d,val=%d\n",currentBit,a, val);
		result = lookup(val);
		count0=0;count1=0;
		for(i=0;i<6;i++) {
			if(result&(1<<i)) count1++;
			else count0++;
			}
			if((count1-count0)<min) min=count1-count0;
			if((count1-count0)>max) max=count1-count0;
		}}
	}
	return max-min;

}