Solved-A1: Enigma -Solution

Getting Started

Although the assignment could seem intimidating at Srst, just take it a step at a time and you’ll do great! The rest of the handout below gives you instructions on each step you should take. There is a series of functions to implement, each of which builds on the ones that came before. By the time you’ve implemented all the functions, you will have nished your Enigma simulator.

The mathematics of the Enigma cipher itself could seem mysterious at Irst. But we’ve carefully designed the functions to break it down into smaller pieces, so that you can focus on each piece in isolation. We’ve also supplied many examples below that will help you to check your understanding. Developing software in the real world always challenges you to become a little bit of an expert in your client’s domain; think of learning about Enigma as practicing that. As a side bene t, you’ll come away from this assignment understanding an important artifact in the history of computer science.

A highly recommended arts and crafts project: As you proceed with building a simulation of the Enigma machine in this assignment, it could be useful to have a completed simulator at your side. The best Enigma simulator we can recommend is this one. It’s totally worth your while to assemble this simulator. It provides excellent insight into the physical machine, especially the wiring of the rotors and the reIector. To assemble it, you need to buy a tube of Pringles potato chips, print out the paper at 100% scaling (which can be tricky because it’s A4; to help with that we provide these close-ups [1] [2] of the important parts that should be printable on letter paper), then cut out the paper pieces and wrap them around the tube.

Step 1: Pair Programming Tutorial

Pair programming is not just “having an assignment partner;” rather, it’s a speciIc way for two people to write code together, and for both of them to own the result. Please watch this video, which explains the driver and navigator model of pair programming:

Does that video have you excited about pair programming? Or are you feeling wary? Either way is okay. The purpose of pair programming in this assignment is to expose you to a tool that you can keep in your toolbox and pull out in the future when it feels right. All we ask is that you keep an open mind and give it a try.

If you’d optionally like to read more about the bene ts of pair programming, Strengthening the Case for Pair Programming by Williams et al. (2000) is a good place to start. It includes this quote:

For years, programmers in industry have claimed that by working collaboratively, they have produced higher-quality software products in shorter amounts of time. But their evidence was anecdotal and subjective: “It works” or “It feels right.” To validate these claims, we have gathered quantitative evidence showing that pair programming—two programmers working side by side at one computer on the same design, algorithm, code, or test—does indeed improve software quality and reduce time to market. Additionally, student and professional programmers consistently nd pair programming more enjoyable than working alone. Yet most who have not tried and tested pair programming reject the idea as a redundant, wasteful use of programming resources: “Why would I put two people on a job that just one can do? I can’t afford to do that!” But we have found, as Larry Constantine wrote, that “Two programmers in tandem is not redundancy; it’s a direct route to greater e ciency and better quality.”

Contact your pair: You have been paired by the instructors with another person in the class.

Please make contact with them and arrange a meeting as soon as possible.

Step 2: Get Git Going

Or, for an interactive tutorial, download and run the latest release of Git-it for your operating system.

Sit down in person with your pair-programming partner. Do the following to start your shared git repository:

1. Each of you independently should login to https://github.coecis.cornell.edu/, which is the Cornell-hosted GitHub site. Login with your Cornell NetID and password. When you create your account, we strongly recommend that you use your Cornell NetID as your username. It will make things much easier. Also, please do use the Cornell GitHub, not the public GitHub (whose URL we deliberately omit).

2. From the terminal, each of you should run these commands on your own machine:

git config –global user.name “Your Name”

git config –global user.email “your-netid@cornell.edu”

If you get an error message that says command not found , you don’t have Git installed. The VM already does have it installed, and anyone on Mac should already have it, too.

3. One of you (it really doesn’t matter which) should create a new repository, or “repo” for short. On the top right of any GitHub page, click the “+” icon, then select “New repository”. Give the repo a name, perhaps “cs3110-a1”, and change the radio button from Public to Private. A public repo would share your source code with the entire Cornell community, which would violate the Academic Integrity policies of this course. Also check “Initialize this respository with a README”. Then click “Create repository”.

