Algoritmul de criptografie DES

Articol postat de:

DES

Standardul de Criptare a Datelor (in engleza Data Encryption StandardDES) este un cifru (o metoda de criptare a informatiei), selectat ca standard federal de procesare a informatiilor in Statele Unite in 1976, si care s-a bucurat ulterior de o larga utilizare pe plan international. Algoritmul a fost controversat initial, avand elemente secrete, lungimea cheii scurta si fiind banuit ca ascunde de fapt o portita pentru NSA. DES a fost analizat intens de catre profesionalisti in domeniu si a motivat intelegerea cifrurilor bloc si criptanaliza lor.

DES este astazi considerat nesigur pentru multe aplicatii. Acest lucru se datoreaza in principiu cheii de 56 de biti, considerata prea scurta; cheile DES au fost sparte in mai putin de 24 de ore. De asemenea, exista unele rezultate analitice care demonstreaza slabiciunile teoretice ale cifrului, desi nu este fezabila aplicarea lor. Se crede ca algoritmul este practic sigur in forma Triplu DES, desi exista atacuri teoretice si asupra acestuia. in ultimii ani, cifrul a fost inlocuit de Advanced Encryption Standard (AES).

In unele documentatii, se face distinctie intre DES ca standard si algoritmul de la baza lui, numit DEA (Algoritmul de Criptare a Datelor- in engleza, Data Encryption Algorithm).

Istorie

Originile DES sunt in anii 1970. in 1972, dupa concluziile unui studiu asupra nevoilor de securitate pentru calculatoare a guvernului Statelor Unite, NBS (National Bureau of Standards) — acum numit NIST (National Institute of Standards and Technology) — a identificat necesitatea unui standard de criptare a datelor importante, nesecrete, care sa fie folosit de toate statele. in consecinta, pe 15 mai 1973, dupa consultarea cu NSA, NBS a solicitat propuneri pentru un cifru care sa fie conform criteriilor de design riguroase. Nici una dintre inregistrari insa nu s-a dovedit a fi corespunzatoare. O a doua cerere a fost emisa pe 27 august 1974. De aceasta data, IBM a inscris un candidat considerat acceptabil, un cifru dezvoltat in perioada 1973–1974, bazat pe un algoritm existent, cifrul Lucifer al lui Horst Feistel. Echipa de la IBM implicata in dezvoltarea si analiza cifrului ii include pe Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, si Bryant Tuckerman.

Algoritmul ca standard

In ciuda criticilor, DES a fost aprobat ca standard federal in noiembrie 1976 si publicat pe 15 ianuarie 1977 ca FIPS PUB 46, utilizarea sa fiind autorizata pentru toate datele care nu sunt secrete de stat. A fost reafirmat ca standard in 1983, 1988 (revizuit ca FIPS-46-1), 1993 (FIPS-46-2) si inca o data in 1998 (FIPS-46-3), ultima varianta recomandand „Triplu DES” (vezi mai jos). Pe 26 mai 2002, DES a fost inlocuit de AES, Advanced Encryption Standard, dupa o competitie publica. Chiar si din 2004, DES inca a ramas folosit pe scara larga. Pe 19 mai 2005, FIPS 46-3 a fost retras oficial, dar NIST a aprobat Triplu DES pana in anul 2030 pentru informatii guvernamentale.

Un alt atac teoretic, criptanaliza liniara, a fost publicat in 1994, dar un atac prin forta bruta a demonstrat in 1998 ca DES poate fi spart practic, si a evidentiat nevoia unui algoritm de inlocuire. Acestea si alte metode de criptanaliza sunt discutate mai jos.

Algoritmi de inlocuire

Grijile despre securitatea si operarea relativ inceata a lui DES in software au motivat cercetatorii sa propuna o varietate de alternative de cifruri bloc, care au inceput sa apara la sfarsitul anilor 1980 si la inceputul anilor 1990; de exemplu, RC5, Blowfish, IDEA, NewDES, SAFER, CAST5 si FEAL. Cei mai multi dintre acesti algoritmi au pastrat blocul de 64 de biti al lui DES si puteau actiona ca inlocuitori, desi foloseau de obicei chei de 64 sau 128 de biti. in URSS, algoritmul GOST 28147-89 a fost introdus, cu marimea blocului de 64 de biti si cheia de 256 de biti, iar acesta a fost folosit in Rusia mai tarziu.

