Алгоритм Луна: как проверить номер карты по модулю 10

Алгоритм Луна (Luhn algorithm) - это простейшая контрольная сумма по модулю 10, которой проверяют, не ошибся ли оператор при вводе длинного номера. Его придумал Ганс Питер Лун, инженер IBM, в 1954 году и запатентовал в 1960-м (US Patent 2 950 048). Не путать с похоже звучащим алгоритмом Куна - тот решает задачу о максимальном паросочетании в двудольном графе и к контрольным суммам отношения не имеет. Сегодня по Луну валидируют номера банковских карт (PAN по стандарту ISO/IEC 7812), IMEI мобильных устройств, канадский Social Insurance Number, израильский Teudat Zehut, греческий идентификатор Φ.Α.Δ.Ν. и десятки других серий. Никакой криптографии в нём нет - задача только одна: поймать случайную опечатку до того, как номер уйдёт в систему.

Алгоритм пошагово

Алгоритм работает с любой последовательностью цифр. Шаги:

1. Начиная с правой цифры, идти влево.
2. Каждую вторую цифру (то есть стоящую на чётной позиции, если считать справа и нумеровать с единицы) - удвоить.
3. Если результат удвоения больше 9 - вычесть 9 (что эквивалентно сложению цифр: $18 \to 1 + 8 = 9$).
4. Сложить все полученные числа (как удвоенные с поправкой, так и нетронутые).
5. Если сумма $S$ удовлетворяет $S \bmod 10 = 0$ - номер валиден.

Формально для номера $d_n d_{n-1} \ldots d_2 d_1$ (где $d_1$ - крайняя правая цифра):

$S = \sum_{i=1}^{n} f(d_i, i), \qquad f(d, i) = \begin{cases} d, & i \text{ нечётно} \\ d \cdot 2 - 9 \cdot [d \geq 5], & i \text{ чётно} \end{cases}$

Условие $S \equiv 0 \pmod{10}$ - критерий валидности. Псевдокод в десять строк:

function luhn(digits):
    sum = 0
    parity = length(digits) mod 2
    for i from 0 to length(digits) - 1:
        d = digits[i]
        if i mod 2 == parity:
            d = d * 2
            if d > 9: d = d - 9
        sum = sum + d
    return sum mod 10 == 0

Хочется не считать руками? Введите номер в поле ниже и выберите режим - проверка, расчёт контрольной цифры, пошаговая трассировка или сравнение с Verhoeff и Damm.

Подробный пример

Возьмём тестовый номер Visa $4532015112830366$ и проверим его. Шестнадцать цифр, нумеруем справа налево.

Сумма столбца «Результат»: $6 + 3 + 3 + 0 + 3 + 7 + 2 + 2 + 1 + 1 + 1 + 0 + 2 + 6 + 5 + 8 = 50$. Деление на 10: $50 \bmod 10 = 0$. Номер валидный.

Если бы где-то проскочила одна ошибка - например, кассир ввёл $4532015112830\mathbf{3}66$ вместо $4532015112830366$ (изменили одну тройку) - сумма сдвинется ровно на ту разницу, которую алгоритм по построению не пропускает.

Что ловит, а что нет

Луна устроен так, чтобы дёшево поймать самые частые опечатки оператора. Реально он гарантирует:

• 100% обнаружение одиночной изменённой цифры. Любая замена одного $d_i$ меняет вклад в сумму на величину, не кратную 10 - кроме одного хитрого случая, описанного ниже.
• Около 90% обнаружения перестановок соседних цифр. Из десяти возможных пар-перестановок $(ab) \leftrightarrow (ba)$ алгоритм пропускает только одну.

Что Луна не ловит:

• Перестановка $09 \leftrightarrow 90$. На паре соседних позиций одна из цифр обязательно удваивается. $0 \cdot 2 = 0$, $9 \cdot 2 = 18 \to 9$. Сумма пары до перестановки: $0 + 9 = 9$. После перестановки: $9 + 0 = 9$. Одно и то же - обмен остался незамеченным.
• Подмена двух цифр, сохраняющая сумму. Если оператор ошибся сразу в двух разрядах так, что одна разница компенсировала другую (например, $+3$ в одном и $-3$ в другом с учётом удвоения) - Луна молчит.
• Любые умышленные подделки. Алгоритм публичный и тривиальный, любой школьник за минуту сгенерирует «правильный по Луну» номер, не соответствующий ни одному счёту.

