Building and using a Paper Enigma

Leave a comment

img_20161130_122120

As part of the book about cryptography, math and programming I’m writing, I’m encouraging readers to assemble their own paper Enigma machine. Since it’s pretty involved, I thought I’d write an illustrated blog post about doing it. I’m going to start with a summary of the context of the Enigma – and as a summary, I’ll gloss over some likely-important stuff, and also probably get some things a bit wrong. Corrections are welcome, of course. So, here we go!

First, the whole idea of making a paper replica of the Enigma came from the amazing Alan Turing, the British mathematician who is the topic of a decent movie, a great book, and is generally credited as being a pioneer of computers, artificial intelligence, and for shortening World War II by two years (and dare I say, perhaps keeping the Nazi’s from winning?) The story isn’t all rosy: he was also gay at a time in the U.K. when that was a punishable crime, and he eventually killed himself due to his treatment by the government. It wasn’t until 2013 that the Queen pardoned and thanked him for his service. As Martin Luther King Jr. said, “The arc of the moral universe is long, but it bends towards justice.” That’s certainly true in this case.

Thinking back to World War II, the German military was kicking butt all over Europe, and their submarines were causing  all sorts of mayhem in the Atlantic. They were able to securely communicate across vast distances by sending radio messages that were encrypted with an Enigma machine. This meant that the Allies could hear their messages, but couldn’t understand them, because they didn’t have the key used to decode them. Polish mathematicians cracked the Enigma code in 1932, taking advantage of a subtle misconfiguration of how the Germans used the machines. By 1938, Germany fixed this flaw, and was able to send secure communications again.

One of the first things Turing did at Bletchley Park was to create a model of the Enigma machine using comic strips. Our paper Enigma, from Franklin Heath (a security firm in the UK), was inspired by his work. The first thing you’ll need is the PDF of the paper Enigma. Since paper in the US isn’t the same shape as in the UK (A4), I had good luck printing it on legal sized paper (11×14 inches). The kit is designed to be wrapped around a cardboard tube that is 75mm in diameter. It turns out a Pringles potato chip can has this diameter (they’re called “crisp tubes” in Britain). I didn’t want to buy Pringles, so I used a cereal box. Here’s my setup before assembly:

img_20161128_160503

Cardboard usually has a way it “likes” to be curled, and one that it resists (creases rather than curls). For this box, the preferred curl is horizontal. So I cut off the tabs at the top and bottom of the box, and curled it by hand a few times, to get the cardboard roughly in the right shape:

img_20161128_161820

Then cut out two of the strips (I chose the input/output strip and the Reflector B), and carefully tape them into bands, put the bands on both ends of the tube, and let it expand, like this:

img_20161128_161914

At this point, I put little tabs of tape inside the tube to help it hold its diameter, and fiddled with it until the bands were able to slide, but also didn’t have any slack. I tacked down the tube with a little tape, and pulled off the bands, then added a full-tube-length of packing tape to the outside-seam, like this:

img_20161128_162454

Finally, wrap the three “rotor” bands around the tube, and tape them, again checking that they can slide around the tube, without being too tight. With the three bands on, add the Input/Output and Reflector B band to the outside-ends of the tubes. Align the grey bars on these bands, and tape them to the tube: they stay put while the rotors move. When you’re done, from left to right, you’ll have the Reflector, Rotor I, Rotor II, Rotor III, then the I/O band. It should look something like this:

img_20161128_164439

Using your paper Enigma

(borrowing heavily from the Franklin Heath wiki – I will rewrite this with my own examples once the book chapter is done)

You can test your basic Enigma now. The “rotor position” part of the key is the letters between the grey bars. In the setup above, the rotor key is FAN. The next aspect of the machine is that each time you encode a character, you first “advance” the rotor, by carefully twisting its band towards you by one letter. Let’s pretend that the key was FAM, and we rotated the right band to make the rotor position FAN. After doing that, take the letter you’re encoding, and locate it on the I/O band on the right, and trace the lines from right to left. In this case, it’s nearly a straight line: A -> N -> A -> G at this point, we’re at the “reflector”, so trace the line on the reflector to see where it leads. It should be W. From there, trace the line back to the I/O band. When I did this, I got W -> I -> S -> K. K is the encrypted version of A. To encrypt the next character, you advance the right ring towards you and repeat the procedure.

With what you know so far, you should be able to decrypt the following message, with the rotors initially set at A B C:

A E F A E  J X X B N  X Y J T Y

If you get that, the rest of the Enigma is just minor tweaks to that process. We’ll go through each of them, because you need to do them all in order to decrypt real Enigma messages (which we’ll do at the end).

Advancing the Rotors

