From 442a49ad5a48d417345959b903ae6a6d32d55759 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 15 Apr 2022 15:51:30 -0500 Subject: Great C programming fun Excellent fundamentals and displine training, many tools and techniques exercises: gdb, emacs, valgrind, git --- 25_break_encr/Makefile | 4 ++++ 25_break_encr/Makefile~ | 8 +++++++ 25_break_encr/README | 51 +++++++++++++++++++++++++++++++++++++++++ 25_break_encr/breaker | Bin 0 -> 16560 bytes 25_break_encr/breaker.c | 56 +++++++++++++++++++++++++++++++++++++++++++++ 25_break_encr/encrypt | Bin 0 -> 16624 bytes 25_break_encr/encryption.c | 40 ++++++++++++++++++++++++++++++++ 25_break_encr/grade.txt | 15 ++++++++++++ 25_break_encr/test.txt | 51 +++++++++++++++++++++++++++++++++++++++++ 9 files changed, 225 insertions(+) create mode 100644 25_break_encr/Makefile create mode 100644 25_break_encr/Makefile~ create mode 100644 25_break_encr/README create mode 100755 25_break_encr/breaker create mode 100644 25_break_encr/breaker.c create mode 100755 25_break_encr/encrypt create mode 100644 25_break_encr/encryption.c create mode 100644 25_break_encr/grade.txt create mode 100644 25_break_encr/test.txt (limited to '25_break_encr') diff --git a/25_break_encr/Makefile b/25_break_encr/Makefile new file mode 100644 index 0000000..00ce3b5 --- /dev/null +++ b/25_break_encr/Makefile @@ -0,0 +1,4 @@ +CFLAGS=-ggdb3 -Wall -Werror -pedantic -std=gnu99 + +breaker: breaker.c + gcc -o breaker breaker.c diff --git a/25_break_encr/Makefile~ b/25_break_encr/Makefile~ new file mode 100644 index 0000000..84bf195 --- /dev/null +++ b/25_break_encr/Makefile~ @@ -0,0 +1,8 @@ +CFLAGS=-ggdb3 -Wall -Werror -pedantic -std=gnu99 + +test-eval: deck.o eval.o eval-c4.o test-eval.o deck-c4.o cards.o input.o future.o + gcc -o test-eval -ggdb3 deck.o deck-c4.o eval-c4.o eval.o test-eval.o cards.o input.o future.o +poker: $(GIVEN_OBJS) $(MY_OBJS) + gcc -o poker -ggdb3 $(MY_OBJS) $(GIVEN_OBJS) +clean: + rm -f test poker cards.o my-test-main.o *~ diff --git a/25_break_encr/README b/25_break_encr/README new file mode 100644 index 0000000..fdbc68d --- /dev/null +++ b/25_break_encr/README @@ -0,0 +1,51 @@ + In the last problem, you saw an implementation of a simple +"encryption" program. In this problem, you will write a program +that breaks that encryption---that is, it will take as input +a text file encrypted with the encryption program you just +saw, and prints out the key used to encrypt it! + +Breaking the Caesar Cipher uses a technique called "frequency counting." +This technique relies on the fact that the distribution of letters +in the English alphabet is far from uniform: 'e' is by far the most +common letter (~13%), followed by 't' (9%), and 'a' (8%). Note +that the average frequency is 100/26 ~= 4%. + +This frequency distribution means that if you know (or suspect) +that a file contains English text encrypted with a Caesar Cipher, +you can simply count the frequency of all letters in it, and guess +that the letter which occurs most often is 'e'. Once you know +which letter is 'e', you can backsolve for the key and decrypt +the file. Note that in practice this requires a large enough +text that "the law of large numbers" applies---and while it is +not guaranteed to work, it typically does. + + +Requirements: +============= + + - Your program will take one command line argument: the name + of a file to read as input + - Your program will then perform frequency counting on the letters + in that text file. Your program should ignore all non-letter + characters (those un-modified by your problem 1 program). + - Your program should use the frequency count information to + determine which letter is 'e', and solve for the key. + - On success, your program should print a single line of output to + stdout, which should contain one decimal (base 10) integer (followed by a + newline character). This number should be the encryption key used + on the text. It should be in the range [0,26). That is, the + number you print should obey 0 <= answer < 26. + - On failure, your program should print an appropriate error + message to stderr, then exit with EXIT_FAILURE. + - Provide a Makefile which compiles your program into + a binary called "breaker" +Hints: + - Divide this problem into sub-problems. You should probably + write at least two functions (other than main) to do this. + - Think about how you want to represent your data. An array + might be handy somewhere. + - You may find a function you wrote in a previous classwork + useful for this assignment. Feel free to use or adapt it. + - Remember that everything (including characters) are numbers. + You might look back at the "Read encryption" assignment + to see an example of doing math on characters. diff --git a/25_break_encr/breaker b/25_break_encr/breaker new file mode 100755 index 0000000..00c5a4a Binary files /dev/null and b/25_break_encr/breaker differ diff --git a/25_break_encr/breaker.c b/25_break_encr/breaker.c new file mode 100644 index 0000000..1f71d2c --- /dev/null +++ b/25_break_encr/breaker.c @@ -0,0 +1,56 @@ +#include +#include +#include + +size_t max(int * letters, size_t n) { + int maxCount = letters[0]; + int maxElementIndex = 0; + + for (size_t i = 1; i < n; i++) { + if (letters[i] > maxCount) { + maxCount = letters[i]; + maxElementIndex = i; + } + } + return maxElementIndex; +} + +int decrypt(FILE * f) { + int c; + int letters[26] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; + while ((c = fgetc(f)) != EOF) { + if (isalpha(c)) { + c = tolower(c); + c -= 'a'; + letters[c] = letters[c] + 1; + } + } + + size_t maxElement = max(letters, 26); + int ans; + + if (maxElement >= 4) { + ans = maxElement - 4; + } else { + ans = 26 - (4 - maxElement); + } + return ans; +} + +int main(int argc, char ** argv) { + if (argc != 2) { + fprintf(stderr,"Usage: breaker inputFileName\n"); + return EXIT_FAILURE; + } + + FILE * f = fopen(argv[1], "r"); + if (f == NULL) { + perror("Could not open file"); + return EXIT_FAILURE; + } + size_t key = decrypt(f); + + printf("%d\n", key); + + return EXIT_SUCCESS; +} diff --git a/25_break_encr/encrypt b/25_break_encr/encrypt new file mode 100755 index 0000000..a85af2f Binary files /dev/null and b/25_break_encr/encrypt differ diff --git a/25_break_encr/encryption.c b/25_break_encr/encryption.c new file mode 100644 index 0000000..3e3b6b1 --- /dev/null +++ b/25_break_encr/encryption.c @@ -0,0 +1,40 @@ +#include +#include +#include + +void encrypt(FILE * f, int key) { + int c; + while ((c = fgetc(f)) != EOF) { + if (isalpha(c)) { + c = tolower(c); + c -= 'a'; + c += key; + c %= 26; + c += 'a'; + } + printf("%c", c); + } +} + +int main(int argc, char ** argv) { + if (argc != 3) { + fprintf(stderr,"Usage: encrypt key inputFileName\n"); + return EXIT_FAILURE; + } + int key = atoi(argv[1]); + if (key == 0) { + fprintf(stderr,"Invalid key (%s): must be a non-zero integer\n", argv[1]); + return EXIT_FAILURE; + } + FILE * f = fopen(argv[2], "r"); + if (f == NULL) { + perror("Could not open file"); + return EXIT_FAILURE; + } + encrypt(f,key); + if (fclose(f) != 0) { + perror("Failed to close the input file!"); + return EXIT_FAILURE; + } + return EXIT_SUCCESS; +} diff --git a/25_break_encr/grade.txt b/25_break_encr/grade.txt new file mode 100644 index 0000000..e7e3b44 --- /dev/null +++ b/25_break_encr/grade.txt @@ -0,0 +1,15 @@ +Grading at Mon 22 Nov 2021 03:21:32 AM UTC +Attempting to compile breaker.c +gcc -o breaker breaker.c +testcase1 passed +################################################# +testcase2: +testcase2 passed +################################################# +testcase3: +testcase3 passed +################################################# +testcase4: +testcase4 passed + +Overall Grade: A diff --git a/25_break_encr/test.txt b/25_break_encr/test.txt new file mode 100644 index 0000000..52d88ee --- /dev/null +++ b/25_break_encr/test.txt @@ -0,0 +1,51 @@ + pu aol shza wyvislt, fvb zhd hu ptwsltluahapvu vm h zptwsl +"lujyfwapvu" wyvnyht. pu aopz wyvislt, fvb dpss dypal h wyvnyht +aoha iylhrz aoha lujyfwapvu---aoha pz, pa dpss ahrl hz puwba +h alea mpsl lujyfwalk dpao aol lujyfwapvu wyvnyht fvb qbza +zhd, huk wypuaz vba aol rlf bzlk av lujyfwa pa! + +iylhrpun aol jhlzhy jpwoly bzlz h aljoupxbl jhsslk "mylxblujf jvbuapun." +aopz aljoupxbl ylsplz vu aol mhja aoha aol kpzaypibapvu vm slaalyz +pu aol lunspzo hswohila pz mhy myvt bupmvyt: 'l' pz if mhy aol tvza +jvttvu slaaly (~13%), mvssvdlk if 'a' (9%), huk 'h' (8%). uval +aoha aol hclyhnl mylxblujf pz 100/26 ~= 4%. + +aopz mylxblujf kpzaypibapvu tlhuz aoha pm fvb ruvd (vy zbzwlja) +aoha h mpsl jvuahpuz lunspzo alea lujyfwalk dpao h jhlzhy jpwoly, +fvb jhu zptwsf jvbua aol mylxblujf vm hss slaalyz pu pa, huk nblzz +aoha aol slaaly dopjo vjjbyz tvza vmalu pz 'l'. vujl fvb ruvd +dopjo slaaly pz 'l', fvb jhu ihjrzvscl mvy aol rlf huk kljyfwa +aol mpsl. uval aoha pu wyhjapjl aopz ylxbpylz h shynl luvbno +alea aoha "aol shd vm shynl ubtilyz" hwwsplz---huk dopsl pa pz +uva nbhyhuallk av dvyr, pa afwpjhssf kvlz. + + +ylxbpyltluaz: +============= + + - fvby wyvnyht dpss ahrl vul jvtthuk spul hynbtlua: aol uhtl + vm h mpsl av ylhk hz puwba + - fvby wyvnyht dpss aolu wlymvyt mylxblujf jvbuapun vu aol slaalyz + pu aoha alea mpsl. fvby wyvnyht zovbsk pnuvyl hss uvu-slaaly + johyhjalyz (aovzl bu-tvkpmplk if fvby wyvislt 1 wyvnyht). + - fvby wyvnyht zovbsk bzl aol mylxblujf jvbua pumvythapvu av + klalytpul dopjo slaaly pz 'l', huk zvscl mvy aol rlf. + - vu zbjjlzz, fvby wyvnyht zovbsk wypua h zpunsl spul vm vbawba av + zakvba, dopjo zovbsk jvuahpu vul kljpths (ihzl 10) pualnly (mvssvdlk if h + uldspul johyhjaly). aopz ubtily zovbsk il aol lujyfwapvu rlf bzlk + vu aol alea. pa zovbsk il pu aol yhunl [0,26). aoha pz, aol + ubtily fvb wypua zovbsk vilf 0 <= huzdly < 26. + - vu mhpsbyl, fvby wyvnyht zovbsk wypua hu hwwyvwyphal lyyvy + tlzzhnl av zaklyy, aolu lepa dpao lepa_mhpsbyl. + - wyvcpkl h thrlmpsl dopjo jvtwpslz fvby wyvnyht puav + h ipuhyf jhsslk "iylhrly" +opuaz: + - kpcpkl aopz wyvislt puav zbi-wyvisltz. fvb zovbsk wyvihisf + dypal ha slhza adv mbujapvuz (vaoly aohu thpu) av kv aopz. + - aopur hivba ovd fvb dhua av ylwylzlua fvby khah. hu hyyhf + tpnoa il ohukf zvtldolyl. + - fvb thf mpuk h mbujapvu fvb dyval pu h wylcpvbz jshzzdvyr + bzlmbs mvy aopz hzzpnutlua. mlls myll av bzl vy hkhwa pa. + - yltltily aoha lclyfaopun (pujsbkpun johyhjalyz) hyl ubtilyz. + fvb tpnoa svvr ihjr ha aol "ylhk lujyfwapvu" hzzpnutlua + av zll hu lehtwsl vm kvpun thao vu johyhjalyz. -- cgit v1.2.3