Relationen $\equiv_n$ är en ekvivalensrelation i mängden $\Z$ och delar $\Z$ i ekvivalensklasser som kallas kongruens- eller restklasser och dessa är mängderna
$\{\ldots,\;\phantom{-n+1,\;\;}\llap{-n,\;\;} \phantom{n-1,\;\;}\llap{0,\;\;} \phantom{2\cdot n-1,\;} \llap{n,\;} \ldots\}$,
$\{\ldots,\;\phantom{-n+1,\;\;}\llap{-n+1,\;\;} \phantom{n-1,\;\;}\llap{1,\;\;} \phantom{2\cdot n-1,\;}\llap{n+1,\;} \ldots\}$,
$\quad\vdots$
$\{\ldots,\;\phantom{-n+1,\;\;}\llap{-1,\;\;} \phantom{n-1,\;\;}\llap{n-1,\;\;} \phantom{2\cdot n-1,\;}\llap{2\cdot n-1,\;} \ldots\}$,
i vilka alla element är kongruenta med varandra modulo $n$.
Följande beteckningar används när $n>0$: $$[k]_n =\set{m\in \Z\mid m\equiv_n k} =\set{m\in \Z\mid \Mod(m,n)=\Mod(k,n)}, \\ \Z/n\Z = \set{[k]_n: k=0,1,2,\ldots,n-1}.$$

Obs! [+]

Eftersom $\Mod(m_1,n)=\Mod(m_2,n)\leftrightarrow [m_1]_n=[m_2]_n$ så väljs ofta elementet $\Mod(m,n)$ till representant för restklassen $[m]_n$ så att man tex. kan prata om talen $0,1,2,\ldots,5$ som element i mängden $\Z/6\Z$ i stället för mängderna $[0]_6, [1]_6,\ldots,[5]_6$. Ibland skriver man $\overline k_n$i stället för $[k]_n$ och $\Z_n$ i stället för $\Z/n\Z$.

Man kan visa att ifall $$a_1\equiv_n a_2 \quad \text{och}\quad b_1\equiv_n b_2$$ så gäller $$\begin{align*} & (a_1+b_1)\equiv_n (a_2+b_2) \\ & (a_1-b_1)\equiv_n (a_2-b_2) \\ & (a_1\cdot b_1)\equiv_n (a_2\cdot b_2) \end{align*}$$ Därför kan man definiera räkneoperationer mängden $\Z/n\Z$ på följande sätt: $$\begin{align*} & [a]_n+[b]_n=[a+b]_n,\\ & [a]_n-[b]_n=[a-b]_n,\\ & [a]_n\cdot [b]_n= [a\cdot b]_n,\\ & [a]_n^j = [a^j]_n, \quad j\in \N_0, \end{align*}$$ och alla "normala" räkneregler (bortsett från de som behandlar olikheter) är fortfarande i kraft.

Exempel [+]

Stämmer det att $3\,|\, 5742385242417$ dvs. delar $3$ talet $5742385242417$?
Svaret är jakande eftersom summan av siffrorna i talet $5+7+4+2+3+8+5+2+4+2+4+1+7$ är delbart med $3$.
En varför gäller den här regeln? [+]

• I decimaltalssystemet avses med talet $x_nx_{n-1}\ldots x_1x_0$ talet $$m=x_n\cdot 10^n+ x_{n-1}\cdot 10^{n-1}+ \ldots+ x_1\cdot 10+ x_0\cdot 10^{0}.$$
• $[10^j]_3=[10]_3^j= [1]_3^j= [1^j]_3= [1]_3$.
• Av detta följer påståendet eftersom $$[m]_3=\bigl[x_n\cdot 10^n+x_{n-1}\cdot 10^{n-1}+ \ldots+x_1\cdot 10+ x_0\cdot 10^{0}\bigr ]_3 \\ =[x_n]_3\cdot [10^n]_3 + [x_{n-1}]_3\cdot [10^{n-1}]_3+ \ldots+[x_1]_3\cdot [10]_3+ [x_0]_3\cdot [1]_3 \\ = [x_n]_3 + [x_{n-1}]_3+ \ldots +[x_1]_3+ [x_0]_3 \\ =[x_n+x_{n-1}+\ldots + x_1+ x_0]_3.$$

