Sisteme secrete - Modelul lui Shannon

Introducere

C.E. Shannon a introdus în 1949 cadrul teoretic fundamental al criptografiei moderne, definind riguros noțiunile de secret, sistem de cifrare și redundanță într-un limbaj matematic.

Modelul matematic al sistemului secret

Un sistem de cifrare implică trei entități:

Cifratorul: transmite mesajul cifrat
Receptorul: primește și descifrează mesajul
Interceptorul: încearcă să descifreze mesajul fără a cunoaște cheia

Se definesc trei mulțimi finite:

M - spațiul mesajelor (toate mesajele posibile)
C - spațiul criptogramelor (toate criptogramele posibile)
K - spațiul cheilor (toate cheile disponibile)

Fiecare cheie kᵢ ∈ K determină o transformare tₖᵢ: M → C.

Definiția Shannon pentru un sistem de cifrare

Un sistem de cifrare este o familie de transformări reversibile dintr-o mulțime de mesaje M într-o mulțime de criptograme C. Cele trei mulțimi T, M și C sunt, de obicei, finite.

Cerința fundamentală: cunoașterea criptogramei, cheii și algoritmului permite determinarea univocă a mesajului. Dacă c = tₖ(m), atunci m = tₖ⁻¹(c).

Diferența esențială: receptorul cunoaște cheia k, pe când interceptorul cunoaște doar probabilitățile apriori ale transformărilor.

Reprezentarea sistemelor secrete

Sistemele secrete se pot reprezenta prin diagrame liniare: punctele din stânga reprezintă mesajele, cele din dreapta criptogramele, iar liniile etichetate cu chei arată transformările. Dacă fiecare mesaj și fiecare criptogramă au exact o linie pentru fiecare cheie, sistemul se numește sistem închis.

Sisteme secrete perfecte

Un sistem secret este perfect dacă pentru toate criptogramele C, probabilitățile aposteriori sunt egale cu probabilitățile apriori ale mesajelor: P(M|C) = P(M).

Aceasta înseamnă că interceptarea criptogramei nu oferă nicio informație despre mesajul transmis. Condiția echivalentă: P(C|M) = P(C), adică probabilitatea de obținere a unei criptograme nu depinde de mesajul ales.

Într-un sistem perfect:

Numărul cheilor ≥ Numărul mesajelor
Entropia cheii satisface H(K) ≥ H(M)

Compunerea sistemelor secrete

Fiind date două sisteme T și R:

Suma ponderată: S = pT + qR, cu p + q = 1

Sistemul rezultat S reunește transformările ambelor sisteme, cu probabilitățile ponderate

Produsul: S = R · T

Se aplică mai întâi T, apoi R pe rezultat
Cheia lui S = (cheia lui T, cheia lui R), alese independent
Produsul nu este comutativ: RT ≠ TR în general
Produsul este asociativ: R(ST) = (RS)T

Proprietăți algebrice:

Distributivitatea: T(pR + qS) = pTR + qTS
Un sistem cu M = C se numește endomorf

Cele 5 principii Shannon

Shannon a elaborat în 1940 cele cinci principii fundamentale de evaluare a sistemelor secrete:

Cantitatea de secretizare oferită - complexitatea și rezistența sistemului trebuie să fie proporționale cu importanța mesajelor
Mărimea cheii - cheia trebuie suficient de lungă pentru a asigura un număr mare de transformări, dar suficient de scurtă pentru distribuire practică; cerințe contradictorii
Simplitatea operațiunilor de cifrare și descifrare - complexitatea excesivă duce la erori (manual) sau la echipamente costisitoare (automat)
Propagarea erorii - erorile de transmitere nu trebuie să afecteze porțiuni mari din mesaj
Extensia mesajului - cifrarea nu trebuie să crească semnificativ lungimea textului

Cele cinci principii sunt parțial incompatibile și nu pot fi satisfăcute simultan.

Difuzia și confuzia

Shannon a propus două tehnici fundamentale de cifrare:

Difuzia: împrăștierea caracteristicilor statistice ale mesajului în structura criptogramei, modificând frecvențele de apariție ale caracterelor. Efectul: criptanalistul trebuie să intercepteze o criptogramă mult mai lungă.

