Metoda permutării verticale. Cifre de substituție (substituție) și permutare

Cifre bloc

Datorită faptului că textul simplu al unui mesaj are de obicei o lungime arbitrară, uneori destul de mare, acesta este împărțit în blocuri mai mici de lungime fixă. Textele acestor blocuri sunt criptate separat și independent unul de celălalt.

O singură cheie cifruri bloc sunt impartite in 3 grupe:

Cifre de permutare

Cifre de substituție

Cifruri compozite.

Când se utilizează cifruri de permutare, care sunt concepute pentru a elimina semnificația unui mesaj prin schimbarea ordinii de alternanță a simbolurilor sale, semnele text simplu sunt rearanjate după o anumită regulă (cheie) în cadrul unui bloc dat. Ca urmare a acestui fapt, ordinea normală a apariției lor și însuși sensul mesajului informativ sunt perturbate. În acest caz, se face o distincție între cifrurile de permutare simple și complexe.

Un cifr de permutare simplu rearanjează un grup de litere de text într-o manieră regulată, în conformitate cu o cheie de permutare aleasă (regulă). Există multe exemple din istorie de utilizare a unor astfel de cifruri pentru criptarea manuală. În acest caz, se foloseau adesea tabele speciale, care prevedeau proceduri simple de criptare (chei), conform cărora literele din mesaj erau rearanjate. Cheia pentru astfel de tabele a fost dimensiunea tabelului, o frază care specifică o permutare sau alte caracteristici speciale ale tabelului.

Un exemplu de cel mai simplu cifr de permutare este prezentat în Fig. 5.5.

Orez. 5.5. Cel mai simplu cifr permutări.

După cum se poate observa din fig. 5.5, pentru a cripta mesajul „YUSTACE ALEX MEET YOUR CONNECTED MAN”, acesta din urmă trebuie scris sub forma unui tabel format, de exemplu, din 5 rânduri și 6 coloane. Textul mesajului este scris în coloane, excluzând spațiile. Dacă ultima coloană este incompletă, este completată aleatoriu cu orice litere. Pentru a obține un mesaj criptat, textul original este citit rând cu rând (de la stânga la dreapta) și scris în grupuri, de exemplu, 5 cifre. Dura

procedura nu se referă la procesul de criptare și se face doar pentru a face mai convenabilă notarea textului care este lipsit de orice sens. Pentru a decripta un astfel de text, trebuie să cunoașteți cheia, și anume numărul de rânduri și coloane din tabel sau, cu alte cuvinte, dimensiunea acestuia.

O metodă de criptare mai practică, foarte asemănătoare cu cea anterioară, este descrisă mai jos. Diferă doar prin aceea că coloanele tabelului sunt rearanjate în funcție de un cuvânt cheie, o expresie sau un set de numere de lungimea unei linii de tabel.

La criptarea prin permutare simplă, textul cifrat este scris în rânduri succesive sub simbolurile cheie, care nu trebuie repetate Pentru a simplifica memorarea cheii, se folosește un cuvânt cheie, ale cărui litere, numerotate în ordinea locației lor. alfabetul, stabilește regula permutării. Textul cifrat este scris în coloane în ordinea în care literele cheii sunt situate în alfabet sau în ordinea numerelor dintr-o serie naturală, dacă cheia este digitală. Procesul de criptare folosind un cifr de permutare simplu este ilustrat în Fig. 5.6. Să presupunem că trebuie să criptați un mesaj de informații

„Întâlnirea va fi ținută mâine JUSTATIE.”

Pentru a cripta acest text simplu, îl scriem fără spații (participarea acestuia din urmă la procedura de criptare, datorită frecventa inalta repetarea, slăbește semnificativ puterea criptografică a cifrului) și alegeți o cheie de criptare, de exemplu, 245 136. Conform acestei chei, formată din 6 cifre, vom împărți întregul mesaj de informare în blocuri, fiecare dintre ele va conține 6 litere de text. După împărțirea în blocuri, am obținut 4 blocuri cu câte 6 litere fiecare și 1 bloc care conține 5 litere. În astfel de cazuri, ultimul grup de litere din mesajul original este suplimentat aleatoriu cu diferite caractere până când se obține un bloc complet. În cazul nostru, lipsește o singură literă, așa că selectăm orice literă, de exemplu Ъ, și o adăugăm la sfârșitul celui de-al cincilea bloc.

Orez. 5.6. Cifru de permutare simplu