Зачем нужен - где применяется

Алгоритм Луна - почти универсальный стандарт там, где длинный номер вводят руками:

• PAN (Primary Account Number) банковских карт - основной потребитель. Стандарт ISO/IEC 7812 прямо предписывает Луна как контрольную цифру в 16-значном номере. Платёжные шлюзы (Stripe, PayPal, Adyen, ЮKassa) запускают Луна на стороне клиента ещё до отправки формы - это экономит сетевой round-trip на очевидные опечатки.
• IMEI мобильных устройств - 15-значный идентификатор, последняя цифра - контрольная по Луну. Когда вы набираете *#06# и вводите IMEI в чёрный список оператора, Луна отсеивает заведомо неправильные.
• Канадский SIN (Social Insurance Number) - 9 цифр, последняя по Луну.
• Израильский Teudat Zehut - 9-значный идентификатор личности.
• Греческий Φ.Α.Δ.Ν. - налоговый номер юридических лиц.
• NPI - National Provider Identifier, идентификатор медицинских работников в США.

Везде Луна выполняет одну и ту же роль: на стороне формы - поймать опечатку, на стороне бэкенда - отсечь явно битый ввод до тяжёлой проверки по базе.

Generation, не только validation

Зеркальная задача - сгенерировать контрольную цифру для нового номера. Алгоритм тот же, но запускается на $n-1$ известной цифре с подстановкой нуля на место контрольной, а потом ответ корректируется.

Пусть мы хотим выпустить карту с первыми 15 цифрами $453201511283036?$. Считаем сумму как обычно, но позиции теперь сдвинулись (контрольная цифра встанет на позицию 1 - нечётную, не удваивается):