DES poate fi adaptat si reutilizat intr-o schema mai complexa. Multi fosti utilizatori ai DES folosesc acum Triplu DES (TDES, 3DES) care a fost descris si analizat de una dintre persoanele care a patentat DES; a implicat aplicarea lui DES de trei ori cu doua (2TDES) sau trei (3TDES) chei diferite. 3DES este privit ca adecvat de sigur, desi este incet. O alternativa computational mai ieftina este DES-X, care incrementeaza marimea cheii prin aplicarea operatiei XOR pe material extra inainte si dupa DES. GDES a fost o varianta a DES propusa drept metoda de a mari viteza de criptare, dar a fost prea susceptibila criptanalizei diferentiale.

In 2001, dupa o competitie internationala, NIST a selectat un cifru nou: Advanced Encryption Standard (AES), ca inlocuitor. Algoritmul care a fost selectat ca AES a fost inscris de catre designerii sai sub numele de Rijndael. Alti finalisti in competitia NIST pentru AES sunt RC6, Serpent, MARS si Twofish.

Descriere

DES este cifrul bloc arhetip — un algoritm care ia un sir de lungime fixa de biti de text normal si il transforma print-o serie de operatii complexe intr-un sir de biti criptati de aceeasi lungime. in cazul DES, marimea blocului este de 64 biti. DES foloseste de asemenea si o cheie pentru particularizarea transformarii, astfel incat numai cei care cunosc cheia folosita sa poata efectua decriptarea. Cheia este formata din 64 de biti; totusi, numai 56 dintre ei sunt folositi propriu-zis de algoritm. Opti biti sunt utilizati ca biti de paritate si nu sunt necesari dupa acest test. Deci cheia efectiva are doar 56 de biti, si asa este citata de obicei.

Ca si alte cifruri bloc, DES nu este o cale sigura de criptare folosit de sine-statator. El trebuie folosit intr-un mod de operare. FIPS-81 specifica cateva feluri pentru utilizarea cu DES. Alte comentarii despre acest lucru apar in FIPS-74

Structura generala

Structura generala a algoritmului apare in Figura de mai jos: sunt 16 pasi identici de procesare, numiti runde. Exista si cate o permutare initiala si finala, numite PI and PF, care sunt functii inverse (PI „anuleaza” actiunea lui PF si vice versa). PI si PF nu au aproape nici o importanta criptografica, dar au fost incluse pentru a facilita incarcarea si descarcarea blocurilor folosind hardware-ul din anii 1970.

Inaintea rundelor principale, blocul este impartit in doua jumatati, de cate 32 de biti, si procesate alternativ; aceasta alternare este cunoscuta drept Schema Feistel. Structura Feistel asigura ca criptarea si decriptarea sunt procese foarte asemanatoare — singura dieferenta este ordinea aplicarii subcheilor – invers la decriptare. Restul algoritmului este identic. Acest lucru simplifica implementarea, in special cea hardware, deoarece nu e nevoie de algoritmi separati.
Simbolul ⊕ cu rosu denota operatia OR exclusiv (XOR). Functia Famesteca jumatate din bloc cu o subcheie.
Rezultatului functiei F este combinat cu cealalta jumatate de bloc, iar jumatatile sunt interschimbate inaintea urmatoarei runde. Dupa ultima runda, jumatatile nu sunt schimbate; aceasta este o trasatura a structurii Feistel care face din criptare si decriptare procese similare.

Functia Feistel (F)

DES

Functia F, care apare in figura, opereaza pe o jumatate de bloc (32 biti) la un moment dat si este formata din patru pasi:

  1. Expansiune — jumatatea de bloc de 32 de biti este extinsa la 48 de biti folosind functia de expansiune, notata E in diagrama, prin duplicarea unor biti.
  2. Amestecare — rezultatul este combinat cu o subcheie folosind operatia XOR. saisprezece subchei de 48 de biti — una pentru fiecare runda — sunt derivate din cheia principala folosinddiversificarea cheilor (descrisa mai jos).
  3. Substitutie — dupa amestecarea cu subcheia, blocul este divizat in opt bucati de 6 biti fiecare inainte de procesarea folosind cutiilor S, sau cutii de substitutie. Fiecare din cele opt cutii S inlocuieste cei sase biti de intrare cu patru biti conform unei transformari neliniare, oferita sub forma unui tabel de cautare. Cutiile S reprezinta securitatea lui DES — fara ele, cifrul ar fi liniar si usor de spart.
  4. Permutare — in final, cele 32 de iesiri din matricile S sunt rearanjate conform permutarii fixe P.

