CRC-64-ECMA-182

CRC-64-ECMA-182 — это 64-битный циклический избыточный код (CRC), определённый стандартом Европейской ассоциации производителей компьютеров (ECMA) под номером 182. Он представляет собой алгоритм вычисления контрольной суммы, предназначенный для обнаружения случайных или преднамеренных изменений в блоках данных, и широко применяется в системах хранения и передачи информации, где требуется высокая степень надёжности.

История и стандартизация

Разработка алгоритмов CRC началась в 1960-х годах, и к 1980-м годам 32-битные версии (CRC-32) стали стандартом для многих протоколов, таких как Ethernet. Однако с ростом объёмов хранимых данных и увеличением требований к целостности информации возникла потребность в более длинных контрольных суммах, способных обнаруживать большее количество ошибок с меньшей вероятностью коллизий (совпадения сумм для разных данных).

В 1992 году ECMA опубликовала стандарт ECMA-182, который описывал формат записи данных на оптические диски DVD (Digital Versatile Disc). Для обеспечения целостности информации на таких носителях был предложен 64-битный полиномиальный код. Позднее этот алгоритм, известный как CRC-64-ECMA-182, был принят и в других областях, в частности, в файловых системах и архиваторах.

Алгоритм

CRC-64-ECMA-182 базируется на вычислении остатка от деления двоичного многочлена, представляющего входные данные, на фиксированный порождающий многочлен (полином). Операции выполняются в поле GF(2) (арифметика по модулю 2) без переносов.

Порождающий многочлен

Полином CRC-64-ECMA-182 имеет вид:

`` 0x42F0E1EBA9EA3693 ``

В двоичной записи (64 бита) он выглядит как:

`` 0100 0010 1111 0000 1110 0001 1110 1011 1010 1001 1110 1010 0011 0110 1001 0011 ``

Старший бит (64-й) опущен, так как он всегда равен 1 для полиномов CRC. В явном виде многочлен можно записать как:

x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 + x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 + x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 + x^7 + x^4 + x^1 + 1

Процесс вычисления

1. Инициализация: Регистр CRC (64-битное значение) устанавливается в начальное значение, которое для ECMA-182 равно 0x0000000000000000.
2. Обработка данных: Каждый байт входных данных (или бит) последовательно обрабатывается. Для каждого байта выполняется операция XOR (исключающее ИЛИ) с текущим содержимым регистра, после чего регистр сдвигается влево (или вправо, в зависимости от реализации) на один бит. Если выдвинутый бит равен 1, то выполняется XOR с полиномом.
3. Финализация: После обработки всех данных может выполняться XOR с финальным значением (для ECMA-182 — 0x0000000000000000, то есть не выполняется). Полученное 64-битное значение является контрольной суммой.

Табличный метод

Для ускорения вычислений на практике используется табличный метод. Предварительно рассчитывается таблица из 256 значений (по одному на каждый возможный байт). В процессе вычисления каждый байт данных обрабатывается путём XOR с текущим значением CRC, затем старший байт результата используется как индекс в таблице, и выполняется сдвиг на 8 бит с XOR с табличным значением. Это позволяет обрабатывать по одному байту за такт, что значительно быстрее побитового подхода.

Характеристики

CRC-64-ECMA-182 обладает следующими свойствами:

• Длина контрольной суммы: 64 бита (8 байт).
• Вероятность коллизии: Для случайных данных вероятность того, что два разных блока данных дадут одинаковую контрольную сумму, составляет приблизительно 2^(-64), что крайне мало.
• Обнаружение ошибок: Алгоритм гарантированно обнаруживает:
• Все одиночные битовые ошибки.
• Все двойные битовые ошибки (при условии, что порождающий многочлен является примитивным).
• Любое нечётное количество ошибок (если многочлен содержит множитель (x+1)).
• Все пакетные ошибки длиной до 64 бит.
• Большинство пакетных ошибок большей длины.
• Скорость вычисления: При табличной реализации скорость может достигать нескольких гигабайт в секунду на современных процессорах, что делает его пригодным для высокопроизводительных систем.

Применение

CRC-64-ECMA-182 используется в нескольких ключевых областях, где требуется высокая степень защиты данных:

Файловые системы

• ZFS (Zettabyte File System): Эта файловая система, разработанная компанией Sun Microsystems, использует CRC-64-ECMA-182 для проверки целостности данных (data integrity) на уровне блоков. Каждый блок данных (обычно 128 КБ) сопровождается своей контрольной суммой, что позволяет обнаруживать «тихое» повреждение данных (bit rot) и ошибки чтения/записи.
• Btrfs (B-tree File System): Аналогично ZFS, Btrfs использует CRC-64-ECMA-182 для проверки целостности данных и метаданных, что обеспечивает устойчивость к скрытым повреждениям.

Архиваторы и сжатие данных

• xz: Популярный архиватор, использующий алгоритм сжатия LZMA2, применяет CRC-64-ECMA-182 для проверки целостности сжатых данных. Это позволяет пользователям быть уверенными, что архив не был повреждён при передаче или хранении.
• 7-Zip: В некоторых режимах работы (например, при создании архивов в формате 7z) может использоваться CRC-64-ECMA-182 для проверки целостности.

Оптические носители

• DVD: Стандарт ECMA-182 изначально был разработан для DVD, и CRC-64-ECMA-182 используется для проверки целостности данных на дисках, хотя в современных проигрывателях и ридерах эта функция может быть реализована на аппаратном уровне.

Другие применения

• Проверка целостности в сетевых протоколах: В некоторых высоконадёжных протоколах передачи данных (например, в промышленных или научных) может использоваться CRC-64-ECMA-182 для обеспечения целостности пакетов.
• Хеширование в базах данных: В некоторых системах управления базами данных (СУБД) CRC-64-ECMA-182 может применяться для быстрой проверки целостности страниц данных или индексов.

Сравнение с другими CRC

CRC-64-ECMA-182 обеспечивает значительно более низкую вероятность коллизий по сравнению с CRC-32 (2^(-64) против 2^(-32)), что делает его предпочтительным для систем, где критична целостность данных, но при этом он требует больше вычислительных ресурсов (хотя на современных процессорах разница незначительна).

Критика и ограничения

Несмотря на высокую надёжность, CRC-64-ECMA-182 не является криптографической хеш-функцией. Он не защищает от преднамеренной подделки данных: злоумышленник, зная алгоритм, может подобрать данные, которые дадут ту же контрольную сумму. Для защиты от атак (например, от подмены файлов) используются криптографические хеши, такие как SHA-256 или SHA-3.

Кроме того, хотя CRC-64-ECMA-182 и обнаруживает большинство ошибок, он не является универсальным: существуют специфические паттерны ошибок, которые он может пропустить (например, некоторые пакетные ошибки длиной более 64 бит). Однако на практике вероятность таких событий крайне мала.

Источники

• ECMA-182: Data Interchange on 120 mm and 80 mm Optical Disk Cartridges using +RW Format (1992).
• Спецификация файловой системы ZFS (OpenZFS Documentation).
• Документация архиватора xz (Tukaani Project).
• Ross N. Williams, "A Painless Guide to CRC Error Detection Algorithms" (1993).