Κρυπτογράφηση και κατάσκοποι

Στη σημερινή Γωνιά των Μαθηματικών, θα ρίξω μια ματιά σε ένα θέμα που συζήτησα στην ετήσια Επιστημονική Κατασκήνωση του Εθνικού Ιδρύματος για παιδιά για παιδιά. Το ίδρυμα αναζητά παιδιά και νέους με επιστημονικά ενδιαφέροντα. Δεν χρειάζεται να είστε εξαιρετικά προικισμένοι, αλλά χρειάζεται να έχετε ένα «επιστημονικό σερί». Δεν απαιτούνται πολύ καλοί σχολικοί βαθμοί. Δοκιμάστε το, μπορεί να σας αρέσει. Εάν είστε μαθητής δημοτικού ή γυμνασίου, κάντε αίτηση. Συνήθως οι γονείς ή το σχολείο κάνουν τις αναφορές, αλλά αυτό δεν συμβαίνει πάντα. Βρείτε την ιστοσελίδα του Ιδρύματος και μάθετε.

Γίνεται όλο και περισσότερος λόγος στο σχολείο για την «κωδικοποίηση», αναφερόμενη στη δραστηριότητα που παλαιότερα ήταν γνωστή ως «προγραμματισμός». Αυτή είναι μια κοινή διαδικασία μεταξύ των θεωρητικών της εκπαίδευσης. Ξεθάβουν παλιές μεθόδους, τους δίνουν νέο όνομα και η «πρόοδος» συμβαίνει από μόνη της. Υπάρχουν πολλές περιοχές όπου εμφανίζεται αυτό το κυκλικό φαινόμενο.

Μπορεί κανείς να συμπεράνει ότι απαξιώνω τη διδακτική. Οχι. Στην ανάπτυξη του πολιτισμού, μερικές φορές επιστρέφουμε σε αυτό που ήταν, εγκαταλείφθηκε και τώρα αναβιώνει. Αλλά η γωνιά μας είναι μαθηματική, όχι φιλοσοφική.

Το να ανήκεις σε μια συγκεκριμένη κοινότητα σημαίνει επίσης «κοινά σύμβολα», κοινές αναγνώσεις, ρήσεις και παραβολές. Όποιος έχει μάθει άψογα την πολωνική γλώσσα «υπάρχει ένα μεγάλο αλσύλλιο στο Szczebrzeszyn, ένα σκαθάρι βουίζει στα καλάμια» θα εκτεθεί αμέσως ως κατάσκοπος μιας ξένης δύναμης αν δεν απαντήσει στην ερώτηση τι κάνει ο δρυοκολάπτης. Φυσικά και πνίγεται!

Αυτό δεν είναι απλώς ένα αστείο. Τον Δεκέμβριο του 1944, οι Γερμανοί εξαπέλυσαν την τελική τους επίθεση στις Αρδέννες με μεγάλα έξοδα. Κινητοποίησαν στρατιώτες που μιλούσαν άπταιστα αγγλικά για να διαταράξουν την κίνηση των συμμαχικών στρατευμάτων, για παράδειγμα οδηγώντας τους σε λάθος κατεύθυνση σε σταυροδρόμια. Μετά από μια στιγμή έκπληξης, οι Αμερικανοί άρχισαν να κάνουν στους στρατιώτες ύποπτες ερωτήσεις, οι απαντήσεις στις οποίες θα ήταν προφανείς σε ένα άτομο από το Τέξας, τη Νεμπράσκα ή τη Τζόρτζια, αλλά αδιανόητες για κάποιον που δεν είχε μεγαλώσει εκεί. Η άγνοια της πραγματικότητας οδήγησε άμεσα στην εκτέλεση.

Μέχρι κάποιο σημείο. Προτείνω στους αναγνώστες το βιβλίο των Lukasz Badowski και Zaslaw Adamashek «Εργαστήριο σε συρτάρι γραφείου – Μαθηματικά». Αυτό είναι ένα υπέροχο βιβλίο που δείχνει περίφημα ότι τα μαθηματικά είναι πραγματικά χρήσιμα για κάτι και ότι το "μαθηματικό πείραμα" δεν είναι κενές λέξεις. Περιλαμβάνει, μεταξύ άλλων, την περιγραφείσα κατασκευή του «χάρτου αινίγματος» - μιας συσκευής που θα μας πάρει μόλις δεκαπέντε λεπτά για να δημιουργήσουμε και η οποία λειτουργεί σαν μια σοβαρή μηχανή κρυπτογράφησης. Η ίδια η ιδέα ήταν τόσο γνωστή, οι αναφερόμενοι συγγραφείς την έφτιαξαν όμορφα, και θα την αλλάξω λίγο και θα την τυλίξω με πιο μαθηματικά ρούχα.

