O introducere în elementele de bază ale cifrurilor moderne cu cheie simetrică. Surse suplimentare de informații. Cifrul Gronsfeld sau substituție polialfabetică

După cum vă amintiți, cifrurile de schimbare, înlocuire, permutare și Vernam aplică o operație fiecărui caracter specific al textului. Trebuie să schimbăm - schimbăm caracterul, aplicăm cheia - o aplicăm caracterului, apoi caracterului următor și așa mai departe, până când criptăm toate caracterele text simplu. Această metodă de criptare se numește criptare flux - criptăm fiecare caracter individual. O altă abordare este împărțirea textului simplu original în grupuri de mai multe caractere (blocuri) și efectuarea operațiunilor de criptare pe fiecare bloc. Aceasta este o metodă de criptare bloc.

Pentru a face diferența dintre cifrurile bloc și fluxul mai clară, să dăm un exemplu: cifru simpluînlocuitori.

Criptare în flux

Să criptăm cuvântul CIPHER cu un cifr de flux de înlocuire:

Am criptat fiecare caracter și am obținut un text cifrat. La fel de ușor ca o plăcintă.

CRIPTARE BLOC

Să criptăm cuvântul AVADAKEDAVRA. Deoarece cifrul este unul bloc, vom împărți textul simplu în blocuri de patru caractere: AVAD | AKED | AVRA (în practică, blocurile de text constau din 64-256 de biți). Pentru fiecare bloc vom veni cu propriul nostru tabel de înlocuire:

Acum criptăm fiecare dintre blocuri cu alfabetul corespunzător:
A ieșit puțin mai bine decât cu abordarea în linie, dacă vorbim despre durabilitate. La urma urmei, am învățat să descifrăm cifrul de substituție obișnuit cu o mână stângă. Și cu o astfel de abordare prin blocare, atacatorul va trebui să-și dezvolte creierul înainte de a putea selecta lungimea blocului și apoi să aplice criptoanaliza pentru cifrurile de înlocuire pentru fiecare bloc.

REŢEA FEISTEL

Acum suntem gata să trecem la un subiect foarte important care deschide ușa către o lume vastă sisteme moderne criptare. Rețeaua Feistel este o metodă de criptare în bloc dezvoltată de Horst Feistel la laboratorul IBM în 1971. Astăzi stă la baza rețelei Feistel cantitate mare protocoale criptografice. Să încercăm să ne dăm seama „pe degete” ce este.

Rețeaua Feistel funcționează pe blocuri de text simplu, așa că ne vom uita la mecanismul de funcționare a acesteia pe unul dintre blocuri. Acțiunile pentru blocurile rămase vor fi similare.

• Blocul este împărțit în două părți egale - stânga (L) și dreapta (R).
• După partiţionare, subblocul din stânga este modificat printr-o funcţie f folosind tasta K: x = f(L, K). Ca funcție, vă puteți imagina orice transformare - de exemplu, vechiul cifr de schimbare cu cheia K.
• Subblocul rezultat este adăugat modulo 2 cu subblocul drept R, care nu a fost folosit înainte: x=x+R
• Apoi, piesele rezultate sunt schimbate și lipite împreună.

După cum puteți vedea, totul este destul de simplu. Pentru a înțelege cum funcționează, priviți diagrama:

Acest circuit se numește o celulă Feistel. Rețeaua Feistel în sine este formată din mai multe celule. Subblocurile obținute la ieșirea primei celule merg la intrarea celei de-a doua celule, subblocurile rezultate din a doua celulă merg la intrarea celei de-a treia celule și așa mai departe, în funcție de numărul de runde ale rețelei Feistel. În fiecare astfel de rundă, este utilizată o cheie rotundă predeterminată. Cel mai adesea, cheile rotunde sunt derivate din cheia principală cheie secreta K. Când toate rundele sunt finalizate, subblocurile de text sunt lipite împreună și se obține un text cifrat normal.

Acum să ne uităm la funcționarea rețelei Feistel folosind un exemplu. Să luăm cuvântul AVADAKEDAVRA și să-l împărțim în două blocuri de șase caractere - AVADAK | EDAVRA. Pentru funcție luăm cifra de schimbare după numărul de poziții determinat de cheia rotundă. Fie cheia secretă K = . Ca taste rotunde, luăm K = 1, K = 2. Pentru adăugarea modulo 2, convertim textul în cod binar conform alfabetului telegrafic, pe care aproape nimeni altcineva îl folosește deloc.

Iată ce s-a întâmplat:

Acum să rulăm primul bloc prin rețeaua Feistel în două runde:

Încercați să criptați singur al doilea bloc, am primit MOSSTR.

Decriptarea se realizează exact în același mod: textul cifrat este împărțit în blocuri și apoi subblocuri, subblocul din stânga trece la funcție, se adaugă modulo 2 cu cel din dreapta și apoi subblocurile sunt schimbate. Diferența este că cheile rotunde sunt furnizate în ordine inversă, adică în cazul nostru, în prima rundă vom folosi cheia K = 2, iar apoi în a doua rundă K = 1.

Cercetările asupra rețelei Feistel au arătat că, cu chei rotunde independente și o funcție pseudo-aleatorie rezistentă la criptografie f, trei runde ale rețelei Feistel vor fi suficiente pentru ca textul cifrat să fie pseudo-aleatoriu. Acest lucru sugerează că cifrurile bazate pe rețeaua Feistel sunt în prezent destul de sigure.

GOST 28147-89 (MAGMA)

Aproape totul este deja în arsenal conceptele necesare, așa că suntem gata să trecem la primul subiect important al criptografiei interne - GOST 28147-89. Merită spus că numai leneșii nu au scris despre acest standard, așa că voi încerca pentru a miliona și prima oară să contur pe scurt și fără un nor de formule esența modurilor de criptare ale marii și teribilei Magme. Dacă decideți să citiți standardul în sine, atunci ar trebui să vă aprovizionați cu timp, energie, răbdare și mâncare, deoarece, după cum știți, scrierea standardelor în limbajul uman este strict interzisă.

Caracteristici principale: cheie 256 biți, bloc 64 biți.

Înainte de a analiza Magma, trebuie să înveți un nou concept - tabele de substituție sau S-boxes. Acesta este același tip de tabel ca și tabelul din cifrul de substituție. Conceput pentru a înlocui simbolurile subblocului cu simbolurile înregistrate în tabel. Nu credeți că S-box sunt numere aleatorii generate de funcția rand(). S-box-urile sunt rezultatul unor secvențe create cu atenție, deoarece puterea criptografică a întregului cifr se bazează pe ele.

GOST 28147 descrie tabelele sale de înlocuire foarte puțin. Spune doar că sunt un element secret suplimentar (împreună cu cheia secretă) și „sunt furnizate în în modul prescris" Nimic altceva. De la adoptarea GOST 28147, incertitudinea științifică și tehnică asociată cu alegerea S-box-urilor a dat naștere la zvonuri și speculații. S-a vorbit despre criterii secrete cunoscute doar de dezvoltatorii GOST. Desigur, această incertitudine a redus încrederea în criptosistem.

Acest neajuns a oferit motive excelente pentru critica standardului. Criptograful francez Nicolas Courtois a publicat mai multe articole care conțin o serie de prevederi controversate cu privire la puterea GOST. Courtois consideră că standardul rus este ușor de atacat și nu poate fi considerat internațional. Cu toate acestea, Courtois își realizează analiza pentru alte S-box-uri decât cele reale, așa că nu ar trebui să vă bazați pe opinia lui.

Acum haideți să vedem ce au venit între zidurile Lubianka mohorâtă.

Mod de înlocuire ușoară

