Cifru simplu cu o singură permutare. Cifru cu permutare verticală. Analiza cifrurilor de permutare
(Vezi si )
Influență mare Dezvoltarea criptografiei a fost influențată de lucrările matematicianului american Claude Shannon care au apărut la mijlocul secolului XX. Aceste lucrări au pus bazele teoriei informației și au dezvoltat, de asemenea, un aparat matematic pentru cercetare în multe domenii ale științei legate de informație. Mai mult, este general acceptat că teoria informaţiei ca știință s-a născut în 1948 după publicarea lucrării lui K. Shannon „Teoria matematică a comunicării”.
În lucrarea sa „Teoria comunicării în sistemele secrete”, Claude Shannon a rezumat experiența acumulată înaintea lui în dezvoltarea cifrurilor. S-a dovedit că, chiar și în cifrurile foarte complexe, următoarele pot fi identificate ca componente tipice: cifruri simple Cum cifruri de substituție, cifre de permutare sau combinații ale acestora.
Caracteristica principală după care sunt clasificate cifrurile este tipul de transformare efectuată pe textul simplu în timpul criptării. Dacă fragmente text simplu(litere individuale sau grupuri de litere) sunt înlocuite cu unele dintre echivalentele lor în textul cifrat, atunci cifrul corespunzător aparține clasei cifruri de înlocuire. Dacă literele textului simplu în timpul criptării se schimbă doar între ele, atunci avem de-a face cu cifru de permutare. Pentru a crește fiabilitatea criptării, textul cifrat obținut folosind un anumit cifr poate fi criptat din nou folosind un cifr diferit.
Orez. 6.1.
Toate posibilele astfel de compoziții ale diferitelor cifruri conduc la a treia clasă de cifre, care sunt de obicei numite cifruri de compoziție. Rețineți că un cifr de compoziție poate să nu fie inclus nici în clasa de cifruri de substituție, nici în clasa de cifruri de permutare (Fig. 6.1).
6.3 Cifre de permutare
Un cifr de permutare, așa cum sugerează și numele, transformă permutarea literelor în text simplu. Un exemplu tipic Cifrul de permutare este cifrul „Scital”. De obicei, textul simplu este împărțit în segmente lungime egală iar fiecare segment este criptat independent. Fie, de exemplu, lungimea segmentelor să fie egală cu și să fie o mapare unu-la-unu a mulțimii în sine. Apoi, cifrul de permutare funcționează astfel: o bucată de text simplu este convertită într-o bucată de text cifrat.
Un exemplu clasic de un astfel de cifru este un sistem care utilizează un card cu găuri - grila, care, atunci când este aplicată pe o coală de hârtie, lasă la vedere doar unele părți din ea. Când sunt criptate, literele mesajului se potrivesc în aceste găuri. Când este decriptat, mesajul se încadrează în diagramă dimensiunile cerute, apoi se aplică un marcaj hash, după care sunt vizibile doar literele textului simplu.
Sunt posibile și alte opțiuni de criptare de permutare, cum ar fi cifrurile cu permutare coloană și dublă.
6.3.1 Cifrul de permutare a coloanei
În timpul decriptării, literele textului cifrat sunt scrise în coloane în funcție de succesiunea numerelor cheilor, după care textul original este citit în rânduri. Pentru a ușura reținerea cheii, coloanele tabelului sunt rearanjate după cuvinte cheie sau fraze, tuturor caracterelor cărora li se atribuie numere determinate de ordinea literelor corespunzătoare din alfabet.
La rezolvarea sarcinilor pentru criptoanaliza cifrurilor de permutare, este necesar să se restabilească ordinea inițială a literelor textului. Pentru a face acest lucru, se folosește analiza compatibilității caracterelor, la care un tabel de compatibilitate poate ajuta (vezi).
| G | CU | Stânga | Pe dreapta | G | CU | |
|---|---|---|---|---|---|---|
| 3 | 97 | l, d, k, t, v, r, n | A | l, n, s, t, r, v, k, m | 12 | 88 |
| 80 | 20 | i, e, y, i, a, o | B | o, s, e, a, r, y | 81 | 19 |
| 68 | 32 | i, t, a, e, i, o | ÎN | o, a, i, s, s, n, l, r | 60 | 40 |
| 78 | 22 | r, y, a, i, e, o | G | o, a, p, l, i, v | 69 | 31 |
| 72 | 28 | r, i, y, a, i, e, o | D | e, a, i, o, n, y, p, v | 68 | 32 |
| 19 | 81 | m, i, l, d, t, r, n | E | n, t, r, s, l, v, m, i | 12 | 88 |
| 83 | 17 | r, e, i, a, y, o | ȘI | e, i, d, a, n | 71 | 29 |
| 89 | 11 | o, e, a și | 3 | a, n, c, o, m, d | 51 | 49 |
| 27 | 73 | r, t, m, i, o, l, n | ȘI | s, n, c, i, e, m, k, h | 25 | 75 |
| 55 | 45 | b, v, e, o, a, i, s | LA | o, a, i, p, y, t, l, e | 73 | 27 |
| 77 | 23 | g, v, s, i, e, o, a | L | i, e, o, a, b, i, yu, y | 75 | 25 |
| 80 | 20 | i, s, a, i, e, o | M | i, e, o, y, a, n, p, s | 73 | 27 |
| 55 | 45 | d, b, n, o, a, i, e | N | o, a, i, e, s, n, y | 80 | 20 |
| 11 | 89 | r, p, k, v, t, n | DESPRE | c, s, t, r, i, d, n, m | 15 | 85 |
| 65 | 35 | în, cu, y, a, i, e, o | P | o, p, e, a, y, i, l | 68 | 32 |
| 55 | 45 | i, k, t, a, p, o, e | R | a, e, o, i, u, i, s, n | 80 | 20 |
| 69 | 31 | s, t, v, a, e, i, o | CU | t, k, o, i, e, b, s, n | 32 | 68 |
| 57 | 43 | h, y, i, a, e, o, s | T | o, a, e, i, b, v, r, s | 63 | 37 |
| 15 | 85 | p, t, k, d, n, m, r | U | t, p, s, d, n, y, w | 16 | 84 |
| 70 | 30 | n, a, e, o și | F | și, e, o, a, e, o, a | 81 | 19 |
| 90 | 10 | y, e, o, a, s și | X | o, i, s, n, v, p, r | 43 | 57 |
| 69 | 31 | e, yu, n, a și | C | i, e, a, s | 93 | 7 |
| 82 | 18 | e, a, y, i, o | H | e, i, t, n | 66 | 34 |
| 67 | 33 | b, y, s, e, o, a, i, v | SH | e, i, n, a, o, l | 68 | 32 |
| 84 | 16 | e, b, a, i, y | SCH | e, i, a | 97 | 3 |
| 0 | 100 | m, r, t, s, b, c, n | Y | L, x, e, m, i, v, s, n | 56 | 44 |
| 0 | 100 | n, s, t, l | b | n, k, v, p, s, e, o și | 24 | 76 |
| 14 | 86 | s, s, m, l, d, t, r, n | E | n, t, r, s, k | 0 | 100 |
| 58 | 42 | b, o, a, i, l, y | YU | d, t, sch, c, n, p | 11 | 89 |
| 43 | 57 | o, n, r, l, a, i, s | eu | c, s, t, p, d, k, m, l | 16 | 84 |
Atunci când analizați compatibilitatea literelor între ele, trebuie să aveți în vedere dependența aspectului literelor în text simplu de un număr semnificativ de litere precedente. Pentru a analiza aceste modele, se folosește conceptul de probabilitate condiționată.
Problema dependenței literelor alfabetului în text simplu față de literele anterioare a fost studiată sistematic de celebrul matematician rus A.A. Markov (1856-1922). El a demonstrat că aparițiile literelor în text clar nu pot fi considerate independente unele de altele. În acest sens, A.A. Markov a remarcat un alt model stabil de texte deschise asociat cu alternanța vocalelor și consoanelor. El a calculat frecvența de apariție a bigramelor vocale-vocale ( g, g), vocală-consoană ( g, s), consoană vocală ( s, g), consoană-consoană ( s, s) în text rusesc cu o lungime de caractere. Rezultatele calculului sunt prezentate în următorul tabel:
| G | CU | Total | |
| G | 6588 | 38310 | 44898 |
| CU | 38296 | 16806 | 55102 |
Exemplul 6.2 Textul simplu, păstrând spații între cuvinte, a fost înregistrat într-un tabel. Începutul a fost în prima linie, textul a fost scris de la stânga la dreapta, trecând de la rând la următorul, criptarea a constat în rearanjarea coloanelor. Găsiți textul simplu.
Cifrarea textului:
| D | ÎN | Y | T | ||
| G | DESPRE | E | R | DESPRE | |
| U | b | D | U | B | |
| M | M | eu | Y | R | P |
Soluţie. Să atribuim numere coloanelor în ordinea în care apar. Sarcina noastră este să găsim o ordine a coloanelor în care textul să aibă sens.
Să facem un tabel:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | X | |||||
| 2 | X | |||||
| 3 | X | |||||
| 4 | X | |||||
| 5 | X | |||||
| 6 | X |
O celulă (,) în acest tabel înseamnă că numărul coloanei urmează numărul coloanei. Marcăm cazurile imposibile cu un „X”.
Combinațiile coloanelor 1, 2 și 5, 2 nu sunt posibile, deoarece o vocală nu poate apărea înaintea unui semn moale. Sunt imposibile și succesiunile coloanelor 2, 1 și 2, 5. Acum, din a treia linie rezultă că 1, 5 și 5, 1 sunt imposibile, deoarece УУ este o bigramă necaracteristică pentru limba rusă. În continuare, două spații la rând nu pot fi în text, ceea ce înseamnă că punem „X” în celulele 3, 4 și 4, 3. Să ne întoarcem din nou la a treia linie. Dacă coloana 2 urmează coloana 4, cuvântul ar începe cu un semn moale. Punem „X” în celula 4, 2. De la prima linie: combinația 4, 5 este imposibilă și, de asemenea, este imposibilă 3, 5. Rezultatul raționamentului nostru este prezentat în tabel:
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | X | X | X | |||
| 2 | X | X | X | |||
| 3 | X | X | X | |||
| 4 | X | X | X | X | ||
| 5 | X | X | X | |||
| 6 | X |
Deci, după coloana 6, trebuie neapărat să urmeze coloana 5. Dar apoi punem un „X” în celula 6, 2 și obținem: coloana 2 urmează coloana 3. Apoi, am tăiat 5, 1 și 2, 1, prin urmare, trebuie să verificăm opțiunile: . ..6532... și...65432... . Dar (4, 3) a fost tăiat mai devreme. Deci, opțiunile rămase pentru aranjarea coloanelor sunt:
- 1, 6, 5, 3, 2, 4
- 6, 5, 3, 2, 4, 1
- 4, 1, 6, 5, 3, 2
- 1, 4, 6, 5, 3, 2
Să scriem 6, 5, 3, 2 coloane pe rând:
| 6 | 5 | 3 | 2 |
| T | s | - | V |
| O | R | O | G |
| b | la | d | b |
| P | R | eu | m |
Încercarea de a pune coloana 1 înaintea coloanei 6 va avea ca rezultat o bigramă MP ultima linieși combinația de DTY în primul. Opțiunile rămase sunt: 653241, 146532.
Răspuns: 653241 - cheie, text simplu: tu\_pe\_pe drum\_fi\_încăpățânat (linie dintr-o melodie populară în anii 1970).
Să dăm un alt exemplu de criptoanaliza a unui cifr de permutare a coloanei.
Exemplul 6.3 Descifrare: SVPOOSLUYYST\_EDPSOKOKAIZO
Soluţie. Textul conține 25 de caractere, ceea ce vă permite să îl scrieți matrice pătrată 5x5. Se știe că criptarea a fost efectuată coloană cu coloană, prin urmare, decriptarea ar trebui efectuată prin schimbarea ordinii coloanelor.
Un cifr din care transformările schimbă doar ordinea simbolurilor text sursă, dar nu le schimbați singuri, se numește un 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 Mesaj originalîntr-o masă dreptunghiulară alegând următorul traseu: 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 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 a liniei 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 cifrul, 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 Foaie albă patru hârtii de aceeași dimensiune moduri posibile tăieturile sale acoperă complet întreaga zonă a foii.
Literele mesajului sunt introduse secvenţial în decupajele stencilului (linie cu linie, în fiecare linie de la stânga la dreapta) în fiecare dintre cele patru poziţii posibile în avans. în modul prescris.
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) din literele mesajului: Scotâ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 de rutare se numește rearanjare verticală„(șurub cu bile). 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 cazurile în care cheia șurubului cu bile nu este recomandat să fie scrisă, 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, să fie cuvântul cheie. Litera A prezentă în el i se dă 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 fi acestea. 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 de 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 al lui Eugen Onegin. Era o jumătate de foaie de hârtie groasă, albăstruie, împăturită în jumătate, 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. Am început să caut 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ă. Tot 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.
Cifre de permutare
Această metodă constă în faptul că caracterele textului criptat sunt rearanjate după anumite reguli în cadrul blocului de caractere criptat, adică. transformările duc la o schimbare numai în ordinea caracterelor din mesajul original. Să ne uităm la unele dintre cele mai comune varietăți ale acestei metode - permutări simple, complicate de tabel și complexe de traseu.
Criptare rearanjare simplă (rearanjarea verticală) se realizează după cum urmează:
1) selectat cuvânt cheie cu caractere care nu se repetă;
2) textul criptat este scris în rânduri consecutive sub simbolurile cuvintelor cheie;
3) 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ă).
Ca o ilustrare, iată un exemplu de criptare folosind o simplă rearanjare a mesajului: „FIȚI ATENȚIE CU REPREZENTANTUL DVS. AL COMPANIEI PHOENIX”. În acest caz aplicăm cheie digitală 5 – 8 – 1 – 3 – 7 – 4 – 6 – 2. În textul sursă, se folosește o literă în loc de spații A.
| B | U | D | b | T | E | A | DESPRE |
| CU | T | DESPRE | R | DESPRE | ȘI | N | Y |
| A | CU | A | P | R | E | D | CU |
| T | A | ÎN | ȘI | T | E | L | E |
| M | A | F | ȘI | R | M | Y | A |
| F | E | N | ȘI | LA | CU | A | A |
Scriind textul în coloane și grupând caracterele câte cinci, obținem textul criptat sub forma:
DO VF NOYSE LRP IIEZH EEMSB S TMF NDLY TOPT RKUTS A E .
Decriptarea se realizează în următoarea ordine:
1) numărați numărul de caractere din textul cifrat și împărțiți la numărul de caractere din cheie;
2) notează cuvântul cheie și sub semnele acestuia, în ordinea corespunzătoare, notează simbolurile criptate în cantitatea determinată mai sus;
3) citiți textul sursă în funcție de rândurile tabelului.
Numărul de chei nu este mai mare de m!, unde m este numărul de coloane din tabel.
Slăbiciunea criptării prin simpla permutare se datorează faptului că, cu o lungime mare a textului criptat, în textul cifrat pot apărea modele de simboluri cheie. Pentru a elimina acest dezavantaj, puteți schimba cheia după criptarea unui anumit număr de caractere. Schimbând cheia suficient de frecvent, puterea criptării poate fi crescută semnificativ. În același timp, însă, organizarea procesului de criptare și decriptare devine mai complicată.
Pentru a obține și a reține o cheie numerică, există diverse metode. Una dintre cele mai frecvente este de a atribui numere literelor în conformitate cu ordinea alfabetică a literelor. Să luăm, de exemplu, cuvântul PERMANENT. Litera A prezentă în ea primește Nr. 1. Dacă o literă apare de mai multe ori, aparițiile ei sunt numerotate succesiv de la stânga la dreapta. Prin urmare, a doua apariție a literei A devine #2. Nu există litera B în acest cuvânt, apoi litera B primește nr. 3 etc.:
| P | E | R | E | CU | T | A | N | DESPRE | ÎN | LA | A |
Făcând mai dificilă rearanjarea unei mese constă în faptul că pentru a înregistra caracterele textului criptat se folosește un tabel special, în care sunt introduse unele elemente complicate. Complicația este că un anumit număr de celule de tabel nu sunt utilizate (sunt goale în figură). Numărul și locația elementelor neutilizate este cheie suplimentară criptare. Text criptat în blocuri de m x n – s elemente (m x n– dimensiunile mesei, s– numărul de elemente neutilizate) se înregistrează în tabel. Criptarea ulterioară este similară cu permutarea simplă.
| B | U | D | b | T | E | A | DESPRE | CU | |
| T | DESPRE | R | DESPRE | ȘI | N | Y | A | ||
| CU | A | DESPRE | R | E | D | CU | T | A | |
| ÎN | ȘI | T | E | L | E | M | A | F | |
| ȘI | R | M | Y | A | F | E | N | ȘI | |
| LA | CU | A | A | A | A | A | A | A |
Textul criptat va arăta astfel: DOPR BSWIK RRTM OY N ENSEF UT I SS AF I HOE EE T ME TJ DL.
În timpul decriptării, caracterele ciphertext sunt scrise în coloane de tabel într-o secvență de caractere cheie, omitând elementele neutilizate. Textul sursă este citit rând cu rând. Variind dimensiunea tabelului, secvența caracterelor cheie și numărul și locația elementelor neutilizate, puteți obține puterea necesară a textului cifrat.
O altă opțiune este cifrarea „Grelă rotativă” . destinat mesajelor de lungime 4mk. Luați un șablon care măsoară 2m*2k celule, decupați m*k celule astfel încât atunci când este aplicat pe o coală de hârtie de aceeași dimensiune 4 căi diferite(rotire cu 90°) decupările sale acoperă complet întreaga zonă a foii. Literele mesajului sunt introduse secvenţial în decupajele stencil pe rânduri, în fiecare rând de la stânga la dreapta, în fiecare dintre cele 4 poziţii posibile ale sale într-o ordine prestabilită. Numărul de șabloane posibile, de ex. numărul de chei din acest cifr este de 4 mk (cu dimensiunea șablonului de 8*8, numărul de opțiuni depășește 4 miliarde).
Se poate obține o putere de criptare foarte mare complicând rearanjamentele de-a lungul rutelor precum cele hamiltoniene. Î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 și trei trasee sunt prezentate în Fig. 7, iar un exemplu de criptare este în Fig. 8. permutare volumetrică (multidimensională).. În 1992 - 94 ideea de a folosi permutarea volumetrică pentru a cripta textul simplu primit dezvoltare ulterioară. O schemă îmbunătățită de permutare bazată pe principiul cubului Rubik, în care, împreună cu textul simplu, permutările sunt de asemenea elemente functionale algoritmul de criptare însuși a stat la baza sistemului Rubicon. Utilizează un cub tridimensional și un tetraedru ca prototipuri de structuri spațiale multidimensionale, bazate pe transformări volumetrice ale căror permutări sunt efectuate.
pe diferite trasee ale unei figuri geometrice.Cel mai simplu exemplu de permutare este permutare cu perioadă fixă d. În această metodă, mesajul este împărțit în blocuri în funcție de d caractere și aceeași permutare se realizează în fiecare bloc. Regula prin care se realizează permutarea este cheia și poate fi specificată printr-o permutare a primei d numere naturale. Drept urmare, literele mesajului în sine nu se schimbă, ci sunt transmise într-o ordine diferită.
De exemplu, pentru d=6, puteți lua 436215 ca cheie de permutare. Aceasta înseamnă că în fiecare bloc de 6 caractere, al patrulea caracter trece pe primul loc, al treilea pe al doilea, al șaselea pe al treilea etc. Să presupunem că trebuie să criptați următorul text:
Numărul de caractere din mesajul original este de 24, prin urmare, mesajul trebuie împărțit în 4 blocuri. Rezultatul criptării folosind permutarea 436215 va fi mesajul
OETET_TLSKDISHR_YAFNAVOI
Teoretic, dacă un bloc este format din d caractere, apoi numărul de permutări posibile d!=1*2*...*(d-1)*d . În ultimul exemplu d=6, prin urmare, numărul de permutări este 6!=1*2*3*4*5*6=720. Astfel, dacă un adversar a interceptat mesajul criptat din exemplul de mai sus, nu i-ar fi nevoie de mai mult de 720 de încercări pentru a rezolva mesajul original (presupunând că dimensiunea blocului este cunoscută de adversar).
Pentru a crește puterea criptografică, două sau mai multe permutări cu perioade diferite pot fi aplicate secvenţial mesajului criptat.
Un alt exemplu de metode de permutare este rearanjarea mesei. În această metodă, textul sursă este scris de-a lungul rândurilor unui tabel și îl citește de-a lungul coloanelor aceluiași tabel. Secvența de umplere a rândurilor și a coloanelor de citire poate fi oricare și este specificată de o cheie.
Să ne uităm la un exemplu. Lăsați tabelul de codificare să aibă 4 coloane și 3 rânduri (dimensiunea blocului este de 3*4=12 caractere). Să criptăm următorul text:
Numărul de caractere din mesajul original este de 24, prin urmare, mesajul trebuie împărțit în 2 blocuri. Să scriem fiecare bloc în tabelul său linie cu linie (Tabelul 2.9).
| 1 bloc | |||
|---|---|---|---|
| E | T | DESPRE | |
| T | E | LA | CU |
| T | D | L | |
| 2 bloc | |||
| eu | SH | ȘI | |
| F | R | DESPRE | ÎN |
| A | N | ȘI | eu |
Apoi vom citi fiecare bloc din tabel secvenţial coloană cu coloană:
ETTTE OKD SLYAFA RNSHOIVYA
Puteți citi coloanele nu secvențial, ci, de exemplu, astfel: al treilea, al doilea, primul, al patrulea:
OKDTE ETT SLSHOI RNYAFAIVA
În acest caz, ordinea în care sunt citite coloanele va fi cheia.
Dacă dimensiunea mesajului nu este un multiplu al dimensiunii blocului, puteți completa mesajul cu orice simboluri care nu afectează semnificația, de exemplu, spații. Totuși, acest lucru nu este recomandat, deoarece oferă inamicului, în cazul interceptării criptogramei, informații despre dimensiunea tabelului de permutare utilizat (lungimea blocului). După ce a determinat lungimea blocului, adversarul poate găsi lungimea cheii (numărul de coloane din tabel) printre divizorii de lungime a blocului.
Să vedem cum să criptăm și să decriptăm un mesaj care nu este un multiplu al mărimii tabelului de permutare. Să criptăm cuvântul
SCHIMBARE
Numărul de caractere din mesajul original este 9. Să scriem mesajul în tabel rând cu rând (Tabelul 2.10) și să lăsăm ultimele trei celule goale.
Apoi vom citi din tabel secvenţial pe coloane:
PMAEERNEC
Pentru a decripta, mai întâi determinați numărul de coloane complete, adică numărul de caractere din ultima linie. Pentru aceasta se împart dimensiunea mesajului(în exemplul nostru – 9) după numărul de coloane sau dimensiunea cheii (în exemplu – 4). Restul diviziunii va fi numărul de coloane complete: 9 mod 4 = 1. Prin urmare, în exemplul nostru a existat 1 coloană completă și trei scurte. Acum puteți pune literele mesajului în locurile lor și puteți descifra mesajul. Deoarece cheia de criptare era numărul 1234 (coloanele au fost citite secvenţial), atunci la decriptare, primele trei caractere (PMA) sunt scrise în prima coloană a tabelului de permutare, următoarele două (EE) - în a doua coloană, următoarele două (RN) - în a treia, iar ultimele două (EK) - în a patra. După ce completăm tabelul, citim rândurile și primim mesajul original SCHIMBARE.
Există și alte metode de permutare care pot fi implementate în software și hardware. De exemplu, atunci când transmiteți date scrise în formă binară, este convenabil să folosiți o unitate hardware care amestecă într-un anumit fel prin cablare adecvată, biți din mesajul original de n biți. Deci, dacă luăm dimensiunea blocului ca fiind de opt biți, putem, de exemplu, să folosim un bloc de permutare, cum ar fi
Asa 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 colțul din stânga 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:
| P | R | Și | m | e | R | m |
| n | T | la | R | w | R | A |
| O | th | P | e | R | e | Cu |
| Și | La | V | O | n | A | T |
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 a dreptunghiului. 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.
Mai complex schimbări de rută poate fi folosit de alții figuri geometriceși trasee mai „delicate”, cum ar fi când ocoliți o tablă de șah cu o „mișcare de cavaler”, cărări în vreun labirint etc. Opțiunile posibile depind de imaginația compilatorului de sistem și, desigur, de cerințele naturale pentru ușurința în utilizare.