Σιδηροπρίονα κρυπτογράφησης

Σε έναν από τους δρόμους του χωριού μου ντάτσα στα προάστια της Βαρσοβίας, το πεζοδρόμιο αποσυναρμολογήθηκε πρόσφατα από "trlinka" - εξαγωνικές πλάκες πλακόστρωτου. Η βόλτα ήταν άβολη, αλλά η ψυχή του μαθηματικού χάρηκε. Η κάλυψη του επιπέδου με κανονικά (δηλαδή κανονικά) πολύγωνα δεν είναι εύκολη. Μπορεί να είναι μόνο τρίγωνα, τετράγωνα και κανονικά εξάγωνα.

Μπορεί να αστειεύτηκα λίγο με αυτή την εγκάρδια χαρά, αλλά το εξάγωνο είναι ένα όμορφο σχήμα. Μπορεί να χρησιμοποιηθεί για την κατασκευή μιας αρκετά επιτυχημένης συσκευής κρυπτογράφησης. Η γεωμετρία θα βοηθήσει. Το εξάγωνο έχει περιστροφική συμμετρία - επικαλύπτεται όταν περιστρέφεται κατά 60 μοίρες. Ένα πεδίο σημειωμένο, για παράδειγμα, με το γράμμα A στο επάνω αριστερό μέρος Σύκο. 1 αφού στρίψει από αυτή τη γωνία, θα πέσει επίσης στο πλαίσιο Α - και το ίδιο με άλλα γράμματα. Ας κόψουμε λοιπόν έξι τετράγωνα από το πλέγμα, το καθένα με διαφορετικό γράμμα. Βάζουμε το πλέγμα που λαμβάνεται με αυτόν τον τρόπο σε ένα φύλλο χαρτιού. Στα ελεύθερα έξι πεδία, εισάγουμε έξι γράμματα του κειμένου που θέλουμε να κρυπτογραφήσουμε. Ας περιστρέψουμε το φύλλο κατά 60 μοίρες. Θα εμφανιστούν έξι νέα πεδία - εισάγετε τα επόμενα έξι γράμματα του μηνύματός μας.

Ρύζι. 1. Trlinks της χαράς στα μαθηματικά.

Στα δεξιά Σύκο. 1 έχουμε το κείμενο κωδικοποιημένο με αυτόν τον τρόπο: «Υπάρχει μια τεράστια βαριά ατμομηχανή στον σταθμό».

Τώρα θα σας φανούν χρήσιμα λίγα σχολικά μαθηματικά. Με πόσους τρόπους μπορούν να ταξινομηθούν δύο αριθμοί μεταξύ τους;

Τι ηλίθια ερώτηση; Για δύο: είτε το ένα μπροστά είτε το άλλο.

Εξαιρετική. Και τρεις αριθμοί;

Δεν είναι επίσης δύσκολο να παραθέσουμε όλες τις ρυθμίσεις:

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

Λοιπόν, για τέσσερα! Μπορεί ακόμα να δηλωθεί ξεκάθαρα. Μαντέψτε τον κανόνα σειράς που έβαλα:

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

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

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

3412, 4312, 3214, 3241, 3421, 4321

Όταν υπάρχουν πέντε αριθμοί, έχουμε 120 πιθανές ρυθμίσεις. Ας τους φωνάξουμε μεταθέσεις. Ο αριθμός των πιθανών μεταθέσεων n αριθμών είναι το γινόμενο του 1 · 2 · 3 · … · n, που ονομάζεται ισχυρή και σημειώνονται με θαυμαστικό: 3!=6, 4!=24, 5!=120. Για τον επόμενο αριθμό 6 έχουμε 6!=720. Θα το χρησιμοποιήσουμε για να προσθέσουμε περισσότερη πολυπλοκότητα στην εξαγωνική ασπίδα κρυπτογράφησης.