Apoi, folosind tasta 245 136, literele textului simplu original sunt rearanjate. De exemplu, prima cifră a cheii este 2, indicând că în noul bloc prima literă a textului cifrat va fi a doua literă a blocului text simplu, a doua cifră a cheii este 4, indicând că a doua literă a text cifrat este a patra literă din blocul text simplu etc. d.

În cele din urmă, după permutările din toate blocurile, obținem text cifrat. Citind-o, vedem că este complet lipsită de orice conținut semantic.

Pentru a face cheia mai ușor de reținut, se folosește de obicei un cuvânt cheie. ÎN în acest caz,- acesta este cuvântul „ROOT”. În ea, numărul 1 al cheii corespunde literei E, deoarece este prima dintre toate literele acestui cuvânt găsite în alfabetul nostru, numărul 2 - litera K (din același motiv), etc.

Același mesaj poate fi criptat folosind un tabel format din, de exemplu, 5 rânduri și 6 coloane (lungimea cuvântului cheie). Textul sursă este scris în coloane și formează un tabel (Fig. 5.7). Cuvântul cheie specifică o regulă pentru rearanjarea coloanelor. Dacă într-un cuvânt cheie apar aceleași litere, acestea sunt numerotate în ordine de la stânga la dreapta. Al doilea text cifrat rezultat, așa cum se poate vedea din Fig. 5.7 este complet diferit de primul.

Orez. 5.7. Criptare folosind un tabel

Principalul dezavantaj al acestui cifr este puterea sa criptografică scăzută. Prin factorizarea textului cifrat (nu există multe opțiuni), puteți determina cu ușurință lungimea probabilă a cuvântului de cod care a fost folosit în timpul criptării.

Pentru a crește puterea criptografică a textului cifrat obținut mai sus, puteți încerca să-l criptați din nou. Această metodă de criptare este cunoscută sub numele de dublă permutare. Esența acestei metode este următoarea. Textul obținut după prima criptare este criptat a doua oară folosind un tabel cu o dimensiune diferită (lungimile rândurilor și coloanelor sunt selectate diferit). În plus, puteți rearanja rândurile într-un tabel și coloanele într-un altul. Puteți completa tabelul cu text sursă în moduri diferite: zig-zag, șarpe, spirală etc.

Un cifr de permutare simplu folosind proprietățile tabelului numit pătrate magice (Figura 5.8) a fost folosit încă din Evul Mediu. Pătratele magice sunt tabele echilaterale, ale căror celule sunt umplute cu numere naturale, începând de la 1. În plus, aceste numere în sumă dau același număr pentru fiecare coloană, fiecare rând și diagonalele pătratului magic (în cazul nostru, acesta este numărul 34). Text sursă - AȘTEPTĂM SĂ TE ÎNCONTREM DREPTATE, la completarea pătratului magic, acesta este introdus în ordinea numerelor naturale, de exemplu, numărul 1 a fost înlocuit cu 1 literă text sursă(G), numărul 12 - 12 literă a mesajului (C), etc. După scrierea textului simplu, conținutul tabelului este citit rând cu rând, rezultând un text cifrat cu o permutare de litere.

Orez. 5.8. Patrat magic

Așa-numitul schimbari de traseu, pe baza unor figuri geometrice. Un segment de text simplu este scris într-o astfel de figură de-a lungul unei anumite traiectorii. Textul cifrat este succesiunea obținută prin scrierea textului pe o traiectorie diferită. De exemplu, puteți scrie un mesaj într-un tabel dreptunghiular alegând următorul traseu: ne vom deplasa orizontal, începând din stânga colțul de sus, alternativ de la stânga la dreapta și de la dreapta la stânga. Vom copia mesajul de-a lungul unui traseu diferit: pe verticală, începând din colțul din dreapta sus și deplasându-ne alternativ de sus în jos și de jos în sus.

Exemplu (permutare de rutare)

Să criptăm fraza folosind metoda de mai sus exemplu de permutare a rutei, folosind o masă dreptunghiulară de 4x7:

Fraza criptată arată astfel:

mastaerreshrnoermiupvkitrpnoi

Inversarea pașilor descriși în timpul decriptării nu este dificilă.

Un tip de permutare a rutei numit rearanjare verticală. Acest sistem folosește și un tabel dreptunghiular în care mesajul este scris în mod obișnuit (în rânduri de la stânga la dreapta). Mesajul este scris vertical (de sus în jos), cu coloanele selectate în ordinea determinată tastă numerică.

