Vad är RSA-kryptering och hur fungerar det?

Vad är RSA-kryptering?

RSA står för Rivest-Shamir-Alderman, vilket är en kombination av algoritmens skapares efternamn. Den presenterades för första gången 1977 av dessa tre professorer medan de arbetade på Massachusetts Institute of Technology (MIT). Bara några år tidigare 1973 hade den engelska matematikern Clifford Cocks upptäckt ett liknande system medans han arbetade för den Brittiska underrättelsetjänsten Government Communications Headquarters (GCHQ), men datorerna som krävdes var på den tiden alldeles för dyra för att det skulle vara rimligt.

Precis som andra asymmetriska krypteringsalgoritmer för end-to-end-kryptering, använder RSA en publik nyckel för att kryptera meddelanden och en privat nyckel för att dekryptera dem. Matematiken som ligger till grund för systemet använder en enkelriktad funktion, det vill säga en funktion som är trivial att beräkna, men svår att sedan med ett givet funktionsvärde hitta de input-värden som gav upphov till det. Mer matematiskt beskrivet är det lätt att beräkna värdemängden, men svårt (kombinatoriskt) att med ett givet tal från värdemängden hitta det korresponderande värdet i definitionsmängden. Det är detta matematiska lås som lägger grunden för RSA-kryptering och som gör brute force-attacker praktiskt omöjliga.

Hur fungerar RSA-kryptering?

RSA-kryptering är en form av asymmetrisk kryptografi och kräver därför både publika och privata nycklar. Den publika nyckeln används för att kryptera meddelandet. Det vill säga, omvandla ett meddelande från klartext till chiffertext. Publika nycklar kan delas öppet utan problem.

Med den privata nyckeln är det annorlunda. Den används för att dekryptera ett krypterat meddelande. Meddelandet som den publika nyckeln omvandlat från klartext till chiffertext omvandlar alltså den privata nyckeln tillbaka till klartext från chiffertext. Hela systemet bygger på att den privata nyckeln hålls hemlig, så denna måste de som använder systemet se till att skydda.

Men vad är då symmetrisk kryptering?

Om man vet hur asymmetrisk kryptering fungerar, kanske det inte är så svårt att gissa sig till hur ett motsvarande symmetriskt krypteringssystem fungerar. Symmetrisk kryptering använder samma nyckel, närmare bestämt en privat sådan, för att kryptera och dekryptera meddelanden. Symmetrisk kryptering är ett utmärkt alternativ så länge man har möjlighet att säkert dela nyckeln med personen man planerar att kommunicera med i förväg. Om man inte har möjlighet att genom en säker kanal utbyta denna nyckel i förväg, lämpar sig asymmetrisk kryptering bättre.

Generering av nycklar

Asymmetrisk kryptering består av fyra väsentliga delar. Först och främst genereras en publik och privat nyckel, därefter sker ett utbyte av nycklar mellan interlokutörer genom en speciell algoritm. När nu underlaget för säker kommunikation etablerats kan kryptering och dekryptering av meddelanden ske per automatik. Det är inte mycket svårare än så egentligen, men låt oss i vilket fall som helst gå in lite mer i detalj. Vi börjar med hur generering av nycklar går till.

Val av primtal (p och q)

Ett underlag för att krypteringen över huvud taget ska vara säker, är att primtalen som slumpvist väljs för nyckelgenerering är tillräckligt stora och distinkta. Här snackar vi inte lite stora. Om du tar 2048-bitars RSA-kryptering som exempel, måste man ta fram primtal som består av 308 siffror. Dessa hisnande stora primtal är inte lätta att ta fram, men som tur är finns det matematiker som tagit fram effektiva primtalstest.

Multiplicera p och q (n)

Den första delen av din publika och privata nyckel består av produkten av p och q. Denna biten kanske känns trivial, men det är väsentligt att det är en praktisk omöjlighet att gissa vilka tal som ingick i multiplikationen. Om du bara känner till n, ska du inte kunna härleda p och q.

