Алгоритм вычисления контрольной цифры

Алгоритм вычисления контрольной цифры — это формализованная процедура, предназначенная для проверки целостности данных и выявления ошибок при вводе, передаче или хранении цифровых последовательностей (номеров банковских карт, паспортов, ИНН, штрихкодов, серийных номеров и т. д.). Контрольная цифра (контрольная сумма, чек-сумма) представляет собой один или несколько символов, вычисляемых по определённому правилу на основе остальных цифр исходного кода. При последующей проверке вычисление повторяется, и если полученная цифра не совпадает с переданной, фиксируется ошибка.

История

Потребность в автоматическом обнаружении ошибок возникла с развитием механических и электронных вычислительных устройств. Одним из первых широко используемых алгоритмов стал код Луна (Luhn algorithm), разработанный в 1954 году инженером IBM Гансом Петером Луном. Первоначально он применялся для проверки номеров кредитных карт и был запатентован в 1960 году. В последующие десятилетия алгоритмы контрольных цифр были внедрены в международные стандарты идентификации: ISBN (книги), ISSN (периодика), EAN/UPC (штрихкоды), IMEI (мобильные устройства), ИНН (налоговые номера в России) и многие другие.

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

Алгоритм вычисления контрольной цифры основан на математических операциях над цифрами исходного номера. Общая схема включает следующие шаги:

1. Взвешивание — каждой цифре присваивается определённый весовой коэффициент (часто повторяющийся циклически).
2. Суммирование — вычисляется сумма произведений цифр на их веса (или иная комбинация, например, с удвоением и сложением цифр).
3. Вычисление остатка — полученная сумма делится на модуль (обычно 10 или 11), остаток от деления используется как контрольная цифра.
4. Дополнение — в некоторых системах контрольная цифра вычисляется как разность между модулем и остатком (если остаток не равен нулю).

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

Классификация алгоритмов

По модулю

• Модуль 10 — наиболее распространён (код Луна, EAN-13, UPC-A, IMEI). Контрольная цифра — одна десятичная цифра (0–9).
• Модуль 11 — используется в российском ИНН (10-значный для организаций, 12-значный для физических лиц), а также в ISBN-10. Контрольная цифра может быть от 0 до 9 или символом «X» (для значения 10).
• Модуль 97 — применяется в международных банковских номерах IBAN, где контрольные цифры вычисляются по модулю 97.

По методу взвешивания

• Фиксированные веса — каждому разряду присвоен постоянный вес (например, 1, 3, 1, 3… для EAN-13).
• Циклические веса — веса повторяются через определённый интервал (например, 7, 1, 3, 7, 1, 3… для ИНН).
• Удвоение с разбиением — характерно для кода Луна: каждая вторая цифра удваивается, и если результат больше 9, его цифры складываются.

По назначению

• Одноразрядные — одна контрольная цифра (большинство штрихкодов, номера карт).
• Многоразрядные — две и более цифры (например, ИНН физического лица содержит две контрольные цифры, IBAN — две цифры).

Примеры алгоритмов

Код Луна (Luhn algorithm)

Используется для проверки номеров банковских карт (Visa, Mastercard, Мир), а также IMEI и некоторых других идентификаторов. Алгоритм:

1. Цифры нумеруются справа налево, начиная с 1 (контрольная цифра — первая справа).
2. Каждая цифра на нечётной позиции (1, 3, 5…) умножается на 2.
3. Если результат умножения больше 9, из него вычитается 9 (или складываются цифры).
4. Все цифры (включая неизменённые на чётных позициях) суммируются.
5. Сумма должна делиться на 10 без остатка.

Пример: номер 4561 2612 1234 5467. Контрольная цифра (последняя) — 7. Проверка: сумма с учётом удвоения равна 70, что кратно 10 — номер корректен.

Алгоритм ИНН (Россия)

Для 10-значного ИНН (юридические лица) используются веса: [2, 4, 10, 3, 5, 9, 4, 6, 8]. Вычисляется сумма произведений, затем остаток от деления на 11. Если остаток больше 9, он уменьшается на 10. Контрольная цифра — последняя цифра номера.

Для 12-значного ИНН (физические лица) — две контрольные цифры. Первая вычисляется по первым 10 цифрам (веса: [7, 2, 4, 10, 3, 5, 9, 4, 6, 8]), вторая — по первым 11 цифрам (веса: [3, 7, 2, 4, 10, 3, 5, 9, 4, 6, 8]). Остаток от деления на 11, при необходимости — корректировка.

EAN-13 (штрихкод)

Контрольная цифра вычисляется по модулю 10 с весами 1 и 3, чередующимися справа налево, начиная с контрольной цифры (которая считается первой справа). Сумма произведений должна делиться на 10.

Применение

Алгоритмы контрольных цифр широко используются в следующих областях:

• Банковские и платёжные системы — номера карт, IBAN, BIC.
• Идентификационные номера — ИНН, СНИЛС, ОГРН, паспортные данные (в некоторых странах).
• Товарная маркировка — штрихкоды EAN, UPC, QR-коды (встроенные контрольные суммы).
• Телекоммуникации — IMEI (международный идентификатор мобильного оборудования).
• Библиотечное дело — ISBN, ISSN.
• Транспорт и логистика — номера контейнеров, авиабилетов, железнодорожных накладных.

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

Алгоритмы контрольных цифр не предназначены для защиты от преднамеренных искажений (криптографическая защита). Они эффективны только против случайных ошибок: одиночных перестановок цифр, замены одной цифры, пропуска или дублирования. При множественных ошибках или целенаправленном подборе ложного номера контрольная цифра может совпасть с корректной (вероятность для модуля 10 — 10%, для модуля 11 — около 9%). Кроме того, некоторые алгоритмы (например, код Луна) не обнаруживают ошибки при замене цифры 0 на 9 и наоборот в определённых позициях.

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

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

• Алгоритм Луна настолько прост, что может быть реализован вручную без вычислительной техники. Он не защищён патентами и является общедоступным.
• В российском СНИЛС контрольная цифра вычисляется по модулю 101, что позволяет использовать значения от 00 до 100 (двузначное число).
• В штрихкоде EAN-13 контрольная цифра может быть вычислена по последним 12 цифрам, и если она не совпадает с напечатанной, сканер отказывается считывать код.

Источники

• Патент США № 2,950,048 (Luhn, 1960)
• ГОСТ Р ИСО/МЭК 15420-2001 «Автоматическая идентификация. Кодирование штриховое. Спецификация символики EAN/UPC»
• Приказ ФНС России от 29.10.2014 № ММВ-7-3/558@ (об утверждении порядка расчёта контрольных цифр ИНН)
• ISO 7064:2003 «Information technology — Security techniques — Check character systems»
• Международный стандарт ISBN (ISO 2108:2017)