Den hälsosamme ekonomisten

Hur fungerar asymmetrisk kryptering?

När man talar om kryptering tänker de flesta på symmetriska krypton. Symmetriska krypton innebär att man använder samma nyckel för att kryptera som för att dekryptera ett meddelande. En enkel form av symmetrisk kryptering är att ersätta varje bokstav med en annan bokstav.

Men hade det bara funnits symmetriska krypton skulle mycket av dagens Internet inte fungerat. Vi hade haft svårt att utföra banktransaktioner, eftersom sådana hade krävt att användaren och banken på förhand kommit överens om vilken krypteringsnyckel som ska användas. Dessutom måste den nyckeln på något sätt föras över mellan användaren och banken - och hur gör man det om man inte från början har en säker förbindelse?

För ungefär 50 år sedan upptäcktes den asymmetriska krypteringen. Den i dag vanligaste metoden för att genomföra asymmetrisk kryptering är genom att utnyttja svårigheten att faktorisera tal som är produkten av två primtal.

Rent matematiskt är det lätt att multiplicera två tal. Det kan exempelvis vara talen p=23 och q=41, som är två primtal. Produkten av dessa tal är 943, något som till och med går att räkna ut för hand. För en dator går det givetvis ännu snabbare.

Så - vad har dessa primtal med kryptering att göra? Jo, antag att frågan som ställs i stället är: Vilka är dessa två tal? Den frågan är inte lika lätt att besvara, även om det finns ett svar. Vi kan kalla numret 943 för den publika nyckeln. Den som ska ta emot meddelandet väljer också en annan siffra, e, som inte får vara delbar med samma tal som (p-1)(q-1)=880 (förutom givetvis med "1"). Båda dessa siffror sänds i klartext till den person som sedan ska skicka meddelandet.

Vi antar att meddelandet i det här fallet är M=35 (kanske en ASCII-kod som motsvarar ett "A"). Avsändaren beräknar värdet av C=M^e(mod N)=35^7(mod 943)= 545. "Mod" är förkortning för "modulus", alltså resten när man dividerar med i detta fall 943. Numret 545 sänds till mottagaren.

För att mottagaren ska kunna avkoda meddelandet måste hen hitta ett tal som uppfyller villkoret: ed=1(mod((p-1)(q-1)))==>7d=1(mod 880). Lösningen på det problemet är: d=503. För att återfå meddelandet räknar man ut 545^503(mod 943), vilket blir 35. Det finns en genväg, så man behöver inte räkna ut det väldigt stora talet 545^503.

För att rekapitulera: Det som händer är alltså följande: Person A som ska ta emot ett meddelande väljer ut två primtal; p och q. Sedan väljer personen också ut ett annat tal, e, som inte har någon gemensam faktor med (p-1)(q-1) (talen är relativa primtal). Produkten av p och q utgör tillsammans med e den publika nyckeln, men eftersom ingen annan vet vilka talen p och q är går det inte att räkna ut (p-1)(q-1).

Den som ska skicka meddelandet använder de två publika talen 943 och 7 för att kryptera meddelandet. När det väl är gjort går det inte att med hjälp av den publika nyckeln återskapa meddelandet (försök gärna om ni inte tror mig). Formeln är som nämnts M^7(mod 943). Talet skickas till mottagaren som vet om att primtalen är 23 och 41 och därmed att (p-1)(q-1)=880. Hen kan därför återställa meddelandet genom att lösa ekvationen 7d=1(mod 880). När detta är gjort och mottagaren vet att d=503 beräknar hen 545^503(mod 943), vilket ger 35.

Enkelt, eller hur? Det här är bara ett sätt att utforma asymmetriska krypton, men det allra vanligaste. I regel krypterar man bara en symmetrisk nyckel (en så kallad sessionsnyckel) med det asymmetriska kryptot, eftersom det går ganska långsamt annars. Sedan krypteras själva meddelandet med den symmetriska nyckeln. Det finns dock i dag betydligt snabbare metoder än RSA, varav en del ännu inte används i kommersiella sammanhang.

Kommentarer