Låt oss ta ett exempel som visserligen inte är helt korrekt eftersom talen är alldeles för små, men som illustrerar den bakomliggande principen. Om p = 7013 och q = 3331 blir n = p q = 23 360 303. Det är enkelt att beräkna med en vanlig miniräknare. Däremot krävs det att man använder speciella metoder för att härleda vilka tal som ingick i skapandet av produkten. Det är svårare att gå från definitionsmängd till värdemängd än värdemängd till definitionsmängd. Algoritmen är beräkningsmässigt mer komplex.

Talen ovan är alldeles för små för att kunna användas som underlag för kryptering – det kan du kontrollera själv genom att sätta in produkten vi tog fram i ett program eller algoritm som letar fram faktorer – men försök att lista ut produkten när 308-siffriga primtal används (2048-bit RSA). Det är omöjligt – och bra det! Annars hade det inte varit mycket till krypteringsalgoritm.

Generera publik nyckel (e)

När vi har tagit fram den första delen av vår publika nyckeln, är det dags att slutföra generationen genom att ta fram talet e. Detta är helt enkelt ett tal som uppfyller följande kriterier:

1. 1.e och (p-1)(q-1) är relativt prima (1 är den största gemensamma delaren).
2. 2.e är högre än 1, men mindre än (p-1)(q-1)

Vanligtvis används talet e = 216+1 = 65 537 för RSA-kryptering. Man kan få bättre prestanda genom använda små tal, men detta har visat sig vara mindre säkert i vissa omständigheter.

Generera privat nyckel (d)

I det sista steget fullbordas den privata nyckeln genom att talet d genereras. Talet måste uppfylla ed 1 (mod (p-1)(q-1)) och med detta kriterium kan man beräkna d genom att använda euklides algoritm.

Begreppet “mod” i ovanstående ekvation står för modulo och är en operation som beskriver rest efter division. Likamedtecknet med en extra linje är kongruens. På vardera sida av detta tecken har du två tal som får samma rest vid division med talet inom parentesen som står efter mod. Uttrycket ovan beskriver att vänsterled är kongruent med högerled.

När vi är klara med detta steg har vi vårt slutresultat. Den publika nyckeln består av n och e, och den privata består av d. Självklart måste d hållas hemlig, men även p och q måste skyddas eftersom de användes för att generera d.

Distribuering av nycklar

Om man nu vill använda RSA-kryptering för att kommunicera – låt oss till exempel säga att någon vill skicka ett meddelande till dig – måste de känna till din publika nyckel. Det som är bra med den publika nyckeln är att du inte behöver tänka på att den delas under säkra förhållanden. Du behöver inte känna att du lämnar känslig information när du ger ut en publik nyckel. Syftet med den är ju att den är publik!

Kryptering

Låt oss nu säga att personen du vill kommunicera med fått din publika nyckel, det vill säga e och n som vi beskrev ovan och att han eller hon nu vill skicka ett meddelande! Men vad är det egentligen som händer med det? Vad är skillnaden mellan ett meddelande som skickas med RSA-kryptering och ett som skickas utan? Om vi låter C representera chiffertexten, och M meddelandet i klartext, beskriver följande ekvation förhållandet: C = Me (mod n)

Det kanske verkar lite konstigt att text används i en ekvation på det här sättet, men i datatekniska sammanhang kan man alltid anta att text går att omvandla till nummer. Ta ASCII som exempel. Meddelandet “Hej, jag gillar dig.” blir “072 101 106 044 032 106 097 103 032 103 105 108 108 097 114 032 100 105 103 046” i ASCII – om man bortser från alla mellanrum.

Dekryptering

Nu har vi egentligen redan gått igenom det tekniskt komplexa i processen. Att dekryptera ett meddelande C är nu mycket enkelt. Du applicerar den privata nyckeln på följande funktion för att kunna läsa ordinarie meddelande M: M = Cd (mod n)