Alternarea substitutiilor din matricile S si permutarea bitilor folosind matricea P si expansiunea E ofera ceea ce se numeste „confuzie si difuzie”, un concept identificat de catre Claude Shannon in anii 1940 ca fiind necesar unui cifru sigur si practic in acelasi timp.

Diversificarea cheilor

DES

Figura ilustreaza diversificarea cheilor pentru criptare — algoritmul care genereaza subcheile. Initial, 56 de biti din cheia principala sunt selectati din cei 64 prin permutarea PC-1 — ceilalti 8 biti sunt ignorati sau folositi ca biti de paritate. Cei 56 de biti sunt apoi impartiti in doua blocuri de 28 de biti; fiecare jumatate este tratata ulterior separat. in runde succesive, ambele jumatati sunt rotate la stanga cu unul sau doi biti (specificati pentru fiecare runda), si apoi sunt selectati cei 48 de biti ai subcheii prin permutarea PC-2 — 24 de biti din jumatatea stanga, si 24 din cea dreapta. Rotatiile (notate cu „<<<” in diagrama) inseamna ca un set de biti diferit este folosit in fiecare subcheie; fiecare bit este folosit in circa 14 din cele 16 chei.

Diversificarea cheilor pentru decriptare este similara — trebuie sa se genereze subcheile in ordine inversa. Asadar, rotatiile sunt la dreapta, si nu la stanga.

Securitate si criptanaliza

Desi despre criptanaliza lui DES s-a publicat mai multa informatie decat despre cea a oricarui alt cifru bloc, atacul cel mai practic ramane cel prin forta bruta. Diferite proprietati criptanalitice minore sunt cunoscute, iar trei atacuri teoretice sunt posibile. Acestea au complexitatea mai mica decat cea a atacului prin forta bruta, dar numarul de texte necesare este nerealist si de aceea nu sunt fezabile.

In ciuda tuturor criticilor si slabiciunilor lui DES, nu exista exemple de persoane care sa fi suferit pierderi banesti din cauza limitarilor de securitate ale lui DES.

Proprietati criptanalitice minore

DES detine proprietatea complementaritatii, adica

EK(P) = C ⇔ EK(P) = C

unde x este complementul pe biti al lui x. EK denota criptarea cu cheia K, P si C sunt textul normal si, respectiv, textul criptat. Proprietatea complementaritatii inseamna ca munca unui atac prin formta bruta se injumatateste (un bit) sub prezumptia unui text ales.

DES are, de asemenea, patru chei slabe. Criptarea (E) si decriptarea (D) cu o cheie slaba au acelasi efect (vezi involutie):

EK(EK(P)) = P sau echivalent, EK = D K

Exista si sase perechi de chei semi-slabe. Criptarea cu o pereche de chei semi-slabe, K1, opereaza identic cu decriptarea cu o alta, K2:

EK1(EK2(P)) = P sau echivalent, EK2 = DK1

Este usor de evitat cheile slabe si semi-slabe intr-o implementare, fie prin testare explicita, fie prina alegerea aleatorie a cheilor; sansele de alegere a unei chei slabe sau semi-slabe sunt neglijabile. Aceste chei nu sunt in realitate mai slabe decat alte chei in nici un fel, pentru ca nu avantajeaza nici un atac.

S-a dovedit ca DES nu este un grup, sau mai precis, multimea {EK} (a tuturor cheilor posibile K) fata de compunerea functiilor nu este grup, si nici macar „aproape” de a fi grup (Campbell si Wiener, 1992). Aceasta a fost o intrebare pentru un timp, si daca asa era cazul, ar fi fost posibil sa se sparga DES, iar modalitatile de criptare multiple, precum Triplu DES nu ar fi marit securitatea.

Este cunoscut faptul ca securitatea criptografica maxima a lui DES este limitata la 64 de biti, chiar si cand se aleg independent subcheile in locul derivarii lor din cheia principala, care ar permite altfel o securitate de 768 de biti.

Sursa: Wikipedia


Add Comment Register



Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile necesare sunt marcate *


*

Poți folosi aceste etichete HTML și atribute: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>