Chiffrierer und Spione

In der heutigen Math Corner werde ich einen Blick auf ein Thema werfen, das ich beim jährlichen Science Camp für Kinder der National Children's Foundation diskutiert habe. Die Stiftung sucht Kinder und Jugendliche mit naturwissenschaftlichen Interessen. Sie müssen nicht besonders begabt sein, aber Sie müssen eine "wissenschaftliche Ader" haben. Sehr gute Schulnoten sind nicht erforderlich. Probieren Sie es aus, es könnte Ihnen gefallen. Wenn Sie ein Schüler der Oberstufe der Grundschule oder des Gymnasiums sind, bewerben Sie sich. Normalerweise machen die Eltern oder die Schule die Berichte, aber das ist nicht immer der Fall. Suchen Sie die Website der Stiftung und finden Sie es heraus.

In der Schule wird immer mehr über „Codieren“ gesprochen, womit die Tätigkeit gemeint ist, die früher als „Programmieren“ bekannt war. Dies ist ein gängiges Vorgehen unter Bildungstheoretikern. Sie graben alte Methoden aus, geben ihnen einen neuen Namen und schon geschieht der „Fortschritt“ von selbst. Es gibt mehrere Bereiche, in denen dieses zyklische Phänomen auftritt.

Man kann daraus schließen, dass ich die Didaktik abwerte. Nein. In der Entwicklung der Zivilisation kehren wir manchmal zu dem zurück, was war, verlassen wurde und jetzt wiederbelebt wird. Aber unsere Ecke ist mathematisch und nicht philosophisch.

Zur Zugehörigkeit zu einer bestimmten Gemeinschaft gehören auch „gemeinsame Symbole“, gemeinsame Lesarten, Sprüche und Gleichnisse. Wer die polnische Sprache „In Szczebrzeszyn ist ein großes Dickicht, im Schilf summt ein Käfer“ perfekt gelernt hat, wird sofort als Spion einer fremden Macht entlarvt, wenn er die Frage, was der Specht macht, nicht beantwortet. Natürlich erstickt er!

Das ist nicht nur ein Witz. Im Dezember 1944 starteten die Deutschen mit großem Aufwand ihre letzte Offensive in den Ardennen. Sie mobilisierten Soldaten, die fließend Englisch sprachen, um die Bewegung alliierter Truppen zu stören, indem sie sie beispielsweise an Kreuzungen in die falsche Richtung führten. Nach einem Moment der Überraschung begannen die Amerikaner, den Soldaten verdächtige Fragen zu stellen, deren Antworten für einen Menschen aus Texas, Nebraska oder Georgia offensichtlich gewesen wären, für jemanden, der nicht dort aufgewachsen war, jedoch undenkbar gewesen wären. Unkenntnis der Realität führte direkt zur Hinrichtung.

Auf den Punkt. Ich empfehle den Lesern das Buch von Lukasz Badowski und Zaslaw Adamashek "Labor in einer Schreibtischschublade - Mathematik". Dies ist ein wunderbares Buch, das brillant zeigt, dass Mathematik für etwas wirklich nützlich ist und dass "Mathe-Experiment" keine leeren Worte sind. Darin enthalten ist unter anderem der beschriebene Bau des „Kartonrätsels“ – ein Gerät, dessen Erstellung wir in nur fünfzehn Minuten benötigen und das wie eine seriöse Chiffriermaschine funktioniert. Die Idee selbst war so bekannt, die genannten Autoren haben sie wunderbar ausgearbeitet, und ich werde sie ein wenig ändern und in mathematischere Klamotten hüllen.

Chiffriersägen

In einer der Straßen meines Datscha-Dorfes in den Vororten von Warschau wurde kürzlich der Bürgersteig von „trlinka“ – sechseckigen Pflastersteinen – abgebaut. Die Fahrt war unbequem, aber die Seele des Mathematikers freute sich. Das Bedecken der Ebene mit regelmäßigen (d.h. regelmäßigen) Polygonen ist nicht einfach. Es können nur Dreiecke, Quadrate und regelmäßige Sechsecke sein.

