Алгоритм Луна

Алгоритм Луна (также известный как формула Луна или алгоритм «mod 10») — это математический алгоритм, используемый для проверки контрольной суммы идентификационных номеров, в частности номеров банковских карт, а также некоторых других типов номеров (например, IMEI, номеров социального страхования в Канаде). Алгоритм был разработан немецким учёным Хансом Петером Луном в 1954 году и запатентован в 1960 году. Основная цель алгоритма — обнаружение случайных ошибок при вводе или передаче данных, таких как опечатки или перестановка цифр.

История

Алгоритм Луна был создан Хансом Петером Луном (1919–2009), который работал в исследовательском подразделении компании IBM. В 1954 году он подал заявку на патент, который был выдан 23 августа 1960 года под номером US 2,950,048. Первоначально алгоритм предназначался для проверки корректности номеров, вводимых в компьютеры, и был одним из первых примеров применения контрольных сумм в цифровой обработке данных. Впоследствии, с развитием банковской системы и электронных платежей, алгоритм Луна стал стандартом для проверки номеров банковских карт, выпускаемых международными платёжными системами, такими как Visa, Mastercard, American Express и другими.

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

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

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

Пример проверки

Рассмотрим номер карты 4539 1488 0343 6467. Для проверки:

• Цифры: 4, 5, 3, 9, 1, 4, 8, 8, 0, 3, 4, 3, 6, 4, 6, 7 (последняя — контрольная).
• Удвоение каждой второй цифры (начиная с первой): 42=8, 32=6, 12=2, 82=16 (1+6=7), 02=0, 42=8, 62=12 (1+2=3), 62=12 (1+2=3).
• Сумма удвоенных: 8+6+2+7+0+8+3+3 = 37.
• Сумма неудвоенных цифр (вторые, четвёртые и т.д.): 5+9+4+8+3+3+4+7 = 43.
• Общая сумма: 37+43 = 80.
• 80 делится на 10, следовательно, номер корректен.

Применение

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

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

Наиболее известное применение — проверка номеров банковских карт. Все основные платёжные системы (Visa, Mastercard, American Express, Discover и другие) используют алгоритм Луна для генерации контрольной цифры. Это позволяет банкам и платёжным шлюзам быстро отсеивать заведомо неверные номера без обращения к эмитенту карты.

IMEI-номера

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

Номера социального страхования (Канада)

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

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

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

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

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

• Одиночные ошибки в цифре (например, 5 вместо 4).
• Перестановку соседних цифр (например, 12 вместо 21), за исключением случаев, когда перестановка приводит к изменению суммы на 0 или кратное 10.
• Некоторые двойные ошибки.

Однако алгоритм не может обнаружить:

• Перестановку цифр, разнесённых на несколько позиций.
• Вставку или удаление цифр.
• Некоторые типы ошибок, связанные с заменой цифр, дающих одинаковую сумму.

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

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

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

Источники

• Патент США № 2,950,048, «Computer for verifying numbers», Hans Peter Luhn, 1960.
• ISO/IEC 7812-1:2017 «Identification cards — Identification of issuers — Part 1: Numbering system».
• Стандарт IMEI (3GPP TS 23.003).
• Официальные документы платёжных систем Visa и Mastercard.
• Материалы по алгоритму Луна на сайте IBM Research.