Descrierea problemei şi a metodelor de rezolvare utilizate

Pornind de la observaţia că algoritmii criptografici şi criptanalitici sunt mari consumatori de resurse de calcul, soluţia propusă are ca scop studiul şi dezvoltarea unor implementări în tehnologie grid a unora dintre aceşti algoritmi, având ca rezultat optimizarea acestora.

Arhitectura soluţiei propuse va conţine următoarele componente, asociate fiecare unui anumit tip de aplicaţii (algoritmi criptografici şi/sau criptanalitici):

1. Algoritmi de criptare cu cheie secretă, de tip bloc
2. Algoritmi de criptare cu cheie secretă, de tip stream
3. Algoritmi de criptare cu cheie publică
4. Functii de hashing
5. Algoritmi de generare a secvenţelor de numere aleatoare
6. Algoritmi de testare a secvenţelor de numere aleatoare
7. Algoritmi criptanalitici

Pentru rezolvarea acestor probleme (tipuri de aplicaţii) a fost necesară definirea unei taxonomii originale, derivată din taxonomia lui Flynn, dar de granularitate mai mare.

In taxonomia de mai sus, datorita specificului executiei pe grid, prin "program" se înţelege un program secvenţial executat pe unul sau mai multe noduri ale gridului, iar prin "data" se înţelege în mod uzual un fişier de intrare.

Pe baza acesteia, au fost definite următoarele moduri de lucru asociate unei aplicaţii (program, implementare a unui algoritm):

*) Deoarece aceste două moduri de lucru sunt seriale, nu se pune poblema paralelismului aici

Date de intrare şi ieşire

Fiecare componentă a aplicaţiei (categorie de algoritmi, tip de aplicaţii) prezintă caracteristici specifice în ce priveşte datele de intrare şi de ieşire, deoarece algoritmii implementaţi acoperă o paletă largă de primitive criptografice. Vom prezenta în cele ce urmează datele de intrare şi de ieşire pentru fiecare componentă a domeniului aplicativ abordat.

1. Algoritmi de criptare cu cheie secretă, de tip bloc
   • Intrare
     • la criptare: fişierul cu textul în clar
     • la decriptare: fişierul cu criptograma
   • Ieşire
     • la criptare: fişierul cu criptograma
     • la decriptare: fişierul cu textul în clar
2. Algoritmi de criptare cu cheie secretă, de tip stream
   • Intrare
     • la criptare: fişierul cu textul în clar
     • la decriptare: fişierul cu criptograma
   • Ieşire
     • la criptare: fişierul cu criptograma
     • la decriptare: fişierul cu textul în clar
3. Algoritmi de criptare cu cheie publică
   • Intrare
     • la generare de chei: numere aleatoare
     • la criptare: fişierul cu textul în clar
     • la decriptare: fişierul cu criptograma
   • Ieşire
     • la generare de chei: perechea de chei generate, stocate în fişiere diferite
     • la criptare: fişierul cu criptograma
     • la decriptare: fişierul cu textul în clar
4. Functii de hashing
   • Intrare
     • fişierul de intrare
   • Iesire
     • valoarea funcţiei de hashing
5. Algoritmi de generare a secvenţelor de numere aleatoare
   • Intrare
     • parametrii de iniţializare a generatorului, lungimea fişierului de ieşire
   • Ieşire
     • secvenţă de numere aleatoare (baiţi), se va stoca în fişier
6. Algoritmi de testare a secvenţelor de numere aleatoare
   • Intrare
     • fişierul cu secvenţa de numere aleatoare de testat
   • Ieşire
     • clasificarea secvenţei de intrare (ca aleatoare sau nu), conform testelor efectuate
7. Algoritmi criptanalitici
   • Intrare
     • fişierul cu numărul de factorizat
   • Ieşire
     • factorii primi ai numărului de factorizat
     • timpul de execuţie

Implementarea in mediul Grid

Justificare

Studiile recente arată creşteri semnificative în performanţă pentru execuţia în mediu grid a unor algoritmi criptografici consacraţi dar şi unele probleme generate de diferiţi factori care generează calcule suplimentare (overheads), ceea ce indică necesitatea de a aprofunda in continuare studiul acestor metode precum şi necesitatea descoperirii unor metode inovatoare care să se adapteze mai bine mediului grid.