Exemplu (rearanjare verticală)

Să criptăm fraza Iată un exemplu de cifru cu permutare verticală, folosind un dreptunghi 6 x 7 și o tastă numerică (5,1,4,7,2,6,3).

Rețineți că este nepotrivit să umpleți ultima linie a dreptunghiului cu litere „nefuncționale”, deoarece acest lucru ar oferi inamicului care a primit această criptogramă informații despre lungimea cheii numerice. Într-adevăr, în acest caz, lungimea cheii ar trebui căutată printre divizorii de lungime a mesajului.

Acum, scriind literele în coloane în ordinea indicată de cheia numerică, obținem următoarea criptogramă:

oreekrfiyamaaeotshrnsivevlrvirkpnpitot

Când decriptați, în primul rând, trebuie să determinați numărul de coloane lungi, adică numărul de litere din ultima linie dreptunghi. Pentru a face acest lucru, trebuie să împărțiți numărul de litere din mesaj la lungimea tastei numerice. Este clar că restul împărțirii va fi numărul dorit. Odată ce acest număr a fost determinat, literele criptogramei pot fi plasate în locurile lor adecvate, iar mesajul va fi citit natural.

În exemplul nostru, 38=7x5+3, deci tabelul completat are 3 coloane lungi și 4 scurte.

Permutările de rute mai complexe pot folosi alte forme geometrice și rute mai „sprețuite”, cum ar fi, de exemplu, când ocoliți o tablă de șah cu o „mișcare de cavaler”, căi într-un labirint etc. Opțiunile posibile depind de imaginația compilatorului de sistem și, desigur, de cerințele naturale pentru ușurința în utilizare.

Poveste

Ora exactă nu se cunoaște aspectul cifrului de permutare. Este foarte posibil ca scribii din antichitate să fi rearanjat literele în numele regelui lor pentru a-și ascunde adevăratul nume sau în scopuri rituale.

Unul dintre cele mai vechi dispozitive de criptare cunoscute de noi este Scytala. Se știe, fără îndoială, că rătăcitorul a fost folosit în războiul Spartei împotriva Atenei la sfârșitul secolului al V-lea î.Hr. e.

Strămoșul anagramei este considerat a fi poetul și gramaticul Lycophron, care a trăit în Grecia anticăîn secolul al III-lea î.Hr e. După cum a relatat autorul bizantin John Tsets, din numele regelui Ptolemeu a compus prima anagramă cunoscută de noi: Ptolemaios - Aro Melitos, care s-a tradus înseamnă „din miere”, iar din numele reginei Arsinoe - ca „ Ion Eras„(violeta Herei).

Cifre simple de permutare

În mod obișnuit, atunci când se criptează și se decriptează un cifr de permutare simplu, se utilizează un tabel de permutare:

Prima linie este poziția caracterului în text simplu, a doua linie este poziția în cifrgramă. Astfel, cu lungimea mesajului n (\displaystyle n) personajele există exact n! (\displaystyle n!\ ) chei.

Cifre de permutare a rutei

Așa-numitele permutări de traseu folosind unele figură geometrică(plată sau volumetrică). Transformările constau în faptul că un segment de text simplu este scris într-o astfel de figură de-a lungul unei anumite traiectorii și scris pe o altă traiectorie. Un exemplu al acestui cifr este cifrul Scytala.

Cifrul permutării de rutare a tabelului

Cel mai răspândit coduri de rutare permutări bazate pe dreptunghiuri (tabele). De exemplu, puteți scrie un mesaj într-un tabel dreptunghiular de-a lungul traseului: orizontal, începând din colțul din stânga sus, alternativ de la stânga la dreapta. Vom copia mesajul de-a lungul traseului: pe verticală, începând din colțul din dreapta sus, alternativ de sus în jos.

CRIPTOGRAMA: yesoeomrnniateairmuptkprrysv

Inversarea pașilor descriși nu va prezenta nicio dificultate la descifrare.

Cifru cu permutare verticală

Un tip de permutare a traseului - permutarea verticală - a devenit larg răspândit. Acest cifru folosește și un tabel dreptunghiular în care mesajul este scris în rânduri de la stânga la dreapta. Cifragrama este scrisă vertical, cu coloanele selectate în ordinea determinată de cheie.

TEXT CLEAR: exemplu de permutare a rutei

CHEIE: (3, 1, 4, 2, 5)

CRIPTOGRAMA: rmuptkmrnrnrnprrysviateaeshoeo

