Алгоритм Луна

Алгоритм Луна (англ. Luhn algorithm), або формула Луна (англ. Luhn formula), також відомий під назвою «modulus 10» або «mod 10», це проста формула перевірки контрольної суми, що використовується для валідації різноманітних ідентифікаційних номерів, таких як номери кредитних/платіжних карток, номери IMEI, американських National Provider Identifier Number, канадських Canadian Social Insurance Number, ізраїльських ID Numbers та грецьких Social Security Numbers (ΑΜΚΑ). Алгоритм був створений науковцем з IBM Гансом Петером Луном^[en] і описаний патентом U.S. Patent No. 2,950,048, описаним 6 січня 1954 року та схваленим 23 серпня 1960 року.

Алгоритм є публічним і широко використовується. Він також вказаний у ISO/IEC 7812^[en]. Цей алгоритм не створювався як криптографічно надійна хеш-функція, а суто як захист від випадкових помилок. Більшість кредитних карток і багато урядових ідентифікаційних номерів використовують цей алгоритм як простий метод відсіювання неправильних номерів.

Опис

Формула перевіряє номер за його контрольною цифрою, котра зазвичай додається до часткового номера акаунту (partial account number) при генеруванні повного номера акаунту (full account number). Цей номер повинен успішно проходити таку перевірку:

1. Починаючи від крайньої правої цифри (контрольної), рухаємося ліворуч, подвоюючи кожну другу цифру. Якщо результат подвоєння є більшим, ніж 9 (як-от: 8 × 2 = 16), то потрібно додати числа результату (наприклад: 16: 1 + 6 = 7, 18: 1 + 8 = 9), або, як альтернатива — відняти 9 від результату (16: 16 − 9 = 7, 18: 18 − 9 = 9).
2. Знайти суму всіх цифр.
3. Якщо ділення суми на 10 не має остачі (сума закінчується нулем,) то номер є правильним відповідно до формули Луна.

Нехай у нас є номер «7992739871», який матиме контрольну цифру в наступному вигляді: 7992739871x. Тоді:

Номер	7	9	9	2	7	3	9	8	7	1	x
Подвоїти через одну	7	18	9	4	7	6	9	16	7	2	x
Додати цифри	7	9	9	4	7	6	9	7	7	2	x

Сума всіх цифр у третьому рядку дорівнюватиме 67+x.

Контрольну цифру (x) можна отримати множенням суми цифр на 9 і діленням результату на 10 ((67 × 9) mod 10). У формі алгоритму:

1. Обчислити суму цифр без контрольної (67).
2. Помножити на 9 (603).
3. Остання цифра (3) буде контрольною цифрою, як-от x=3.

Альтернативний метод: контрольна цифра (x) отримується в результаті суми решти цифр (3 рядок), ділення її на 10 з остачею, і віднімання цієї остачі від 10 (остача (67/10) = 7; 10 − 7 = 3). В алгоритмічній формі:

1. Вирахувати суму цифр без контрольної (67).
2. Отримати остачу (7).
3. Відняти остачу від 10.
4. Результат (3) є контрольною цифрою. Якщо сума закінчується нулем, то нуль буде контрольною цифрою.

Відповідно повний номер акаунту матиме вигляд 79927398713.

Кожен з номерів 79927398710, 79927398711, 79927398712, 79927398713, 79927398714, 79927398715, 79927398716, 79927398717, 79927398718, 79927398719 може пройти перевірку наступним чином:

1. Подвоїти цифри через одну, починаючи з крайньої правої: (1×2) = 2, (8×2) = 16, (3×2) = 6, (2×2) = 4, (9×2) = 18
2. Додати всі окремі цифри (цифри в дужках є результатами кроку 1): x (контрольна цифра) + (2) + 7 + (1+6) + 9 + (6) + 7 + (4) + 9 + (1+8) + 7 = x + 67.
3. Якщо сума ділиться без остачі на 10, то номер може бути правильним. Зверніть увагу, що 3 — це єдина правильна контрольна цифра, котра поверне суму (70), яка ділиться на 10 без остачі.
4. Отже всі ці номери є неправильними, окрім 79927398713, котрий має правильну контрольну цифру.

Ви можете також використати той самий алгоритм створення контрольної суми, припускаючи що наявна перевірка контрольної суми насправді відсутня. Тоді порахуйте контрольну суму і порівняйте результат із оригінальною контрольною сумою, наявною в кредитної картки. Якщо оригінальна контрольна сума відповідає порахованій, то номер є правильним.

Переваги та недоліки

Алгоритм Луна може знайти помилку в одній цифрі, так само як і всі перестановки сусідніх цифр, проте він не може виявити перестановку двоцифрових послідовностей 09 - 90 (чи навпаки). Він виявлятиме також 7 із 10 можливих помилок дублювання (але не виявить 22 ↔ 55, 33 ↔ 66 або 44 ↔ 77).

Інші, складніші алгоритми перевірки контрольної цифри (такі як алгоритм Вергуффа чи алгоритм Дамма) можуть знаходити більше помилок. Існує ще алгоритм Луна mod N (Luhn mod N algorithm), який є розширенням звичайного і додає підтримку нецифрових рядків.

Оскільки алгоритм оперує цифрами справа наліво і нулі впливають на результат тільки тоді, коли вони викликають зміщення позиції, то нулі на початку послідовності цифр не вплинуть на розрахунок. Внаслідок цього системи, які мають на початку певну кількість цифр (наприклад при конвертуванні 1234 в 0001234), можуть проходити перевірку алгоритмом Луна з нулями або без них і видавати однакові результати.

Додавання 0 до номерів непарної довжини дозволяє перевіряти номери зліва направо, а не навпаки, з подвоєнням цифр на непарних місцях.

Алгоритм з'явився в американському патенті для ручного механічного пристрою для обрахунку контрольних сум, а тому основною вимогою до алгоритму була відносна простота реалізації. Механізм пристрою ділив суму на 10, але цифри від подвоєння та наступної редукції не отримувалися механічним шляхом, а позначалися у зміненому порядку на самому пристрої.

Приклади імплементації

Псевдокод

 function checkLuhn(string purportedCC) {
     int sum := 0
     int nDigits := length(purportedCC)
     int parity := nDigits modulus 2
     for i from 0 to nDigits - 1 {
         int digit := integer(purportedCC[i])
         if i modulus 2 = parity
             digit := digit × 2
             if digit > 9
                 digit := digit - 9
         sum := sum + digit
     }
     return (sum modulus 10) = 0
 }

Посилання