• Om $[m]_n\in \Z/n\Z$ och det finns en restklass $[j]_n\in \Z/n\Z$ så att $[m]_n\cdot [j]_n=[1]_n$, dvs. $m\cdot j\equiv_n 1$ så säger man att $[m]_n$ har en invers eller att $[m]_n$ är inverterbar i $\Z/n\Z$ och inversen är $[j]_n=[m]_n^{-1}$.
• Om $[m]_n$ har en invers så kan man dividera med $[m]_n$ för det är samma sak som att multiplicera med $[j]_n$.
• Om $[j]_n=[m]_n^{-1}$ så finns det ett heltal $k$ så att $m\cdot j=1+k\cdot n$. Om nu $d|m$ och $d|n$ så gäller $d|(m\cdot j-k\cdot n)$ dvs. $d|1$ och därför är $d=1$. Med andra ord gäller $\Gcd(m,n)=1$. Man kan visa att det omvända påståendet också gäller så att $$[m]_n \text{ har en invers i $\Z/n\Z$}\quad\leftrightarrow\quad \Gcd(m,n)=1.$$

Obs! [+]

Om $p$ är ett primtal så har alla element i $\Z/p\Z$ utom $[0]_p$ en invers.

Exempel: Studerandenummer [+]

I ett universitet innehåller studerandenumren sex siffror och en kontrollbokstav. En studerande skrev sitt nummer i formen $53x576J$ där siffran $x$ blev så suddig att den blev oläsbar. Vad är $x$ då kontrollbokstaven $J$ betyder att då det tal som bildas av siffrorna före $J$ divideras med $23$ så blir resten $9$. Svar [+]

Vi kan skriva talet $53x576$ i formen $530\,576+x\cdot 1\,000$ och då får vi med de givna uppgifterna $$[9]_{23}= [530\,576+x\cdot 1\,000]_{23} = [530\,576]_{23}+[x]_{23}\cdot [1\,000]_{23} \\ =[12]_{23}+[x]_{23}\cdot [11]_{23},$$ eftersom $\Mod(530\,576,23)=12$ och $\Mod(1\,000,23)=11$. Av detta följer att $[x]_{23}\cdot [11]_{23}= [-3]_{23}$ och eftersom $[11]_{23}^{-1}=[21]_{23}$ då $\Mod(21\cdot 11,23)= \Mod(231,23)=1$ så blir $$[x]_{23}= [-3]_{23}\cdot [11]_{23}^{-1}= [-3]_{23}\cdot [21]_{23}=[-63]_{23}= [-63+3\cdot 23]_{23}=[6]_{23},$$ och vi kan dra slutsatsen att $x=6$ eftersom $0\leq x\leq 9$.

• Antag att $m\geq n>0$.
• Välj $r_0=m$ och $r_1=n$.
• Bestäm $q_j$ och $r_j$ så att $0\leq r_j < r_{j-1}$ och $$\begin{equation*} r_{j-2}=q_j\cdot r_{j-1}+ r_j \end{equation*}$$ då $j\geq 2$ och $r_{j-1}> 0$.
• $\Gcd(m,n)= r_{k-1}$ om $r_k=0$.

Exempel: [+]

När vi räknar ut $\Gcd(291,108)$ med Euklides algoritm blir resultatet följande: $$\begin{align*} 291 &= 2\cdot 108 + 75\\ 108 &= 1\cdot 75 + 33\\ 75 &= 2\cdot 33 + 9\\ 33 &= 3\cdot 9 + 6\\ 9 & = 1 \cdot 6 + 3\\ 6& = 2\cdot 3 + 0 \end{align*}$$ så att $\Gcd(291,108)=3$.

