У любой длинной последовательности цифр есть слабое место: человек, который её набирает, рано или поздно ошибётся. Алгоритм Луна придуман именно для того, чтобы такую ошибку заметить, — и только для этого. Это арифметика по модулю десять, предложенная Хансом Петером Луном в компании IBM в пятидесятых годах прошлого века и позже закреплённая в стандарте нумерации карт. Здесь мы разберём, как посчитать контрольную цифру обычной ручкой на бумаге, что эта проверка гарантирует и чего от неё ждать нельзя.
Какую задачу решает контрольная цифра?
Любая система, которая принимает длинные числовые идентификаторы, хочет отдешевить одну вещь: обнаруживать опечатку до того, как неверная строка уйдёт дальше. Полноценная криптографическая подпись для этого слишком дорога — она защищала бы от подделки, но обходилась бы в вычисления и лишние согласования. Нужна дешёвая проверка, которую можно провести где угодно, в том числе в голове у кассира или в старой кассе без сети.
Контрольная цифра — ровно такой инструмент. Она вычисляется из всех остальных цифр номера и записывается последней. Изменилась хотя бы одна цифра из середины — сумма перестала делиться на десять, и номер отвергнут. Никаких секретов, никаких ключей, никакого сетевого доступа.
Важно и то, чего в схеме нет: она не требует базы данных. Проверяющий не спрашивает ни у кого, существует ли такой номер. Он просто пересчитывает сумму и сравнивает остаток с нулём.
Как посчитать вручную
Правило укладывается в четыре шага, и его действительно можно выполнить на бумаге.
- Отбросьте последнюю цифру — это и есть контрольная, её мы пока не считаем.
- Двигаясь справа налево, удвойте каждую вторую цифру из оставшихся.
- Если после удвоения получилось число больше девяти, вычтите из него девять.
- Сложите всё, включая отброшенную контрольную цифру; номер корректен, если итог делится на десять без остатка.
Возьмём известный набор из повторяющихся четвёрок и двоек, который заканчивается четвёркой. Удвоенные четвёрки дают восемь, и таких позиций восемь — это шестьдесят четыре. Двойки стоят на неудваиваемых местах, их тоже восемь, это шестнадцать. Итог восемьдесят делится на десять, значит последовательность записана правильно.
Теперь испортим ровно одну цифру где-нибудь в середине. Итог станет другим, остаток от деления на десять уже не ноль, и это сразу видно. Одиночная опечатка при наборе с клавиатуры — самая частая ошибка, и именно её схема ловит безошибочно.
Какие ошибки алгоритм не заметит
С перестановками всё интереснее. Большинство случаев, когда две соседние цифры меняются местами, тоже приводят к ненулевому остатку — но не все. Классический контрпример: нуль и девятка меняются местами незаметно для суммы. Есть и другие пары, где перестановка не меняет итог, поэтому утверждение «перестановки ловятся всегда» неверно.
Второй класс пропущенных ошибок — ошибки, которые взаимно компенсируют друг друга: одну цифру увеличили, другую уменьшили так, что сумма осталась той же. Наконец, лишняя или пропущенная цифра в середине сдвигает всю картину удвоения, и результат становится непредсказуемым: чаще всего проверка всё-таки провалится, но полагаться на это как на гарантию нельзя.
Отсюда важный для практики вывод: успешная проверка контрольной цифры означает лишь, что строка не противоречит сама себе. Она не означает, что номер набран правильно, и уж точно не означает, что он кому-то принадлежит.
Где эта же арифметика используется ещё
Дешевизна сделала схему популярной далеко за пределами платёжной отрасли. Тот же принцип встречается в идентификаторах мобильных устройств, в канадских номерах социального страхования, в греческом налоговом номере и в ряде национальных удостоверений. Это полезно держать в голове, когда вы читаете чужой код: функция, подписанная как проверка карт, нередко оказывается общей утилитой и вызывается ещё в десятке мест, где правила могут отличаться.
Практическое следствие: перед правкой такой функции посмотрите, кто ещё её вызывает. Изменение поведения ради одной платёжной системы легко сломает проверку студенческого билета или номера устройства.
Почему это не защита от подделки?
Главное недоразумение темы — уверенность, будто прохождение проверки что-то говорит о подлинности карты. Не говорит ничего. Арифметика открыта и полностью обратима: для любого начала номер дополняется верной последней цифрой мгновенно, а значит подобрать её может кто угодно, включая самый обычный генератор.
Второе следствие того же свойства: из любой строки цифр можно сделать формально корректный номер, поменяв одну последнюю цифру. Поэтому на результате этой проверки нельзя строить решения о правах доступа, о доверии к источнику данных или о том, «настоящий» ли перед вами пользователь. Это фильтр опечаток, и его место — в начале обработки, рядом с проверкой длины и допустимого начала.
Что важно разработчику
Порядок проверок важнее самой реализации. Сначала приведите вход к одному виду: уберите пробелы, дефисы и любые разделители, отбросьте невидимые символы. Затем убедитесь, что остались только цифры: буква или знак внутри строки должны приводить к отказу, а не к молчаливому игнорированию. Только после этого проверяйте длину, затем допустимое начало для заявленной платёжной системы, и лишь в самом конце считайте контрольную цифру.
Причина такого порядка проста: контрольная сумма не знает ни о длине, ни о диапазонах, поэтому сама по себе она пропустит и слишком короткую, и слишком длинную строку. Кроме того, ранняя проверка суммы даёт бессмысленно точное сообщение об ошибке вместо понятного «проверьте номер».
Отдельная ловушка — числовое преобразование. Длинную строку нельзя переводить в число: в языках с плавающей точкой теряются младшие цифры, а ведущие нули исчезают при любом преобразовании. Работать нужно с отдельными символами и с их числовыми значениями, а не со значением всей строки целиком.
И ещё одна ловушка: удвоение должно начинаться с правильной позиции относительно контрольной цифры. Именно здесь чаще всего ошибаются, и функция начинает считать контрольной цифру, стоящую слева, а не справа. Хороший способ это поймать — сравнить свою реализацию с независимой на большом наборе входов, включая пустую строку, одну цифру и строку с нецифровыми символами. Расхождение почти всегда указывает именно на сдвиг позиции, а не на ошибку в арифметике.
Наконец, проверьте поведение на строке, состоящей из одних нулей, и на строке, длина которой равна единице. Оба случая формально проходят проверку суммы, и если ваш код их отвергает, значит, где-то смешаны правила длины и правила контрольной цифры.
Что делать дальше
Если вам нужны данные, которые заведомо проходят описанную проверку, генератор выдаёт структурно корректные номера, которые никогда не выпускались ни одним банком. Чтобы понять, как такая строка устроена целиком, перейдите к разбору формата номера, а чтобы увидеть место проверки в общем процессе — к чек-листу платёжной формы.