Jak obliczana jest suma kontrolna CRC32?

Może po prostu tego nie widzę, ale CRC32 wydaje się albo niepotrzebnie skomplikowane, albo niewystarczająco wyjaśnione nigdzie, co mogłem znaleźć w sieci.

Rozumiem, że jest to reszta z arytmetycznego podziału wartości wiadomości nie opartego na przenoszeniu, podzielonej przez wielomian (generujący), ale faktyczna jego implementacja mi umyka.

Przeczytałem Bezbolesny przewodnik po algorytmach wykrywania błędów CRC i muszę powiedzieć, że nie był bezbolesny. Całkiem dobrze omawia teorię, ale autor nigdy nie przechodzi do prostego „to jest to”. Mówi, jakie są parametry dla standardowego algorytmu CRC32, ale zaniedbuje jasno określić, jak do tego dojdziesz.

Część, która mnie dopada, to kiedy mówi „to jest to”, a potem dodaje: „a tak przy okazji, można to odwrócić lub rozpocząć z innymi warunkami początkowymi” i nie daje jasnej odpowiedzi, jaki jest ostateczny sposób obliczenia sumy kontrolnej CRC32 przy uwzględnieniu wszystkich zmian, które właśnie dodał.

• Czy istnieje prostsze wyjaśnienie sposobu obliczania CRC32?

Próbowałem zakodować w C sposób tworzenia tabeli:

for (i = 0; i < 256; i++)
{
    temp = i;

    for (j = 0; j < 8; j++)
    {
        if (temp & 1)
        {
            temp >>= 1;
            temp ^= 0xEDB88320;
        }
        else {temp >>= 1;}
    }
    testcrc[i] = temp;
}

ale wydaje się, że generuje to wartości niezgodne z wartościami, które znalazłem w innych miejscach w Internecie. I mógłby użyć wartości mogę znaleźć w internecie, ale chcę, aby zrozumieć, w jaki sposób zostały one utworzone.

Każda pomoc w wyjaśnieniu tych niesamowicie zagmatwanych liczb byłaby bardzo mile widziana.

Wielomian dla CRC32 to:

x ³² + x ²⁶ + x ²³ + x ²² + x ¹⁶ + x ¹² + x ¹¹ + x ¹⁰ + x ⁸ + x ⁷ + x ⁵ + x ⁴ + x ² + x + 1

• Wikipedia
• Obliczanie CRC

Lub szesnastkowo i binarnie:

0x 01 04 C1 1D B7
1 0000 0100 1100 0001 0001 1101 1011 0111

Najwyższy wyraz (x ³² ) zwykle nie jest jawnie zapisywany, więc zamiast tego można go przedstawić w postaci szesnastkowej, tak jak

0x 04 C1 1D B7

Możesz policzyć jedynki i zera, ale przekonasz się, że pasują do wielomianu, gdzie 1jest bitem 0 (lub pierwszym bitem) i xbitem 1 (lub drugim bitem).

Dlaczego ten wielomian? Ponieważ musi istnieć standard, podany wielomian, a standard został określony przez IEEE 802.3. Niezwykle trudno jest również znaleźć wielomian, który skutecznie wykrywa różne błędy bitowe.

Możesz myśleć o CRC-32 jako o serii „arytmetyki binarnej bez przenoszenia” lub w zasadzie „operacje XOR i przesunięcia”. Technicznie nazywa się to arytmetyką wielomianową.

• CRC primer, rozdział 5

Aby lepiej to zrozumieć, pomyśl o tym mnożeniu:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
= (x^6 + x^4 + x^3
 + x^5 + x^3 + x^2
 + x^3 + x^1 + x^0)
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Jeśli przyjmiemy, że x jest podstawą 2, otrzymamy:

x^7 + x^3 + x^2 + x^1 + x^0

• CRC primer rozdz.5

Czemu? Ponieważ 3x ^ 3 to 11x ^ 11 (ale potrzebujemy tylko 1 lub 0 przed cyfrą), więc przenosimy:

=1x^110 + 1x^101 + 1x^100          + 11x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^100 + 1x^100 + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^101 + 1x^101          + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^110 + 1x^110                   + 1x^11 + 1x^10 + 1x^1 + x^0
=1x^111                            + 1x^11 + 1x^10 + 1x^1 + x^0