Varför fungerar Euklides algoritm? [+]

Om $d\,|\, r_{j}$ och $d\,|\, r_{j-1}$ så gäller $d\,|\, r_{j-2}$ eftersom $r_{j-2}=q_j\cdot r_{j-1}+ r_j$ och det betyder att $\Gcd(r_{j-2},r_{j-1}) \geq \Gcd(r_{j-1},r_j)$. På motsvarande sätt, om $d\,|\, r_{j-2}$ och $d\,|\, r_{j-1}$ så gäller $d\,|\, r_{j}$ eftersom $r_j=r_{j-2}-q_j \cdot r_{j-1}$ och det innebär att $\Gcd(r_{j-1},r_j)\geq \Gcd(r_{j-2},r_{j-1})$ och således gäller $\Gcd(r_{j-1},r_j)= \Gcd(r_{j-2},r_{j-1})$.
Om $r_k=0$ så gäller $\Gcd(r_{k-1},r_k) = \Gcd(r_{k-1},0) =r_{k-1}$ eftersom $d|0$ för alla $d$ så att $$\Gcd(m,n)= \Gcd(r_0,r_1) = \ldots=\Gcd(r_{k-1},r_k)= \Gcd(r_{k-1},0) = r_{k-1}.$$   

I Euklides algoritm väljer man $r_0=m$, $r_1=n$ och sedan räknar man $q_j$ och $r_j$ då $j=2,\ldots, k$ med formeln $r_{j-2}=q_j\cdot r_{j-1}+r_j$ tills $r_k=0$, och då får man $r_{k-1}=\Gcd(m,n)$. Eftersom $r_{k-3}=q_{k-1}\cdot r_{k-2}+r_{k-1}$ så gäller $$\Gcd(m,n)=r_{k-1}=r_{k-3}-q_{k-1}\cdot r_{k-2} =a_{k-3}j\cdot r_{k-3}+b_{k-3}\cdot r_{k-2 },$$ där alltså $a_{k-3}=1$ och $b_{k-3}=q_{k-1}$. Det betyder att $\Gcd(m,n)= a_j\cdot r_j+b_j\cdot r_{j+1}$ åtminstone då $j=k-3$ och om detta gäller också då $1\leq j\leq k-3$ så kan man i den här ekvationen som sätta in $r_{j+1}= r_{j-1}-q_{j+1}\cdot r_j$ som man får ur ekvationen $r_{j-1}=q_{j+1}\cdot r_{j}+ r_{j+1}$ och då blir resultatet $$\Gcd(m,n)= a_j\cdot r_j +b_j\cdot( r_{j-1}-q_{j+1}\cdot r_j)=a_{j-1}\cdot r_{j-1}+ b_{j-1}\cdot r_j,$$ där $a_{j-1}=a_j+b_j$ och $b_{j-1}=-b_j\cdot q_{j+1}$. Det betyder att man med induktion kan visa att $$\Gcd(m,n) = a_0\cdot m+ b_0\cdot n.$$

Om nu $\Gcd(m,n)=1$ så gäller $$\begin{align*} [a_0]_n\cdot [m]_n&=[1]_n\quad \text{dvs.}\quad [a_0]_n= [m]_n^{-1}, \\ [b_0]_m\cdot [n]_m&=[1]_m\quad \text{dvs.}\quad [b_0]_m= [n]_m^{-1}. \end{align*}$$

Exempel: Inversen av en restklass [+]