As you advance the right-most ring, eventually you’ll come back to the original configuration. If the Enigma did nothing else, it would be not too different from the Vigenère cipher – not a bad cipher (it was used during the Civil War) – but definitely not strong enough to protect against the codebreakers of the 1900’s. The next (and primary) advance of the Enigma machines was its rotor stepping process. When you are about to advance a band, look at whether the letters are grey in the line between the grey bars on the reflector and I/O bands, and

  • if the letter on the middle rotor is shaded grey, turn all three rotors one step towards you,
  • otherwise, if the letter on the right-hand rotor is shaded grey, turn the middle and right-hand rotors one step towards you,
  • otherwise, turn just the right-hand rotor one step towards you (this is the normal action).

Now the configuration won’t repeat for 26 * 26 * 26 (= 17,576) steps – much better.

To make sure you get it, here are some rotor  position scenarios. When you’re about to rotate, and the rotors are in positions:

  • F A V, because V is grey, you would advance both the right-hand and middle rotors toward you, resulting in position F B W
  • F E W, because E is gray, you advance all three rotors, resulting in G F X
  • G F X, because none of them are grey, only rotate the right-hand rotor, resulting in G F Y

Test your procedure by setting the rotors to A B R, and decrypt the message
M A B E K  G Z X S G

Double-stepping

One tweak to the above procedure (which is, so far, just like a car’s odometer), is that if, after you follow the above procedure, the middle rotor’s grey bar enters the start position, then all three rotors step again. I’m not sure if this is critical to the strength of the Enigma, but doing so is critical to compatibility with real Enigma machines.

You can test whether you understand this part by starting in position B F C, and decoding
R Z F O G  F Y H P L

Rings – changing the turnover points

The next-to-last feature of the Enigma is that which rotor positions trigger turnover could be adjusted. In the real machine, this was done by removing the rotor and moving a pin from one position to another. In our paper Enigma, it’s done by sliding rings over each of the rotors. Each ring covers up the letters underneath it, and its position determines a different configuration of the machine (is part of the message key). Ring positions are described by the position of the ring’s letter A with respect to the letter it covers. Position 1 means that the ring’s A covers the rotor’s letter A, 2 means A covers B, etc. For convenience, here’s a list of which ring letter A needs to cover for each ring setting.

Setting 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Ring A  A B C D E F G H I J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
 covers

Test whether you’ve got this by setting ring’s I, II and II to 10, 14 and 21. Then turn the rotors to set the message key (on the rings) to X Y Z  and decipher the following message:

Q K T P E  B Z I U K

Pokemon Go and graph theory

Leave a comment

Lately I’ve been focusing my efforts on teaching. One thing I’m working on is writing a book about cryptography, math and programming that is targeted at high school-aged students. One of my motivators is equity, so I’m licensing it under a creative commons license, and the source code to the book is here, on github.

Another motivator is enthusiasm – I like to convey my enthusiasm for the material to the students I’m working with. One way to do that is to tap into things they’re already enthusiastic about. For the book, it’s the innate fascination we all have about secret codes.

For this blog post, I’ve got a tidbit about graph theory that is motivated by many folks’ fascination with Pokemon Go. Pokemon Go players do a few different things: they walk around their town collecting items at Pokestops, which are associated with landmarks in the real world:

img_7499.png
(image credit: Business Insider)

Some of those items are Pokeballs, which are used to capture the Pokemon creatures that also wander around town. You can evolve and power up the Pokemon you catch to make them more powerful. The reason you care about your Pokemon’s power is that in addition to Pokemon and Pokestops, there are Gymnasiums, which are also associated with real-world landmarks, but instead of having items, they’re places where Pokemon can battle each other. I’ll skip past the part about teams because that’s not relevant, but the part that is relevant is that a Gymnasium can have up to ten different Pokemon in it, and when you battle, you can choose six of your Pokemon collection to fight against the ones in the Gymnasium. The question is: “how do you choose which Pokemon to battle?”

It’s a good question because the designers of the game created complex varieties of Pokemon (e.g., Fire, Grass, Electric, Poison, etc), and a complex hierarchy of strengths and weaknesses among them. So, for example, it’s easy to remember that if you’re going up against a Fire-type Pokemon, that a Water-type Pokemon has a strong advantage. On the other hand, Fire has an advantage against Grass and Ice. It’s a lot like rock-paper-scissors, but with over a dozen types instead of just three. Even more complex than the Big Bang Theory’s rock-paper-scissors-lizard-Spock.

Now we’re up to where Graph Theory can help. Just as this link shows the interactions between rocks, paper, scissors, lizards and Spockrpssl

In computer science, the above diagram is called a graph. It’s not the same as the graphs we draw of functions, so it’s kind of a confusing name, but you get used to it. These kinds of graphs have nodes and edges. If the edges have arrows, it’s called a directional graph (digraph for short). What this graph tells us is that an arrow from one node to another means that the node “beats” the one it points to.

