Public Key Cryptography and RSA

I finished the rest of Simon Singh’s book last week over break as I tried to wrap my head around cryptography. Dan Boneh’s online Cryptography class started as well so there’s quite a few things to keep track of at the same time. Let’s go through it one step at a time.

The thing with RSA and PKE is that they are all very well documented. From the conception to implementation, everyone knows everything about them, but thats what gives the algorithm its strength, that exactly so many mathematicians and computer scientists know how the system works but haven’t been able to suggest a way to break it.

The concept by itself is startling, the idea that you can encrypt something with every one knowing most everything about the encryption process and yet not being able to decrypt the message. That’s because the algorithms use certain one-way functions like modulus arithmetic to encrypt, and then utilize properties of modulus arithmetic to undo the one way function.

Whitfield Diffie, Martin Hellman and Ralph Merkle worked on the idea of public key cryptography when every else thought they were insane. From the birth of cryptography all encryption ciphers were symmetric and as a result when the scope of what was being encrypted by whom grew the problem of key generation and distribution grew as well into a herculean task. Diffie, Hellman and Merkle began work to find a new way of key exchange that wouldn’t require perfect secrecy to create secret keys. What they came up with is the Diffie-Hellman key exchange system.

Diffie Hellman Exchange Algorithm shown using paint as a metaphor
Diffie Hellman Exchange Algorithm shown using paint as a metaphor.

The algorithm is explained beautifully on the wikipedia page, but what you might note is that this process that they created is simultaneous. That is, both parties need to send messages back and forth before a key can be created. With email, this can be a type of problem since people might not both be online. Instead, the solution to that problem came from three other very famous cryptographers, Ron Rivest, Adi Shamir, and Leonard Adleman (RSA).

What Rivest, Shamir and Adleman did was respond to a paper by Diffie, Hellman and Merkle that proposed the idea of public key cryptography. That is cryptographic ciphers that used entirely public keys to encrypt a message, but could then only be (easily) decrypted using a second more private key.

Utilizing the same modulus arithmetic that Diffie, Hellman and Merkle were working with the trio came up with an algorithm based on the properties of prime numbers. To start with, party A (in cryptography circles party A is referred to as Alice) creates a number N by multiplying two very very large prime numbers, prime ‘p’ and ‘q’.  Alice then creates another number called an exponent ‘e’ using Euler’s Totient, and releases this number publicly.

Now we party B (or Bob) who tries to send Alice an encrypted message M. He does this by taking exponential result of M^e (where ‘e’ is the same ‘e’ that Alice publically released) and then modulo the result by Alice’s public N. The resulting integer is the encrypted message C. Thus the formula is  C = M^e (mod N).

Now Alice takes the result and runs it through the decryption algorithm where M = C^d (mod N). ‘d’ is defined as the multiplicative inverse of the ‘e’ modulo Euler’s totient of N.

This works and works well enough for this algorithm to have become the basis of all modern cryptography. It’s used in billions of transactions a day, and while it has its problems, the algorithm is secure enough. I’m hoping to learn more about the mathematics behind this to be able to concisely explain why it works the way it does but in the meantime I’m moving onto another aspect of cryptography, visual cryptography. More on that soon!

The Waiting Game

Maybe it’s because I’m in Big Games or maybe I’m just on a gaming bend, but I’ve been working on developing another game as well. For our class in Spatial Media, my friend and I decided to build a spatially aware installation called the Waiting Game to help pass the time for those people stuck in line at some location.

During the design process we considered the different types of places and experiences you might have at those places while waiting in line. My friend Mark Kleback and I were originally inspired by the long lines at the Post Office near NYU, but we quickly decided against designing any interaction for the Post Office simply because the space was so charged as it is that an interactive game might inflame passions rather than provide a fun diversion.

So instead we set our eyes upon the waiting lines at check-in counters at the airport, specifically JFK’s JetBlue check-in terminals. Mind you, we love JetBlue, but we could do with waiting less in line anywhere. So with this in mind we designed a simple interactive piece where little airplanes would take off at the beginning of the line and fly in determined flightpaths through the line and then land in the end while circumventing objects along the path.

Mockup of our waiting line game
This Sketchup mockup made by Mark Kleback details how we envisioned the game to be played by travelers waiting in line at the check-in counter.

