DD1320 Tillämpad datalogi

Föreläsning 12 - Kryptering

Läs i boken: kap 3.4.3
Kryptering:
Transpositionschiffer
Cesarchiffer
RSA

Kryptering

Att kryptera ett meddelande innebär att vi kodar det så att det blir oläsligt för alla utom den som vet hur man dekrypterar det. Kryptering används i alla sammanhang där man har anledning att hålla något hemligt, t ex vid överföring av kontokortsnummer över internet eller när man vill skicka lägesrapporter från diktaturer.

Olika former av kryptering har använts så länge man har velat ha skriftliga hemligheter. Redan dom gamla grekerna hade flera system för kryptering.

Transpositionschiffer

I det antika Grekland användes en scytale - en dekrypteringspinne för att avkoda hemliga meddelanden skrivna på en remsa skinn. Avsändaren och mottagaren har varsin pinne av samma diameter. Avsändaren lindar skinnremsan som en spiral runt pinnen och skriver sitt meddelande längs med pinnen. Remsan blir då obegriplig tills den hamnar i mottagarens händer.

Samma effekt kan vi få genom att skriva meddelandet i en mxn-matris och bilda det kodade meddelandet genom att ta varje kolumn i texten. Den som känner till matrisens storlek kan lätt avkoda det. Man brukar skippa mellanslag och skiljetecken för att göra det svårare att knäcka koden.

JAGGÖ
MMERP
ENGAR
NAIDE
NGAML
AEKEN

kodas alltså som:

JMENNAAMNAGEGEGIAKGRADMEÖPRELN

Caesarchiffer

Julius Caesar lär ha använt denna metod:
A byts mot D
B byts mot E
C byts mot F
osv.

En variant är rot13 där man förskjuter varje bokstav 13 steg. Hamnar man utanför alfabetet roterar man runt till början igen.

def rot13(meddelande):
    alfabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    kod = ""
    for bokstav in meddelande:
        index = (alfabet.find(bokstav) + 13) % 26
        kod = kod + alfabet[index]
    return kod

Om vi skippar ÅÄÖ får vi ett alfabet som består av 26 tecken, vilket innebär att vi kan använda samma funktion för dekryptering!

rot13("HEMLIGHETER") blir URZYVTURGRE

rot13("URZYVTURGRE") blir HEMLIGHETER

Ännu hemligare blir det om vi slumpar fram en mappning istället för att flytta fram ett visst antal steg.

ABCDEFGHIJKLMNOPQRSTUVWXY
|||||||||||||||||||||||||
FSXNVDQBCULRHKTPAOMWJEIGY

Alla dessa chiffer är dock enkla att knäcka om man har statistik över hur ofta varje bokstav förekommer i det aktuella språket. Så här ser det ut för svenska:
stapeldiagram över bokstavsfrekvenser

RSA

Ett problem med många chiffer är att man måste berätta för mottagaren hur hon ska dechiffrera meddelandet. Hur är man säker på att den viskningen inte blir avlyssnad?

Krypteringsalgoritmen RSA (döpt efter Ron Rivest, Adi Shamir och Leonard Adleman som först publicerade den) löser detta genom att ha en offentlig nyckel och en privat nyckel. Den offentliga nyckeln delar du ut till alla, så att dom kan kryptera meddelanden och skicka till dig, men det är bara du som kan dekryptera med hjälp av den privata nyckeln.

Först måste vi beräkna nycklarna:

Välj två stora primtal, p och q.
Beräkna n = p*q.
Beräkna f = (p-1)*(q-1).
Välj e så att det inte har några gemensamma faktorer med f (dvs gcd(e,f) ska bli 1).
Beräkna d som den multiplikativa inversen till e modulo f, dvs så att e*d modulo f = 1.

e och n är offentliga, medan d är privat. Själva krypteringen går till så att man först konverterar meddelandet till ett tal (t ex genom att konkatenera ASCII-koderna). Man delar upp det i lagom stora delar som vi kallar m₁, m₂ osv.

Sedan beräknar vi m_i^e modulo n för att få de kodade delarna c_i.

Den som vill dekryptera måste känna till d, och kan då få ut det ursprungliga meddelandet genom att beräkna c_i^d modulo n för varje c_i.

På University of Illinois har man gjort en demo av RSA, prova gärna!