Ale matematycy zmienili reguły, tak że jest to mod 2. Więc w zasadzie każdy binarny wielomian mod 2 jest po prostu dodawaniem bez przeniesienia lub XOR. Więc nasze oryginalne równanie wygląda następująco:

=( 1x^110 + 1x^101 + 1x^100 + 11x^11 + 1x^10 + 1x^1 + x^0 ) MOD 2
=( 1x^110 + 1x^101 + 1x^100 +  1x^11 + 1x^10 + 1x^1 + x^0 )
= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 (or that original number we had)

Wiem, że to skok wiary, ale to przekracza moje możliwości jako programisty liniowego. Jeśli jesteś zagorzałym studentem CS lub inżynierem, wzywam to do rozbicia. Wszyscy skorzystają na tej analizie.

Aby więc opracować pełny przykład:

   Original message                : 1101011011
   Polynomial of (W)idth 4         :      10011
   Message after appending W zeros : 11010110110000

Teraz dzielimy powiększoną wiadomość przez Poly, używając arytmetyki CRC. To taki sam podział jak poprzednio:

            1100001010 = Quotient (nobody cares about the quotient)
       _______________
10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
=Poly   10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder = THE CHECKSUM!!!!

Dzielenie daje iloraz, który odrzucamy, i resztę, czyli obliczoną sumę kontrolną. To kończy obliczenia. Zwykle suma kontrolna jest następnie dołączana do wiadomości, a wynik jest przesyłany. W tym przypadku transmisja wyglądałaby następująco: 11010110111110.

• CRC primer, rozdział 7

Jako dzielnika używaj tylko liczby 32-bitowej i jako dywidendy używaj całego strumienia. Wyrzuć iloraz i zachowaj resztę. Dodaj resztę na końcu wiadomości i masz CRC32.

Średnia recenzja faceta:

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER

1. Weź pierwsze 32 bity.
2. Przesuwaj bity
3. Jeśli 32 bity są mniejsze niż DIVISOR, przejdź do kroku 2.
4. XOR 32 bity firmy DIVISOR. Przejdź do kroku 2.

(Należy pamiętać, że strumień musi być podzielny przez 32 bity lub powinien być wypełniony. Na przykład 8-bitowy strumień ANSI musiałby być wypełniony. Również na końcu strumienia podział jest zatrzymywany).

W przypadku IEEE802.3, CRC-32. Pomyśl o całej wiadomości jako o szeregowym strumieniu bitów, dodaj 32 zera na końcu wiadomości. Następnie MUSISZ odwrócić bity KAŻDEGO bajtu wiadomości i uzupełnić jedynkami pierwsze 32 bity. Teraz podziel przez wielomian CRC-32, 0x104C11DB7. Na koniec musisz uzupełnić 1 do 32-bitowej pozostałej części tego podziału, odwrócić bitowo każdy z 4 bajtów pozostałej części. To staje się 32-bitowym CRC, które jest dołączane na końcu wiadomości.

Przyczyną tej dziwnej procedury jest to, że pierwsze implementacje Ethernetu serializowały wiadomość po jednym bajcie i przesyłały najpierw najmniej znaczący bit z każdego bajtu. Szeregowy strumień bitów przeszedł następnie przez szeregowe obliczenia rejestru przesuwnego CRC-32, które zostały po prostu uzupełnione i wysłane przewodem po zakończeniu wiadomości. Powodem uzupełnienia pierwszych 32 bitów wiadomości jest to, że nie otrzymasz zerowego CRC, nawet jeśli wiadomość zawierała same zera.

CRC jest całkiem proste; bierzesz wielomian reprezentowany jako bity i dane i dzielisz go na dane (lub reprezentujesz dane jako wielomian i robisz to samo). Reszta, która mieści się między 0 a wielomianem, to CRC. Twój kod jest trochę trudny do zrozumienia, częściowo dlatego, że jest niekompletny: temp i testcrc nie są zadeklarowane, więc nie jest jasne, co jest indeksowane i ile danych przechodzi przez algorytm.

Sposobem na zrozumienie CRC jest próba obliczenia kilku przy użyciu krótkiego fragmentu danych (około 16 bitów) z krótkim wielomianem - być może 4-bitowym. Jeśli będziesz ćwiczyć w ten sposób, naprawdę zrozumiesz, jak możesz to zakodować.

Jeśli robisz to często, CRC dość wolno oblicza się w oprogramowaniu. Obliczenia sprzętowe są znacznie wydajniejsze i wymagają tylko kilku bramek.

