Asymmetrisk kryptering

Asymmetrisk kryptering är en teknik inom kryptografi som innebär att man använder två olika nycklar: en offentligt tillgänglig nyckel för andra att kryptera med och en egen privat nyckel för dekryptering. Tekniken kan användas också för kryptografisk underskrift, varvid den publika nyckeln används för dekryptering, alltså verifiering. Dessa nycklar är matematiskt relaterade på ett sätt som gör att det tar lång tid att hitta den privata utgående från den öppna nyckeln. Genom tillräcklig nyckellängd kan man se till att den förväntade tiden att hitta nyckeln med nu kända metoder är hundratal år även med stor datorkapacitet.

Historia
Vid mitten av 1970-talet fick kryptologen Whitfield Diffie idén att använda en nyckel för att kryptera ett meddelande och en annan för att dekryptera det, till skillnad från alla tidigare kända krypteringsmetoder. Därmed kan den som vill kryptera något (i detta exempel kallad Alice) skapa två nycklar, en hemlig och en offentlig som alla har tillgång till. När någon skickar meddelanden till Alice använder de hennes öppna nyckel för att kryptera meddelandet, och den enda nyckel som nu kan dekryptera meddelandet är Alices privata, som ingen annan än hon själv känner till.

Diffie kände inte till något sätt att skapa och använda två sådana nycklar, men han tog ändå fram följande krav som en sådan algoritm måste uppfylla:

 Det är lätt att skapa ett nyckelpar (en öppen och en privat nyckel).
 Det är lätt för en avsändare att kryptera ett meddelande med mottagarens öppna nyckel.
 Det är lätt för mottagaren att dekryptera meddelandet med sin privata nyckel.
 Det är ogörligt för en annan part att utifrån den öppna nyckeln ta reda på den privata.
 Det är ogörligt för en annan part att utifrån den öppna nyckeln och ett krypterat meddelande dekryptera detta.

Vad han inte visste var att James Ellis på uppdrag av den brittiska underrättelsetjänsten redan "uppfunnit" denna typ av kryptering 1969 och att Clifford Cocks 1973 också funnit en lämplig algoritm. Datorernas begränsade kapacitet på 1970-talet gjorde att den brittiska militären inte kunde använda algoritmen; datorerna orkade inte. Idén hölls dock hemligt fram till slutet av 90-talet; det är fullt möjligt att även andra länders militära institutioner kommit på samma sak. Cocks algoritm upptäcktes återigen 1977 av den amerikanska forskartrion Ronald Rivest, Adi Shamir och Leonard Adleman, som kallade den RSA.

Praktisk användning
Öppen-nyckel-kryptering kräver mycket mer datorkraft och är långsammare än traditionell, symmetrisk kryptering. Detta beror på beräkningarna som utförs och de enorma tal som används. Därför väljer man oftast att inte kryptera stora meddelanden med denna metod – i exempelvis krypteringsprogrammet Pretty Good Privacy gör man istället så här:

 Avsändaren skriver ett meddelande och slumpar fram en engångsnyckel.
 Meddelandet krypteras med en symmetrisk algoritm (CAST-128, IDEA eller 3DES) med engångsnyckeln.
 Engångsnyckeln krypteras med en öppen-nyckel-algoritm (RSA eller ElGamal) med mottagarens öppna nyckel och bifogas meddelandet i krypterad form.

På så vis behöver man bara använda de kostsamma beräkningarna för att kryptera engångsnyckeln, som vanligtvis är mellan 40 och 256 bitar lång.

För att krypteringen skall uppfylla sitt syfte krävs dels att den privata nyckeln inte läcker ut, dels att den öppna nyckeln finns tillgänglig och säkert kan kopplas till rätt person. Dessutom måste engångsnycklarna och sättet nycklarna används på vara säkra.

Om en privat nyckel förvaras och används på en viss dator kommer den att vara lika utsatt för dataintrång (och operatörsmissbruk) som resten av informationen där. Om ett virus eller annan malware kommer åt att köra på datorn kan den som kontrollerar programmet i många fall kopiera nyckeln och därefter avkoda alla meddelanden han eller hon kommer över, eller underteckna texter i nyckelägarens namn. Motsvarande gäller den som har kontroll över datorn eller kommer över säkerhetskopior eller tillfälliga kopior av nyckeln. För att krypteringen skall erbjuda mer än viss tilläggssäkerhet måste nycklarna hanteras noggrant.

Eskalerande nyckelstorlekar
Vanliga storlekar på nycklar för symmetriska algoritmer som DES och AES är 100 till 200 bitar. För öppen-nyckel-algoritmer som RSA är nycklarna vanligen större, ofta 512–4096 bitar. En nyckel på 128 bitar kan beskrivas med 39 siffror jämfört med 617 siffror för en 2048-bitarsnyckel. Den mindre nyckelstorleken användes på 1990-talet i sammanhang där datorresurserna var begränsade, den större är vad som numera rekommenderas.