Om vi skall räkna ut $[23]_{67}^{-1}$ så bestämmer vi först $\Gcd(67,23)$ så här: $$\begin{align*} 67 &= 2 \cdot 23 + 21\\ 23 &= 1 \cdot 21 + 2\\ 21 &= 10 \cdot 2 + 1\\ 2 &= 2 \cdot 1 + 0 \end{align*}$$ För att vi skall kunna uttrycka $\Gcd(67,23)$ med hjälp av talen $67$ och $23$ så räknar vi baklänges och utnyttjar de uttryck för $2$ och $21$ som vi får ur räkningen ovan: $$\Gcd(67,23)=1 =21-10\cdot 2\\ = 1 \cdot 21 -10\cdot (23 - 1\cdot 21)\\ =-10\cdot 23+11\cdot 21 \\ = -10 \cdot 23 +11\cdot (67 - 2\cdot 23)\\ =11\cdot 67-32\cdot 23$$ Av det här följer att $(-32)\cdot 23= 1-11\cdot 67$ vilket betyder att $[(-32)\cdot 23]_{67}=[1]_{67}$ vilket i sin tur är ekvivalent med att $[23]_{67}^{-1} = [-32]_{67}=[-32+67]_{67}=[35]_{67}$.

Hur många räkneoperationer behövs då man räknar ut $\Gcd(m,n)$ och $[n]_{m}^{-1}$ med Euklides algoritm? [+]

Vi antar att $m> n$. I Euklides algoritm väljer vi $r_0=m$, $r_1=n$ och sedan räknar vi ut $r_i$ och $q_i$ så att $r_{i-2}=q_ir_{i-1}+ r_i$ då $i\geq 2$ tills $r_{K}=0$ och då får vi $r_{K-1}=\Gcd(m,n)$. För detta behöver vi $K-1$ divisioner.

Vi skall alltså uppskatta hur stor $K$ kan vara och för att göra detta väljer vi $x_1=1$, $x_2=2$ och $$x_{j+2}=x_{j+1}+x_{j}, \quad j\geq 1.\tag{$\star$}$$ Vi vet att $r_{K-1}\geq x_1$ och $r_{K-2}\geq x_2$ eftersom $r_{K-2}> r_{K-1}$. Om vi nu antar att $r_{K-i}\geq x_i$ då $1\leq i\leq j$ så får vi, eftersom $q_{K-j+1}\geq 1$ att $$r_{K-(j+1)} = q_{K-j+1} r_{K-j}+ r_{K-j+1}\geq r_{K-j}+ r_{K-j+1} \geq x_j+ x_{j-1} =x_{j+1}.$$ Med stöd av induktionsprincipen ser vi nu att $r_{K-j}\geq x_j$ för alla $j=1,\ldots ,K$.

Vi kan lösa ekvationen ($\star$) (det är frågan om Fibonaccis ekvation med en aning avvikande indexering) men det är enklare att visa med hjälp av induktion att $x_j\geq \left (\frac {1+\sqrt 5}2\right )^{j-1}$ då $j\geq 1$ (Hur? [+])

Genom att notera att $x_1=1= \left (\frac {1+\sqrt 5}2\right )^{1-1}$, $x_2=2\geq \left (\frac {1+\sqrt 5}2\right )^{2-1}$ och att $\left (\frac {1+\sqrt 5}2\right )^{j+1-1} + \left (\frac {1+\sqrt 5}2\right )^{j-1}= \left (\frac {1+\sqrt 5}2\right )^{j+2-1}$.

Av detta följer att $$m=r_0\geq x_{K}\geq \left (\frac {1+\sqrt 5}2\right )^{K-1},$$ av vilket i sin tur följer att $$K-1 \leq \frac {\log(m)}{\log\left (\frac {1+\sqrt 5}2\right )},$$ vilket betyder att det behövs $O(\log(\max(m,n)))$ räkneoperationer för att bestämma $\Gcd(m,n)$ med Euklides algoritm. Av detta följer också att det behövs $O(\log(m))$ räkneoperationer för att räkna ut $[n]_{m}^{-1}$.

Ett delbarhetsresultat [+]

Om $m$ och $n$ är heltal och $p$ är ett primtal så att $m\cdot n$ är delbar med $p$ så är antingen $m$ eller $n$ delbar med $p$ och här är det frågan om hur man kan bevisa detta utan att använda något som stöder sig på det här resultatet.