$d_{16} = (10 - S' \bmod 10) \bmod 10,$

где $S'$ - сумма Луна по 15 «известным» цифрам с уже сдвинутой нумерацией. Для нашего примера $S' = 44$, тогда $d_{16} = (10 - 44 \bmod 10) \bmod 10 = (10 - 4) \bmod 10 = 6$. Контрольная цифра 6 - и полный номер $4532015112830366$ совпал с тем, что мы проверяли выше.

Сравнение с другими checksum

Алгоритмов «контрольной суммы для коротких номеров» больше одного. Соседи Луна по нише:

• Verhoeff (1969). Голландский математик Якобус Верхуф построил схему на группе диэдра $D_5$ порядка 10. Это первая контрольная сумма, которая ловит все одиночные ошибки и все перестановки соседних цифр (включая злополучные $09 \leftrightarrow 90$). Цена - табличное умножение и перестановка вместо простого удвоения.
• Damm (2004). Хайнрих Дамм нашёл квазигруппу порядка 10 без неподвижных точек, которая даёт те же гарантии, что Verhoeff, но проще описывается и реализуется одной таблицей $10 \times 10$.
• CRC (Cyclic Redundancy Check). Совсем из другой ниши: CRC проверяет блоки данных в десятки-сотни байт (Ethernet-кадры, ZIP-архивы), а не короткие номера. Стоимость выше, но и ошибки ловит куда более тонкие.
• MD5, SHA-1, SHA-256. Криптографические хеши - для проверки целостности файлов и подписей, а не для опечаток. На 16-значном номере применять SHA - стрелять из пушки по воробью и получить хеш длиннее самого номера.

Verhoeff и Damm строго лучше Луна по математике, но проигрывают в трёх вещах: их нельзя посчитать в уме, их таблицы надо хранить, и они появились на 15-50 лет позже - ниша банковских номеров была уже занята. Поэтому Луна жив и хорошо себя чувствует.

Реализации

Алгоритм укладывается в десяток строк на любом языке. Канонические шаблоны:

JavaScript (паттерн, который используют Stripe, ЮKassa и большинство фронтенд-валидаторов карт):

function luhn(num) {
    const digits = String(num).replace(/\D/g, '').split('').map(Number);
    const parity = digits.length % 2;
    const sum = digits.reduce((acc, d, i) => {
        if (i % 2 === parity) {
            d *= 2;
            if (d > 9) d -= 9;
        }
        return acc + d;
    }, 0);
    return sum % 10 === 0;
}

// Stripe test cards - все проходят Luhn, ни одной реальной транзакции
luhn('4242424242424242'); // true (Visa)
luhn('5555555555554444'); // true (Mastercard)
luhn('378282246310005');  // true (American Express)

Python (PyPI-пакет luhn ровно про это, но однострочник пишется без библиотек):

def luhn(num: str) -> bool:
    digits = [int(c) for c in num if c.isdigit()]
    s = sum(d if i % 2 == len(digits) % 2 else (d * 2 - 9 if d > 4 else d * 2)
            for i, d in enumerate(digits))
    return s % 10 == 0

Hardware. Чипы Visa/Mastercard на EMV-картах содержат микроконтроллер, который умеет сам считать Луна при выдаче ATC (Application Transaction Counter). На стороне POS-терминалов проверка часто хардварная - в FPGA уличных терминалов даже не используется CPU.

Тестовые карты для разработчиков

Платёжные провайдеры публикуют официальные тестовые номера, чтобы можно было прогонять Sandbox-транзакции и проверять интеграцию. Все они построены так, чтобы пройти Луна, но ни один не привязан к реальному счёту. Самые известные:

• Stripe - 4242 4242 4242 4242 (Visa, успешная), 4000 0000 0000 0002 (отклонённая), 5555 5555 5555 4444 (Mastercard).
• PayPal - 4032 0388 5605 2515 и серия 4111 1111 1111 1111.
• Adyen - 5555 4444 3333 1111 (Mastercard), 4111 1111 4555 1142 (Visa с 3-D Secure).
• ЮKassa - 5555 5555 5555 4444 для успеха, 5555 5555 5555 4477 для отказа.

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

Частые ошибки

• Путают чётность. На номерах с разной длиной (15 цифр у IMEI и AmEx, 16 у Visa, 19 у новых карт UnionPay) меняется, какая позиция удваивается. Правильный признак - «считать справа», а не «индекс в массиве».
• Делают d * 2 - 10 вместо - 9. Удвоение 5 → 10, и $10 - 10 = 0$ - но правильный ответ $1 + 0 = 1$. Вычитать надо именно 9.
• Запускают Луна и считают, что проверили карту. Луна - детектор опечаток, не подтверждение существования счёта. Авторизация делается через эмитента.
• Хранят PAN после проверки. PCI DSS требует никогда не сохранять полный номер карты в логах/БД на стороне мерчанта. Луна проверили - отдали в шлюз - забыли.

FAQ

Можно ли по алгоритму Луна определить тип карты (Visa, Mastercard)? Нет, Луна - только контрольная сумма. Тип определяется по первой цифре или нескольким первым (IIN/BIN-диапазон по ISO/IEC 7812): 4 - Visa, 51-55 и 2221-2720 - Mastercard, 34 и 37 - American Express, 2200-2204 - Мир.

Почему именно модуль 10, а не 11 или 7? Луна работал в эпоху механических калькуляторов IBM, и модуль 10 удобен ровно потому, что цифр в десятичной системе тоже 10 - никакой остаток нельзя выразить «лишней цифрой». Альтернатива - ISBN-10 с модулем 11 и символом X для остатка 10 - Луна явно избегал.

Чем отличается алгоритм Луна от алгоритма Verhoeff? Verhoeff (1969) гарантирует обнаружение всех одиночных ошибок и всех перестановок соседних цифр, тогда как Луна пропускает $09 \leftrightarrow 90$ и ещё около 10% перестановок. Цена - табличное умножение в группе диэдра $D_5$ вместо устного удвоения.

Коротко

Алгоритм Луна - контрольная сумма по модулю 10 для длинных номеров: идём справа налево, удваиваем каждую вторую цифру (если результат больше 9 - вычитаем 9), складываем всё, делим на 10. Остаток ноль - номер прошёл. Применяется в банковских картах, IMEI, SIN и десятке других идентификаторов; ловит 100% одиночных ошибок и 90% перестановок соседних цифр, не ловит подмену $09 \leftrightarrow 90$ и не защищает от подделки. Для математически строгих задач есть Verhoeff и Damm, но Луна остаётся стандартом де-факто из-за простоты и инерции 70 лет совместимости.