4. On the new repo’s page, double-check: does it say “Private” next to the name of the repo? If not, go to “Settings”, “Danger Zone”, “Make this repository private”, and click “Make private”.

4. Click “Settings”; on the settings page click “Collaborators”, and type your partner’s NetID into the search box. Click “Add collaborator”.

4. Your partner should now click on the GitHub icon on the top left in their browser. They should see the repo you just created listed on the left as a repo to which they have access.

4. Next, on the page for the repo, click “Clone or download”. The box that opens can be set to “Clone with HTTPS” or “Clone with SSH”. Set it to HTTPS. Copy the URL from the box.

4. In your terminal, navigate to whatever directory you want to store the repo in on your local lesystem. Type git clone URL , replacing URL with the URL you copied from the box. That

will download the repo into a directory with the same name that you gave it before. Change into that directory by typing cd DIR , replacing DIR with that name.

9. Download the starter code for this assignment from CMS. Suppose you save that in ~/Downloads/a1.zip . Then from your repo directory, issue the following commands to

move the les into your repo and clean away the downloaded [le:

• mv ~/Downloads/a1.zip .

• unzip a1.zip

• rm a1.zip

A common mistake is to use a graphical le browser to copy les. If you do that, you will most likely omit copying some dotSles: les whose names start with . and most of the time

are hidden from you by graphical tools. The most likely symptom of this mistake will be that VS Code is unable to understand your OUnit test suite.

10. Continuing in the terminal in that same directory, put the starter code into source control by running:

$ git add a1

10. • git commit -m “Import release code from course website”

10. • git push

10. Your partner should now clone the repo on their own machine and verify that the starter code is present in the repo.

Congratulations! You now have a shared repository for this assignment.

Step 3: Make Sure Make Works

Run make check from the folder containing the release code. Double check that you aren’t getting any warnings about your environment, or your names or types. The make , make doc , make clean , and make finalcheck commands are also available, as in A0.

There is also a new makeIle target, make build . This command will build your source Iles, which are named enigma.ml and enigma_test.ml . Most text editors, including VS Code, will not automatically rebuild your code for you when you edit it; you are responsible for building your code by running a command. (This is different from IDEs like Eclipse.)

Tip: if you ever get errors in VS Code that say something about an “Unbound module”, you probably need to rebuild your code.

Step 4: Index

Now start pair programming. Choose one of you to be the driver and the other to be the navigator.

The navigator should now close their computer and put away any distracting devices.

Your goal is to implement the function index : char -> int in the le enigma.ml .

The driver should begin by typing code . from the directory that contains the starter code enigma.ml . That will open your project directory in VS Code. Then use VS Code’s Explorer to open enigma.ml . Both of you should read the speciIcation comment for index .

Then open enigma_test.ml and locate the unit test for index . Both of you should read it.

Now talk about index and agree on what it is supposed to do. The navigator should suggest an idea for one new unit test for the function. The driver should add that unit test to the suite. Remember, the driver is in charge of the low-level details of writing the code; the navigator is in charge of watching out for higher-level issues. The navigator should never take the keyboard away from the driver. The driver is always free to say “trust me” and continue to code for a couple moments without interruption. Barring that, the navigator should do their best to interject helpful advice, to ask helpful questions, and to problem-solve when compilation errors arise.

The driver should run make and verify that the unit tests for index are currently failing.

That’s good! It means you now have a concrete goal: get those two tests to pass.

The driver should now implement index . Hint 1: your solution should need only about one line of code. Hint 2: read the documentation of the Char.code function and think about how it could help.

The driver should run make to compile and run the test suite. Make sure that both the tests pass.

Add any other unit tests that you would like to have in the suite. Make sure all tests pass.

Finally, re-run make check to double-check that you haven’t changed the names and types of any required functions. Continue to do that after implementing each function below.

Congratulations! You’ve implemented and tested your rst function as a pair. The methodology you used is called test-driven development (TDD). You write an automated test or two, and check that those tests fail. Then you write code to make the test(s) pass. Working this way ensure that, by the time you’re done coding, you already have an automated test suite; it’s not just something you write at the end. It also capitalizes on your brain’s desire to be rewarded, because you keep getting the sweet, sweet satisfaction of a test case going from failing to passing. Finally, if you ever happen to break older code as you are writing new code, you will instantly be alerted by your older automated tests suddenly failing.

Now let’s save the work that you did in your repo:

Run git status . You should see that enigma.ml and enigma_test.ml have been modi ed.

Run git add enigma.ml enigma_test.ml to add those les to the staging area of work that you want to commit.

Run git commit . That will open the Vim editor, in which you can type a commit message. It’s important to get used to using an editor to type commit messages, so that you can write longer and more informative messages, rather than always typing them on the command line with the -m option. Vim is a modal editor.

Press i to enter insert mode. Now type your multiline commit message using the following format. In fact, feel free to use this exact commit message (assuming it’s accurate).

Implement Enigma.index

• Replaced release code implementation with our own

• Added a test case

We recommend that the rst line of the commit be just a few words, with the Xrst one capitalized. The words should complete the sentence “If you pulled this commit into your own copy of the repo, this commit would…” You’re informing the reader what value they’re getting from your commit. The remaining lines should supply details. You’ll notice that if you type too many characters on the rst line, Vim will warn you by changing colors. The reason is that

GitHub uses that Wrst line to summarize your commit on the website, and too much text makes it unsuitable as a summary.

Press the Escape key, then type :wq , and press the Enter key. Escape puts Vim into normal mode, the colon moves you to the command-line mode, and wq says to write the le you are editing to disk (i.e., save it) then quit. Vim will close.

Back at the command line, type git push . Now the navigator should get their machine back out, pull from the repo, and verify that they have the most recent version of the code.

Congratulations! That was a pretty simple function, but you’ve accomplished so much more, including pair programming and git. Feel free to have a dance party. ┏(･o･)┛♪┗ (･o･) ┓

Step 5: Enigma Tutorial

Either with your partner or separately, please watch this video, which introduces the Enigma machine

158,962,555,217,826,360,000 (Enigma Machine) – Numberphile

(The video ends abruptly; you can watch the second part here. It explains how the Enigma cipher was broken. You don’t need to understand that to complete the assignment, but it’s fun!)

The Enigma was not just a single machine, but a family of closely related machines. So keep in mind that there might be details that differ from one video to another that you watch online, or even between a video and this writeup.

Substitution ciphers. The Enigma machine implemented a substitution cipher, which encrypts a message by substituting one character for another. Such ciphers go back at least as far as Julius

Caesar, who used a simple substitution cipher to encrypt military orders. The Caesar cipher speciIed that each letter in the alphabet would be encrypted using the letter three positions later in the alphabet. For example, ‘A’ would be encrypted as ‘D’, ‘B’ would be encrypted as ‘E’, ‘C’ would be encrypted as ‘F’, and so on. The code wraps around at the end of the alphabet, so ‘X’, ‘Y’ and ‘Z’ would be encrypted as ‘A’, ‘B’, and ‘C’, respectively. Although the Caesar cipher was effective in its time (when very few people could read at all), its simple pattern of encrypting letters seems pretty obvious today.

The Enigma cipher. The Enigma machine, shown below, implemented a more complex keyed substitution cipher. The key is a secret presumably known only to the message sender and receiver; it deMnes the mapping between a plaintext letter and a ciphertext letter. For the Caesar cipher, the key amounts to the “rotate by 3” operation. The key for the Enigma cipher involved many aspects of the physical con guration of the machine; we describe these below.

(Click on that image and any of the images below to link to the website where we found the image.)

After the machine was conGgured with the key, an operator pressed a letter on a typewriter-like

keyboard, which caused a circuit to close and light up a letter on a lampboard aka lightboard, a

kind of simple display screen. (Note the two different uses of “key” in the previous sentence: the

rst refers to a cryptographic key, which is a secret used as an input to encryption and decryption algorithms; the second is in the word “keyboard”, which refers to a button that is pressed.) To encrypt a message, the operator typed the plaintext letters, the ciphertext letters would light up, and the operator would record each ciphertext letter on paper. Likewise, to decrypt a message, the operator typed the ciphertext letters, the plaintext letters would light up, and the operator would record each plaintext letter on paper.

Here is a diagram showing more of the internals of the Enigma machine:

What the diagram calls a wheel is also called a rotor in literature about the Enigma. Henceforth, we will use the term rotor. The rotors were installed next to each other on a spindle, around which they rotated. Here is a picture of three rotors:

You’ll see the alphabet, in order, on each rotor in that picture. Sometimes rotors were labeled with the alphabet, and sometimes (as in the video linked above) they were instead labeled with the integers 1..26. It makes no difference to the operation of the machine which labeling scheme was used: ‘A’ corresponds to 01, ‘B’ to 02, and so forth.

In the wiring diagram above, there is another disc at the far left of the spindle that looks something like a rotor but in fact does not rotate; it is called the reIector. Here is a picture of a reIector:

http://

As the diagram shows, when the operator typed a key on the keyboard, electrical current would ow through the plugboard to the rotors, through the reIector, back through the rotors and

plugboard, and light up a letter on the lightboard. The reIector, wheels, and plugboard are all mechanisms that could be installed in different ways into the machine. The way in which they all were collectively installed determined the key that was being used for encryption or decryption.

Here is a brief description of each of the mechanisms; we go into greater detail in later parts of this writeup:

Each rotor implements its own, distinct substitution cipher by wires that connect the 26 contacts on its left side with the 26 contacts on its right side. The combination of many rotors together on the spindle creates an even more sophisticated substitution cipher. The original Enigma machines used at the beginning of World War II had three rotors, known by the Roman-numeral designations I, II, and III, which could be placed on the spindle in any order. Later, other rotors with different wirings were manufactured, as were machines that could accept up to ve rotors on the spindle.

The reIector also implements a substitution cipher, though a less sophisticated one. It has 26 contacts only on its right side, but none on its left. Current that it receives from the right side is wired to be reIected back out that side, but in a different position. The reIector was always inserted at the leftmost side of the spindle. A keypress caused current to ow right-to-left through the rotors, through the reIector, then back through the rotors, left-to-right. The reIector’s substitution pattern caused the entire circuit to be symmetric, meaning that if ‘E’ mapped to ‘Q’ in a particular machine state, then ‘Q’ would likewise be mapped to ‘E’ in that same state. The minor advantage of this design was that the machine did not need separate modes of operation for decryption and encryption. But it turned out to be a major cryptographic weakness, enabling the code to be cracked.

The plugboard implements yet another substitution cipher, which simply swaps pairs of letters. Though the wiring of the rotors and reIector was pre-determined by how they were manufactured, the wiring of the plugboard could easily be changed by the operator by plugging cables into ports. The plugboard could have up to 13 cables inserted in it. A cable inserted between two letters caused those letters to be swapped. Even though it seems

A1: Enigma – CS 3110

simpler than a rotor, the plugboard was a major source of cryptographic strength for the Enigma cipher.

The static wheel shown above is of no interest to us. (It is effectively a no-op.)

What made the Enigma cipher especially dicult to break was that just after the operator typed a letter, and just before that letter was enciphered, the rotors moved, changing the substitution pattern. Thus, the letter ‘E’ might get mapped to a ‘Q’ the rst time it was enciphered, but to a completely different letter each successive time. The rightmost rotor stepped for every letter typed, and the other rotors stepped conditionally based on notches on the rotors: when a rotor stepped past a notch, not only did that rotor step, but also the rotor to its left. This stepping mechanism made the rotors work somewhat like a mechanical odometer.

When a rotor was installed, the operator could manually rotate it to be in any of the 26 possible orientations, based on the 26 labels appearing on the rotor (either ‘A’..’Z’ or 01..26). There was a window in the machine through which the operator could observe the top letter showing on each rotor. The letter that would be on top of the rotor at the point in time when the notch engaged was known as the turnover.

(Note: we are omitting one more Enigma mechanism, the ring setting. You can safely ignore it.

A%cionados: assume the ring setting is always ‘A’ for each rotor.

The key for the Enigma machine comprises all those physical settings: which rotors were installed, the order they were on the spindle, their initial top letters, and which pairs of letters were connected on the plugboard. An Enigma operator would set all those, then encipher a message. That message would be sent (perhaps by Morse code on a radio channel). The receiver would set their Enigma machine with the same key, type in the received ciphertext, and out would come the plaintext.

Check your understanding: Together with your partner, answer these questions. (There’s no need to turn in your answers to be graded.)

De ne the following terms: plaintext, ciphertext, key.

Describe the physical design of a rotor. How does it differ from a reIector?

How many rotors could be installed on the spindle? Were they always installed in the same order?

How does the plugboard affect the cipher?

What is the top letter of a rotor? What causes it to change? How often does it change?

Don’t worry if you are not yet 100% solid on how the Enigma cipher works. You now know enough to get started building your simulator, and we’ll Pll in the gaps as we proceed.

Step 6: Rotors

Our goal in this step is to implement functions that model how current passes through rotors.

Please note that all the examples and unit tests in this section have been carefully double checked; they do not contain any typos. If you think you’ve found a typo, try to convince your partner. The Pringles-can model is especially good at helping you to debug your understanding. If you’re both convinced, try to convince a consultant.

Rotor wiring. Here is a picture of a disassembled rotor showing some of the internal wiring:

Rather than using complicated diagrams, the wiring of a rotor is often speciXed in literature on the Enigma as a 26-character string that is a permutation of the uppercase letters of the alphabet. For example, EKMFLGDQVZNTOWYHXUSPAIBRCJ is a wiring speci cation. Let’s give that a formal de nition:

A valid wiring speci cation is a 26-character uppercase string that is a permutation of the letters of the alphabet.

A wiring speci cation has nothing to do with the order in which letters are printed on the exterior of the rotor. (Indeed, you will note that all the pictures above show the letters in alphabetical order.) Rather, the specication describes the interior wiring.

To understand a wiring speciEcation, rst forget about the letters. They are really just shorthand for a number—speci cally, the index of that letter in the alphabet. So wiring speciRcation EKMFLGDQVZNTOWYHXUSPAIBRCJ is better understood as the following list of numbers: 4, 10, 12, 5, 11, … (Now you know why we had you implement index .)

Next, let’s associate each of those numbers with its index in the list:

index in list	index in alphabet
0	4

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 13/24

Finally, think of that table as deEning a function _w, such that _{w(0) = 4}, _{w(1) = 10}, _{w(2) = 12}, w(3) = 5^, w(4) = 11^{, etc.}

The function _w we have thus constructed is what the wiring specication really denotes. A rotor has a left side and a right side, and each side has 26 contacts from which electrical current can enter or leave the rotor. If current enters the rotor from the right side at contact _i, it leaves the rotor from the left side at contact _w(i). And if current enters the rotor from the left side at contact _j, it leaves the rotor from the right side at contact _w⁻¹_(j), where _w⁻¹ denotes the inverse of _w.

Rotor orientation. There are 26 xed positions at which current can enter a rotor. (For example, if the plugboard is empty, typing ‘A’ causes current to enter the right-most rotor at position 0, ‘B’ at 1, etc.) But current entering at position _i does not necessarily connect with contact _i on the rotor, because rotors turn around the spindle. That rotation causes an offset between the positions and the contacts.

Recall that the operator can see on the top of the machine, for each rotor, one of the letters that appears as exterior label on the rotor. Also recall that those letters are printed on the rotor in alphabetical order. So the offset of the rotor can be can be determined by looking at the letter that is showing. We call that the top letter of the rotor. Here, for example, is a closeup of a three-rotor Enigma machine in which the top letters are currently RDK:

When a rotor is in its default orientation, with ‘A’ showing as the top letter, the offset of the rotor is 0: current entering at position 0 touches contact 0, position 1 touches contact 1, and so forth. But

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 14/24

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 15/24

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 16/24

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 17/24

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 18/24

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 19/24

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 20/24

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 21/24

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 22/24

http://www.cs.cornell.edu/courses/cs3110/2018fa/a1/ 23/24