Kontrollsumma – definition, metoder (CRC, Hamming, mod 97) och exempel

Lär dig vad en kontrollsumma är, hur CRC, Hamming och mod 97 fungerar, samt tydliga exempel för att upptäcka fel i kontonummer och data.

Kontrollsumma är ett nummer som används som en enkel form av redundanskontroll för att upptäcka fel i data som skrivits ner eller överförts. Det finns flera olika metoder för att beräkna en kontrollsumma; i sin enklaste form adderas till exempel alla siffror. Den enkla summan är snabb men svag: den kan upptäcka vissa fel (t.ex. en felaktig siffra som förändrar totalsumman) men inte positionella fel där två siffror byter plats. Kraftfullare algoritmer för kontrollsummor använder bland annat Hamming-kod, cyklisk redundanskontroll (CRC) eller modulär aritmetik. En vanlig praktisk användning av kontrollsummor är att kontrollera att bankkontonummer eller andra identifierare har angetts korrekt.

Hur fungerar kontrollsumma i praktiken?

• Enkel siffersumma: summera siffrorna i en talsträng (eller summan av bytes) och eventuellt ta modulus av summan. Enkel att beräkna men fångar inte många typer av fel.
• Viktade summor: varje position ges en vikt innan summering (t.ex. ISBNs kontrollsiffra eller Luhn-algoritmen för kreditkort). Viktning gör det möjligt att upptäcka vissa positionsfel och transpositionsfel bättre än enkel summa.
• Modulär aritmetik (t.ex. mod 97): används i bankrutiner och i IBAN. Rester vid division med ett tal (t.ex. 97) används som kontrollvärde.
• Hamming-kod: en kod som både kan upptäcka och rätta enkla bitfel. Hamming-koder är uppbyggda med paritetsbitar placerade på strategiska positioner.
• CRC (cyclic redundancy check): en polynomdivision i GF(2) som ger en rest (CRC) som är mycket effektiv på att fånga slumpmässiga fel i bitströmmar och korta felkorrigeringar i sekvenser (burst-fel).

Exempel: portugisiskt bankkontonummer (mod 97)

Portugisiska bankkontonummer är ett tydligt exempel på användning av modulär aritmetik. De har 21 siffror. De första 19 siffrorna identifierar bank, filial och konto, och de två sista siffrorna är kontrollsiffror beräknade med mod 97. Ett typiskt portugisiskt bankkontonummer skrivs som 0002.0123.12345678901.54 där siffrorna betyder:

·    Siffrorna "0002" står för banken.

·    Siffrorna "0123" står för bankens filial.

·    Siffrorna "12345678901" står för kontonumret.

·    Siffrorna "54" står för kontrollsumman.

Om man tar bankkontonumret utan punkter som ett långt tal (i originalexemplet: 00020123121234567890154) och dividerar det med 97 blir kvoten ett stort tal och resten är 1. Eftersom resten är "1" stämmer kontrollsiffrorna och numret är troligen korrekt. Om någon siffra saknas, är felplacerad eller felaktig kommer resten vanligtvis att skilja sig från 1 och ett fel kan upptäckas — då bör systemet generera ett felmeddelande.

Hur räknar man mod 97 för stora tal (praktisk metod)

Eftersom långa tal inte alltid får plats i vanliga heltal används en stegvis metod:

• Ta de första 9 siffrorna (eller ett annat lämpligt antal som ryms i din miljö).
• Dela dessa med 97 och spara resten.
• Sätt resten framför nästa grupp av siffror (t.ex. rest följt av nästa 7–9 siffror) och dela igen med 97.
• Upprepa tills alla siffror behandlats. Den slutliga resten är talets rest modulo 97.

Denna tekniken är densamma som används när man kontrollerar IBAN-nummer i praktiken.

Kort om Hamming-kod

Hamming-koder är kanalkoder som både kan upptäcka och korrigera enkla fel. De är uppbyggda så att paritetsbitar placeras i positioner som är potenser av två (1, 2, 4, 8 …). Varje paritetsbit täcker en uppsättning bitpositioner. Med rätt uppsättning paritetsbitar får man en minsta Hamming-avstånd på 3, vilket innebär att:

• En enkelsidig bitfel kan lokaliseras och rättas.
• Två bitfel kan upptäckas (men inte alltid rättas).

Exempel (förenklat): data 1011 (4 bitar) kan ges tre paritetsbitar så att den totala koden blir 7 bitar. Genom att räkna paritetskontrollerna får mottagaren en syndrom-vektor som visar vilken bit (om någon) är felaktig.

Kort om CRC

CRC är en metod där bitsträngen betraktas som ett polynom över GF(2) och divideras med ett förutbestämt generatorpolynom. Resten (CRC) läggs till i slutet av data. Vanliga varianter är CRC-8, CRC-16 och CRC-32. Egenskaper:

• Mycket bra på att upptäcka slumpmässiga fel och korta burst-fel upp till en viss längd (beroende på polynomet).
• Väl vald generator kan garantera upptäckt av alla enkla fel, de flesta transpositionsfel och de flesta korta burst-fel.
• Inte säker mot avsiktlig manipulation — CRC är inte kryptografiskt säker.

CRC används i nätverk (Ethernet), lagringsmedia och filformat där man behöver en snabb och effektiv felkontroll.

Vad kan kontrollsummor upptäcka — och vad inte?

• Kontrollsummor fångar oftast slumpmässiga fel snabbt och billigt. En väl utvald metod upptäcker de flesta vanliga feltyper.
• De kan ofta inte skydda mot avsiktlig manipulation: en angripare som känner algoritmen kan skapa en annan giltig kombination som ger samma kontrollsumma.
• Styrkan beror på metoden: Hamming kan rätta enkelbitfel, CRC fångar burst-fel effektivt, modulära metoder fångar många numeriska fel (och används mycket i banktillämpningar).
• För integritetsskydd eller autentisering krävs kryptografiska metoder (t.ex. MAC eller kryptografiska hashfunktioner). Kontrollsummor är inte ett säkert substitut för dessa.

Andra praktiska exempel

• Bankkonton och IBAN (mod 97) använder modulära kontroller för att reducera tangentfel.
• ISBN (boknummer) använder en viktad kontrollsiffra (mod 11 för 10-siffrigt ISBN) för att upptäcka transpositionsfel.
• EAN/UPC-streckkoder använder mod 10 med vikter för att verifiera skannade koder.
• Kreditkortsnummer verifieras ofta med Luhn-algoritmen (vikter och mod 10).
• Kontrollsummor används även i programvaruserialnummer och serienummer för datorprogram för att minska risken för skrivfel vid inmatning.

Sammanfattning

Kontrollsummor är effektiva verktyg för att upptäcka oavsiktliga fel i data. Valet av metod avgör hur många och vilka typer av fel som kan upptäckas eller korrigeras. För enkla felkontroller räcker ofta modulära kontroller eller Luhn; för dataströmmar och nätverk är CRC vanligt; för felkorrigering på bitnivå används Hamming-koder. För säkerhet mot avsiktliga attacker krävs däremot kryptografiska metoder.

Frågor och svar

F: Vad är en kontrollsumma?

F: Hur beräknas kontrollsummor?

F: Vad är ett exempel på hur kontrollsummor fungerar?

F: Hur hjälper detta till att upptäcka fel?

F: Var annars används kontrollsummor?

F: Vad händer om ett fel upptäcks av en kontrollsumma?

Sök med bokstav