Varför? [+]

Vi antar att $m$ inte är delbar med $p$ (i annat är ju saken klar). Då gäller $\Gcd(p,m)=1$ eftersom $p$ är ett primtal. Med Euklides utvidgade algoritm hittar vi heltal $a$ och $b$ så att $a\cdot p + b\cdot m=1$. Vi multiplicerar båda sidorna av denna ekvation med $n$ och får $$n = n\cdot 1 = n\cdot a\cdot p + b\cdot m\cdot n .$$ Eftersom $m\cdot n$ är delbar med $p$ så finns det ett heltal $k$ så att $m\cdot n=k\cdot p$. Av det här följer att $$n= n\cdot a\cdot p+ b\cdot k\cdot p = (n\cdot a+ b\cdot k)\cdot p,$$ vilket betyder att $n$ är delbar med $p$.

$$\varphi(n) =\card{ \set{m\in \Z: 0\leq m\leq n-1, \Gcd(m,n)=1}},$$ dvs. $\varphi(n)$ är antalet element i mängden $\Z/n\Z$ som har en invers.

Observera att $[0]_1$ har en invers (dvs. $[0]_1$) i mängden $\Z/1\Z$ så att $\varphi(1)=1$ men $[0]_n$ har naturligtvis (?) inte någon invers i mängden $\Z/n\Z$ då $n>1$.

I matlab/octave kan man använda funktionen @(n)sum(gcd(0:n-1,n)==1) för att räkna ut värdena av $\varphi$.

Exempel: $\varphi(p\cdot q)=(p-1)\cdot (q-1)$ då $p$ och $q$ är olika primtal [+]

Eftersom $p$ och $q$ är primtal är mängden $\set{k\in \Z\mid 0\leq k < p\cdot q,\, \Gcd(k,p\cdot q)\neq 1}$ lika med mängden $\{0\} \cup \{q,2\cdot q, \ldots (p-1)\cdot q\} \cup \{p, 2\cdot p,\ldots (q-1)\cdot p\}$ och vi kan se att i den här mängden finns det $1+(p-1)+(q-1)$ element. Eftersom det i mängden $\{0,1,2,\ldots,p\cdot q-1\}$ finns $p\cdot q$ element så är $\varphi(p\cdot q)= p\cdot q - \bigl (1+(p-1)+(q-1)\bigr )= (p-1)\cdot (q-1).$

Det här resultatet är ett specialfall av resultatet enligt vilket $\varphi(a\cdot b)=\varphi(a)\cdot \varphi(b)$ om $\Gcd(a,b)=1$.

Om $\Gcd(a,n)=1$ och $n>1$ så gäller $$a^{\varphi(n)}\equiv_n 1 \quad\text{dvs.}\quad\Mod(a^{\varphi(n)},n)=1 \quad\text{dvs.}\quad \left [a^{\varphi(n)}\right ]_n=[1]_n.$$ I synnerhet, om $p$ är ett primtal och $\Gcd(a,p)=1$ så gäller $$a^{p-1} \equiv_p 1 \quad \text{eli}\quad \Mod(a^{p-1},p)=1 \quad\text{eli}\quad \left[a^{p-1}\right ]_p=[1]_p.$$

Bevis [+]