We’d like a similar diagram for Pokemon Go. It’s subtly different: instead of a simple “Fire beats grass” relationship, we have “Fire is unusually strong against grass”. Even so, this is important information. With a simple cheatsheet like this, we could go up to any Gymnasium with a decent collection of Pokemon, and do serious damage. Also, we could learn which Pokemon we should add to a Gymnasium to make it stronger. So, how to do this?

I started by Googling for “Pokemon Go rock paper scissors” to get a list of the strengths and weaknesses of Pokemon creature types. This list seemed good for my purposes. I don’t know how accurate or authoritative it is, but that’s not as important as what I did with the information. What I could have done is use an art program to draw the graph. The drawback of this approach is that it is very “brittle”, meaning if I want a different layout I have a lot of work to do, or if the data is wrong, I have do a tedious search through the diagram.

What I did instead is use a tool that is designed to take a definition of a graph as its input, and to create pretty drawings of them. The tool I used is called graphviz, and it’s quite powerful and configurable.

The input to graphviz is called a “dot” file (the filenames end in .dot). Here’s my conversion of the above Pokemon database into a dot file:

digraph Battles {
 node [margin=0 fontsize=24 shape=plaintext ]
 # layout=circo
 Fire -> Steel
 Fire -> Bug
 Fire -> Ice
 Fire -> Grass
 Water -> Fire
 Water -> Ground
 Water -> Rock
 Grass -> Water
 Grass -> Ground
 Grass -> Rock
 Electric -> Water
 Electric -> Flying
 Ground -> Fire
 Ground -> Electric
 Ground -> Poison
 Ground -> Rock
 Ground -> Steel
 Rock -> Fire
 Rock -> Ice
 Rock -> Flying
 Rock -> Bug
 Fighting -> Normal
 Fighting -> Ice
 Fighting -> Rock
 Fighting -> Dark
 Fighting -> Steel
 Flying -> Bug
 Flying -> Fighting
 Flying -> Grass
 Ice -> Grass
 Ice -> Ground
 Ice -> Flying
 Ice -> Dragon
 Poison -> Grass
 Poison -> Fairy
 Psychic -> Fighting
 Psychic -> Poison
 Steel -> Fairy
 Steel -> Ice
 Steel -> Rock
 Bug -> Grass
 Bug -> Psychic
 Bug -> Dark
 Dragon -> Dragon
 Fairy -> Fighting
 Fairy -> Dragon
 Fairy -> Dark
 Ghost -> Psychic
 Ghost -> Ghost
 Dark -> Psychic
 Dark -> Ghost
}