Recent tot mai multe universităţi se orientează spre acest domeniu prin crearea unor laboratoare specializate pe această direcţie de cercetare (ex: Ottawa University’s Bioinformatics and Cryptography Grid Computing Lab) ceea ce subliniază interesul crescut pentru acest domeniu.

Considerăm deci justificată migrarea în mediul grid a unor algoritmi criptografici şi criptanalitici care se va dovedi că se pretează pentru o execuţie în mediul grid, având în vedere avantajele care pot decurge de aici. Menţionăm în acest context că în opinia noastră accentul în cadrul acestei soluţii se pune pe adaptarea unor algoritmi existenţi pe infrastructura de tip grid, algoritmii în sine fiind cunoscuţi şi pe larg studiaţi de comunitatea ştiinţifică internaţională (ex: NIST contest for AES standard), adaptare care să aducă cu sine o creştere cât mai mare de performanţă.

Soluţia de implementare

Fiecare componentă a aplicaţiei constă dintr-o serie de algoritmi criptografici sau criptanalitici. Fiecare algoritm este implementat separat, folosind limbajul de programare C (unanim recunoscut pentru eficienţa implementării), rezultând un fişier executabil al cărui nume va fi chiar numele algoritmului implementat, eventual un acronim al acestuia (ex: Mars, Serpent, AES, BBSG, etc).

Pentru modurile de lucru paralele, am implementat o serie de scripturi care permit folosirea facilă a acestor moduri de lucru pe baza unui fişier de configurare corespunzător.

Cerinţe privind infrastructura Grid

Toate componentele aplicaţiei sunt complet funcţionale, nu necesită cerinţe speciale din punct de vedere hardware şi software, cu excepţia unei biblioteci matematice necesare pentru algoritmii de factorizare. Considerăm aceasta ca unul din avantajele aplicaţiei, care contribuie la portabilitatea ei în mediul grid pe oricare dintre site-urile GridMOSI.

Interfaţa de utilizare

Aplicaţia poate fi utilizată numai de către utilizatorii certificaţi şi înregistraţi în VO GridMOSI. Există două interfeţe de utilizare:

1. Interfata bazata pe linia de comanda
2. Interfata Web

Prin intermediul interfeţei bazate pe linia de comandă, utilizatorii autorizaţi pot executa oricare dintre algoritmii criptografici şi criptanalitici implementaţi, în oricare dintre cele 8 moduri de lucru implementate (din care 2 seriale şi 6 paralele). Pentru a uşura folosirea modurilor de lucru paralele, furnizăm utilizatorilor o serie de scripturi care permit lansarea job-urilor şi gestionarea facilă a acestora

Interfaţa Web implementată este complet echivalentă din punct de vedere funcţional cu interfaţa bazată pe linia de comandă. Ca şi în cazul acesteia, utilizatorii autorizaţi pot executa oricare dintre algoritmii criptografici şi criptanalitici implementaţi, în oricare dintre cele 8 moduri de lucru implementate (din care 2 seriale şi 6 paralele). Diferenţa constă în uşurinţa crescută în utilizare.

Astfel, utilizatorii care nu dispun de cunoştinţele de specialitate necesare pentru a opera pe baza unor scripturi care trebuie configurate corect, vor fi practic asistaţi prin intermediul acestei interfeţe pentru crearea automată a fişierelor de configurare necesare execuţiei paralele a algoritmilor.

Avantaje

Un prim avantaj oferit de aplicaţiile oferite constă în punerea la dispoziţia utilizatorilor sau dezvoltatorilor de aplicaţii a unui pachet complet de algoritmi criptografici care acoperă principalele categorii de primitive criptografice necesare pentru securizarea aplicaţiilor în mediul Grid.

Astfel, în situaţia în care un utilizator oarecare al Gridului are la un moment dat nevoie de un anumit algoritm criptografic oferit de aplicaţia noastră (de exemplu o secvenţă de numere aleatoare), poate apela la aceasta pentru a obţine rezultatul dorit, fără a mai fi nevoit să implementeze el însuşi respectivul algoritm.

În plus, utilizatorul va beneficia de puterea de calcul superioară oferită de infrastructura Grid şi va putea rula algoritmi costisitori ca timp (de exemplu factorizare, care durează ore sau chiar zile) sau care lucrează pe cantităţi mari de date (de exemplu de ordinul GB).