• Vi antar att de inverterbara elementen i $\Z/n\Z$ är $[x_1]_n,\ldots ,[x_{\phi(n)}]$.
• Eftersom $\Gcd(a,n)=1$ så har också $[a]_n$ en invers och eftersom $[\alpha]_n\cdot [\beta]_n$ är inverterbar (med inversen $[\beta]_n^{-1}\cdot [\alpha]_n^{-1}$) om $[\alpha]_n$ och $[\beta]_n$ är inverterbara så är $[a]_n\cdot [x_j]$ inverterbar för alla $j$.
• Om nu $[a]_n\cdot [x_j]_n=[a]_n\cdot [x_k]_n$ så är $[a]_n^{-1}\cdot [a]_n\cdot [x_j]_n= [a]_n^{-1}\cdot [a]_n\cdot [x_k]_n$ dvs. $[x_j]_n=[x_k]_n$. Av det här följer att elementen $[a]_n\cdot [x_1]_n, \ldots [a]_n\cdot [x_{\varphi(n)}]_n$ är de samma som elementen [x_1]_n,\ldots ,[x_{\varphi(n)}]$ men möjligen i en annan ordning.
• Men produkterna är lika, dvs. $$[a]_n^{\varphi(n)}\Pi_{i=1}^{\varphi(n)}[x_i]_n= \Pi_{i=1}^{\varphi(n)} \left ([a]_n\cdot [x_i]_n\right )= \Pi_{i=1}^{\varphi(n)} [x_i]_n.$$
• Eftersom alla elementen $[x_i]_n$ är inverterbara kan vi dividera bort alla $[x_i]_n$ och slutresultatet är att $[a]_n^{\varphi(n)}=[1]_n$ dvs. $\Mod(a^{\varphi(n)},n)=1$.

I RSA-algoritmen använder man en publik nyckel $(n,k)$ för att kryptera ett meddelande och en privat nyckel $(n,d)$ för att dekryptera meddelandet:

• Kryptering: Meddelandet $a$, som är ett tal mellan $0$ och $n-1$, krypteras $b=\Mod(a^k,n)$ som sänds iväg.
• Dekryptering: Mottagaren dekrypterar det krypterade meddelandet $b$ det till det ursprungliga meddelandet $a = \Mod(b^d,n)$.

Metoden bygger på att det är (kall vara) oöverkomligt svårt att med hjälp av endast den publika nyckeln $(n,k)$ bestämma den privata nyckeln $(n,d)$ så att vem som helst kan skicka ett meddelande krypterat med mottagarens publika nyckel men endast mottagaren, som känner till sin privata nyckel kan dekryptera det krypterade meddelandet.

Hur skall nycklarna i RSA-algoritmen väljas? [+]

• $n=p\cdot q$ där $p$ och $q$ är två stora primtal så att det är oöverkomligt svårt att faktorisera $n$ i faktorerna $p$ och $q$ (vilket tex. betyder att också $\abs{p-q}$ måste vara stort).
• $k$ är ett stort tal så att $0< k < m$ och $\Gcd(k,m)=1$ där $m=(p-1)\cdot (q-1)$.
• Med Euklides algoritm bestämmer man $d$ så att $[d]_m= [k]_m^{-1}$.

Krypteringen baserar sig på att det är svårt att bestämma talet $d$ om man inte känner till $m$ och det i sin tur är svårt om man inte känner till $p$ och $q$.

Exempel [+]

Om vi vill kryptera meddelandet $9$ med RSA-algoritmen och den publika nyckeln $(55,23)$ så skall vi räkna ut $\Mod(9^{23},55)$. Fastän talen $55$ och $23$ är alldeles för små för krypteringen är det ändå inte förnuftigt att först räkna $m=9^{23}$ och sedan $\Mod(m,55)$. I stället konstaterar vi först att $23=16+4+2+1=2^4+2^2+2^1+2^0$ så $9^{23} = 9^{16}\cdot 9^{4}\cdot 9^2\cdot 9=(((9^2)^2)^2)^2\cdot (9^2)^2\cdot 9^2\cdot 9$ och i varje skede kan vi tillämpa $\Mod$-funktionen dvs. vi räknar först $\Mod(9^2,55)= 26$, sedan $\Mod(9^4,55)=\Mod(26^2,55)=16$ osv. så att vi får $\Mod(9^j,55)$ då $j=1,2,4,8,16$. Sedan räknar vi $\Mod(9^3,55)= \Mod(9\cdot 9^2,55)=\Mod(9\cdot 26,55)$ och sedan på samma sätt $\Mod(9^7,55)$ och $\Mod(9^{23},55)$. Enklast kan vi gör detta med följande algoritm som räknar ut $\Mod(x^y,n)$:

