Datakryptering och pålitlig identifiering av personer är nödvändigt på webben. Till exempel försäkrar internetbanksanvändning med HTTPS-protokoll att uppgifterna överförs i krypterat format och att endast den rätta personen har tillgång till dem. Utan pålitlig kryptering kan en tredje part läsa meddelandet under resan.
RSA är ett allmänt använt sätt att utbyta krypterad information. RSA utvecklades av Ron Rivest, Adi Shamir och Leonard Adleman år 1977.
Asymmetrisk kryptering
Det här är idén med asymmetrisk kryptering:
Anna vill ta emot hemliga meddelanden.
Anna skapar en offentlig nyckel och en hemlig nyckel. Med den offentliga nyckeln kan man kryptera meddelanden och med den hemliga nyckeln kan man dekryptera dem.
Anna skickar den offentliga nyckeln till alla som behöver den (det gör inget om hela världen kan se den).
Ville får den offentliga nyckeln och använder den för att kryptera sitt meddelande till Anna.
Ville skickar ett krypterat meddelande till Anna.
Anna får Villes meddelande. Det kan enbart öppnas med en privat nyckel, så endast Anna kan läsa Villes meddelande.
Hela korrespondensen kan ske helt offentligt, men informationen är säker så länge den hemliga nyckeln är gömd.
Situationen kan jämföras med ett kassaskåp som Anna skickar olåst till Ville och som han kan stänga, låsa och skicka tillbaka; Anna har den enda nyckeln.
RSA:s funktion
RSA fungerar på följande sätt: Först väljer man heltalen $e$, $d$ och $n$ så att \[ (v^e)^d \equiv v \quad (\textrm{mod} \ n) \] gäller för alla heltal $v$ (Detta är möjligt, vi återkommer senare till hur det fungerar.) Talens roll är som följer:
talparet $e$ och $n$ bildar den offentliga nyckeln
talet $d$ den hemliga nyckeln
Ville skickar ett meddelande till Anna på följande sätt: Först omvandlas det verbala meddelandet till heltal $v$ på något sätt (Till exempel a = 10, b = 11, c = 12,...). I det här skedet kan man öka säkerheten med en komplex konvertering, till exempel med OAEP-metoden.
Sedan krypterar Ville meddelandet. Det krypterade meddelandet $s$ är resten av talet $v^e$ när man dividerar med talet $n$. Alltså gäller \[ v^e \equiv s \quad (\textrm{mod} \ n). \] Det krypterade meddelandet $s$ skickas till Anna, som kan dekryptera det genom att beräkna resten av talet $s^d$, som divideras med talet $n$. Eftersom talen $n$, $e$ och $d$ har valts lämpligt, är resultatet det ursprungliga meddelandet: \[ s^d \equiv (v^e)^d \equiv v \quad (\textrm{mod} \ n). \]
Algoritmen kan förmedla talen $v$ om meddelanden om de är mindre än talet $n$.
Exempel 1
En fungerande (om än med tanke på säkerheten alldeles för liten) trio till RSA-algoritmen är $n=143$, $e=7$, $d=103$.
Meddelandet $v$ kan vara vilket icke-negativt heltal som helst som är mindre än $n$, till exempel $v = 123$. Krypterat är det \[v^e = 123^7 \equiv 7 \quad (\textrm{mod} \ 143 ). \] Det krypterade meddelandet $s$ är alltså enbart talet 7. Meddelandet kan dekrypteras genom att beräkna \[s^d = 7^{103} \equiv 123 \quad (\textrm{mod} \ 143 ). \]
Att beräkna modulär exponentiering med datorn går mycket snabbt med en lämplig algoritm. Till exempel med Python-språket kan beräkningarna utföras med kommandot pow(v,e,n), som returnerar resten av talet $v^e$ modulo $n$.
n = 143
e = 7
d = 103
# Meddelande:
v = 123
# Kryptering
s = pow(v,e,n)
# Dekryptering
dekrypterat_meddelande = pow(s,d,n)
Exempel 2
Ett verbalt meddelande kan skickas genom att byta ut bokstäverna mot siffror till exempel genom att använda ASCII-koder. Följande tabell används för omvandlingen:
kod
tecken
kod
tecken
kod
tecken
032
mellanslag
105
i
114
r
097
a
106
j
115
s
098
b
107
k
116
t
099
c
108
l
117
u
100
d
109
m
118
v
101
e
110
n
119
w
102
f
111
o
120
x
103
g
112
p
121
y
104
h
113
q
122
z
På så här sätt kodas till exempel meddelandet pengarna är på vinden i formatet
$$v = 114 097 104 097 116 032 111 118 097 116 032 117 108 108 097 107 111 108 108 097.$$ Man använder talen
Det krypterade meddelandet är resten av talet $v^e$ modulo $n$, och det kan räknas till exempel med Python-koden
n = 145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053
e = 65537
d = 89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713
v = 114097104097116032111118097116032117108108097107111108108097
s = pow(v,e,n)
varav det är mycket svårt att gissa det ursprungliga meddelandet. Meddelandet kan dekrypteras genom att beräkna resten av talet $s^d$ modulo $n$, varpå resultatet är det ursprungliga meddelandet $v$.
Uppgift 1
Olöst
Gör ett program, som använder talen $n = 143$, $e = 7$ och $d = 103$. Programmet ska kryptera meddelandet $42$ och skriva ut det krypterade meddelandet.
Skriv ditt program här:
Uppgift 2
Olöst
Gör ett program, som använder talen $n$, $e$ och $d$ i exempel 2. Det krypterade meddelandet är följande:
s = 85428277862587239591968124579786099007709414278223047737899318765259424056436086074826093092150818499345040297473507839007632632095558200735189531211857679546669771791600041613523605832579335482328444517404371063136115723068982913626804303813782231498500488302844347689387955529396562717610808940562862565420
Skriv ett program, som skriver ut det dekrypterade meddelandet i siffror på en rad och meddelandet tolkat i text på en annan rad. Du kan omvandla siffrorna till text antingen direkt i koden eller för hand med tabellen i exempel 2.
Skriv ditt program här:
RSA:s detaljer
Generering av nycklarna
Varifrån får vi talen $n$, $e$ och $d$? Processen är följande:
Vi väljer två stora primtal $p$ och $q$ (Helst av nästan samma storlek.)
Vi beräknar $n = p\cdot q$
Vi beräknar $\lambda (n) = \textrm{pym}(p-1, q-1)$ ($\lambda (n)$ är Carmichael-funktionen, vars egenskaper inte behövs i denna sats, annat än att $\lambda(n)$ är delbar med talen $p-1$ och $q-1$.)
Vi väljer $e$ så att $1 < e < \lambda (n)$ och $\textrm{syt}(e, \lambda (n))=1$. Vanligtvis $e$ är relativt liten, till exempel primtalet $2^{16}+1=65537$.
Talet $d$ löser vi ur ekvationen $d\cdot e \equiv 1 \left(\textrm{mod} \ \lambda (n) \right) $. Ekvationen är i formatet $ed-k\lambda(n)=1$, dvs. i formen $ax+by=c$, vilket gör att den har en lösning när $\textrm{syt}(e, \lambda (n))=1$.
RSA:s säkerhet
I princip är det enkelt att knäcka RSA-kryptering: man behöver endast dividera talet $n$ i sina delare $p$ och $q$ och lösa den hemliga nyckeln $d$ ur ekvationen $ed \equiv 1 \left(\text{mod } \lambda (n) \right)$. Det tar emellertid en lång stund att dela upp stora tal i delare. I RSA-kryptering används numera nycklar, vars längd är mellan 1 024 och 4 096 bit i det binära talsystemet. Av dessa är 4 096 bit år 2021 helt utom räckhåll för datorernas egenskaper. Kvantdatorer kan ändra spelet. Det har inte fastställts att inte RSA i allmänhet skulle kunna knäckas även med en enklare metod än genom att dividera $n$ i sina delare. Det finns emellertid inga bevis på detta. Några kända problem är emellertid:
Om $p$ och $q$ är av samma storlek, ska $n$ snabbt delas upp i delare. (Fermats stora sats)
Om talen $p-1$ och $q-1$ endast har små primfaktorer, kan $n$ snabbt delas upp i delare. (Pollards $p-1$-algoritm)
Om den hemliga nyckeln $d$ är för liten, kan den utredas effektivt med talen $e$ och $n$.
Om talen $p$ och $q$ har valts med en dålig pseudoslumptalsgenerator, kan två offentliga nycklar $n$ ha samma delare $p$. Det vill säga $n_1 = pq_1$ och $n_2=pq_2$. I detta fall kan man knäcka båda krypteringarna genom att beräkna SGD$(n_1,n_2) = p$.
Eftersom vem som helst kan kryptera meddelanden med den offentliga nyckeln, är det möjligt att prova hur sannolika meddelanden ser ut när de är krypterade. Dessa kan jämföras med det verkliga meddelandet och på så sätt kan man få fram dess innehåll. För att skydda meddelandet mot detta omvandlas det till talet $v$ på ett komplext och slumpmässigt sätt. Redan att lägga till några slumpmässiga tecken i slutet av meddelandet hjälper mycket.
Bevis på RSA:s funktion
För beviset behövs Fermats lilla sats som hjälpresultat:
Fermats lilla sats
När $p$ är ett primtal, gäller \[ a^p \equiv a \quad (\textrm{mod} \ p ). \] Satsen kan även formas så här: När $p$ är ett primtal där $a$ inte är delbart, \[ a^{p-1} \equiv 1 \quad (\textrm{mod} \ p ). \] Den övre formen följer den nedre genom att multiplicera till hälften med talet $a$ och undersöka separat fallet $a\equiv 0 (\textrm{mod} \ p)$.
Bevis för Fermats lilla sats
$p$ är ett primtal och $a$ ett tal, som inte är delbart med $p$. Vi undersöker talen \[ a, \ 2a, \ 3a, \ \ldots ,\ (p-1)a. \] Vi påstår att dessa tals rester modulo $p$ är alla olika stora. Så här måste det vara, för om det är $ma = na \ (\textrm{mod} \ p ) $ borde det vara $p|(ma-na)$, dvs. $p|a(m-n)$. Eftersom $p$ inte dividerar talet $a$, måste det vara $p|(m-n)$, men detta är möjligt endast när $m=n$, eftersom $m$ och $n$ är mindre än talet $p$. Resterna är alltså olik stora.
Resterna av talen $a, \ 2a, \ 3a, \ \ldots ,\ (p-1)a$ är alltså (i någon ordning) $1, \ 2, \ 3, \ \ldots ,\ (p-1)$. Vi kan skriva \[ a\cdot 2a \cdot 3a \cdot \ldots \cdot (p-1)a \equiv 1\cdot 2 \cdot 3 \ldots \cdot (p-1) \quad (\textrm{mod} \ p ), \] dvs. \[ a^{p-1}\cdot (p-1)! \equiv (p-1)! \quad (\textrm{mod} \ p ). \] Eftersom $(p-1)!$ inte kan vara delbart med primtalet $p$, det kan reduceras bort och vi får \[ a^{p-1} \equiv 1 \quad (\textrm{mod} \ p ). \quad _\Box \]
Lemma om rester
Vi säger att $p$ och $q$ är tal, som inte har gemensamma delare.
Påstående: Om $a \equiv r \ (\textrm{mod} \ p) $ och $a \equiv r \ (\textrm{mod} \ q) $, gäller $a \equiv r \ (\textrm{mod} \ pq) $
Bevis: På basis av antaganden $a = mp +r$ och $a = nq + r$. Genom att subtrahera dessa från varandra får vi $0=mp-nq$, dvs. $mp = nq$. Talet $mp$ är alltså delbart med talet $q$, och eftersom SGD$(p,q)=1$, måste det vara $m=kq$. Alltså \[a = mp +r = kqp +r, \], dvs. $a \equiv r \ (\textrm{mod} \ pq).$
Själva beviset
Påståendet är att för alla tal $v$ gäller \[(v^e)^d \equiv v \quad (\textrm{mod} \ n) \] alltid när \[n=pq \quad \textrm{ja} \quad ed \equiv 1 \ \ (\textrm{mod} \ (p-1)(q-1) ), \] där $p$ och $q$ är primtal.
Beviset är följande:
Eftersom $ed \equiv 1 \ \ (\textrm{mod} \ \textrm{pym}(p-1)(q-1))$, talet $ed - 1$ är delbart med talen $(p-1)$ och $(q-1)$.
Vi kan alltså skriva $ed-1 = k(q-1)$ och å andra sidan $ed-1 = r(p-1)$.
Vi vill nu bevisa $(v^e)^d \equiv v \ \ (\textrm{mod} \ n )$. För att konstatera detta räcker det med att kontrollera att $(v^e)^d \equiv v \ \ (\textrm{mod} \ p )$ och $(v^e)^d \equiv v \ \ (\textrm{mod} \ q )$ (se. lemma om rester).
Fallet $v \equiv 0 \ \ (\textrm{mod} \ p )$ är klart, eftersom med stöd av räknereglerna för kongruens även $(v^e)^d \equiv 0 \ \ (\textrm{mod} \ p )$.
Om däremot $v \not\equiv 0 \ \ (\textrm{mod} \ p )$, kan vi skriva \[ (v^e)^d = v^{ed} = v^{ed-1}\cdot v = v^{r(p-1)}\cdot v =(v^{p-1})^r\cdot v \equiv 1^r\cdot v \equiv v \ \ (\textrm{mod} \ p ).\] Mellanformen $v^{p-1} \equiv 1 \ \ (\textrm{mod} \ p )$ följer Fermats lilla sats.
Motsvarande resonemang visar att $(v^e)^d \equiv v \ \ (\textrm{mod} \ q )$.
Eftersom $(v^e)^d \equiv v \ \ (\textrm{mod} \ p )$ och $(v^e)^d \equiv v \ \ (\textrm{mod} \ q )$, gäller $(v^e)^d \equiv v \ \ (\textrm{mod} \ n )$. $_\Box$