Nu este recomandabil să completați ultimul rând al tabelului cu litere „nefuncționale”, deoarece criptoanalistul care a primit această criptogramă primește informații despre lungimea cheii numerice.

Cod „grilă rotativă”

În 1550, matematicianul italian Gerolamo Cardano (1501-1576) a propus în cartea sa Despre subtilități tehnologie nouă criptarea mesajelor - zăbrele.

Inițial, zăbrele Cardano era un șablon cu găuri în care erau scrise litere, silabe sau cuvinte ale unui mesaj. Apoi șablonul a fost îndepărtat și spatiu liber plin cu text mai mult sau mai puțin semnificativ. Această metodă de ascundere a informațiilor se referă la steganografie.

Mai târziu, a fost propus cifrul „rețea rotativă” - primul cifr transpozițional (geometric). Chiar dacă există mare diferentaÎntre propunerea inițială a lui Cardano și cifrul cu zăbrele rotative, metodele de criptare bazate pe șablon sunt denumite în mod obișnuit „zăbrele Cardano”.

Pentru a cripta și decripta folosind acest cifru, se realizează un șablon cu celule decupate. Când aplicați un șablon pe o masă de aceeași dimensiune cu patru moduri posibile, tăieturile sale trebuie să acopere complet toate celulele tabelului exact o dată.

La criptare, un șablon este plasat pe masă. Literele de text simplu sunt scrise în celule vizibile de-a lungul unui anumit traseu. În continuare, șablonul este răsturnat de trei ori, efectuând de fiecare dată operația de umplere.

Cifragrama este scrisă din tabelul rezultat de-a lungul unui anumit traseu. Cheia este șablonul, traseul inscripției și ordinea virajelor.

Această metodă criptarea a fost folosită pentru transmitere informatii clasificate conducătorii olandezi în anii 1740. În timpul Primului Război Mondial, armata lui Kaiser Wilhelm a folosit cifrul „grilă rotativă”. Germanii foloseau baruri dimensiuni diferite, însă, pentru o perioadă foarte scurtă (patru luni), spre marea dezamăgire a criptoanaliştilor francezi, care tocmai începuseră să selecteze cheile acestora. Pentru grile de diferite dimensiuni, francezii au venit cu propriile nume de cod: Anna (25 de litere), Bertha (36 de litere), Dora (64 de litere) și Emile (81 de litere).

În criptarea prin permutare, caracterele textului criptat sunt rearanjate în conformitate cu anumite reguli în cadrul blocului criptat al acestui text.

Simplă rearanjare

Se selectează o dimensiune de bloc de criptare de n coloane și m rânduri și o secvență de chei, care este formată dintr-o serie naturală de numere 1,2,...,n prin permutare aleatorie.

Criptarea se realizează în următoarea ordine:

Textul criptat este scris în rânduri succesive sub numerele secvenței de chei, formând un bloc de criptare de dimensiunea n*m.

Textul cifrat este scris în coloane în ordinea crescătoare a numerelor coloanelor specificate de secvența de taste.

Completat bloc nou etc.

De exemplu, să criptăm textul

LOAD_ORANGE_IN BOLII

bloc dimensiunea 8*3 și cheia 5-8-1-3-7-4-6-2.

Un tabel simplu de permutare va arăta astfel:

Mesaj criptat:

WEB_NHZLOESLGAYEIAICHRP_

Decriptarea se realizează în următoarea ordine:

Din textul cifrat este extras un bloc de caractere de dimensiunea n*m.

Acest bloc este împărțit în n grupuri de m caractere.

Simbolurile sunt scrise în acele coloane ale tabelului de permutare ale căror numere coincid cu numerele grupului din bloc. Textul decriptat este citit în funcție de rândurile tabelului de permutare.

Se alocă un nou bloc de caractere etc.

Permutarea complicată conform tabelului

Când permutarea între tabele devine mai complexă, celulele neutilizate ale tabelului sunt introduse în tabelul de permutare pentru a crește puterea cifrului. Numărul și locația elementelor neutilizate reprezintă o cheie de criptare suplimentară.

La criptarea textului, caracterele de text nu sunt scrise în elemente neutilizate și nici un caracter din acestea nu este scris în textul cifrat - ele sunt pur și simplu omise. La decriptare, caracterele de text cifrat nu sunt, de asemenea, incluse în elementele neutilizate.