För att knäcka RSA måste man faktorisera n, dvs lista ut vilka de två stora primtalen p och q är. Det finns ännu ingen algoritm som kan göra detta i polynomisk tid, dvs O(L^k) där L är längden av primtalet och k är en godtycklig konstant, vilket innebär att beräkningen tar för lång tid för att vara praktiskt användbar. Därför räknar man med att RSA i nuläget är oknäckbar för tillräckligt stora primtal.

Mer att läsa

I Simon Singhs kodbok finns tio chiffreringsuppgifter av stigande svårighetsgrad. De första att knäcka alla tio var ett lag med dåvarande/blivande doktorander i teorigruppen (TCS) på ert labbsalsplan! Här är deras berättelse om hur det gick till.

En fortsättningskurs som bland annat handlar om tillämpningar av kryptering är DD2395 Datasäkerhet. Där får man också lära sig om t ex virus och datajuridik.

Säkerhetsaspekter tas även upp i kursen DD1334 Databasteknik som vissa av er läser redan i vår.

Vi har förstås också kursen DD2448 Kryptografins grunder (men den kräver att man läst DD1352 ADK först).

Stavningskontroll

Ett stavningskontrollprogram ska läsa en text och markera alla ord som är felstavade. Om man har tillgång till en ordlista som innehåller alla riktiga svenska ord kan man använda följande enkla algoritm för att stavningskontrollera en text.

Läs in ordlistan i en lämplig datastruktur.
Öppna textfilen.
Så länge filslut inte nåtts:

Läs in nästa ord från filen.
Slå upp ordet i ordlistan och skriv ut det på skärmen om det inte finns med.

Enda problemet är hur man ska välja datastruktur för lagring av ordlistan. Svenska akademiens ordlista innehåller ungefär 200000 ord. Förutom dessa ord finns en hel del böjningsformer och oändligt många tänkbara sammansättningar. Låt oss bortse från detta och anta att vi har köpt en ordlista med dom 200000 vanligaste orden i svenskan. Om vi snabbt ska kunna stavningskontrollera en stor text med en normal persondator måste följande krav på datastrukturen vara uppfyllda.

Uppslagning måste gå jättesnabbt.
Datastrukturen får inte ta så mycket minne (helst inte ens så mycket minne som orden i klartext).
Orden måste vara kodade (eftersom ordlistan är köpt och inte får spridas till andra).
Vi kan tillåta att uppslagningen gör fel någon gång ibland.

Den sista punkten är inte ett krav utan en egenskap hos vårt problem som vi kan utnyttja. Det är nämligen inte hela världen om programmet missar något enstaka felstavat ord i en jättestor text.

Vanliga datastrukturer (sorterad array, sökträd, hashtabell) faller alla på något av kraven ovan.

Försök med datastruktur: boolesk hashtabell

Låt oss först försöka med hashning där vi inte lagrar själva orden och inte tar hand om eventuella krockar. Vi har en hashfunktion f(ord)=index som för varje ord anger en position i en boolesk hashtabell tab. Den booleska variabeln tab[f(ord)] låter vi vara sann då ord ingår i ordlistan. Detta ger en snabb, minnessnål och kodad datastruktur, men den har en stor brist: Om det råkar bli så att hashfunktionen antar samma värde för ett ord i ordlistan som för ett felstavat ord så kommer det felstavade ordet att godkännas. Om hashtabellen exempelvis är fylld till häften med ettor så är sannolikheten för att ett felstavat ord ska godkännas ungefär 50% vilket är alldeles för mycket.

Bloomfilter

Lösningen är att använda många hashfunktioner som alla ger index i samma hashtabell tab. I Viggos stavningskontrollprogram Stava används till exempel 14 olika hashfunktioner f₀(ord),f₁(ord), f₂(ord),...,f₁₃(ord). Ett ord godkänns bara om alla dessa 14 hashfunktioner samtidigt ger index till platser i tab som innehåller sant.

Uppslagning av ett ord kan då ske på följande sätt:

    for i in range(14):
       if not tab[f(i, ord)]: return False
    return True

Om hashtabellen är till hälften fylld med ettor blir sannolikheten för att ett felstavat ord godkänns så liten som (1/2)¹⁴=0.006%.

Denna datastruktur kallas bloomfilter efter en datalogiforskare vid namn Bloom. Ett abstrakt bloomfilter har bara två operationer: insert(x) som stoppar in x i datastrukturen och isIn(x) som kollar ifall x finns med i datastrukturen.

Programmet Stava kan köras på webben på http://www.nada.kth.se/stava/ (hjälp finns via webbsidan)

För den som tycker det här verkar intressant finns kursen DD2418, Språkteknologi.