Criptare folosind metoda permutării. Tipuri și metode de criptare. Cifre de permutare

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.

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.

Cifre de înlocuire (de înlocuire). se bazează pe o operaţie algebrică numită substituţie. O permutare este o mapare unu-la-unu a unei multimi finite M pe sine. Numărul N de elemente ale mulțimilor se numește grad de substituție. Numărul n de numere mutate efectiv prin substituție se numește lungimea ciclului de substituție.

Cifre de permutare este un cifr, a cărui conversie este schimbată numai ordinea apariţiei caracterele textului sursă, dar nu le modificați singuri.

Slăbiciunea cifrurilor de înlocuire. Dacă un anumit caracter apare frecvent într-un mesaj deschis, atunci caracterul corespunzător apare cu aceeași frecvență într-un mesaj criptat. Pentru cantități mari de text, acest lucru duce la o criptoanaliză de succes. Astfel, este imposibil să criptezi mesajele suficient de lungi folosind o singură cheie.

Rețele (ca element de criptare) - orice cifru bloc este o combinație a primelor două scheme. Utilizarea conceptului de „rețele” în criptarea bloc implică repetarea operațiunilor originale de mai multe ori (repetițiile sunt cicluri sau runde, iar operațiunile în sine sunt straturi). Unele dintre straturi pot conține chei. Asta permite:

Faceți cifrul ușor de complicat (prin creșterea numărului de runde)
Reduceți dimensiunea codului
Unificați formula de criptare algoritmică

Rețeaua Feisil (Feistel) este o metodă de construire a unui ciclu de criptare în algoritmi de criptare iterativă bazat pe un registru de deplasare, cu o funcție de feedback în funcție de cheia rotundă (numărul optim de runde este de la 8 la 32)

DES – standard federal de criptare din SUA (1997-2001).

Arhitectura este o rețea Faisil clasică, echilibrată, cu permutări inițiale și finale de biți de formă generală. Dimensiunea cheii este de 56 de biți. Se bazează pe standardul internațional ISO 8372-87. Algoritmul este conceput pentru a cripta datele în blocuri de 64 de biți.

DES este o combinație a două metode principale:

Substituţie
Rearanjare.

O singură combinație a acestor două metode este aplicată textului.

DES are 16 runde, ceea ce înseamnă că aceeași combinație de metode este aplicată textului simplu de 16 ori.

Runda cheii este aplicată utilizând operația XOR

Text sursă => Permutare inițială => Criptare * 16(<=Ключ) =>Permutarea finală => text cifrat

Scopul permutării inițiale este de a distribui uniform biții adiacenți în blocuri.

Aceeași funcție poate fi folosită pentru a cripta și decripta, dar cheile sunt folosite în ordine inversă.

DES oferă 4 tipuri de muncă:

ECB-pad de cifră electronică. Textul simplu este procesat în blocuri de 64 de biți, criptat cu o singură cheie
CBC - block chain. Elimină dezavantajul primului mod. Valoarea de intrare a algoritmului de criptare este setată egală cu diferența XOR dintre blocul de text simplu curent și blocul de text cifrat obținut la pasul anterior. Astfel, toate blocurile textului original sunt conectate (text=>ciphertext=>XOR=>text=>ciphertext)
CFB – feedback cu text cifrat. Algoritmul este convertit într-un cifr de flux, adică fiecare caracter poate fi criptat și transmis imediat destinatarului
OFB – feedback de ieșire. O parte a textului cifrat este introdusă în registrul de deplasare. Pentru fiecare sesiune de criptare, este utilizată o nouă stare inițială a registrului.

Se crede că patru moduri sunt suficiente pentru a utiliza DES în aproape orice zonă pentru care algoritmul este potrivit

Implementarea hardware a algoritmului pe un cip separat face posibilă atingerea unor viteze mari de criptare cu dimensiuni mici ale dispozitivului.

AES este standardul federal de criptare din SUA, utilizat în prezent.

AES este un standard avansat de criptare.

Cerințe:

Cifrul trebuie să fie blocat
Cifrul trebuie să aibă o lungime de bloc de 128 de biți
Cifrul trebuie să accepte chei cu lungimea de 128, 192, 256 de biți

Algoritmul este un cifr bloc neconvențional deoarece nu folosește o rețea Feishtel pentru criptotransformări.

Algoritmul reprezintă fiecare bloc de date codificate ca o matrice bidimensională de octeți de dimensiunea 4x4, 4x6 sau 4x8, în funcție de lungimea blocului setată.

Algoritmul constă dintr-un anumit număr de runde (de la 10 la 14 - aceasta depinde de dimensiunea blocului și lungimea cheii).

