RSA förklarat
Varje gång en webbläsare visar ett hänglås, ett meddelande signeras eller ett program kontrollerar en uppdatering är kryptografi med öppen nyckel i arbete, och RSA är dess mest kända form. Idén är att nyckeln som låser ett meddelande kan publiceras medan nyckeln som öppnar det förblir privat. Anmärkningsvärt nog vilar hela systemet på aritmetik som lärs ut i skolan: primtal, multiplikation och rester.
Problemet som RSA löser
Äldre chiffer, från Caesarchiffret till moderna AES, använder samma nyckel för att låsa och låsa upp, så de två parterna måste först dela en nyckel i hemlighet. Kryptografi med öppen nyckel tar bort det steget. Varje person har två nycklar: en öppen nyckel som vem som helst får använda för att kryptera ett meddelande till personen, och en privat nyckel som bara personen själv har och som ensam kan dekryptera det. Whitfield Diffie och Martin Hellman beskrev idén 1976, och ett år senare hittade Ron Rivest, Adi Shamir och Leonard Adleman vid MIT ett sätt att förverkliga den, som fick namnet RSA efter deras initialer.
Att skapa nycklarna
Välj två stora primtal, p och q, och multiplicera dem: n = p × q. Beräkna φ(n) = (p − 1)(q − 1), Eulers fi-funktion, som räknar de tal under n som inte har någon gemensam faktor med det. Välj en offentlig exponent e som inte har någon gemensam faktor med φ(n); 65537 är det vanliga valet. Hitta sedan den privata exponenten d så att e × d ger resten 1 vid division med φ(n). Utökade Euklides algoritm gör detta snabbt. Den öppna nyckeln är paret (e, n); den privata nyckeln är d. Med p = 61 och q = 53 ger detta n = 3233, φ(n) = 3120, e = 17 och d = 2753.
Kryptering och dekryptering
Ett meddelande görs först om till ett tal m som är mindre än n. För att kryptera det beräknar man c = mᵉ mod n, resten av mᵉ vid division med n. För att dekryptera beräknar man cᵈ mod n. Eulers sats garanterar att detta ger tillbaka m, eftersom e × d är 1 mer än en multipel av φ(n). Med nycklarna ovan blir bokstaven A, kod 65, till 65¹⁷ mod 3233 = 2790, och 2790²⁷⁵³ mod 3233 = 65 igen. Så stora potenser skrivs aldrig ut: upprepad kvadrering beräknar dem med en kvadrering per bit i exponenten och tar resten i varje steg.
Digitala signaturer
RSA fungerar också baklänges. Att upphöja ett meddelande till den privata exponenten, s = mᵈ mod n, ger en signatur som bara nyckelns ägare kan skapa. Vem som helst kan kontrollera den med den öppna nyckeln: om sᵉ mod n ger tillbaka m kom meddelandet från innehavaren av d och ändrades inte på vägen. I praktiken är det en kort hash av meddelandet som signeras snarare än själva meddelandet. Signaturer av det här slaget skyddar programuppdateringar, säkra webbplatser och elektroniska dokument.
Varför det är säkert
Alla kan se n och e. För att hitta d behöver en angripare φ(n), och för att hitta φ(n) krävs p och q, så att knäcka RSA handlar i grunden om att faktorisera n. Att multiplicera två primtal tar en dator en bråkdel av en mikrosekund; att dela upp produkten i dem igen anses vara extremt svårt. Det största RSA-utmaningstalet som hittills har faktoriserats, RSA-250 år 2020, har 829 bitar och krävde omkring 2700 års datortid. Nycklar som används i dag har minst 2048 bitar, ungefär 617 siffror.
En hemlighet som upptäcktes två gånger
År 1973, fyra år före RSA, hittade den brittiske matematikern Clifford Cocks samma system när han arbetade vid underrättelsetjänsten GCHQ, med utgångspunkt i en idé från sin kollega James Ellis. Arbetet var hemligstämplat och offentliggjordes först 1997. RSA patenterades i USA 1983; patentet löpte ut i september 2000, två veckor efter att algoritmen hade släppts som allmän egendom.
RSA i praktiken
Riktig RSA krypterar aldrig text direkt. Meddelandet fylls ut med slumpmässiga byte enligt ett schema som OAEP, så att samma meddelande krypteras olika varje gång och inga mönster kan läcka ut. Eftersom RSA är långsamt används det mest för att utbyta eller skydda en kort nyckel för ett snabbt symmetriskt chiffer som AES, eller för att signera. Tillräckligt stora kvantdatorer skulle kunna faktorisera n snabbt med Shors algoritm från 1994, vilket är varför nya postkvantmetoder nu införs vid sidan av RSA.
Utforska det
Öppna RSA-krypteringsdemon för att bygga nycklar av dina egna primtal eller av slumpmässiga primtal med 2 till 8 siffror, se utökade Euklides algoritm hitta d rad för rad, kryptera eller signera ett meddelande tecken för tecken och följa den upprepade kvadreringen för valfritt tecken. Låt sedan Eve faktorisera n och se hur tiden hon behöver växer med primtalens storlek.
Ofta ställda frågor
Varför behöver RSA primtal?
Eftersom φ(n) bara är lätt att beräkna när man vet hur n delas upp i primtal. För n = p × q med p och q primtal är φ(n) = (p − 1)(q − 1). Primtal gör också n så svårt som möjligt att faktorisera för sin storlek, eftersom det inte har några små faktorer alls.
Varför är e ofta 65537?
65537 = 2¹⁶ + 1 är ett primtal och har bara två ettor binärt, så kryptering med det kräver bara 16 kvadreringar och en multiplikation. Det är också tillräckligt stort för att undvika svagheter hos mycket små exponenter som 3.
Vad är skillnaden mellan RSA och Diffie–Hellman?
Diffie–Hellman låter två personer komma överens om en gemensam hemlig nyckel över en öppen kanal; den krypterar eller signerar ingenting i sig. RSA krypterar och signerar direkt med ett nyckelpar. Båda vilar på problem som är lätta åt ena hållet och svåra åt det andra: faktorisering för RSA, den diskreta logaritmen för Diffie–Hellman.
Kan demons nycklar användas för riktig kryptering?
Nej. Dess primtal har högst ett dussin siffror, så varje nyckel den skapar kan faktoriseras på några sekunder eller mindre, och den krypterar varje tecken för sig utan utfyllnad. Den är till för att visa hur RSA fungerar, inte för att skydda något.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna RSA-krypteringsdemon