Επιλέγουμε μια μετάθεση αριθμών από το 0 έως το 5, για παράδειγμα 351042. Ο εξαγωνικός μας δίσκος σύγχυσης έχει μια παύλα στο μεσαίο πεδίο - έτσι ώστε να μπορεί να τοποθετηθεί "στη θέση μηδέν" - με μια παύλα προς τα πάνω, όπως στο Σχ. 1. Τοποθετούμε τον δίσκο με αυτόν τον τρόπο σε ένα φύλλο χαρτί στο οποίο θα γράψουμε την αναφορά μας, αλλά δεν το γράφουμε αμέσως, αλλά τον περιστρέφουμε τρεις φορές κατά 60 μοίρες (δηλαδή 180 μοίρες) και γράφουμε έξι γράμματα στο άδεια πεδία. Επιστρέφουμε στην αρχική θέση. Περιστρέφουμε το καντράν πέντε φορές κατά 60 μοίρες, δηλαδή κατά πέντε «δόντια» του καντράν μας. Εκτυπώνουμε. Η επόμενη θέση κλίμακας είναι η θέση που περιστρέφεται κατά 60 μοίρες γύρω από το μηδέν. Η τέταρτη θέση είναι 0 μοίρες, αυτή είναι η αρχική θέση.

Καταλαβαίνετε τι έγινε; Έχουμε μια πρόσθετη ευκαιρία - να περιπλέκουμε τη "μηχανή" μας περισσότερο από επτακόσιες φορές! Έτσι, έχουμε δύο ανεξάρτητες θέσεις του "αυτόματου" - επιλογή πλέγματος και επιλογή μετάθεσης. Το πλέγμα μπορεί να επιλεγεί με 66 = 46656 τρόπους, μετάθεση 720. Αυτό δίνει 33592320 δυνατότητες. Πάνω από 33 εκατομμύρια κρυπτογράφηση! Σχεδόν λίγο λιγότερο, γιατί Ορισμένα πλέγματα δεν μπορούν να κοπούν από χαρτί.

Στο κάτω μέρος Σύκο. 1 Έχουμε ένα μήνυμα κωδικοποιημένο ως εξής: «Σας στέλνω τέσσερα τμήματα αλεξίπτωτων». Είναι εύκολο να καταλάβει κανείς ότι ο εχθρός δεν μπορεί να ενημερωθεί για αυτό. Αλλά θα καταλάβει κάτι από αυτά:

TPOROPVMANVEORDISZ

ΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕΕ

ακόμα και με την υπογραφή 351042;

Κατασκευάζουμε Enigma - μια γερμανική μηχανή κρυπτογράφησης

Ρύζι. 2. Ένα παράδειγμα της αρχικής εγκατάστασης του μηχανήματος κρυπτογράφησης.

Μεταθέσεις (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).

Όπως ανέφερα ήδη, οφείλω την ιδέα της δημιουργίας μιας τέτοιας μηχανής από χαρτόνι στο βιβλίο "Εργαστήριο σε ένα συρτάρι - Μαθηματικά". Η «κατασκευή» μου είναι κάπως διαφορετική από αυτή που έδωσαν οι συγγραφείς της.

Η μηχανή κρυπτογράφησης που χρησιμοποιούσαν οι Γερμανοί κατά τη διάρκεια του πολέμου είχε μια έξυπνα απλή αρχή, κάπως παρόμοια με αυτή που είδαμε με τον εξάγωνο κρυπτογράφηση. Κάθε φορά είναι το ίδιο: σπάστε τη δύσκολη αντιστοίχιση ενός γράμματος σε ένα άλλο γράμμα. Πρέπει να είναι αντικαταστάσιμο. Πώς να το κάνετε αυτό για να έχετε τον έλεγχο;

Ας επιλέξουμε όχι οποιαδήποτε μετάθεση, αλλά μια που έχει κύκλους μήκους 2. Με απλά λόγια, κάτι σαν το "Gaderipoluk" που περιγράφηκε εδώ πριν από λίγους μήνες, αλλά καλύπτει όλα τα γράμματα του αλφαβήτου. Ας συμφωνήσουμε σε 24 γράμματα - χωρίς ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Πόσες τέτοιες μεταθέσεις; Αυτό είναι ένα έργο για αποφοίτους γυμνασίου (θα πρέπει να μπορούν να το λύσουν αμέσως). Πόσα? Πολλά απο? Αρκετές χιλιάδες; Ναί:

1912098225024001185793365052108800000000 (ας μην προσπαθήσουμε καν να διαβάσουμε αυτόν τον αριθμό). Υπάρχουν τόσες πολλές δυνατότητες για να ορίσετε τη θέση «μηδέν». Και μπορεί να είναι δύσκολο.

Η μηχανή μας αποτελείται από δύο στρογγυλούς δίσκους. Ένα από αυτά, που στέκεται ακόμα, έχει γραμμένα γράμματα. Μοιάζει λίγο με το καντράν σε ένα παλιό τηλέφωνο, όπου καλούσατε έναν αριθμό γυρνώντας τον επιλογέα μέχρι τέρμα. Το Rotary είναι το δεύτερο με χρωματικό συνδυασμό. Ο πιο εύκολος τρόπος είναι να τα βάλετε σε κανονικό φελλό χρησιμοποιώντας μια καρφίτσα. Αντί για φελλό, μπορείτε να χρησιμοποιήσετε ένα λεπτό χαρτόνι ή ένα χοντρό χαρτόνι. Ο Lukasz Badowski και ο Zaslav Adamaszek συνιστούν να τοποθετήσετε και τους δύο δίσκους σε μια θήκη CD.

Ας φανταστούμε ότι θέλουμε να κωδικοποιήσουμε τη λέξη ARMATY (Ρύζι. 2 και 3). Ρυθμίστε τη συσκευή στη θέση μηδέν (βέλος προς τα πάνω). Το γράμμα Α αντιστοιχεί στο F. Περιστρέψτε το εσωτερικό κύκλωμα ένα γράμμα προς τα δεξιά. Έχουμε το γράμμα R να κωδικοποιήσουμε, τώρα αντιστοιχεί στο Α. Μετά την επόμενη περιστροφή, βλέπουμε ότι το γράμμα Μ αντιστοιχεί στο U. Η επόμενη περιστροφή (τέταρτο διάγραμμα) δίνει την αντιστοιχία Α - Ρ. Στον πέμπτο καντράν έχουμε Τ - Α. Τέλος (έκτος κύκλος) Y – Y Ο εχθρός μάλλον δεν θα μαντέψει ότι τα CFCFA μας θα είναι επικίνδυνα για αυτόν. Και πώς θα διαβάσουν οι «δικοί μας» την αποστολή; Πρέπει να έχουν το ίδιο μηχάνημα, το ίδιο «προγραμματισμένο», δηλαδή με την ίδια μετάθεση. Η κρυπτογράφηση ξεκινά από τη θέση μηδέν. Άρα η τιμή του F είναι Α. Γυρίστε τον επιλογέα δεξιόστροφα. Το γράμμα Α συνδέεται τώρα με το R. Γυρίζει το καντράν προς τα δεξιά και κάτω από το γράμμα U βρίσκει το M, κ.λπ. Ο υπάλληλος κρυπτογράφησης τρέχει στον στρατηγό: «Στρατηγέ, αναφέρω, έρχονται τα όπλα!»

Ρύζι. 3. Η αρχή λειτουργίας της εργασίας μας Enigma.

Ρύζι. 3. Η αρχή λειτουργίας της εργασίας μας Enigma.

Οι δυνατότητες ακόμη και ενός τόσο πρωτόγονου Enigma είναι εκπληκτικές. Μπορούμε να επιλέξουμε άλλες μεταθέσεις εξόδου. Μπορούμε - και υπάρχουν ακόμη περισσότερες ευκαιρίες εδώ - όχι με ένα «σερίφ» τακτικά, αλλά με μια συγκεκριμένη, καθημερινή μεταβαλλόμενη σειρά, παρόμοια με ένα εξάγωνο (για παράδειγμα, πρώτα τρία γράμματα, μετά επτά, μετά οκτώ, τέσσερα ... .. κλπ. .).

