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

Лун алгоритм или формула Лун , также известный как « модуль 10» или « по модулю 10» алгоритм , названный в честь его создателя, IBM ученый Ханс Петер Лун , это простая контрольная формула используется для проверки различных идентификационных номеров, таких как кредит номера карт , номер IMEI , номер идентификатора национального провайдера в Соединенных Штатах, канадское социальное страхование число , израильские идентификационные номера, южноафриканские идентификационные номера, Swedish национальных идентификационные номера , шведский Фирменный стиль номер (OrgNr), греческие номера социального страхования (ΑΜΚΑ), Номера SIM-карт и коды опросов , указанные в квитанциях McDonald's , Taco Bell и Tractor Supply Co. Он описан в патенте США № 2,950,048, выданном 23 августа 1960 г.

Алгоритм является общественным достоянием и широко используется сегодня. Он указан в ISO / IEC 7812-1 . Он не предназначен для использования в качестве криптографически безопасной хеш-функции ; он был разработан для защиты от случайных ошибок, а не от злонамеренных атак. Большинство кредитных карт и многие государственные идентификационные номера используют алгоритм в качестве простого метода отличия действительных номеров от набранных с ошибками или иным образом неправильных номеров.

Описание

Контрольная цифра вычисляется следующим образом:

  1. Возьмите исходное число и, начиная с крайней правой цифры, двигаясь влево, удвойте значение каждой второй цифры (включая крайнюю правую цифру).
  2. Замените полученное значение в каждой позиции суммой цифр значения этой позиции.
  3. Суммировать полученные значения со всех позиций ( ы ).
  4. Расчетная контрольная цифра равна .

Пример вычисления контрольной цифры

Предположим, пример номера счета «7992739871» (только «полезная нагрузка», контрольная цифра еще не включена):

7 9 9 2 7 3 9 8 7 1
Множители 1 2 1 2 1 2 1 2 1 2
знак равно знак равно знак равно знак равно знак равно знак равно знак равно знак равно знак равно знак равно
7 18 9 4 7 6 9 16 7 2
Сумма цифр 7 9 (1 + 8) 9 4 7 6 9 7 (1 + 6) 7 2

Сумма полученных цифр 67.

Контрольная цифра равна .

Это делает полный номер счета 79927398713.

Пример проверки контрольной цифры

Просто обрежьте контрольную цифру (последнюю цифру) числа для подтверждения. 79927398713 -> 7992739871 Вычислите контрольную цифру (см. Выше) (3) и сравните свой результат с контрольной цифрой, которую вы отсекли (3 = 3). Если они совпадают, число прошло проверку.

Сильные и слабые стороны

Алгоритм Луна обнаружит любую ошибку, связанную с одной цифрой, а также почти все перестановки соседних цифр. Однако он не обнаружит транспонирование двузначной последовательности 09 в 90 (или наоборот). Он обнаружит большинство возможных двойных ошибок (он не обнаружит 2255 , 3366 или 4477 ).

Другие, более сложные алгоритмы проверки цифр (например, Verhoeff алгоритм и алгоритм Дамм ) могут обнаружить больше ошибок транскрипции. Лун мод N алгоритм является расширением , которое поддерживает нечисловые строки.

Поскольку алгоритм работает с цифрами справа налево, а нулевые цифры влияют на результат только в том случае, если они вызывают сдвиг позиции, заполнение нулями начала строки чисел не влияет на вычисления. Следовательно, системы, которые дополняют определенное количество цифр (например, путем преобразования 1234 в 0001234), могут выполнять проверку Luhn до или после заполнения и достигать того же результата.

Алгоритм появился в патенте США на портативное механическое устройство для вычисления контрольной суммы. Следовательно, требовалось, чтобы это было достаточно просто. Механическим способом устройство взяло мод 10 сум. Эти замены цифры , то есть, результаты двойной и сокращения процедуры, не были получены механическим способом . Скорее, цифры были отмечены на корпусе машины в порядке их перестановки.

Реализация псевдокода

function checkLuhn(string purportedCC) {
    int nDigits := length(purportedCC)
    int sum := integer(purportedCC[nDigits-1])
    int parity := (nDigits-1) modulus 2
    for i from 0 to nDigits - 2 {
        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
}

использованная литература

  1. ^ a b Патент США 2950048A , Luhn, Hans P. , «Компьютер для проверки чисел», опубликован 23 августа 1960 г. 
  2. ^ "Приложение B: Формула Луна для вычисления модуля-10" двойное добавление-двойное "контрольные цифры". Идентификационные карты - Идентификация эмитентов - Часть 1: Система нумерации (Стандарт). Международная организация по стандартизации , Международная электротехническая комиссия . Январь 2017. ISO / IEC 7812-1 : 2017.

внешние ссылки