Modulo 10

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

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

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

1. Удвоение цифр на чётных позициях: Начиная с самой правой цифры (которая считается первой, позиция 1), каждая вторая цифра (на позициях 2, 4, 6 и т.д.) умножается на 2.
2. Суммирование разрядов: Если результат удвоения даёт двузначное число (от 10 до 18), его цифры складываются отдельно (например, 12 → 1+2=3). Если результат однозначный, он используется как есть.
3. Суммирование нечётных: Цифры, стоящие на нечётных позициях (1, 3, 5 и т.д.), включая контрольную, складываются без изменений.
4. Проверка по модулю 10: Общая сумма всех полученных значений суммируется. Если результат делится на 10 без остатка (т.е. сумма mod 10 == 0), номер считается корректным.

Пример расчёта

Рассмотрим гипотетический номер карты 4539 1488 0343 4567. Проверим его корректность.

1. Запишем номер, начиная с последней цифры (контрольная — 7). Позиции: 1 — 7, 2 — 6, 3 — 5, 4 — 4, 5 — 3, 6 — 0, 7 — 4, 8 — 3, 9 — 8, 10 — 8, 11 — 1, 12 — 4, 13 — 9, 14 — 3, 15 — 5, 16 — 4.
2. Применим шаг 1 к цифрам на чётных позициях (2, 4, 6... 16):

• 6 → 12 → 1+2 = 3
• 4 → 8
• 0 → 0
• 3 → 6
• 8 → 16 → 1+6 = 7
• 4 → 8
• 3 → 6
• 4 → 8

1. Сложим полученные значения: 3 + 8 + 0 + 6 + 7 + 8 + 6 + 8 = 46.
2. Сложим цифры на нечётных позициях (1,3,5...15):

• 7 + 5 + 3 + 4 + 8 + 1 + 9 + 5 = 42.

1. Общая сумма = 46 + 42 = 88.
2. Проверка: 88 mod 10 = 8, а не 0. Следовательно, номер недействителен.

История

Алгоритм был разработан в 1954 году немецким инженером Гансом Петером Луном (Hans Peter Luhn) из компании IBM. Изначально он предназначался для проверки номеров в системах обработки чеков. Патент США № 2950048 на изобретение был получен в 1960 году. Широкое распространение алгоритм получил в 1960–70-х годах с развитием кредитных карт и необходимостью быстрой проверки их номеров без обращения к центральной базе данных. Он стал стандартом де-факто для международных платёжных систем и был включён в стандарты ISO/IEC 7812 (идентификация финансовых карт) и ISO/IEC 7064 (системы проверки цифр).

Применение

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

Наиболее известное применение — проверка номеров кредитных и дебетовых карт. Номера карт (16 или 19 цифр) обязательно содержат контрольную цифру, вычисленную по алгоритму Modulo 10. Это позволяет банкоматам и платёжным терминалам мгновенно отсекать номера с явными опечатками, не отправляя их в банк-эмитент.

IMEI

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

Социальные и страховые номера

Хотя алгоритм Луна широко применяется в финансовой сфере, многие государственные идентификаторы (например, СНИЛС в России, номер социального страхования в США) используют другие методы проверки, часто основанные на других модулях (11, 101) или полиномиальных кодах.

Преимущества и ограничения

Преимущества

• Простота реализации: Алгоритм легко реализуется в программном и аппаратном обеспечении.
• Эффективность: Требует минимальных вычислительных ресурсов.
• Обнаружение распространённых ошибок: Надёжно выявляет одиночные ошибки и более 90% перестановок соседних цифр.

Ограничения

• Не защищает от намеренных подделок: Алгоритм не является криптографически стойким. Зная структуру (например, первые 6 цифр — BIN), можно сгенерировать последовательность, проходящую проверку, но не имеющую реального номера.
• Не обнаруживает все возможные ошибки: Некоторые двойные ошибки могут быть не замечены.
• Не учитывает длину номера: Алгоритм проверяет только цифры, не проверяя длину строки.

Критика и альтернативы

Хотя алгоритм Луна остаётся стандартным для платёжных карт, в современных условиях его недостатки стали более заметны. В частности, он не учитывает контекст (например, тип карты, код страны). Для более строгих контрольных сумм в банковских системах часто применяют Modulo 97 (например, в российских номерах счетов — 20-значный счёт, где последние 2 цифры — ключ, рассчитываемый по модулю 97 алгоритмом BIC).

Также существуют специализированные алгоритмы, такие как Verhoeff (использует диедрическую группу D5) и Damm (дизъюнктивная группа), которые обладают лучшими свойствами обнаружения ошибок, в частности, 100% обнаружением одиночных и двойных ошибок, включая все типы перестановок. Однако они сложнее в реализации и реже используются в потребительской электронике.

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

• Количество возможных номеров, проходящих проверку Modulo 10, составляет ровно 1/10 от всех теоретически возможных комбинаций цифр заданной длины.
• В некоторых системах (например, в номерах российских банковских карт, выпущенных по национальной платёжной системе «Мир») алгоритм может быть дополнен собственными внутренними правилами расчёта контрольной цифры, хотя базовая структура Modulo 10 сохраняется.
• Алгоритм Луна иногда ошибочно называют «алгоритмом Luhn Mod 10», но термин Modulo 10 является более корректным описанием его математической основы.

Источники

• Патент США № 2950048. Computer for verifying numbers. Hans Peter Luhn. 1960.
• Стандарт ISO/IEC 7812-1:2017. Identification cards — Identification of issuers — Part 1: Numbering system.
• Стандарт ISO/IEC 7064:2003. Information technology — Security techniques — Check character systems.