Matematiska institutionen
Avd matematik

Stockholms universitet		 Matematisk lusttur 5p
Orienteringskurs
Hösten 2003    www.math.su.se/lusttur/

Föreläsning 11
En dag blev det mest onyttiga nyttigt – kryptering, talteori och RSA

Tisdag 16 december 2003 kl 18.00-20.00
Clas Löfwall, clasmath.su.se
Johan Thorbiörnson, johanmath.su.se

Inlämningsuppgift:
Hemliga meddelanden till mig kodas enligt följande princip. Om meddelandet är x (där x är ett tal mellan 1 och 54) så skickas talet x3 modulo 55 till mig.

Någon skickar mig nu det kodade meddelandet 2. Vilket är det ursprungliga siffermeddelandet?

Senaste nytt (3 december 2003):
RSA Laboratories sponsrar sedan många år tävlingen Factoring Challenge of RSA Security som går ut på att faktorisera vissa mycket stora utvalda tal som är produkten av två ej angivna primtal. Nyligen lyckades en tysk forskargrupp faktorisera det 174-siffriga talet RSA-576. Metoder att faktorisera denna typ av tal gör RSA-koden osäker. Läs mer här »

Något om RSA-algoritmen
(Texten nedan är ett utdrag ur Förberedande kurs i matematik 5p, avsnitt A12 Fördjupning, se http://www.math.su.se/forb/)

Detta fördjupningsavsnitt bygger på resultat om primtalsfaktorisering och något om räkning med rester, så kallad resträkning eller moduloräkning » (eller kongruensräkning), samt det resultat som kallas Fermats lilla sats ».

 

KRYPTERING MED RSA

Det blir allt viktigare att kunna sända information via Internet på ett säkert sätt. Användningen av Internet till att sköta sina betalningar, sända digitala signaturer och elektroniska dokument ökar alltmer. Man kanske också inte har lust att alla ska kunna snoka och läsa den epost man skickar till kompisar eller arbetskamrater.

Kommentar

Ladda ner ditt eget PGP-program gratis

International PGP Home Page »

Läs mer om RSA på RSA Security Inc. »

Ett mycket vanligt program för kryptering är PGP (Pretty Good Privacy) som också kan kallas för Internets rövarspråk. Programmet bygger på världens idag mest kända krypteringsmetod RSA (uppkallat efter upphovsmännen Ron Rivest, Adi Shamir och Leonard Adelman som utvecklade algoritmen 1977). RSA är patentskyddat i USA men får användas fritt av privatpersoner. Många av de stora programvarujättarna använder RSA, t.ex. Microsoft, IBM, Adobe och Apple. RSA används bland annat också för att säkra de elektroniska nycklarna till den amerikanska kärnvapenarsenalen.

Teorin bakom RSA är relativt enkel och ger ett extremt säkert krypteringssystem. Metoden bygger på att det är mycket lätt att multiplicera två primtal men mycket krävande att faktorisera ett givet tal i sina primtalskomponenter (om de ingående primtalen är stora). Det finns idag inga effektiva metoder att faktorisera ett heltal i sina primtalskomponenter. Exempelvis är 7907 och 7919 två primtal och deras produkt beräknas lätt med ett fåtal räkneoperationer till 62615533, men att faktorisera detta tal skulle i princip kräva att man går igenom alla tänkbara primtalsfaktorer upp till och med talet 7907. För en modern PC så skulle det ta ca 5 år att faktorisera ett tal av storleken 10130 (d.v.s. ett tal med 130 siffror i 10-systemet).

Eftersom svårigheten att faktorisera ett tal växer snabbt med storleken på talet blir det extremt värdefullt att hitta metoder att faktorisera heltal som består av produkter av mycket stora primtal. Idag kan man faktiskt bli rik om man hittar smarta sådana metoder. Denna praktiska användning av primtal var det ingen som kunde förutse fram till 1960-talet. Sedan antikens dagar hade primtalsforskning varit ett exempel på något som totalt saknar praktisk tillämpning och som endast hade inom-matematiskt intresse. Ett populärt skämt var t.ex. att på dörren till fikarummet sätta upp en skylt med texten "Institutionen för primtalsforskning". Idag skulle man vara en mycket hipp och tidsmedveten person om man hade en sådan skylt till sitt arbetsrum. Den som hittar nya sätt att attackera befintliga kryptosystem blir snabbt mycket känd.

Kommentar

Hur skickade man hemliga meddelanden på diligensernas tid?
Antag att man vill skicka ett hemligt meddelande till en person genom att låsa in ett brev i en kista och skicka denna till personen. Problemet blir då att personen måste ha nyckeln till låset för att kunna läsa meddelandet. Och man vill inte gärna skicka nyckeln med kistan, för då kan vem som helst öppna låset och läsa meddelandet i kistan.

Lösningen blir att man skriver sitt meddelande, låser kistan, skickar kistan till mottagaren som sätter på ytterligare ett lås på kistan så att kistan får dubbla lås. Sedan returnerar mottagaren kistan till den ursprunliga avsändaren som nu kan låsa upp i sitt lås och skicka tillbaka kistan ännu en gång till mottagaren, som nu får tillbaka kistan igenlåst med bara ett lås som mottagaren själv har nyckel till.

RSA-algoritmen är ett exempel på ett s.k. "public key"-system, d.v.s. ett system med en offentlig nyckel, till skillnad från system med en hemlig nyckel som både avsändaren och mottagaren har utbytt i förväg och som bara de känner till. En offentlig nyckel är en smart lösning som gör det möjligt för två personer att skicka säkrade meddelanden emellan sig. Klassiska kryptosystem använder en och samma nyckel för kryptering och dekryptering. Om man använder ett sådant system så är problemet att hitta ett tillräckligt säkert sätt att överföra nyckeln till det krypto man använder, men då kunde man ju nästan lika gärna ha överfört meddelandet i sig. En offentlig nyckel innebär att varje person har två nycklar: en hemlig som man inte lämnar ut till någon och en offentlig som man lämnar ut överallt, t.ex. i slutet på alla sina e-postmeddelanden. Den som vill kommunicera säkert med en person tar denna persons offentliga nyckel som personen erbjuder offentligt, krypterar med RSA-algoritmen meddelandet till personen med hjälp av den offentliga nyckeln. Meddelandet kan nu bara dekrypteras med mottagarens hemliga nyckel som bara denne känner till. Den offentliga nyckeln kan allstå användas fritt av alla för att kryptera. Dekryptering kan endast ske med den hemliga nyckeln.

Klartexten till meddelandena som krypteras är heltal, vilket inte är någon inskränkning eftersom det är lätt att översätta godtyckliga symboler och bilder till talföljder innan man sätter igång och krypterar. Om vi vill sända ett textmeddelande med bokstäver ur det svenska alfabetet så kan vi t.ex. komma överens om att varje bokstav motsvaras av ett visst heltal. Man kan t.ex. låta bokstäverna A, B, C, D... i alfabetet representeras av tvåsiffriga heltal 11, 12, 13, 14, etc:
A B C D E F G H I J K L M ...  
11 12 13 14 15 16 17 18 19 20 21 22 23 ...  

I så fall skulle meddelandet

HEJ

representeras av heltalet

181519

Ett annat sätt är t.ex. att använda den vedertagna standarden ASCII (The American Standard Code for Information Interchange, uttalas på samma sätt som "ask-key" på engelska). Denna standard föreslogs 1963 och infördes slutligen 1968. Binärt använder man 7 stycken nollor och ettor, vilket ger talen från 0 till 127. Var och ett av dessa tal motsvarar ett tecken (bokstäver, siffror, interpunkteringstecken och specialtecken). The Extended ASCII Character Set bygger på 8 stycken ettor och nollor binärt och använder ytterligare 128 tal från 128 till 255 för att representera ytterligare matematiska och grafiska symboler samt diverse utländska bokstäver. I denna ASCII-kod representeras bokstäverna H, E, J av 072, 069 respektive 074.

Kommentar

Om modulo-räkning
I definitionen av variablerna till vänster så använder vi beteckningen

när vi menar att a och b bildar samma rest vid division med N. Vi utläser detta "a är kongruent med b modulo N". Exempelvis är

eftersom 8 och 5 bildar samma rest vid division med 3. Man kan räkna med kongruenstecken och de aritmetiska operationerna nästan som med vanligt likhetstecken.

Läs mer om moduloräkning här »

RSA-algoritmen arbetar med följande heltalsvariabler:

M = meddelandet (en följd av siffror som vi uppfattar som ett heltal)
N, k = offentliga nycklar (två heltal)
C = krypterat meddelande, , se kommentaren till höger
d = hemlig nyckel, ett heltal som uppfyller








Vi visar först med två exempel hur algoritmen går till innan vi förklarar teorin.

Exempel

Att sända ett hemligt meddelande
Antag att vi vill sända meddelandet M = 11 till vår kompis Olle. Vi kollar upp Olles offentliga nycklar och erhåller nycklarna

N = 35,
k = 5.

Olle har sin hemliga personliga nyckel d = 5.
Innan vi sänder vårt meddelande M så krypterar vi det genom att beräkna vilken rest talet 115 bildar vid division med 35:

och erhåller alltså det krypterade meddelandet C = 16 som vi sänder helt öppet till Olle, t.ex. via e-post.
Olle tar nu emot detta meddelande och dekrypterar det med hjälp av sin hemliga nyckel d = 5 som bara han känner till. (Vi ska sedan visa hur man kommer fram till dessa tal.) Olle beräknar nu vilken rest 165 bildar vid division med 35:

och erhåller helt korrekt det meddelande som vi sänt M = 11. Här använder vi skrivsättet att 1048576 är kongruent med 11 modulo 35. Med detta menas att 1048676 bildar resten 11 vid division med 35. Läs mer om kongruensräkning här »


Exempel

Ett hemligt meddelande med ett större tal
Vi använder nu lite större tal. Antag att vi vill sända meddelandet M = 1234 till Kalle som har de offentliga nycklarna

N = 2537
k = 11

Kalle har sin personliga hemliga nyckel d = 443.
Vi krypterar nu vårt meddelande M och får

Det kan tyckas att 123411 är ett väldigt stort tal och kräver enorma beräkningar, men beräkningarna ska bara ske modulo 2537 så faktum är att vi klarar av detta för hand. Vi använder då räknereglerna för moduloräkning som du kan läsa om moduloräkning här » .


Vi skickar alltså det krypterade meddalandet C = 1396 till Kalle. Kalle tar nu sin hemliga personliga nyckel d = 443 och beräknar

vilket stämmer, eftersom talet 1234 är samma som originaltexten vi skickade till Kalle.

I faktiska exempel är de tal man använder som nycklar betydligt större.

Hur fungerar RSA?

Vi ska nu förklara hur RSA fungerar. Algoritmen bygger på primtalsfaktorisering, Eulers phi-funktion och ett klassiskt teorem som kallas "Fermats lilla sats" (som är ett specialfall av "Eulers sats"). Algoritmen är följande:

  1. Välj två primtal p och q. Bilda talet N = pq. Man bör välja primtal som har en produkt som är större än de meddelande man kommer att vilja kryptera, se punkt 5 nedan.
  2. Beräkna talet . Vi betecknar detta tal . Detta är precis värdet av Eulers phi-funktion » för talet N ovan, d.v.s. .
  3. Välj ett tal k mellan 0 och , sådant att k och saknar gemensamma delare (d.v.s. sådant att ). För enkelhets skull kan vi välja k = 3, under förutsättning att vi väljer primtal i punkt 1 ovan sådana att inte är delbart med 3. Talen N och k blir de offentliga nycklarna. Dessa tal kan man dela ut till alla som vill ska kunna skicka meddelanden till dig.
  4. Beräkna talet d som den multiplikativa inversen till k modulo , d.v.s. beräkna ett heltal d sådant att , vilket med valet k = 3 innebär att . En lösning är , eftersom då blir

    Talet d blir den personliga hemliga nyckeln, och detta tal behåller du själv för att kunna dekryptera de meddelanden som du får. Talet d uppfyller alltså att kd bildar resten 1 vid division med . Allmänt för andra val av k än talet 3 så är det möjligt att bestämma d så att t.ex. med hjälp av den så kallade Euklides algoritm.
  5. Om en användare vill skicka ett krypterat meddelande så låter man meddelandet i klartext representeras av heltalet M (alltså en följd av siffror som kanske egentligen betyder en följd av bokstäver). Talet M måste vara mindre än talet N = pq som man valt i punkt 1. Kryptering sker nu genom att använda talen k och N (de offentliga nycklarna) ovan och beräkna talet C :

  6. Talet C är det krypterade meddelandet. Detta kan skickas helt öppet till dig och kan dekrypteras med hjälp av talet d som bara du känner till. Med hjälp av talet d kan man beräkna vilken rest Cd bildar vid division med N. Denna rest är precis M (som är meddelandet i klartext i punkt 5 ovan), , se förklaringen nedan.

Kommentar

Sammanfattning av kryptering/dekryptering med RSA

  1. Välj två primtal p och q sådana att varken p — 1 eller q — 1 är delbara med 3. Bilda talet N = pq.
  2. Beräkna talet .
  3. Välj k = 3. Talen N och 3 blir de offentliga nycklarna. Dessa tal kan man dela ut till alla som vill ska kunna skicka meddelanden till dig.
  4. Beräkna talet . Talet d blir den personliga hemliga nyckeln, som används för dekryptering.
  5. Ett meddelande i form av heltalet M krypteras genom att beräkna talet C :
  6. Talet C är det krypterade meddelandet. Med hjälp av talet d kan mottagaren beräkna vilken rest Cd bildar vid division med N. Denna rest är precis M (som är meddelandet i klartext i punkt 5 ovan):

Hur man räknar modulo N kan du läsa här »

Att beräkna meddelandet i klartext

Vi har sett i punkt 1-6 ovan hur man tar fram sina offentliga nycklar (N och k) samt sin personliga nyckel d. Vi ska nu se hur man kan få tillbaka klartexten M från det krypterade meddelandet C via den hemliga nyckeln d genom att beräkna vilken rest Cd bildar vid division med N. Denna rest är klartexten M. Förklaringen ser man i följande kalkyl:

Vi använder här att modulo N, där N = pq. Detta följer ur följande resultat:

Fermats lilla sats:
För varje heltal a och varje primtal p gäller att ap — a är delbart med p.

(Läs om resultatet och dess bevis i A12 Fördjupning Fermats lilla sats » )

Hur ser man då att modulo N följer från Fermats lilla sats? Låt oss göra en kalkyl, men vi behöver först formulera om Fermats lilla sats till följande form:

Fermats lilla sats (alternativ formulering):
För varje primtal p och varje heltal a som inte är delbart med p gäller att ap — 1 — 1 är delbart med p.

Detta kan också uttryckas

Vi kan nu med hjälp av detta resultat få

    (*)

under förutsättning att M inte är delbart med p. På samma sätt, under förutsättning att M inte är delbart med q, så får vi

    (**)

Kommentar

Varför är omformuleringen av Fermats lilla sats sann?
Antag att a inte är jämnt delbart med p. Vi vet att Fermats lilla sats gäller, d.v.s. att ap — a är delbart med p. Detta betyder det att ap — a är en multipel av p. Alltså gäller att ap — a = mp för något heltal m. Vi kan faktorisera ut talet a i vänsterledet och får a(ap — 1 — 1) = mp. I vänsterledet och högerledet står två heltal som är lika. Talet i högerledet är delbart med p. Då måste p gå jämnt upp även i vänsterledet. Eftersom p är ett primtal så följer då från Aritmetikens fundamentalsats » (resultatet om entydig faktorisering) att p måste gå jämnt upp i antingen faktorn a i vänsterledet eller faktorn ap — 1 — 1. Men vi har antagit att a inte är jämnt delbart med p. Alltså går p jämnt upp i ap — 1 — 1.

Om M uppfyller förutsättningarna att varken vara delbart med p eller q, så är alltså enligt (*) och (**) talet delbart med både p och q och således delbart med produkten pq. Detta är samma sak som att

(mod pq )

vilket var det vi behövde för att beräkna klartexten ovan » och få . Men detta gäller alltså bara under förutsättning att meddelandet M varken är delbart med p eller q. Vi måste också reda ut vad som gäller om M vore delbart med p eller med q. Eftersom vi bara krypterar meddelanden M som är mindre än pq så kan inte M vara delbart med både p och q utan högst en av dem. Vi kan därför anta att M är delbart med p, men ej med q. Fallet att M är delbart med q men ej med p behandlas på samma sätt.

Vi ska visa att

d.v.s. att är delbart med pq. Vi skriver om uttrycket genom att bryta ut M och skriver detta

där vi ser att M är delbart med p enligt antagandet och att är delbart med q enligt antagandet att M ej är delbart med q, ty analogt med resonemanget i (**) gäller

Alltså är delbart med både p och med q och därför med produkten N = pq eftersom p och q är primtal. Vi har alltså visat att

om M är mindre än pq.

Vad är egentligen Eulers phi-funktion?

Eulers phi-funktion definieras allmänt som antalet positiva heltal mindre än n som är relativt primiska till n, d.v.s. antalet positiva heltal mindre än n som inte har några gemensamma delare med n. T.ex. får vi

Talen 1, 2 är relativt primiska till n = 3.
Talen 1, 2, 3, 4, 5, 6 är relativt primiska till n = 7.
Talen 1, 5 är relativt primiska till n = 6.

Hur beräknar man ?
För vissa specialfall finns enkla metoder. Om p är primtal så gäller

Om p och q är primtal så kan man visa att

Läs mer om RSA på RSA Security Inc. »

Om modulo-räkning

Om man ställer frågan
—"Hur mycket är klockan?"

så kan man exempelvis få svaret

—"Klockan är tre."

Om man ställer samma fråga nästa dag vid samma tid på dygnet eller efter en vecka vid samma tid på dygnet

—"Hur mycket är klockan?"

så får man samma svar

—"Klockan är tre."

Det är alltså ingen skillnad på om klockan är tre en dag eller om klockan är tre en annan dag. Vid midnatt har klockan nått fram till 24.00. Då börjar man räkna från 00.00 tills man har nått fram till 24.00 igen nästa midnatt och då börjar man om från 00.00 igen, o.s.v.

Den egenskap vi frågar efter är hur många timmar som gått, fast bara i förhållande till varje multipel av 24. Matematiskt så frågar vi alltså efter resten vid division med 24. Vi skulle kunna beskriva detta genom att säga att tiden är klockan 3 modulo 24.

Mycket i detta avsnitt bygger på modulräkning. Vi skriver

som utläses "a är kongruent med b modulo n" och menar då att a och b bildar samma rest vid division med n. Detta innebär att för något heltal c.
a och b har samma rest vid division med n.

Man kan räkna med kongruenstecknet på ungefär samma sätt som vanligt likhetstecken. Följande räkneregler gäller:

Om och så gäller

Exempel

Vi vet att och . Vi får alltså

Exempel

Räkneregeln för multiplikation kan användas till att beräkna potenser. Eftersom så gäller

Talet 9285 är ett väldigt stor tal (det har 271 siffror i 10-systemet). Vi kan ändå lätt med hjälp av räkneregeln för multiplikation i kongruensräkning lätt räkna ut vilken rest talet bildar vid division med 10, d.v.s. vilken den sista siffran i talets representatione är i 10-systemet:

Vi kan formulera några ytterligare räkneregler.

Om och och om K = minsta gemensamma multipeln till m och n så gäller

Speciellt gäller att om p och q är primtal att minsta gemensamma multipeln till p och q är pq. Därför följer från ovanstående räkneregel:

Om p och q är primtal så gäller och

Man kan också visa följande strykningslag (ungefär som vid vanlig aritmetik):

Om p är ett primtal och om så gäller