STUDIUL EXPERIMENTAL AL ALGORITMILOR DE CRIPTARE A DATELOR CU CHEIE SIMETRICA

OBIECTIVELE LUCRARII

Obiectivele lucrarii sunt urmatoarele:

analiza algoritmilor de criptare a datelor cu cheie simetrica de tip cifrul lui Caesar, substitutie monoalfabetica, transpozitie pe coloane, metoda cheilor acoperitoare;

implementarea acestor algoritmi folosind tehnica de calcul.

2. BREVIAR TEORETIC

2.1. Introducere in criptografie

Criptografia descrie un camp larg al comunicatiilor secrete si se identifica prin totalitatea mijloacelor si metodelor utilizate pentru protectia interceptarii pasive (inregistrarea mesajului transmis) sau/si active (modificarea informatiei sau introducerea de mesaje false pe canalul transmisiunii, intre emitatorul si receptorul legali).

Mesajele ce trebuie criptate, cunoscute sub numelele de text clar sunt transformate printr-o functie parametrizata de o cheie (key). Cheia consta dintr-un sir (relativ) scurt care selecteaza una dintre mai multe criptari potentiale.

Iesirea procesului de criptare cunoscuta sub numele de text cifrat sau criptograma este apoi transmisa adeseori prin curier sau radio.

Arta de a sparge cifruri se numeste criptanaliza. Arta de a concepe cifruri (criptografia) si cea de a le sparge (criptanaliza) sunt cunoscute sub numele colectiv de criptologie.

Din punctul de vedere al criptanalistului, problema sa are trei variante principale:

Cand are la dispozitie o cantitate de text cifrat si nici un fel de text clar este confruntat cu problema textului cifrat;

Cand are la dispozitie ceva text clar si textul criptat corespunzator, problema este cunoscuta sub numele de problema textului clar cunoscut;

Cand criptanalistul poate cripta bucati de text clar la propria sa alegere, avem de-a face cu problema textului clar ales

In criptografia traditionala, metodele de criptare au fost impartite in doua categorii:

cifruri cu substitutie;

cifruri cu transpozitie.

In criptografia moderna, clasificarea sistemelor de criptare se realizeaza in functie de cheie. Astfel, acestea se pot clasifica in:

Sisteme criptografice cu chei secrete, cunoscute si sub numele de sisteme criptografice simetrice, care necesita dezvoltarea unor servicii suplimentare de management al cheilor secrete;

Sisteme criptografice cu chei publice, cunoscute si sub numele de sisteme criptografice asimetrice, care furnizeaza servicii specializate de autentificare dar sunt in general ineficiente pentru criptarile de date corespunzatoare unor mesaje scurte.

Sistemul criptografic este sigur daca criptanaliza nu isi atinge obiectivul de determinare a mesajului.

Un sistem secret care rezista la orice atac criptanalitic, indiferent de volumul calculelor care se cer, se numeste sigur neconditionat.

Sistemul este sigur computational cand se recunoaste posibilitatea criptanalistului de a intra in posesia mesajului dupa o cantitate finita de calcule care ocupa un volum de calcul foarte mare, neacoperit din punct de vedere economic.

2.2. Algoritmi de criptare cu cheie simetrica

Cifrul lui Caesar generalizat

Cifrul lui Caesar este un cifru cu substitutie in care fiecare litera din grup este inlocuita pentru deghizare cu o alta litera.

Acest algoritm este unul dintre cele mai vechi cifruri cunoscute si este atribuit lui Julius Caesar. In aceasta metoda, A devine D, B devine E, C devine F, . , X devine A, Y devine B, Z devine C.

De exemplu, mesajul

acesta este un text cODIFICat

devine

dfhvwd hvwh xq whaw fRGLILFDW

O mica generalizare a cifrului lui Caesar permite alfabetului textului cifrat sa fie deplasat cu litere, in loc de a fi deplasat intotdeauna cu 3 . In acest caz, devine o cheie pentru metoda generala a alfabetelor deplasate circular.

Matematic, cifrul lui Caesar generalizat se exprima astfel:

,                                                       

unde:

este mesajul de criptat;

este criptograma rezultata aplicarii lui a functiei ;

, este lungimea mesajului.

Printr-o transformare liniara a functiei de mai sus, se obtine

, pentru (9.2)

unde:

si este lungimea mesajului,

este lungimea alfabetului,

este cheia.

Pentru o cheie , se obtine cifrul lui Caesar

Pentru o cheie , alfabetul de 26 de litere () si criptograma corespunzatoare lui arata astfel:

Daca mesajului

ACESTA ESTE UN TEXT CODIFICAT

i se aplica corespondenta din tabelul de mai sus, rezulta urmatorul mesaj criptat (criptograma):

JLNBCJ NBCN DW CNGC LXMRORLJC

2.2.2.Criptarea prin substitutie monoalfabetica

Principala imbunatatire a acestui tip de criptare o reprezinta stabilirea pentru fiecare simbol din textul clar, sa spunem pentru simplitate cele 26 de litere de mai sus, o corespondenta cu o alta litera.

Matematic, daca exista o singura lege de corespondenta notata cu (intre elementele alfabetului mesajului si elementele alfabetului criptogramei), substitutia este monoalfabetica.

Pentru mesajul , se obtine criptograma :

,     (9.3)

printr-o transformare liniara de forma:

,                          (9.4)

unde:

este mesajul de criptat

este criptograma rezultata aplicarii lui a functiei ,

, este lungimea mesajului,

este lungimea alfabetului,

si sunt doua numere de tip intreg.

cheia este data de ansamblul

Criptarea care foloseste substitutia monoalfabetica este slaba la atacuri criptanalitice (in principal cu text criptat), pentru ca identificarea cheii conduce la obtinerea intregului mesaj.

Ca un caz particular, este prezentat cifrul aleator de substitutie. Cheia este constituita din 26 de perechi de numere echivalente de forma , cu  . Intr-un mod pseudoaleator, fierarei litere a alfabetului primar ii corespunde o litera a alfabetului secundar. Literele alfabetului de substituire sunt static independente dar exista dezavantaje legate de generarea, transmiterea si pastrarea cheii.

De exemplu

Cheia acestui tip de codificare o reprezinta sirul de 26 de litere corespunzand intregului alfabet.

Tinand cont de cheia prezentata in tabelul anterior, mesajul

ACESTA ESTE UN TEXT CODIFICAT

devine:

QETLZQ TLZT XF ZTBZ EGROYOEQZ

2.2.3.Criptarea prin transpozitie pe coloane

Spre deosebire de cifrurile cu substitutie, cifrurile cu transpozitie reordoneaza caracterele, dar nu le deghizeaza.

In exemplul urmator este aratat modul de realizare a criptogramelor folosind un cifru cu transpozitie pe coloane. Cifrul are drept cheie un cuvant sau o expresie ce nu contine caractere repetate. In urmatorul exemplu cheia este universala.

Textul clar (necodificat) este scris orizontal, pe randuri. Scopul cheii este sa stabileasa numarul de coloane si sa ordoneze caracterele, coloana 1 fiind sub litera din cheie cea mai apropiata de inceputul alfabetului.

Text clar (mesaj): Acest algoritm de codificare este foarte bun.

Text criptat (criptograma):

leafntmft eidetg ro.cro r  iebsdc uAoceastise

2.2.4.Metoda cheilor acoperitoare

Construirea unui cifru imposibil de spart este actualmente destul de simpla. Tehnica este cunoscuta de decenii, avand urmatoarele etape:

se alege un sir aleatoriu de biti pe post de cheie;

se converteste textul clar intr-un sir de biti;

pentru a obtine codificarea textului clar, se calculeaza xor intre cheie si textul clar, bit cu bit;

pentru a realiza decodificarea se calculeaza tot xor intre aceeasi cheie si textul codificat, tot bit cu bit.

Tabela de adevar a functiei XOR este

Aceasta metoda, cunoscuta sub numele de metoda cheilor acoperitoare (one-time pad) are urmatoarele avantaje:

textul codificat nu ofera criptanalistului nici o informatie,

se poate codifica orice tip fisier (text, imagine, sunet, video, baza de date, executabil),

chiar si atunci cand afla metoda de codificare utilizata, criptanalistul nu are sanse sa deduca cheia, deoarece, sirul de biti al cheii poate avea orice lungime in raport cu sirul de biti corespunzator textului clar.

Cu toata siguranta pe care o ofera aceasta metoda, ea prezinta si dezavantaje practice importante:

cheia nu poate fi memorata, necesitand un suport de preferinta electronic, o copie a ei putand ajunge oricand in posesia unei persoane neautorizate;

indiferent ca este consultata partial sau in intregime informatia codificata trebuie decodificata in inregime.

Acesta este un foarte mare dezavantaj in cazul bazelor de date, utilizatorul fiind obligat sa o decodifice si codifice in intregime, indiferent de numarul de inregistrari pe care le consulta/modifica;

cu cat fisierul codificat este mai mare, cu atat maniputarea lui (consultare/modificare) este mai greoaie, incetinind operarea cu produse software in care este implementata acesta metoda de codificate.

Exemplu

Mesaj

Cheie

Criptograma

Programe pentru criptarea datelor

2.3.1.Programul "Cifrul lui Ceasar generalizat" (P1)

La baza acestui program sunt cele doua functii de criptare si respectiv decriptarea caracterelor.

Functia Codificare() returneaza caracterul codificat si are doua argumente:

unul de tip caracter (el ia valuarea caracterului ce trebuie criptat si

unul de tip intreg si reprezinta cheia dupa care se realizeaza criptarea.

Functia DeCodificare() returneaza caracterul decodificat si are tot doua argumente:

unul de tip caracter (el ia valuarea caracterului ce trebuie decriptat si

unul de tip intreg si reprezinta cheia dupa care se realizeaza decriptarea.

Functia de codificare in limbajul C++

unsigned char Codificare(unsigned char CaracterC, unsigned char Cheie)

else

if((CaracterC>=(unsigned char)'a')&&(CaracterC<=(unsigned char)'z'))

else CaracterR=CaracterC;

return CaracterR;

Functia de decodificare in limbajul C++

unsigned char DeCodificare(unsigned char CaracterC, unsigned char Cheie)

else

if((CaracterC>=(unsigned char)'a')&&(CaracterC<=(unsigned char)'z'))

else CaracterR=CaracterC;

return CaracterR;

2.3.2.Programul "Substitutia monoalfabetica" (P2)

Functia CodificareMonoalfabetica() returneaza caracterul codificat si are drept argumente doua siruri de caractere corespunzatoare alfabeului si cheii, caracterul de codificat si un numar intreg corespunzator lungimii alfabetului/cheii.

Functia de codificare in limbajul C++

unsigned char CodificareMonoalfabetica(char Alfabet[251], char Cheie[251],

char OctetNecodificat, int LungimeAlfabet)

Functia DecodificareMonoalfabetica() returneaza caracterul decodificat si are drept argumente doua siruri de caractere corespunzatoare alfabeului si cheii, caracterul codificat si un numar intreg corespunzator lungimii alfabetului/cheii.

Functia de decodificare in limbajul C++

unsigned char DecodificareMonoalfabetica(char Alfabet[251],

char Cheie[251], char OctetCodificat, int LungimeCheie)

2.3.3.Programul "Transpozitia pe coloane" (P3)

Functiile CodificarePrinTranspozitie() si DecodificarePrinTranspozitie() se utilizeaza la criptarea respectiv decriptarea unor fisiere de tip text. Ele returneaza valoarea 0 daca s-a executat codificarea sau valoarea 1 daca fisierul sursa nu exista. Ele au argumentele: numele fisierului sursa, numele fisierului destinatie si cheia dupa care se realizeaza codificarea.

Functia de codificare in limbajul C++

unsigned char CodificarePrinTranspozitie(char *FisierSursa,

char *FisierDestinatie, char *Cheie)

FisierScris.open(FisierDestinatie, ios::binary | ios::trunc);

LungimeFisier=FisierCitit.tellp();

for(i=0; i<LungimeCheie; i++)

}

FisierCitit.close();

FisierScris.close();

}

else Eroare=1;

return Eroare;

Functia de decodificare in limbajul C++

unsigned char DecodificarePrinTranspozitie(char *FisierSursa,

char *FisierDestinatie, char *Cheie)

LungimeFisier=FisierCitit.tellp();

LungimeGrupe=div(LungimeFisier, LungimeCheie);

for(i=0; i<LungimeCheie; i++)

}

FisierScris.open(FisierDestinatie, ios::binary | ios::trunc);

for(m=0; m<=LungimeGrupe.quot; m++)

for(i=0; i<LungimeCheie; i++)

}

FisierScris.close();

FisierCitit.close();

}

else Eroare=1;

return Eroare;

Programul "Metoda cheilor acoperitoare" (P4)

Functia MetodaCheilorAcoperitoare() este utilizata atat pentru operatia de codificare cat si pentru operatia de decodificare.

In cazul codificarii argumentele ei sunt: numele fisierului ce contine informatia de codificat, numele fisierului de contine cheia si numele fisierului ce va contine informatia codificata.

In cazul decodificarii argumentele ei sunt: numele fisierului ce contine informatia codificata, numele fisierului de contine cheia si numele fisierului ce va contine informatia decodificata.

Functia de codificare/decodificare in limbajul C++

unsigned char MetodaCheilorAcoperitoare(char *FisierSursa,

char *FisierDestinatie, char *Cheie)

OctetDestinatie=OctetSursa^OctetCheie;

FisierScris.write((unsigned char *) &OctetDestinatie, sizeof(OctetDestinatie));

FisierCitit.read((unsigned char *) &OctetSursa, sizeof(OctetSursa));

}

FisierCitit.close();

FisierCheie.close();

FisierScris.close();

return 0;

3. MOD DE LUCRU

- se completeaza secventele de program propuse P1, P2, P3, P4 cu declaratiile si celelalte elemente de program necesare;

- se compileaza, se linkediteaza si se lanseaza in executie;

Lucrarea se considera incheiata cand toate programele sunt functionale.

4. CHESTIUNI DE STUDIAT

- Ce avantaje si dezavantaje are criptosistemul "Cifrul lui Caesar generalizat"?

- Ce proprietati se folosesc pentru a sparge cu usurinta criptosistemul 'mono-substitutie alfabetica'

- Cum se poate deduce ca un text este codificat cu transpozitie pe coloane

- Cum se poate sparge ipotetic un criptosistem cu transpozitie pe coloane

- Enuntati principalele avantaje de criptare prin 'metoda cheilor acoperitoare'

- Care este dezavantajul major al criptarii prin 'metoda cheilor acoperitoare'

Sa se calculeze:

numarul de chei posibile ale criptosistemul "cifrul lui Caesar generalizat";

numarul de chei posibile ale criptosistemul 'monosubstitutie alfabetica';

numarul de chei posibile ale criptosistemul ' transpozitie pe coloane';

lungimea minima si maxima a cheii prin 'metoda cheilor acoperitoare'.