function z=pmod(x,y,n)
z=1;
x=mod(x,n);
while y > 0
   k=mod(y,2);
   if k == 1, z=mod(z*x,n); end
   y=(y-k)/2;
   if y > 0, x=mod(x*x,n); end
end
return,endfunction

Med den här algoritmen får vi följande mellanresultat när vi räknar ut $\Mod(9^{23},55)$ dvs. pmod(9,23,55):

$k$	$z$	$x$	$y$
	$1$	$9$	$23$
1	$\Mod(1\cdot 9,55)=9$	$\Mod(9\cdot 9,55)=26$	$11$
1	$\Mod(9\cdot 26,55)=14$	$\Mod(26\cdot 26,55)=16$	$5$
1	$\Mod(14\cdot 16,55)=4$	$\Mod(16\cdot 16,55)=36$	$2$
0	$4$	$\Mod(36\cdot 36,55)=31$	$1$
$1$	$\Mod(4\cdot 31,55)=14$	$31$	$0$

och det sista $z$-värdet $14$ är det krypterade meddelandet.
Observera att talföljden $10111$ som man kan bilda av värdena på $k$ är $23$ som binärtal.

För att vi skall kunna dekryptera det det krypterade meddelandet $14$ måste vi känna till den privata nyckeln och eftersom $55=5\cdot 11$ och $(5-1)\cdot (11-1)=40$ så skall vi räkna ut $[23]_{40}^{-1}$ och vi får som svar $[7]_{40}$ vilket vi kan kontrollera genom att räkna $\Mod(23\cdot 7,40)= \Mod(161,40)=1$. Den privata nyckeln är alltså $(55,7)$ och vi skall räkna $\Mod(14^7,55)$. Om vi använder samma algoritm som ovan så ser räkningen ut på följande sätt:

$k$	$z$	$x$	$y$
	$1$	$14$	$7$
1	$\Mod(1\cdot 14,55)=14$	$\Mod(14\cdot 14,55)=31$	$3$
1	$\Mod(14\cdot 31,55)=49$	$\Mod(31\cdot 31,55)=26$	$1$
1	$\Mod(49\cdot 26,55)=9$		$0$

Varför fungerar RSA-algoritmen? [+]

• Vi antar för enkelhetens skull först att $\Gcd(a,n)=1$.
• $\varphi(n) =\varphi(p\cdot q)=(p-1)\cdot(q-1) =m$.
• Enligt Eulers sats gäller $[a^m]_n=[1]_n$.
• Eftersom $[d]_m= [k]_m^{-1}$ så är $k\cdot d=1+ r\cdot m$ och $$\left [b^d\right ]_n= \left [a^{k\cdot d}\right ]_n=\left[a^{1+r\cdot m}\right]_n= [a]_n\cdot\left[a^m\right]_n^r = [a]_n\cdot [1]_n^r= [a]_n,$$ av vilket följer att $\Mod(b^d,n)=\Mod(a,n)=a$.

Varför fungerar RSA-algoritmen då $\Gcd(a,n)\neq 1$? [+]

