Как рассчитывается контрольная сумма CRC32?

103

Возможно, я просто не вижу этого, но CRC32 кажется либо излишне сложным, либо недостаточно объясненным в любом месте, которое я мог найти в Интернете.

Я понимаю, что это остаток от арифметического деления значения сообщения, не основанного на переносе, деленный на полином (генератора), но его реальная реализация ускользает от меня.

Я прочитал «Безболезненное руководство по алгоритмам обнаружения ошибок CRC» и должен сказать, что это было не безболезненно. Это довольно хорошо проходит через теорию, но автор никогда не доходит до простого «вот оно». Он действительно говорит, каковы параметры для стандартного алгоритма CRC32, но он пренебрегает четким изложением того, как к нему добраться.

Меня пугает то, что он говорит: «Вот и все», а затем добавляет: «О, кстати, это можно изменить или начать с другими начальными условиями», и не дает четкого ответа о том, какой окончательный способ вычисления контрольной суммы CRC32 с учетом всех внесенных им изменений.

  • Есть ли более простое объяснение того, как вычисляется CRC32?

Я попытался закодировать на C, как формируется таблица:

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;
}

но похоже, что это генерирует значения, несовместимые со значениями, которые я нашел в других местах в Интернете. Я мог бы использовать значения, которые нашел в Интернете, но я хочу понять, как они были созданы.

Мы будем очень благодарны за любую помощь в прояснении этих невероятно запутанных чисел .

акванар
источник
9
Ваш код для создания таблицы CRC32 кажется правильным. Ваш полином lsbit-first ( обратный ) CRC32 0xEDB88320также можно записать msbit-first ( нормальный ) как 0x04C11DB7. Были ли значения таблицы, которые вы нашли в другом месте, были сгенерированы с использованием того же полинома CRC?
jschmier
1
@jschmier привет, мне кажется, я на шаг позади этого парня, задающего вопросы? stackoverflow.com/questions/62168128/…
bluejayke
Если кому-то еще интересно прочитать «Безболезненное руководство по алгоритмам обнаружения ошибок CRC», ссылка на который приведена выше, этот исходный URL-адрес скрыт, но Google легко нашел несколько копий, включая эту: zlib.net/crc_v3.txt
Стефан

Ответы:

118

Полином для CRC32:

х 32 + х 26 + х 23 + х 22 + х 16 + х 12 + х 11 + х 10 + х 8 + х 7 + х 5 + х 4 + х 2 + х + 1

Или в шестнадцатеричном и двоичном формате:

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

Наивысший член (x 32 ) обычно явно не записывается, поэтому вместо этого он может быть представлен в шестнадцатеричном формате так же, как

0x 04 C1 1D B7

Не стесняйтесь подсчитывать единицы и нули, но вы обнаружите, что они совпадают с полиномом, где 1бит 0 (или первый бит) иx бит 1 (или второй бит).

Почему этот многочлен? Потому что должен быть стандарт заданного многочлена, а стандарт был установлен IEEE 802.3. Также чрезвычайно сложно найти многочлен, который эффективно обнаруживает различные битовые ошибки.

Вы можете думать о CRC-32 как о серии «двоичной арифметики без переносов» или, по сути, «операций XOR и сдвига». Технически это называется полиномиальной арифметикой.

Чтобы лучше понять это, представьте себе это умножение:

(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

Если мы предположим, что x является основанием 2, мы получим:

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

Зачем? Поскольку 3x ^ 3 равно 11x ^ 11 (но нам нужна только 1 или 0 предварительная цифра), мы переносим:

=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

Но математики изменили правила так, что это mod 2. Таким образом, в основном любой двоичный полином по модулю 2 - это просто сложение без переноса или XOR. Итак, наше исходное уравнение выглядит так:

=( 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)

Я знаю, что это прыжок веры, но это выходит за рамки моих возможностей как линейного программиста. Если вы заядлый студент или инженер в области компьютерных наук, я призываю вас разбить это на части. Этот анализ принесет пользу всем.

Итак, чтобы проработать полный пример:

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

Теперь мы разделим расширенное сообщение на Poly, используя арифметику CRC. Это то же деление, что и раньше:

            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!!!!

Деление дает частное, которое мы отбрасываем, и остаток, который является вычисленной контрольной суммой. На этом расчет заканчивается. Обычно контрольная сумма затем добавляется к сообщению и передается результат. В этом случае передача будет: 11010110111110.

Используйте только 32-битное число в качестве делителя и используйте весь поток в качестве дивиденда. Выбросьте частное и оставьте остаток. Добавьте остаток в конец сообщения, и у вас будет CRC32.

Средний отзыв парня:

         QUOTIENT
        ----------
DIVISOR ) DIVIDEND
                 = REMAINDER
  1. Возьмите первые 32 бита.
  2. Биты сдвига
  3. Если 32 бита меньше DIVISOR, перейдите к шагу 2.
  4. XOR 32 бита от DIVISOR. Переходите к шагу 2.

