Sumă de control

O sumă de control este un mic bloc de date derivate dintr-un alt bloc de date digitale în scopul detectarea erorilor care ar fi putut fi introduse în timpul transmisiei sau stocării lor. Sumele de control sunt folosite pentru a verifica integritatea datelor, însă rolul lor nu este de a verifica autenticitatea acestor date.

Sumele de control (engleză checksum) calculate pentru textele din zonele albastre de funcția Unix cksum

O sumă de control este generată de un algoritm bazat pe o funcție hash sau o funcție hash criptografică. În funcție de obiectivele sale de proiectare, un algoritm bun produce de obicei o valoare semnificativ diferită a sumelor de control, chiar și pentru modificările mici aduse datelor de intrare. Acest lucru este valabil mai ales în ceea ce privește funcția hash criptografică. Sumele de control pot fi utilizate pentru a detecta multe erori determinate de corupția datelor și pentru a verifica integritatea datelor: dacă suma de control calculată pentru intrarea de date curentă se potrivește cu valoarea stocată a unei sume de control calculate anterior, există o probabilitate foarte mare ca datele să nu fi fost modificate sau corupte accidental.

Funcțiile pentru sume de control sunt legate de funcțiile hash, amprentele digitale, funcțiile de randomizare și funcțiile hash criptografice. Totuși, fiecare dintre aceste concepte are aplicații diferite, prin urmare și obiective de proiectare diferite. De exemplu, o funcție care returnează începutul unui șir poate oferi un hash adecvat pentru anumite aplicații, dar nu va da niciodată o sumă de control bună. Sumele de control sunt utilizate ca primitive criptografice în algoritmi de autentificare mai mari.

Cifrele de control și biții de paritate sunt cazuri particulare ale sumelor de control, fiind adecvate pentru blocuri mici de date, cum ar fi codurile numerice personale, numerele de conturi bancare, un cuvânt de memorie din calculatoare, un octet etc. Unele coduri corectoare de erori se bazează pe sume de control speciale care nu numai că detectează erori comune, dar în anumite cazuri permit și recuperarea datelor originale.

Algoritmi

Bait și cuvânt de paritate

Cel mai simplu algoritm pentru calcului unei sume de control este așa-numitul longitudinal redundancy check (în română test de redundanță longitudinală), care împarte datele în „cuvinte” cu un număr fix n de biți și apoi calculează sau exclusiv (XOR) al tuturor acelor cuvinte. Rezultatul este atașat la mesaj ca un cuvânt suplimentar. Pentru a verifica integritatea unui mesaj, primitorul calculează sau exclusiv al tuturor cuvintelor din mesaj, inclusiv pentru suma de control; dacă rezultatul nu este un cuvânt format din n zerouri, primitorul știe că a apărut o eroare de transmisie.

Cu această sumă de control va fi detectată orice eroare de transmisie care schimbă un singur bit sau un număr impar de biți ai mesajului. Însă o eroare care afectează un număr par de biți nu va fi detectată dacă acești biți se află în aceeași poziție în două cuvinte diferite. De asemenea, schimbarea a două sau mai multe cuvinte nu va fi detectată. Dacă biții afectați sunt luați la întâmplare (independent), probabilitatea ca o eroare de doi biți să fie nedetectată este 1/n.

Complementul sumei

O variantă a algoritmului anterior este cea care adaugă toate „cuvintele” ca numere binare fără semn, ignorând biții de depășire și adăugând complementul față de doi al totalului ca sumă de control. Pentru a valida un mesaj, primitorul adună toate cuvintele în același mod, inclusiv suma de control. Dacă rezultatul nu este un cuvânt format doar din zerouri, trebuie să fi apărut o eroare. Și această variantă detectează orice eroare pe un singur bit, dar suma modulară este utilizată în SAE J1708.

Dependentă de poziție

Sumele de control simple descrise mai sus nu reușesc să detecteze unele dintre erori care afectează mai mulți biți simultan, cum ar fi schimbarea ordinii cuvintelor din date sau inserarea sau ștergerea cuvintelor care au toți biții zero. Cei mai utilizați în practică algoritmi pentru sumele de control, cum ar fi suma de control Fletcher, Adler-32 și cyclic redundancy check (CRC), abordează aceste slăbiciuni luând în considerare nu numai valoarea fiecărui cuvânt ci și poziția sa în secvență. Această caracteristică mărește în general costul de calcul al sumei de control.

Sumă de control fuzzy

Ideea sumei de control fuzzy a fost dezvoltată pentru detectarea spamului prin e-mail prin construirea de baze de date cooperative privind furnizorii de servicii de e-mail (ISP) suspecți de a difuza spam. Conținutul unui astfel de spam poate varia de multe ori prin detaliile sale, ceea ce ar face ineficientă suma normală de control. Prin contrast, o „sumă de control fuzzy” reduce textul corpului la minimul caracteristic, apoi generează o sumă de control în mod obișnuit. Acest lucru mărește foarte mult șansele ca e-mailurile spam ușor diferite să producă aceeași sumă de control. Software-ul de detectare a spamului ISP-ilor care cooperează, cum ar fi SpamAssassin, trimite sumele de verificare ale tuturor e-mailurilor către serviciul centralizat, cum ar fi DCC. Dacă numărul sumelor de control fuzzy trimise depășește un anumit prag, baza de date consideră că acest lucru indică probabil spam. Utilizatorii serviciului ISP generează în mod similar o sumă de control fuzzy pentru fiecare e-mail și indică serviciului că probabil acesta este spam.

Considerații generale

Un mesaj care are o lungime de m biți poate fi vizualizat ca un colț al unui hipercub m-dimensional. Efectul unui algoritm care produce o sumă de control de n biți este de a aplica fiecare mesaj de m biți pe un colț al unui hipercub mai mare, cu dimensiunea $m+n$. Colțurile $2^{m+n}$ din acest hipercub reprezintă toate mesajele posibile primite. Mesajele valide primite (cele care au suma de verificare corectă) formează un set mai mic, cu doar $2^{m}$ colțuri.

O eroare de transmisie pe un singur bit corespunde apoi unei deplasări dintr-un colț valid (mesajul corect și suma de control) în unul dintre colțurile m adiacente. O eroare care afectează k biți mută mesajul într-un colț care este la k pași din colțul său corect. Scopul unui algoritm bun pentru sume de control este de a împrăștia colțurile valide cât mai departe unul de celălalt, astfel încât să crească probabilitatea ca erorile de transmisie „tipice” să ajungă într-un colț nevalid.

Vezi și

• Cyclic redundancy check (în română sumă de control de tip CRC)

Legături externe

• en Additive Checksums (C) theory from Barr Group
• en Practical Application of Cryptographic Checksums