Using the Kinect we tracked people as they walked through the line and had the planes divert around the object until they could return to their flight plans. Travelers can interact with the planes by sticking out their hands and feet and gently guiding the planes through the line. The code has a few bugs that we need to fix, but for the most part the code works wonderfully. Unfortunately due to bad projector selection we had to scale down our design as you can see in the video below. With the right equipment however we don’t see any reason why we couldn’t implement this at JFK.

The code was written with OpenFrameworks and OpenCV. You can find the code online on github.

Mime Tribe

This term I’m enrolled in a game design course that deals specifically with high level game design theory. Big Games as it’s called, is an incredibly enlightening and fun exploration into a medium I have spent an enormous amount of time in (playing games of course). Instead of just playing games (and we do play a lot of games) we also read a lot of theoretical texts to help break down what it is about games that makes them such a compelling story telling medium. In order to aid our understanding of game aesthetics, dynamics and mechanics we design and build our own games, like Mime Tribe.

Mime Tribe is a round-based social game where the participants are split into teams and then individually they play the rounds to gain points for their teams. At the start of each round the players all get a card with a word they must try to mime. The goal of the round is to try to find the other players that are trying to mime the same thing as yourself. At the end of each round teams are awarded points based on the number of their members who were able to find the correct “tribes.”

The team dynamic is what was really important to us. We wanted people to be playing for each other as well as themselves, that way we hoped we could encourage different strategies in playing the game. By the end of a few rounds we had people trying to sabotage other teams.

Mime Tribe Cards
These cards carried a variety of noun's that players would have to try to mime.

Below is the document we drafted to define the game and the rules in case you’d like to try and play it with your friends:

The group is divided into 4 color teams. Teams will have 30 seconds to strategize before each game.

Each player will receive a card designating their TRIBE.

Players look at their own card, but may not show anyone else.

Upon the instruction to begin, players have 15 seconds to silently find other members of their TRIBE

Once you are confident that someone is in your tribe you must form a circle by holding hands.

Each player in a correct tribal circle will be awarded points for their team based on the number of players in that circle. Two members of the same tribe will each win 2 points for their team. Three members will win 3 points. And so on.

If just one player is in the wrong tribal circle, everyone in that circle receives zero points. Players that are alone at the close of play will also receive zero points.

Text Viz (TV)

Here at ITP we have an email list that is constantly connecting all the students together in this massive conversation about everything from arts to technology to politics. It’s really quite wonderful and at times also very overwhelming. Many student’s don’t bother to read the list because of the sheer volume of messages that are sent, others are very protective of the list and will jump at anyone who might try to subvert the list or appropriate it for their own cause.

With this example in mind, my friend Dekunle Somade suggested we work on a project together to bring text message (SMS) based group conversations to the shared space of ITP. There were several analogues and examples of this kind of communications system before hand aside from the ITP Student List. One is the Blackboard Blogger of Liberia and the other was an internal IDEO project I remember hearing about but can’t seem to find any documentation regarding. The project was an interactive display of all the IDEO employee’s timelines and feeds, each getting a moment on screen and each allowing those who were viewing it in the common room to get a better sense of what their coworkers were working on and thinking.

Daily Talk Liberia

With those two examples in mind we set about creating a platform that would be simple to use but would allow ITP students to share and connect with other ITP students on the floor without having to know everyone’s phone number. It was a virtual billboard that you could send text messages to.

The project had two parts, the first was a PHP/MySQL web app that at first utilized the TextMarks API and then later the Twilio APIto receive text messages, associate the phone number with an ITP face and then display it on our website. You can view the current iteration of the site here.

Text Viz Web App
A view of the Text Viz Web App Interface

After the web app was complete we built a kiosk application that would take the JSON formed data from the website and present it in a manner on the kiosk.

Text Viz Processing App
An image from the Text Viz Processing Application

I plan on returning to this project shortly and improving the interaction and functionality of both the webapp and kiosk application. After the project is in a better state I will also release all of the source code. Stay tuned!

The Enigma Machine

There is no way to summarize succinctly the incredible story of the Enigma Machine and the drama that surrounded the machine in this blog post, so I highly recommend reading some of the many wonderful books on the subject or reading the excellent chapter on the machine in Simon Singh’s book as I am.

With that said, I will try to give you an overview of how it is the Enigma Machine was developed and how it worked, as well as how it was finally cracked.

Arthur Scherbius, a German inventor and engineer developed the Enigma around the end of the first world war and tried at first (unsuccessfully) to sell it to commercial companies to help them protect their communications from competitors.