GOST 28147089 – standard rusesc pentru criptarea datelor și protecția datelor.

Algoritmul este conceput pentru implementare hardware și software, satisface cerințele criptografice necesare și nu impune restricții cu privire la gradul de secretizare a informațiilor protejate.

Algoritmul implementează criptarea blocurilor de date de 64 de biți folosind o cheie de 256 de biți constând din opt subchei de 32 de biți.

La fiecare i-a rundă, este utilizată subcheia K i-a.

Algoritmii de criptare GOST 28147-89 au avantajele altor algoritmi pentru sisteme simetrice și le depășesc în capacitățile lor.

La fiecare i-a rundă a algoritmului GOST, sunt efectuate următoarele operații:

L i =R i -1 , R i =L i -1 (plus cerc)f(R i -1 , Ki i)

După finalizarea acestor 32 de operațiuni, implementarea algoritmului de criptare va fi finalizată.

Avantajul GOST este prezența protecției împotriva impunerii de date false (modul de inserare a imitației), precum și același ciclu de criptare în toate cele 4 moduri (algoritmi) ale GOST.

Puterea criptografică ridicată este asigurată datorită lungimii mari a cheii (256 de biți) și a 32 de runde de conversie.

Standardul include moduri (algoritmi):

Mod de înlocuire ușoară
Modul Gamma
Modul Gamma cu feedback
Modul de generare a inserției de simulare

Algoritmi de criptare asimetrici.

În algoritmii de criptare asimetrică (sau criptografia cu cheie publică), o cheie (publică) este utilizată pentru informații criptate, iar alta (secretă) este utilizată pentru decriptare.

Aceste chei sunt diferite și nu pot fi derivate unele de altele.

Schema de schimb de informații:

Destinatarul calculează cheile publice și secrete; cheia secretă este păstrată secretă, dar cheia publică este pusă la dispoziție (informează expeditorul, un grup de utilizatori ai rețelei, publică)
Expeditorul, folosind cheia publică a destinatarului, criptează mesajul care este trimis destinatarului
Destinatarul primește mesajul și îl decriptează folosind cheia sa privată

Folosind o metodă de criptare asimetrică

Utilizarea unor astfel de cifruri a devenit posibilă datorită lui K. Shannon, care a propus construirea unui cifr în așa fel încât soluția lui să fie echivalentă cu rezolvarea unei probleme matematice care necesită efectuarea unor volume de calcule care depășesc capacitățile computerelor moderne (de exemplu, operații cu numere prime mari și produsele acestora; aflarea valorii produsului P =x*y)

Criptosistem de criptare a datelor RSA.

În prezent, cea mai dezvoltată metodă de protecție a informațiilor criptografice cu o cheie cunoscută este RSA, numită după literele inițiale ale numelor inventatorilor săi (Rivest, Shamir, Adleman)

Pentru a utiliza algoritmi RSA, trebuie mai întâi să generați o cheie publică și privată urmând acești pași:

Alegeți două numere prime foarte mari p și q și definiți n ca rezultat al înmulțirii p cu q (n=p*q)
Alegeți un număr mare aleatoriu d. Acest număr trebuie să fie coprim la m, rezultatul înmulțirii (p-1)(q-1)
Determinați un număr e pentru care următoarea relație este adevărată (e*d)mod(m)=1 sau e=(1mod(m))/d
Cheia publică va fi numerele e,n, iar cheia secretă vor fi numerele d,n

Crearea cheii este evidențiată cu roșu.

Criptosisteme asimetrice bazate pe curbe eliptice.

Pe baza curbelor eliptice E, este posibil să se implementeze nu numai algoritmi criptografici pentru criptarea asimetrică, ci și să se genereze o cheie secretă partajată pentru criptarea simetrică.

Criptosistemele bazate pe curbe eliptice permit utilizarea unor chei semnificativ mai mici în comparație cu alți algoritmi criptografici, menținând în același timp același nivel de putere criptografică.

Pentru implementările de mai sus, sunt utilizate curbele eliptice peste câmpurile Galois GF(p) cu un număr finit p de elemente de două tipuri:

Curbă eliptică peste un câmp finit de tip E(GF(p)), unde p este un număr prim
Curba eliptică peste un câmp finit de tip E(GF(2m)), unde p=2m

Exemplu: algoritm de criptare asimetrică bazat pe curbe eliptice ECES (Elliptic Curve Encryption Scheme)

Algoritmul ElGamal.

