Scop: să luăm în considerare noțiunea de substituție, substituția identică,
explicați cum se efectuează multiplicarea substituțiilor, găsirea substituției inverse,
enumeră proprietățile produsului de substituții,
ia în considerare conceptele de inversiune, permutări paritare ciudate
arată cum sunt utilizate permutările în criptografie
Am primit o telegramă de la unul dintre prietenii mei cumva. Această telegramă era ciudată. Asta este ceea ce spune: "yazhirponchors mej".
Puteți citi acest text? Foma, după un moment de gândire, înțelegea secretul acestei telegrame. El a fost invitat să viziteze. El a decis să răspundă în același spirit. A compilat o telegramă de răspuns și a criptat-o în același mod. Rezultatul a fost o înregistrare de două linii:
"Voi veni sâmbătă să vă întâlnesc"
După terminarea criptării, Thomas și-a dorit toată corespondența cu un prieten să conducă numai texte criptate, schimbând din când în când metoda de criptare. Prin urmare, el a început cu zel în dezvoltarea metodei de criptare.
El a decis să înlocuiască literele textului sursă cu numerele pozițiilor pe care le ocupă aceste litere. Iată o listă cu numerele primite de Thomas pentru telegrama unui prieten:
Apoi a observat că textul criptat diferă de textul original doar prin ordinea schimbată a fagurilor. Modificarea ordinii literelor este ușor de văzut cu ajutorul acelorași numere de poziție. De exemplu, textul criptat al telegramei unui alt prieten ar putea fi acum reprezentat de o listă:
Comparația acestor două liste oferă cheia criptării textului:
.
Intrarea de caractere se citește după cum urmează: "1 merge la 18". O intrare diferită este adesea folosită în schimb.
Direcția săgeților determină ordinea în care textul este criptat. De exemplu, scrisoarea din textul criptat în prima poziție ar trebui să ocupe a 18-a poziție în textul cifrat.
Dacă direcția săgeților este inversată, atunci aceeași masă cu două linii va determina ordinea decodificării textului. De exemplu, litera din textul cifrat în poziția 18 ar trebui să ocupe prima poziție în textul decodificat.
În cele din urmă, dacă prima linie este întotdeauna asociată cu textul sursă, atunci nu va mai fi nevoie să utilizați săgețile. (Când criptarea textului sursă este text criptat și atunci când este decodificat - criptat).
După ce a înțeles toate acestea, Foma a scris repede cheia celui de-al doilea cifru al telegramei sale:
Rămâne doar să informăm într-un fel acest chei prietenului său, iar secretul corespondenței este garantat!
Dacă înțelegeți ideile lui Thomas, aici este dicta dvs. criptată preferată:
Este criptat cu o cheie:
Încercați să citiți această vorbă!
Cheia pentru criptare:
"Încredere, dar verificați!"
Probabil că deja știți că puteți găsi o mulțime de chei de criptare de acest tip. Fiecare dintre ele poate fi reprezentată ca o masă cu două linii:
.
Aici în linia superioară sunt toate numerele naturale de la 1 la n în ordine crescătoare. Linia inferioară este obținută prin o anumită permutare a numerelor de la rândul de sus. Întreaga tabelă ca întreg este numită permutare a ordinului n.
Luați în considerare setul, în cazul în care fiecare element în care este prezentat o singură dată. Apoi, o cartografiere unu-la-unu asupra setului se numește o permutare a gradului n.
Se indică setul de permutări ale puterii n-a.
Relația este binară, prin urmare este obișnuit să se substituie o matrice cu două rânduri, în prima linie a cărora sunt scrise preimaginile, iar în al doilea - imaginile lor:
În cazul în care prototipuri (argumente) sunt aranjate în ordine crescătoare (de la schimbarea de intrare de acest tip este numit canonic. Dacă nu argumente sunt scrise în ordine crescătoare, apoi rearanjarea coloanele (în acest caz, în sine de substituție nu este schimbat, ci doar modifică ordinea cuvântului corespondențelor) poate fi linia de sus duceți la o formă comandată:
Dacă este posibil, vom folosi înregistrarea canonică. O astfel de înregistrare a fost întâlnită când am înregistrat o permutare a elementelor n. Rețineți că imaginea prematură a permutației este un set finit arbitrar și este necesară o pre-imagine a substituției.
Am găsit numărul diferitelor permutări posibile de gradul n. Deoarece fiecare substituție echivalentă canonic permutare corespunzător, numărul de permutări de gradul n-lea este egal cu numărul de permutări de n elemente, m. E. Setul este format din elemente.
Să ne întoarcem la Thomas. Folosind înlocuirea cheilor
el a criptat un mesaj format dintr-un singur cuvânt și la trimis unui prieten. Mesajul necriptat care a criptat din nou, dar cu o altă cheie
Deciphează acest mesaj. , "Pine"
Procesul de decriptare poate fi realizat mult mai repede dacă știți cum se efectuează o operație algebrică asupra substituțiilor. Această operație se numește multiplicare de substituții. (Dacă doriți, puteți să o numiți altfel, deoarece nu are nimic de-a face cu înmulțirea obișnuită a numerelor).
Să ne uităm la un exemplu al modului în care funcționează. Multiplicați permutările cu care mesajul lui Thomas a fost criptat:
Procedura de multiplicare este redusă la substituții succesive.
În prima substituție (A): 1 → 5;
în a doua substituție (B). 5 → 1;
Ca rezultat, obținem: 1 → 1.
În mod similar, din "2 → 2" și "2 → 3" urmează: "2 → 3". Realizând alte trei argumente de acest tip, obținem o substituție a produsului
Folosind înlocuirea AV ca encoder, puteți decoda mesajul "Thomas" "într-un singur pas". În același timp, vă controlați. (VA = "pompă")
Dacă sunteți interesat, puteți să veniți cu proprii înlocuiți-encryptori de mesaje și să păstrați corespondența secretă cu prietenii.
În timp ce ați descifrat mesajele, ați făcut cunoștință cu operațiile algebrice cu obiecte noi prin substituții. Dacă vreunul dintre dvs. este interesat nu numai de criptare, ci și de substituții proprii, atunci puteți să le cunoașteți mai bine prin îndeplinirea următoarelor sarcini.
DESEMNARE 1. Gasiti lucrari de substitutie:
DESEMNARE 2. Găsiți produsul BA al înlocuirilor A și B considerate mai sus. Folosind substituția BA ca encoder, decriptați din nou mesajul "snoas". Comparați rezultatul cu rezultatul transcrierii anterioare. După aceea, puteți spune dacă multiplicarea substituțiilor are proprietatea de comutativitate.
Să presupunem că sunt date două permutări u și