Luhn-algoritmen

Luhnalgoritmen, även kallad modulus-10-algoritmen eller mod-10-algoritmen, är en vanligt förekommande algoritm för att beräkna en enkel felupptäckande kod i form av en kontrollsumma. Luhnalgoritmen används bland annat för att beräkna kontrollsiffran i svenska personnummer, samt i kreditkorts-, plusgiro-, bankgiro- och bankkontonummer. Den ingår i kontrollsiffrorna för OCR-nummer (referensnummer på inbetalningskort av typ bankgiro och plusgiro), men där är den ibland kompletterad med ytterligare en kontrollsiffra som anger entalssiffran i antalet siffror i OCR-numret. På så sätt kan man även upptäcka om en nolla lagts till eller tagits bort ur OCR-numret.

Algoritmen kan alltid upptäcka enkelfel, det vill säga en enstaka felskriven siffra, och nästan alltid ett byte av två intilliggande siffror (med undantag av om de två siffrorna är 0 och 9). Om två eller fler siffror är felskrivna finns emellertid en liten risk att felen inte upptäcks därför att de tar ut varandra så att de ger upphov till samma kontrollsiffra.

Algoritmen är utformad så att det är möjligt att infoga ett godtyckligt antal nollor i början av koden utan att det påverkar kontrollsiffran (exempelvis "000123" och "123" ger upphov till samma kontrollsiffra).

När algoritmen uppfanns fanns det krav på en enkel algoritm för att kunna kontrollera och generera kontrollsiffror och Luhnalgoritmen uppfyller detta krav. I jämförelse med moderna felupptäckande koder har algoritmen inte någon betydande styrka eller effektivitet.

Algoritmen utvecklades av Hans Peter Luhn på IBM och beskrivs i US patent 2950048, med ansökningsdatum den 6 januari 1954, och beviljandedatum den 23 augusti 1960.

Vid kontroll av koden, inklusive kontrollsiffra, fungerar algoritmen på så sätt att med start från den sista siffran i koden (den minst signifikanta siffran), det vill säga kontrollsiffran, multipliceras siffrorna ömsom med 1 och ömsom med 2. Skulle något tal vid en sådan multiplikation bli större än 9 ersätts talet med dess siffersumma (eller, likvärdigt, med talet subtraherat med 9). Därefter summeras talen. Om den erhållna summan är jämnt delbar med 10 så är kontrollsiffran korrekt.

Exempel på personnummer 811218-9876:

   8  1 1 2 1 8  9 8  7 6
*  2  1 2 1 2 1  2 1  2 1
-------------------------
   ^  ^ ^ ^ ^ ^  ^ ^  ^ 
  16  1 2 2 2 8 18 8 14 6

Tvåsiffriga produkter splittras upp i ensiffriga tal. Siffrorna summeras därefter:

${\displaystyle 1+6+1+2+2+2+8+1+8+8+1+4+6=50}$

Denna summa är delbar med 10 och sålunda har vi inte upptäckt något fel i numret.

import re

def check_pnr(s):
        if not bool(re.search("^\d{10}$", s)):
                return False
        return sum(map(lambda x: x%10 + int(x/10), 
                map(lambda x,y: x*y, map(int, s), [2,1]*5))) % 10 == 0
     
     
# Alternativ och något mer generell rutin.
def check_swedish_pnr(personnummer: str) -> bool:
    """Return True when personnummer passes the Luhn test, else False.

    Accept personnummer strings in the format [åå]ÅÅMMDD[-+]NNNC.  All
    non-digits are scrubbed and only the last 10 digits (ÅÅMMDDNNNC)
    are used when performing the Luhn test.
    
    >>> check_swedish_pnr("19811218+9876")
    True
    >>> check_swedish_pnr("811218-9876")
    True
    >>> check_swedish_pnr("8112189876")
    True

    Number the sequence of digits ÅÅMMDDNNNC left to right from 10 to
    1.  The even numbered digits should be multiplied by 2, but when
    the product is >= 10 use the digit sum of the product. Odd
    numbered digits are summed as they are.  Two cases when
    multiplying

       1. 2*d < 10 ---> d + d
       2. 2*d >= 10 use the respective digit sum ---> d + d - 9
       --->
       sum(all_digits, even_digits)
    """
    digits = [int(c) for c in personnummer if c.isdigit()][-10:]
    if len(digits) != 10:
        return False
    even_digitsum = sum(x if x < 5 else x - 9 for x in digits[::2])
    return 0 == sum(digits, even_digitsum) % 10

