Pe scurt
Criptarea și compresia sunt două domenii fundamentale ale informaticii, aplicate frecvent în securitatea datelor și optimizarea stocării. Criptarea transformă datele într-o formă ilizibilă folosind un algoritm și o cheie, în timp ce compresia reduce dimensiunea datelor prin eliminarea redundanței. Pentru Bacalaureat (opțional), accentul cade pe algoritmi clasici precum Caesar, Vigenere și RLE, ușor de implementat în pseudocod sau limbaje de programare.
Criptarea datelor
Criptarea transformă datele (text clar) într-o formă ilizibilă (text cifrat) folosind un algoritm și o cheie, asigurând confidențialitatea.
Tipuri de criptare
- Criptarea simetrică – aceeași cheie pentru criptare și decriptare (exemple: Caesar, Vigenere, AES)
- Criptarea asimetrică – cheie publică și cheie privată (exemplu: RSA)
Algoritmul Caesar
Deplasează fiecare literă cu un număr fix de poziții în alfabet (cheia).
Exemplul 1 – Criptare Caesar în C:
- Se citește un șir de caractere și o cheie k (întreg)
- Fiecare literă mică 'a'-'z' este deplasată circular cu k poziții
- Pentru decriptare, se scade k
- Implementare:
for(i=0; i<strlen(s); i++) if(s[i]>='a' && s[i]<='z') s[i] = ((s[i]-'a'+k)%26)+'a';
- Atenție: la decriptare se folosește
(s[i]-'a'-k+26)%26
Algoritmul Vigenere
Folosește un cuvânt-cheie pentru a deplasa literele diferit, pe baza unei matrici.
Exemplul 3 – Criptare Vigenere în pseudocod:
- Se citește textul clar și un cuvânt-cheie
- Pentru fiecare caracter, se determină deplasarea pe baza literei corespunzătoare din cheie (reluată circular)
- Formula:
criptat[i] = (clar[i] + cheie[j]) % 26, unde j = i % lungime_cheie
- Decriptarea se face prin scădere
- Acest algoritm este mai robust decât Caesar
Compresia datelor
Compresia reduce dimensiunea datelor prin eliminarea redundanței.
Tipuri de compresie
- Compresia fără pierderi (lossless) – exemple: Run-Length Encoding (RLE), Huffman
- Compresia cu pierderi (lossy) – exemple: JPEG, MP3 (nu se studiază în detaliu la BAC opțional)
Run-Length Encoding (RLE)
Înlocuiește șirurile repetate de caractere cu perechi (contor, caracter).
Exemplul 2 – Compresie RLE în C:
- Se citește un șir, de exemplu 'aaabbcccc'
- Rezultatul comprimat: 'a3b2c4'
- Implementare: parcurgem șirul, numărăm caracterele consecutive, afișăm caracterul și numărul
- Atenție: pentru șiruri fără repetiții (ex: 'abcd'), compresia poate crește dimensiunea; de aceea RLE este eficient doar pe date redundante
Codarea Huffman
Construiește un arbore binar optim, atribuind coduri mai scurte caracterelor frecvente.
Concepte cheie
- Criptare simetrică vs asimetrică
- Algoritmul Caesar (deplasare circulară)
- Algoritmul Vigenere (cuvânt-cheie)
- Compresie RLE (Run-Length Encoding)
- Compresie fără pierderi (lossless)
- Cheie de criptare
- Decriptare reversibilă
Observații importante
- Algoritmii moderni (AES, RSA) sunt menționați doar la nivel teoretic, fără implementare
- Securitatea criptării depinde de lungimea cheii și de rezistența la atacuri
- Compresia trebuie să fie reversibilă complet pentru date text
- Un text simplu poate fi criptat cu Caesar (cheie 3) și comprimat cu RLE pentru a ilustra combinarea tehnicilor
- În cadrul opțional, se cere înțelegerea principiilor, implementarea simplă în pseudocod și analiza eficienței
- Lecția include exemple concrete de implementare în C și exerciții grilă și cu răspuns liber, model BAC
Verifică-te!
- Care este diferența principală între criptarea simetrică și cea asimetrică?
- Ce se întâmplă cu dimensiunea datelor atunci când aplici compresia RLE pe un șir fără caractere repetate?
- Cum se determină deplasarea pentru fiecare caracter în algoritmul Vigenere?