În modul de înlocuire simplă pentru 32 de runde, conform standardului, avem nevoie de 32 de chei rotunde. Pentru a genera chei rotunde, cheia originală de 256 de biți este împărțită în opt blocuri de 32 de biți: K1...K8. Tastele K9...K24 sunt o repetare ciclică a tastelor K1...K8. Cheile K25…K32 sunt cheile K8…K1.

1. Fiecare bloc de 64 de biți este împărțit în două subblocuri - Ai și Bi.
2. Subblocul din stânga Ai este adăugat modulo 232 cu tasta rotundă K1: Ai+1 = Ai + Ki mod 232.
3. Subblocul din stânga trece prin S-box.
4. Biții din subblocul stâng sunt deplasați cu 11 poziții (deplasare ciclică).
5. Subblocul din stânga se adună cu cel din dreapta modulo 2: A = A ⊕ B . iii
6. Subblocul corect acceptă sens original subbloc stânga: Bi+1 = Ai.
7. Subblocurile sunt schimbate.

Doar un exemplu de o rundă. cheie pe 256 de biți:

Apoi cheile rotunde

Cum se utilizează această S-box? Foarte simplu! Dacă intrarea S-box-ului este 0, atunci ieșirea va fi 1 (luați al 0-lea simbol al S-box-ului), dacă 4, atunci ieșirea va fi 5 (luați al 4-lea simbol), dacă intrarea este 7 , atunci rezultatul va fi 4 și așa mai departe.

Text simplu:

Împărțit în două blocuri de 32 de biți de biți înalți și de jos:

Exemplul, desigur, s-a dovedit a fi sălbatic, deoarece GOST nu este încă un standard încât toată lumea să poată trece prin el cu propriile mâini.

Modul de înlocuire simplă este prea simplu și are dezavantaje semnificative:

• o eroare dintr-un bloc criptat corupe toți biții acelui bloc;
• atunci când criptați blocuri identice de text simplu, se obține blocuri identice text cifrat, care poate furniza anumite informații unui criptoanalist.

Astfel, este recomandabil să utilizați GOST 28147-89 în modul de înlocuire simplă numai pentru criptarea datelor cheie.

MODUL DE JOC

Acest mod nu are dezavantajele modului simplu de înlocuire. Modul gamma este numit așa deoarece folosește gamma, o secvență pseudo-aleatorie care este adăugată modulo 2 textului simplu în fiecare rundă. Gamma se formează din mesajul de sincronizare S - o secvență pseudo-aleatorie care se modifică cu fiecare iterație și este criptată în modul de înlocuire simplă, după care se transformă în gamma și se suprapune textului simplu.

Și acum totul este în ordine.

Pașii 3-5 se repetă pentru fiecare bloc. Toate aceste manipulări pot fi văzute în diagramă.

Decriptarea este efectuată în același mod în loc de un bloc de text simplu, este furnizat un bloc de text cifrat.

Modul Gamma cu feedback

Să fim mai complicati. Algoritmul este similar cu modul gamma, dar gama se formează pe baza blocului anterior de date criptate, astfel încât rezultatul criptării blocului curent depinde și de blocurile anterioare. 1. Mesaj de sincronizare S - secvență pseudo-aleatorie pe 64 de biți.

2. S este criptat în modul de înlocuire simplă.
3. Textul simplu este adăugat modulo 2 la gama rezultată.
4. Textul cifrat rezultat este trimis ca mesaj de sincronizare pentru următorul bloc și este, de asemenea, trimis la ieșire. Puteți vedea cum arată în diagramă.

Mod de inserare simulat

În acest mod, este generată o inserție simulată - un bloc suplimentar de lungime fixă, în funcție de textul și tastele sursă. Un astfel de bloc mic este necesar pentru a confirma că nicio distorsiune nu a fost introdusă accidental sau intenționat în textul cifrat - adică pentru a verifica integritatea. Acest mod funcționează astfel:

1. Un bloc de text simplu trece prin 16 runde în modul de înlocuire simplă.
2. Un alt bloc de text simplu este adăugat la blocul rezultat modulo 2.
3. Suma trece prin alte 16 runde în modul de înlocuire simplă.
4. Următorul bloc de text simplu este adăugat și din nou inlocuire usoarași așa mai departe până când nu mai există blocuri de text simplu.

Pentru verificare, destinatarul, după decriptarea textului, efectuează o procedură similară celei descrise. Dacă rezultatul nu se potrivește cu inserția imitativă transmisă, toate blocurile M corespunzătoare sunt considerate false.

GOST 34.12-2015 (GRASSHOPPER)

Mulți consideră că GOST 28147-89 este învechit și nu este suficient de robust în comparație cu algoritmii străini. Pentru a-l înlocui, criptografii autohtoni au lansat un nou standard de criptare. Ei spun că acest lucru s-a întâmplat fie din cauza numărului mare de atacuri asupra vechiului GOST, fie pentru că această lungime a blocului este deja depășită și prea mică pentru seturile de date moderne. Motivele reale nimeni nu face publicitate. Desigur, au existat unele modificări ale principalelor caracteristici.

Caracteristici principale: cheie 256 biți, bloc 128 biți.

De asemenea, merită spus că în noul standard, cutiile S sunt fixe și atent, așa că nu este nevoie să vă inventați propriile substituții aleatorii miraculoase. Noul GOST are mult mai multe moduri de criptare:
mod simplu de înlocuire (Electronic Codebook, ECB);
modul gamma (contor, CTR);
modul gamma cu feedback de ieșire (Output Feedback, OFB);
mod simplu de înlocuire cu angajare (Cipher Block Chaining, SBC);
modul gamma cu feedback text cifrat (Cipher Feedback, CFB);
modul de generare a inserției de simulare (algoritmul codului de autentificare a mesajelor).

Să ne uităm la noile moduri.

Mod de înlocuire ușoară cu angajare

După cum s-a văzut în standardul anterior, modul de înlocuire simplă este cel mai slab dintre moduri, așa că în noul standard iese acum cu angajare și nu a devenit deloc atât de simplu.

1. Un vector de inițializare sună înfricoșător, dar în realitate este doar o secvență de biți care intră în intrare.
2. Vectorul este împărțit în două părți - L și R, dintre care una este adăugată modulo 2 cu textul simplu, iar cealaltă devine jumătate din vectorul de inițializare pentru următorul bloc.
3. Suma textului simplu și a unei părți din vectorul de inițializare este trecută printr-un cifr de substituție simplu.
4. Blocurile de text cifrat rezultate sunt lipite împreună.

Odată ce te uiți la diagramă, totul devine imediat clar.

Desigur, vectorul de inițializare nu este atât de simplu: trece printr-o serie de transformări liniare (folosind un registru cu deplasare liniară) înainte de a începe criptarea unui nou bloc. Dar pentru a vă familiariza cu cifrul, este suficient să vă imaginați o astfel de schemă. Decriptarea în acest mod nu este, de asemenea, complet evidentă, așa că este mai bine să priviți diagrama.

Pentru plusuri - Criptări. Printre evoluțiile interne se numără furnizorul de criptografii CryptoPro CSP.

Câteva cuvinte despre puterea modurilor de criptare. Mulți criptografi străini au încercat să ridice mâna împotriva standardului nostru, dar în momentul de față nu se cunoaște niciun atac care să poată fi implementat la nivelul actual de dezvoltare tehnologică. Printre programatori acest standard pentru o lungă perioadă de timp nu a fost foarte popular, deoarece este dificil de înțeles algoritmul de operare din textul său și nu există suficiente descrieri mai clare. Dar acum există deja o mulțime de implementări în multe limbaje de programare. Deci acum utilizarea GOST este destul de posibilă și, în multe privințe, depășește standardele străine. Până la urmă, unde este patriotismul?!

