Nycklarna
Så hittas d: utökade Euklides algoritm
Varje rad dividerar de två raderna ovanför. I raden med resten 1 är den sista kolumnen d (lägg till φ(n) om den är negativ).
| Kvot | Rest | Koefficient för e |
|---|
Meddelandet
Skickas över nätet
| Bit | Kvadrera | Multiplicera med m |
|---|
Att knäcka nyckeln
RSA-krypteringsdemo
Med RSA kan vem som helst låsa ett meddelande med din öppna nyckel, medan bara du kan låsa upp det med din privata nyckel. Bakom det ligger några rader skolaritmetik: två primtal, en multiplikation, en rest och en listig invers. Bygg ett nyckelpar av primtal du själv väljer, kryptera och dekryptera ett meddelande tecken för tecken, signera det så att vem som helst kan kontrollera att det kom från dig, och spela sedan angripare och faktorisera n för att se varför riktiga nycklar behöver hundratals siffror. Välj två primtal p och q, eller tryck på Nya primtal. Appen bygger den öppna nyckeln (e, n) och den privata nyckeln d och visar hur utökade Euklides algoritm hittar d. Skriv ett meddelande: varje tecken krypteras med den öppna nyckeln och dekrypteras med den privata nyckeln. Klicka på en rad för att se potensen beräknad med upprepad kvadrering. Byt till Signera för att i stället signera med den privata nyckeln, och tryck på Faktorisera n för att se hur snabbt små nycklar knäcks.
Hur det fungerar
- Ange två primtal p och q, eller välj en storlek och tryck på Nya primtal; appen beräknar n, φ(n), e och d och visar hur d hittas.
- Skriv ett meddelande och välj Kryptera eller Signera. Varje tecken görs om till ett tal och upphöjs till en potens mod n; klicka på en rad för att se den upprepade kvadreringen.
- Tryck på Faktorisera n för att låta Eve dela upp n i dess två primtal och återskapa den privata nyckeln.
Hur nycklarna fungerar
Multiplicera två primtal: n = p × q. Med p = 61 och q = 53 blir n = 3233. Talet φ(n) = (p − 1)(q − 1) = 3120 räknar de tal under n som inte har någon gemensam faktor med det, och det kan bara beräknas av den som känner till p och q. Välj e = 17, som inte har någon gemensam faktor med 3120, och hitta d så att e × d är 1 mer än en multipel av φ(n): här är d = 2753, eftersom 17 × 2753 = 46801 = 15 × 3120 + 1. Publicera (e, n) och behåll d. Ett meddelande m blir c = mᵉ mod n, och Eulers sats garanterar att cᵈ mod n ger tillbaka m.
Varför det är svårt att knäcka
Allt en angripare behöver är gömt i faktorerna i n. Med n = 3233 är det inget skydd: att pröva udda delare hittar 53 efter ungefär två dussin försök. Men arbetet växer med kvadratroten ur n. En modul på 2048 bitar har ungefär 617 siffror, och ingen känd metod, på någon dator som finns i dag, kan faktorisera den på rimlig tid. Signering kör RSA baklänges: s = mᵈ mod n kan bara skapas med den privata nyckeln, och vem som helst kan kontrollera att sᵉ mod n ger tillbaka m.
Ofta ställda frågor
Varför kan ingen beräkna d ur den öppna nyckeln?
För att hitta d behöver du φ(n) = (p − 1)(q − 1), och för att få φ(n) behöver du p och q. Att återskapa dem ur n innebär att faktorisera det, och för tal med hundratals siffror känner man inte till någon snabb metod. Demon låter dig faktorisera leksaksnycklar på en bråkdel av en sekund, vilket visar precis varför riktiga nycklar är så stora.
Varför krypteras meddelandet ett tecken i taget?
Eftersom leksaksnycklarna är små: RSA kan bara kryptera ett tal som är mindre än n. Med n = 3233 får varje teckenkod plats, men en hel mening skulle inte få det. Riktig RSA använder en modul på 2048 bitar eller mer, fyller ut meddelandet med slumpmässiga byte så att samma meddelande aldrig krypteras på samma sätt två gånger, och krypterar i praktiken bara en kort nyckel för ett snabbare chiffer som AES.
Vad gör upprepad kvadrering?
Den beräknar enorma potenser som m²⁷⁵³ mod n utan att någonsin skriva ner det enorma talet. Skriv exponenten binärt och gå sedan igenom dess bitar: kvadrera det löpande resultatet för varje bit och multiplicera med m för varje etta, och ta resten mod n varje gång. En exponent på 2048 bitar kräver bara ungefär 2048 kvadreringar.
Vad är skillnaden mellan att kryptera och att signera?
Kryptering använder mottagarens öppna nyckel, så att bara mottagarens privata nyckel kan häva den. Signering använder avsändarens privata nyckel, så att vem som helst kan kontrollera signaturen med avsändarens öppna nyckel och veta att meddelandet kom från innehavaren av den nyckeln och inte har ändrats.
Skickas mitt meddelande någonstans?
Nej. Allt beräknas i din webbläsare, och dina primtal och ditt meddelande sparas i den här webbläsarens lokala lagring.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor