This problem set is intended to help you prepare for Exam 1. You may work on it by yourself or with any number of other students of your choice, but you will need to do the exam on your own.
Regardless of whether you work alone or not, you are encouraged to discuss this assignment with other students in the class and ask and provide help in useful ways.
Remember to follow the pledge you read and signed at the beginning of the semester. For this assignment, you may consult any outside resources, including books, papers, web sites and people, you wish except for materials from previous cs1120, cs150, and cs200 courses. You may consult an outside person (e.g., another friend who is a CS major but is not in this class) who is not a member of the course staff, but that person cannot type anything in for you and all work must remain your own. That is, you can ask general questions such as "can you explain recursion to me?" or "how do lists work in Scheme?", but outside sources should never give you specific answers to problem set questions. If you use resources other than the class materials, lectures and course staff, explain what you used in your turn-in.You are strongly encouraged to take advantage of the scheduled help hours and office hours for this course.
Since making up good encrypt and decrypt functions and keeping them secret is hard, most cryptosystems are designed to be secure even if the encryption and decryption algorithms are revealed. The security relies on a key which is kept secret and known only to the sender and receiver. The key alters the encryption and decryption algorithm in some way that would be hard for someone who doesn't know the key to figure out. If the sender and receiver use the same secret key we call it a symmetric cipher. If the sender and receiver can use different keys we call it an asymmetric cipher.
Ciphertext = ((encrypt KE) Plaintext))
Plaintext = ((encrypt KD) Ciphertext))
If KE = KD it is symmetric encryption. If KE is different from KD it is asymmetric encryption.
In this problem set, you will explore a symmetric cipher based on the
Lorenz Cipher that was used by the German Army High Command to send
some of the most important and secret messages during World War
II. The Lorenz Cipher was broken by British Cryptographers at Bletchley Park.
Arguably the first electronic programmable computer,
Colossus, was designed and built by Tommy Flowers, a
Post Office engineer working at Bletchley Park during the war.
(There is a lot of arguing about what should be considered the
first computer.
Who
Invented the Computer? The Legal Battle That Changed Computing
History supports John Atanasoff's case; this Scientific
American post summarizes some of the other candidates.)
Ten Collosi were built in 1943 and 1944, and used to break some of the most important German messages during World War II. Messages broken by Colossus were crucial to the D-Day invasion since the allies were able to learn that their campaign to deceive Hitler about where the attack would come was succeeding and knew where German troops were positioned. |
Bletchley Park (Summer 2004) |
D. Mitchie, J. Good, G. Timms. General Report on Tunny, 1945. (Released to the Public Record Office in 2000). http://www.alanturing.net/tunny_report
In addition to identifying the properties that hold, you should justify your answer by:
This file contains:
In cryptography, it is usually easier to deal with 1 and 0 instead of true and false. For this problem set, use 1 to represent true and 0 to represent false. We will call each 0 or 1 a bit, since this is the smallest unit of information.
Your xor function should produce these evaluations:
> (xor 0 0) 0 > (xor 0 1) 1 |
> (xor 1 0) 1 > (xor 1 1) 0 |
Fortunately for the allies, the Nazis didn't have a way of generating and distributing perfectly random bit sequences. Instead, they generated non-random sequences of bits using rotors. The Soviet Union also used a one-time pad cipher following WWII. Because their key bits were not truly random, and because they sometimes reused keys, the NSA was able to decrypt many important KGB messages. Details of this were released in 1995, and are available at the NSA's web site. We will look at how the Lorenz cipher used xor to encrypt messages soon. First, we consider how to turn messages into sequences of bits.
Table 1 shows the letter mappings for the Baudot code. For example, the letter H is represented by 10100 while I is 00110. We can put letters together just by concatenating their encodings. For example, the string "HI" is represented in Baudot as 10100 00110. There are some values in the Baudot code that are awkward to print: carriage return, line feed, letter shift, figure shift and error. For our purposes we will use printable characters unused in the Baudot code to represent those values so we can print encrypted messages as normal strings. Table 1 shows the replacement values in parenthesis.
A | 00011 | H | 10100 | O | 11000 | V | 11110 | space | 00100 | ||||
B | 11001 | I | 00110 | P | 10110 | W | 10011 | carriage return (,) | 01000 | ||||
C | 01110 | J | 01011 | Q | 10111 | X | 11101 | line feed (-) | 00010 | ||||
D | 01001 | K | 01111 | R | 01010 | Y | 10101 | letter shift (.) | 11111 | ||||
E | 00001 | L | 10010 | S | 00101 | Z | 10001 | figure shift (!) | 11011 | ||||
F | 01101 | M | 11100 | T | 10000 | error (*) | 00000 | ||||||
G | 11010 | N | 01100 | U | 00111 |
We can use lists of ones and zeros to represent Baudot
codes. H is represented as (list 1 0 1 0 0). A
string is represented as a list of these lists: "HI" is
(list (list 1 0 1 0 0) (list 0 0 1 1 0)).
We have provided these two functions in lorenz.ss:
char-to-baudot: Character → BaudotTakes a character as input, and outputs the corresponding Baudot code represented as a list of five bits.baudot-to-char: Baudot → CharacterTakes a baudot code, represented as a list of five bits, as input and outputs the corresponding character.
Characters are represented in MzScheme using #\character. For example, #\H is the character H and #\space is the space character.
There are two useful built-in procedures for converting between a string and a list of characters:
string->list: String → ListTakes a String as input and outputs the corresponding List of Characters.list->string: List → StringTakes a List of Characters as input and outputs the corresponding String.
For example:
> (string->list "HI") (#\H #\I) > (list->string (list #\H #\I)) "HI"
Your functions should be inverses. Hence, you can test your code by
evaluating baudot-to-string composed with
string-to-baudot. For example,
(baudot-to-string (string-to-baudot "HELLO"))
should evaluate to "HELLO".
Lorenz Cipher Machine |
The first 5 wheels were called the K wheels. Each bit of the Baudot representation of a letter was xor-ed with the value showing on the respective wheel. The same process was repeated with the next 5 wheels, named the S wheels. The resulting value represented the encrypted letter. After each message letter the K wheels turn one rotation. The movement of the S wheels was determined by the positions of the final two wheels, called the M wheels.
Like most ciphers, the Lorenz machine also required a key. The key was the starting position of each of the 12 wheels. To decipher the message you simply need to start the wheels with the same position as was used to encrypt and enter the ciphertext. There were 16,033,955,073,056,318,658 possible starting positions. This made the Nazis very confident that without knowing the key (starting positions of the wheels), no one would be able to break messages encrypted using the Lorenz machine. (But, their confidence was misplaced.)
Since the full Lorenz cipher would be too hard for this problem set, we will implement a simplified version. You should be suitably amazed that the allied cryptographers in 1943 were able to build a computer to solve a problem that is still hard for us to solve today! (Of course, they did have more that a week to solve it, and more serious motivation than we can provide in this course.)
Our Lorenz machine will use 11 wheels, each with only 5 positions. The first five wheels will be the K wheels and the second five the S wheels. Each of these will only have a single starting position for all 5 that is, unlike the real Lorenz machine, for this problem set we will assume all five K wheels must start in the same position and all five S wheels must start in the same position.
The final wheel will act as the M wheel. After each letter all the K wheels and the M wheel should rotate. If the M wheel shows a 1 the S wheels should also rotate, but if the M wheel shows a 0 the S wheels do not rotate.
We have provided 3 lists that represent the wheels. The first is called K-wheels and is a list of lists, each of the inner lists containing the 5 settings. The definition is:
(define K-wheels (list (list 1 1 0 1 0) (list 0 1 0 0 1) (list 1 0 0 1 0) (list 1 1 1 0 1) (list 1 0 0 0 1))).
There is a similar list called S-wheels to represent the S wheels of our simulated machine.
The final list represents the M wheels and is just a single list. The definition is:
(define M-wheel (list 0 0 1 0 1))
To rotate our wheels, we will take the number at the front of the list and move it to the back. Thus, the first number in the list represents the current position of the wheel.
Next, we define similar procedures that work on a list of wheels at a time instead of a single wheel.
Now that we can rotate our wheels, we simulate the Lorenz machine using our K and S wheels. Since both sets of wheels are doing the same thing, we should be able to write one procedure that will work with either the K wheels or the S wheels.
We now have all the procedures we need to implement our simplified Lorenz machine. A quick review of how the machine should work:
> (do-lorenz (string-to-baudot "COOKIE") K-wheels S-wheels M-wheel)
((1 1 0 1 0) (0 0 0 0 1) (1 1 0 0 1) (1 0 0 0 1) (0 0 1 1 1) (1 1 0 1 1))
[Hints]
You should now be able to encrypt strings using the simplified Lorenz cipher. To test it, call your lorenz function with a string and offsets of your choice to produce ciphertext. Since our encryption and decryption functions are the same, if you evaluate lorenz again using the ciphertext and the same offsets you should get your original message back. For example:
> (lorenz "CAKE" 1 2 3)
"BNR!"
> (lorenz "BNR!" 1 2 3)
"CAKE"
The messages were sent to John Tiltman at Bletchley Park. Tiltman was able to discern both messages and determine the generated key. The messages were then passed on to Bill Tutte who, after two months of work, figured out the complete structure of the Lorenz machine only from knowing the key it generated. The British were then able to break the Lorenz codes, but much of the work needed to be done by hand, which took a number of weeks to complete. By the time the messages were decrypted they were mostly useless.
The problem was given to Tommy Flowers, an electronics engineer from the Royal Post Office. Flowers designed and built a device called Colossus that worked primarily with electronic valves. The Colossus was the first electronic programmable computer. It was able to decrypt the Lorenz messages in a matter of hours, a huge improvement from the previous methods. The British built ten more Colossi and were able to decrypt an enormous amount of messages sent between Hitler and his high commanders. The British kept Colossus secret until the 1970s. After the war, eight of the Colossi were quickly destroyed and the remaining two were destroyed in 1960 and all drawings were burnt. The details of the breaking of the Lorenz Cipher were kept secret until 2000, but are now available at http://www.codesandciphers.org.uk/documents/newman/newmix.htm.
Our simplified cipher will be much easier to break. Since there are only 5 starting positions for the K wheels, 5 for the S wheels, and 5 for the M wheel, there are only 125 different keys. This is such a small number that we can simply try every possibility and look at the results to find the original message. Breaking a cipher by trying all possible key values is called a brute-force attack.
Remember to call the passed-in procedure once on each decoded string (i.e., many times total), not once on a big list of strings. To put it another way, your call to the passed-in procedure should be inside, not outside.
a. Describe how the amount of work needed to break a Lorenz-encrypted message grows as a function of the number of wheel positions, n, using Θ notation. Assume the message length and number of wheels are fixed.
b. Suppose instead that it was possible to add S and K wheels to the Lorenz cipher, and w represents the number of S and K wheels (for example, for the cipher machine in the problem set, w is 5). Describe how the amount of work needed to break a Lorenz-encrypted message grows as a function of w, using Θ notation. Assume the message length and number of wheel positions are fixed.
c. If the Nazis had learned of Bletchley Park's success in breaking the Lorenz cipher during the war, what changes that could be done without building and redistributing completely new cipher machines, would be most likely to prevent further successful cryptanalysis?
If you are working with a partner, you should each submit your own answer to this in the version of ps4.ss you submit electronically.
If you are working with a partner, you should each submit your own answer to this in the version of ps4.ss you submit electronically.
The creators of the fractals that get the most votes will receive extra credit and public acclaim.
This message was encrypted using a Lorenz-like cipher, but unlike the ciphertext for Question 14 (and the machine you simulated to solve that), the wheels in each group are not necessarily all rotated by the same amount. So, each of the five K-wheels, each of the five S-wheels, and the one M-wheel can be rotated by any amount. This means instead of having 125 possible initial wheel settings, this machine has 511 = 48828125 possible settings.
Solving this challenge is worth at least one extra credit point (and potentially multiple depending on how you solve it), and is open until solved. Email your solution to cs1120-staff@cs.virginia.edu.
This problem has already been solved for Fall 2010.
Note: this is definitely a challenging problem, but trivially easy compared to breaking the actual Lorenz cipher as was done at Bletchley Park in 1943! (Hint: The encrypted message is in English, but you definitely don't want to look at 48 million output strings by hand to see which one is English!)
Colossus (Original, 1943) |
Colossus (Rebuilt, 2004) |
Thomas Jefferson's instructions to Captain Lewis for the
Expedition to the Pacific.
The complete text is available from
http://www.th-jefferson.org/html/instructions.html.