Criptarea datelor este extrem de importantă pentru a proteja confidențialitatea. În acest articol voi vorbi despre tipuri variateși metode de criptare care sunt folosite pentru a proteja datele astăzi.

Știați?
În epoca romană, criptarea era folosită de Iulius Caesar pentru a face scrisorile și mesajele să nu fie citite inamicului. A jucat un rol important ca tactică militară, mai ales în timpul războaielor.

Pe măsură ce capacitățile internetului continuă să crească, tot mai multe dintre afacerile noastre se desfășoară online. Dintre acestea, cele mai importante sunt internet banking, plata online, e-mailuri, schimb de privat și mesaje oficiale etc., care presupun schimbul de date și informații confidențiale. Dacă aceste date cad în mâini greșite, ar putea provoca rău nu numai utilizator individual, dar și toate sistem online Afaceri.

Pentru a preveni acest lucru, unii măsuri de rețea securitate pentru a proteja transmiterea datelor cu caracter personal. Principalele dintre acestea sunt procesele de criptare și decriptare a datelor, care este cunoscută sub numele de criptografie. Există trei metode principale de criptare utilizate în majoritatea sistemelor de astăzi: hashing, criptare simetrică și asimetrică. ÎN următoarele rânduri, voi vorbi mai detaliat despre fiecare dintre aceste tipuri de criptare.

Tipuri de criptare

Criptare simetrică

În criptarea simetrică, datele normale care pot fi citite, cunoscute sub numele de text simplu, sunt criptate astfel încât să devină ilizibile. Această amestecare a datelor se face folosind o cheie. Odată ce datele sunt criptate, acestea pot fi trimise în siguranță către destinatar. La destinatar, datele criptate sunt decodificate folosind aceeași cheie care a fost folosită pentru codare.

Deci este clar că cheia este cea mai mare parte importantă criptare simetrică. Trebuie să fie ascuns de străini, deoarece oricine are acces la el va putea decripta datele private. Acesta este motivul pentru care acest tip de criptare este cunoscut și ca „cheie secretă”.

În sistemele moderne, cheia este de obicei un șir de date care provine dintr-o parolă puternică sau dintr-o sursă complet aleatorie. Este alimentat în criptare simetrică software, care îl folosește pentru a cripta datele de intrare. Codificarea datelor se realizează folosind algoritm simetric criptare, cum ar fi Standardul de criptare a datelor (DES), Standardul de criptare avansată (AES) sau algoritmul internațional de criptare a datelor (IDEA).

Restricții

Cea mai slabă verigă în acest tip de criptare este securitatea cheii, atât în ​​ceea ce privește stocarea, cât și transmiterea către utilizatorul autentificat. Dacă un hacker este capabil să obțină această cheie, el poate decripta cu ușurință datele criptate, înfrângând întregul scop al criptării.

Un alt dezavantaj este că software-ul care prelucrează datele nu poate funcționa cu date criptate. Prin urmare, pentru a putea folosi acest software, datele trebuie mai întâi decodificate. Dacă software-ul în sine este compromis, atunci un atacator poate obține cu ușurință datele.

Criptare asimetrică

Criptarea cheii asimetrice funcționează în mod similar cheie simetrică, este că folosește o cheie pentru a codifica mesajele transmise. Cu toate acestea, în loc să folosească aceeași cheie, el folosește una complet diferită pentru a decripta acest mesaj.

Cheia folosită pentru codificare este disponibilă pentru toți utilizatorii rețelei. Ca atare, este cunoscută ca o cheie „publică”. Pe de altă parte, cheia folosită pentru decriptare este păstrată secretă și este destinată utilizării private de către utilizator însuși. Prin urmare, este cunoscută drept cheia „privată”. Criptarea asimetrică este cunoscută și sub numele de criptare cu cheie publică.

Deoarece, prin această metodă, cheia secretă necesară pentru decriptarea mesajului nu trebuie transmisă de fiecare dată și, de obicei, este cunoscută doar de utilizator (destinator), probabilitatea ca un hacker să poată decripta mesajul este mare. inferior.

Diffie-Hellman și RSA sunt exemple de algoritmi care utilizează criptarea cu chei publice.

Restricții

Mulți hackeri folosesc man-in-the-middle ca formă de atac pentru a ocoli acest tip de criptare. În criptarea asimetrică, vi se oferă o cheie publică care este utilizată pentru a face schimb de date în siguranță cu o altă persoană sau serviciu. Cu toate acestea, hackerii folosesc înșelăciunea în rețea pentru a vă păcăli să comunicați cu ei în timp ce sunteți făcut să credeți că vă aflați pe o linie sigură.

Pentru a înțelege mai bine acest tip de hacking, luați în considerare două părți care interacționează, Sasha și Natasha, și un hacker, Serghei, cu intenția de a le intercepta conversația. Mai întâi, Sasha trimite un mesaj prin intermediul rețelei destinat Natasha, cerându-i cheia publică. Serghei interceptează acest mesaj și obține cheia publică asociată cu ea și o folosește pentru a cripta și a trimite un mesaj fals către Natasha, care conține cheia lui publică în loc de a lui Sasha.

Natasha, crezând că acest mesaj a venit de la Sasha, acum îl criptează cu cheia publică a lui Serghei și îl trimite înapoi. Acest mesaj a fost din nou interceptat de Serghei, decriptat, modificat (dacă se dorește), criptat din nou folosind cheia publică pe care Sasha a trimis-o inițial și trimis înapoi lui Sasha.

Astfel, atunci când Sasha primește acest mesaj, el a fost făcut să creadă că a venit de la Natasha și rămâne inconștient de joc greșit.

Hashing

Tehnica hashing folosește un algoritm cunoscut sub numele de funcție hash pentru a genera un șir special din datele date, cunoscut sub numele de hash. Acest hash are următoarele proprietăți:

• aceleași date produc întotdeauna același hash.
• Nu este posibil să generați date brute numai dintr-un hash.
• Nu merită încercat diferite combinații date de intrare pentru a încerca să genereze același hash.

Astfel, principala diferență dintre hashing și celelalte două forme de criptare a datelor este că, odată ce datele sunt criptate (hashing), nu pot fi recuperate înapoi în forma sa originală (decriptate). Acest fapt asigură că, chiar dacă un hacker pune mâna pe hash, acesta nu îi va fi de nici un folos, deoarece nu va putea decripta conținutul mesajului.

Message Digest 5 (MD5) și Secure Hashing Algorithm (SHA) sunt doi algoritmi de hashing utilizați pe scară largă.

Restricții

După cum am menționat mai devreme, este aproape imposibil să decriptați datele dintr-un anumit hash. Cu toate acestea, acest lucru este adevărat numai dacă este implementat hashing puternic. În cazul unei implementări slabe a tehnicii de hashing, folosind suficiente resurse și atacuri forta bruta, un hacker persistent poate fi capabil să găsească date care se potrivesc cu hash-ul.

Combinație de metode de criptare

După cum sa discutat mai sus, fiecare dintre aceste trei metode de criptare suferă de unele dezavantaje. Cu toate acestea, atunci când o combinație a acestor metode este utilizată, ele formează o fiabilă și extrem de sistem eficient criptare.

Cel mai adesea, tehnicile cu chei private și publice sunt combinate și utilizate împreună. Metoda cheii private permite o decriptare mai rapidă, în timp ce metoda cheii publice oferă o decriptare mai sigură și mai mult mod convenabil pentru a transfera cheia secretă. Această combinație de metode este cunoscută sub denumirea de „plic digital”. Program de criptare E-mail PGP se bazează pe tehnica „plicului digital”.