Ich war mit dieser herzlichen Freude vielleicht ein bisschen ein Scherz, aber ein Sechseck ist eine wunderschöne Form. Es kann verwendet werden, um ein ziemlich erfolgreiches Verschlüsselungsgerät herzustellen. Geometrie wird helfen. Das Sechseck ist rotationssymmetrisch – es überlappt sich selbst, wenn es um den Faktor 60 Grad gedreht wird. Ein Feld, das beispielsweise oben links mit dem Buchstaben A gekennzeichnet ist Feige. 1 nach dem Drehen um diesen Winkel fällt es auch in Feld A - und dasselbe gilt für andere Buchstaben. Schneiden wir also sechs Quadrate aus dem Raster aus, jedes mit einem anderen Buchstaben. Das so erhaltene Raster legen wir auf ein Blatt Papier. Geben Sie in die freien sechs Felder sechs Buchstaben des Textes ein, den wir verschlüsseln möchten. Lassen Sie uns das Blatt um 60 Grad drehen. Es erscheinen sechs neue Felder – geben Sie die nächsten sechs Buchstaben unserer Nachricht ein.

Reis. 1. Freude an der Mathematik.

Recht Feige. 1 Wir haben den Text so codiert: „Auf dem Bahnhof steht eine riesige schwere Dampflokomotive.“

Jetzt wird ein wenig Schulmathematik nützlich sein. Auf wie viele Arten können zwei Zahlen relativ zueinander angeordnet werden?

Was für eine dumme Frage? Für zwei: entweder einer vorne oder der andere.

Großartig. Und drei Zahlen?

Es ist auch nicht schwer, alle Einstellungen aufzulisten:

123, 132, 213, 231, 312, 321.

Nun, das ist für vier! Es kann immer noch klar gesagt werden. Erraten Sie die Bestellregel, die ich eingegeben habe:

1234, 1243, 1423, 4123, 1324, 1342,

1432, 4132, 2134, 2143, 2413, 4213,

2314, 2341, 2431, 4231, 3124, 3142,

3412, 4312, 3214, 3241, 3421, 4321

Bei fünf Zahlen ergeben sich 120 mögliche Einstellungen. Nennen wir sie Permutationen. Die Anzahl der möglichen Permutationen von n Zahlen ist das Produkt von 1 · 2 · 3 · … · n, genannt сильный und sind mit einem Ausrufezeichen gekennzeichnet: 3!=6, 4!=24, 5!=120. Für die nächste Zahl 6 haben wir 6!=720. Wir werden dies nutzen, um unserem sechseckigen Verschlüsselungsschild mehr Komplexität zu verleihen.

Wir wählen eine Permutation der Zahlen von 0 bis 5, zum Beispiel 351042. Unsere sechseckige Würfelscheibe hat im mittleren Feld einen Strich – damit sie „in die Nullposition“ gebracht werden kann – mit Strich nach oben, wie in Abb. 1. Wir legen die Scheibe auf diese Weise auf ein Blatt Papier, auf das wir unseren Bericht schreiben werden, schreiben ihn aber nicht gleich, sondern drehen ihn dreimal um 60 Grad (also 180 Grad) und schreiben sechs Buchstaben hinein Leerfelder. Wir kehren in die Ausgangsposition zurück. Wir drehen das Zifferblatt fünfmal um 60 Grad, also um fünf „Zähne“ unseres Zifferblattes. Wir drucken. Die nächste Skalenposition ist die um 60 Grad um Null gedrehte Position. Die vierte Position ist 0 Grad, dies ist die Ausgangsposition.

Verstehen Sie, was passiert ist? Wir haben eine zusätzliche Chance – unsere „Maschine“ um mehr als das Siebenhundertfache zu komplizieren! Wir haben also zwei unabhängige Positionen des „Automaten“ – die Wahl eines Gitters und die Wahl einer Permutation. Das Raster kann auf 66 = 46656 Arten gewählt werden, Permutation 720. Dies ergibt 33592320 Möglichkeiten. Über 33 Millionen Chiffren! Fast etwas weniger, weil Manche Gitter lassen sich nicht aus Papier ausschneiden.