Sistemul ElGamal este un criptosistem cu cheie publică bazat pe problema logaritmului. Acest algoritm este utilizat atât pentru criptare, cât și pentru semnătura digitală.

Setul de parametri de sistem include un număr prim p și un întreg g, ale căror puteri modulo p generează un număr mare de elemente Z p

Metode de înlocuire.

Un cifr de substituție înlocuiește unele caractere cu altele, dar păstrează ordinea acestora în mesaj.

4 tipuri de înlocuire (înlocuire):

Mono-alfabetic. Formula = Y i =k 1 X i +k 2 (modN), unde Y i este caracterul i al alfabetului, k 1, k 2 sunt constante, X i este caracterul i al textului simplu, N este lungimea alfabetului folosit.

Exemplu. Înlocuire - text simplu, Cheie - Cheie

Substituție omofonică - înlocuirea unui caracter de text simplu se potrivește cu mai multe caractere de text cifrat. Această metodă este folosită pentru a distorsiona proprietățile statistice ale textului cifrat. Se folosește înlocuirea tabelului. Valorile sunt folosite una câte una din coloană.

Substituția polialfabetică este utilizarea mai multor alfabete. Alfabetul se schimbă la fiecare pas de criptare. Se folosește o înlocuire treptată a literelor conform tabelului.
Înlocuire poligramă - format dintr-un singur alfabet folosind reguli speciale. Cifrul este situat într-o matrice, iar textul simplu este împărțit în perechi de simboluri XiXi+1

Cifre de permutare.

Diferența dintre un cifr de permutare este că numai ordinea caracterelor unui text similar este schimbată, dar ele însele nu sunt modificate.

Exemplu. Text „Încărcați portocale în butoaie, frații Karamazov”

Text cifrat „Ptr_aezguionl_byseit_kramchaizryamaak_a__v____oi”

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 o cheie ș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).

Tabelul 2.9. Criptare folosind metoda de permutare a tabelului

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 inițial 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ă biții mesajului original de n biți într-un anumit mod, folosind cablaje electrice adecvate. Deci, dacă luăm dimensiunea blocului ca fiind de opt biți, putem, de exemplu, să folosim un bloc de permutare, cum ar fi

Transpunere criptare este că caracterele de text simplu sunt rearanjate în conformitate cu o anumită regulă într-un 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 o masă

Unde i 1 – numărul locației textului cifrat în care se află prima literă a textului simplu în timpul transformării selectate, i 2 - numărul locului pentru a doua literă etc. În linia de sus a tabelului numerele de la 1 la n, iar în partea de jos sunt aceleași numere, dar în ordine aleatorie. Acest tabel se numește permutare de grade n.

Cunoscând permutarea care specifică 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 un număr tot mai mare n sens n! creste foarte repede. Pentru utilizare în practică, un astfel de cifru nu este convenabil, deoarece pentru valori mari n Trebuie să lucrez cu mese lungi. Prin urmare, cifrurile care folosesc nu tabelul de permutare în sine, ci o anumită regulă care generează acest tabel, au devenit larg răspândite. Să ne uităm la câteva exemple de astfel de cifruri.

Cifrul de permutare a scytala. Se știe că în secolul al V-lea î.Hr. conducătorii Spartei, cel mai războinic dintre statele grecești, aveau un sistem bine dezvoltat de comunicații militare secrete și își criptau mesajele folosind rătăcit 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ă în spirală (turn-to-turn) pe o tijă cilindrică, care se numea skitala, iar pe ea erau scrise mai multe rânduri de text de mesaj de-a lungul tijei (Fig. 1.2). Apoi o fâșie de pergament cu text scris a fost scoasă din tijă. Literele de pe această bandă s-au dovedit a fi localizate haotic.

Orez. 1.2. Codul Scytala

Același rezultat poate fi obținut dacă literele mesajului sunt scrise într-un inel, nu pe rând, ci printr-un anumit număr de poziții până la epuizarea întregului text. Mesaj " AVANS„Când sunt plasate în jurul 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, descifrarea mesajului nu a fost ușoară.

Tabelele de criptare. De la începutul Renașterii (sfârșitul secolului al XIV-lea), criptografia a început să revină. Cifrurile de permutare dezvoltate la acea vreme foloseau tabele de criptare, care, în esență, stabileau regulile pentru permutarea literelor dintr-un mesaj.

Cheile utilizate în tabelele de criptare sunt:

dimensiunea mesei;

cuvânt sau expresie care specifică o permutare;

caracteristicile structurii tabelului.

