Алгоритм Luhn

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

История

Алгоритм был разработан в 1954 году Гансом Петером Луном (Hans Peter Luhn), работавшим в компании IBM. Первоначально он был запатентован в США (патент № 2 950 048, подан в 1954 году, выдан в 1960 году). Изначально алгоритм предназначался для использования в механических устройствах для проверки номеров, но впоследствии получил широкое распространение в цифровых системах. В 1970-х годах алгоритм Luhn стал стандартом для проверки номеров кредитных карт, выпускаемых по стандарту ISO/IEC 7812.

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

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

Этапы вычисления

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

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

Рассмотрим номер карты: 4992 7398 7160 1597 (контрольная цифра — последняя, 7).

1. Начинаем с правой цифры (7) и удваиваем каждую вторую цифру, двигаясь влево:

• 7 (не удваивается)
• 9 (удваивается: 9 × 2 = 18 → 1 + 8 = 9)
• 5 (не удваивается)
• 1 (удваивается: 1 × 2 = 2)
• 0 (не удваивается)
• 6 (удваивается: 6 × 2 = 12 → 1 + 2 = 3)
• 1 (не удваивается)
• 7 (удваивается: 7 × 2 = 14 → 1 + 4 = 5)
• 9 (не удваивается)
• 3 (удваивается: 3 × 2 = 6)
• 2 (не удваивается)
• 7 (удваивается: 7 × 2 = 14 → 1 + 4 = 5)
• 9 (не удваивается)
• 9 (удваивается: 9 × 2 = 18 → 1 + 8 = 9)
• 4 (не удваивается)

1. Суммируем все полученные цифры (включая неудвоенные):

• 7 + 9 + 5 + 2 + 0 + 3 + 1 + 5 + 9 + 6 + 2 + 5 + 9 + 9 + 4 = 76

1. Проверяем: 76 mod 10 = 6 ≠ 0. Номер недействителен.

Исправленный пример: Для корректного номера, например 4992 7398 7160 1596 (контрольная цифра 6), сумма будет равна 70, что делится на 10 без остатка.

Применение

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

• Платёжные карты: Номера кредитных и дебетовых карт (Visa, Mastercard, American Express, «Мир» и другие) обязательно проходят проверку по алгоритму Luhn. Это первичный фильтр, отсеивающий случайные опечатки при вводе номера.
• Идентификационные номера: IMEI-коды мобильных телефонов, номера социального страхования (в Канаде, США), номера некоторых банковских счетов (IBAN — частично).
• Железнодорожные билеты: Номера билетов РЖД (Российские железные дороги) также содержат контрольную цифру, вычисляемую по алгоритму Luhn.
• Другие системы: Номера некоторых государственных регистрационных документов, коды товаров (UPC, EAN — частично).

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

Алгоритм Luhn обладает рядом недостатков:

• Низкая криптостойкость: Алгоритм не предназначен для защиты от злонамеренных атак. Зная алгоритм, можно легко подобрать корректный номер, не зная реального.
• Не все ошибки обнаруживаются: Алгоритм не гарантирует обнаружение всех возможных ошибок. Например, перестановка цифр 09 и 90 (0 и 9) не будет обнаружена, так как 0 × 2 = 0, а 9 × 2 = 18 → 1 + 8 = 9, и наоборот. Также не обнаруживаются ошибки, связанные с заменой одной цифры на другую, если разница между ними кратна 5 (например, 0 → 5, 1 → 6 и т.д.).
• Не является хеш-функцией: Алгоритм не обладает свойствами криптографической хеш-функции, такими как необратимость и устойчивость к коллизиям.

Несмотря на эти ограничения, алгоритм Luhn остаётся широко распространённым благодаря своей простоте, скорости и эффективности для выявления случайных ошибок ввода, что является его основной целью.

Реализация

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

`` function luhnCheck(cardNumber): sum = 0 alternate = false for i from length(cardNumber)-1 down to 0: digit = cardNumber[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», 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, «Мир».