Oprócz artykułów z Wikipedii Cyclic redundancy check and Computation of CRC , dobrym źródłem jest artykuł zatytułowany Reversing CRC - Theory and Practice ^* .

Istnieją zasadniczo trzy podejścia do obliczania CRC: podejście algebraiczne, podejście zorientowane na bit i podejście oparte na tabelach. W Reversing CRC - Theory and Practice ^* , każdemu z tych trzech algorytmów / podejść wyjaśniono w teorii, któremu towarzyszy implementacja CRC32 w języku programowania C.

^{* PDF Link
Reversing CRC - Teoria i praktyka.
Raport publiczny HU Berlin
SAR-PR-2006-05
maja 2006
Autorzy:
Martin Stigge, Henryk Plötz, Wolf Müller, Jens-Peter Redlich}

Spędziłem chwilę, próbując znaleźć odpowiedź na to pytanie, iw końcu opublikowałem dzisiaj tutorial na temat CRC-32: Samouczek skrótu CRC-32 - Społeczność AutoHotkey

W tym przykładzie pokazuję, jak obliczyć skrót CRC-32 dla ciągu ASCII „abc”:

calculate the CRC-32 hash for the ASCII string 'abc':

inputs:
dividend: binary for 'abc': 0b011000010110001001100011 = 0x616263
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7

011000010110001001100011
reverse bits in each byte:
100001100100011011000110
append 32 0 bits:
10000110010001101100011000000000000000000000000000000000
XOR the first 4 bytes with 0xFFFFFFFF:
01111001101110010011100111111111000000000000000000000000

'CRC division':
01111001101110010011100111111111000000000000000000000000
 100000100110000010001110110110111
 ---------------------------------
  111000100010010111111010010010110
  100000100110000010001110110110111
  ---------------------------------
   110000001000101011101001001000010
   100000100110000010001110110110111
   ---------------------------------
    100001011101010011001111111101010
    100000100110000010001110110110111
    ---------------------------------
         111101101000100000100101110100000
         100000100110000010001110110110111
         ---------------------------------
          111010011101000101010110000101110
          100000100110000010001110110110111
          ---------------------------------
           110101110110001110110001100110010
           100000100110000010001110110110111
           ---------------------------------
            101010100000011001111110100001010
            100000100110000010001110110110111
            ---------------------------------
              101000011001101111000001011110100
              100000100110000010001110110110111
              ---------------------------------
                100011111110110100111110100001100
                100000100110000010001110110110111
                ---------------------------------
                    110110001101101100000101110110000
                    100000100110000010001110110110111
                    ---------------------------------
                     101101010111011100010110000001110
                     100000100110000010001110110110111
                     ---------------------------------
                       110111000101111001100011011100100
                       100000100110000010001110110110111
                       ---------------------------------
                        10111100011111011101101101010011

remainder: 0b10111100011111011101101101010011 = 0xBC7DDB53
XOR the remainder with 0xFFFFFFFF:
0b01000011100000100010010010101100 = 0x438224AC
reverse bits:
0b00110101001001000100000111000010 = 0x352441C2

thus the CRC-32 hash for the ASCII string 'abc' is 0x352441C2

Następnie zawsze jest kod Rosetta, który pokazuje kod crc32 zaimplementowany w dziesiątkach języków komputerowych. https://rosettacode.org/wiki/CRC-32 i zawiera linki do wielu wyjaśnień i implementacji.

Aby zredukować crc32 do przyjmowania przypomnienia, musisz:

1. Odwróć bity w każdym bajcie
2. xor pierwsze cztery bajty z 0xFF (ma to na celu uniknięcie błędów w początkowych zerach)
3. Dodaj dopełnienie na końcu (ma to na celu uwzględnienie ostatnich 4 bajtów w hashu)
4. Oblicz przypomnienie
5. Ponownie odwróć bity
6. xor ponownie wynik.

W kodzie to jest:

func CRC32 (file []byte) uint32 {
    for i , v := range(file) {
        file[i] = bits.Reverse8(v)
    }
    for i := 0; i < 4; i++ {
        file[i] ^= 0xFF
    }

    // Add padding
    file = append(file, []byte{0, 0, 0, 0}...)
    newReminder := bits.Reverse32(reminderIEEE(file))

    return newReminder ^ 0xFFFFFFFF
}

gdzie reminderIEEE jest czystym przypomnieniem na GF (2) [x]