Pe Internet, există mai multe opțiuni pentru calcularea sumei de control CRC. Dar ce este de fapt o sumă de control și de ce este calculat în acest fel? Să recunoaștem. Și, în același timp, a scrie un program care va calcula CRC cu parametrii specificați.
1 Teoria care stă la baza calculului CRC
În primul rând, trebuie să înțelegem un pic teorie. Deci, ce este CRC? Pe scurt, acesta este unul dintre soiurile de calcul al sumei de control. Checksum - o metodă de verificare a integrității informațiilor primite pe partea de receptor a transmisiei prin canale de comunicare. De exemplu, una dintre cele mai simple teste - utilizarea de biți de paritate. Acest lucru atunci când a adăugat toți biții mesajului transmis, iar în cazul în care suma este chiar, apoi se adaugă la mesajul 0 dacă impar - 1. Atunci când recepția se calculează ca suma de biți de mesaje și este comparat cu bitul de paritate primit. În cazul în care acestea sunt diferite, atunci apar erori de transmisie, iar informațiile transmise au fost denaturate.
Dar această metodă de determinare a prezenței de bug-uri - foarte uninformative și nu funcționează întotdeauna, deoarece distorsiunea puținele posturi biți, paritate suma nu poate fi schimbată. Prin urmare, există mai multe teste „avansate“, inclusiv CRC.
De fapt, CRC - acest lucru nu este suma, iar rezultatul divizării o anumită cantitate de informații (mesaj de date) la o constantă - sau, mai degrabă, restul de posturi de divizare o constantă. Cu toate acestea, CRC, de asemenea, denumit punct de vedere istoric ca „control“. Valoarea CRC contribuie fiecare bit al mesajului. Aceasta este, în cazul în care cel puțin un bit al mesajului inițial sa schimbat în tranzit, suma de control se va schimba de asemenea, cu considerabil. Acesta este un mare plus acest test, deoarece vă permite să identificați în mod unic distorsionat mesajul original atunci când trimiteți sau nu.
Care este mesajul original - este de înțeles. Aceasta este o secvență de biți continuă de lungime arbitrară.
Ce fel de constantă, pe care trebuie să împartă mesajul original? Este, de asemenea, un număr de orice lungime, dar sunt utilizate în mod tipic multipli de 1 octet - 8, 16 sau 32 de biți. Doar așa că este mai ușor să credem, deoarece calculatoarele pentru a lucra cu bytes, mai degrabă decât cu biți.
Constantă-divizor este scris de obicei ca un polinom (polinom) astfel: x 8 + x 2 + x 1 + x 0. Aici, gradul de „x“ indică poziția bit în unități, inclusiv începând cu zero, iar MSB indică gradul polinomului este îndepărtat și formele de interpretare. Aceasta este, numărul înregistrat anterior - acest lucru nu este nimic mai mult decât o (1) 00000111 în notație binară sau zecimală 7. În paranteze, am implicat numărul MSB, nu se obișnuiește să se scrie.
Iată un exemplu: x 16 + x 15 + x 2 + x = 0 (1) 1000000000000101 = 0x8005 = 32773.
anumite polinoame standard sunt frecvent utilizate pentru diferite tipuri de CRC. Iată câteva dintre ele:
Articolul Wikipedia consacrat calculul CRC, există o masă mare de formare polinoame.
Deci, cum considerați suma de control? Există o metodă de bază - împărțirea posturilor de un „cap“ polinom - și modificarea acesteia, în scopul de a reduce cantitatea de calcul și, astfel, accelera calculul CRC. În primul rând, am o metodă de bază ia în considerare.
În general, numărul de divizare prin polinomul se realizează prin acest algoritm. Algoritmul de calcul CRC control:
- array Creat (registru) umplut cu zerouri egale în lungime-lățime (grade) polinomială.
- Mesajul original este căptușit în rândurile juniori, într-o cantitate egală cu numărul de biți ai polinomului.
- În mai tineri cifră de registru este introdus una mesaje MSB, și se extinde de la descărcarea mai vechi registru de un bit.
- Dacă bitul extins este „1“, bitul inversia se efectuează (operație XOR, XOR) biților din registrele care corespund unităților din polinoamelor.
- Dacă mesajul are încă biți, mergeți la pasul 3).
- Atunci când toți biții mesajului primit, în cazul și au fost prelucrate de către acest algoritm, registrul rămâne restul împărțirii, care este un CRC sumă de control.
Noi numim această metodă de calcul metoda de deplasare biți CRC sau o metodă simplă.
Figura ilustrează divizarea secvenței originale de biți de numărul (1) 00000111, sau polinomul x 8 + x 2 + x + 1 x 0.
Apropo, verifică corectitudinea calculului CRC este foarte simplu. La alineatul (2) din acest algoritm avem în loc de adaosurile de mesaje zerouri inițiale pentru a completa biții săi calculate de control, iar restul este lăsat așa cum este. Acum, restul mesajului diviziune augmentată la polinomului trebuie să fie zero - acesta este adevăratul semn al sumei de control calculate. Un rest nenulă indică o eroare.
Există încă câteva puncte merită să spun. După cum puteți vedea, mesajul poate fi împărțit în orice număr. Cum să-l aleg? Există un număr de polinoame standard, care sunt utilizate în calculul CRC. De exemplu, crc32 pentru acest lucru poate fi numărul 0x04C11DB7, iar pentru acest lucru poate fi CRC16 0x8005.
În plus, în cazul de la începutul calculelor pot fi scrise nu este zero, dar unele alt număr. (Este recomandat să faceți: astfel, crește fiabilitatea de a determina începerea transmiterii unui mesaj, de exemplu, dacă un mesaj este la începutul zero biți).
De asemenea, în calculele imediat înainte de emiterea de control CRC final poate fi împărțit în alt număr.
Și ultimul. Posturi octeți pentru înregistrarea în registru poate fi plasat ca cel mai semnificativ bit „înainte“, și vice-versa, un junior. Și CRC rezultat poate fi, de asemenea, emise, începând cu MSB sau mai tineri.
Schimbarea ordinii de biți într-un octet pentru a inversa noi numim „tratament“, „inversă“ sau „oglindire“ octet.
Total are 6 parametri care afectează valoarea de control:
- ordin al CRC;
- definirea polinom (numită uneori „polinomului generator“, Traducere din limba engleză literalmente);
- Conținutul inițial al registrului;
- valoare, care a făcut XOR final;
- mesaj de date octet Reverse;
- Reverse bytes CRC înainte de XOR finală.
2 CRC metoda de calcul al sumei de control trecerea de biți
Pe baza celor de mai sus, să scrie o funcție în Visual Basic .NET limba, care se va calcula CRC sumă de control, luând o serie de parametri pe care le-am descris mai sus, și returnarea valoarea CRC ca un 32 de biți numere fără semn.
Programul propus este scalabilitate slabă. Adică, funcționează bine în calcularea sumei de control CRC pentru mesaje scurte de până la câteva zeci de kilobytes. L-am scris cu scopul de a arăta doar munca unui algoritm simplu, și nu este angajată în optimizare. La calcularea CRC pentru un mesaj lung, dimensiunea de zeci sau sute de megabytes, programul va supraîncărca procesor și memorie, ca întregul mesaj este descărcat la coada. Acest lucru contribuie la o metodă de conversie într-o secvență de biți folosind Coadă (de Boolean). Pentru a lucra cu astfel de mesaje mari este de dorit să se pună în aplicare un tampon intermediar, care va transmite un mesaj către program în porții mici.
Dar acest program are un alt avantaj: acesta poate fi utilizat pentru calculul CRC orice ordine, nu neapărat 8, 16 sau 32. Poate fi CRC5 sau CRC49. Numai pentru un număr mai mare de 32-biți pentru a fi modificat în consecință intrări - să zicem, poli transmite nu ca UInteger. ci ca ulong. sau transmite ca bitmap (procedura CRC atunci, teoretic, în general, va fi nelimitat).
3 CRC metoda de calcul de control al tabular
Pentru a reduce numărul de calcule ale metodei anterioare - metoda de deplasare biți - a venit cu unele optimizare.
În special, trecerea nu este un bit la un moment dat, și de la câteva. Cea mai mare popularitate câștigat realizări în care mesajul numărul de biți decalate cu un multiplu al numărului de biți dintr-un octet este 8, 16 sau 32, după cum Byte mai ușor la locul de muncă (nu sunt necesare mai multe modificări). În acest algoritm, ideea rămâne aceeași: o schimbare și de conținut registru SAU exclusiv cu.
În plus, se pare că o parte din calculele pot fi efectuate în prealabil și scris într-o matrice - tabelul de la care va fi luată de numărul necesar după cum este necesar. O astfel de metodă de calcul numită metoda de calcul tabelar CRC.
Acest cod este gata de utilizare, puteți lua și aplica. Pentru a utiliza acest program, după cum urmează:
- a crea o instanță a clasei RocksoftCrcModel (). a trecut la modelul parametrilor de constructor CRC;
- pentru a calcula suma de control, pentru a invoca o metodă a unui obiect ComputeCrc () sau ComputeCrcAsBytes (). utilizând un mesaj de informații parametru pentru care doriți să calculeze suma de control;
- dacă modificați parametrii modelului CRC, tabelul se recalculează automat, și o nouă instanță a clasei, nu puteți crea.
Aici este un exemplu de utilizare a acestui algoritm de clasă CRC16. Ca mesaj de mesaje vor utiliza un șir de octeți, care este un șir de caractere „123456789“ în codul ASCII, care este folosit în multe calculatoare on-line CRC:
Acest calcul punerea în aplicare a CRC a fost verificată de mine prin comparație cu multe calculatoare on-line CRC (numesc test de „slab“, și anume o definiție dată în articolul de mai sus, atunci când verificarea se efectuează prin compararea control calculată cu standardul, folosind aceiași parametri inițiali și mesajul) .
Pentru fanii C # rescrie clasa după cum urmează:
Este aplicat articolul complet de lucru și gata de utilizare dosar RocksoftCrcModel.vb cu punerea în aplicare a calculului sumei de control CRC, pe care am analizat aici, precum și RocksoftCrcModel.cs în C #.
4 "Hacking" checksum CRC32 și CRC16
atinge pe scurt întrebarea, „furt» crc32. Și, mai presus de toate, să ne definim conceptul de „hacking“, în legătură cu această problemă.
În cazul în care problema determinării sumei de control a unui set de date - o provocare directă, de „hacking“ - este problema inversă, și anume ajustarea sumei de control pentru un anumit set de date.
Să presupunem că aveți un fișier și se calculează suma de control. Ai nevoie să-l schimbe la un număr arbitrar de octeți, menținând în același timp o sumă de control. Asigurați-vă că nu este dificil.
Mai întâi trebuie să găsiți în mod obișnuit crc32, CRC16 sau orice alta, ceea ce ai nevoie pentru acest fișier modificat. Să fie C1. Acum trebuie să adăugați același număr de bytes nule la dosar, care conține o sumă de control (pentru CRC32 - 4 octeți pentru CRC16 - 2 bytes, etc.). Puteți alege un simplu număr C2 brute-force. care scriem aceste octeți nule. La urma urmei, este clar că întreaga gamă de valori admise stabilite CRC32 2 32
4.295 miliarde. Aceasta este pentru 4 miliarde cu o cantitate mică de calcul iterații controlul cu conținutul inițial al registrului egal cu C1. Noi brute force ( „cap“ brute force) va selecta valoarea dorită. Cu putere de calcul modernă este nici o problema. Și „hack“, folosind CRC16 busting la toate o chestiune de secunde.
Pot pune octeți nule în mijlocul sau începutul unui fișier? Posibil. K XOR lege funcționare asociative se aplică: a XOR (XOR b c) = (a XOR b) XOR c. Prin urmare, poate fi împărțit cu succes fișierul în 3 părți: pentru a insera după inserția, și inserția în sine. Se calculează CRC pentru primele două părți (C1 și C2 în figură), combina XOR funcționarea lor, umple acest număr cuprins registru inițial și apoi „sbrutforsit» CRC rest treia parte X.
Sunt mod mai inteligent și elegant pentru a ajusta CRC sub valoarea dorită. Esența ei este că, în loc de o căutare în serie a tuturor valorilor într-un rând suntem „înapoi“ de câteva ori (numărul de octeți sau de control biți), algoritmul de tabele sau de biți algoritm de schimbare în sus, până când CRC nu este de dorit. Nu voi intra în detalii cu privire la acest subiect există o mulțime de detalii și materiale de calitate în rețea.
Astfel, concluzia: CRC tip de control este foarte potrivit pentru controalele de integritate a datelor la denaturări aleatorii ale informațiilor în canalul de transmisie de date, dar nu este potrivit pentru o protecție împotriva falsificării intenționate.
Deci, pentru a rezuma rezultatele. În acest articol, vom:
- a învățat ce CRC și care sunt tipurile sale;
- a învățat cum să calculeze CRC metoda de schimbare biți și metoda de tabel; - să învețe algoritmi „hacking» CRC și a concluzionat că limitele de aplicabilitate a tipului de control CRC.