• Eftersom vi antar att $0 < a< n$ så gäller $\Gcd(a,n)\neq 1$ endast om $p\,|\,a$ eller $q\,|\,a$. Vi antar att $p\,|\,a$ så att $a=p^j\cdot c$ där $\Gcd(c,n)=1$.
• Nu är $[b^d]_n=[((p^j\cdot c)^k)^d]_n=[(p^k)^d]_n^j\cdot [(c^k)^d]_n$ och eftersom $\Gcd(c,n)=1$ så gäller enligt det vi redan visat $[(c^k)^d]_n=[c]_n$ och vi skall ännu visa att $[(p^k)^d]_n=[p]_n$ för då får vi $[b^d]_n= [p]_n^j\cdot [c]_n = [p^j\cdot c]_n= [a]_n$.
• Eftersom $q$ är ett primtal så är $\varphi(q)=q-1$ och eftersom $p$ också är ett primtal och $p\neq q$ så är $\Gcd(p,q)=1$ så att det följer av Eulers sats att $[p^{q-1}]_q=[1]_q$.
• Då gäller också $[p^{(q-1)(p-1)r}]_q=[1]_q$ dvs. $p^{(q-1)(p-1)r}= 1+ sq$ och då vi multiplicerar båda sidorna med $p$ så får vi $p^{1+(q-1)(p-1)r}= p + spq=p+sn$. Eftersom $[d]_m=[k]_m^{-1}$ så är $k\cdot d=1+mr=1+(p-1)(q-1)r$ och det betyder att $[(p^k)^d]_n=[p^{1+(q-1)(p-1)r}]_n = [p]_n$ och algoritmen fungerar också i det här fallet!

RSA-algoritmen och underskrifter [+]

Om A vill skicka meddelande $a$ till B och $B$ vill bli övertygad om att meddelandet verkligen kommer från A så kan de gå tillväga på följande sätt:

• A räknar ut ett kondensat eller hashvärde $h(a)$ av meddelandet $a$.
• A krypterar meddelandet $a$ med B:s publika nyckel $(n_B,k_B)$ till det krypterade meddelandet $b=\Mod(a^{k_B},n_B)$.
• A krypterar $h(a)$ med sin egen privata nyckel $(n_A,d_A)$ till en underskrift $s=\Mod(h(a)^{d_A},n_A)$.
• A skickar $b$ och $s$ till B.
• B dekrypterar $b$ med sin privata nyckel $(n_B,d_B)$ och får som resultat $a$.
• B räknar ut hashvärdet $h(a)$:n och dekrypterar $s$ med A:s publika nyckel $(n_A,k_A)$ och om resultatet är samma som $h(a)$ så blir B övertygad om att meddelandet $a$ verkligen kommer från A eftersom ingen annan kan kryptera $h(a)$ med A:s privata nyckel $(n_A,d_A)$.

Det här baserar sig på att $[k]_{m}=[d]_{m}^{-1}$ så kan ett meddelande som krypterats med en privat nyckel dekrypteras med motsvarande publika nyckel.

Exempel [+]

A vill skicka meddelandet $9$ till B och lägga till en underskrift så att B kan vara säker på att A verkligen är avsändaren.

Om nu A:s publika RSA-nyckel är $(n_A,k_A)=(91,11)$, privata nyckel $(n_A,d_A)=(91,59)$ och på motsvarande vis B:s publika nyckel är $(n_B,k_B)=(55,23)$ och privata nyckel $(n_B,d_B)=(55,7)$ och de som hashfunktion använder $h(x)= \lfloor 2^{6}\cdot \Mod(x\cdot (\sqrt{5}-1)/2,1)\rfloor$ så utför A och B följande räkneoperationer:

• A krypterar meddelandet $9$ med B:s publika nyckel och får som resultat $\Mod(9^{k_B},n_B)=\Mod(9^{23},55)=14$
• A räknar hashvärdet $h(9)=35$.
• A krypterar hashvärdet med sin egen privata nyckel och får som resultat underskriften $\Mod(35^{d_A},n_A)=\Mod(35^{11},91)=42$.
• A skickar talen $14$ och $42$ till B.
• B dekrypterar det krypterade meddelandet $14$ med sin egen privata nyckel och får som resultat $\Mod(14^{d_B},n_B)=\Mod(14^7,55)= 9$.
• B räknar ut hashvärdet $h(9)=35$.
• B dekrypterar A:s underskrift med A:s publika nyckel och får som resultat $\Mod(42^{k_A},n_A)=\Mod(42^{59},91) =35$.
• Eftersom resultatet är $h(9)$ kan B lita på att det är A som skickat meddelandet.