Arthur Scherbius' patent for the Enigma Machine
Arthur Scherbius' patent for the Enigma Machine

The device looked like a typewriter with a keyboard in the middle, a plug board below it and a set of lights that were associated with letters in the alphabet above the keyboard. The keyboard sent an electrical signal through a plug board which allowed the user to customize the wirings of letters, mapping the A key to the P key for example, the signal would then continue to a set of three scrambling cylinders that would take the signal and output it to another position. This process would be repeated two more times scrambling the signal through three levels of the rings and then into a reflector at the end which would then send the signal back up through another path on the scramblers. The signal would then finally terminate at the lights, illuminating the cipher text which corresponded with the original keypress.

What made the machine complicated was the fact that on top of the customizations available (the plug board settings, the scrambler settings and the scrambler order) the machine would then automatically rotate the scramblers with every key press creating a new scrambling order and developing a new cipher for every sequential key.

After many attempts to decipher the messages being enciphered by the Enigma most cryptanalysts simply gave up, believing the system was impregnable. At the same time many governments were shuttering their cryptanalysis bureaus because of the new sensibility that couldn’t permit the eavesdropping and spy craft necessary.

This was not the case in Poland, the young nation was terrified of its neighbors and when faced with the challenge of the Enigma Machine they adapted and persevered. The Polish Biuro Szyfrów began recruiting German-speaking mathematicians into their ranks to take a stab at deciphering the Enigma and when coupled with some excellent spy craft that gave them the scrambler wiring configurations a mathematician named Marian Rejewski was able to deduce a weakness in their system.

To understand the weakness you have to understand the process used to encrypt and send messages. The Germans utilized a set of code books that were developed and distributed every month to all of the hundreds of Enigma operators. The code books detailed day codes to be used by all operators that set the plug board order, the scrambler order and the scrambler settings. This was the greatest weakness they realized. If the code books fell into enemy hands it could be conceivable that the enemy could simply plug-in the settings and intercept all of the orders being broadcasted by all the Enigma operators.

To combat this the Germans instituted a message key system that the message senders used to make unique encryptions for each message. After setting the Enigma to the day code, the operators were instructed to pick a random three-letter combination for a new message key and transmit that twice in the day code setting, and then reset their machines to the new message key settings and finally transmit the entire message. The weakness was the repetition. As you remember, repetition is the enemy of security, and when Rejewski realized this fatal error he exploited it ruthlessly.

Through tedious experimentation he was able to deduce that in order for a message key such as ABR, when repeated ABRABR, and enciphered TWEVZP, to become this unintelligible mess the rotors of the scramblers had to have turns 6 times. Since the first and fourth letters, as well as the second and fifth letter and the third and sixth letters were identical, the process of scrambling had in fact been revealed. If you could track how the scrambler had to have turned in order for the letter to be enciphered one way initially and another way in just three steps then you can deduce how the scramblers were set up.

With this information Rejewski and the team at Biuro Szyfrów were able to monitor almost all German communications even as their allies were blind. Unfortunately, this wasn’t able to save Poland, as just before the war broke out Germany added several layers of complexity to the Enigma machine by adding additional scrambler configurations and extra plug board inputs. The Polish then decided to share what they knew with other allied forces just two weeks before Germany invaded Poland.

Utilizing what Rejewski and the Biuro had managed to do, the teams of cryptanalysts in Britain’s Bletchley Park were able to decipher the now more complex Enigma messages up until the German’s stopped broadcasting the repeated message keys. At this point however, a brilliant mathematician named Alan Turing had begun work on a slightly varied way of exploiting the numerical structure of the Enigma cipher.

Turing is widely acknowledged to have developed a formal framework for the modern computer as a young academic before taking up his secretive role at Bletchley Park. Utilizing this system of computing, Turing thought of a way of mechanizing the process of deciphering the day codes through exploiting yet another human error: the error of being predictable. The cryptanalysts realized at some point that the German operators often wrote messages the same way again and again. For example the weather reports would often start one way. If you could reasonable assume that a message included a specific text (this was called a crib), then you can play with this piece of cipher text and run through the various permutations of scramblers until the code was revealed.

Turing built this machine and after a few iterations had a series of these machines to descramble the day codes in hours if the cribs were accurate. This wouldn’t always work, but it worked well enough to provide a huge advantage to the Allied forces as they intercepted German assault boats and convoys as well as troops and reinforcements. The German’s never suspected their Enigma had been cracked.

Radio Changes the Paradigm

