Föreläsning 5: Kryptering, datasäkerhet

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.

Rollista:

  • Alice som vill skicka ett meddelande till Bob
  • Bob som vill få meddelandet från Alice (oläst)
  • Eve (av engelskans eavesdrop - tjuvlyssna) som försöker avkoda meddelandet

Transpositionschiffer

I det antika Grekland användes en scytale Länkar till en extern sida. - en dekrypteringspinne för att avkoda hemliga meddelanden skrivna på en remsa skinn. Avsändaren (Alice) och mottagaren (Bob) 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 för Eve, som har statistik över hur ofta varje bokstav förekommer i det aktuella språket. Så här ser det ut för svenska:

stapel

Bokchiffer

I Sir Arthur Conan Doyles The Valley of Fear Länkar till en extern sida. knäcker Sherlock Holmes ett bokchiffer.

Det är ett enkelt men mycket effektivt chiffer där man använder en bok som nyckel. Man letar rätt på ordet i boken och skriver ner sidnummer samt ordets nummer på sidan, t ex

534 13 127 220 10 109 220 129

Den ena siffran anger sidan och den andra anger vilket ord på sidan det är.  Alice och Bob måste i förväg ha kommit överens om vilken bok det gäller utan att Eve hör.

One-time pad

One-time pad är en oknäckbar krypteringsmetod som använder sig av en slumpad nyckel.

Givet ett meddelande på binär form:

  • Slumpa fram en nyckel med lika många binära siffror som meddelandet har
  • Gör bitvis xor mellan meddelandet och nyckeln (operatorn ^ i Python)

    0^0 =

    0

    0^1 =

    1

    1^0 =

    1

    1^1 = 

    0

Det resulterande kodade meddelandet kan bara dekrypteras av den som har den slumpade nyckeln.

Alice och Bob måste ha varsitt exemplar av en "pad" (ett block Länkar till en extern sida.) med slumpade siffror, som inte Eve har tillgång till.
Alice använder första sidan i sitt block för att kryptera ett meddelande och river sedan av första arket och förstör det.

meddelande   10010001010
nyckel 01010011110
-----------
krypterat 11000010100

Bob river av första sidan i sitt block och använder den för att dekryptera:


krypterat 11000010100
nyckel 01010011110
-----------
dekrypterat 10010001010

 

Säker nyckelöverföring (key exchange)

Alice vill skicka ett exemplar av blocket till Bob utan att Eve (som jobbar som brevbärare) kan kopiera det. Hur ska hon göra?

  1. Alice lägger blocket i en inbrottssäker låda och sätter sitt A-lås på det. Endast hon själv har A-nyckeln.
  2. Hon skickar lådan till Bob (Eve kan inte låsa upp den).
  3. Bob kan inte öppna lådan ännu. Han sätter på sitt B-lås. Endast Bob har B-nyckeln.
  4. Han skickar tillbaka lådan till Alice.
  5. Alice låser upp A-låset och plockar bort det. Nu är lådan enbart låst med B-lås.
  6. Hon skickar lådan till Bob, som låser upp den och får sitt block.

 

Symmetrisk kryptering

De krypteringsalgoritmer vi tittat på hittills är exempel på symmetrisk kryptering.

Vid symmetrisk kryptering har sändare och mottagare samma krypteringsnyckel. Det går i regel mycket fortare än asymmetrisk kryptering. Standarden idag är AES. Länkar till en extern sida.

 

Asymmetrisk kryptering

Ett problem med många chiffer är att man måste berätta för mottagaren hur hon ska dechiffrera meddelandet, dvs vilken nyckel som ska användas.

I asymmetrisk kryptering används nyckelpar. En publik och en privat nyckel hos vardera part. Man krypterar med mottagarens publika nyckel. Mottagaren dekrypterar med sin privata nyckel.

Bob har en publik och privat nyckel. Han lägger upp den publika på sin webbsida där alla kan se den (även Eve). Alice krypterar ett meddelande med Bobs publika nyckel och skickar meddelandet till Bob. Eve kan inte läsa det krypterade meddelandet, men Bob kan dekryptera det med sin privata nyckel.

 

Autentisering

Hur ska Bob veta att det verkligen är Alice som har skickat meddelandet?

Hon kan signera meddelandet genom att kryptera en sträng med sin egen privata nyckel innan hon skickar det till Bob. Bob kan sedan autentisera meddelandet genom att dekryptera denna sträng med Alice publika nyckel.

 

RSA

Krypteringsalgoritmen RSA (döpt efter Ron Rivest, Adi Shamir och Leonard Adleman som först publicerade den) är ett exempel på asymmetrisk kryptering. Du har 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 m1, m2 osv.

Sedan beräknar vi mie modulo n för att få de kodade delarna ci.

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

Här finns 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(Lk) 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.

 

Ovannämnda algoritmer är offentliga och man kan matematiskt verifiera att de fungerar. Det som är hemligt är nycklarna. 

 

Datasäkerhet

 

Lösenord

Lösenord bör inte sparas i klartext. Vi kan använda en hashfunktion för att konvertera till ett stort tal. Istället för att lagra lösenordet lagrar vi talet. En hashfunktion kan ge samma värde för två helt olika indata så det går inte att, givet hashvärdet, lista ut vilket det ursprungliga värdet var.

>>> hash("sesam")
-225076712
password["Ali Baba"] = -225076712

Då kan vi kontrollera lösenordet så här:

def checkPassword(username, password):
   if password[username] == hash(password) :
       return True
   else: 
       return False

 

Salt är en slumpad sträng (olika för varje lösenord) som slås ihop med lösenordet före hashningen. Saltet ger en längre sträng så vi får större variation i värdena som hashas in. Detta kompenserar för korta lösenord, och gör att identiska lösenord inte får samma hashvärde.

def storePassword(username, password):
   salt = randomString() #salt = "123£"!#¤!..."
   hashed_password = hash(password + salt)
password[username] = (salt, hashed_password)

 

Det finns bra och dåliga lösenord. Rekommendationer för bra lösenord varierar med tiden!

Här är de senaste förslagen från Microsoft Länkar till en extern sida..

https://xkcd.com/936/ Länkar till en extern sida.

Validera indata

Ett användarvänligt program berättar för användaren om indata är på fel format så att hen har chans att rätta till det. Men det finns ytterligare skäl till att validera inmatning innan den skickas vidare till programmet - det är en möjlig säkerhetsrisk.

Kontrollera t ex:

  • Indatas längd
  • Datatyp
  • Filformat (inte bara ändelsen)

 

Mer att läsa (och lyssna på)

 

https://xkcd.com/177/     Länkar till en extern sida.(+förklaring Länkar till en extern sida.)