Kom ihåg att din privata nyckel består av d och n. Detta konverterar chiffertexten tillbaka till klartext. Kryptering låter mer tekniskt invecklat än vad det är. Någonting är inte säkert bara för att algoritmerna är komplexa. RSA är säkert eftersom det är kombinatoriskt omöjligt (eller väldigt svårt!) att knäcka resulterande chiffertext.

Hur används RSA-kryptering?

Eftersom RSA-kryptering använder publika nycklar är det en lämplig metod för att säkert skicka information till personer eller servrar du inte haft tidigare kontakt med. Symmetrisk kryptering kräver ju som sagt att man delat sin privata nyckel med personen eller enheten man vill kommunicera med i förväg. Därför är det vanligt att RSA-kryptering används inom webbläsare, e-postklienter, molntjänster, VPN -tjänster, chatapplikationer och andra sorters kommunikationsmetoder där “främlingar” är mottagare.

Hur kommer det sig att en så gammal metod som RSA-kryptering fortfarande används? Har det inte hänt någonting sedan 1977? Självklart har saker och ting inte stått stilla. RSA-kryptering står inte längre på sina egna två ben, utan brukar kombineras med andra sorters krypteringsmetoder. Det är till exempel vanligt att använda RSA för att kryptera den initiala delningen av den privata nyckeln i ett symmetriskt krypteringssystem.

RSA används faktiskt främst för att upprätta säker uppkoppling och för att skapa digitala signaturer. När det kommer till att kryptera specifika meddelanden eller filer som överförs finns det betydligt mer effektiva, snabbare, säkrare och mer sofistikerade krypteringsmetoder och system.

Upprätta säker uppkoppling

RSA har många år på ryggen och har således använts i många olika syften. RSA var faktiskt den första algoritmen som användes inom PGP-kryptering för att kryptera sessionsnycklar.

Webbläsare använder till exempel RSA-kryptering för att skapa en säker uppkoppling. Detta förhindrar avlyssning av internettrafik och MITM-attacker och säkrar användarens integritet mot den simplaste typen av attacker.

RSA sköter dock sällan själva trafiken, utan detta använder man mestadels SSL för. Vanligt är att RSA sköter SSL/TLS handshakes, det vill säga den initiala kontakten. Lite som vi beskrev ovan.

OpenVPN är ett kommunikationsprotokoll för VPN-tjänster där kommunikationen mellan användarklient och server använder RSA-kryptering för att upprätta kontakt. Själva trafiken som överförs använder dock andra krypteringsmetoder. NordVPN använder till exempel AES-256-GCM för att se till så att all data som överförs är säkrad.

Skapa digitala signaturer

Din privata RSA-nyckel kan användas för att signera meddelanden såväl som dokument. Andra parter kan därefter använda din publika nyckel för att verifiera att meddelandet kommer från dig och är autentiskt. E-postmeddelanden signeras till exempel med PGP-kryptering som använder RSA-algoritmen för att skapa digitala signaturer.

För- och nackdelar med RSA-kryptering

Även om fördelarna är många med RSA-kryptering så finns det givetvis även ett par nackdelar.

Fördelar:

• RSA-kryptering är enkel att förstå, mångsidig och smidig att implementera. Algoritmen är inte speciellt invecklad och beräkningarna behöver inte nödvändigtvis kräva stora resurser.

• Algoritmen används och har använts i många system genom åren. Metoden är alltså beprövad. Ingenting klarar sig så länge i IT-världen utan resultat.

• RSA-kryptering är omöjligt att knäcka. Till och med med dagens beräkningskapacitet går det inte att utföra en brute force-attack för att knäcka krypteringen. Det återstår att se om detta håller framöver, men RSA-kryptering kommer förmodligen att finnas kvar en bra tid framöver.

Nackdelar:

• Det är väsentligt att nycklar som RSA genererar är tillräckligt långa. 2048-bit RSA har till exempel nycklar som består av 308 siffror. Att generera nycklarna kan därmed vara beräkningsmässigt kostsamt. Om RSA implementeras på fel sätt är det dessutom en ganska utsatt metod.