Im unteren Teil Feige. 1 Wir haben eine Nachricht, die so kodiert ist: „Ich schicke Ihnen vier Fallschirmdivisionen.“ Es ist leicht zu verstehen, dass der Feind darüber nicht informiert werden darf. Aber wird er irgendetwas davon verstehen:

TPOROPVMANVEORDISZ

JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ

auch mit der Signatur 351042?

Wir bauen Enigma – eine deutsche Verschlüsselungsmaschine

Reis. 2. Ein Beispiel für die Ersteinrichtung unserer Verschlüsselungsmaschine.

Permutationen (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).

Wie ich bereits erwähnt habe, verdanke ich die Idee, eine solche Pappmaschine zu bauen, dem Buch "Labor in einer Schublade - Mathematik". Meine „Konstruktion“ unterscheidet sich etwas von der ihrer Autoren.

Die von den Deutschen im Krieg verwendete Verschlüsselungsmaschine hatte ein genial einfaches Prinzip, ähnlich dem, das wir bei der Hex-Chiffre gesehen haben. Es ist jedes Mal das Gleiche: die harte Zuordnung eines Buchstabens zu einem anderen Buchstaben auflösen. Es muss austauschbar sein. Wie macht man das, um die Kontrolle darüber zu haben?

Wählen wir nicht irgendeine Permutation, sondern eine, die Zyklen der Länge 2 hat. Einfach gesagt, so etwas wie das hier vor ein paar Monaten beschriebene „Gaderipoluk“, das aber alle Buchstaben des Alphabets abdeckt. Vereinbaren wir 24 Buchstaben - ohne ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Wie viele solcher Permutationen? Das ist eine Aufgabe für Abiturienten (die sollten sie auf Anhieb lösen können). Wie viele? Viel? Mehrere tausend? Ja:

1912098225024001185793365052108800000000 (versuchen wir gar nicht erst, diese Zahl zu lesen). Es gibt so viele Möglichkeiten, die „Null“-Position festzulegen. Und es kann schwierig sein.

Unsere Maschine besteht aus zwei runden Scheiben. Auf einem von ihnen, der noch steht, sind Buchstaben geschrieben. Es ist ein bisschen wie das Wählrad an einem alten Telefon, bei dem man eine Nummer wählt, indem man das Wählrad ganz durchdreht. Rotary ist das zweite mit einem Farbschema. Am einfachsten ist es, sie mit einer Nadel auf einen normalen Korken zu stecken. Anstelle von Kork können Sie auch ein dünnes Brett oder dicken Karton verwenden. Lukasz Badowski und Zaslav Adamaszek empfehlen, beide CDs in eine CD-Hülle zu legen.

Stellen wir uns vor, wir möchten das Wort ARMATY (Reis. 2 und 3). Stellen Sie das Gerät auf Nullstellung (Pfeil nach oben). Der Buchstabe A entspricht F. Drehen Sie die interne Schaltung um einen Buchstaben nach rechts. Wir müssen den Buchstaben R codieren, jetzt entspricht er A. Nach der nächsten Drehung sehen wir, dass der Buchstabe M U entspricht. Die nächste Drehung (viertes Diagramm) ergibt die Entsprechung A - P. Auf dem fünften Zifferblatt haben wir T - A. Schließlich (sechster Kreis) Y – Y Der Feind wird wahrscheinlich nicht ahnen, dass unsere CFCFAs für ihn gefährlich sein werden. Und wie wird „unser“ die Depesche lesen? Sie müssen dieselbe Maschine haben, dieselbe "programmiert", dh mit derselben Permutation. Die Chiffre beginnt bei Position Null. Der Wert von F ist also A. Drehen Sie die Wählscheibe im Uhrzeigersinn. Der Buchstabe A ist nun mit R verbunden. Er dreht die Wählscheibe nach rechts und findet unter dem Buchstaben U ein M usw. Der Chiffrierer rennt zum General: „General, ich melde mich, die Waffen kommen!“