Skillnaden mellan nyckellängderna beror på att nyckellängden har olika betydelse. För en symmetrisk algoritm innebär nyckellängden 128 att det totala antalet möjliga nycklar är 2128. I genomsnitt måste en avlyssnare prova hälften av alla dessa nycklar innan den rätta nyckeln hittas, vilket alltså ger 2127 nycklar som måste testas innan meddelandet kan läsas. Om vi tänker oss att avlyssnaren hinner prova 100 miljarder nycklar per sekund – den ungefärliga hastigheten man kom upp i när DES knäcktes 1998 – skulle det ta omkring 5x1019 år, vilket motsvarar 3,6 miljarder gånger universums ålder. Trots att datorerna blir allt snabbare kan man i praktiken inte knäcka koden annat än genom svagheter i hur den används – eller genom eventuella svagheter i själva algoritmen. Sådana svagheter innebär ofta att man inte behöver undersöka alla dessa nycklar.

För att hitta rätt nyckel i öppen-nyckel-algoritmerna behöver man inte prova alla tal. RSA grundar sig på primtal, varför man bara behöver pröva sådana. Med hjälp av olika metoder att hitta primfaktorer kan man ganska effektivt räkna ut vilka tal som behöver prövas. Då primtal blir allt sällsyntare bland stora tal innebär en fördubbling av nyckellängden inte en lika stor ökning av de resurser som krävs för att knäcka den som för symmetriska nycklar.

RSA Security hade tidigare en tävling där varje knäckt nyckel ger en belöning i form av stora prispengar. Den största knäckta nyckeln var på 200 decimala siffror (666 bitar), vilket offentliggjordes i maj 2005. Tävlingen lades ner under 2007.

Så länge som matematikerna inte hittar ett snabbare sätt att finna primfaktorerna kommer RSA kunna motstå alla attacker – bara man kontinuerligt ökar nyckelstorleken i takt med att datorerna blir fler och kraftfullare. Då information skall hållas hemlig länge måste man dock räkna med den framtida beräkningskapaciteten. 

Kryptografi baserad på elliptiska kurvor bygger också på öppen-nyckel-idén men behöver inte lika långa nycklar. Dessutom räknar man med att elliptiska kurvor inte såsom RSA:s primtalsberäkningar enkelt kan beräknas med kvantdatorer.

Exempel på användning

Asymmetrisk kryptering kan dels användas för kryptering, dels för signering (underskrift):

Vid kryptering av en text krypterar man den text som skall hållas hemlig med en symmetrisk nyckel. Den symmetriska nyckeln krypteras med mottagarens öppna (offentliga) nyckel och bifogas den krypterade texten eller överförs på annat sätt. Endast den som känner den privata nyckeln, alltså mottagaren, skall då kunna dekryptera och läsa texten.

Vid signering av en text skapar man först ett kontrolltal (digest eller hash-värde) ur alla tecknen i texten med hjälp av en matematisk formel. Kontrolltalet krypteras med den egna privata nyckeln. Den som känner undertecknarens öppna nyckel kan avkryptera kontrolltalet och jämföra det med ett kontrolltal skapat direkt ur texten. Om de stämmer överens är texten undertecknad med den privata nyckeln. Annars är texten inte identisk, men man vet inte om skillnaden beror på triviala ändringar som uppkommit under överföringen (t.ex. olika radbrytning) eller om det är frågan om en förfalskning.

Exempel 1 – signering 

Avsändare:
    1. Brevtext:   Denna text har jag skrivit själv
    2. Räkna ut kontrolltal för brevtexten:        4e4329076ab5efa045a2
    3. Använd privat nyckel för signering - kryptera kontrolltalet
    4. Signatur/Krypterat kontrolltal:         56e2096af450071639cb67e0774a28

Mottagare:
    Brevtext:      Denna text har jag skrivit själv
    Signatur/Krypterat kontrolltal:            56e2096af450071639cb67e0774a28

    1. Avkryptera signatur med den publika nyckeln: 4e4329076ab5efa045a2
    2. Räkna ut kontrolltal för brevtexten:    4e4329076ab5efa045a2
    3. Är det samma kontrolltal? Ja!

Exempel 2 – kryptering 
Avsändare  
    1. Brevtext:       Denna text har jag skrivit själv och den är hemlig!
    2. Ta ett slumptal: 788237621773719970976235443
    3. Kryptera brevet med slumptalet:          kjdbchuewqqw¤3h<YtkUtre"hsaasl)hTgbsgtreyuIut6ext:
    4. Kryptera slumptalet med den publika nyckeln: 876a43fecc760fa757653309aebc9870
    5. Skicka det krypterade brevet och den krypterade symmetriska nyckeln till mottagaren

Mottagare
    Krypterat brev:   kjdbchuewqqw¤3h<YtkUtre"hsaasl)hTgbsgtreyuIut6ext:
    Krypterad nyckel: 876a43fecc760fa757653309aebc9870

    1. Avkryptera den symmetriska nyckeln med den privata nyckeln
    2. Brevets nyckel: 788237621773719970976235443
    3. Avkryptera brevet (symmetriskt): Denna text har jag skrivit själv och den är hemlig!
    Om man kan läsa brevet så gick det bra,
    annars var brevets nyckel eller det krypterade brevet fel, 
    eller så hörde inte den publika och privata nyckeln ihop.

Litteratur

Se även
 Public Key infrastructure bygger på asymmetrisk kryptering.
 Symmetrisk kryptering
 RSA

Kryptografi