(Обратите внимание, что поток должен быть разделен на 32 бита или должен быть дополнен. Например, 8-битный поток ANSI должен быть дополнен. Также в конце потока деление останавливается.)

Ilkkachu
источник
13
+1 за «Обзор среднего парня» в конце - может быть, подумайте о том, чтобы переместить это прямо в начало - своего рода TL; DR: P
aaronsnoswell
4
@abstractnature Помните, что мы делим многочлены, а не только двоичные числа. Мы не можем выполнять «нормальное» вычитание, потому что мы не можем «одолжить» $ x ^ n $ у $ x ^ {n + 1} $; это разные вещи. Кроме того, поскольку биты только 0 или 1, что вообще будет -1? На самом деле, мы работаем в кольце многочленов с коэффициентами в поле $ Z / 2Z $, которое имеет только два элемента, 0 и 1, и где $ 1 + 1 = 0 $. Помещая cofficients в поле, тогда полиномы образуют так называемую евклидову область, которая в основном позволяет четко определить то, что мы пытаемся сделать.
calavicci
6
Просто чтобы уточнить, фактический полином равен 100000100110000010001110110110111 = 0x104C11DB7. MSB является неявным, но его все же следует учитывать при реализации. Поскольку он всегда будет установлен, потому что многочлен должен быть длиной 33 бита (так что остаток может быть длиной 32 бита), некоторые люди опускают MSB.
Felipe T.
2
x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 ... If we assume x is base 2 then we get: x^7 + x^3 + x^2 + x^1 + x^0. Математика работает не так. Коэффициенты полинома равны mod (2) или GF (2), x остаются в покое, в результате получается x ^ 6 + x ^ 5 + x ^ 4 + x ^ 3 + x ^ 2 + x ^ 1 + x ^ 0 (поскольку 3 mod (2) = 1). Tack the remainder on the end of your message- технически остаток вычитается из 0 битов, которые были добавлены к сообщению, но поскольку это математика mod (2), и сложение, и вычитание такие же, как XOR, а нулевые биты, XOR'ed с остатком, такие же как остаток.
rcgldr
2
@MarcusJ - Why did you append four 0s though?программные алгоритмы вычисления crc эффективно добавляют нули, хотя это не очевидно. Если вы показываете вычисление CRC с использованием длинного деления, то для правильного отображения примера деления необходимо добавить нули.
rcgldr
11

Для IEEE802.3, CRC-32. Думайте обо всем сообщении как о последовательном потоке битов, добавьте 32 нуля в конец сообщения. Затем вы ДОЛЖНЫ поменять местами биты КАЖДОГО байта сообщения и добавить 1 к первым 32 битам. Теперь разделите на полином CRC-32, 0x104C11DB7. Наконец, вы должны добавить 1 к 32-битному остатку от этого деления, перевернув каждый из 4 байтов остатка. Это становится 32-битной CRC, которая добавляется в конец сообщения.

Причина этой странной процедуры в том, что первые реализации Ethernet сериализовали бы сообщение по одному байту за раз и сначала передавали младший бит каждого байта. Затем последовательный поток битов прошел через последовательное вычисление регистра сдвига CRC-32, которое было просто дополнено и отправлено по сети после завершения сообщения. Причина дополнения первых 32 бита сообщения заключается в том, чтобы вы не получили CRC полностью нулевым, даже если сообщение было полностью нулями.

Павел Бобрек
источник
2
На данный момент это лучший ответ, хотя я бы заменил «побитовое реверсирование каждого из 4 байтов» на «побитовое реверсирование 4 байтов, рассматривая их как одно целое», например, «abcdefgh ijklmnop qrstuvwx yzABCDEF» на «FEDCBAzy xwvutsrq. ponmlkji hgfedcba '. См. Также: Руководство по хешированию CRC-32 - Сообщество AutoHotkey .
vafylec 09
1
привет, какое точное "сообщение" вы делаете наоборот? stackoverflow.com/questions/62168128/…
bluejayke
10

CRC довольно прост; вы берете многочлен, представленный как биты и данные, и делите многочлен на данные (или вы представляете данные как многочлен и делаете то же самое). Остаток, который находится между 0 и полиномом, является CRC. Ваш код немного сложен для понимания, отчасти потому, что он неполный: temp и testcrc не объявлены, поэтому неясно, что индексируется и сколько данных проходит через алгоритм.

Способ понять CRC - это попытаться вычислить несколько, используя короткий фрагмент данных (16 бит или около того) с коротким полиномом - возможно, 4 бита. Если вы попрактикуетесь таким образом, вы действительно поймете, как можно его кодировать.

Если вы делаете это часто, CRC довольно медленно вычисляется программным обеспечением. Аппаратные вычисления намного более эффективны и требуют всего несколько вентилей.

Вихрь
источник
1
Для CRC32 или CRC32b получаем ли мы значение коллизии хэшей для двух разных строк, получаем ли мы одинаковый CRC
indianwebdevil
1
привет, я немного запутался, что вы подразумеваете под "разделить многочлены на данные"? stackoverflow.com/questions/62168128/… что такое X в полиноме, представленном? Могу ли я использовать дополнительные байты из чанка?
bluejayke
7