Reis. 3. Das Funktionsprinzip unseres Papier-Enigma.

Reis. 3. Das Funktionsprinzip unseres Papier-Enigma.

Die Möglichkeiten selbst einer solch primitiven Enigma sind erstaunlich. Wir können andere Ausgangspermutationen wählen. Wir können – und hier gibt es noch mehr Möglichkeiten – nicht regelmäßig eine „Serife“ nehmen, sondern in einer bestimmten, täglich wechselnden Reihenfolge, ähnlich einem Sechseck (z.B. erst drei Buchstaben, dann sieben, dann acht, vier … .. usw. .).

Wie kannst du es erraten?! Und doch für polnische Mathematiker (Marian Reevski, Heinrich von Zigalski, Jerzy Rózicki) passiert. Die auf diese Weise gewonnenen Informationen waren von unschätzbarem Wert. Zuvor hatten sie einen ebenso wichtigen Beitrag zur Geschichte unserer Verteidigung geleistet Wacław Sierpinski i Stanislaw Masurkewitschder 1920 gegen den Kodex der russischen Truppen verstieß. Das abgefangene Kabel gab Piłsudski die Möglichkeit, das berühmte Manöver vom Fluss Wieprz aus durchzuführen.

Ich erinnere mich an Waclaw Sierpinski (1882-1969). Er schien ein Mathematiker zu sein, für den die Außenwelt nicht existierte. Er konnte nicht über seine Teilnahme am Sieg im Jahr 1920 sprechen, sowohl aus militärischen als auch aus politischen Gründen (die Behörden der Polnischen Volksrepublik mochten diejenigen nicht, die uns vor der Sowjetunion verteidigten).

Reis. 4. Permutation (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Reis. 5. Schöne Dekoration, aber nicht für die Verschlüsselung geeignet. Zu regelmäßig.

Aufgabe 1. Na Feige. 4 Sie haben eine weitere Permutation, um Enigma zu erstellen. Kopieren Sie die Zeichnung auf einen Xerographen. Bauen Sie ein Auto, verschlüsseln Sie Ihren Vor- und Nachnamen. Mein CWONUE JTRYGT. Wenn Sie Ihre Notizen geheim halten müssen, verwenden Sie ein Enigma aus Pappe.

Aufgabe 2. Verschlüsseln Sie Ihren Vor- und Nachnamen eines der „Autos“, die Sie gesehen haben, aber (Achtung!) Mit einer zusätzlichen Komplikation: Wir drehen nicht eine Kerbe nach rechts, sondern nach dem Schema {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - also erst um eins, dann um zwei, dann um drei, dann um 2, dann wieder um 1, dann um 2 usw., so ein „Wavelet“ . Stellen Sie sicher, dass mein Vor- und Nachname als CZTTAK SDBITH verschlüsselt sind. Verstehst du jetzt, wie mächtig die Enigma-Maschine war?

Lösung des Problems für Abiturienten. Wie viele Konfigurationsoptionen für Enigma (in dieser Version, wie im Artikel beschrieben)? Wir haben 24 Buchstaben. Wir wählen das erste Buchstabenpaar aus - dies ist möglich

Wege. Das folgende Paar kann unter ausgewählt werden

Methoden, weiter

usw. Nach den entsprechenden Berechnungen (alle Zahlen müssen multipliziert werden) erhalten wir

151476660579404160000

Dann teilen Sie diese Zahl durch 12! (12 Fakultät), weil die gleichen Paare in einer anderen Reihenfolge erhalten werden können. Also am Ende bekommen wir "total"

316234143225,

Das sind etwas mehr als 300 Milliarden, was für moderne Supercomputer keine erstaunlich große Zahl zu sein scheint. Wenn wir jedoch die zufällige Reihenfolge der Permutationen selbst berücksichtigen, erhöht sich diese Zahl deutlich. Wir können uns auch andere Arten von Permutationen vorstellen.

Siehe auch: