Алгоритм модуль 10

Алгоритм модуль 10 — это метод вычисления контрольной цифры или контрольного символа, основанный на операции деления по модулю 10. Он используется для автоматической проверки целостности и достоверности последовательностей цифр, таких как номера банковских карт, кредитных счетов, серийные номера, штрихкоды и идентификационные номера. Основная цель алгоритма — выявление случайных ошибок ввода (например, замены одной цифры на другую или перестановки двух соседних цифр). Алгоритм модуль 10 не является единым стандартом; существует несколько его вариантов, наиболее известным из которых является алгоритм Луна.

Принцип действия

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

1. Определение направления обработки. Обычно цифры обрабатываются справа налево (начиная с самой младшей значащей цифры), но возможны варианты.
2. Удвоение каждой второй цифры. Начиная с определённой позиции (чаще всего — с первой цифры справа), каждая вторая цифра умножается на 2. Если результат умножения превышает 9, то цифры полученного двузначного числа складываются (эквивалентно вычитанию 9 или взятию цифровой суммы).
3. Суммирование. Все цифры (те, что не удваивались, и те, что прошли обработку) складываются.
4. Вычисление контрольного значения. Результат суммы делится по модулю 10. Полученный остаток (от 0 до 9) используется либо как контрольная цифра, либо для её вычисления.

В случае алгоритма Луна (Luhn algorithm, также известного как «mod 10» или «mod 10 check digit») контрольная цифра подбирается так, чтобы общая сумма делилась на 10 без остатка. Если при проверке существующего номера сумма не кратна 10, номер считается недействительным.

История

Методы контроля с использованием модульной арифметики применялись в вычислительной технике и криптографии с середины XX века. Однако стандартизация алгоритма модуль 10 в его современном виде связана с разработкой и внедрением пластиковых карт.

• 1954 год: Ганс Питер Луна (Hans Peter Luhn), инженер IBM, подал заявку на патент США № 2 950 048, в котором описывался метод вычисления контрольной цифры для идентификационных номеров. Патент был выдан в 1960 году.
• 1960-е годы: Алгоритм был принят в качестве стандарта для номеров кредитных карт международными платёжными системами (Visa, Mastercard). Простота вычислений позволяла проверять номера вручную или с помощью простых механических устройств.
• Конец XX — начало XXI века: Алгоритм модуль 10 стал основой для многих отраслевых стандартов, включая IMEI (телефонные аппараты), номера социального страхования (в некоторых странах), номера железнодорожных билетов и т.д.

Разновидности алгоритма модуль 10

Хотя термин «модуль 10» часто отождествляется с алгоритмом Луна, существуют и другие формулы, использующие деление на 10 для проверки.

Классический алгоритм Луна (Luhn)

• Основные характеристики: удвоение каждой второй цифры справа, суммирование, проверка на кратность 10.
• Область применения: номера банковских карт (первые 15 цифр — идентификатор, 16-я — контрольная), номера карт лояльности, некоторые идентификаторы в системах учёта.
• Пример: Номер карты 4532 0123 4567 8901? Проверка справа налево: цифры 1, 0, 7, 5, 3, 1, 2, 4? (удваиваются цифры, стоящие на чётных позициях). После вычисления суммы и проверки на mod 10 номер будет признан действительным или недействительным.

Алгоритм с постоянным модулем (ISO 7064 / Luhn с модификациями)

В некоторых стандартах (например, ISO 7064) используется более сложная схема, где взвешивание цифр производится по определённой последовательности весовых коэффициентов (например, 2, 3, 4, 5, 6, 7, 2, 3...), а затем результат делится по модулю 10. Такой подход применяется в номерах IMEI (15 цифр, 15-я — контрольная) и в номерах некоторых национальных идентификационных систем.

Простая контрольная сумма по модулю 10

Самый примитивный вариант: все цифры складываются, и контрольная цифра вычисляется как (10 — остаток от деления суммы на 10) mod 10. Этот метод менее надёжен, чем алгоритм Луна, так как не защищает от перестановок цифр, но используется в простых кодировках (например, в некоторых штрихкодах UPC-A).

Применение

Алгоритм модуль 10 широко распространён в областях, где требуется быстрая автоматическая проверка вводимых данных без обращения к базе данных.

Платёжные системы

• Номера банковских карт (PAN): Все основные эмитенты (Visa, Mastercard, Maestro, Мир и др.) используют алгоритм Луна для формирования номера карты. Это позволяет банкоматам и терминалам отклонять номера, введённые с ошибкой, до отправки запроса в процессинговый центр.
• Номера счетов IBAN (International Bank Account Number): Хотя в расчёте IBAN применяется модуль 97-10 (ISO 7064), в некоторых этапах проверки также используется деление на 10.

Связь и электроника

• IMEI (International Mobile Equipment Identity): 15-значный номер мобильного устройства. Последняя цифра вычисляется по алгоритму Луна с весовыми коэффициентами (ISO 7064, mod 10).
• IMSI (International Mobile Subscriber Identity): 15-значный номер, используемый в сотовых сетях. Контрольная цифра (Luhn) применяется для верификации номера.

Торговля и логистика

• Штрихкоды: В стандартах UPC-A (12 цифр) последняя цифра — контрольная, вычисляемая по модулю 10. Аналогично в EAN-13 (13 цифр) контрольная цифра рассчитывается по модулю 10 с весовыми коэффициентами (1 и 3 для чётных/нечётных позиций).
• Номера трекинга почтовых отправлений: Многие почтовые службы (Почта России, DHL, UPS) используют алгоритм mod 10 для генерации трек-номеров.

Гражданские и административные системы

• ИНН (Идентификационный номер налогоплательщика) в России: 10 цифр для организаций. Проверка последней цифры выполняется по алгоритму, основанному на делении по модулю 11 с последующим взятием остатка по модулю 10. Результат делится на 10 и сравнивается с контрольной цифрой. Аналогичный принцип (но с другими весами и модулями) используется для 12-значных ИНН физических лиц.
• СНИЛС (Страховой номер индивидуального лицевого счёта) в России: хотя в основе расчёта контрольной цифры лежит деление на 101 (mod 101), промежуточные вычисления включают суммирование с последующим делением на 10 для выделения двухзначного контрольного числа.

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

Несмотря на широкую распространённость, алгоритм модуль 10 (особенно классический Луна) обладает рядом недостатков:

• Низкая криптографическая стойкость: Алгоритм не предназначен для защиты от злонамеренного изменения номера. Любой, кто знает алгоритм, может легко подобрать корректную контрольную цифру для произвольного набора цифр. Это делает его непригодным для хранения паролей или аутентификации.
• Ограниченная обнаруживающая способность: Алгоритм хорошо находит одиночные ошибки (замена одной цифры) и ошибки перестановки двух соседних цифр (около 90% таких ошибок). Однако он практически не выявляет двойные ошибки (замена двух цифр) и не защищает от вставки или удаления цифр.
• Зависимость от длины кода: Для корректной работы необходимо знать точное количество цифр в идентификаторе. При вводе номера с пропущенной или лишней цифрой алгоритм может дать ложноположительный результат.

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

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

• Алгоритм Луна был запатентован ещё в эпоху, когда не было массового использования компьютеров, и проверка номера могла выполняться на калькуляторе или даже вручную за несколько секунд.
• В номере банковской карты «Мир» (национальная платёжная система РФ) контрольная цифра также вычисляется по алгоритму Луна.
• Наибольшую известность алгоритм получил благодаря тому, что он является первым шагом в алгоритме проверки кредитной карты (наряду с проверкой длины номера и префикса эмитента).
• В 2008 году был предложен алгоритм «Verhoeff» (с использованием дицикличной группы D5), который лучше обнаруживает перестановки цифр, но из-за более сложной реализации не получил массового распространения в платёжных системах.

Источники

• Патент США 2 950 048 (Luhn, 1960).
• Международный стандарт ISO/IEC 7812-1 (идентификация финансовых транзакций).
• Стандарт ISO 7064 (модульные контрольные функции).
• Руководство GS1 по расчёту контрольной цифры для штрихкодов EAN/UPC.
• Описание алгоритма IMEI (3GPP TS 23.003).
• Официальная документация ФНС России по алгоритму расчёта контрольной суммы ИНН.