Note: The second edition of this book is available under the title Cracking Codes with Python

“I couldn’t help but overhear, probably because I was eavesdropping.”

 

Anonymous

 

What is Cryptography?

Look at the following two pieces of text:

“Zsijwxyfsi niqjsjxx gjyyjw. Ny nx jnymjw ktqqd tw bnxitr; ny nx anwyzj ns bjfqym fsi anhj ns utajwyd. Ns ymj bnsyjw tk tzw qnkj, bj hfs jsotd ns ujfhj ymj kwznyx bmnhm ns nyx xuwnsl tzw nsizxywd uqfsyji. Htzwynjwx tk lqtwd, bwnyjwx tw bfwwntwx, xqzrgjw nx ujwrnyyji dtz, gzy tsqd zuts qfzwjqx.”

“Flwyt tsytbbnz jqtw yjxndwri iyn fqq knqrqt xj mh ndyn jxwqswbj. Dyi jjkxxx sg ttwt gdhz js jwsn; wnjyiyb aijnn snagdqt nnjwww, xstsxsu jdnxzz xkw znfs uwwh xni xjzw jzwyjy jwnmns mnyfjx. Stjj wwzj ti fnu, qt uyko qqsbay jmwskj. Sxitwru nwnqn nxfzfbl yy hnwydsj mhnxytb myysyt.”

 

The text on the left side is a secret message. The message has been encrypted, or turned into a secret code. It will be completely unreadable to anyone who doesn’t know how to decrypt it (that is, turn it back into the plain English message.) This book will teach you how to encrypt and decrypt messages.

The message on the right is just random gibberish with no hidden meaning whatsoever. Encrypting your written messages is one way to keep them secret from other people, even if they get their hands on the encrypted message itself. It will look exactly like random nonsense.

Cryptography is the science of using secret codes. A cryptographer is someone who uses and studies secret codes. This book will teach you what you need to know to become a cryptographer.

Of course, these secret messages don’t always stay secret. A cryptanalyst is someone who can hack secret codes and read other people’s encrypted messages. Cryptanalysts are also called code breakers or hackers. This book will also teach you what you need to know to become a cryptanalyst. Unfortunately the type of hacking you learn in this book isn’t dangerous enough to get you in trouble with the law. (I mean, fortunately.)

Spies, soldiers, hackers, pirates, royalty, merchants, tyrants, political activists, Internet shoppers, and anyone who has ever needed to share secrets with trusted friends have relied on cryptography to make sure their secrets stay secret.

Codes vs. Ciphers

The development of the electric telegraph in the early 19^th century allowed for near-instant communication through wires across continents. This was much faster than sending a horseback rider carrying a bag of letters. However, the telegraph couldn’t directly send written letters drawn on paper. Instead it could send electric pulses. A short pulse is called a “dot” and a long pulse is called a “dash”.

