Алгоритм Луна (англ. Luhn Algorithm) — алгоритм вычисления контрольной цифры номера пластиковых карт в соответствии со стандартом ISO/IEC 7812. Не является криптографическим средством, предназначение алгоритма в первую очередь — выявление ошибок, вызванных непреднамеренным искажением данных (например, при ручном вводе номера карты, при приёме данных о номере социального страхования по телефону). Позволяет лишь с некоторой степенью достоверности судить об отсутствии ошибок в блоке цифр, но не даёт возможности локализации и коррекции обнаруженной неточности.
Алгоритм разработан сотрудником фирмы IBM Гансом Питером Луном, описан в США в 1954 году, патент получен в 1960 году. В настоящее время содержание алгоритма является публичным достоянием.
Наиболее распространённые применения для подсчёта контрольной цифры:
- Номера всех банковских карт.
- Номера некоторых дисконтных карт.
- Коды социального страхования.
- IMEI-коды.
- MEID (модифицированный алгоритм).
Достоинства и недостатки:
В силу простоты реализации, алгоритм отнимает минимум вычислительных мощностей; в ряде случаев при наличии навыка расчёт может быть произведён «в уме». В то же время, алгоритм Луна позволяет только выявить ошибки в блоках данных, и то не все. Искажение одной цифры — обнаруживается. Обнаруживаются практически все парные перестановки подряд идущих цифр (за исключением 09 ↔ 90). Не могут быть обнаружены некоторые искажения двух подряд идущих цифр, а именно 22 ↔ 55, 33 ↔ 66 и 44 ↔ 77. Алгоритм не даёт информации о месте и характере возникшей ошибки.
Алгоритм может применяться для последовательностей цифр любой длины, однако при этом следует иметь в виду, что при достаточно длинных числах вероятно появление одновременно нескольких искажений данных; некоторые из таких ошибок могут привести к ошибочному выводу, что контрольное число, вычисленное по алгоритму Луна, подтверждает неизменность данных.
Алгоритм проверки контрольной цифры (оригинальный алгоритм, описанный разработчиком):
- Цифры проверяемой последовательности нумеруются справа налево.
- Цифры, оказавшиеся на нечётных местах, остаются без изменений.
- Цифры, стоящие на чётных местах, умножаются на 2.
- Если в результате такого умножения возникает число больше 9, оно заменяется суммой цифр получившегося произведения — однозначным числом, то есть цифрой.
- Все полученные в результате преобразования цифры складываются.
Если сумма кратна 10, то исходные данные верны.
Проверка пластиковой карты согласно алгоритму Луна:
| 4 | 0
| 0
| 0
| | 0 | 0
| 1
| 2
| | 3
| 4
| 5
| 6
| | 7
| 8
| 9
| 9
|
| 16 | 15
| 14
| 13
| 12
| 11
| 10
| 09
| 08
| 07
| 06
| 05
| 04
| 03
| 02
| 01
|
29=
| 0
| +
| 0 | +
| 0 | + | 2
| +
| 4
| +
| 6
| +
| 8
| +
| 9
|
4×2
| +
| 0×2 | +
| 0×2 | +
| 1×2 | +
| 3×2 | +
| 5×2 | +
| 7×2 | +
| 9×2 | =31
|
Результат: В результате сложения двух полученных значений (п.5 алгоритма) "
29" и "
31" получается сумма равная значению "
60" - кратная 10, следовательно исходные данные верны.
