Ciphers and spies
In today's Math Corner, I'm going to take a look at a topic I discussed at the National Children's Foundation's annual Science Camp for kids. The foundation is looking for children and youth with scientific interests. You don't have to be extremely gifted, but you do need to have a "scientific streak." Very good school grades are not required. Try it, you might like it. If you are a senior elementary school or high school student, apply. Usually the parents or the school make the reports, but this is not always the case. Find the Foundation's website and find out.
There is more and more talk in school about "coding", referring to the activity formerly known as "programming". This is a common procedure for theoretical educators. They dig up old methods, give them a new name, and "progress" is made by itself. There are several areas where such a cyclical phenomenon occurs.
It can be concluded that I devalue didactics. No. In the development of civilization, we sometimes return to what was, was abandoned and is now being revived. But our corner is mathematical, not philosophical.
Belonging to a particular community also means "common symbols", common readings, sayings and parables. The one who perfectly learned the Polish language “there is a large thicket in Szczebrzeszyn, a beetle is buzzing in the reeds” will immediately be exposed as a spy of a foreign state if he does not answer the question of what the woodpecker is doing. Of course he's suffocating!
This is not just a joke. In December 1944, the Germans launched their last offensive in the Ardennes at great expense. They mobilized soldiers who spoke fluent English to disrupt the movement of allied troops, for example by leading them in the wrong direction at crossroads. After a moment of surprise, the Americans began to ask the soldiers suspicious questions, the answers to which would be obvious to a person from Texas, Nebraska or Georgia and inconceivable to someone who did not grow up there. Ignorance of the realities led directly to the execution.
To the point. I recommend to readers the book by Lukasz Badowski and Zaslaw Adamashek "Laboratory in a Desk Drawer - Mathematics". This is a wonderful book that brilliantly shows that mathematics is really useful for something and that "math experiment" is not empty words. It includes, among other things, the described construction of the "cardboard enigma" - a device that will take us only fifteen minutes to create and which works like a serious cipher machine. The idea itself was so well known, the mentioned authors worked it out beautifully, and I'll change it a bit and wrap it in more mathematical clothes.
hacksaws
On one of the streets of my dacha village in the suburbs of Warsaw, the pavement was recently dismantled from “trlinka” - hexagonal paving slabs. The ride was uncomfortable, but the soul of the mathematician rejoiced. Covering the plane with regular (i.e. regular) polygons is not easy. It can only be triangles, squares and regular hexagons.
Maybe I joked a little with this spiritual joy, but the hexagon is a beautiful figure. From it you can make a fairly successful encryption device. Geometry will help. The hexagon has rotational symmetry - it overlaps itself when rotated by a multiple of 60 degrees. The field marked, for example, with the letter A in the upper left fig. 1 after turning through this angle, it will also fall into box A - and the same with other letters. So let's cut out six squares from the grid, each with a different letter. We put the grid obtained in this way on a sheet of paper. In the free six fields, enter six letters of the text that we want to encrypt. Let's rotate the sheet 60 degrees. Six new fields will appear - enter the next six letters of our message.
Rice. 1. Trlinks of the joy of mathematics.
On right fig. 1 we have a text encoded in this way: "There is a huge heavy steam locomotive at the station."
Now a little school math will come in handy. In how many ways can two numbers be arranged relative to each other?
What a stupid question? For two: either one in front or the other.
Fine. And three numbers?
It is also not difficult to list all the settings:
123, 132, 213, 231, 312, 321.
Well, it's for four! It can still be clearly spelled out. Guess the order rule I put:
1234, 1243, 1423, 4123, 1324, 1342,
1432, 4132, 2134, 2143, 2413, 4213,
2314, 2341, 2431, 4231, 3124, 3142,
3412, 4312, 3214, 3241, 3421, 4321
When the digits are five, we get 120 possible settings. Let's call them permutations. The number of possible permutations of n numbers is the product 1 2 3 ... n, called сильный and marked with an exclamation point: 3!=6, 4!=24, 5!=120. For the next number 6 we have 6!=720. We'll use this to make our hexagonal cipher shield more complex.
We choose a permutation of numbers from 0 to 5, for example 351042. Our hexagonal scrambling disk has a dash in the middle field - so that it can be put "in the zero position" - a dash up, as in fig. 1. We put the disk in this way on a sheet of paper on which we have to write our report, but we do not write it right away, but turn it three times by 60 degrees (i.e. 180 degrees) and enter six letters in the empty fields. We return to the starting position. We turn the dial five times by 60 degrees, that is, by five "teeth" of our dial. We print. The next scale position is the position rotated 60 degrees around zero. The fourth position is 0 degrees, this is the starting position.
Do you understand what happened? We have an additional opportunity - to complicate our "machine" by more than seven hundred times! So, we have two independent positions of the "automaton" - the choice of the grid and the choice of the permutation. The grid can be chosen in 66 = 46656 ways, permutation 720. This gives 33592320 possibilities. Over 33 million ciphers! Almost a little less, because some grids cannot be cut out of paper.
In the lower part fig. 1 we have a message coded like this: "I am sending you four parachute divisions." It is easy to understand that the enemy should not be allowed to know about this. But will he understand any of this:
ТПОРОПВМАНВЕОРДИЗЗ
YYLOAKVMDEYCHESH,
even with signature 351042?
We are building Enigma, a German cipher machine
Rice. 2. An example of the initial setup of our encryption machine.
Permutations (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).
As I already mentioned, I owe the idea of \uXNUMXb\uXNUMXbcreating such a cardboard machine to the book "Lab in a Drawer - Mathematics". My “construction” is somewhat different from the one given by its authors.
The cipher machine used by the Germans during the war had an ingeniously simple principle, somewhat similar to the one we saw with the hex cipher. Every time the same thing: break hard assignment of a letter to another letter. It must be replaceable. How to do it in order to have control over it?
Let's choose not any permutation, but one that has cycles of length 2. Simply put, something like the "Gaderipoluk" described here a few months ago, but covering all the letters of the alphabet. Let's agree on 24 letters - without ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. How many such permutations? This is a task for high school graduates (they should be able to solve it right away). How many? A lot of? Several thousand? Yes:
1912098225024001185793365052108800000000 (let's not even try to read this number). There are so many possibilities to set the "zero" position. And it can be difficult.
Our machine consists of two round discs. On one of them, which is still standing, letters are written. It's a bit like the dial of an old phone, where you dialed a number by turning the dial all the way. Rotary is the second with a color scheme. The easiest way is to put them on a regular cork using a pin. Instead of cork, you can use a thin board or thick cardboard. Lukasz Badowski and Zasław Adamaszek recommend placing both discs in a CD box.
Imagine we want to encode the word ARMATY (Rice. 2 and 3). Set the device to zero position (arrow up). The letter A corresponds to F. Rotate the internal circuit one letter to the right. We have the letter R to encode, now it corresponds to A. After the next rotation, we see that the letter M corresponds to U. The next rotation (fourth diagram) gives the correspondence A - P. On the fifth dial we have T - A. Finally (sixth circle ) Y – Y The enemy will probably not guess that our CFCFAs will be dangerous for him. And how will “ours” read the dispatch? They must have the same machine, the same "programmed", that is, with the same permutation. The cipher starts at position zero. So the value of F is A. Turn the dial clockwise. The letter A is now associated with R. He turns the dial to the right and under the letter U finds M, etc. The cipher clerk runs to the general: “General, I’m reporting, the guns are coming!”
Rice. 3. The principle of operation of our paper Enigma.
| Rice. 3. The principle of operation of our paper Enigma. | ||
The possibilities of even such a primitive Enigma are amazing. We can choose other output permutations. We can - and there are even more opportunities here - not by one “serif” regularly, but in a certain, daily changing order, similar to a hexagon (for example, first three letters, then seven, then eight, four ... .. etc. .).
How can you guess?! And yet for Polish mathematicians (Marian Reevski, Henryk Zigalski, Jerzy Ruzicki) happened. The information thus obtained was invaluable. Previously, they had an equally important contribution to the history of our defense. Vaclav Serpinski i Stanislav Mazurkevichwho violated the code of Russian troops in 1920. The intercepted cable gave Piłsudski the opportunity to make the famous maneuver from the Vepsz River.
I remember Vaslav Sierpinski (1882-1969). He seemed like a mathematician for whom the outside world did not exist. He could not talk about his participation in the victory in 1920 both for military and ... for political reasons (the authorities of the Polish People's Republic did not like those who defended us from the Soviet Union).
Rice. 4. Permutation (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).
Rice. 5. Beautiful decoration, but not suitable for encryption. Too regularly.
Task 1. Na fig. 4 you have another permutation to create Enigma. Copy the drawing to the xerograph. Build a car, code your first and last name. My CWONUE JTRYGT. If you need to keep your notes private, use Cardboard Enigma.
Task 2. Encrypt your name and surname of one of the “cars” you saw, but (attention!) with an additional complication: we turn not one notch to the right, but according to the scheme {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - that is, first by one, then by two, then by three, then by 2, then again by 1, then by 2, etc., such a “wavelet”. Make sure my first and last name are encrypted as CZTTAK SDBITH. Now do you understand how powerful the Enigma machine was?
Problem solving for high school graduates. How many configuration options for Enigma (in this version, as described in the article)? We have 24 letters. We select the first pair of letters - this can be done on
ways. The next pair can be chosen on
ways, more
etc. After the corresponding calculations (all numbers must be multiplied), we get
151476660579404160000
Then divide that number by 12! (12 factorial), because the same pairs can be obtained in a different order. So in the end we get "total"
316234143225,
that's just over 300 billion, which doesn't seem like a staggeringly large number for today's supercomputers. However, if the random order of the permutations themselves is taken into account, this number increases significantly. We can also think of other types of permutations.
See also:
