summaryrefslogtreecommitdiff
path: root/25_break_encr
diff options
context:
space:
mode:
Diffstat (limited to '25_break_encr')
-rw-r--r--25_break_encr/Makefile4
-rw-r--r--25_break_encr/Makefile~8
-rw-r--r--25_break_encr/README51
-rwxr-xr-x25_break_encr/breakerbin0 -> 16560 bytes
-rw-r--r--25_break_encr/breaker.c56
-rwxr-xr-x25_break_encr/encryptbin0 -> 16624 bytes
-rw-r--r--25_break_encr/encryption.c40
-rw-r--r--25_break_encr/grade.txt15
-rw-r--r--25_break_encr/test.txt51
9 files changed, 225 insertions, 0 deletions
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
--- /dev/null
+++ b/25_break_encr/breaker
Binary files 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 <stdio.h>
+#include <stdlib.h>
+#include <ctype.h>
+
+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
--- /dev/null
+++ b/25_break_encr/encrypt
Binary files 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 <stdio.h>
+#include <stdlib.h>
+#include <ctype.h>
+
+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.