Pentru a crește și mai mult puterea criptografică a cifrului, în timpul procesului de criptare puteți modifica cheile, dimensiunea tabelului de permutare, numărul și locația elementelor neutilizate în conformitate cu un anumit algoritm, iar acest algoritm devine o cheie suplimentară de criptare.

Permutarea complicată de rute

Puterea ridicată a criptării poate fi asigurată prin complicarea permutărilor de-a lungul rutelor de tip Hamiltonian. În acest caz, vârfurile unui anumit hipercub sunt folosite pentru a înregistra caracterele textului cifrat, iar caracterele textului cifrat sunt citite de-a lungul rutelor Hamilton și sunt folosite mai multe rute diferite. De exemplu, luați în considerare criptarea folosind rute Hamilton cu n=3.

Structura unui hipercub tridimensional este prezentată în Figura 6.

Figura 6. Hipercub tridimensional

Numerele vârfurilor cubului determină succesiunea în care acesta este umplut cu simboluri criptate atunci când formează un bloc. În general, un hipercub n-dimensional are n 2 vârfuri.

Figura 7. Trasee Hamilton

Secvența de permutări de simbol în blocul criptat pentru prima schemă este 5-6-2-1-3-4-8-7, iar pentru a doua este 5-1-3-4-2-6-8- 7. În mod similar, puteți obține o secvență de permutări pentru alte rute: 5-7-3-1-2-6-8-4, 5-6-8-7-3-1-2-4, 5-1-2 -4-3 -7-8-6 etc.

Dimensiunea hipercubului și numărul de tipuri de rute Hamilton selectate constituie cheia secretă a metodei.

Puterea unei permutări simple este determinată în mod unic de dimensiunea matricei de permutare utilizată. De exemplu, când se folosește o matrice 16*16, numărul de permutări posibile ajunge la 1,4E26. Este imposibil să sortați un astfel de număr de opțiuni chiar și folosind un computer. Stabilitatea permutărilor complicate este chiar mai mare. Cu toate acestea, trebuie avut în vedere că la criptarea prin permutare, caracteristicile probabilistice ale textului sursă sunt complet păstrate, ceea ce facilitează criptoanaliza.

Criptare folosind metoda pătratului magic.

Pătratele magice sunt tabele pătrate cu numere naturale consecutive înscrise în celulele lor, începând de la 1, care însumează același număr pentru fiecare coloană, rând și diagonală.

La criptare, literele textului simplu trebuie introduse în pătratul magic în conformitate cu numerotarea celulelor acestuia. Pentru a obține textul cifrat, citiți conținutul tabelului completat rând cu rând.

Să criptăm expresia „PUTERE MAGICĂ” folosind un pătrat magic 4x4. Pentru a face acest lucru, vom alege una dintre cele 880 de opțiuni pentru pătratele magice de o dimensiune dată (Figura 8a). Apoi introducem fiecare literă a mesajului într-o celulă separată a tabelului cu un număr corespunzător numărului de serie al literei din fraza originală (Figura 8b). Când citim rând cu rând tabelul completat, obținem textul cifrat: „_GAIAESSCHYA_KIALM”.

Figura 8. Exemplu de criptare folosind pătrate magice

Un cifr din care transformările schimbă doar ordinea caracterelor din textul sursă, dar nu le schimbă ele însele, se numește cifr de permutare

Să luăm în considerare o transformare din Silk, concepută pentru a cripta un mesaj cu o lungime de caractere. Poate fi reprezentat cu ajutorul unui tabel

unde este numărul locului din textul cifrat unde prima literă a mesajului original se încadrează sub transformarea selectată, numărul locului pentru a doua literă etc. linia de sus Tabelele sunt scrise în ordinea numerelor de la 1 la 1, iar în partea de jos sunt aceleași numere, dar în ordine aleatorie. Acest tabel se numește substituție de grade

Cunoscând substituția care specifică transformarea, este posibil să se efectueze atât criptarea, cât și decriptarea textului. De exemplu, dacă utilizați înlocuirea pentru conversie

iar cuvântul este criptat în conformitate cu acesta. Încercați să decriptați mesajul primit ca urmare a transformării folosind substituția de mai sus.

Ca exercițiu, cititorul este invitat să scrie în mod independent substituții care specifică transformări în cele trei descrise mai jos

exemple de cifruri de permutare. Răspunsurile se află la sfârșitul secțiunii.