• Eftersom allt fler publika RSA-nycklar genereras, blir det över tid lättare för hackers att hitta sätt att bryta krypteringen.

• Dekryptering tar lång tid och kräver förhållandevis stora resurser.

RSA-algoritmens sårbarheter

Säkerheten som RSA kan erbjuda varierar beroende på hur väl den har implementerats. Det är en känslig process där varje steg kan leda till minskad eller äventyrad säkerhet.

Otillräckligt bra slumptal

Första delen i RSA-algoritmens process består av att välja primtal. Om primtalen som genereras inte är tillräckligt bra slumpade, är det mycket enklare att knäcka krypteringen. Slumptalsgeneratorer är ett brett ämne som vi rekommenderar att du efterforskar på egen hand om du är intresserad av RSA-kryptering.

Felinställd generering av nycklar

Även om du har en bra slumpgenerator kan det vara så att primtalen är för små eller för lika varandra. Eftersom RSA-kryptering är asymmetrisk och därmed har en publik nyckel, är nyckelns storlek viktig att tänka på. Ju större primtalen är desto svårare är det att generera dem. Om talen som genereras dessutom ligger för nära varandra på tallinjen, kommer den privata nyckeln bli alldeles för liten. Nya implementationer av RSA använder ganska stora nyckelstorlekar på 4096-bit. Ju större desto bättre – men också desto dyrare. Nyckeln ska dock alltid vara så stor som möjligt.

Attacker riktade mot RSA-kryptering

Det är viktigt att vara medveten om vilka sorters attacker RSA-kryptering utsätts för.

Faktorisering

RSA-kryptering bygger på att primtalen p och q inte kan upptäckas. Om primtalen ligger för nära varandra, om de är för små eller inte tillräckligt bra slumpade, kan en potentiell hacker helt enkelt faktorisera dem för att på så sätt få tag på den privata nyckeln.

Side-channel attack

En side-channel attack är en attack där angriparen analyserar information som dekrypteringsprocessen lämnar efter sig. Istället för att direkt försöka knäcka krypteringen, kollar man till exempel på saker som hur mycket ström algoritmen använder eller hur lång tid det tar för olika chiffertexter att dekrypteras. På så sätt kan angriparen göra mer informerade knäckningsförsök.

Klartext

Om en angripare lyckas gissa delar av klartextsvarianten av meddelandet, kan detta användas för att utföra olika sorters attacker. Om man vet vad en del av ett visst meddelande innehåller, kan man dra en koppling mellan detta och chiffertexten. Informationen som utvinns här kan sedan användas för att härleda resten av meddelandet

Är RSA-kryptering säkert?

Hur säker RSA-kryptering är beror helt och hållet på hur väl det har implementerats. Om man ser till att nyckeln är framställd på rätt sätt, finns det ingen anledning att oroa sig. Experter rekommenderar att man använder minst 2048-bit RSA eftersom man redan börjat upptäcka svagheter med till exempel 1024-bit RSA. Även om enbart en liten andel av dessa visat sig vara enkla att knäcka, är det inte värt risken. En krypteringsmetod som fungerar till 99% är värdelös.

Hur ser framtiden ut för RSA-kryptering?

Även om RSA-kryptering fortfarande används, ser framtiden inte speciellt ljus ut för veteranalgoritmen. Det är en teoretisk och praktiskt omöjlighet för RSA att knäckas med vanliga datorer, men kvantdatorer verkar lovande. Självklart kan man inte förutse någonting konkret på den här fronten ännu, men experter inom kryptering nämner ofta teknologins potential.

Enligt den amerikanska myndigheten National Institute of Standards and Technology (NIST), kommer 2048-bit nycklar endast vara säkra att använda fram till 2030 och 4096-bit nycklar bara något längre än så. Tyvärr är det inte riktigt beräkningsmässigt rimligt att generera större tal. Användning av RSA verkar alltså inte ha någon framtid. Det är en ganska ineffektiv och kostsam metod om man jämför med andra system som finns. I skrivande stund är det dock fortfarande en ytterst kapabel algoritm.