completed task6 nearly completly

just a few characters are still wrong in the key.
freqencies analysis has to be made more comprehensive

1 files changed, 138 insertions, 66 deletions

diff --git a/lib.c b/lib.c
index 252deb2..fc07022 100644
--- a/lib.c
+++ b/lib.c
@@ -6,6 +6,7 @@ static const unsigned char base64_encode[] =
 	"abcdefghijklmnopqrstuvwxyz"
 	"0123456789+/";
 
+
 static const unsigned char hex_encode[] =
 	"0123456789abcdef";
 
@@ -19,7 +20,6 @@ static int bit_on(char test, int bit)
 	char tmp;
 	tmp = 1 << bit;
 	tmp = test & tmp;
-	tmp = tmp >> bit;
 
 	return (int) tmp;
 }
@@ -29,7 +29,7 @@ static int bit_on(char test, int bit)
  * returns true if the given string contains only printable or whitespace
  * characters
  */
-static int isprintable(char *string, int length)
+int isprintable(char *string, int length)
 {
 	int i;
 
@@ -86,41 +86,74 @@ static void three_bytes_to_base64(char * encode, int bytes_to_print, char *resul
 		result[3] = ret[3];
 }
 
+void print_char_bit(char print)
+{
+	int i;
+	for(i=0;i<8;i++) {
+		if (bit_on(print,i))
+			printf("1");
+		else
+			printf("0");
+	}
+}
 /**
  * Transform four base64 encoded characters back to three bytes
  */
 
+const char decodeCharacterTable[256] = {
+	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
+	,-1,62,-1,-1,-1,63,52,53,54,55,56,57,58,59,60,61,-1,-1,-1,-1,-1,-1,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21
+	,22,23,24,25,-1,-1,-1,-1,-1,-1,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,-1,-1,-1,-1,-1,
+	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+	-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
+	,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+	-1,-1,-1
+};
+
+
 void decode_four_base64_byte(char *string1, char *result)
 {
-	char one, two, three, tmp;
+	char buf[4];
+
+	// map the bytes back to the orginial bitmap
+	// A = 0
+	buf[0] = decodeCharacterTable[(int)string1[0]];
+	buf[1] = decodeCharacterTable[(int)string1[1]];
+	buf[2] = decodeCharacterTable[(int)string1[2]];
+	buf[3] = decodeCharacterTable[(int)string1[3]];
+
 	// first byte is first six bits of base64 one and 2 bit of base64 second
-	one = string1[0] << 2;
-	one = one & 0xFC;
-	tmp = string1[1] >> 4;
-	tmp = tmp & 0x03;
-	one = one | tmp;
+	result[0] = ((buf[0] << 2) & 0xFC) | ((buf[1] >> 4) & 0x03);
 
 	// second byte 4 bits of second base64 + 4 bits of third base64
-	two = string1[1] << 4;
-	tmp = string1[2] >> 2;
-	two = two | tmp;
+	result[1] = ((buf[1] << 4) & 0xF0) | ((buf[2] >> 2) & 0x0F);
 
 	// third byte 2 bits of third base54 + 6 bits of fourth base64
-	three = string1[2] << 6;
-	tmp =  string1[3];
-	three = three | tmp;
-	
-	printf("%c%c%c", one, two, three);
+	result[2] = ((buf[2] & 0x03) << 6) | (buf[3] & 0x3F);
+
 }
 
-void decode_base64(char *string1, char *result)
+
+int decode_base64(char *string1, char *result)
 {
-	int i;
+	int i, j, padding;
+	
+	for(i=0, j=0;i<strlen(string1);i += 4, j +=3) {
+		decode_four_base64_byte(&string1[i], &result[j]);
+	}
 
-	for(i=0;i<strlen(string1)-3;i++) {
-		decode_four_base64_byte(&string1[i*4], &result[i*3]);
+	// handle padding in the last four bytes
+	i -= 4;
+
+	for(padding=0;i<strlen(string1);i++) {
+		if (string1[i] == '=')
+			padding++;
 	}
-	// TODO handle = in base64 at the end
+
+	result[j-padding] = '\0';
+
+	return (j-padding);
+
 }
 
 static char string_to_hex_map[] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06,
@@ -237,18 +270,17 @@ void xor_string(char *str1, char *key, char *result, int length_key, int length_
  */
 void hex_binary_to_string(char *str1, char *result, int length)
 {
-	int i;
-	int tmp = 0;
+	int i, j, tmp = 0;
 
-	for(i=0;i<length/2;i++) {
+	for(i=0,j=0;i<length;i++, j+=2) {
 		tmp = str1[i] & 0xF0;
 		tmp = tmp >> 4;
-		result[i*2] = hex_encode[tmp];
+		result[j] = hex_encode[tmp];
 		tmp = str1[i] & 0x0F;
-		result[(i*2)+1] = hex_encode[tmp];
+		result[j+1] = hex_encode[tmp];
 	}
 
-	result[i*2] = '\0';
+	result[j] = '\0';
 }
 
 /**
@@ -270,30 +302,70 @@ int decode_hex_string(char *encode, char* result)
  * total number of characters
  * @param string string where the frequent characters should be counted
  * @param length length of string
- * @return number between 0 and 100 (percentage) of frequent characters
  */
 
-static int score_based_on_frequent_characters(char *string, int length)
+static int frequent_histogramm_matchs(char *string, int length)
 {
-	int number = 0;
 	int i;
+	int hits = 0;
 	char tmp;
+	int number_frequent_characters[10] = { 0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0};
+	// a e h i n o r s t u
+	double standard_frequencies[10] = { 8.1, 12.7, 6.0, 6.9, 6.7, 7.5, 5.9, 6.3, 9.0, 2.7 };
 
+	// count frequent characters
 	for(i=0;i<length;i++) {
 		tmp = tolower(string[i]);	
-		if( tmp == 'e' || tmp == 'a' || tmp == 'i' || tmp == 'o'
-			|| tmp == 'u' )
-			number++;
+		switch(tmp) {
+			case 'a':
+				number_frequent_characters[0]++;
+				break;
+			case 'e':
+				number_frequent_characters[1]++;
+				break;
+			case 'h':
+				number_frequent_characters[2]++;
+				break;
+			case 'i':
+				number_frequent_characters[3]++;
+				break;
+			case 'n':
+				number_frequent_characters[4]++;
+				break;
+			case 'o':
+				number_frequent_characters[5]++;
+				break;
+			case 'r':
+				number_frequent_characters[6]++;
+				break;
+			case 's':
+				number_frequent_characters[7]++;
+				break;
+			case 't':
+				number_frequent_characters[8]++;
+				break;
+			case 'u':
+				number_frequent_characters[9]++;
+				break;
+		}
 	}
-
-	return ((number*100)/length);
+	#define FREQ_AREA 0.8
+	// compare frequncies with standard frequencies
+	for(i=0;i<10;i++) {
+		double freq =(double) ((double)number_frequent_characters[i]*100/(double)length);
+		if((((standard_frequencies[i] * (1-FREQ_AREA) < freq)
+			)&& ((standard_frequencies[i] * (1+FREQ_AREA)) > freq))) {
+			hits++;
+		}
+	}
+	return hits;
 }
 
 /**
  * encode the given string into base64 and stores it in result
  */
 
-int encode_to_base64(char *encode, char *result)
+void encode_to_base64(char *encode, char *result)
 {
 	int length = strlen(encode);
 	
@@ -318,7 +390,7 @@ int encode_to_base64(char *encode, char *result)
 /**
  * prints and base64 encoded string
  */
-int print_base64_string(char *string)
+void print_base64_string(char *string)
 {
 	// after 76 charactes line break
 	
@@ -330,16 +402,16 @@ int print_base64_string(char *string)
  * @parma string2 second string
  * @return returns the hamming distance
  */
-int hamming_distance_equal_length(char *string1, char *string2)
+int hamming_distance_equal_length(char *string1, char *string2, int length)
 {
 	char tmp;
 	int i, j;
 	int hamming_distance = 0;
 
-	for(i=0;i<strlen(string1);i++) {
+	for(i=0;i<length;i++) {
 		tmp = string1[i] ^ string2[i];
 		for(j = 0; j < 8; j++) {
-			if ( bit_on(tmp, j))
+			if (bit_on(tmp, j))
 				hamming_distance++;
 		}
 	}
@@ -347,42 +419,42 @@ int hamming_distance_equal_length(char *string1, char *string2)
 }
 
 /**
- * returns true if the given strings may represent human language
- */
-int string_looks_like_it_is_human_language(char *string, int length)
-{
-	// string has to be printable and a score bigger than 20
-	// to be assumed to be human language
-	if (!isprintable(string, length))
-		return 0;
-	if (score_based_on_frequent_characters(string, length) < 20)
-		return 0;
-
-	return 1;
-}
-
-/**
  * test every byte on the string as key and returns the found keys
  */
-int brute_force_single_byte_xor(char *string, int length, char* keys)
+char brute_force_single_byte_xor(char *string, int length, struct key_and_freq *ret)
 {
-	int i, number_found_keys=0;
+	int i;
 	char *xor_tmp;
 	char single_byte_key;
-	
-	xor_tmp = malloc(length);
+	char key = 'A';
+	int max_hits = 0;
+	int tmp_hits = 0;
+
+	xor_tmp = malloc(length+1);
 
+//	printf("NEW STINGT TO BREAK\n");
+	// test for every byte
 	for(i=1;i<255;i++) {
 		single_byte_key = (char) i;
 		xor_string(string, &single_byte_key, xor_tmp, 1, length);
-		if (string_looks_like_it_is_human_language(xor_tmp, length)) {
-			keys[number_found_keys++] = single_byte_key;
-			printf("%s\n", xor_tmp);
+		
+		// if string contains not printable characters it is not
+		// the cleartext
+		if (!isprintable(xor_tmp, length))
+			continue;
+		
+		tmp_hits = frequent_histogramm_matchs(xor_tmp, length);
+
+		if (tmp_hits > max_hits) {
+			max_hits = tmp_hits;
+			key = single_byte_key;
+			//printf("Key: %c, hits: %i\n", key, max_hits);
 		}
+		
 	}
-	keys[number_found_keys] = '\0';
+	
+	ret->key = key;
+	ret->hits= max_hits;
 
-	return number_found_keys;
+	return key;
 }
-
-