It’s really simple: to say that Dark Pokemon are strong against Ghost Pokemon I wrote “Dark -> Ghost” and so on. Then I loaded this file into graphviz (with and without the “#” in front of layout), I got these two images:

 

If you look closely you’ll see they have the same set of relationships, they only differ in how they’re laid out. Pretty cool, huh? So if you encounter a Gymnasium that has a Nidoking (ground/poison), Rapidash (fire), Snorlax (normal) and Gyrados (flying/water) you can use this chart, and know that you could choose a Water, Water, Fighting and Electric Pokemon to defeat them. Note that some Pokemon, like Nidoking, have two types, so you want to choose an opponent that is strong against one or both types, but is not weak against either. In this case, water fills the bill. Water works against fire, then you see that the only thing good against normal is Fighting, and finally electric against flying/water.

A nice follow-on activity, now that we have this graph, is to optimize sequences of Pokemon in Gyms so that it’s as hard as possible to defeat them. You’ll note that our above example had two water-type weaknesses in a row – you’d want to avoid that. After that, you’d like to find, given a set of Pokemon, which ones you can safely trade away, because their strengths are subsumed (dominated in CS-speak) by other Pokemon. And so on — there’s a lot of meat in this graph!

Installing MITE (minecraft is too easy) mod on MacOS

Leave a comment

Thanks to a pointer from our neighbor (hi, Sten!), I decided to try to install MITE on my Mac.

It turns out the very good instructions in the MITE zipfile are very much Windows-specific. If you try to follow them as best you can on a mac, it’s probably not going to work.

Here are the Windows instructions: (interspersed with my MacOS translations)

Step 1 = Paste this folder into .minecraft versions folder if you have not already done so =

open Terminal and type

cd ~/Library/Application\ Support/minecraft

Step 2 = Copy 1.6.4.jar to this folder =

cd 1.6.4-MITE
cp ../1.6.4/1.6.4.jar original.zip

Step 3 = Rename it to 1.6.4-MITE.jar =

skip this step

Step 4 = Open 1.6.4-MITE.jar using WinZip or 7Zip =

First, in terminal type “open .” to fire up the Finder in this folder
In Finder, double-click on “original.zip” – it will create a folder called “original”

Step 5 = Delete META_INF folder inside =

In Finder, open your “original” folder, and delete the META_INF folder in there

Step 6 = Copy contents of class Files folder into 1.6.4-MITE.jar =

This is the key place where Windows and the Mac differ. If you drag the contents of “class Files” to the “original” folder, it will clobber important files. Instead, open the “class Files” folder in Finder, select all of its contents (first click on a.class, then press Cmd-a to select all), then drag those files to the “original” folder. It will ask if you want to keep or replace. IMPORTANT: hold down the Option key, and the “Skip” button turns into “Keep Both”. Select that.

This procedure does the important interleaving, then create the new, modified jar file with these commands (you have to have the “JDK” installed):

cd ../original
jar cf ../1.6.4-MITE.jar .

Step 7 = Move MITE Resource Pack 1.6.4.zip to the resourcepacks folder in .minecraft =

this is right, except drag it to “~/Library/Application Support/minecraft/resourcepacks”

Step 8 = Run the Minecraft launcher and edit your profile to use 1.6.4-MITE version =

Step 9 = Play Minecraft and select the MITE Resource Pack =

Yay – it should work!

The error message I kept getting when I followed the windows instructions was:

java.lang.NoClassDefFoundError: net/minecraft/client/main/Main

It was that error that lead me down the path of the solution. I checked the contents of my improperly-created jar file with the command

jar tf 1.6.4-MITE.jar

and saw that indeed there was no “net/minecraft/client/main/Main” entry. From there, I saw that the directory path in the “original” directory was deleted with the drag-and drop operation, and remembered the “tar” command solution to interleaving-copies (and then, thanks to Google, found the way to do this in Finder).

I hope this helps someone else install (the excellent-but-very difficult) MITE mod to minecraft. Apologies for the built-in dependencies on knowledge of “Terminal”, and assuming you’ve installed the JDK. It’s very possible you could avoid those dependencies, but this was my way of fixing the problem.

π Day programming activity

1 Comment

In our math club this afternoon, since it’s π day, I’m going to try to lead an activity where we write a program (on the Raspberry Pi, of course) that computes π. The idea I thought of (but we’ll see what the students think of as well) is to use the Monte Carlo method – guess random points (with uniform distribution) in a 2r x 2r square, and compute whether they’re “inCircle” or not (whether the distance from the center of the square <= r). Then use algebra to solve for the unknown quantity π in the formula

π r2 / 4r2 = inCircle / totalPoints

In my little Python program that does this, it pretty quickly gets to 3.14, but doesn’t get much further. Since these are 4th – 8th graders, I thought I should focus on techniques that have an intuition behind them, so Ramanujan’s fancy equations are out of the question. I’d be keen to hear other suggestions!
More

An entire music label goes “pay what you want”

Leave a comment

An entire music label goes “pay what you want”

Deep Elm’s entire catalog has gone to the “pay what you want” model. Already I have discovered (and paid for) music from three bands I’d never heard of before.

Keystone Kids’ “Things Get Shaky” is pleasant, well-done synth-pop, Lights and Motion’s “Unreleased” is really nice orchestral, post-rock, and their “Reanimation” sounds like the soundtrack to a movie I’d like to see, and Moonlit Sailor (also post-rock), is more intimate, also really good background music – especially liking their “We Come from Exploding Stars.”

I think it shows a lot of confidence to do this – believing that giving away your music is going to gain fans who are willing to pay. It’s already worked with me!

Lights & Motion’s “Unreleased”

Moonlit Sailor’s “We Come from Exploding Stars”

 

Domain Squatters Stink

Leave a comment

My previous post (3 years ago!) mentioned that discountdomainregistry was a bit wonky. Turns out they were circling the drain, and about 2 years ago were bought by web.com.  For some reason my “mecodegoodsomeday.com” domain didn’t come along with my other ones, and I had a difficult time convincing them I was the owner of the account, which interfered with my ability to renew the domain until…da da dum, a domain squatter (from Japan, of all places) registered my domain, and won’t let me have it back.  The web.com folks in charge of the snafu apologized to me, but didn’t make it better.  I’m bummed out.

Something’s up with my DNS provider

Leave a comment

I use(d) discountdomainregistry as my DNS host for mecodegoodsomeday.com and cheapimpostor.com. I got a weird spam from someone claiming to be them asking me to change my password, and shortly after, saw their site was either defaced, hijacked, or otherwise wonky.  It’s now down, and so are the DNS records for my two sites.

Hmmm.  Wonder what I should do?  Wait another day or two and find another host and try to migrate them?  It’s a puzzling state of affairs! Searching the web, I don’t see tons of other folks with my problem – I see a few tweets about the issue, so I know it’s not a “personal problem.”

[edit] Seems to be working fine now, though maybe under new management.  Feels a little iffy, but functional.

Older Entries