So last time I visited the Simon Singh’s Code Book was just as Charles Babbage was breaking Vigenére’s cipher by applying frequency analysis to the individually addressed letters in the key.

As Singh later describes, repetition is the enemy of security, and this holds true in pretty much all cases. It is the reason Babbage was able to break the Vigenére cipher and the reason, as we see later, that Allied cryptographers used to break the Enigma.

One way to make a perfect cipher is to prevent repetition, with for example a one-time pad of random keys. This is as Singh suggest, a “perfect cipher”, impregnable to any cryptanalysis. It is not easy to maintain though, and producing random one-time pads is very difficult.

So short cuts are taken, especially considering that around this time period (late 19th/early 20th century) the invention of the telegraph and radio means that more and more communication is being done out in the open, available for any to capture.  As a result, cryptography becomes part of the mainstream as many members of the public try to encrypt their private correspondence to prevent prying eyes and ears from reading their messages.

All the meanwhile, government-run cryptanalysis centers beef up their staff and talent as politics gets heated. When war finally breaks out in Europe, cryptanalysis plays a large role in determining the outcome of the battles and the war as a whole.

During the war some really interesting insights are developed. Since this is the first time radio is used to communicate during wartime, analysts realize the power of traffic and signal analysis, both very interesting fields in of themselves. For example, analysts are able to determine the location of message senders through triangulation and are able to uniquely identify the message sender by analyzing how the message is being sent.

The real gem of cryptanalysis during the First World War comes from the British. British cryptanalysts at Room 40 had managed to completely decipher German communications at some point and were openly reading all of the messages being sent by German command. Singh doesn’t really go over the ciphers and how they were decrypted, but it appears that this had been done mostly through spycraft and intelligence gather rather than through cryptanalysis.

Nonetheless, the intelligence they gained was gold. At one point the German command had decided to renege on a deal that had kept the United States out of the war in order to ensure themselves a swift victory against the British. The British decrypted the message with the order to begin unrestricted U-Boat warfare as well as the invitation for Mexico to make war against the United States in order to keep America too busy to engage in Europe. With some slick spycraft, they were able to publicize the message without even letting the German’s suspect their cipher had been cracked, which in turn let them continue to read all communiqué unhindered.

Even after the war, the Germans didn’t know their cipher had been broken. Years after the war when it slowly became public knowledge that the British had been reading everything they had broadcasted, the Germans decided to take steps to protect themselves with a neat little machine developed by a German inventor named Arthur Scherbius, the Enigma Machine

The next post will cover the Enigma Machine, the mechanism and the goliath task of cracking it.

An Intro to Modulus Arithmetic

So I decided to take a break from Simon Singh’s book which I mentioned in my last two posts to take a look at some practical applications of modern cryptography in Cristof Paar and Jan Pelzl’s Understanding Cryptography: A Textbook for Students and Practitioners. The book is surprisingly informative and so far easy to read, even though it deals with a set of mathematics and code that I haven’t worked with.

The book starts of general enough, with a condensed introduction to cryptography and cryptanalysis. The authors give a brief overview the state of modern cryptography and the avenues an interested party can take to crack the codes being utilized today. One that I had briefly heard of before and would be interested in researching more about later is a side channel attack, where an attacker uses the system’s physical properties to circumvent the encryption by gleaming a little about the process. This can include anything from tapping the actual processor to read the electrical currents flowing through, to analyzing the sounds a keyboard makes when a user types in their keyphrase. Interesting as this is, it isn’t what I wanted to post about today, modulus arithmetic is.

Modulus arithmetic is more commonly known as remainder arithmetic or “clock arithmetic.” In code, the modulus operator is signified by the “%” symbol and when applied to two numbers X and Y will simply give the remainder of the two when X is divided by Y.

As Paar and Pelzl explain, even in early caesar cipher’s, all cipher text is created out of a finite set of objects. Modulus math can be used to tell us where in the set of numbers a digit/character lays after being ciphered and deciphered. What’s more, modulus arithmetic has certain fascinating properties, such as equivalency sets.

Now equivalency sets took me a while to understand completely since the concept was a bit foreign to me. Take for example 12 % 9… for the most part the answer we see and use is 3. But according to modulus arithmetic, there is an equivalency set made up of all other numbers that would also have the same remainder, that is {…, -6, 3, 12, 21, … }. This equivalency allows us to do some math with the other numbers in the set which can be very useful as we get more involved in public key cryptography.

More to come soon!

 

