Lovecard nu har DU 5-6 år på dej.... :wink:Ursprungligen postat av lovecard
RSA
Inledning
I dagens IT-samhälle, där datoriseringen och antalet Internetanvändare ständigt ökar, är säkerhet ett av de viktigaste nyckelorden. Kryptering har förekommit sedan urminnes tider, men det är kanske främst under det senaste århundradet som det har blivit allt viktigare. Kryptering är en bra metod för skydda sig mot de säkerhetsrisker som finns, men allteftersom utvecklingen går framåt ökar också kraven på krypteringsalgoritmerna.
RSA är en algoritm som är uppkallad efter upphovsmännen Rivest, Shamir och Adelman. Det är den bäst kända och mest använda krypteringsalgoritmen som bygger på asymmetrisk kryptering. Nedan följer en kort presentation om hur algoritmen är uppbyggd, samt hur den kan användas vid kryptering och dekryptering. Avslutningsvis kommer en diskussion om säkerheten i RSA.
Kort introduktion till RSA
RSA är ett public-key kryptosystem. Public-key kryptering bygger på att man använder sig av olika nycklar för kryptering respektive dekryptering. Detta ger en s.k. asymmetrisk kryptering.
Man använder sig av en publik nyckel för kryptering och en privat nyckel för dekryptering. Vem som helst kan använda den publika nyckeln för att kryptera ett meddelande, men det är endast mottagaren som har tillgång till motsvarande dekrypteringsnyckel (den privata nyckeln), som kan läsa meddelandet.
Krypteringen i RSA går till på så sätt att man tar två stora primtal (helst över 512 bitar) och multiplicerar dessa. Att generera två primtal är lätt, men däremot är det oerhört svårt att finna de två primtalen ur deras produkt. Säkerheten i RSA bygger på just detta faktum - att faktorisering av stora tal är väldigt komplext.
RSA-systemet används i många olika produkter, plattformer, och industrier runt om i världen. Algoritmen är inbyggd i operativsystem av Microsoft, Apple, Sun och Novell. Man hittar den även i hårdvara som exempelvis nätverkskort och s.k. smartcards. Algoritmen finns också inbyggd i alla stora protokoll för säker kommunikation över Internet, t.ex. S/MIME och SSL.
Algoritmen
RSA-algoritmen bygger på matematikens stora gåta - primtalen. Det har bevisats att det finns oändligt många primtal. De primtal som används vid krypteringen kan vara hundrasiffriga.
Matematiken bakom RSA är ganska avancerad. I grunden bygger den på Eulers talteorem, men innan vi går in på teoremet kan en förklaring av Eulers funktion underlätta.
Eulers funktion
f(n) är antalet heltal t, där 1 ‹ t ‹ n, sådana att sgd(t,n) = 1
Exempelvis är f(6) = 2 eftersom sgd(t,6) = 1 och 1 ‹ t ‹ 6 för t = 1 och t = 5
Eulers teorem
af(n) = 1 mod n, där a och n är relativa primtal
Vi tänker inte härleda beviset bakom teoremet, utan bara visa ett litet exempel för att förtydliga formeln ovan (för den intresserade finns beviset i kapitel 8 i Stallings bok).
Välj två relativa primtal exempelvis a = 3 och n = 10.
f(10) = 4 ; 34 = 81 = 1 mod 10
Nyckelgenerering
Här nedan beskrivs RSA-algoritmen i olika steg för att generera nycklarna.
1. Välj två stora primtal p, q
2. Beräkna produkten n = p * q
3. Beräkna Eulers n, f(n) = f (p) * f (q) = (p-1)(q-1)
4. Välj e så att sgd(f(n), e) = 1 ; 1 < e < f(n)
- (e och f(n) är relaterade primtal d.v.s. e och f(n) har gemensamma delare som är 1)
5. Beräkna d, en multiplikativ invers modulo f(n), d * e - 1 = mod f(n) eller
d * e = 1 mod f(n) d.v.s. (d * e) mod f (n) = 1 => d = (1+ k f (n) / e) för något k
6. Publik nyckel blir KU = {e, n}
7. Privat nyckel blir KR = {d, n}
För att kryptera och dekryptera meddelanden med nycklarna från RSA-algoritmen används följande krypteringsformel:
Kryptering
klarttext M < n
chiffertext C = Me (mod n)
Dekryptering
chiffertext C
klarttext M = Cd (mod n)
Exempel på RSA-kryptering
Ett meddelande som är M = 6 ska krypteras.
1. Nyckelgenerering
För enkelhets skull väljer vi små primtal för att genera nycklarna.
· p = 5
· q = 11
· n = 5 * 11 = 55
· f(n) = (5-1) * (11-1) = 40
· välja e = 3 >> sgd(40,3) = 1;
· d = 27 (d * 3 – 1 är delbart med 40 >> d = (1 + k*40) /3 >> d = 27)
· publik nyckel KU {3, 55}
· privat nyckel KR {27, 55}
2. Kryptera meddelandet
C = 63 mod 55 = 51
klartext M = 6 krypteras till chiffertext C = 51
3. Dekryptera meddelandet
M = 5127 mod 55 = 6
Chifftertext C = 51 dekrypteras till klartext M = 6
Sändaren använder mottagarens publika nyckel (e , n) för att kryptera ett meddelande och mottagaren använder sin privata nyckel (d , n) för att dekryptera meddelandet. Således måste båda veta värdet n.
Säkerheten i RSA
Om man vill knäcka RSA-systemet så finns det några olika alternativ för detta. Det som vore mest skadligt är om en angripare lyckas hitta den privata nyckeln (n, d) som hör ihop med en publik nyckel (n, e). Lyckas man med detta kan man både läsa alla meddelanden som krypteras med den publika nyckeln och generera falska signaturer.
Ett sätt för att hitta en privat nyckel är genom en s.k. ”brute force” attack, vilket innebär att man testar alla möjliga nycklar tills man finner den rätta. Även här är det bästa försvaret att använda stora nycklar.
Det finns flera möjliga matematiska attacker på RSA-algoritmen – alla med den gemensamma nämnaren att man försöker hitta faktorerna p och q till ett primtal n.
Produkten n av primtalen är allmänt känd eftersom den är en del av den publika nyckeln. Har man p, q och e kan man lätt räkna fram d.
Det finns inga garantier mot att nya, effektivare algoritmer för primtalsfaktorisering konstrueras, men detta är ett av de svåraste matematiska problemen i världen. Men så länge man använder en tillräcklig storlek på nycklarna så är säkerheten i kryptosystemet inte hotad.
RSA Laboratories har utlyst en tävling som går ut på att faktorisera ett antal tal i storleksordningen 576 bitar till 2048 bitar. I dagsläget är det största talet man har lyckats faktorisera på 512 bitar, vilket man lyckades med i augusti 1999. Nästa år förväntar man sig att det går att faktorisera 576-bitars värden. Däremot så tror man att det dröjer flera årtionden innan man lyckas faktorisera 2048-bitars tal.
Att man har lyckats faktorisera ett tal innebär inte att användare genast behöver ersätta sina nuvarande nycklar med större nycklar, eller att de bör sluta använda RSA. Att man lyckats faktorisera ett tal ger endast en uppfattning om hur mycket arbete som krävs för att knäcka ett visst par av nycklar.
Som exempel kan vi tänka oss att år 2010 klarar man av att faktorisera ett 768-bitars tal om man under sex månaders tid har tillgång till 100 000 datorer. Om datan som ska skyddas endast behöver skyddas en kort tid och om dess värde är mycket mindre än kostnaden för att använda 100 000 datorer under den här perioden så kan man fortsätta använda 768-bitars nyckeln ett tag till. Om man däremot behöver skydda datan under en längre tid så ska man välja en större storlek på nyckeln.
Nedan visas en tabell som innehåller ungefärliga värden på hur mycket resurser som krävs för att faktorisera ett tal om man har ett år till förfogande. Kolumnen för antal datorer visar hur många Pentium 500 MHz maskiner (eller dyl.) som behövs. Minneskolumnen visar hur mycket minne som krävs i varje dator.
Tallängd (bitar)
Antal datorer
Minne
430
1
trivial
760
215,000
4 Gb
1020
342,000,000
170 Gb
1620
1.6 x 1015
120 Tb
Förutom ”brute force”-attacker och matematiska attacker finns det ytterligare en metod för att hitta en privat nyckel – genom s.k. timingattacker. För att hitta en privat nyckel kan man se hur lång tid en dator behöver för att dekryptera meddelanden. Detta kan jämföras med att man försöker gissa låskombinationen till ett kassaskåp genom att man tittar hur lång tid det tar att ”ratta in” varje siffra.
Användning av RSA i praktiken
RSA-systemet brukar ofta användas tillsammans med secret-key kryptosystem, som exempelvis DES, för att kryptera ett meddelande. Om en person vill skicka krypterade meddelanden så görs först en kryptering med DES där man använder en slumpmässig nyckel. Därefter används mottagarens publika nyckel för att kryptera DES-nyckeln. Dekryptering av ett meddelande görs genom att man först dekrypterar DES-nyckeln med den privata nyckeln, och därefter används denna nyckel för att dekryptera själva meddelandet. RSA-systemet kan även användas för autentifiering och digitala signaturer.
Sammanfattning
I dagsläget finns det mycket digital information som ska skyddas eller verifieras som autentisk. RSA kan användas för att kryptera och dekryptera data, men det finns fler användningsområden som exempelvis signering av meddelanden. RSA-kryptosystemet har ett stort användningsområde, eftersom säkerhetskraven ständigt ökar i och med nya tjänster som erbjuds på Internet.
RSA-kryptosystemet bygger på att man multiplicerar två primtal, och säkerheten i RSA bygger på svårigheten att faktorisera talet. Som vi har beskrivit ovan så är RSA relativt säkert så länge man använder tillräckligt stora nycklar. Förmodligen kommer RSA att finnas kvar ganska många år framöver eftersom RSA är det mest använda krypteringssystemet som är asymmetriskt. Jämfört med symmetrisk kryptering så är det långsammare, men med dagens datorkraft är det inget större problem. Nya krypteringssystem utvecklas hela tiden som är snabbare och effektivare t.ex. 3DES, AES. Man kan fråga sig varför RSA har funnits så länge? Jo, förmodligen eftersom RSA använder olika nycklar vid kryptering och dekryptering, vilket är en bra egenskap ur säkerhetssynpunkt, samt att RSA är en väl fungerade krypto-algoritm.
Om man finner en effektivare faktoriseringsalgoritm än de som finns i dagsläget, måste man sluta använda RSA då? Eller räcker det om man hela tiden ökar nyckelstorleken? Det finns många frågor som i dagsläget inte kan besvaras, men forskning pågår hela tiden för att finna svaren.
