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

Алгоритм Луна или формула Луна , также известный как « модуль 10» или «модуль 10» алгоритм , названный в честь его создателя, IBM ученого Ханса Питера Луна , представляет собой простую формулу контрольных цифр , используемую для проверки различных идентификационных номеров. Он описан в патенте США 2950048А, выданном 23 августа 1960 г.

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

Описание

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

1. Если номер уже содержит контрольную цифру, отбросьте эту цифру, чтобы сформировать «полезную нагрузку». Контрольная цифра чаще всего является последней цифрой.
2. С полезной нагрузкой начните с самой правой цифры. Двигаясь влево, удвойте значение каждой второй цифры (включая самую правую цифру).
3. Суммируйте значения полученных цифр.
4. Контрольная цифра рассчитывается по формуле $(10-(s{\bmod {1}}0))$, где s — сумма из шага 3. Это наименьшее число (возможно, ноль), которое необходимо прибавить к $s$ чтобы получить кратное 10. Другие действительные формулы, дающие то же значение: $9-((s+9){\bmod {1}}0)$, $(10-s){\bmod {1}}0$, и $10\lceil s/10\rceil -s$. Обратите внимание, что формула $(10-s){\bmod {1}}0$ не будет работать во всех средах из-за различий в том, как отрицательные числа обрабатываются операцией по модулю .

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

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

	7	9	9	2	7	3	9	8	7	1
Множители	2	1	2	1	2	1	2	1	2	1
	=	=	=	=	=	=	=	=	=	=
	14	9	18	2	14	3	18	8	14	1
Суммировать цифры	5 (1+4)	9	9 (1+8)	2	5 (1+4)	3	9 (1+8)	8	5 (1+4)	1

Сумма получившихся цифр равна 56.

Контрольная цифра равна $(10-(56\operatorname {mod} 10))=4$.

В результате полный номер счета будет выглядеть как 17893729974.

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

1. Отбросьте контрольную цифру (последнюю цифру) номера для проверки. (например, 17893729974 → 1789372997)
2. Вычислите контрольную цифру (см. выше)
3. Сравните полученный результат с исходной контрольной цифрой. Если оба числа совпадают, результат действителен. (например (givenCheckDigit = вычисленнаяCheckDigit) ⇔ (isValidCheckDigit)).

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

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

Другие, более сложные алгоритмы контрольных цифр (такие как алгоритм Верхуффа и алгоритм Дамма ) могут обнаруживать больше ошибок транскрипции. Алгоритм Луна mod N — это расширение, поддерживающее нечисловые строки.

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

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

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

Следующая функция принимает номер карты, включая контрольную цифру, как массив целых чисел и выводит true, если контрольная цифра правильная, и false в противном случае.

function isValid(cardNumber[1..length])
    sum := 0
    parity := length mod 2
    for i from 1 to length do
        if i mod 2 != parity then
            sum := sum + cardNumber[i]
        elseif cardNumber[i] > 4 then
            sum := sum + 2 * cardNumber[i] - 9
        else
            sum := sum + 2 * cardNumber[i]
        end if
    end for
    return cardNumber[length] == (10 - (sum mod 10))
end function

Реализация кода

С#

bool IsValidLuhn(in int[] digits)
{
    int check_digit = 0;
    for (int i = digits.Length - 2; i >= 0; --i)
        check_digit += ((i & 1) is 0) switch
        {
            true  => digits[i] > 4 ? digits[i] * 2 - 9 : digits[i] * 2,
            false => digits[i]
        };

    return (10 - (check_digit % 10)) % 10 == digits.Last();
}

Ява

public static boolean isValidLuhn(String number) {
    int n = number.length();
    int total = 0;
    boolean even = true;
    // iterate from right to left, double every 'even' value
    for (int i = n - 2; i >= 0; i--) {
        int digit = number.charAt(i) - '0';
        if (digit < 0 || digit > 9) {
            // value may only contain digits
            return false;
        }
        if (even) {
            digit <<= 1; // double value
        }
        even = !even;
        total += digit > 9 ? digit - 9 : digit;
    }
    int checksum = number.charAt(n - 1) - '0';
    return (total + checksum) % 10 == 0;
}

Машинопись

function luhnCheck(input: number): boolean {
  const number = input.toString();
  const digits = number.replace(/\D/g, '').split('').map(Number);
  let sum = 0;
  let isSecond = false;
  for (let i = digits.length - 1; i >= 0; i--) {
    let digit = digits[i];
    if (isSecond) {
      digit *= 2;
      if (digit > 9) {
        digit -= 9;
      }
    }
    sum += digit;
    isSecond = !isSecond;
  }
  return sum % 10 === 0;
}

Питон

• Этот раздел включает исходный код из Git репозитория github. .с /codeperfectplus / Выздоровление .git на GitHub , который распространяется по лицензии Apache , версия 2.0, авторские права © codeperfectplus, 2022–2024, troyfigiel, 2024 г.

"""Verhoeff's algorithm implementation for checksum digit calculation"""


class LuhnAlgorithm(BaseChecksumAlgorithm):
    """
    Class to validate a number using Luhn algorithm.

    Arguments:
        input_value (str): The input value to validate.

    Returns:
        bool: True if the number is valid, False otherwise.
    """
    def __init__(self, input_value: str) -> None:
        self.input_value = input_value.replace(' ', '')

    def last_digit_and_remaining_numbers(self) -> tuple:
        """Returns the last digit and the remaining numbers"""
        return int(self.input_value[-1]), self.input_value[:-1]

    def __checksum(self) -> int:
        last_digit, remaining_numbers = self.last_digit_and_remaining_numbers()
        nums = [int(num) if idx % 2 != 0 else int(num) * 2 if int(num) * 2 <= 9
                else int(num) * 2 % 10 + int(num) * 2 // 10
                for idx, num in enumerate(reversed(remaining_numbers))]

        return (sum(nums) + last_digit) % 10 == 0

    def verify(self) -> bool:
        """Verify a number using Luhn algorithm"""
        return self.__checksum()

Использование

Алгоритм Луна используется во множестве систем, в том числе:

• Номера кредитных карт
• номера IMEI
• Национальные идентификационные номера поставщика услуг в США
• Номера канадского социального страхования
• Израильские идентификационные номера
• Южноафриканские идентификационные номера
• Южной Африки Справочные номера налоговых органов
• Шведские национальные идентификационные номера
• Шведские фирменные номера (OrgNr)
• Номера социального страхования Греции (AMKA)
• ICCID SIM-карт
• европейские патенты Номера заявок на
• Коды опросов, указанные в McDonald's , Taco Bell и Tractor Supply Co. квитанциях
• В номерах отслеживания посылок Почтовой службы США используется модифицированный алгоритм Луна.
• Итальянские номера НДС ( номер НДС )

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

• Тест Луна номеров кредитных карт в Rosetta Code : реализация алгоритма/формулы Луна на 160 языках программирования по состоянию на 22 июля 2024 г.