From 81e563f2c32dfa719365ef418587510bd09eabaf Mon Sep 17 00:00:00 2001 From: Zachary Vance Date: Wed, 24 May 2017 19:05:20 -0700 Subject: [PATCH] Solve Set 1, Problem 4 --- Makefile | 11 +++++--- english.c | 1 + io.c | 14 ++++++++++ io.h | 2 ++ set1p3.test.c | 24 ++++------------- set1p4.test.c | 73 +++++++++++++++++++++++++++++++++++++++++++++++++++ xor_decrypt.c | 44 +++++++++++++++++++++++++++++++ xor_decrypt.h | 2 ++ 8 files changed, 148 insertions(+), 23 deletions(-) create mode 100644 set1p4.test.c create mode 100644 xor_decrypt.c create mode 100644 xor_decrypt.h diff --git a/Makefile b/Makefile index 71f7f4b..36d9376 100644 --- a/Makefile +++ b/Makefile @@ -1,19 +1,22 @@ CC=gcc ODIR=obj -CFLAGS=-fstack-protector-all +CFLAGS=-fstack-protector-all -ggdb all: libs -libs: io.o xor.o util.o english.o +libs: io.o xor.o util.o english.o xor_decrypt.o set1p1.test: set1p1.test.c io.o $(CC) -o $@ $? $(CFLAGS) set1p2.test: set1p2.test.c io.o xor.o $(CC) -o $@ $? $(CFLAGS) -set1p3.test: set1p3.test.c io.o xor.o util.o english.o +set1p3.test: set1p3.test.c io.o xor_decrypt.o english.o util.o xor.o $(CC) -o $@ $? $(CFLAGS) -test: set1p1.test set1p2.test set1p3.test +set1p4.test: set1p4.test.c io.o xor_decrypt.o english.o util.o xor.o + $(CC) -o $@ $? $(CFLAGS) +test: set1p1.test set1p2.test set1p3.test set1p4.test ./set1p1.test >/dev/null || echo "Set 1, Problem 1: Failed" ./set1p2.test >/dev/null || echo "Set 1, Problem 2: Failed" ./set1p3.test >/dev/null || echo "Set 1, Problem 3: Failed" + ./set1p4.test >/dev/null || echo "Set 1, Problem 4: Failed" clean: rm -f *.o a.out *.test %.o: %.c diff --git a/english.c b/english.c index 184f97b..24273cd 100644 --- a/english.c +++ b/english.c @@ -6,6 +6,7 @@ float score_english_character(char c) { case 'e': case 't': case 'a': case 'o': case 'i': case 'n': return 3; break; case 'S': case 'H': case 'R': case 'D': case 'L': case 'U': return 2; break; case 's': case 'h': case 'r': case 'd': case 'l': case 'u': return 2; break; + case 0: return 0; break; default: break; } if (strchr("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz", c) != 0) return 1; diff --git a/io.c b/io.c index 9713754..dbc0874 100644 --- a/io.c +++ b/io.c @@ -129,3 +129,17 @@ int decode_base64(char* src, char* dest, int* destlen) { } return 1; } + +char* printable_buffer(char* buffer, int length) { + char* output = malloc(length*3+2); + encode_hex(buffer, length, output); + memcpy(output + length * 2, ": ", 2); + memcpy(output + length * 2 + 2, buffer, length); + return output; +} + +void print_buffer(char* buffer, int length) { + char* output = printable_buffer(buffer, length); + printf("%s\n", output); + free(output); +} diff --git a/io.h b/io.h index 63d99c8..f0be7c1 100644 --- a/io.h +++ b/io.h @@ -2,3 +2,5 @@ int decode_hex(char* src, char* dest, int *destlen); int decode_base64(char* src, char* dest, int* destlen); void encode_base64(const char* src_bytes, int src_size, char* dest); void encode_hex(const char* src_bytes, int src_size, char* dest); +char* printable_buffer(char* buffer, int length); +void print_buffer(char* buffer, int length); diff --git a/set1p3.test.c b/set1p3.test.c index 1f85d9d..5c985f3 100644 --- a/set1p3.test.c +++ b/set1p3.test.c @@ -1,10 +1,8 @@ #include #include #include -#include "english.h" #include "io.h" -#include "util.h" -#include "xor.h" +#include "xor_decrypt.h" #define S 34 int main() { @@ -19,24 +17,12 @@ int main() { int candidate; unsigned char xor_byte; - float scores[256]; unsigned char best_xor_candidate; - char xor_buffer[S]; - char plaintext_buffer[S+1]; + float score; char best_decryption[S+1]; - plaintext_buffer[S] = 0; // Look like a string for score_english - for (candidate=0; candidate<256; candidate++) { - xor_byte=candidate & 0xFF; // Avoid an infinite loop - - fill(&xor_byte, 1, xor_buffer, S); - xor(xor_buffer, ciphertext_buffer, plaintext_buffer, S); - scores[xor_byte] = score_english_buf(plaintext_buffer, S); - if (scores[xor_byte] > scores[best_xor_candidate]) { - best_xor_candidate=xor_byte; - strncpy(best_decryption, plaintext_buffer, S+1); - } - } - //printf("Best decryption (%hhx => %0.2f): %s\n", best_xor_candidate, scores[best_xor_candidate], best_decryption); + best_decryption[S] = '\0'; // Make it a string. + find_best_xor_candidate_buf(1, ciphertext_buffer, S, &xor_byte, best_decryption, &score); + printf("Best decryption (%hhx => %0.2f): %s\n", xor_byte, score, best_decryption); if (strcmp("Cooking MC's like a pound of bacon", best_decryption) == 0) { printf("%s\n", best_decryption); exit(0); diff --git a/set1p4.test.c b/set1p4.test.c new file mode 100644 index 0000000..d33f572 --- /dev/null +++ b/set1p4.test.c @@ -0,0 +1,73 @@ +#include +#include +#include +#include +#include "io.h" +#include "xor_decrypt.h" +#define MAX_TEXTS 400 +#define CIPHERTEXT_LENGTH 30 +#define HEX_LENGTH (CIPHERTEXT_LENGTH*2) + +int main() { + char *ciphertext_buffers[MAX_TEXTS]; + int candidate_ciphertext_count=0; + + int candidate; + unsigned char xor_byte; + unsigned char best_xor_candidate; + float score, best_score; + int best_candidate; + char decryption[CIPHERTEXT_LENGTH+1], best_decryption[CIPHERTEXT_LENGTH+1]; + int i; + + FILE *fd = fopen("problems/set-1/4.txt", "r"); + for (i=0; i0) { + switch (read_length-1) { + case 60: + case 59: + ciphertext_hex[HEX_LENGTH]='\0'; + ciphertext_buffers[candidate_ciphertext_count] = malloc(CIPHERTEXT_LENGTH); + memset(ciphertext_buffers[candidate_ciphertext_count], 0, CIPHERTEXT_LENGTH); + decode_hex(ciphertext_hex, ciphertext_buffers[candidate_ciphertext_count], &decoded_length); + candidate_ciphertext_count++; + memset(ciphertext_hex, '0', buf_size); + break; + case 58: + printf("That one line (%d) is wrong length... skipping.\n", candidate_ciphertext_count+1); + continue; + default: + printf("Read line %d from file... wrong length: %d\n", candidate_ciphertext_count+1, read_length-1); + exit(1); + break; + } + } + printf("Reading from file complete. Read %d lines.\n", candidate_ciphertext_count); + + decryption[CIPHERTEXT_LENGTH] = '\0'; // Make it a string. + + best_score = -1000; + for(i=0;ibest_score) { + best_score = score; + memcpy(best_decryption, decryption, CIPHERTEXT_LENGTH+1); + best_candidate=i; + } + } + + printf("Best decryption (line %d => %0.2f): %s\n", best_candidate+1, score, best_decryption); + char* expected = "Now that the party is jumping\n"; + if (strcmp(expected, best_decryption) == 0) { + printf("%s\n", best_decryption); + exit(0); + } else { + printf("Wrong decryption: %s\n", best_decryption); + printf(" Expected: %s\n", expected); + print_buffer(best_decryption, CIPHERTEXT_LENGTH); + print_buffer(expected, CIPHERTEXT_LENGTH); + exit(1); + } +} diff --git a/xor_decrypt.c b/xor_decrypt.c new file mode 100644 index 0000000..fdfb45c --- /dev/null +++ b/xor_decrypt.c @@ -0,0 +1,44 @@ +#include +#include +#include "english.h" +#include "util.h" +#include "xor.h" + +void select_best_xor_candidate_buf(char** candidates, int num_candidates, int candidate_length, char* ciphertext_buffer, int ciphertext_length, char* best_candidate, char* best_decryption, float* best_score) { + int candidate; + unsigned char xor_byte; + float score; + unsigned char best_xor_candidate; + char *xor_buffer = malloc(ciphertext_length); + char *plaintext_buffer = malloc(ciphertext_length); + int ci; + + *best_score = -100; + for (ci=0; ci *best_score) { + *best_score = score; + strncpy(best_decryption, plaintext_buffer, ciphertext_length); + strncpy(best_candidate, candidates[ci], candidate_length); + } + } +} + +void find_best_xor_candidate_buf(int length, char* ciphertext, int ciphertext_length, char* best_candidate, char* best_decryption, float* best_score) { + int num_candidates = 1; + unsigned int i, j, ci; + for (i=0; i> (j*8))); + } + } + select_best_xor_candidate_buf(candidate_pointers, num_candidates, length, + ciphertext, ciphertext_length, + best_candidate, best_decryption, best_score); +} diff --git a/xor_decrypt.h b/xor_decrypt.h new file mode 100644 index 0000000..f39417f --- /dev/null +++ b/xor_decrypt.h @@ -0,0 +1,2 @@ +void select_best_xor_candidate_buf(char** candidates, int num_candidates, int candidate_length, char* ciphertext, int ciphertext_length, char* best_candidate, char* best_decryption, float* best_score); +void find_best_xor_candidate_buf(int length, char* ciphertext, int ciphertext_length, char* best_candidate, char* best_decryption, float* best_score); -- 2.47.3