Vigenère’s cipher: Crypto gets serious

I’ve been reading Simon Singh’s Code Book which reads as part cryptography lesson and part historical thriller. The last time I updated we read about the cipher of Mary Queen of Scots and how it was broken through excellent spy craft and cryptanalysis. Even though most us mere mortals wouldn’t be able to break her cipher, to a trained analyst like those who served Queen Elizabeth and Walsingham her spy master, the cipher was easily broken.

Mary was at the time under house arrest in England, watched over by a stern guardian who monitored all of her communication. As Singh tells the story, Mary thought herself forgotten by the world until a young catholic named Gilbert Gifford offered his services as a courier between Mary and a young radical named Babington. It turns out that Gifford was in fact a double agent who was asked by Walsingham (Queen Elizabeth’s spymaster) to become the courier. Needless to say during the entire time he was ferreting letters back and forth between Babington and Mary, he was letting Walsingham copy the letters character by character, giving Walsingham and his cryptanalysts time to decipher them, all the while leaving Babington and Mary to believe they were communicating securely. These encrypted letters which later decrypted by Walsingham, condemn Mary Queen of Scots to death for her role in the Babington Plot against Queen Elizabeth.

Now what Singh fails to mention is of critical importance here. Singh fails to mention how Babington and Mary, who had never met and as we know never really had a secure channel of communications, were able to coordinate their initial cipher. The challenge nowadays in cryptography is that initial handshake, how did Mary and Babington manage to overcome this problem?

Around the same time another cipher was developed that Singh suggests would have saved Mary’s life had she used it, the Vigenère cipher. Vigenére was a mathematician and cryptographer who developed a new cipher that used more than one caesar cipher alphabet. According to Singh, no one really thought to use the cipher until decades later, but the polyalphabetic cipher were considerably more difficult to crack than the monoalphabetic cipher. The problem that monoalphabetic ciphers like Mary’s had was that they were susceptible to frequency analysis. Polyalphabetic ciphers were also susceptible as Charles Babbage later proves.

Babbage is more famously known for his ingenious designs that predicted the computer over a century before the first transistor was invented at Bell Labs. Babbage saw the Vigenére cipher as a challenge and used mathematics and statistics, much like before the earlier cryptanalysts did when using frequency analysis against monoalphabetic ciphers, but this time around the mathematics gets considerably more complicated.

As we can see from Babbage and the Vigenére cipher, math is becoming more and more important in cryptography. Babbage’s Victorian-era story, the story of the “father of computing” tackling a challenging puzzle of mathematics and linguistics only to break yet another cryptographic protocol foreshadows our contemporary story of hackers and cryptopunks constantly tweaking away at the systems that secure the internet and our data.

As always, I’ll have more soon. Stay tooned!

Introduction to Cryptography

I’ve always been fascinated and terrified by encryption algorithms. They’re the backbone of our web based economy and provide companies and users with some level of privacy. Of course nothing is fool proof, not even the most advanced of our encryption algorithms. It seems day after day we hear about hacker collectives that exploit a flaw in a system and extracted hashed and encrypted data that everyone fears might be cracked. I say fears, because most no one understands how these encryption algorithms work and how they really protect our data. Where are they weak and how do they shine?

For my research studio on algorithms I’ve decided to concentrate on understanding and implementing some encryption and decryption algorithms as well as playing around with some advanced mathematics, just so I can get a better idea of what it is we need in applications and to protect ourselves in an increasingly open (to spy on) world.

For this purpose, I’ve begun reading The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography as a primer for understanding modern cryptography before I start reading some more advanced texts like Understanding Cryptography: A Textbook for Students and Practitioners.

It was surprising to learn that the origins of cryptanalysis can be traced to the Muslim world after the birth of Islam. Considering the other numerous breakthroughs in the areas of arts, science and mathematics pioneered by those early Muslims, this shouldn’t have been a surprise but it was.

Hoping to find many more pleasant little surprises in the history and the code before I’m done.

New Term, New Challenges

We started a new term here at ITP, and it is really quite insane. My term consists of researching algorithms, appropriating technologies, building interactive installations, dissecting circuits, and designing games.

The amazing thing about ITP is that I can do all of these things and still feel like you’re only seeing a fraction of what there is to learn about. This place is a generalists dream come true, and a nightmare to explain concisely to anyone who hasn’t experienced it. I still have trouble telling my parents what I do.

Regardless, I hope to be able to share some of what is going on here with you.