В дополнение к статьям « Проверка циклическим избыточным кодом» и « Вычисление CRC» в Википедии , я нашел хорошим справочником документ под названием Reversing CRC - Theory and Practice * .

По сути, существует три подхода к вычислению CRC: алгебраический подход, бит-ориентированный подход и подход, управляемый таблицами. В обращении CRC - теория и практика * каждый из этих трех алгоритмов / подходов объясняется теоретически и сопровождается в ПРИЛОЖЕНИИ реализацией CRC32 на языке программирования C.

* PDF Link
Reversing CRC - Теория и практика.
Публичный отчет Берлинского университета
SAR-PR-2006-05,
май 2006 г.
Авторы:
Мартин Стигге, Хенрик Плётц, Вольф Мюллер, Йенс-Петер Редлих

jschmier
источник
привет, можешь немного уточнить?
bluejayke
7

Я потратил некоторое время, пытаясь найти ответ на этот вопрос, и, наконец, сегодня опубликовал учебное пособие по CRC-32: руководство по хешированию CRC-32 - AutoHotkey Community

В этом примере я демонстрирую, как вычислить хэш CRC-32 для строки 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
вафилек
источник
1
Если вам нужна большая скорость, то в 2006 году некоторые инженеры Intel разработали метод, использующий обычно 4 или 8 байтов ширины шины данных машины одновременно. Академическая статья: static.aminer.org/pdf/PDF/000/432/446/… Проект на Sourceforge: sourceforge.net/projects/slicing-by-8 Общая страница crc
Алан Кори
1
Привет, спасибо, отлично выглядит, но как именно получить значение полинома? что именно представляет X? И когда он говорит x ^ 32, это x в степени 32 или побитовый оператор ^? stackoverflow.com/questions/62168128/…
bluejayke
2

Затем всегда есть Rosetta Code, который показывает, что crc32 реализован на десятках компьютерных языков. https://rosettacode.org/wiki/CRC-32 и содержит ссылки на множество объяснений и реализаций.

Дон яркий
источник
1
можешь немного уточнить? stackoverflow.com/questions/62168128/…
bluejayke
1

Чтобы уменьшить crc32 до приема напоминаний, вам необходимо:

  1. Инвертировать биты в каждом байте
  2. xor первые четыре байта с 0xFF (чтобы избежать ошибок в начальных 0)
  3. Добавьте заполнение в конце (чтобы последние 4 байта участвовали в хэше)
  4. Вычислить напоминание
  5. Снова переверните биты
  6. xor результат снова.

В коде это:


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
}

где напоминаниеIEEE - чистое напоминание о GF (2) [x]

Габриэль Фюрстенхайм
источник
1
У меня есть небольшие проблемы с пониманием этого? stackoverflow.com/questions/62168128/…
bluejayke
1
эй @bluejayke, проверьте эту библиотеку github.com/furstenheim/sparse_crc32/blob/master/main.go, она реализует crc32 для разреженных файлов, вы можете увидеть здесь мельчайшие подробности вычислений. Он не оптимизирован, поэтому за ним легче следить, чем за обычными реализациями. Может случиться так, что вы не понимаете часть GF (2) [x]. Обычно x ^ 3 + x означает 1010, x ^ 4 + x + 1 означает 10011. Затем вам нужно выполнить деление, например x ^ 3 + x - это x * (x ^ 2 + 1). поэтому напоминание о x ^ 3 + x над x равно 0, но над x ^ 2 будет x ^ 2 * x + x, то есть напоминанием будет x.
Габриэль Фюрстенхайм,
1
@bluejayke и напоминание IEEE означает напоминание против хорошо известного полинома, полинома IEEE
Габриэль Фюрстенхайм,
привет еще раз, спасибо за ваш ответ. Я просто пытаюсь понять (для целей javascript), что представляет собой "x" в полиноме. "X" - это какое-то кодовое слово для чего-то, чего мне здесь не хватает? Здесь много терминов, которые меня смущают, я никогда раньше не слышал о CRC32, и даже после поиска я не смог найти его объяснения. Для PNG, например, он говорит, что мне нужно взять «CRC для каждого фрагмента», означает ли это «для всех данных в фрагменте»? Но как мне «подключить» его к полиному? Что означает «х»? Также, когда он говорит, что x ^ 32, это похоже на Math.pow (x, 32) или побитовое ^
bluejayke
1
Привет @bluejayke, x - это абстракция, упрощающая вычисления. Не предполагается, что он будет чем-либо заменен. x ^ 2 Я имею в виду x * x, как формальное умножение. Здесь chrisballance.com/wp-content/uploads/2015/10/CRC-Primer.html вы можете найти хорошее объяснение этого разделения. Я попытался со своим ответом заполнить пробел между делением (в этой ссылке) и фактическим вычислением
Габриэль Фюрстенхайм