Un cititor familiarizat cu metoda de inducție matematică poate verifica cu ușurință dacă există opțiuni (citește factorial) pentru completarea rândului de jos al tabelului (6). Astfel, numărul de transformări diferite ale unui cifr de permutare conceput pentru a cripta mesajele de lungime este mai mic sau egal cu (rețineți că acest număr include și o opțiune de transformare care lasă toate caracterele la locul lor!).

Pe măsură ce numărul crește, valoarea crește foarte repede. Iată un tabel de valori pentru primele 10 numere naturale:

(vezi scanare)

Pentru valori mari, pentru un calcul aproximativ, puteți folosi cunoscuta formulă Stirling

Un exemplu de sistem de criptare silențios conceput pentru a cripta mesajele de lungime este un cifr în care setul de substituții de grade este luat ca un set de chei și transformările de criptare corespunzătoare sunt specificate așa cum este descris mai sus. Numărul de chei dintr-un astfel de cifr este

Pentru utilizare practică, un astfel de cifru nu este convenabil, deoarece valori mari Trebuie să lucrez cu mese lungi.

Cifrurile de permutare care folosesc unele figuri geometrice au devenit larg răspândite. Transformările din acest cifru constau în faptul că textul original este introdus în figură de-a lungul unei „rute” și apoi scris din el de-a lungul celuilalt. Acest cifru se numește permutare rută. De exemplu, puteți intra mesajul originalîntr-o masă dreptunghiulară, alegând următorul traseu: orizontal, începând din colțul din stânga sus, alternativ de la stânga la dreapta și de la dreapta la stânga. Vom scrie mesajul de-a lungul unui traseu diferit: pe verticală, începând din colțul din dreapta sus și deplasându-ne alternativ de sus în jos și de jos în sus.

Să criptăm, de exemplu, în modul specificat fraza:

folosind dimensiunea dreptunghiului

(vezi scanare)

Fraza criptată arată astfel:

Teoretic, rutele ar putea fi mult mai sofisticate, dar ofuscarea rutelor face ca astfel de cifruri să fie dificil de utilizat.

Mai jos sunt descrieri a trei tipuri de cifruri de permutare întâlnite în problemele olimpiadei.

Cifrul „Scitala”. Unul dintre primele dispozitive de criptare a fost toiagul („Scital”), care a fost folosit în timpul războiului de la Sparta împotriva Atenei în secolul al V-lea î.Hr. e. Era un cilindru pe care era înfășurată rând cu rând o bandă îngustă de papirus (fără goluri sau suprapuneri), iar apoi textul necesar transmiterii era scris pe această bandă de-a lungul axei sale. Banda a fost desfășurată din cilindru și trimisă destinatarului, care, având un cilindru de exact același diametru, a înfășurat banda în jurul ei și a citit mesajul. Este clar că această metodă de criptare rearanjează literele mesajului.

Cifrul Scital, după cum se poate vedea din soluția problemei 2.1, nu mai implementează permutări ca înainte - lungimea mesajului). Într-adevăr, acest cifru, așa cum este ușor de observat, este echivalent cu următorul cifr de permutare a rutare: un mesaj este scris linie cu linie într-un tabel format din coloane, după care literele sunt scrise în coloane. Numărul de coloane din tabel implicate nu poate depăși lungimea mesajului.

Există și curate limitări fizice, impus de implementarea cifrului Scital. Este firesc să presupunem că diametrul tijei nu trebuie să depășească 10 centimetri. Cu o înălțime de linie de 1 centimetru, nu se vor potrivi mai mult de 32 de litere pe o tură a unei astfel de tije. Astfel, numărul de permutări implementate de Scytala este puțin probabil să depășească 32.

Cod „Grătar rotativ”. Pentru a utiliza un cifr numit hash rotativ, se face un șablon dintr-o foaie dreptunghiulară de hârtie în carouri de dimensiunea pătratelor. Numărul de celule este decupat în șablon astfel încât atunci când este aplicat ardezie goală hârtie de aceeași dimensiune în patru moduri posibile, tăieturile sale acoperă complet întreaga zonă a foii.

Literele mesajului sunt introduse secvenţial în decupajele sablonului (linie cu linie, în fiecare linie de la stânga la dreapta) în fiecare dintre cele patru poziţii posibile ale acesteia, într-o ordine predeterminată.

Să explicăm procesul de criptare cu un exemplu. Lăsați grila prezentată în fig. să fie folosită ca cheie. 1.

Să criptăm textul folosindu-l

