We all have secrets. Some of us are trying to trying to hide them from our friends, spouses, or even totalitarian governments. This week in CS50 we covered cryptography; the art of keeping secrets. Cryptography is an incredibly immense and incredible science dating back to antiquity with the Greeks and the Arabs. Also one that is incredibly relevant to the privacy crisis we have going on today. Let’s dive into three examples of cryptography in this weeks PSet 2.
Initial.c is not an encryption task, it is a string manipulation task. Our goal is simple, to receive a name from the user and return to them their initials. To understand a little about why this task is interesting let’s take a short dive into how computers store text. Everything a computer deals with is binary, on’s and off’s, zeros and ones. However, Computer Science allows us to abstract away the pesky binary into constructions and syntax that makes up programming languages. In C, and most other modern languages, characters are stored in a system called ascii. Ascii allows us to represent characters using a series of binary bits (lots of 1’s and 0’s) and thus make characters. Now how might we make words? We can make array’s of these characters (chars) to represent words. This means that each letter is at a certain numeric index (position) and it’s relatively easy to step through an array and look at each character.
With this knowledge, we can quickly design an algorithm to give us initials. First we’re going to automatically assume the first character in the name in an initial. Next we’re going to keep stepping through this array of characters until we find a position that contains a space, and has a valid character after it (ie. a letter, not another space), and we will call this our next initial. We will continue this second step until we reach the end of the array when we will print these initials.
Nice warmup, huh?
A Caesarian shift cipher is perhaps the most ubiquitous cipher every created. This simple algorithm goes back to Julius Caesar himself, who at least according to Suetonius in The Twelve Caesar’s, used it himself to protect important military messages. The cipher is simply, shift each letter in the message either forward or backwards some number of characters.
For example ‘Go Town! Beat George!’ shifted twenty one characters would be ‘Bj Ojri! Wzvo Bzjmbz!’ after shifting. While on paper this is pretty easy, it is a pretty non trivial programming challenge. It requires us to develop two algorithms that we derive from the ASCII table, one for upper case, and one for lower. While this builds on top of the string manipulation we saw in initials.c it is also a challenging forward. This is our first time deriving algorithms by ourself and would prove quick the challenge to the first time programmer.
The last problem of our second Pset involved us implementing a more complex form of cipher called a Vigenére cipher. The Vigenêre cipher works like a Caesarian shift, however we do not shift based on a constant, we shift based off of a key string. For example we’d have our key string ‘Beat George’ and our message ‘Go Town’. We’d offset each letter in ‘Go Town’ based on the position in the alphabet of the corresponding letter in ‘Beat George’ giving us ‘Hs Thcr’. This cipher, while still incredibly insecure by modern standards, was an incredible step forward compared to the Caesarian cipher (which could be broken by trying all 26 possibilities).
This was yet another problem to teach us string manipulation and algorithm design. If you are interested into exactly how exactly we might implement this you can see the algorithm in the image above.
This was a difficult week in CS50; the second problem set was a major leap forward in difficulty. While the subject at hand, storing, modifying, and manipulating strings isn’t incredibly difficult it is certainly compounded in difficulty if you haven’t seen cryptography before. I can see a lot of students will struggle on this first real deep dive into C and I am happy I did not share their toil. This week was a lot of fun for me, cryptography is one of my passions, and my familiarity made implementing these ciphers trivial. If cryptography piqued your interest at all I highly recommend reading The Code Book: The Evolution Of Secrecy From Mary, Queen Of Scots To Quantum Cryptography by Simon Singh. It is a great nontechnical introduction to the history and science of Cryptography.