Hashingul este folosit ca mijloc de verificare a puterii unei parole. Dacă sistemul stochează un hash al parolei în loc de parola în sine, va fi mai sigur, deoarece chiar dacă un hacker pune mâna pe acest hash, el nu îl va putea înțelege (citi). În timpul verificării, sistemul va verifica hash-ul parolei de intrare și va vedea dacă rezultatul se potrivește cu ceea ce este stocat. În acest fel, parola reală va fi vizibilă doar în momentele scurte când trebuie schimbată sau verificată, reducând foarte mult probabilitatea ca aceasta să cadă în mâini greșite.

Hashingul este, de asemenea, folosit pentru a autentificarea datelor folosind o cheie secretă. Un hash este generat folosind datele și această cheie. Prin urmare, doar datele și hash-ul sunt vizibile, iar cheia în sine nu este transmisă. În acest fel, dacă se fac modificări fie la date, fie la hash, acestea vor fi detectate cu ușurință.

În concluzie, aceste tehnici pot fi folosite pentru a codifica eficient datele într-un format care nu poate fi citit, care poate asigura că acestea rămân în siguranță. Cele mai multe sisteme moderne folosesc de obicei o combinație a acestor metode de criptare împreună cu implementare puternică algoritmi pentru a îmbunătăți securitatea. Pe lângă securitate, aceste sisteme oferă și multe beneficii aditionale, cum ar fi verificarea identității utilizatorului și asigurarea faptului că datele primite nu pot fi modificate.

Serghei Panasenko,
Șef al departamentului de dezvoltare software la Ankad,
[email protected]

Noțiuni de bază

Procesul de conversie a datelor deschise în date criptate și invers se numește de obicei criptare, iar cele două componente ale acestui proces sunt numite criptare și, respectiv, decriptare. Matematic, această transformare este reprezentată de următoarele dependențe care descriu acțiuni cu informațiile originale:

C = Ek1(M)

M" = Dk2(C),