För att beräkna kontrollsiffran är förfarandet likvärdigt, med skillnaden att man multiplicerar ömsom med 2 och ömsom med 1 (det vill säga att man börjar att multiplicera den sista siffran med 2, och inte med 1 som i fallet vid kontroll). Den erhållna summan dras därefter ifrån närmast större 10-tal, varvid kontrollsiffran erhålles.

För att beräkna kontrollsiffran för det niosiffriga personnumret 811218-987 erhålles följande produkter:

   8  1 1 2 1 8  9 8  7
*  2  1 2 1 2 1  2 1  2
-------------------------
   ^  ^ ^ ^ ^ ^  ^ ^  
  16  1 2 2 2 8 18 8 14

Tvåsiffriga produkter splittras upp i ensiffriga tal. Siffrorna summeras därefter:

${\displaystyle 1+6+1+2+2+2+8+1+8+8+1+4=44}$

Kontrollsiffran erhålls genom att detta tal subtraheras från närmast högre tiotal. Om differensen är 10 blir kontrollsiffran 0^[1].

${\displaystyle 50-44=6}$

Den avslutande kontrollsiffran blir således en sexa och det tiosiffriga personnumret blir 811218-9876.

import re

def compute_check_digit_pnr(s):
        if not bool(re.search("^\d{9}$", s)):
                return False
        return (10 - (sum(map(lambda x: x%10 + int(x/10), 
                map(lambda x,y: x*y, map(int, s), [2,1]*4 + [2]))) % 10)) % 10

                
def swedish_pnr_check_digit(s):
    """Return check digit associated with partial personnummer s or None.

    Accept partial personnummer strings in the format
    [åå]ÅÅMMDD[-+]NNN.  All non-digits are scrubbed and only the last
    9 digits (ÅÅMMDDNNN) are used when calculating the check digit C
    using the Luhn algorithm.

    None is returned when there are too few digits.  None rather than
    False, since it is harder to interpret as 0.

    >>> swedish_pnr_check_digit("19811218-987")
    6
    >>> swedish_pnr_check_digit("19811218+987")
    6
    >>> swedish_pnr_check_digit("811218+987")
    6
    >>> swedish_pnr_check_digit("811218987")
    6
    >>> swedish_pnr_check_digit("81121898") == None
    True
    >>> swedish_pnr_check_digit("818181818")
    1
    >>> check_swedish_pnr("8181818181")
    True
    """
    digits = [int(d) for d in re.sub(r'\D', '', s)][-9:]
    if len(digits) != 9:
        return None
    even_digitsum = sum(x if x < 5 else x - 9 for x in digits[::2])
    check_digit = sum(digits, even_digitsum) % 10
    return 10 - check_digit if check_digit else 0

Koden förutsätter att input-strängen är normaliserad för att kunna utföra beräkningen, dvs en sträng med minst 9 siffror, där metoden räknar ut den tionde siffran (dvs kontrollsiffran) med hjälp av Luhn-algoritmen.

Koden är kraftigt förenklad för att vara så kärnfull som möjligt.

import static java.lang.Integer.parseInt;
import static java.lang.String.valueOf;
import static java.util.stream.IntStream.range;

public class ChecksumHelper {
    private static final int INDEX_START = 0;
    private static final int INDEX_BEFORE_CHECKSUM = 9;
    private static final int BASE = 10;
    private static final int ODD = 1;
    private static final int EVEN = 2;

    public static int calculateChecksum(char[] strArray) {
        return (BASE - (range(INDEX_START, INDEX_BEFORE_CHECKSUM)
                .map(i -> parseInt(valueOf(strArray[i])) * (i % EVEN == 0 ? EVEN : ODD))
                .map(s -> ((s >= BASE) ? (1 + (s % BASE)) % BASE : s))
                .sum() % BASE)) % BASE;
    }
}

Exempel på användning för att räkna ut kontrollsiffra för ett 10-siffrigt personnummer. OBS! personnummer beräknas endast med födelseårets årtionde och år i beräkningen. Årtusende och århundrade utelämnas alltså. Födelseåret 1912 bilr därför endast 12, då 19 inte ska tas med i beräkningen. Ett anrop till metoden kan se ut så här ...

int checksum = ChecksumHelper.calculateChecksum("121212-121".replaceAll("\\D", "").toCharArray());
System.out.println(checksum);

Konsol utskrift:

2

Vilket är den korrekta checksumman (sista siffran i personnumret 19121212-1212