După ce am plasat o grilă pe o foaie de hârtie, introducem primele 15 (în funcție de număr

decupaje) litere de mesaj: Îndepărtând grila, vom vedea textul prezentat în Fig. 2. Rotiți grătarul la 180°. În ferestre vor apărea celule noi, încă necompletate. Introducem următoarele 15 litere în ele. Rezultatul va fi intrarea prezentată în Fig. 3. Apoi întoarcem zăbrelele pe cealaltă parte și criptăm restul textului în același mod (Fig. 4, 5).

Destinatarul mesajului, având exact același hash, poate citi cu ușurință textul original aplicând hash-ul textului cifrat în ordine în patru moduri.

Se poate dovedi că numărul de șabloane posibile, adică numărul de chei din cifrul latice, este (vezi Problema 1.1). Acest cifru este destinat mesajelor de lungime Numărul tuturor permutărilor dintr-un text de această lungime va fi de mai multe ori

mai mare decât numărul Cu toate acestea, chiar și cu dimensiunea șablonului, numărul de grătare posibile depășește 4 miliarde.

O variantă utilizată pe scară largă a cifrului de permutare a rutei se numește un cifr de permutare verticală (VPC). Folosește din nou un dreptunghi în care se încadrează mesajul în mod obișnuit(linie cu linie de la stânga la dreapta). Literele sunt scrise vertical, iar coloanele sunt luate în ordinea determinată de cheie. Să fie, de exemplu, această cheie: (5,4,1,7,2,6,3), iar cu ajutorul ei trebuie să criptați mesajul:

Să scriem mesajul într-un dreptunghi, ale cărui coloane sunt numerotate în funcție de cheie:

(vezi scanare)

Acum, selectând coloanele în ordinea specificată de cheie și scriind literele fiecăreia dintre ele succesiv de sus în jos, obținem următoarea criptogramă:

Numărul de chei cu șurub cu bile nu este mai mare decât numărul coloanelor din tabel. De regulă, mult mai puțin decât lungimea textului (mesajul se încadrează în mai multe rânduri de litere) și, prin urmare, mult mai puțin

Folosind formula Stirling de mai sus pentru numere mari, încercați să estimați de câte ori numărul de permutări posibile pe coloane este mai mic decât numărul tuturor permutărilor pe un text de lungime care este un multiplu de

În cazul în care nu este recomandat să scrieți cheia șurubului cu bile, aceasta poate fi extrasă dintr-un cuvânt sau o propoziție ușor de reținut. Există multe moduri de a face acest lucru. Cea mai obișnuită este să atribuiți numere literelor în mod obișnuit ordine alfabetică scrisori De exemplu, lasa cuvânt cheie va Litera A prezentă în ea primește numărul 1. Dacă o literă apare de mai multe ori, atunci aparițiile ei sunt numerotate succesiv de la stânga la dreapta. Prin urmare, a doua apariție a literei A primește numărul 2. Deoarece nu există nicio literă în acest cuvânt, litera B primește numărul 3 și așa mai departe. Procesul continuă până când

până când toate literele primesc numere. Astfel, obținem următoarea cheie:

Să trecem la problema metodelor de spargere a cifrurilor de permutare. Problema care apare la recuperarea unui mesaj criptat de Silk nu este doar că numărul de chei posibile este mare, chiar și cu lungimi mici de text. Chiar dacă este posibil să treci prin toate permutările posibile, nu este întotdeauna clar care dintre aceste opțiuni este adevărată. De exemplu, să presupunem că trebuie să recuperăm textul original dintr-o criptogramă și nu știm nimic decât că a fost folosit un cifr de permutare. Ce versiune a textului sursă „cu sens” este acceptată ca adevărată: sau A poate Să dăm un exemplu de situație și mai confuză. Să presupunem că doriți să recuperați un mesaj folosind o criptogramă

permutarea obținută de cifr. Există cel puțin două opțiuni pentru mesajul original:

Aceste opțiuni au exact sensul opus și, în condițiile existente, nu avem nicio modalitate de a determina care opțiune este adevărată.

Uneori, datorită particularităților implementării cifrului, este posibil să obțineți informații despre transformarea (permutarea) utilizată. Să ne uităm la cifrul Scital din problema 2.1. Problema numărului de permutări implementate de Scytala a fost deja discutată mai sus. Nu au fost mai mult de 32. Acest număr este mic, așa că puteți căuta prin toate opțiunile. Dacă mesajul este suficient de lung, cel mai probabil vom primi o singură versiune lizibilă a textului. Cu toate acestea, folosind informații despre locația liniilor lăsate de codificator, este posibil să se determine diametrul tijei și, prin urmare, permutarea rezultată a literelor (vezi problema 2.1).

