CRC: контрольная сумма как остаток от деления

Если ты разделишь сообщение на образующее число столбиком с ^ вместо вычитания, объяснишь, почему перестановку байтов сумма пропускает, а CRC нет, и скажешь, чем CRC отличается от криптографического хеша, - листай до «Теперь сам».

Как думаешь, заметит ли сумма переставленные байты

К сообщению приписывают контрольную сумму: все байты складывают и берут младший байт результата. Получатель считает то же самое и сравнивает. При передаче два соседних байта поменялись местами.

Прежде чем читать дальше, ответь себе: заметит ли получатель? Не заметит: от перестановки слагаемых сумма не меняется. Не заметит он и другого: один байт стал на единицу больше, соседний - на единицу меньше. Нужна проверка, которой важно, где стоит каждый бит.

На что это похоже

Проверка умножения «по девятке» из школы: остаток от деления числа на 9. Он считается быстро, и если в длинном числе исказилась одна цифра, остаток почти наверняка изменится. Остаток от деления - сжатая сводка обо всём числе: в него вносит вклад каждая цифра, и вклад зависит от её места.

У девятки есть слабость: вес каждого разряда по модулю 9 равен единице, поэтому перестановку цифр она не замечает - ровно как сумма байтов. Делитель надо выбирать так, чтобы веса разрядов были разными. И хочется, чтобы деление было дешёвым - дешевле настоящего, с его вычитаниями и заёмами.

Механизм: деление без переносов

В первом уроке раздела сказано: у ^ нет переноса. Возьмём арифметику, в которой сложение - это ^. Вычитание в ней - тоже ^: прибавить число дважды значит вернуться к исходному. Умножение на степень двойки - по-прежнему сдвиг. Деление столбиком в такой арифметике устроено как обычное двоичное из прошлой главы, только вместо «вычесть делитель, если поместился» стоит «сделать ^ с делителем, если старший бит - единица».

Делитель называют образующим числом. Пусть оно 1011, четыре бита; остаток тогда - три бита. К сообщению 1101 справа приписывают три нуля - место под остаток - и делят:

1101 000
1011              старший бит единица: ^ с образующим, сдвинутым под него
----
0110 000
 101 1
 ----
 011 100
  10 11
  -----
  01 010
   1 011
   -----
   0 001          остаток 001

Отправитель передаёт 1101 001: сообщение и остаток вместо нулей. Получатель делит всё целиком и должен получить ноль: остаток, приписанный к сообщению, сокращает сам себя.

Почему ловится одиночная ошибка. Искажение одного бита - это ^ сообщения с числом вида 100…0. Остаток при этом изменится на остаток от деления 100…0 на образующее число. Он не ноль, если у образующего числа хотя бы две единицы: при умножении без переносов старшая и младшая единицы множителя дают две разные единицы в произведении, так что число с одной единицей на него не делится. Похожим доводом ловится любая пачка ошибок - несколько искажённых битов подряд - не длиннее остатка: сама пачка короче образующего числа, а сдвиг её не спасает, если младший бит образующего числа - единица. У всех принятых образующих чисел он единица; придумывать их не нужно, их берут из стандартов.

Если старший бит остатка ноль, шаг деления пропускается: остаток просто сдвигается к следующему разряду. В программе деление идёт по байтам: очередной байт подмешивается к текущему остатку, затем восемь раз «сдвиг и, если выдвинулась единица, ^ с образующим числом». Дописывать нули не нужно: восемь сдвигов после последнего байта и есть место под остаток.

Правило

CRC сообщения - остаток от деления сообщения, дополненного нулями, на образующее число в арифметике без переносов. Шаг на бит: сдвинуть остаток; если выдвинулась единица - сделать ^ с образующим числом. Сообщение вместе со своим CRC даёт остаток ноль. CRC длиной r битов ловит любую одиночную ошибку и любую пачку ошибок длиной до r. CRC линеен: при нулевом начальном значении crc(a ^ b) = crc(a) ^ crc(b) для сообщений одной длины, - поэтому от намеренных изменений он не защищает.

Разбор: CRC-8 против суммы байтов

def crc8(dannye):
    crc = 0
    for bajt in dannye:
        crc = crc ^ bajt
        for i in range(8):
            if crc & 0x80:
                crc = (crc << 1 ^ 0x07) & 0xFF
            else:
                crc = crc << 1
    return crc

def summa(dannye):
    s = 0
    for bajt in dannye:
        s = s + bajt & 0xFF
    return s

soobshchenie = [49, 50, 51, 52, 53, 54, 55, 56, 57]
perestavleno = [50, 49, 51, 52, 53, 54, 55, 56, 57]
plyus_minus = [48, 51, 51, 52, 53, 54, 55, 56, 57]
print(hex(crc8(soobshchenie)), hex(summa(soobshchenie)))
print(hex(crc8(perestavleno)), hex(summa(perestavleno)))
print(hex(crc8(plyus_minus)), hex(summa(plyus_minus)))
print(hex(crc8(soobshchenie + [crc8(soobshchenie)])))

0xf4 0xdd
0x4a 0xdd
0x9e 0xdd
0x0

Образующее число здесь - 0x107, девять битов; старшая единица в программе не хранится - это тот бит, который «выдвинулся», - остаётся 0x07. Сообщение - коды цифр от 1 до 9; для этой строки принято публиковать эталонный ответ, и у CRC-8 с таким числом он 0xF4.

Вторая строка - два первых байта переставлены. Третья - первый уменьшен на единицу, второй увеличен. Сумма во всех трёх случаях 0xDD; CRC все три раза разный. Последняя строка - проверка получателя: сообщение с приписанным CRC даёт ноль.

Если исказить по очереди каждый из 72 битов сообщения, CRC изменится все 72 раза - это гарантия из механизма, а не удача. Для перестановки байтов такой гарантии у восьмибитного остатка нет: два соседних байта - пачка до 16 битов. Перебор всех пар показывает, что CRC-8 не замечает перестановку, когда a ^ b = 0xFD, - одну пару из 255, - а искажение «плюс один, минус один» в соседних байтах пропускает в шести случаях из ста: среди таких искажений есть само образующее число 0x0107. CRC-32 те же искажения ловит все - они короче 32 битов.

Разбор: таблица, CRC-32 и чего от CRC ждать нельзя

Восемь кругов на байт - медленно. Заметим, что они зависят только от байта, с которого начались. Значит, для всех 256 значений их можно выполнить заранее:

tablica = []
for b in range(256):
    crc = b
    for i in range(8):
        if crc & 0x80:
            crc = (crc << 1 ^ 0x07) & 0xFF
        else:
            crc = crc << 1
    tablica.append(crc)

def crc8_tablicej(dannye):
    crc = 0
    for bajt in dannye:
        crc = tablica[crc ^ bajt]
    return crc

print(hex(crc8_tablicej([49, 50, 51, 52, 53, 54, 55, 56, 57])))

0xf4

На сообщении из 400 случайных байтов побитовый вариант стоит 10 403 шага, табличный цикл - 801; построение таблицы - 6 913 шагов, один раз.

В архивах, сетевых кадрах и картинках стоит CRC-32. Он считает младшим битом вперёд - сдвиг вправо, а образующее число 0x04C11DB7 записано с развёрнутым порядком битов, 0xEDB88320:

def crc32(dannye):
    crc = 0xFFFFFFFF
    for bajt in dannye:
        crc = crc ^ bajt
        for i in range(8):
            if crc & 1:
                crc = crc >> 1 ^ 0xEDB88320
            else:
                crc = crc >> 1
    return crc ^ 0xFFFFFFFF

print(hex(crc32([49, 50, 51, 52, 53, 54, 55, 56, 57])))

0xcbf43926

Это эталонное значение CRC-32 для строки «123456789» - то же, что вернёт zlib.crc32(b"123456789") в Python. Начальное значение из одних единиц нужно, чтобы нули в начале сообщения меняли результат: у показанной crc8 начало нулевое, и crc8([0, 0, 5]) равно crc8([5]). Финальный ^ со всеми единицами закрывает похожую дыру с нулями в конце.

Теперь граница. CRC придуман против случайных помех, и против них его гарантии точны. Против человека он бессилен, и причина - в линейности:

a = [1, 2, 3]
b = [7, 0, 9]
c = [1 ^ 7, 2 ^ 0, 3 ^ 9]
print(crc8(a) ^ crc8(b) == crc8(c))

True

CRC от ^ двух сообщений одной длины равен ^ их CRC; при ненулевом начальном значении, как у CRC-32, к этому добавляется постоянная поправка, и суть та же. Значит, зная, какие биты сообщения ты меняешь, можно заранее вычислить, как изменится контрольная сумма, и поправить её - не зная самого сообщения. Для защиты от подделки нужны криптографические хеши и подписи из раздела про числа; CRC отвечает только на вопрос «не испортилось ли по дороге».

Что ломается без этого

Первое: CRC как защита от подмены. Обновление прошивки, проверяемое только по CRC, принимает любой файл, к которому приписана верная сумма. Нужна подпись.

Второе: CRC как ключ в хеш-таблице для чужих данных. Тот, кто присылает данные, может подобрать сколько угодно строк с одинаковым CRC, и таблица выродится в список. Для внутренних данных CRC как хеш-функция вполне хорош.

Третье: варианты одного имени. «CRC-32» - это не один алгоритм: различаются образующее число, начальное значение, порядок битов и финальный ^. Два устройства с разными вариантами никогда не сойдутся. Сверяться нужно по эталонной строке «123456789».

Четвёртое: короткий CRC на длинном сообщении. Восемь битов - это 256 возможных остатков. Случайное искажение длинного блока остаётся незамеченным в одном случае из 256. У CRC-32 - в одном из четырёх миллиардов.

Зачем это в работе

CRC-32 стоит в каждом кадре Ethernet, в каждом файле ZIP и gzip, в каждом блоке PNG. Когда архив «повреждён», это сообщение о несовпавшем CRC. Файловые системы ext4 и btrfs проверяют им свои служебные блоки, и для их варианта - CRC-32C - в процессорах есть отдельная команда.

В шинах автомобилей и в USB стоят короткие CRC на 5-16 битов: кадры там маленькие, а помехи - как раз пачками.

И знакомство из раздела про строки: полиномиальный хеш в алгоритме Рабина-Карпа - тоже остаток от деления строки, прочитанной как число. Разница в арифметике: там обычное деление по простому модулю, здесь - деление без переносов, которое в железе собирается из сдвигового регистра и нескольких элементов ^.

Теперь сам

1. Раздели 1010 000 на 1011 без переносов. Какой остаток припишут к сообщению 1010?
2. Получатель принял 1101 011. Образующее число 1011. Есть ли ошибка?
3. Сообщение из трёх байтов 10, 20, 30. Назови искажение двух байтов, которое сумма не заметит.
4. Почему образующее число 1000 - с одной единицей - бесполезно?
5. CRC-16 защищает блок в 4096 байтов. Какова доля случайных искажений, которые он пропустит, и какие пропустить не может?