Totodată dacă se recurge la unul din modurile de lucru paralele, utilizatorul poate beneficia de creşteri substanţiale de performanţă care rezultă prin exploatarea paralelismului de date şi a celui de control, acolo unde este posibil (nu toţi algoritmii pot beneficia de ambele tipuri de paralelism).

Nu în ultimul rând, aplicaţia se adresează dezvoltatorilor de aplicaţii în mediul Grid, oferindu-le un set acoperitor de servicii criptografice pentru implementarea componentei de securitate a aplicaţiei lor.

Potenţialul de utilizare

Descrierea rezultatelor

Rezultatele obţinute pot fi încadrate în două categorii distincte: rezultate teoretice şi rezultate aplicative (practice). Rezultatele teoretice obţinute sunt:

• definirea unei taxonomii unitare pentru aplicaţii Grid, derivată prin analogie cu taxonomia lui Flynn, dar de nivel mai inalt (la nivel de aplicaţie, nu de instrucţiune)
• definirea a 8 moduri de lucru (din care 2 seriale şi 6 paralele) derivate din taxonomia propusă, adaptate pentru Grid

Rezultatele practice obţinute sunt concretizate în implementarea următorilor algoritmi criptografici şi criptanalitici:

1. Algoritmi de criptare cu cheie secretă, de tip bloc (Mars, RC6, Rijndael, Serpent, Twofish – criptare, decriptare)
2. Algoritmi de criptare cu cheie secretă, de tip stream (RC4 – criptare, decriptare)
3. Algoritmi de criptare cu cheie publică (RSA – generare chei, criptare, decriptare)
4. Functii de hashing (SHA-1, SHA-256, SHA-512)
5. Algoritmi de generare a secvenţelor de numere aleatoare (LCG, MODEXP, BBSG, MSG, XORG, QCG1, CCG)
6. Algoritmi de testare a secvenţelor de numere aleatoare (Block Frequency, Bit Stream, 3D Spheres, DNA Test, Squeeze, Runs, Birthday)
7. Algoritmi criptanalitici (QS, GNFS)

La aceste rezultate practice se adaugă elaborarea unui set de scripturi care facilitează folosirea acestor algoritmi în modurile paralele de lucru, şi a unei interfeţe Web care permite accesul şi mai facil la setul de aplicaţii implementate.

Evaluarea impactului ştiinţific şi social

Considerăm ca o contribuţie ştiinţifică importantă definirea unei taxonomii unitare pentru aplicaţii Grid, derivată prin analogie cu taxonomia lui Flynn, dar de nivel mai inalt (ca granularitate, la nivel de aplicaţie/program, nu de instrucţiune). Această taxonomie nu este legată în vreun fel de categoriile de algoritmi implementaţi, putând fi folosită şi aplicată pentru orice altă categorie de algoritmi sau aplicaţii care folosesc acelaşi mod de execuţie (batch processing).

De asemenea, cele 8 moduri de lucru (din care 2 seriale şi 6 paralele) derivate din taxonomia propusă şi validată prin prezentarea la manifestări ştiinţifice recunoscute din domeniu, pot fi aplicate la rândul lor şi altor categorii de algoritmi sau aplicaţii.

Aceşti algoritmi pot fi folosiţi în orice domeniu de utilizare care necesită fie securizare prin metode criptografice fie alte cerinţe care au legătură cu acestea. Un exemplu notabil sunt aplicaţiile de simulare bazate pe metode de tip Monte Carlo, care necesită uneori cantităţi semnificative de numere aleatoare; acestea pot fi obţinute cu uşurinţă prin rularea pe grid a unor algoritmi implementaţi în cadrul aplicaţiei de faţă. Conform unor estimări, calculele de tip Monte Carlo consumă aproximativ jumătate din ciclurile procesor ale supercalculatoarelor existente.

Nu în ultimul rând menţionăm ca utilizatori ai aplicaţiei dezvoltate studenţii anului 4 ai secţiei de calculatoare a Universităţii Tehnice din Cluj-Napoca, care folosesc această aplicaţie în cadrul orelor de laborator (laboratorul dedicat programării pe arhitecturi Grid) la disciplina "Programare paralelă". De asemenea masteranzii şi doctoranzii secţiei de calculatoare pot avea acces la această aplicaţie atunci când programul lor de pregătire necesită aceasta.