În exemplul luat în considerare, operatorul de cifrare a lăsat din neatenție urme pe papirus care ne permit să citim cu ușurință mesajul. Există și alte situații în care utilizarea nu foarte „competentă” a cifrului facilitează deschiderea corespondenței.

Problema 5.2 conține un exemplu de text criptat de un șurub cu bile. Prin convenție, spațiile dintre cuvinte au fost omise la scrierea textului în tabel. Prin urmare, concluzionăm că toate coloanele care conțin un spațiu în ultima linie trebuie să apară la sfârșitul textului. Astfel, coloanele sunt împărțite în două grupuri (conținând 6 litere și

O situație similară apare cu utilizarea „incompletă” a cifrului reticulat (vezi problema 4.1). Să existe o rețea de dimensiune și un mesaj de lungime k criptat folosindu-l, fără spații. K spații neumplute în grilă, cu condiția ca k să corespundă decupărilor din poziția a patra a grilajului. Pe baza unor astfel de informații, există o scădere bruscă a numărului de grile admisibile (vor exista. Cititorul este invitat să calculeze în mod independent numărul de grile admisibile la

Folosind exemplul de rezolvare a problemei 5.2, vom demonstra o altă abordare a rupturii cifrurilor cu permutare verticală – lingvistică. Se bazează pe faptul că în limbile naturale unele combinații de litere apar foarte des, altele mult mai puțin frecvent și multe nu apar deloc (de exemplu -

Vom selecta ordinea coloanelor una după alta, astfel încât în ​​toate rândurile acestor coloane să obținem segmente de text „lizibile”. În soluția dată problemei, recuperarea textului începe cu selectarea unui lanț de trei coloane din primul grup, care conține o combinație în ultima linie, deoarece este firesc să presupunem că mesajul se termină cu un punct. În continuare, sunt selectate coloane care continuă secțiuni de text în alte rânduri etc.

Combinarea metodei lingvistice ținând cont Informații suplimentare poate duce destul de repede la deschiderea mesajului.

Pentru a încheia povestea despre cifrurile de permutare, vă prezentăm o poveste cu autograful criptat al lui A. S. Pușkin, descris în romanul lui V. Kaverin „Împlinirea dorințelor”.

Personajul principal al romanului, un student la istorie Trubaciovski, care lucra în arhivele profesorului său, academicianul S.I. Bauer, a găsit într-unul dintre sertarele secrete ale biroului lui Pușkin un fragment din capitolul X neterminat din „Eugene Onegin”. Era o jumătate de foaie pliată dublu de hârtie groasă, albăstruie, cu un filigran datat 1829. Pe foaie era scris următoarele.

(vezi scanare)

(vezi scanare)

Fără efort deosebit Trubaciovski a citit manuscrisul și nu a înțeles nimic. A rescris-o, s-a dovedit a fi o prostie incoerentă, în care un rând, care abia începea un gând, este întrerupt de altul, iar cel de-al treilea, și mai lipsit de sens și mai incoerent. A încercat să despartă manuscrisul în strofe, dar din nou nu a funcționat. A început să caute rime - de parcă nu ar exista rime, deși toate acestea nu seamănă puțin cu versul alb. Am calculat linia - tetrametrul iambic, metrul în care a fost scris „Eugene Onegin”.

Trubaciovski a preluat cu entuziasm manuscrisul, a încercat să-l citească, sărind câte un rând, apoi două, apoi trei, sperând să ghicească accidental secvența secretă în care au fost scrise rândurile. Nimic nu a funcționat pentru el. Apoi a început să citească al treilea rând după primul, al cincilea după al treilea, al optulea după al cincilea, presupunând că golurile ar trebui să crească în progresia aritmetică. Totul este la fel! Disperat, a abandonat această idee. Totuși, ea nu i-a dat pace nici la prelegere, nici în tramvai... Ca un șahist care se joacă în capul lui, nu numai că știa fiecare rând pe de rost, ci o vedea în zece combinații deodată.

Timpul a trecut. Într-o zi, când se uita la punctele de lumină ale ferestrelor unui tren care se apropia de peron, cu o oarecare viziune interioară a

Am văzut întregul manuscris în fața mea - și cu o claritate atât de extraordinară, așa cum se întâmplă doar într-un vis.