Transformările din acest cifru constau în faptul că textul original este introdus în figură de-a lungul unui „traseu”, iar apoi, de-a lungul celuilalt, este scris din ea. Acest cifr este numit permutarea traseului.
De exemplu, puteți introduce mesajul original într-un tabel 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 pe un traseu diferit: pe verticală, începând din colțul din dreapta sus și deplasându-se alternativ de sus în jos și de jos în sus.
La decriptare, este necesar să se determine numărul de coloane lungi, adică numărul de litere din ultima linie a dreptunghiului. Pentru a face acest lucru, împărțiți numărul de geamanduri din mesaj la lungimea tastei numerice. Restul diviziunii va fi numărul dorit.
Cifrul „Scytala” „ .
Unul dintre cele mai vechi dispozitive de criptare a fost o baghetă (Szitala), 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ă o bandă îngustă de papirus (fără goluri și suprapuneri), iar apoi textul necesar transmiterii a fost 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 lui și a citit mesajul. Este clar că această metodă de criptare permută literele mesajului.
Cifrul `` Scytala '' 'nu mai implementează n permutări ( n- 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 coloană cu coloană. Numărul de coloane din tabel implicate nu poate depăși lungimea mesajului.
Există, de asemenea, limitări pur fizice impuse de implementarea cifrului Scitala. Este firesc să presupunem că diametrul baghetei nu trebuie să depășească 10 centimetri. Cu o înălțime a liniei de 1 centimetru, nu mai mult de 32 de litere (10p< 32). Таким образом, число перестановок, реализуемых ``Сциталой"", вряд ли превосходит 32.
Cod „Grilă pivotantă”.
Pentru a utiliza un cifr numit rețea pivotantă, un șablon este realizat dintr-o foaie dreptunghiulară de hârtie în carouri de dimensiunea celulelor.
Tăiere cu șablon 2 m x 2 k celule, astfel încât atunci când sunt aplicate pe o foaie goală de hârtie de aceeași dimensiune în patru moduri posibile, decupările sale să acopere 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 ale acesteia, într-o ordine predeterminată.
- Cifre de înlocuire. Model matematic. Exemple.
Stream Ciphers (Cezar)
Cifre bloc (port și Pfeiffer)
Baza este un tabel dreptunghiular în care este scris un alfabet amestecat sistematic.
Regula de criptare:
Litere bigrame ( i,j), i ¹ j sunt în acest tabel. Când criptați o bigramă ( i,j) se înlocuiește cu bigrama ( k,l), unde sunt definite cu regulile:
- Dacă iși j nu se află pe un rând sau pe o coloană, atunci pozițiile lor formează vârfuri opuse ale dreptunghiului. Atunci kși l- o altă pereche de vârfuri, și k– Un vârf pe aceeași linie cu i.
- Dacă iși jîntinde-te într-o singură linie, atunci kși l- litere din aceeași linie, situate imediat în dreapta iși j respectiv. Mai mult, dacă una dintre litere este ultima dintr-o linie, atunci se consideră că „vecinul său drept” este prima literă din aceeași linie.
- În mod similar dacă iși j se află în aceeași coloană, apoi sunt înlocuite cu „vecini de jos”.
Exemplu Cifrul Playfair.
Lăsați cifrul să folosească un dreptunghi de 5x6 care conține un alfabet rusesc de 30 de litere combinat sistematic, bazat pe cuvântul cheie „comandant”.
Ca „fachin” vom folosi o literă rară f.
Să reprezentăm fraza ca o secvență de bigrame:
AV TO RO MF ME TO YAV LYA ET SYA UI TS TO NF
Text cifrat:
VP ZD ZR OH DB ZD KN EE TU TSh ShD Tiroidă ZhT ZD OCH
Criptanaliza cifrului Playfair se bazează pe analiza frecvenței bigramelor, trigramelor și a patru grame de text cifrat și pe particularitățile înlocuirii valorilor cifrului cu denumiri de cifr asociate cu locația alfabetului într-un dreptunghi.
Informațiile esențiale despre substituții sunt furnizate de cunoașterea faptului că se folosește un alfabet amestecat sistematic.
- Cifre de permutare. Model matematic. Exemple.
Un cifr, transformări din care doar schimbă ordinea caracterelor din textul original, dar nu le schimbă ele însele, se numește cifr de permutare.
Exemplu
Luați în considerare un mesaj destinat criptării unui mesaj de lungime n personaje. Poate fi reprezentat cu ajutorul unui tabel
Unde i1- numărul locului textului cifrat în care se încadrează prima literă a mesajului original odată cu transformarea selectată, i2- numărul locului pentru a doua literă etc.
Linia de sus a tabelului conține numerele de la 1 la în ordine, iar linia de jos conține aceleași numere, dar fără o ordine anume. Un astfel de tabel se numește substituție de putere n... Cunoscând substituția care definește transformarea, este posibil să se efectueze atât criptarea, cât și decriptarea textului.
Cunoscând substituția care definește transformarea, este posibil să se efectueze atât criptarea, cât și decriptarea textului. De exemplu, dacă transformarea folosește substituția
și în conformitate cu acesta, cuvântul Moscova este criptat,
primești COSVMA.
Numărul de transformări diferite ale unui cifr de permutare concepute pentru a cripta mesajele de lungime n, mai mic sau egal n!(acest număr include și o opțiune de conversie care lasă toate personajele la locul lor!).
- Codurile de jocuri. Model matematic. Exemple.
Gamma este o metodă de criptare simetrică bazată pe „impunerea” unei secvențe gamma pe un text simplu. De obicei, aceasta este o însumare într-un câmp finit.
Principiul criptării constă în formarea unei game de criptări de către un generator de numere pseudo-aleatoare (PRNG) și impunerea acestei game asupra datelor deschise în mod reversibil, de exemplu, prin adăugarea modulo doi. Procesul de decriptare a datelor se rezumă la regenerarea cifrului gamma și aplicarea gama la datele criptate. Cheia de criptare în acest caz este starea inițială a generatorului de numere pseudoaleatoare. Cu aceeași stare inițială, PRNG va genera aceleași secvențe pseudo-aleatoare.
- Principii ale cifrurilor bloc de construcție. Schema lui Feistel.
Rețeaua Feistel:
Rețeaua Feistel este o metodă generală de transformare a unei funcții arbitrare Fîntr-o permutare pe un set de blocuri. Constă din celule care se repetă ciclic - runde. În fiecare rundă, blocul de text simplu este împărțit în două părți egale. Funcție rotundă
ia o jumătate (chiar în figură), o transformă folosind o cheie K i iar rezultatul XOR cu cealaltă jumătate. Această cheie este setată de cheia originală Kși este diferit pentru fiecare rundă. Apoi jumătățile sunt schimbate (altfel doar o jumătate din bloc va fi transformată) și servite pentru runda următoare. Transformarea rețelei Feistel este o operațiune reversibilă.
Pentru funcție F există anumite cerințe:
Munca sa ar trebui să ducă la un efect de avalanșă
Trebuie să fie neliniar în ceea ce privește operațiunea XOR
Dacă prima cerință nu este îndeplinită, rețeaua va fi susceptibilă la atacuri diferențiate (mesajele similare vor avea cifruri similare). În al doilea caz, acțiunile cifrului sunt liniare și pentru rupere este suficientă rezolvarea unui sistem de ecuații liniare.
Acest design are un avantaj tangibil: procedurile de criptare/decriptare sunt aceleași, doar cheile derivate din original sunt folosite în ordine inversă. Aceasta înseamnă că aceleași blocuri pot fi folosite atât pentru criptare, cât și pentru decriptare, ceea ce simplifică cu siguranță implementarea cifrului. Dezavantajul acestei scheme este că doar jumătate din bloc este procesat în fiecare rundă, ceea ce duce la necesitatea creșterii numărului de runde.
Schimbați criptarea constă în faptul că caracterele textului simplu sunt rearanjate după o anumită regulă în cadrul unui anumit bloc al acestui text. Luați în considerare o permutare concepută pentru a cripta un mesaj de lungime n personaje. Poate fi reprezentat cu folosind tabelul
Unde i 1 – numărul locului textului cifrat în care se încadrează prima literă a textului simplu în transformarea selectată, i 2 - numărul locului pentru a doua literă etc. Linia de sus a tabelului conține numere de la 1 la n, iar în partea de jos sunt aceleași numere, dar fără o ordine anume. Un astfel de tabel se numește permutare de grade n.
Cunoscând permutarea care definește transformarea, este posibil să se efectueze atât criptarea, cât și decriptarea textului. În acest caz, tabelul de permutare în sine servește ca cheie de criptare.
Numărul de transformări diferite ale unui cifr de permutare concepute pentru a cripta mesajele de lungime n, mai mic sau egal n! (n factoriale). Rețineți că acest număr include și o opțiune de conversie care lasă toate caracterele la locul lor.
Cu o creștere a numărului n sens n! creste foarte repede. Pentru utilizare practică, un astfel de cifru nu este convenabil, deoarece la valori mari n trebuie să lucrezi cu mese lungi. Prin urmare, s-au răspândit cifrurile care folosesc nu tabelul de permutare în sine, ci o anumită regulă care generează acest tabel. Să luăm în considerare câteva exemple de astfel de cifruri.
Cifrul de permutare „rătăcire”. Se știe că în secolul al V-lea î.Hr., conducătorii Spartei, cel mai militant dintre statele grecești, aveau un sistem bine dezvoltat de comunicații militare secrete și își criptau mesajele folosind rătăcire, primul cel mai simplu dispozitiv criptografic care implementează metoda permutării simple.
Criptarea a fost efectuată după cum urmează. O fâșie de pergament a fost înfășurată într-o spirală (coil to coil) pe o tijă cilindrică numită skitala și mai multe rânduri de text de mesaj au fost scrise pe ea de-a lungul tijei (Fig. 1.2). Apoi s-a scos din tijă o fâșie de pergament cu textul scris. Literele de pe această bandă s-au dovedit a fi localizate aleatoriu.
Orez. 1.2. Cifrul „Skital”.
Același rezultat poate fi obținut dacă literele mesajului sunt scrise în cerc nu pe rând, ci după un anumit număr de poziții până la epuizarea întregului text. Mesaj " INCEPE„când sunt plasate de-a lungul circumferinței tijei, fiecare trei litere oferă textul cifrat:” NUTAPESA_TY".
Pentru a decripta un astfel de text cifrat, trebuie nu numai să cunoașteți regula de criptare, ci și să aveți o cheie sub forma unei tije cu un anumit diametru. Cunoscând doar tipul de cifru, dar neavând cheia, nu a fost ușor să descifrezi mesajul.
Tabelele de criptare. De la începutul Renașterii (sfârșitul secolului al XIV-lea), și criptografie a început să revină. În cifrurile de permutare dezvoltate la acea vreme, s-au folosit tabele de cifrare care, în esență, stabileau regulile pentru permutarea literelor dintr-un mesaj.
Următoarele sunt folosite ca cheie în tabelele de criptare:
dimensiunea mesei;
un cuvânt sau o expresie care definește o permutare;
caracteristici ale structurii tabelului.
Unul dintre cele mai primitive cifruri de permutare a tabelului este o permutare simplă, pentru care dimensiunea tabelului este cheia. Această metodă de criptare este similară cu cifrul rătăcitor. De exemplu, mesajul „ TERMINATOR sosește șapte la miezul nopții„se scrie în tabel unul câte unul coloană cu coloană. Rezultatul umplerii unui tabel de 5 rânduri și 7 coloane este prezentat în Fig. 1.3.
După ce ați completat tabelul cu textul mesajului pe coloane pentru a forma textul cifrat, citiți conținutul tabelului pe rânduri. Dacă textul cifrat este scris în grupuri de cinci litere, primiți următorul mesaj criptat: " TNPVE GLEAR ADONR TIEEV OMOBT MPCHIR YSOOO".
Orez. 1.3. Popularea unui tabel de criptare de 5 rânduri și 7 coloane
Desigur, expeditorul și destinatarul mesajului trebuie să cadă de acord în prealabil asupra unei chei comune sub forma unei dimensiuni de tabel. Trebuie remarcat faptul că combinația de litere ale textului cifrat în grupuri de 5 litere nu este inclusă în cheia de cifră și este efectuată pentru confortul scrierii unui text fără sens. La decriptare, acțiunile sunt efectuate în ordine inversă.
Metoda de criptare numită permutarea unei singure taste... Această metodă diferă de cea anterioară prin faptul că coloanele tabelului sunt rearanjate după un cuvânt cheie, o expresie sau un set de numere atât de lungi cât un rând de tabel.
Să folosim ca cheie, de exemplu, cuvântul „ PELICAN", și luați textul mesajului din exemplul anterior. Figura 1.4 prezintă două tabele completate cu textul mesajului și un cuvânt cheie, cu tabelul din stânga corespunzând umplerii înainte de schimbare, iar tabelul din dreapta completării după schimb.
Orez. 1.4. Cifrați tabelele pline cu cuvinte cheie și text de mesaj
Cheia este scrisă în linia de sus a tabelului din stânga, iar numerele de sub literele cheie sunt determinate în conformitate cu ordinea naturală a literelor cheie corespunzătoare din alfabet. Dacă s-ar găsi litere identice în cheie, acestea ar fi numerotate de la stânga la dreapta. În tabelul din dreapta, coloanele sunt rearanjate în funcție de numerele de litere ordonate ale cheii.
Când citim conținutul tabelului drept cu rând și scriem textul cifrat în grupuri de cinci litere, primim un mesaj criptat: " GNVEP LTOOA DRNEV TEIO RPOTM BCHMOR SOYYI".
Pentru un secret suplimentar, puteți recripta un mesaj care a fost deja criptat. Această metodă de criptare este numită dubla permutare. În cazul permutării duble a coloanelor și rândurilor din tabel, permutările sunt definite separat pentru coloane și separat pentru rânduri. Mai întâi, textul mesajului este scris în tabel, apoi coloanele sunt rearanjate alternativ, iar apoi rândurile. La decriptare, ordinea permutărilor trebuie inversată.
Un exemplu de realizare a criptării folosind metoda permutării duble este prezentat în Fig. 1.5. Dacă citiți textul cifrat din tabelul din dreapta linie cu rând în blocuri de patru litere, obțineți următoarele: " TYUAE OOGM RLIP OSV".
Orez. 1.5. Un exemplu de realizare a criptării utilizând metoda dublei permutări
Cheia cifrului cu permutare dublă este succesiunea numerelor de coloană și a numerelor de rând ale tabelului original (în exemplul nostru, secvențele sunt 4132 și, respectiv, 3142).
Numărul de opțiuni de permutare dublă crește rapid pe măsură ce dimensiunea tabelului crește:
36 de opțiuni pentru o masă 3x3;
pentru masa 4x4 576 opțiuni;
pentru o masă 5x5 există 14.400 de opțiuni.
Criptare folosind pătrate magice.În Evul Mediu, pătratele magice erau folosite și pentru criptarea permutării. ... Pătrate magice se numesc tabele pătrate cu numere naturale secvențiale înscrise în celulele lor, începând de la 1, care însumează același număr pentru fiecare coloană, fiecare rând și fiecare diagonală.
Textul criptat a fost înscris în pătrate magice, în conformitate cu numerotarea celulelor lor. Dacă apoi scrieți conținutul unui astfel de tabel rând cu rând, obțineți un text cifrat format prin rearanjarea literelor mesajului original.
Un exemplu de pătrat magic și umplerea lui cu un mesaj " SOSIREA CEI OPPT„este prezentat în Fig. 1.6.
Orez. 1.6. Un exemplu de pătrat magic 4x4 și umplerea acestuia cu un mesaj
Textul cifrat, primit la citirea conținutului tabelului drept cu rând, pare destul de misterios: „ ORM EOSYU VTAT LGOP".
Numărul de pătrate magice crește rapid odată cu dimensiunea pătratului. Există doar un pătrat magic de 3x3 (fără numărarea rotațiilor acestuia). Numărul de pătrate magice 4x4 este deja 880, iar numărul de pătrate magice 5x5 este de aproximativ 250.000.
Pătratele magice de dimensiuni medii și mari ar putea servi ca o bază bună pentru satisfacerea nevoilor de criptare din acea perioadă, deoarece este aproape imposibil să enumerați manual toate opțiunile pentru un astfel de cifr.
O varietate de permutare a rutei - permutarea verticală - a devenit larg răspândită. Acest cifru folosește și un tabel dreptunghiular în care mesajul este scris rând cu rând de la stânga la dreapta. Un cifr este scris vertical, cu coloanele selectate în ordinea specificată de cheie.
TEXT DESCHIS: Exemplu de schimbare a rutei
CHEIE: (3, 1, 4, 2, 5)
CRIPTOGRAMA: rmuptkmrnprrrysviateaieshoeo
Nu este practic 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 de permutare verticală. Este o variație a cifrului anterior. Caracteristicile cifrului includ următoarele:
Numărul de coloane din tabel este fix și determinat de lungimea cheii;
Calea de intrare este strict de la stânga la dreapta de sus în jos;
Programul de cifrare este scris în coloane în funcție de numerotarea lor (cheie).
Figura 5.5. Exemplu de utilizare a cifrului de permutare verticală
Puteți folosi un cuvânt sau o expresie ca cheie. Apoi, ordinea de scriere a coloanelor corespunde ordinii alfabetice a literelor din cheie. De exemplu, dacă cuvântul cheie este „UNCLE”, atunci litera prezentă în el A primește numărul 1, D- 2 etc. Dacă o literă apare într-un cuvânt de mai multe ori, atunci aparițiile sale sunt numerotate secvenţial de la stânga la dreapta. În exemplu, prima literă D primește numărul 2, al doilea D – 3.
La criptarea mesajului „ABRAMOV ILYA SERGEEVIC”, rezultatul va fi „OYAE_AV_ERIEIALRCHMG_B_SV”.
(Vezi si )
Lucrările matematicianului american Claude Shannon, apărute la mijlocul secolului al XX-lea, au influențat foarte mult dezvoltarea criptografiei. În aceste lucrări s-au pus bazele teoriei informației și s-a dezvoltat un aparat matematic pentru cercetarea î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 sa în dezvoltarea cifrurilor. S-a dovedit că, chiar și în cifre foarte complexe, astfel de cifre simple precum cifruri de înlocuire, cifre de permutare sau combinații ale acestora.
Ca criteriu principal prin care se realizează clasificarea cifrurilor, se utilizează tipul de transformare efectuată cu textul simplu în timpul criptării. Dacă fragmente de 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 schimbă doar locuri între ele, atunci avem de-a face cu cifru de permutare... Pentru a îmbunătăți fiabilitatea criptării, textul cifrat obținut prin utilizarea anumitor cifruri poate fi din nou criptat folosind un alt cifr.
Orez. 6.1.
Toate tipurile de 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ă cifrul de compoziție poate să nu fie inclus nici în clasa de criptare de înlocuire, nici în clasa de criptare de permutare (Fig. 6.1).
6.3 Coduri de permutare
Cifrul de permutare, după cum sugerează și numele, convertește permutarea literelor în text simplu. Un exemplu tipic de cifru de permutare este cifrul „Scital”. De obicei, textul simplu este împărțit în segmente de lungime egală și fiecare segment este criptat independent. De exemplu, lăsați lungimea segmentelor să fie egală cu și să fie o mapare unu-la-unu a mulțimii 
în tine însuți. 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 - zăbrele, care, atunci când este aplicată pe o coală de hârtie, lasă deschise doar câteva dintre părțile sale. Când sunt criptate, literele mesajului se potrivesc în aceste găuri. La decriptarea mesajului, acesta se încadrează într-o diagramă a dimensiunilor necesare, apoi se aplică o zăbrele, după care sunt vizibile doar litere de text simplu.
Alte variante ale cifrului de permutare sunt, de asemenea, posibile, de exemplu, cifrurile cu permutare columnară și dublă.
6.3.1 Cifrul de permutare a coloanei
În timpul decriptării, literele textului cifrat sunt scrise coloană cu coloană în conformitate cu succesiunea numerelor cheilor, după care textul original este citit rând cu rând. Pentru confortul memorării cheii, coloanele tabelului sunt rearanjate printr-un cuvânt cheie sau o expresie, cărora li se atribuie numere tuturor simbolurilor determinate de ordinea literelor corespunzătoare din alfabet.
La rezolvarea sarcinilor de criptoanaliza a cifrurilor de permutare, este necesar să se restabilească ordinea inițială a literelor textului. Pentru aceasta se folosește o analiză de compatibilitate a caracterelor, care poate fi ajutată de un tabel de colare (vezi).
| G | CU | Stânga | Pe dreapta | G | CU | |
|---|---|---|---|---|---|---|
| 3 | 97 | l, d, k, t, v, r, n | A | l, n, s, t, p, v, k, m | 12 | 88 |
| 80 | 20 | i, e, y și, a, o | B | o, s, e, a, p, y | 81 | 19 |
| 68 | 32 | i, t, a, e, u, o | V | o, a, i, s, s, n, l, r | 60 | 40 |
| 78 | 22 | p, y, a, u, e, o | G | o, a, p, l, u, b | 69 | 31 |
| 72 | 28 | p, i, y, a, i, e, o | D | e, a, u, 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 | p, e, u, a, y, o | F | e, i, d, a, n | 71 | 29 |
| 89 | 11 | o, e, a și | 3 | a, n, v, o, m, d | 51 | 49 |
| 27 | 73 | p, t, m, i, o, l, n | ȘI | s, n, v, i, e, m, k, z | 25 | 75 |
| 55 | 45 | b, b, f, o, a, i, c | LA | o, a, u, p, y, t, l, e | 73 | 27 |
| 77 | 23 | r, v, s, i, e, o, a | L | u, e, o, a, b, i, u, u | 75 | 25 |
| 80 | 20 | i, s, a, i, e, o | M | i, e, o, y, a, n, n, s | 73 | 27 |
| 55 | 45 | d, b, n, o, a, i, e | N | o, a, i, e, s, n, y | 80 | 20 |
| 11 | 89 | p, n, k, v, t, n | O | v, s, t, p, i, d, n, m | 15 | 85 |
| 65 | 35 | c, c, y, a, i, e, o | P | o, p, e, a, y, u, l | 68 | 32 |
| 55 | 45 | u, k, t, a, p, o, e | R | a, e, o, i, y, i, s, n | 80 | 20 |
| 69 | 31 | s, t, v, a, e, u, 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, b, p, c | 63 | 37 |
| 15 | 85 | n, t, k, d, n, m, r | Avea | t, n, s, d, n, u, f | 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, u, s, n, v, p, r | 43 | 57 |
| 69 | 31 | e, u, n, a și | C | u, e, a, s | 93 | 7 |
| 82 | 18 | e, a, y, u, o | H | e, u, t, n | 66 | 34 |
| 67 | 33 | b, y, s, e, o, a și, în | SH | e, i, n, a, o, l | 68 | 32 |
| 84 | 16 | f, b, a, i, u | SCH | e, u, a | 97 | 3 |
| 0 | 100 | m, r, t, s, b, c, n | S | L, x, e, m, i, v, s, n | 56 | 44 |
| 0 | 100 | n, s, t, l | B | n, k, v, n, s, e, o și | 24 | 76 |
| 14 | 86 | s, s, m, l, d, t, r, n | E | n, t, p, 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, p, l, a, u, s | EU SUNT | v, s, t, p, d, k, m, l | 16 | 84 |
Când se analizează compatibilitatea literelor între ele, ar trebui să se țină seama de dependența apariției literelor în textul simplu de un număr semnificativ de litere precedente. Pentru a analiza aceste modele, se folosește conceptul de probabilitate condiționată.
Celebrul matematician rus A.A. Markov (1856-1922). El a demonstrat că apariția literelor în text simplu nu poate fi considerată independentă una de alta. Î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 vocală-vocală ( r, r), vocală-consoană ( r, s), consoană vocală ( s, g), consoană-consoană ( s, s) în text rusesc cu lungimea în caractere. Rezultatele calculului sunt reflectate î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 scris în tabel. Începutul a fost în prima linie, textul a fost scris de la stânga la dreapta, trecând de la o linie la alta, criptarea a constat în rearanjarea coloanelor. Găsiți text simplu.
Text cifrat:
| D | V | S | T | ||
| G | O | E | R | O | |
| Avea | B | D | Avea | B | |
| M | M | EU SUNT | S | R | P |
Soluţie. Să atribuim numere coloanelor în ordinea în care apar. Sarcina noastră este să găsim o astfel de 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ă coloana numerotată urmează coloanei numerotate. Marcam 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. Succesiunea coloanelor 2, 1 și 2, 5 este, de asemenea, imposibilă. Acum din a treia linie rezultă că 1, 5 și 5, 1 sunt imposibile, deoarece UU este o bigramă necaracteristică pentru limba rusă. În plus, două spații la rând nu pot fi în text, ceea ce înseamnă că punem un „X” în celulele 3, 4 și 4, 3. Să ne întoarcem din nou la a treia linie. Dacă coloana 2 urmează coloana 4, atunci cuvântul ar începe cu un semn moale. Punem „X” în celulele 4, 2. Din prima linie: combinația dintre 4, 5 este imposibilă și 3, 5 este, de asemenea, imposibilă. 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 „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ă verificați opțiunile:. . 6532 ... și ... 65432 .... Dar (4, 3) a fost șters mai devreme. Deci, opțiunile pentru aranjarea coloanelor rămân:
- 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 sunt | m |
Încercarea de a pune coloana 1 în fața coloanei 6 va avea ca rezultat o bigramă MT pe ultimul rând și o combinație de DTA pe primul. Opțiunile rămase sunt: 653241, 146532.
Răspuns: 653241 - cheie, text simplu: tu \ _in \ _the road \ _fi \ _ încăpățânat (un vers dintr-o melodie populară în anii 1970).
Iată un alt exemplu de criptoanaliza a cifrului de permutare a coloanei.
Exemplul 6.3 Decriptare: SORRY \ _EDPSOCOKAIZO
Soluţie. Textul conține 25 de caractere, ceea ce îi permite să fie scris într-o matrice pătrată de 5x5. Se știe că criptarea a fost efectuată coloană cu coloană, prin urmare, decriptarea ar trebui efectuată prin schimbarea ordinii coloanelor.
Cifrul de permutare „rătăcire”. În secolul V. î.Hr. conducătorii statului grec Sparta aveau un sistem bine pus la punct de comunicații militare secrete și își criptau mesajele cu ajutorul wander-ului, primul dispozitiv criptografic simplu care implementează metoda permutării simple (Fig. 1.6).
Orez. 1.6.
Criptarea a fost efectuată după cum urmează. Pe o tijă cilindrică, care se numea skitala, o fâșie de piele era înfășurată în spirală (turn-to-turn) și pe ea erau scrise mai multe rânduri de text de mesaj de-a lungul tijei. Apoi au scos banda din tijă - literele de pe ea s-au dovedit a fi localizate la întâmplare.
Mesagerul obișnuia să ascundă mesajul folosind o bandă de piele pe post de curea, adică. pe lângă criptare s-a folosit și steganografia. Pentru a obține mesajul original, o fâșie de piele trebuie înfășurată în jurul unei folii de același diametru. Cheia acestui cifr este diametrul tijei - de la cifr. Cunoscând doar tipul de cifru, dar neavând cheia, nu este ușor să descifrezi mesajul. Cifrul „rătăcitor” a fost îmbunătățit de multe ori în perioadele ulterioare.
Modul de a sparge acest cifr a fost propus de Aristotel. Este necesar să faceți un con lung și, începând de la bază, să-l înfășurați cu o bandă cu un mesaj criptat, deplasându-l treptat spre vârf. La un moment dat, fragmente din mesaj vor începe să fie vizualizate. Diametrul conului în acest punct corespunde cu diametrul rătăcirii.
Tabelele de criptare. Unul dintre cele mai primitive cifruri de permutare a tabelului este o permutare simplă, pentru care dimensiunea tabelului este cheia. Această metodă de criptare în forma sa cea mai simplă este similară cu cifrul „rătăcitor”. De exemplu, mesajul text este scris într-un tabel de o anumită dimensiune într-o coloană și citit în rânduri.
Să scriem expresia „Terminator sosește pe al șaptelea la miezul nopții” într-un tabel 5x7 (Fig. 1.7) dar coloane. După ce am scris textul din tabel rând cu rând, vom primi codul: "tnnweglearadonrtie'vobtmnchirysooo".
Orez. 1.7.
Expeditorul și destinatarul mesajului trebuie să convină în prealabil asupra unei chei comune sub forma unei dimensiuni de tabel. La decriptare, acțiunile sunt efectuate în ordine inversă (scriere rând cu rând, citire pe coloane).
Acest cifru poate fi oarecum complicat: de exemplu, coloanele pot fi rearanjate într-o anumită secvență determinată de cheie. Posibilă dublă permutare - coloane și rânduri.
Grila Cardano. O grilă Cardano (grilă pivot) este o carte dreptunghiulară sau pătrată cu un număr par de rânduri și coloane 2k X 2t. Găurile sunt făcute în el în așa fel încât, cu reflexia sau rotirea succesivă și umplerea celulelor deschise ale cardului, toate celulele foii să fie umplute treptat.
Cardul este mai întâi reflectat în jurul axei verticale de simetrie, apoi în jurul axei orizontale și din nou în jurul axei verticale (Figura 1.8).
Dacă rețeaua Cardano este pătrată, atunci este posibilă o altă variantă a transformărilor sale - rotație cu 90 ° (Fig. 1.9).
Orez. 1.8.
Orez. 1.9.
Când scrieți în mod obișnuit (de la stânga la dreapta și de sus în jos) expresia „criptare text” (fără spații) în celulele libere ale rețelei rotative prezentate în Fig. 1.9, obținem textul sub forma unui tabel (Fig. 1.10) sau, scriind textul pe o singură linie, - "kshiioesvtafatren".
Orez. 1.10.
Destinatarul trebuie să cunoască șablonul și să îl aplice în aceeași secvență ca la criptare. Cheia este tipul selectat de mișcare a rețelei (reflexie sau rotație) și șablonul - locația găurilor, care pentru o zăbrele pătrată sunt 2t X 2k poate fi selectat în 4 "" * moduri (ținând cont de orientarea inițială a șablonului). În acest caz, printre șabloanele considerate a fi diferite, vor fi cele care sunt imagini în oglindă sau rotații ale altor șabloane, adică. stenciluri diferind doar prin locația inițială (orientare). Dacă neglijăm poziția inițială a șablonului, atunci, evident, vor fi de 4 ori mai puține șabloane diferite - 4 "" * "
De exemplu, pentru grile 4X4, există 256 de opțiuni posibile de șabloane (pe baza orientării inițiale) sau un total de 64 de șabloane diferite.
În ciuda faptului că numărul de șabloane pentru zăbrele mari este destul de mare (aproximativ 4 milioane (4-10 e)), este încă semnificativ mai mic decât numărul de permutări aleatorii ale elementelor de tabel, al căror număr este (2t? 2k).
De exemplu, pentru un tabel 4x4, numărul de permutări aleatorii este de ordinul a 2? 10 13, iar pentru mesele 8x8 - aproximativ 10 89.
Rețelele Cardano, ca și tabelele de cifrare, sunt cazuri speciale de rutare a cifrurilor de permutare.