Confuzia: realizarea unei corelații cât mai complexe între criptogramă și cheie, astfel încât fiecare caracter cifrat să depindă de întreaga structură a cheii.

Exemplu: sistemul cu acoperire unică (one-time pad)

Cel mai sigur sistem criptografic cunoscut. Mesajul și cheia sunt șiruri binare de aceeași lungime, iar cifrarea se face prin XOR:

Mesaj:       m = 0 1 0 0 1 0 1 1 1 0 1
Cheie:       k = 1 0 1 1 0 0 0 1 0 1 1
Criptograma: c = 1 1 1 1 1 0 1 0 1 1 0

unde c = m ⊕ k (operația XOR bit cu bit).

Proprietăți:

Sistemul este perfect (Shannon a demonstrat acest lucru)
Cheia trebuie să fie aleatoare, de lungime cel puțin egală cu mesajul, și folosită o singură dată
Nu prezintă propagare a erorii: o eroare într-un bit afectează doar acel bit
Necesită sincronizare perfectă între emițător și receptor
Dezavantaj principal: lungimea cheii este egală cu lungimea mesajului

Puncte cheie pentru examen

Modelul Shannon: tripletul (M, T, C) cu transformări tₖ: M → C
Definiția Shannon: familie de transformări reversibile din M în C
Sistem perfect: P(M|C) = P(M) - criptograma nu oferă informație despre mesaj
Compunerea: suma ponderată S = pT + qR și produsul S = RT (asociativ, necomutativ)
Cele 5 principii: cantitatea de secretizare, mărimea cheii, simplitatea, propagarea erorii, extensia mesajului
Difuzia: împrăștie statisticile mesajului; Confuzia: complică relația cheie-criptogramă
One-time pad: sistem perfect, c = m ⊕ k, cheie aleatoare de lungimea mesajului, folosită o singură dată

Exemple practice suplimentare

Exemplu 1: Secretul perfect — cifrul Vernam (OTP)

Fie alfabetul binar. Mesajul: M = 10110, cheia: K = 01101 (aceeași lungime, aleatoare uniform).

Cifrare (XOR):

M:    1 0 1 1 0
K:    0 1 1 0 1
─────────────────
C:    1 1 0 1 1

Descifrare:

C:    1 1 0 1 1
K:    0 1 1 0 1
─────────────────
M:    1 0 1 1 0  ✓

De ce e secret perfect? Pentru orice text clar M și orice text cifrat C, există exact o cheie K = M ⊕ C. Dacă cheile sunt echiprobabile, P(M|C) = P(M) — observarea textului cifrat nu furnizează nicio informație despre mesaj.

Exemplu 2: Redundanța limbajului și distanța de unicitate

Redundanța unui limbaj natural cu entropia H și dimensiunea alfabetului L:

R = 1 - H / log₂(L)

Pentru limba română (L = 31 caractere, H ≈ 3.5 biți/caracter):

R = 1 - 3.5 / log₂(31) = 1 - 3.5 / 4.954 = 1 - 0.707 = 0.293

Redundanța ≈ 29.3%

Distanța de unicitate (lungimea minimă de text cifrat pentru a determina unic cheia):

U = H(K) / R_L

Dacă H(K) = 40 biți (spațiul cheilor) și R_L = 0.293 · 4.954 = 1.452 biți/caracter:

U = 40 / 1.452 ≈ 28 caractere

Deci cu ~28 caractere de text cifrat se poate (teoretic) determina unic cheia.

Exemplu 3: Equivocația mesajului

Equivocația H(M|C) reprezintă incertitudinea rămasă asupra mesajului după interceptarea textului cifrat:

H(M|C) = H(K|C) - H(K) + H(M)   (din relațiile Shannon)

Pentru secretul perfect: H(M|C) = H(M) — interceptarea nu reduce deloc incertitudinea.

Pentru cifrul substitut simplu: H(M|C) → 0 pe măsură ce lungimea textului crește, deoarece redundanța limbii elimină ambiguitatea.