Figure 1-1. Samuel Morse April 27, 1791 – April 2, 1872	Figure 1-2. Alfred Vail September 25, 1807 – January 18, 1859
In order to convert these dots and dashes to English letters of the alphabet, an encoding system (or code) is needed to translate from English to electric pulse code (called encoding) and at the other end translate electric pulses to English (called decoding). The code to do this over telegraphs (and later, radio) was called Morse Code, and was developed by Samuel Morse and Alfred Vail. By tapping out dots and dashes with a one-button telegraph, a telegraph operator could communicate an English message to someone on the other side of the world almost instantly! (If you’d like to learn Morse code, visit http://invpy.com/morse.)	A ● ▬   T ▬ B ▬ ● ● ●   U ● ● ▬ C ▬ ● ▬ ●   V ● ● ● ▬ D ▬ ● ●   W ● ▬ ▬ E ●   X ▬ ● ● ▬ F ● ● ▬ ●   Y ▬ ● ▬ ▬ G ▬ ▬ ●   Z ▬ ▬ ● ● H ● ● ● ●       I ● ●       J ● ▬ ▬ ▬   1 ● ▬ ▬ ▬ ▬ K ▬ ● ▬   2 ● ● ▬ ▬ ▬ L ● ▬ ● ●   3 ● ● ● ▬ ▬ M ▬ ▬   4 ● ● ● ● ▬ N ▬ ●   5 ● ● ● ● ● O ▬ ▬ ▬   6 ▬ ● ● ● ● P ● ▬ ▬ ●   7 ▬ ▬ ● ● ● Q ▬ ▬ ● ▬   8 ▬ ▬ ▬ ● ● R ● ▬ ●   9 ▬ ▬ ▬ ▬ ● S ● ● ●   0 ▬ ▬ ▬ ▬ ▬ Figure 1-3. International Morse Code, with characters represented as dots and dashes.

Codes are made to be understandable and publicly available. Anyone should be able to look up what a code’s symbols mean to decode an encoded message.

Making a Paper Cipher Wheel

Before we learn how to program computers to do encryption and decryption for us, let’s learn how to do it ourselves with simple paper tools. It is easy to turn the understandable English text (which is called the plaintext) into the gibberish text that hides a secret code (called the ciphertext). A cipher is a set of rules for converting between plaintext and ciphertext. These rules often use a secret key. We will learn several different ciphers in this book.

Let’s learn a cipher called the Caesar cipher. This cipher was used by Julius Caesar two thousand years ago. The good news is that it is simple and easy to learn. The bad news is that because it is so simple, it is also easy for a cryptanalyst to break it. But we can use it as a simple learning exercise. More information about the Caesar cipher is given on Wikipedia: http://en.wikipedia.org/wiki/Caesar_cipher.

To convert plaintext to ciphertext using the Caesar cipher, we will create something called a cipher wheel (also called a cipher disk). You can either photocopy the cipher wheel that appears in this book, or print out the one from http://invpy.com/cipherwheel. Cut out the two circles and lay them on top of each other like in Figure 1-8.

 

 

 

Figure 1-4. The inner circle of the cipher wheel cutout.

 

Figure 1-5. The outer circle of the cipher wheel cutout.

 

Don’t cut out the page from this book!

Just make a photocopy of this page or print it from http://invpy.com/cipherwheel.

Figure 1-6. Cutting out the cipher wheel circles.

Figure 1-7. The cut-out circles.

Figure 1-8. The completed cipher wheel.

 

After you cut out the circles, place the smaller one in the middle of the larger one. Put a pin or brad through the center of both circles so you can spin them around in place. You now have a tool for creating secret messages with the Caesar cipher.

A Virtual Cipher Wheel

There is also a virtual cipher wheel online if you don’t have scissors and a photocopier handy. Open a web browser to http://invpy.com/cipherwheel to use the software version of the cipher wheel. To spin the wheel around, click on it with the mouse and then move the mouse cursor around until the key you want is in place. Then click the mouse again to stop the wheel from spinning.

Figure 1-9. The online cipher wheel.

 

How to Encrypt with the Cipher Wheel

First, write out your message in English on paper. For this example we will encrypt the message, “The secret password is Rosebud.” Next, spin the inner wheel around until its letters match up with letters in the outer wheel. Notice in the outer wheel there is a dot next to the letter A. Look at the number in the inner wheel next to the dot in the outer wheel. This number is known the encryption key.

The encryption key is the secret to encrypting or decrypting the message. Anyone who reads this book can learn about the Caesar cipher, just like anyone who reads a book about locks can learn how a door lock works. But like a regular lock and key, unless they have the encryption key, they will not be able to unlock (that is, decrypt) the secret encrypted message. In Figure 1-9, the outer circle’s A is over the inner circle’s number 8. That means we will be using the key 8 to encrypt our message. The Caesar cipher uses the keys from 0 to 25. Let’s use the key 8 for our example. Keep the encryption key a secret; the ciphertext can be read by anyone who knows that the message was encrypted with key 8.

 

 

For each letter in our message, we will find where it is in the outer circle and replace it with the lined-up letter in the inner circle. The first letter in our message is T (the first “T” in “The secret…”), so we find the letter T in the outer circle, and then find the lined-up letter in the inner circle. This letter is B, so in our secret message we will always replace T’s with B’s. (If we were using some other encryption key besides 8, then the T’s in our plaintext would be replaced with a different letter.)

The next letter in our message is H, which turns into P. The letter E turns into M. When we have encrypted the entire message, the message has transformed from “The secret password is Rosebud.” to “Bpm amkzmb xiaaewzl qa Zwamjcl.” Now you can send this message to someone (or keep it written down for yourself) and nobody will be able to read it unless you tell them the secret encryption key (the number 8).

Figure 1-10. A message encrypted with the cipher wheel.

Each letter on the outer wheel will always be encrypted to the same letter on the inner wheel. To save time, after you look up the first T in “The secret…” and see that it encrypts to B, you can replace every T in the message with B. This way you only need to look up a letter once.

How to Decrypt with the Cipher Wheel

To decrypt a ciphertext, go from the inner circle to the outer circle. Let’s say you receive this ciphertext from a friend, “Iwt ctl ephhldgs xh Hldgsuxhw.” You and everyone else won’t be able to decrypt it unless you know the key (or unless you are a clever hacker). But your friend has decided to use the key 15 for each message she sends you.

Line up the letter A on the outer circle (the one with the dot below it) over the letter on the inner circle that has the number 15 (which is the letter P). The first letter in the secret message is I, so we find I on the inner circle and look at the letter next to it on the outer circle, which is T. The W in the ciphertext will decrypt to the letter H. One by one, we can decrypt each letter in the ciphertext back to the plaintext, “The new password is Swordfish.”

 

 

If we use an incorrect key like 16 instead of the correct key 15, the decrypted message is “Sgd mdv ozrrvnqc hr Rvnqcehrg.” This plaintext doesn’t look plain at all. Unless the correct key is used, the decrypted message will never be understandable English.

A Different Cipher Tool: The St. Cyr Slide

Figure 1-11. Photocopy these strips to make a St. Cyr Slide.

There’s another paper tool that can be used to do encryption and decryption, called the St. Cyr slide. It’s like the cipher wheel except in a straight line. Photocopy the image of the St. Cyr slide on the following page (or print it out from http://invpy.com/stcyrslide) and cut out the three strips. Tape the two alphabet strips together, with the black box A next to the white box Z on the other strip. Cut out the slits on either side of the main slide box so that the taped-together strip can feed through it. It should look like this: Figure 1-12. The completed St. Cyr Slide When the black box A is underneath the letter H (and the number 7), then to encrypt you must find where the plaintext letter is on the long strip, and replace it with the letter above it. To decrypt, find the ciphertext letter on the top row of letters and replace it with the letter on the long strip below it. The two slits on the larger box will hide any extra letters so that you only see one of each letter on the slide for any key. The benefit of the St. Cyr slide is that it might be easier to find the letters you are looking for, since they are all in a straight line and will never be upside down like they sometimes are on the cipher wheel. A virtual and printable St. Cyr slide can be found at http://invpy.com/stcyrslide.

 

Practice Exercises, Chapter 1, Set A

Practice exercises can be found at http://invpy.com/hackingpractice1A.

Don’t ignore the practice exercises!

There isn’t enough room in this book to put in all the practice exercises, but they’re still important.

You don’t become a hacker by just reading about hacking and programming. You have to actually do it!

 

Doing Cryptography without Paper Tools

The cipher wheel and St. Cyr slide are nice tools to do encryption and decryption with the Caesar cipher. But we can implement the Caesar cipher with just pencil and paper.

Write out the letters of the alphabet from A to Z with the numbers from 0 to 25 under each letter. 0 goes underneath the A, 1 goes under the B, and so on until 25 is under Z. (There are 26 letters in the alphabet, but our numbers only go up to 25 because we started at 0, not 1.) It will end up looking something like this:

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12

 

N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

 

With the above letters-to-numbers code, we can use numbers to represent letters. This is a very powerful concept, because math uses numbers. Now we have a way to do math on letters.

Now to encrypt we find the number under the letter we wish to encrypt and add the key number to it. This sum will be the number under the encrypted letter. For example, we encrypt, “Hello. How are you?” with the key 13. First we find the number under the H, which is 7. Then we add the key to this number. 7 + 13 = 20. The number 20 is under the letter U, which means the letter H encrypts to the letter U. To encrypt the letter E, we add the 4 under E to 13 to get 17. The number above 17 is R, so E gets encrypted to R. And so on.

This works fine until we get to the letter O. The number under O is 14. But when we add 14 + 13 we get 27. But our list of numbers only goes up to 25. If the sum of the letter’s number and the key is 26 or more, we should subtract 26 from it. So 27 – 26 is 1. The letter above the number 1 is B. So the letter O encrypts to the letter B when we are using the key 13. One by one, we can then encrypt the letters in, “Hello. How are you?” to “Uryyb. Ubj ner lbh?”

So the steps to encrypt a letter are:

1. Decide on a key from 1 to 25. Keep this key secret!

2. Find the plaintext letter’s number.

3. Add the key to the plaintext letter’s number.

4. If this number is larger than 26, subtract 26.

5. Find the letter for the number you’ve calculated. This is the ciphertext letter.

6. Repeat steps 2 to 5 for every letter in the plaintext message.

Look at the following table to see how this is done with each letter in “Hello. How are you?” with key 13. Each column shows the steps for turning the plaintext letter on the left to the ciphertext letter on the right.

Table 1-1. The steps to encrypt “Hello. How are you?” with paper and pencil.

 

To decrypt, you will have to understand what negative numbers are. If you don’t know how to add and subtract with negative numbers, there is a tutorial on it here: http://invpy.com/neg.

To decrypt, subtract the key instead of adding it. For the ciphertext letter B, the number is 1. Subtract 1 – 13 to get -12. Like our “subtract 26” rule for encrypting, when we are decrypting and the result is less than 0, we have an “add 26” rule. -12 + 26 is 14. So the ciphertext letter B decrypts back to letter O.

Table 1-2. The steps to decrypt the ciphertext with paper and pencil.

 

As you can see, we don’t need an actual cipher wheel to do the Caesar cipher. If you memorize the numbers and letters, then you don’t even need to write out the alphabet with the numbers under them. You could just do some simple math in your head and write out secret messages.

Practice Exercises, Chapter 1, Set B

Practice exercises can be found at http://invpy.com/hackingpractice1B.

Double-Strength Encryption?

You might think that encrypting a message twice with two different keys would double the strength of our encryption. But this turns out not to be the case with the Caesar cipher (and most other ciphers). Let’s try double-encrypting a message to see why.

If we encrypt the word “KITTEN” with the key 3, the resulting cipher text would be “NLWWHQ”. If we encrypt the word “NLWWHQ” with the key 4, the resulting cipher text of that would be “RPAALU”. But this is exactly the same as if we had encrypted the word “KITTEN” once with a key of 7. Our “double” encryption is the same as normal encryption, so it isn’t any stronger.

The reason is that when we encrypt with the key 3, we are adding 3 to plaintext letter’s number. Then when we encrypt with the key 4, we are adding 4 to the plaintext letter’s number. But adding 3 and then adding 4 is the exact same thing as adding 7. Encrypting twice with keys 3 and 4 is the same as encrypting once with the key 7.

For most encryption ciphers, encrypting more than once does not provide additional strength to the cipher. In fact, if you encrypt some plaintext with two keys that add up to 26, the ciphertext you end up with will be the same as the original plaintext!

Programming a Computer to do Encryption

The Caesar cipher, or ciphers like it, were used to encrypt secret information for several centuries. Here’s a cipher disk of a design invented by Albert Myer that was used in the American Civil War in 1863.

Figure 1-13. American Civil War Union Cipher Disk at the National Cryptologic Museum.

If you had a very long message that you wanted to encrypt (say, an entire book) it would take you days or weeks to encrypt it all by hand. This is how programming can help. A computer could do the work for a large amount of text in less than a second! But we need to learn how to instruct (that is, program) the computer to do the same steps we just did.

We will have to be able to speak a language the computer can understand. Fortunately, learning a programming language isn’t nearly as hard as learning a foreign language like Japanese or Spanish. You don’t even need to know much math besides addition, subtraction, and multiplication. You just need to download some free software called Python, which we will cover in the next chapter.