unde M (mesaj) - informații deschise(în literatura despre securitatea informațiilor este adesea numită „ text original");
C (text cifrat) - textul cifrat (sau criptograma) obținut ca urmare a criptării;
E (criptare) - o funcție de criptare care efectuează transformări criptografice asupra textului sursă;
k1 (cheie) - parametrul funcției E, numită cheie de criptare;
M" - informații obținute ca urmare a decriptării;
D (decriptare) - funcție de decriptare care realizează transformări criptografice inverse asupra textului cifrat;
k2 este cheia folosită pentru decriptarea informațiilor.

Conceptul de „cheie” din standardul GOST 28147-89 (algoritm de criptare simetrică) este definit după cum urmează: „o stare secretă specifică a unor parametri ai algoritmului de transformare criptografică, asigurând selecția unei transformări dintr-un set de posibili pentru a acestui algoritm transformări". Cu alte cuvinte, cheia este un element unic cu care puteți modifica rezultatele algoritmului de criptare: același text sursă atunci când este utilizat chei diferite va fi criptat diferit.

Pentru ca rezultatul decriptării să coincidă cu mesaj original(adică, pentru M" = M), două condiții trebuie să fie îndeplinite simultan. În primul rând, funcția de decriptare D trebuie să corespundă funcției de criptare E. În al doilea rând, cheia de decriptare k2 trebuie să corespundă cheii de criptare k1.

Dacă pentru criptare a fost folosit un algoritm de criptare puternic din punct de vedere criptografic, atunci în absența cheii corecte k2 este imposibil să se obțină M" = M. Puterea criptografică este principala caracteristică a algoritmilor de criptare și indică în primul rând gradul de complexitate al obținerii originalei. text dintr-un text criptat fără cheie k2.

Algoritmii de criptare pot fi împărțiți în două categorii: simetrici și criptare asimetrică. Pentru primul, raportul dintre cheile de criptare și de decriptare este definit ca k1 = k2 = k (adică, funcțiile E și D folosesc aceeași cheie de criptare). Cu criptarea asimetrică, cheia de criptare k1 este calculată din cheia k2 în așa fel încât transformarea inversă să fie imposibilă, de exemplu, folosind formula k1 = ak2 mod p (a și p sunt parametrii algoritmului utilizat).

Criptare simetrică

Algoritmii de criptare simetrică datează din cele mai vechi timpuri: această metodă de a ascunde informații a fost folosită de împăratul roman Gaius Julius Caesar în secolul I î.Hr. e., iar algoritmul inventat de el este cunoscut sub numele de „criptosistem Caesar”.

În prezent, cel mai cunoscut algoritm este simetricul Criptare DES(Standard de criptare a datelor), dezvoltat în 1977. Până de curând, a fost un „standard american”, deoarece guvernul acestei țări a recomandat utilizarea lui pentru implementare diverse sisteme criptarea datelor. În ciuda faptului că DES a fost inițial planificat să fie utilizat pentru cel mult 10-15 ani, încercările de a-l înlocui au început abia în 1997.

Nu vom trata DES în detaliu (aproape toate cărțile de pe lista de materiale suplimentare îl au descriere detaliata), și să trecem la algoritmi de criptare mai moderni. Este de remarcat doar faptul că principalul motiv pentru modificarea standardului de criptare este puterea sa criptografică relativ slabă, motivul pentru care lungimea cheii DES este de numai 56 de biți semnificativi. Se știe că orice algoritm de criptare puternic poate fi spart încercând toate cheile de criptare posibile (așa-numita metodă de forță brută - forta bruta atac). Este ușor de calculat că un grup de 1 milion de procesoare, fiecare dintre ele calculează 1 milion de chei pe secundă, va verifica 256 de variante de chei DES în aproape 20 de ore și, după standardele actuale, așa putere de calcul sunt destul de reale, este clar că cheia pe 56 de biți este prea scurtă și algoritmul DES trebuie înlocuit cu unul mai puternic.

Astăzi, doi algoritmi moderni de criptare puternici sunt din ce în ce mai folosiți: standardul intern GOST 28147-89 și noul standard cripto din SUA - AES ( Criptare avansată Standard).

Standard GOST 28147-89

Algoritmul definit de GOST 28147-89 (Fig. 1) are o lungime a cheii de criptare de 256 de biți. Acesta criptează informațiile în blocuri de 64 de biți (astfel de algoritmi se numesc algoritmi bloc), care sunt apoi împărțiți în două subblocuri de 32 de biți (N1 și N2). Subblocul N1 este în curs de procesare într-un anumit fel, după care valoarea sa se adaugă la valoarea subblocului N2 (adăugarea se efectuează modulo 2, adică se aplică operația logică XOR - „exclusiv sau”), iar apoi subblocurile sunt schimbate. Această transformare se efectuează de un anumit număr de ori („runde”): 16 sau 32, în funcție de modul de funcționare al algoritmului. În fiecare rundă se efectuează două operații.

Primul este cheiatul. Conținutul subblocului N1 este adăugat modulo 2 cu partea de 32 de biți a cheii Kx. Cheie completă criptarea este reprezentată ca o concatenare de subchei pe 32 de biți: K0, K1, K2, K3, K4, K5, K6, K7. În timpul procesului de criptare, se utilizează una dintre aceste subchei, în funcție de numărul rotund și de modul de funcționare al algoritmului.

A doua operație este înlocuirea mesei. După introducere, subblocul N1 este împărțit în 8 părți a câte 4 biți, valoarea fiecăruia fiind înlocuită în conformitate cu tabelul de înlocuire pentru această parte a subblocului. Subblocul este apoi rotit cu 11 biți spre stânga.

Inlocuiri de tabel(Cutie de substituție - S-box) sunt adesea folosite în algoritmii moderni de criptare, așa că merită explicat cum este organizată o astfel de operațiune. Valorile de ieșire ale blocurilor sunt înregistrate în tabel. Un bloc de date de o anumită dimensiune (în cazul nostru - 4 biți) are propriul său reprezentare numerică, care specifică numărul valorii de ieșire. De exemplu, dacă S-box arată ca 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 și blocul de 4 biți „0100” a venit la intrare (valoarea 4), apoi, conform tabelului, valoarea de ieșire va fi 15, adică „1111” (0 a 4, 1 a 11, 2 a 2 ...).

Algoritmul, definit de GOST 28147-89, oferă patru moduri de operare: înlocuire simplă, joc, joc cu părereși generarea de prefixe de imitație. Ei folosesc aceeași transformare de criptare descrisă mai sus, dar deoarece scopul modurilor este diferit, această transformare se realizează diferit în fiecare dintre ele.

În modul inlocuire usoara Pentru a cripta fiecare bloc de informații pe 64 de biți, sunt efectuate cele 32 de runde descrise mai sus. În acest caz, subcheile pe 32 de biți sunt utilizate în următoarea secvență:

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 etc. - în rundele 1 până la 24;

K7, K6, K5, K4, K3, K2, K1, K0 - în rundele 25 până la 32.

Decodificare în acest mod se desfășoară exact în același mod, dar cu o secvență ușor diferită de utilizare a subcheilor:

K0, K1, K2, K3, K4, K5, K6, K7 - în rundele 1 până la 8;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 etc. - în rundele 9 până la 32.

Toate blocurile sunt criptate independent unul de celălalt, adică rezultatul criptării fiecărui bloc depinde numai de conținutul acestuia (blocul corespunzător al textului original). Dacă există mai multe blocuri identice de text original (plat), blocurile de text cifrat corespunzătoare vor fi, de asemenea, identice, ceea ce oferă Informatii utile pentru un criptoanalist care încearcă să spargă un cifr. Prin urmare, acest mod este utilizat în principal pentru criptarea cheilor de criptare în sine (se implementează foarte des schemele cu mai multe chei, în care, din mai multe motive, cheile sunt criptate una pe cealaltă). Alte două moduri de operare sunt destinate criptării informațiilor în sine - gamma și gamma cu feedback.

ÎN modul gamma Fiecare bloc de text simplu este adăugat bit cu bit modulo 2 la un bloc gamma de criptare de 64 de biți. Cifrul gamma este o secvență specială care se obține în urma anumitor operații cu registrele N1 și N2 (vezi Fig. 1).

1. Umplerea lor inițială este scrisă în registrele N1 și N2 - o valoare de 64 de biți numită mesaj de sincronizare.

2. Conținutul registrelor N1 și N2 este criptat (în în acest caz,- sincronizare mesaje) în modul de înlocuire simplă.

3. Conținutul registrului N1 se adaugă modulo (232 - 1) cu constanta C1 = 224 + 216 + 28 + 24, iar rezultatul adunării se scrie în registrul N1.

4. Conținutul registrului N2 se adaugă modulo 232 cu constanta C2 = 224 + 216 + 28 + 1, iar rezultatul adunării se scrie în registrul N2.

5. Conținutul registrelor N1 și N2 este scos ca un bloc gamma de 64 de biți al cifrului (în acest caz, N1 și N2 formează primul bloc gamma).

Dacă este necesar următorul bloc gamma (adică, criptarea sau decriptarea trebuie să continue), se revine la pasul 2.

Pentru decriptare, gamma este generată într-o manieră similară, iar apoi textul cifrat și biții gamma sunt din nou XOR. Întrucât această operație este reversibilă, în cazul unei scale corect dezvoltate, se obține textul (tabelul) original.

Criptare și decriptare în modul gamma

Pentru a dezvolta cifrul necesar pentru a decripta gama, utilizatorul care decriptează criptograma trebuie să aibă aceeași cheie și aceeași valoare a mesajului de sincronizare care au fost folosite la criptarea informațiilor. În caz contrar, nu se va putea obține textul original din cel criptat.

În majoritatea implementărilor algoritmului GOST 28147-89, mesajul de sincronizare nu este secret, cu toate acestea, există sisteme în care mesajul de sincronizare este același element secret ca și cheia de criptare. Pentru astfel de sisteme, lungimea efectivă a cheii a algoritmului (256 de biți) este mărită cu alți 64 de biți ai mesajului secret de sincronizare, care poate fi considerat și ca element cheie.

În modul feedback gamma, pentru a umple registrele N1 și N2, începând cu al 2-lea bloc, nu se folosește blocul gamma anterior, ci rezultatul criptării blocului de text simplu anterior (Fig. 2). Primul bloc din acest mod este generat complet similar cu cel anterior.

Orez. 2. Dezvoltarea unui cifr gamma în modul gamma cu feedback.

Având în vedere modul generarea de prefixe de imitaţie, ar trebui definit conceptul de subiect al generației. Prefixul de imitație este un criptografic verifica suma, calculat folosind cheia de criptare și conceput pentru a verifica integritatea mesajelor. La generarea prefixelor de imitație, se execută următoarele: urmatoarele operatii: primul bloc de informații pe 64 de biți pentru care se calculează prefixul de imitație este scris în registrele N1 și N2 și criptat în modul de înlocuire simplă redusă (se efectuează primele 16 runde din 32). Rezultatul rezultat este însumat modulo 2 cu următorul bloc de informații și rezultatul este stocat în N1 și N2.

Ciclul se repetă până când ultimul bloc informație. Conținutul rezultat pe 64 de biți al registrelor N1 și N2 sau o parte a acestora ca urmare a acestor transformări se numește prefix de imitație. Mărimea prefixului de imitație este selectată în funcție de fiabilitatea necesară a mesajelor: cu lungimea prefixului de imitație r biți, probabilitatea ca o schimbare a mesajului să treacă neobservată este de 2-r. Se folosește prefixul de imitație de biți, adică jumătate din conținutul registrelor. Acest lucru este suficient, deoarece, ca orice sumă de control, atașamentul de imitație este destinat în primul rând să protejeze împotriva distorsiunii accidentale a informațiilor. Pentru a proteja împotriva modificării intenționate a datelor, altele metode criptografice- în primul rând o semnătură digitală electronică.

La schimbul de informații, prefixul de imitație servește ca un fel de mijloace suplimentare Control. Este calculat pentru textul simplu atunci când orice informație este criptată și este trimisă împreună cu textul cifrat. După decriptare, o nouă valoare a prefixului de imitație este calculată și comparată cu cea trimisă. Dacă valorile nu se potrivesc, înseamnă că textul cifrat a fost corupt în timpul transmiterii sau au fost folosite chei incorecte în timpul decriptării. Prefixul de imitație este util în special pentru verificarea corectitudinii decriptării informatie cheie atunci când se utilizează scheme cu mai multe chei.

Algoritmul GOST 28147-89 este considerat un algoritm foarte puternic - în prezent nu a mai fost propus pentru dezvăluire metode eficiente decât metoda „forței brute” menționată mai sus. Securitatea sa ridicată este atinsă în primul rând datorită lungimii mari a cheii - 256 de biți. Când utilizați un mesaj de sincronizare secretă, lungimea efectivă a cheii crește la 320 de biți, iar criptarea tabelului de înlocuire adaugă biți suplimentari. În plus, puterea criptografică depinde de numărul de runde de transformare, care conform GOST 28147-89 ar trebui să fie 32 (efectul complet al dispersării datelor de intrare este atins după 8 runde).

Standardul AES

Spre deosebire de algoritmul GOST 28147-89, care a rămas secret mult timp, standard american Criptare AES, destinat să înlocuiască DES, a fost selectat printr-un concurs deschis în care toate organizațiile și persoanele interesate au putut studia și comenta algoritmii candidați.

Un concurs pentru înlocuirea DES a fost anunțat în 1997. Institutul National Standarde și tehnologii din SUA (NIST - Institutul Național de Standarde și Tehnologie). La concurs au fost supuși 15 algoritmi candidați, dezvoltați atât de organizații cunoscute din domeniul criptografiei (RSA Security, Counterpane etc.), cât și de persoane fizice. Rezultatele competiției au fost anunțate în octombrie 2000: câștigătorul a fost algoritmul Rijndael, dezvoltat de doi criptografi din Belgia, Vincent Rijmen și Joan Daemen.

Algoritmul Rijndael nu este similar cu cei mai cunoscuți algoritmi de criptare simetrică, a căror structură se numește „rețea Feistel” și este similară cu GOST rusesc 28147-89. Particularitatea rețelei Feistel este că valoarea de intrare este împărțită în două sau mai multe subblocuri, dintre care o parte în fiecare rundă este procesată conform unei anumite legi, după care este suprapusă subblocurilor neprocesate (vezi Fig. 1).

Spre deosebire de standardul de criptare autohton, algoritmul Rijndael reprezintă un bloc de date sub forma unei matrice bidimensionale de octeți de dimensiunea 4X4, 4X6 sau 4X8 (este permisă utilizarea mai multor dimensiuni fixe ale blocului de informații criptat). Toate operațiunile sunt efectuate pe octeți individuali ai matricei, precum și pe coloane și rânduri independente.

Algoritmul Rijndael efectuează patru transformări: BS (ByteSub) - înlocuirea tabelului a fiecărui octet al matricei (Fig. 3); SR (ShiftRow) - deplasarea rândurilor matricei (Fig. 4). Cu această operație, prima linie rămâne neschimbată, iar restul sunt deplasate ciclic octet cu octet la stânga cu un număr fix de octeți, în funcție de dimensiunea matricei. De exemplu, pentru o matrice 4X4, liniile 2, 3 și 4 sunt deplasate cu 1, 2 și, respectiv, 3 octeți. Urmează MC (MixColumn) - o operație pe coloane matrice independente (Fig. 5), când fiecare coloană este înmulțită cu o matrice fixă ​​c(x) conform unei anumite reguli. Și, în sfârșit, AK (AddRoundKey) - adăugarea unei chei. Fiecare bit al matricei este adăugat modulo 2 cu bitul corespunzător al cheii rotunde, care, la rândul său, este calculat într-un anumit mod din cheia de criptare (Fig. 6).

Orez. 3. Operațiunea BS.

Orez. 4. Operațiunea SR.

Orez. 5. Operațiunea MC.

Numărul de runde de criptare (R) în algoritmul Rijndael este variabil (10, 12 sau 14 runde) și depinde de dimensiunea blocului și de cheia de criptare (există și mai multe dimensiuni fixe pentru cheie).

Decriptarea se realizează utilizând următoarele operații inverse. Tabelul este inversat și tabelul este înlocuit cu un tabel invers (față de cel folosit pentru criptare). Operația inversă față de SR este de a roti rândurile spre dreapta și nu spre stânga. Operația inversă pentru MC este înmulțirea folosind aceleași reguli cu o altă matrice d(x) care îndeplinește condiția: c(x) * d(x) = 1. Adăugarea cheii AK este inversul acesteia, deoarece folosește doar XOR Operațiune. Aceste operații inverse sunt utilizate în timpul decriptării în secvența inversă celei utilizate în timpul criptării.

Rijndael a devenit noul standard pentru criptarea datelor datorită unui număr de avantaje față de alți algoritmi. În primul rând, oferă de mare viteză criptare pe toate platformele: atât în ​​implementare software cât și hardware. Se distinge incomparabil cele mai bune oportunități paralelizarea calculelor în comparație cu alți algoritmi supuși concursului. În plus, cerințele de resurse pentru funcționarea sa sunt minime, ceea ce este important atunci când este utilizat în dispozitive cu capacități de calcul limitate.

Singurul dezavantaj al algoritmului poate fi considerat schema sa neconvențională inerentă. Faptul este că proprietățile algoritmilor bazați pe rețeaua Feistel au fost bine cercetate, iar Rijndael, în schimb, poate conține vulnerabilități ascunse care pot fi descoperite doar după ce a trecut ceva timp de la începutul utilizării sale pe scară largă.

Criptare asimetrică

Algoritmii de criptare asimetrică, după cum sa menționat deja, folosesc două chei: k1 - cheia de criptare sau publică și k2 - cheia de decriptare sau secretă. Cheie publică calculat din secretul: k1 = f(k2).

Algoritmii de criptare asimetrică se bazează pe utilizarea funcțiilor unidirecționale. Prin definiție, o funcție y = f(x) este unidirecțională dacă: este ușor de calculat pentru toate valorile posibile ale lui x și pentru cele mai multe valori posibile ale lui y este destul de dificil să se calculeze o valoare a lui x pentru care y = f(x).

Un exemplu de funcție unidirecțională este înmulțirea a două numere mari: N = P*Q. În sine, o astfel de înmulțire este o operație simplă. Cu toate acestea, funcția inversă (descompunerea lui N în doi factori mari), numită factorizare, conform estimărilor timpului modern, este destul de complexă. problema de matematica. De exemplu, factorizarea N cu o dimensiune de 664 biți la P ? Q va necesita aproximativ 1023 de operații, iar pentru a calcula invers x pentru exponentul modular y = ax mod p cu a, p și y cunoscute (cu aceleași dimensiuni de a și p) trebuie să efectuați aproximativ 1026 de operații. Ultimul exemplu dat se numește Problema logaritmului discret (DLP), iar acest tip de funcție este adesea folosit în algoritmii de criptare asimetrică, precum și în algoritmii utilizați pentru a crea o semnătură digitală electronică.

O altă clasă importantă de funcții utilizate în criptarea asimetrică sunt funcțiile backdoor unidirecționale. Definiția lor afirmă că o funcție este unidirecțională cu o ușă din spate dacă este unidirecțională și poate fi calculată eficient funcție inversă x = f-1(y), adică dacă „pasajul secret” este cunoscut (un anumit număr secret, în aplicarea algoritmilor de criptare asimetrică - valoarea cheii secrete).

Funcțiile backdoor unidirecționale sunt utilizate în algoritmul de criptare asimetric RSA, utilizat pe scară largă.

algoritmul RSA

Dezvoltat în 1978 de trei autori (Rivest, Shamir, Adleman), și-a primit numele de la primele litere ale numelor dezvoltatorilor. Fiabilitatea algoritmului se bazează pe dificultatea factorizării numerelor mari și calculării logaritmilor discreti. Parametrul principal algoritmul RSA- modulul sistemului N, conform căruia se efectuează toate calculele din sistem și N = P*Q (P și Q sunt simple aleatoare secrete numere mari, de obicei de aceeași dimensiune).

Se selectează cheia secretă k2 la întâmplareși trebuie să îndeplinească următoarele condiții:

1

unde GCD este cel mai mare divizor comun, adică k1 trebuie să fie coprime față de valoarea funcției Euler F(N), aceasta din urmă fiind egală cu numărul de numere întregi pozitive din intervalul de la 1 la N coprime la N și se calculează ca F(N) = (P - 1)*(Q - 1).

Cheia publică k1 se calculează din relație (k2*k1) = 1 mod F(N), iar în acest scop se folosește algoritmul euclidian generalizat (algoritmul de calcul al celui mai mare divizor comun). Criptarea blocului de date M folosind algoritmul RSA se realizează după cum urmează: C=M [la puterea k1] mod N. Rețineți că, deoarece într-un criptosistem real care utilizează RSA numărul k1 este foarte mare (în prezent, dimensiunea sa poate ajunge până la 2048 de biți), calculul direct al lui M [la puterea k1] ireal. Pentru a-l obține, se folosește o combinație de pătrat repetat a lui M și înmulțirea rezultatelor.

Inversarea acestei funcții pentru dimensiuni mari nu este fezabilă; cu alte cuvinte, este imposibil să găsim M având în vedere C, N și k1 cunoscute. Cu toate acestea, având o cheie secretă k2, folosind transformări simple se poate calcula M = Ck2 mod N. Evident, pe lângă cheia secretă în sine, este necesar să se asigure secretul parametrilor P și Q. Dacă un atacator obține valorile acestora , el va putea calcula cheia secretă k2.

Care criptare este mai bună?

Principalul dezavantaj al criptării simetrice este necesitatea de a transfera cheile „din mână în mână”. Acest dezavantaj este foarte grav, deoarece face imposibilă utilizarea criptării simetrice în sistemele cu un număr nelimitat de participanți. Cu toate acestea, în caz contrar, criptarea simetrică are unele avantaje care sunt clar vizibile pe fondul dezavantajelor serioase ale criptării asimetrice.

Prima dintre ele este viteza redusă a operațiunilor de criptare și decriptare, din cauza prezenței operațiunilor care consumă intens resurse. Un alt dezavantaj „teoretic” este că puterea criptografică a algoritmilor de criptare asimetrică nu a fost dovedită matematic. Acest lucru se datorează în primul rând problemei logaritmului discret - încă nu s-a dovedit că soluția sa într-un timp acceptabil este imposibilă. Dificultăți inutile sunt create și de necesitatea de a proteja cheile publice împotriva înlocuirii - prin înlocuirea cheii publice a unui utilizator legal, un atacator va putea cripta un mesaj important cu cheia sa publică și, ulterior, îl va decripta cu ușurință cu cheia sa privată.

Cu toate acestea, aceste dezavantaje nu împiedică utilizarea pe scară largă a algoritmilor de criptare asimetrică. Astăzi există criptosisteme care acceptă certificarea cheilor publice, precum și combinarea algoritmilor de criptare simetrici și asimetrici. Dar acesta este un subiect pentru un articol separat.

09.07.2003

Ce este criptarea?

Criptarea a fost folosită de omenire încă din momentul în care au apărut primele informații secrete, adică acele informații la care accesul ar trebui limitat. Aceasta a fost cu mult timp în urmă - de exemplu, una dintre cele mai faimoase metode de criptare poartă numele lui Cezar, care, dacă nu a inventat-o ​​el însuși, a folosit-o în mod activ (vezi bara laterală).

Criptografia asigură că sensul unui mesaj este ascuns și este dezvăluit prin decriptare folosind algoritmi și chei speciali. Înțelegem cheia ca o stare secretă specifică a parametrilor algoritmilor de criptare și decriptare. Cunoașterea cheii face posibilă citirea mesajului secret. Cu toate acestea, după cum veți vedea mai jos, ignorarea cheii nu garantează întotdeauna că mesajul nu poate fi citit de un străin.

Procesul de spargere a unui cifr fără a cunoaște cheia se numește criptoanaliza. Timpul necesar pentru spargerea unui cifr este determinat de puterea sa criptografică. Cu cât este mai mare, cu atât algoritmul de criptare este mai „puternic”. Este chiar mai bine dacă inițial este imposibil să afli dacă rezultatul hack-ului este realizabil.

Metode moderne de criptare de bază

Dintre diferitele metode de criptare, se pot distinge următoarele metode principale:

• Algoritmi de înlocuire sau înlocuire - caracterele textului sursă sunt înlocuite cu caractere ale altui (sau același) alfabet în conformitate cu o schemă predeterminată, care va fi cheia acestui cifr. Separat, această metodă nu este practic utilizată în criptosistemele moderne datorită puterii sale criptografice extrem de scăzute.
• Algoritmi de rearanjare - caracterele textului original sunt schimbate conform unui anumit principiu, care este o cheie secretă. Algoritmul de permutare în sine are o putere criptografică scăzută, dar este inclus ca element în multe criptosisteme moderne.
• Algoritmi Gamma - caracterele textului sursă sunt adăugate la caracterele unei anumite secvențe aleatorii. Cel mai obișnuit exemplu este criptarea fișierelor „username.pwl”, în care sistemul de operare Microsoft Windows 95 stochează parole pentru resursele de rețea ale unui anumit utilizator (parole pentru autentificarea la serverele NT, parolele pentru acces la Internet DialUp etc.) .

Când un utilizator își introduce parola atunci când se conectează la Windows 95, se generează un gamma (întotdeauna același) folosind algoritmul de criptare RC4, care este folosit pentru a cripta parolele de rețea. Simplitatea selectării parolei în acest caz se datorează faptului că Windows preferă întotdeauna aceeași schemă de culori.

• Algoritmi bazați pe transformări matematice complexe ale textului sursă după o anumită formulă. Mulți dintre ei folosesc probleme de matematică nerezolvate. De exemplu, algoritmul de criptare RSA utilizat pe scară largă pe Internet se bazează pe proprietățile numerelor prime.

Criptosisteme simetrice și asimetrice

Înainte de a trece la algoritmi individuali, să luăm în considerare pe scurt conceptul de criptosisteme simetrice și asimetrice. Generarea unei chei secrete și criptarea unui mesaj cu ea este doar jumătate din luptă. Dar cum poate fi trimisă o astfel de cheie cuiva care trebuie să o folosească pentru a decripta mesajul original? Transmiterea cheii de criptare este considerată una dintre principalele probleme ale criptografiei.

Rămânând în cadrul unui sistem simetric (numit așa pentru că aceeași cheie este folosită pentru criptare și decriptare), este necesar să existe un canal de comunicare fiabil pentru transmiterea cheii secrete. Dar un astfel de canal nu este întotdeauna disponibil și, prin urmare, matematicienii americani Diffie, Hellman și Merkle au dezvoltat conceptul de cheie publică și criptare asimetrică în 1976. În astfel de criptosisteme, doar cheia pentru procesul de criptare este disponibilă public, iar procedura de decriptare este cunoscută numai de proprietarul cheii secrete.

De exemplu, când vreau să-mi fie trimis un mesaj, generez chei publice și private. Ți-l trimit, tu criptezi mesajul și mi-l trimiți. Numai eu pot decripta mesajul, deoarece nu am dat cheia secretă nimănui. Desigur, ambele chei sunt legate într-un mod special (în moduri diferite în fiecare criptosistem), iar distribuția cheii publice nu distruge puterea criptografică a sistemului.

În sistemele asimetrice, trebuie îndeplinită următoarea cerință: nu există un algoritm (sau nu este încă cunoscut) care să derive textul original din criptotext și cheia publică. Un exemplu de astfel de sistem este binecunoscutul sistem criptografic RSA.

algoritmul RSA

Algoritmul RSA (după primele litere ale numelor de familie ale creatorilor săi Rivest-Shamir-Adleman) se bazează pe proprietățile numerelor prime (și ale celor foarte mari). Numerele prime sunt acele numere care nu au alți divizori decât ele însele și unul. Și numerele coprime sunt acele numere care nu au divizori comuni alții decât 1.

Mai întâi, să alegem două numere prime foarte mari (sunt necesare numere prime mari pentru a construi chei mari și puternice. De exemplu, programul Unix ssh-keygen generează implicit chei lungi de 1024 de biți).

Să definim parametrul n ca urmare a înmulţirii pȘi q. Să alegem un număr mare aleatoriu și să îl numim d, și trebuie să fie coprim cu rezultatul înmulțirii (p -1)*(q -1).

Să găsim un număr e pentru care relația este adevărată

(e*d) mod ((p -1)*(q -1)) = 1

(mod- restul diviziunii, adică dacă e înmulțit cu d este împărțit cu ((p -1)*(q -1)), atunci restul este 1).

Cheia publică este o pereche de numere e și n, și închis - d și n.

La criptare, textul sursă este tratat ca o serie de numere și efectuăm o operație pe fiecare număr

C(i)= (M(i) e) mod n.

Rezultatul este succesiunea C(i), care va alcătui criptotextul. Decodificarea informațiilor are loc conform formulei

M(i) = (C(i) d) mod n.

După cum puteți vedea, decriptarea necesită cunoașterea cheii secrete.

Să încercăm pe numere mici.

Hai să instalăm p=3, q=7. Apoi n=p*q=21. Alege d ca 5. Din formula (e*5) mod 12=1 calculati e=17. Cheie publică 17, 21 , secret - 5, 21 .

Să criptăm secvența „12345”:

C(1)= 1 17 mod 21= 1

C(2)= 2 17 mod 21 =11

C(3)= 3 17 mod 21= 12

C(4)= 4 17 mod 21= 16

C(5)= 5 17 mod 21= 17

Criptotext - 1 11 12 16 17.

Să verificăm decriptarea:

M(1)= 1 5 mod 21= 1

M(2)= 11 5 mod 21= 2

M(3)= 12 5 mod 21= 3

M(4)= 16 5 mod 21= 4

M(5)= 17 5 mod 21= 5

După cum puteți vedea, rezultatul a coincis.

Criptosistemul RSA este utilizat pe scară largă pe Internet. Când vă conectați la un server securizat prin SSL, instalați un certificat WebMoney pe computer sau vă conectați la un server la distanță folosind Open SSH sau SecureShell, toate aceste programe folosesc criptarea cu chei publice folosind idei din algoritmul RSA. Este acest sistem cu adevărat atât de fiabil?

Competiții de hacking RSA

De la crearea sa, RSA a fost supus constant atacurilor cu forță brută. În 1978, autorii algoritmului au publicat un articol în care prezentau un șir criptat folosind metoda pe care tocmai o inventaseră. Prima persoană care a descifrat mesajul a primit o recompensă de 100 USD, dar aceasta a necesitat împărțirea unui număr de 129 de cifre în doi factori. Aceasta a fost prima competiție care a spart RSA. Problema a fost rezolvată la numai 17 ani de la publicarea articolului.

Puterea criptografică a RSA se bazează pe presupunerea că este extrem de dificil, dacă nu imposibil, să se determine cheia privată din cheia publică. Pentru a face acest lucru, a fost necesar să se rezolve problema existenței divizorilor unui întreg imens. Până acum, nimeni nu a rezolvat-o folosind metode analitice, iar algoritmul RSA poate fi spart doar prin forță brută. Strict vorbind, afirmația că problema factorizării este dificilă și că ruperea sistemului RSA este dificilă, de asemenea, nu este dovedită.

Numărul obținut ca urmare a procesării textului mesajului de către funcția hash este criptat folosind algoritmul RSA pe cheia privată a utilizatorului și trimis destinatarului împreună cu scrisoarea și o copie a cheii publice. Destinatarul, folosind cheia publică a expeditorului, îndeplinește aceeași funcție hash pe mesajul primit. Dacă ambele numere sunt egale, înseamnă că mesajul este autentic, dar dacă cel puțin un caracter a fost modificat, atunci numerele nu se vor potrivi.

Unul dintre cei mai obișnuiți clienți de e-mail din Rusia, programul The Bat, are capabilități încorporate de a adăuga semnături digitale la scrisori (atenție la elementul din meniul Confidențialitate când editați o scrisoare). Citiți mai multe despre această tehnică în articol (vezi „PC World”, Nr. 3/02).

Orez. 3

Criptografie

Criptografia este știința principiilor, mijloacelor și metodelor de transformare a informațiilor pentru a le proteja de accesul neautorizat și denaturare. În ultimul timp s-a dezvoltat foarte, foarte rapid. Este o cursă nesfârșită, captivantă, care necesită mult timp și efort: criptoanalistii sparg algoritmi care până de curând erau standarde și folosiți pe scară largă. Apropo, recent matematicienii Dan Goldston (SUA) și Kem Ildirim (Turcia) au dovedit prima regularitate în distribuția numerelor prime (asemenea regularități nu fuseseră observate până acum). Numerele prime sunt situate pe axa numerelor în anumite grupuri, ceea ce le face oarecum mai ușor de găsit.

Cercetările matematice efectuate în întreaga lume conduc în mod constant la noi descoperiri. Cine știe, poate că suntem pe punctul de a sparge algoritmul RSA sau alte criptosisteme bazate pe probleme matematice nerezolvate.

Oleg Bunin- specialist in dezvoltare software pentru proiecte mari de internet, angajat al companiei Rambler, http://www..htm).

Sistemul de cifrare Caesar

Un exemplu de algoritm de înlocuire este sistemul de criptare Caesar. Această metodă se bazează pe înlocuirea fiecărei litere a mesajului cu alta prin trecerea de la original cu un număr fix de caractere. Încercați să descifrați catrenul lui Omar Khayyam (timp de finalizare - 10 minute).

RLZ YOMEYZ AVBZHU IYZAVLU, BZHSCHLU ZHSCHEZZHZ ZHUOSCHZ, EYSH YSHCHAZhFO IYSHCHYVESH BSHCHIZHV EESH ZHSCHRSCHG: LF EMRSYU ЪZEZESCHG, RYU RLZ IZISHCHEZ ZEVSYUKOY , ZISHCHEZ.

Ai reușit? Iată răspunsul:

Pentru a-ți trăi viața cu înțelepciune, trebuie să știi multe,

Amintiți-vă două reguli importante pentru a începe:

Prefer să mori de foame decât să mănânci orice,

Și este mai bine să fii singur decât cu oricine.

Cheie de decriptare: deplasați cu șapte caractere (luați al șaptelea) la stânga în ordine alfabetică. Alfabetul este în buclă. Caracterele nu sunt sensibile.

Windows și parole

Cum criptează Windows parolele?

Sistemul preia parola, o convertește în majuscule, o decupează la 14 caractere, apoi le împarte în două jumătăți de câte 7, criptează fiecare separat și o salvează astfel, ceea ce ușurează puțin hacking-ul. Apropo, atunci când vii cu o parolă, ține cont de faptul că o combinație mai lungă de 14 caractere are puțină semnificație.

Concurență AES (Advanced Encryption Standard).

În anii 80 în SUA au adoptat un standard de criptare simetrică pentru uz intern - DES ((Data Encryption Standard, există un standard similar în Rusia). Dar în 1997, când a devenit clar că cheia DES pe 56 de biți nu era suficientă pentru o fiabilă criptosistem, Institutul American de Standarde a anunțat concurs pentru un nou algoritm standard Din 15 opțiuni, a fost aleasă cea mai bună: algoritmul belgian Rijndael (numele său este format din numele autorilor - Rijmen și Daemen, citit ca „Rijndael”. Acest algoritm este deja integrat în diverse instrumente criptografice furnizate pieței de către alți finaliști. Câștigătorii competiției au fost MARS, RC6, Serpent, TwoFish. Toți acești algoritmi s-au dovedit a fi destul de robusti și rezistă cu succes tuturor metodelor de criptoanaliza binecunoscute. .

Funcții hash criptografice

Funcțiile hash criptografice convertesc datele de intrare de orice dimensiune într-un șir de dimensiune fixă. Este extrem de greu de găsit pentru ei:

• două seturi de date diferite cu același rezultat al transformării (rezistența la coliziune); de exemplu, numărul de operații aritmetice necesare pentru a găsi un bloc de date care are și un mesaj scurt pentru funcția hash MD5 este de aproximativ 2 64;
• valoarea de intrare bazată pe un rezultat de hashing cunoscut (ireversibilitate); pentru MD5, numărul estimat de operații necesare pentru a calcula mesajul original este de 2.128.