Luhn-алгоритм¶

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

¶История

Алгоритм был впервые описан в патенте США № 2 950 048, поданном Хансом Петером Луном 6 января 1954 года и выданном 23 августа 1960 года. В патенте алгоритм назывался «Computer for Verifying Numbers» (Компьютер для проверки номеров). Изначально он предназначался для использования в механических устройствах, но позже получил широкое распространение в электронных системах. После истечения срока действия патента алгоритм стал общедоступным и был принят в качестве стандарта для многих международных платёжных систем, включая Visa, Mastercard, American Express и Discover.

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

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

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

¶Пример расчёта контрольной цифры

Допустим, требуется вычислить контрольную цифру для номера 7992739871X (где X — искомая цифра). Цифры номера (без X) — 7, 9, 9, 2, 7, 3, 9, 8, 7, 1. Нумерация справа налево:

Удваиваются цифры на позициях 2, 4, 6, 8, 10: 7, 9, 7, 9, 7. После удвоения: 14, 18, 14, 18, 14. Сумма цифр этих чисел: 1+4=5, 1+8=9, 1+4=5, 1+8=9, 1+4=5. Сумма неудвоенных цифр (позиции 1,3,5,7,9): 1+8+3+2+9 = 23. Общая сумма: 5+9+5+9+5 + 23 = 56. Чтобы сумма делилась на 10, необходимо добавить 4 (56+4=60). Контрольная цифра X = 4. Полный номер: 79927398714.

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

Для номера 79927398714 (с контрольной цифрой 4) проверка даёт сумму 60, которая делится на 10 — номер корректен. Если бы контрольная цифра была другой, например 5, сумма стала бы 61 — номер не прошёл бы проверку.

¶Применение

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

Luhn-алгоритм используется для проверки номеров банковских карт (PAN — Primary Account Number) в платёжных системах Visa, Mastercard, American Express, Discover, JCB, Diners Club и других. Номер карты обычно состоит из 16 цифр (у American Express — 15), последняя из которых является контрольной, вычисленной по алгоритму. Это позволяет банкам и терминалам мгновенно отсеивать явно неверные номера при вводе.

¶IMEI

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

¶Номера социального страхования (США)

В некоторых штатах США алгоритм применяется для проверки номеров социального страхования (SSN), хотя это не является обязательным требованием федерального законодательства.

¶Другие идентификаторы

Luhn-алгоритм также используется в номерах кредитных карт некоторых розничных сетей, в идентификаторах участников программ лояльности, в номерах заказов и в некоторых системах маркировки товаров.

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

Luhn-алгоритм не является криптографически стойким. Он не защищает от преднамеренного мошенничества, так как злоумышленник, зная алгоритм, может легко подобрать корректную контрольную цифру для произвольного номера. Алгоритм не обнаруживает двойные ошибки (например, замену 22 на 55) и некоторые типы перестановок цифр (например, 09 ↔ 90). Для повышения надёжности в современных системах часто используются более сложные алгоритмы, такие как Verhoeff-алгоритм или алгоритм Damm, которые исправляют большее количество ошибок.

¶Реализация

Алгоритм легко реализуется программно. Пример на псевдокоде:

`` function luhnCheck(number): sum = 0 alternate = false for i from length(number)-1 down to 0: digit = number[i] if alternate: digit = digit * 2 if digit > 9: digit = digit - 9 sum = sum + digit alternate = not alternate return (sum % 10 == 0) ``

¶Источники

• Патент США № 2 950 048 «Computer for Verifying Numbers», 1960.
• ISO/IEC 7812-1:2017 «Identification cards — Identification of issuers — Part 1: Numbering system».
• Luhn, H. P. (1954). «Computer for Verifying Numbers». IBM Journal of Research and Development.
• Wagner, N. R. (1983). «The Luhn Algorithm for Credit Card Validation». Communications of the ACM.