Hogyan kell kiszámítani az ellenőrző crc32, CRC16, crc8
Az interneten sok lehetőség kiszámításához az ellenőrző CRC. De mit is jelent egy ellenőrző és miért így számított? Nézzünk szembe a tényekkel. És egyúttal írj egy programot, amely kiszámítja a CRC a megadott paraméterekkel.
1 Az elmélet alapjául szolgáló CRC
Először is, nézzük megérteni egy kis elmélet. Szóval, mi a CRC? Röviden, ez az egyik fajta kiszámításának ellenőrző. Ellenőrző - módszer sértetlenségének ellenőrzése a kapott információt a fogadó oldalán az átviteli kommunikációs csatornákon keresztül. Például, az egyik legegyszerűbb tesztek - használata paritásbit. Ez adva minden bit a továbbított üzenet, és ha az összeg páros, akkor hozzáadjuk az üzenet 0, ha páratlan - 1. A fogadás összegeként kiszámított üzenet bitek és összehasonlítjuk a kapott paritás bit. Ha ezek különbözőek, akkor az átviteli hibák fordulnak elő, és a továbbított információt nem torzul.
De ez a módszer jelenlétének meghatározására hibákat - nagyon nem informatív, és nem mindig működik, mert a torzítás a pár hozzászólás bit, paritás az összeg nem lehet változtatni. Ezért sok „fejlettebb” vizsgálatok, beleértve a CRC.
Tény, hogy a CRC - ez nem az összeg, és az eredmény felosztásának egy bizonyos mennyiségű információ (adat üzenet) állandó - vagy inkább a maradék osztály üzenete állandó. Azonban CRC történelmileg is nevezik „ellenőrző”. A CRC érték hozzájárul minden kis üzenet. Azaz, ha legalább egy kicsit az eredeti üzenet megváltozott a szállítás, az ellenőrző is meg fog változni, és jelentősen. Ez egy nagy plusz ezt a tesztet, mivel lehetővé teszi, hogy egyedi azonosítására torz az eredeti üzenetet, ha elküldi, vagy sem.
Mi az eredeti üzenet - érthető. Ez egy folyamatos bitszekvencia tetszőleges hosszúságú.
Milyen állandó, amit meg kell osztani az eredeti üzenetet? Ez is egy szám bármilyen hosszúságú, de jellemzően használt többszörösei 1 bájt - 8, 16 vagy 32 bit. Csak így könnyebb azt hinni, mert a számítógépek dolgozni bájt helyett bit.
A konstans-elválasztó általában írva, mint egy polinom (polinom) így: x 8 + x 2 + x 1 + x 0. Itt, a mértéke „X” jelzi a bit pozíció egységek, beleértve a kiindulási nulla, és az MSB jelzi fokú polinom eldobjuk és értelmezési formákat. Ez azt jelenti, a korábban felvett számot - ez nem más, mint egy (1) 00000111 bináris jelölés vagy decimális 7. Zárójelben, már burkolt MSB szám, ez nem szokás írni.
Itt egy példa: x 16 + x 15 + x 2 + x 0 = (1) 1000000000000101 = 0x8005 = 32773.
egyes általános polinomok gyakran használják a különböző típusú CRC. Íme néhány közülük:
A Wikipedia cikket szentelt a számítás a CRC, van egy nagy asztal alkotó polinomok.
Szóval hogyan lehet vizsgálni az ellenőrző? Van egy alapvető módszer - a szétválás üzenete polinom „fej” - és annak módosítását annak érdekében, hogy csökkentse a számítás, és így felgyorsítja a CRC számítás. Először is vizsgáljuk meg, hogy egy alapvető módszer.
Általában az osztás száma polinommal végezzük ezt az algoritmust. Algoritmust az ellenőrző CRC:
- Alkotó array (regisztrálja) nullákkal töltjük fel egyenlő hosszúak-szélesség (fok) polinom.
- Az eredeti üzenet párnázott a junior soraiban, olyan összegben a bitek száma a polinom.
- Fiatalabb regiszter digit bevitele egy MSB üzeneteket, és kiterjeszti a régebbi egybites regiszter mentesítést.
- Ha a kiterjesztett bit „1”, a bit inverzió végezzük (XOR művelet, XOR) a bitek a nyilvántartások, amelyek megfelelnek az egységek a polinom.
- Ha az üzenet továbbra is bit, ugorjon a 3. lépésre).
- Amikor az összes bit a kapott üzenet esetében, és már feldolgozott ezt az algoritmust, a nyilvántartás továbbra is fennmaradó részlege, amely egy ellenőrző CRC.
Ezt hívjuk számítási módszere CRC Biteltolás módszer, vagy egy egyszerű módszerrel.
Az ábra illusztrálja a szétválás az eredeti szekvencia a bitek száma (1) 00000111, vagy polinom x 8 + x 2 + x 1 + x 0.
By the way, ellenőrizze a helyességét a kiszámítása CRC nagyon egyszerű. A (2) Ennek az algoritmusnak van helyette a kezdeti nullák üzenet kiegészítések kiegészítését bit számított ellenőrző, és a többi marad, ahogy van. Most a való osztás maradéka kibővített üzenetet a polinom nullának kell lennie - ez az igazi jele a kiszámított ellenőrző. A nullától fennmaradó hibát jelez.
Van még egy pár pontot ér mondani. Mint látható, az üzenet lehet osztani minden számot. Hogyan választja meg? Számos szabványos polinomok, amelyek kiszámítására használt CRC. Például, a CRC32 az lehet a számot 0x04C11DB7, és ez lehet CRC16 0x8005.
Ezen túlmenően, abban az esetben az elején a számítások felírható nem nulla, hanem egy másik számot. (Javasoljuk, hogy nem: így növeli a megbízhatóságát meghatározó kezdete üzenettovábbításba, például, ha az üzenet elején nulla bit).
Szintén a számítások közvetlenül megelőzően a kiadását a végső CRC osztható más számot.
És az utolsó. Hozzászólások byte felvétel a nyilvántartásban hozható a legjelentősebb kicsit „előre”, és fordítva, a junior. És a kapott CRC is kiadható, kezdve az MSB vagy annál fiatalabb.
Sorrendjének megváltoztatása bit egy bájt visszafordítani nevezünk „kezelés”, „hátra” vagy „tükrözés” byte.
Összesen 6 befolyásoló paramétereket az érték a checksum:
- sorrendben a CRC;
- meghatározó polinom (néha a „generátor polinom”, fordította angol szó);
- kezdeti regiszter tartalma;
- értéke, amely lehetővé tette a végső XOR;
- Fordított byte üzenet;
- Fordított CRC bájt, mielőtt a végső XOR.
2 CRC számítási módszere Biteltolás
A fentiek alapján, írjunk egy függvényt a Visual Basic .NET nyelven, amely kiszámítja az ellenőrző összeget CRC, figyelembe számos paraméter, amit a fent leírt, és a visszatérő a CRC értéket, mint a 32 bites előjel nélküli számok.
A javasolt program gyenge skálázhatóság. Ez azt jelenti, hogy jól működik a számítás az ellenőrző összeg CRC rövid üzenetek akár több tíz kilobájt. Írtam azzal a céllal, csak hogy megmutassa a munka egy egyszerű algoritmus, és nem folytat optimalizálás. Kiszámításánál a CRC egy hosszú üzenetet, a mérete több tíz vagy több száz megabájt, a program túl a processzor és a memória, az egész üzenet letöltődik a sorban. Ez hozzájárul egy eljárás átalakul egy bitsorozat a Queue (Boole). Ahhoz, hogy működjön együtt az ilyen nagyméretű üzenetek kívánatos, hogy végre egy köztes puffer, amely egy üzenetet küldhet a program kis adagokban.
De ez a program még egy előnye: hogy lehet használni a CRC számítás tetszőleges sorrendben, nem feltétlenül a 8, 16 vagy 32. lehet CRC5 vagy CRC49. Csak nagyobb számok 32-bit ennek megfelelően módosítani kell bemenetek - mondjuk, poli továbbítja nem UInteger. de ULONG. vagy továbbítja azt a bitmap (CRC eljárás akkor elméletileg általában korlátlan).
3 CRC ellenőrző számítási módszer a táblázatos
Számának csökkentése érdekében a számításokat az előző módszer - a módszer Biteltolás - jött némi optimalizálás.
Különösen a váltás nem egy kicsit egy időben, és egy pár. A legnagyobb népszerűségnek szerzett kiviteli alakokban, amelyekben az üzenet bitjei számának eltolt többszöröse száma bit egy bájt 8, 16 vagy 32, a Byte könnyebb dolgozni (nincs több változtatásra van szükség). Ebben az algoritmusban az ötlet ugyanaz marad: a műszak, és kizárólagos VAGY nyilvántartási tartalmat.
Emellett úgy tűnik, hogy része a számítások lehet tenni előre, és írt egy sor - az asztal veszik a szükséges számú, ha szükséges. Egy ilyen számítási módszer az úgynevezett táblázatos módszer CRC-számítást.
Ez a kód használatra kész, akkor megteszi és alkalmazni. Ahhoz, hogy használni ezt a programot az alábbiak szerint:
- hozzon létre egy példányát az osztálynak RocksoftCrcModel (). átadni a kivitelező paraméterek CRC modellt;
- kiszámításához az ellenőrző, hogy hivatkozhat egy eljárás egy tárgy ComputeCrc () vagy ComputeCrcAsBytes (). paraméter segítségével információs üzenet, amelyre szeretnénk számítani az ellenőrző;
- Ha megváltoztatja a paramétereket a CRC modell, a tábla automatikusan újratervezi, és egy új példányát az osztálynak, nem hozhat létre.
Itt egy példa segítségével ebbe az osztályba CRC16 algoritmus. Ahogy üzenetek üzenet fog használni egy byte tömböt, ami egy string „123456789” az ASCII kódot, amelyet használnak a sok online kalkulátorok CRC:
Ez a végrehajtási CRC számítás igazolta számomra képest sok online kalkulátorok CRC (nevezzük „gyenge” teszt, azaz a meghatározás a fenti cikkben, amikor az ellenőrzési folyamatot során összehasonlították a kiszámított ellenőrző standard, ugyanazt a kezdeti paraméterek és az üzenet) .
A rajongók a C # átírni az osztály az alábbiak szerint:
Alkalmazzák a cikket teljesen működő, és használatra kész RocksoftCrcModel.vb fájl végrehajtása a CRC számítás, amit felül van, valamint RocksoftCrcModel.cs a C #.
4 "Hacking" ellenőrző CRC32 és CRC16
Röviden érintse meg a kérdést: „betörés» CRC32. És mindenek felett, definiáljuk a „hacker” kapcsolatban ezt a kérdést.
Ha a probléma meghatározásának checksum egy adathalmaz - közvetlen kihívást, a „hacker” - az inverz probléma, nevezetesen a kiigazítás a checksum egy adott adathalmaz.
Tegyük fel, hogy van egy fájl, és kiszámítja az ellenőrző összeget. Meg kell változtatni, hogy tetszőleges számú bájt, miközben egy ellenőrző. Legyen ez nem nehéz.
Először meg kell találni a szokásos módon ellenőrző CRC32, CRC16 vagy bármely más, amire szükség van a módosított fájl. Legyen C1. Most meg kell adni az azonos számú nulla bájt a fájl, amely egy ellenőrző (a CRC32 - 4 byte az CRC16 - 2 bájt, stb.) Akkor válasszon egy egyszerű brute-force szám C2. amelyhez írja le ezeket a nulla bájt. Végtére is, egyértelmű, hogy a teljes körű megengedett megállapított érték CRC32 2 32
4.295 Mrd. Ez a 4 milliárd egy kis mennyiségű számítási iteráció a kontroll a kezdeti regiszter tartalmához egyenlő C1. Mi brute force ( „fej” brute force) választja ki a kívánt értéket. A modern számítási teljesítmény nem jelent problémát. És a „hack” segítségével CRC16 mellszobor egyáltalán másodpercek kérdése.
Tehetek a nulla bájt közepén vagy elején egy fájlt? Lehetséges. K XOR művelet asszociatív törvény vonatkozik: egy XOR (XOR b c) = (a XOR b) XOR c. ezért lehet sikeresen szét a fájlt 3 részből áll: szúrni után a betét és a betétet is. Számítsuk CRC az első két rész (C1 és C2 az ábrán), egyesítik működésüket XOR, töltse ez a szám a kezdeti regiszter tartalmát, majd a „sbrutforsit» CRC fennmaradó harmadik rész X.
Jelenleg több intelligens és elegáns módon állítsa be a CRC alatt a kívánt értéket. Ennek lényege, hogy ahelyett, hogy egy soros keresés minden érték egy sorban vagyunk „vissza” egy párszor (a bájtok számát vagy bit checksum) a táblázatos algoritmust vagy algoritmus Biteltolás egészen a CRC nem kívánatos. Nem megyek bele a részletekbe ebben a témában van egy csomó részlet és a minőségi anyagok a hálózatban.
Tehát a következtetés: CRC típus kiválóan alkalmas az adatok integritását ellenőrzéseket véletlenszerűen torzulását az információt az adatátviteli csatorna, de ez nem alkalmas elleni védelem szándékos beavatkozás.
Tehát, összefoglalva az eredményeket. Ebben a cikkben fogjuk:
- megtanult, amit a CRC és mik a fajta;
- megtanulta, hogyan kell kiszámítani a CRC Biteltolás eljárás és táblázatos módszerrel; - további algoritmusok „hacker» CRC és arra a következtetésre jutott, hogy a határértékek alkalmazhatóságának CRC típusát.