Πώς μπορείτε να μαντέψετε;! Και όμως για τους Πολωνούς μαθηματικούς (Μαριάν Ρέβσκι, Ερρίκος του Ζιγκάλσκι, Ezhi Ruzicki) συνέβη. Οι πληροφορίες που αποκτήθηκαν με αυτόν τον τρόπο ήταν ανεκτίμητες. Παλαιότερα είχαν εξίσου σημαντική συμβολή στην ιστορία της άμυνάς μας Waclaw Sierpinski i Στάνισλαβ Μαζούρκεβιτςπου παραβίασε τον κώδικα των ρωσικών στρατευμάτων το 1920. Το αναχαιτισμένο καλώδιο έδωσε στον Piłsudski την ευκαιρία να κάνει τον περίφημο ελιγμό από τον ποταμό Wieprz.

Θυμάμαι τον Waclaw Sierpinski (1882-1969). Έμοιαζε σαν μαθηματικός για τον οποίο δεν υπήρχε ο έξω κόσμος. Δεν μπορούσε να μιλήσει για τη συμμετοχή του στη νίκη του 1920, τόσο για στρατιωτικούς όσο και για... πολιτικούς λόγους (οι αρχές της Λαϊκής Δημοκρατίας της Πολωνίας δεν συμπαθούσαν αυτούς που μας υπερασπίστηκαν από τη Σοβιετική Ένωση).

Σύκο. 4. Μετάθεση (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).

Ρύζι. 5. Ωραία διακόσμηση, αλλά δεν είναι κατάλληλη για κρυπτογράφηση. Πάρα πολύ τακτικά.

Εργασία 1. Na Σύκο. 4 έχετε άλλη μια μετάθεση για να δημιουργήσετε το Enigma. Αντιγράψτε το σχέδιο σε έναν ξηρογράφο. Κατασκευάστε ένα αυτοκίνητο, κωδικοποιήστε το όνομα και το επίθετό σας. Το CWONUE JTRYGT μου. Εάν πρέπει να κρατήσετε τις σημειώσεις σας μυστικές, χρησιμοποιήστε ένα Enigma από χαρτόνι.

Εργασία 2. Κρυπτογραφήστε το όνομα και το επώνυμό σας ενός από τα «αυτοκίνητα» που είδατε, αλλά (προσοχή!) με μια επιπλέον περιπλοκή: δεν στρίβουμε μια εγκοπή προς τα δεξιά, αλλά σύμφωνα με το σχήμα {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - δηλαδή, πρώτα από ένα, μετά από δύο, μετά από τρία, μετά από 2, μετά πάλι κατά 1, μετά από 2, κ.λπ., ένα τέτοιο "κύμα" . Βεβαιωθείτε ότι το όνομα και το επώνυμό μου είναι κρυπτογραφημένα ως CZTTAK SDBITH. Τώρα καταλαβαίνετε πόσο ισχυρό ήταν το μηχάνημα Enigma;

Επίλυση προβλήματος για αποφοίτους Λυκείου. Πόσες επιλογές διαμόρφωσης για το Enigma (σε αυτήν την έκδοση, όπως περιγράφεται στο άρθρο); Έχουμε 24 γράμματα. Επιλέγουμε το πρώτο ζεύγος γραμμάτων - αυτό μπορεί να γίνει

τρόπους. Το παρακάτω ζεύγος μπορεί να επιλεγεί στο

μεθόδους, περαιτέρω

και τα λοιπά. Μετά τους κατάλληλους υπολογισμούς (όλοι οι αριθμοί πρέπει να πολλαπλασιαστούν) παίρνουμε

151476660579404160000

Στη συνέχεια, διαιρέστε αυτόν τον αριθμό με το 12! (12 παραγοντικό), επειδή τα ίδια ζεύγη μπορούν να ληφθούν με διαφορετική σειρά. Έτσι στο τέλος παίρνουμε "σύνολο"

316234143225,

αυτό είναι λίγο πάνω από 300 δισεκατομμύρια, που δεν φαίνεται να είναι εκπληκτικά μεγάλος αριθμός για τους σύγχρονους υπερυπολογιστές. Ωστόσο, αν λάβουμε υπόψη την τυχαία σειρά των ίδιων των μεταθέσεων, ο αριθμός αυτός αυξάνεται σημαντικά. Μπορούμε επίσης να σκεφτούμε άλλους τύπους μεταθέσεων.

Δείτε επίσης: