2017 Summer Cryptography Project – Caesar Ciphers and ASCII Tables

Admittedly, the time before my summer semester in Japan was ill-spent in regards to furthering my understanding in the Computer Science world. However, there were still a couple of projects that I did for fun before I left. This first project, a rather simple caesar cipher, was the first of two projects I did. I did this project in particular as a way to brush up on some of the knowledge of the C language I gained during my spring semester CS 2505 class at Virginia Tech. For those unfamiliar with the concept of a caesar cipher, it’s a crude way to encode a chunk of information — simply taking every letter and shifting it up or down a predetermined number of spaces in the alphabet. For instance, the string “abcd” would be encrypted to “bcde” with a caesar key of positive one. Of course, traditionally, wrapping occurs at the ends of the alphabet; meaning z -> a with a key of +1, and a -> z with a key of -1.

There are a couple key parts when it comes to translating this into code. First and foremost, I made it runnable via. the command line. The program expects the file path to the text file the user wants scrambled or unscrambled, along with either ‘e’ or ‘d’ for ‘encode’ and ‘decode’ respectively. Next, instead of letting the letters wrap once at the end/beginning of the alphabet, I allowed the characters to go above/below this limit, possible thanks to the format of the ASCII table.

asciifull

ASCII table

In C, along with the vast majority of programming languages used today, ‘char’ (character) variables are actually stored as integers. Each character is 1 byte, allowing for up to 256 different characters to exist. This not only includes your standard upper/lower case alphabet and numbers, but also special characters, along with some special, machine only characters, like ‘\n’ (new line). So, instead of wrapping at the ends of the alphabet, I wrapped at the ends of the ASCII table (see methods encode and decode in the block below to see how). In regards to my program, this is relevant because it allows for characters to spill over into generally weird or unexpected characters, making it easier on us to program because we don’t need to look for specific ASCII values to wrap around, as well as adding a bit more effectiveness to the final product. Of course, this method won’t fool someone who knows what they’re doing when it comes to decryption, but it should generally prevent friends or co-workers from snooping into information you don’t want shared.

There are still plenty of improvements that can be made to this system to improve it even further and lessen the chance of someone cracking a particular files key. As you can see in this iteration of the program below, the key is static between all files, meaning a correct guess on one file means access to your entire library of secret text files. This could be improved by simply making the key random between files and stored somewhere inconspicuous. For instance, the key could be between 0 and 255, and simply written as the first character of the encoded file. While again, this method would fail almost instantly in the case of a professional crack, it should stump the average Joe for a couple of hours. Or, perhaps this method is repeated for every character in any one file; the key for any given character placed just before or after it. I’m sure you can see how this method can become increasingly complex, and increasingly difficult to break, the longer you think about it.

FILE *f;

int caesar = 5;

int main(int argc, char **argv) {
	if (argc != 3)
		badInput();
	FILE* f = getFile(argv[1]);
	if (strcmp(argv[2], "e") == 0)
		encode(f);
	else if (strcmp(argv[2], "d") == 0)
		decode(f);
	else
		badInput();
	fclose(f);
	return 0;
}

void badInput() {
	printf("Format is '.../caeser <.../fileToEdit.txt> <e/d>'\n");
	exit(1);
}

FILE* getFile(char *url) {
	FILE *f = fopen(url, "r+");
	if (f == NULL) {
		printf("Can't locate file '%s'", url);
		badInput();
	}
	return f;
}

void encode(FILE *f) {
	int c;
	while((c = fgetc(f)) != EOF) {
		fseek(f, -1, SEEK_CUR);
		fputc((c + caesar) % 255, f);
		fseek(f, 0, SEEK_CUR);
	}
}

void decode(FILE *f) {
	int c;
	while((c = fgetc(f)) != EOF) {
		fseek(f, -1, SEEK_CUR);
		fputc((c - caesar) % 255, f);
		fseek(f, 0, SEEK_CUR);
	}
}

The C code behind the Caesar Cipher. If you have any questions about the code feel free to email me: brendan.mccloskey@gmail.com.

This project was an easy, quick, and fun way to stay familiar with the ins and outs of ASCII values and C I/O alike. Feel free to take this idea further and create ciphers of your own!

