Чек-диджит

Чек-диджит (от англ. check digit, «контрольная цифра») — это цифра (или, реже, буква или символ), добавляемая к строке цифр (например, к номеру банковской карты, коду товара, серийному номеру или идентификационному номеру) для обнаружения ошибок, возникающих при ручном вводе, передаче или обработке данных. Чек-диджит вычисляется на основе остальных цифр номера по определённому алгоритму и служит средством верификации целостности и корректности всего идентификатора.

Назначение и принцип работы

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

Принцип работы заключается в том, что алгоритм, применяемый к цифрам номера (исключая саму контрольную цифру), даёт некий результат. Этот результат сравнивается с последней (или специально отведённой) цифрой. Если они совпадают, номер считается корректным. Вероятность того, что случайная ошибка приведёт к совпадению, крайне мала (обычно не превышает 1–10 % в зависимости от алгоритма).

История

Идея использования контрольных символов для обнаружения ошибок возникла в середине XX века с развитием вычислительной техники и автоматизированных систем обработки данных. Одним из первых массово применяемых алгоритмов стал алгоритм Лу́на (Luhn algorithm), разработанный в 1954 году учёным IBM Хансом Петером Луном. Изначально он предназначался для проверки номеров в механических системах, но позже лёг в основу проверки номеров кредитных карт (включая Visa, Mastercard, American Express) и некоторых других идентификаторов.

С распространением штрихкодов (UPC, EAN) и международных стандартов (ISBN, ISSN) чек-диджиты стали обязательным элементом кодирования. В России и странах бывшего СССР широкое распространение получили алгоритмы для ИНН, СНИЛС, ОГРН и других государственных регистрационных номеров.

Основные алгоритмы и их применение

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

Алгоритм Луна (Luhn algorithm)

Самый известный и широко распространённый алгоритм. Используется для проверки номеров банковских карт (PAN), номеров IMEI, некоторых национальных идентификаторов.

Принцип работы:

1. Цифры номера (справа налево, начиная с последней, которая является чек-диджитом) последовательно удваиваются через одну.
2. Если при удвоении получается число больше 9, его цифры складываются (например, 14 → 1+4=5).
3. Все полученные значения (включая неудвоенные цифры) суммируются.
4. Если сумма делится на 10 без остатка, номер корректен.

Модуль 10 (Mod 10) и Модуль 11 (Mod 11)

Базовые алгоритмы, используемые в различных системах (например, в некоторых штрихкодах, номерах паспортов, ИНН).

• Mod 10: Каждая цифра номера умножается на определённый весовой коэффициент (часто повторяющийся ряд, например, 1, 3, 1, 3... или 7, 1, 3, 7...). Произведения суммируются. Чек-диджит вычисляется как (10 — (сумма mod 10)) mod 10. Если сумма делится на 10, чек-диджит равен 0.
• Mod 11: Аналогично Mod 10, но делитель — 11. Чек-диджит может принимать значения от 0 до 9, а в некоторых системах — также букву «X» (римская 10). Используется в номерах ISBN-10, СНИЛС, ОГРН.

Алгоритм Верхоффа (Verhoeff algorithm)

Более сложный и надёжный алгоритм, способный обнаруживать практически все типичные ошибки ввода (одиночные, перестановки соседних цифр, двойные ошибки). Основан на теории групп диэдра. Применяется в некоторых банковских и медицинских системах, но менее распространён, чем алгоритм Луна, из-за большей вычислительной сложности.

CRC (Cyclic Redundancy Check)

Хотя CRC обычно используется для проверки целостности блоков данных в компьютерных сетях и цифровых запоминающих устройствах, его частным случаем является контрольная цифра, вычисляемая как остаток от деления полинома. В некоторых системах (например, в номерах SIM-карт) применяются модифицированные версии CRC.

Примеры использования в России и мире

Банковские карты (PAN)

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

Международный стандартный книжный номер (ISBN)

• ISBN-10 (до 2007 года): Чек-диджит — последняя цифра. Вычисляется по модулю 11. Контрольное число может быть от 0 до 10, при значении 10 используется буква «X».
• ISBN-13 (с 2007 года): Чек-диджит вычисляется по модулю 10 с весовыми коэффициентами 1 и 3 (аналогично EAN-13).

Идентификационный номер налогоплательщика (ИНН) в России

ИНН для физических лиц состоит из 12 цифр, для юридических — из 10. Последние две или одна цифра соответственно являются чек-диджитами, вычисленными по алгоритму Mod 11 (с весовыми коэффициентами). Это позволяет проверять корректность ИНН при подаче налоговой отчётности или регистрации.

Страховой номер индивидуального лицевого счёта (СНИЛС) в России

Номер СНИЛС (11 цифр) содержит контрольную сумму, вычисляемую по алгоритму Mod 11 (с весовыми коэффициентами от 1 до 9). Контрольное число — последние две цифры номера. Алгоритм позволяет обнаруживать ошибки ввода, но не обеспечивает защиту от подделки.

ОГРН (Основной государственный регистрационный номер) в России

ОГРН для юридических лиц состоит из 13 цифр. Последняя (13-я) цифра — чек-диджит, вычисляемый как остаток от деления на 11 (или на 10, если остаток равен 10) числа, образованного первыми 12 цифрами.

Номера IMEI (International Mobile Equipment Identity)

Уникальный 15-значный номер мобильного устройства содержит чек-диджит, вычисляемый по алгоритму Луна. Последняя цифра IMEI является контрольной.

Штрихкоды (EAN-13, UPC-A)

В штрихкодах EAN-13 (13 цифр) последняя цифра — чек-диджит, вычисляемый по модулю 10 с весовыми коэффициентами 1 и 3. Это стандартный метод для товарных кодов.

Ограничения и критика

Чек-диджит не является средством криптографической защиты или аутентификации. Он предназначен исключительно для обнаружения случайных ошибок ввода (опечаток, перестановок). Злоумышленник, знающий алгоритм, может подобрать корректный номер, если ему известны остальные цифры. Например, подделка номера банковской карты с использованием алгоритма Луна не представляет сложности.

Кроме того, алгоритмы с низкой надёжностью (например, простой Mod 10) могут пропускать некоторые типы ошибок (например, двойные перестановки). Для критически важных систем (например, в авиационной или медицинской сфере) применяются более сложные алгоритмы, такие как Verhoeff или Damm.

Интересные факты

• Алгоритм Луна был запатентован в 1960 году, но патент давно истёк, и алгоритм находится в общественном достоянии.
• В некоторых системах чек-диджит может быть не цифрой, а буквой (например, в номерах некоторых паспортов или в системе ISBN-10).
• Существуют алгоритмы, способные не только обнаруживать, но и исправлять одиночные ошибки (например, коды Рида-Соломона), но они требуют большего количества контрольных символов.

Источники

1. Luhn, H. P. (1954). «Computer for Verifying Numbers». U.S. Patent 2,950,048.
2. ISO/IEC 7812-1:2017 «Identification cards — Identification of issuers — Part 1: Numbering system».
3. Федеральный закон от 08.08.2001 № 129-ФЗ «О государственной регистрации юридических лиц и индивидуальных предпринимателей» (приложение о порядке формирования ОГРН).
4. Приказ Минтруда России от 22.04.2020 № 211н «Об утверждении порядка подтверждения регистрации в системе индивидуального (персонифицированного) учета» (описание структуры СНИЛС).
5. Verhoeff, J. (1969). «Error Detecting Decimal Codes». Mathematical Centre Tracts, Amsterdam.