Unul dintre cele mai primitive cifruri de permutare a tabelului este permutarea simplă, pentru care cheia este dimensiunea tabelului. Această metodă de criptare este similară cu cifrul scytal. De exemplu, mesajul „ TERMINATOR ASOSTE ÎN A ȘAPTEA 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ă completarea tabelului cu textul mesajului, conținutul tabelului este citit rând cu rând pentru a forma textul cifrat. Dacă textul cifrat este scris în grupuri de cinci litere, rezultatul este un mesaj criptat: " TNPVE GLEAR ADONR TIEV OMOBT MPCHIR YSOOO".

Orez. 1.3. Completarea unui tabel de criptare cu 5 rânduri și 7 coloane

Desigur, expeditorul și destinatarul mesajului trebuie să cadă de acord în prealabil asupra unei chei partajate sub forma unei dimensiuni de tabel. Trebuie remarcat faptul că combinarea literelor de text cifrat în grupuri de 5 litere nu este inclusă în cheia de cifrare și se realizează pentru confortul scrierii unui text fără sens. La decriptare, pașii sunt efectuati în ordine inversă.

O metodă de criptare numită o singură permutare prin cheie. Această metodă diferă de cea anterioară prin faptul că coloanele tabelului sunt rearanjate printr-un cuvânt cheie, o expresie sau un set de numere pe lungimea rândului tabelului.

Să folosim, de exemplu, cuvântul „ PELICAN", și să luăm textul mesajului din exemplul anterior. Figura 1.4 prezintă două tabele umplute cu textul mesajului și un cuvânt cheie, cu tabelul din stânga corespunzător umplerii înainte de rearanjare, iar tabelul din dreapta umplerii după rearanjare.

Orez. 1.4. Tabele de criptare pline cu cuvinte cheie și text de mesaj

Rândul de sus al tabelului din stânga conține cheia, iar numerele de sub literele cheie sunt determinate în funcție de ordinea naturală a literelor cheie corespunzătoare din alfabet. Dacă ar exista 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 ordonate ale literelor cheie.

Când citim conținutul tabelului din dreapta rând cu rând și scriem textul cifrat în grupuri de cinci litere, primim mesajul criptat: " GNVEP LTOOA DRNEV TEIO RPOTM BCHMOR SOYYI".

Pentru a oferi confidențialitate 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, permutările tabelelor sunt definite separat pentru coloane și separat pentru rânduri. Mai întâi, textul mesajului este scris în tabel, apoi coloanele și apoi rândurile sunt rearanjate unul câte unul. La decriptare, ordinea permutărilor ar trebui inversată.

Un exemplu de realizare a criptării folosind metoda dublei permutări este prezentat în Fig. 1.5. Dacă citiți textul cifrat din tabelul din dreapta linie cu rând în blocuri de patru litere, veți obține 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 sursă (î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:

pentru o masă 3x3 există 36 de opțiuni;

pentru o masă 4x4 576 opțiuni;

pentru o masă 5x5 există 14400 de opțiuni.

Criptare folosind pătrate magice.În Evul Mediu, pătratele magice erau folosite și pentru criptare prin permutare. . Pătrate magice se numesc 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ă, fiecare rând și fiecare diagonală.

Textul criptat a fost introdus î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, veți obține un text cifrat format prin rearanjarea literelor mesajului original.

Un exemplu de pătrat magic și umplerea acestuia cu mesajul " AJUN PE A OPTA" este prezentat în Fig. 1.6.

Orez. 1.6. Exemplu de pătrat magic 4x4 și umplerea acestuia cu un mesaj

Textul cifrat obținut prin citirea conținutului tabelului din dreapta rând cu rând are un aspect complet misterios: „ OIRM EOSYU VTA LGOP".

Numărul de pătrate magice crește rapid pe măsură ce dimensiunea pătratului crește. Există un singur pătrat magic de dimensiunea 3x3 (dacă nu țineți cont de rotațiile 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 drept bază bună pentru a asigura nevoile de criptare ale acelei vremuri, deoarece este aproape imposibil să căutați manual toate opțiunile pentru un astfel de cifr.

(Vezi si )

Lucrarea matematicianului american Claude Shannon, care a apărut la mijlocul secolului al XX-lea, a avut o mare influență asupra dezvoltării criptografiei. 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 cifre foarte complexe, astfel de cifre simple precum 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 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 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 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. Fie, de exemplu, 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 - 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 este încadrat într-o diagramă a dimensiunilor necesare, apoi este suprapusă o grilă, 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).

Tabelul 6.1. Combinație de litere rusești

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:

Tabelul 6.2. Alternarea vocalelor și a consoanelor

	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 bigrama MP pe ultimul rând și combinația DTY pe 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 î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.