Advertisements

2015 Winter Cryptography Project – P / NP, The Clique Problem

I recently read a book titled The Golden Ticket by Lance Fortnow in which the P / NP Problem and its importance to the theory of Computer Science are heavily discussed. Explained briefly, the P / NP Problem asks if every single problem can be solved quickly and efficiently. In relations to cryptography, P / NP is crucial because it allows for the creation of hard math problems to, for example, be able to hide private information on a public network. One of the most famous P / NP Problems, the Clique problem, was discussed and is, in my opinion, one of the more intriguing problems in the book.

Take, for example, a society called Frenemy, in which every citizen either has a 50% chance to be friends or a a 50% chance to be an enemy with a person they just met. In Fortnow’s book, he details how it would be virtually impossible to find all cliques of varying sizes (difficulty/time to find all cliques increases as size of desired clique increase) inside of this society (A clique is a group of people in which everyone is friends with all other members). At first, I didn’t think it would be that difficult to find the largest clique, but after making a simulation for myself, I was proven otherwise.

I stayed true to the Frenemy rules in my simulation – every time someone meets someone else, they have a 50% chance to either be their friend or their enemy. I experimented with varying population sizes as well as varying amounts of citizens in which each person can meet. I made two methods in order to experiment, one in which everyone meets everyone else in the society, and one in which everyone meets everyone on their own street (9 total streets in which 1/9 of the total population lives on each given street). To make the data easier to set up and understand, each citizen is given an identification number as well as an ‘address’, the number of street they live on. I aimed to find every single clique of size 3 in the society, and to see for myself how difficult it became to find them as population size increased.

Screen Shot 2016-01-13 at 1.49.10 PM

A couple of cliques present in a population size of 100 in which citizens met everyone on their own street.

I found that the total time to generate the population and find cliques of size 3 took much much longer the higher the population size was, which makes sense in hindsight. Adding a single citizen to a population size of 20 where everyone meets everybody doesn’t have nearly the impact as adding a citizen to a population size of 10,000,  as the number of updates a computer has to make to each citizen’s list of friends and enemies for a population of 10,000 is much larger. When I was reading Fortnow’s book, I didn’t put much thought into the rate at which the updates change as population size grows. I naively thought growth was generally linear, allowing total computations to find all cliques of size 3 to be relatively small compared to the actual value. Only after I made my own simulation did I truly understand the difficulty surrounding finding a solution to the Clique problem. If you find find yourself with some free time, I would recommend making a simple simulation like this for yourself so you can see the results firsthand.

I’d like to thank Lance Fortnow for pushing me to explore this problem through his book, as all P / NP problems (not just the Clique problem) are profoundly interesting in their own rights. And, if you’re planning to look more into the P / NP problem, Lance Fortnow’s The Golden Ticket is a must read. The discussion as well as the existence of the P / NP Problem has really expanded my understanding of Computer Science and the importance of not only the physical act of coding, but the theory behind CS as well.

2015 Fall Cryptography Project – Password Generator

During the early part of 2015 I was fairly interested in cryptography. In particular, I was interested in penetration testing of all sorts – accounts, WEP and WPA wifi password cracking, etc. Of course, I was only cracking  accounts I owned.

The pinnacle of my interest with pen testing came when I decided to make a password cracker. For example, say my password is C0d3BR3ND4N!. You enter a few words that you think your target would include in their password, as well as a few parameters, and let it go. The magical components for my password would simply be brendan and code, input with the parameters –H (includes capital permutations as well as numbers substituted for letters), –P !#(adds ! and numbers 0-9 before and after each possible password), and -w (writes to file), and after a few seconds, the program would find my password with relative ease.

Screen Shot 2015-12-12 at 12.45.11 PM

Portion of the words generated.

It essentially mashes all the words it was given together, finds all of the capital permutations and all forms of numbers switched with letters, etc., then adds it to the file.

Screen Shot 2015-12-12 at 12.41.21 PM

Terminal display.

Because this program can crack passwords, I’ll refrain from posting the source code. You can, however, access the .txt file I generated for the purposes of this post here: https://drive.google.com/file/d/0Bz_0wgRmDpKqNHFtU2pLZV96SDg/view?usp=sharing