Relaatio $\equiv_n $ on ekvivalenssirelaatio joukossa $\Z$ ja jakaa $\Z$:n ekvivalenssiluokkiin joita kutsutaan kongruenssi- tai jäännösluokiksi, ja nämä ovat joukot
$\{\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\}$,
joissa kaikki alkiot ovat kongruentteja toistensa kanssa modulo $n$.
Seuraavia merkintöjä käytetään kun $n>0$:

Huom! [+]

Koska $\Mod(m_1,n)=\Mod(m_2,n)\leftrightarrow [m_1]_n=[m_2]_n$ niin usein valitaan alkio $\Mod(m,n)$ edustamaan jäännösluokkaa $[m]_n$ niin että voidaan esim. puhua luvuista $0,1,2,\ldots,5$ joukon $\Z/6\Z$ alkioina joukkojen $[0]_6, [1]_6,\ldots,[5]_6$ sijasta. Joskus kirjoitetaan $[k]_n$:n sijasta $\overline k_n$ ja $\Z/n\Z$:n sijasta $\Z_n$.

Voidaan osoittaa, että jos \[ a_1\equiv_n a_2 \quad \text{ja}\quad b_1\equiv_n b_2 \] niin \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*} Näin ollen voidaan määritellä laskuoperaatiota joukossa $\Z/n\Z$ seuraavasti: \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*} ja kaikki "normaalit" laskusäännöt (paitsi epäyhtälöihin liittyvät) pätevät edelleen.

Esimerkki [+]

Päteekö $3\,|\, 5742385242417$ eli jakaako $3$ luvun $5742385242417$?
Vastaus on kyllä koska luvun numeroiden summa $5+7+4+2+3+8+5+2+4+2+4+1+7$ on kolmella jaollinen.
Mutta miksi tämä sääntö pätee? [+]

• Kymmenjärjestelmässä luvulla $x_nx_{n-1}\ldots x_1x_0$ tarkoitetaan lukua
• $[10^j]_3=[10]_3^j= [1]_3^j= [1^j]_3= [1]_3$.
• Tästä seuraa väite koska

• Jos $[m]_n\in \Z/n\Z$ ja on olemassa jäännösluokka $[j]_n\in \Z/n\Z$ siten, että $[m]_n\cdot [j]_n=[1]_n$, eli $m\cdot j\equiv_n 1$ niin sanotaan, että $[m]_n$:llä on käänteisalkio tai että $[m]_n$ on kääntyvä $\Z/n\Z$:ssa ja käänteisalkio on $[j]_n=[m]_n^{-1}$.
• Jos $[m]_n$:llä on käänteisalkio niin voidaan jakaa $[m]_n$:llä koska se on yhtäpitävää sen kanssa, että kerrotaan $[j]_n$:llä.
• Jos $[j]_n=[m]_n^{-1}$ niin on olemassa kokonaisluku $k$ siten, että $m\cdot j=1+k\cdot n$. Jos nyt $d|m$ ja $d|n$ niin pätee $d|(m\cdot j-k\cdot n)$ eli $d|1$ joten $d=1$. Näin ollen $\Gcd(m,n)=1$. Voidaan osoittaa, että myös käänteinen tulos pätee joten

Huom [+]

Jos $p$ on alkuluku niin kaikilla $\Z/p\Z$:n alkioilla paitsi $[0]_p$:llä on käänteisalkio.

Esimerkki: Opiskelijanumero [+]

Eräässä yliopistossa opiskelijanumerot sisältävät kuusi numeroa ja tarkistuskirjaimen. Opiskelija kirjoitti numeronsa muodossa $53x576J$ missä numero $x$ jäi niin suttuisaksi, ettei siitä saanut selvää. Mikä $x$ on kun tarkistuskirjain $J$ tarkoittaa, että kun $J$:tä edeltävien numeroiden muodostama luku jaetaan $23$:lla niin jakojäännös on $9$. Vastaus [+]

Voimme kirjoittaa luvun $53x576$ muodossa $530\,576+x\cdot 1\,000$ ja silloin saamme annettujen tietojen avulla koska $\Mod(530\,576,23)=12$ ja $\Mod(1\,000,23)=11$. Tästä seuraa, että $[x]_{23}\cdot [11]_{23}= [-3]_{23}$ ja koska $[11]_{23}^{-1}=[21]_{23}$ koska $\Mod(21\cdot 11,23)= \Mod(231,23)=1$ joten ja voimme päätellä, että $x=6$ koska $0\leq x\leq 9$.

• Oleta, että $m\geq n>0$.
• Valitse $r_0=m$ ja $r_1=n$.
• Laske $q_j$ ja $r_j$ siten, että $0\leq r_j < r_{j-1}$ ja \begin{equation*} r_{j-2}=q_j\cdot r_{j-1}+ r_j \end{equation*} kun $j\geq 2$ ja $r_{j-1}> 0$.
• $\Gcd(m,n)= r_{k-1}$ jos $r_k=0$.

Esimerkki: [+]

Kun laskemme $\Gcd(291,108)$ Eukleideen algoritmin avulla niin tulos on seuraava: \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*} joten $\Gcd(291,108)=3$.

Miksi Eukleideen algoritmi toimii? [+]

Jos $d\,|\, r_{j}$ ja $d\,|\, r_{j-1}$ niin $d\,|\, r_{j-2}$ koska $r_{j-2}=q_j\cdot r_{j-1}+ r_j$ joten $\Gcd(r_{j-2},r_{j-1}) \geq \Gcd(r_{j-1},r_j)$. Vastaavasti, jos $d\,|\, r_{j-2}$ ja $d\,|\, r_{j-1}$ niin $d\,|\, r_{j}$ koska $r_j=r_{j-2}-q_j \cdot r_{j-1}$ joten $\Gcd(r_{j-1},r_j)\geq \Gcd(r_{j-2},r_{j-1})$ ja näin ollen $\Gcd(r_{j-1},r_j)= \Gcd(r_{j-2},r_{j-1})$.
Jos $r_k=0$ niin $\Gcd(r_{k-1},r_k) = \Gcd(r_{k-1},0) =r_{k-1}$ koska $d|0$ kaikilla $d$ joten   

Eukleideen algoritmissa valitaan $r_0=m$, $r_1=n$ ja sitten lasketaan $q_j$ ja $r_j$ kun $j=2,\ldots, k$ kaavalla $r_{j-2}=q_j\cdot r_{j-1}+r_j$ kunnes $r_k=0$, jolloin $r_{k-1}=\Gcd(m,n)$. Koska $r_{k-3}=q_{k-1}\cdot r_{k-2}+r_{k-1}$ niin missä siis $a_{k-3}=1$ ja $b_{k-3}=q_{k-1}$. Näin ollen $\Gcd(m,n)= a_j\cdot r_j+b_j\cdot r_{j+1}$ ainakin kun $j=k-3$ ja jos tämä tulos pätee myös jollakin $j$, $1\leq j\leq k-3$ niin tähän sijoitetaan $r_{j+1}= r_{j-1}-q_{j+1}\cdot r_j$ yhtälöstä $ r_{j-1}=q_{j+1}\cdot r_{j}+ r_{j+1}$ jolloin missä $a_{j-1}=a_j+b_j$ ja $b_{j-1}=-b_j\cdot q_{j+1}$. Näin ollen saadaan induktiolla \[ \Gcd(m,n) = a_0\cdot m+ b_0\cdot n. \]

Jos nyt $\Gcd(m,n)=1$ niin \begin{align*} [a_0]_n\cdot [m]_n&=[1]_n\quad \text{eli}\quad [a_0]_n= [m]_n^{-1}, \\ [b_0]_m\cdot [n]_m&=[1]_m\quad \text{eli}\quad [b_0]_m= [n]_m^{-1}. \end{align*}

Esimerkki: Jäännösluokan käänteisalkio [+]

Jos haluamme laskea $[23]_{67}^{-1}$ niin ensin laskemme $\Gcd(67,23)$ eli \begin{align*} 67 &= 2 \cdot 23 + 21\\ 23 &= 1 \cdot 21 + 2\\ 21 &= 10 \cdot 2 + 1\\ 2 &= 2 \cdot 1 + 0 \end{align*} Jotta voisimme esittää $\Gcd(67,23)$:n lukujen $67$ ja $23$ avulla laskemme takaperin : \[ \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 \] Tästä seuraa, että $(-32)\cdot 23= 1-11\cdot 67$ joten $[(-32)\cdot 23]_{67}=[1]_{67}$ mikä on yhtäpitävää sen kanssa, että $[23]_{67}^{-1} = [-32]_{67}=[-32+67]_{67}=[35]_{67}$.

Montako laskutoimitusta tarvitaan kun $\Gcd(m,n)$ ja $[n]_{m}^{-1}$ lasketaan Eukleideen algoritmilla? [+]

Oletamme, että $m> n$. Eukleideen algoritmissa valitsemme $r_0=m$, $r_1=n$ ja sitten laskemme $r_i$ ja $q_i$ siten, että $ r_{i-2}=q_ir_{i-1}+ r_i $ kun $i\geq 2$ kunnes $r_{K}=0$ ja silloin $r_{K-1}=\Gcd(m,n)$. Tähän tarvitaan $K-1$ jakolaskua.

Meidän pitää siis arvioida miten iso $K$ voi olla ja tätä varten valitsemme $x_1=1$, $x_2=2$ ja \[ x_{j+2}=x_{j+1}+x_{j}, \quad j\geq 1.\tag{$\star$} \] Tiedämme, että $r_{K-1}\geq x_1$ ja $r_{K-2}\geq x_2$ koska $r_{K-2}> r_{K-1}$. Jos nyt oletamme, että $r_{K-i}\geq x_i$ kun $1\leq i\leq j$ niin saamme, koska $q_{K-j+1}\geq 1$ että Induktioperiaatteesta seuraa nyt, että $r_{K-j}\geq x_j$ kaikilla $j=1,\ldots ,K$.

Voisimme ratkaista yhtälön ($\star$) (kyseessä hän on Fibonaccin yhtälö tavallisesta hieman poikkeavalla indeksoinnilla) mutta on ehkä yksinkertaisempaa osoittaa, induktion avulla, että $x_j\geq \left (\frac {1+\sqrt 5}2\right )^{j-1}$ kun $j\geq 1$ (Miten? [+])

Toteamalla, että $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}$ ja että $\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}$.

Tästä seuraa, että \[ m=r_0\geq x_{K}\geq \left (\frac {1+\sqrt 5}2\right )^{K-1}, \] josta seuraa, että \[ K-1 \leq \frac {\log(m)}{\log\left (\frac {1+\sqrt 5}2\right )}, \] eli tarvitaan $O(\log(\max(m,n)))$ laskutoimitusta $\Gcd(m,n)$:n laskemiseksi Eukleideen algoritmin avulla. Tästä seuraa myös, että $[n]_{m}^{-1}$:n laskemiseksi tarvitaan $O(\log(m))$ laskutoimitusta.

Jaollisuustulos [+]

Jos $m$ ja $n$ ovat kokonaislukuja ja $p$ on alkuluku siten, että $m\cdot n$ on $p$:llä jaollinen niin joko $m$ tai $n$ on $p$:llä jaollinen ja tässä on kyse siitä miten tämä väite todistetaan käyttämättä tuloksia, jotka perustuvat tähän tulokseen.

Miksi ? [+]

Oletamme, että $m$ ei ole $p$:llä jaollinen. Silloin pätee $\Gcd(p,m)=1$ koska $p$ on alkuluku. Eukleideen laajennetun algoritmin nojalla on olemassa kokonaislukuja $a$ ja $b$ siten, että $a\cdot p + b\cdot m=1$. Kerromme tämän yhtälön molemmat puolet $n$:llä ja saamme \[ n = n\cdot 1 = n\cdot a\cdot p + b\cdot m\cdot n . \] Koska $m\cdot n$ on $p$:llä jaollinen niin on olemassa kokonaisluku $k$ siten, että $m\cdot n=k\cdot p$. Tästä seuraa, että \[ n= n\cdot a\cdot p+ b\cdot k\cdot p = (n\cdot a+ b\cdot k)\cdot p, \] josta seuraa, että $n$ on $p$:llä jaollinen.

\[ \varphi(n) =\card{ \set{m\in \Z: 0\leq m\leq n-1, \Gcd(m,n)=1}}, \] eli $\varphi(n)$ on niiden joukon $\Z/n\Z$ alkioiden lukumäärä, joilla on käänteisalkio.

Huomaa, että $[0]_1$:llä on käänteisalkio joukossa $\Z/1\Z$ joten $\varphi(1)=1$ mutta $[0]_n$:llä ei tietenkään (?) ole käänteisalkiota joukossa $\Z/n\Z$ kun $n>1$.

Matlab/octave:ssä tämän funktion laskemiseksi voidaan käyttää funktiota @(n)sum(gcd(0:n-1,n)==1).

Esimerkki: $\varphi(p\cdot q)=(p-1)\cdot (q-1)$ kun $p$ ja $q$ ovat eri alkulukuja [+]

Koska $p$ ja $q$ ovat alkulukuja niin joukko $\set{k\in \Z\mid 0\leq k < p\cdot q,\, \Gcd(k,p\cdot q)\neq 1}$ on $\{0\} \cup \{q,2\cdot q, \ldots (p-1)\cdot q\} \cup \{p, 2\cdot p,\ldots (q-1)\cdot p\}$ ja tässä joukossa on $1+(p-1)+(q-1)$ alkiota. Koska joukossa $\{0,1,2,\ldots,p\cdot q-1\}$ on $p\cdot q$ alkiota niin

Tämä tulos on erikoistapaus tuloksesta, joka sanoo että $\varphi(a\cdot b)=\varphi(a)\cdot \varphi(b)$ kun $\Gcd(a,b)=1$.

Jos $\Gcd(a,n)=1$ ja $n>1$ niin Erityisesti, jos $p$ on alkuluku ja $\Gcd(a,p)=1$ niin

Todistus [+]

• Oletamme, että $[x_1]_n,\ldots ,[x_{\phi(n)}]$ ovat ne $\Z/n\Z$:n alkiot joilla on käänteisalkio eli ovat kääntyviä.
• Koska $\Gcd(a,n)=1$ niin myös $[a]_n$ on kääntyvä ja koska $[\alpha]_n\cdot [\beta]_n$ on kääntyvä jos $[\alpha]_n$ ja $[\beta]_n $ ovat kääntyviä, niin $[a]_n\cdot [x_j]$ on kääntyvä kaikilla $j$.
• Jos nyt $[a]_n\cdot [x_j]_n=[a]_n\cdot [x_k]_n$ niin $[a]_n^{-1}\cdot [a]_n\cdot [x_j]_n= [a]_n^{-1}\cdot [a]_n\cdot [x_k]_n$ eli $[x_j]_n=[x_k]_n$. Tästä seuraa, että alkiot $[a]_n\cdot [x_1]_n, \ldots [a]_n\cdot [x_{\varphi(n)}]_n$ ovat samat kuin alkiot $[x_1]_n,\ldots ,[x_{\varphi(n)}]$ mutta mahdollisesti eri järjestyksessä.
• Mutta tulot ovat samat, eli
• Koska kaikki alkiot $[x_i]_n$ ovat kääntyviä niin voimme supistaa pois kaikki $[x_i]_n$:t ja lopputulos on, että $[a]_n^{\varphi(n)}=[1]_n$ eli $\Mod(a^{\varphi(n)},n)=1$.

RSA-algoritmissa käytetään julkista avainta $(n,k)$ viestin kryptaamiseen eli salaamiseen ja yksityistä avainta $(n,d)$ kryptatun viestin purkamiseen:

• Kryptaaminen: Viesti $a$, joka on luku $0$:n ja $n-1$:n väliltä kryptataan eli salataan lähetettäväksi viestiksi $b=\Mod(a^k,n)$.
• Vastaanotettu viesti $b$ puretaan alkuperäiseksi viestiksi $a = \Mod(b^d,n)$.

Menetelmä perustuu siihen, että julkisen avaimen avulla on (pitää olla) ylivoimaisen vaikeata määrittää yksityistä avainta jolloin kuka tahansa voi lähettää viestin, joka on salattu vastaanottajan julkisella avaimella mutta ainoastaan vastaanottaja, joka tuntee oman yksityisen avaimensa pystyy purkamaan salatun viestin.

Miten RSA-algoritmin avaimet on valittava? [+]

• Valitaan $n=p\cdot q$ missä $p$ ja $q$ ovat kaksi isoa alkulukua siten, että luvun $n$ jakaminen alkulukutekijöiksi on ylivoimaisen vaikeata (jolloin myös esimerkiksi $\abs{p-q}$:n on oltava "iso").
• Valitaan $k$ olemaan iso luku siten että $\Gcd(k,m)=1$ missä $m=(p-1)\cdot (q-1)$.
• Eukleideen algoritmin avulla määritetään $d$ siten, että $[d]_m= [k]_m^{-1}$.

Salaus siis perustuu siihen, että on vaikeata määrittää lukua $d$ jos lukua $m$ ei tunneta ja sen laskemiseksi tarvitaan luvut $p$ ja $q$.

Esimerkki [+]

Jos RSA-algoritmilla ja julkisella avaimella $(55,23)$ haluamme salata viestin $9$ niin meidän pitää laskea $\Mod(9^{23},55)$. Vaikka luvut $55$ ja $23$ ovat salauksen kannalta aivan liian pieniä, ei ole järkevää laskea ensin $m=9^{23}$ ja sitten $\Mod(m,55)$. Sen sijaan toteamme ensin, että $23=16+4+2+1=2^4+2^2+2^1+2^0$ joten $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$ ja joka vaiheessa voimme soveltaa $\Mod$-funktiota eli laskemme ensin $\Mod(9^2,55)= 26$ sitten $\Mod(9^4,55)=\Mod(26^2,55)=16$ jne. jolloin saamme $\Mod(9^j,55)$ kun $j=1,2,4,8,16$. Lopuksi laskemme $\Mod(9^3,55)= \Mod(9\cdot 9^2,55)=\Mod(9\cdot 26,55)$ ja sitten samalla tavalla $\Mod(9^7,55)$ ja $\Mod(9^{23},55)$. Tehokkaimmen voimme tehdä tämän seuraavan algoritmin avulla joka laskee $\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

Tämän algoritmin avulla saamme seuraavat välitulokset kun laskemme $\Mod(9^{23},55)$ eli 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$

ja viimeinen $z$-arvo $14$ on salattu viesti.
Huomaa, että $k$:n arvoista muodostettu jono $10111$ on luvun $23$ binääriesitys.

Jotta voisimme purkaa lähetettyä viestiä $14$ meidän täytyy tietää mikä yksityinen avain on ja koska $55=5\cdot 11$ ja $(5-1)\cdot (11-1)=40$ niin meidän täytyy laskea $[23]_{40}^{-1}$ ja saamme vastaukseksi $[7]_{40}$ koska $\Mod(23\cdot 7,40)= \Mod(161,40)=1$. Yksityinen avain on siis $(55,7)$ ja meidän pitää laskea $\Mod(14^7,55)$. Jos käytämme samaa algoritmia kuten edellä lasku näyttää seuraavanlaiselta:

$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$

Miksi RSA-algoritmi toimii? [+]

• Oleta ensin yksinkertaisuuden vuoksi, että $\Gcd(a,n)=1$.
• $\varphi(n) =\varphi(p\cdot q)=(p-1)\cdot(q-1) =m$.
• Eulerin lauseen mukaan $[a^m]_n=[1]_n$.
• Koska $[d]_m= [k]_m^{-1}$ niin $k\cdot d=1+ r\cdot m$ ja josta seuraa, että $\Mod(b^d,n)=\Mod(a,n)=a$.

Miksi RSA-algortimi toimii jos $\Gcd(a,n)\neq 1$? [+]

• Koska oletamme, että $0 < a< n$ niin $\Gcd(a,n)\neq 1$ ainoastaan jos $p\,|\,a$ tai $q\,|\,a$. Oletamme seuraavaksi, että $p\,|\,a$ joten $a=p^j\cdot c$ missä $\Gcd(c,n)=1$.
• Nyt $[b^d]_n=[((p^j\cdot c)^k)^d]_n=[(p^k)^d]_n^j\cdot [(c^k)^d]_n$ ja koska $\Gcd(c,n)=1$ niin $[(c^k)^d]_n=[c]_n$ ja meidän täytyy vielä osoittaa, että $[(p^k)^d]_n=[p]_n$ koska silloin $[b^d]_n= [p]_n^j\cdot [c]_n = [p^j\cdot c]_n= [a]_n$.
• Koska $q$ on alkuluku niin $\varphi(q)=q-1$ ja koska myös $p$ on alkuluku ja $p\neq q$ niin $\Gcd(p,q)=1$ joten Eulerin lauseesta seuraa, että $[p^{q-1}]_q=[1]_q$.
• Silloin myös $[p^{(q-1)(p-1)r}]_q=[1]_q$ eli $p^{(q-1)(p-1)r}= 1+ sq$ ja kun kerromme molemmat puolet $p$:llä saamme $p^{1+(q-1)(p-1)r}= p + spq=p+sn$. Koska $[d]_m=[k]_m^{-1}$ niin $k\cdot d=1+mr=1+(p-1)(q-1)r$ ja näin ollen $[(p^k)^d]_n=[p^{1+(q-1)(p-1)r}]_n = [p]_n$ ja algoritmi toimii siis myös tässä tapauksessa!

RSA-algoritmi ja allekirjoukset[+]

Jos A haluaa lähettää viestin $a$ B:lle ja B haluaa tulla vakuuttuneeksi siitä, että viesti todella on peräisin A:lta niin he voivat toimia seuraavalla tavalla:

• A laskee tiivisteen eli hajautusarvon $h(a)$ viestistä $a$.
• A salaa viestin $a$ B:n julkisella avaimella $(n_B,k_B)$ salatuksi viestiksi $b=\Mod(a^{k_B},n_B)$.
• A salaa tiivisteen $h(a)$ omalla yksityisella avaimellaan $(n_A,d_A)$ allekirjotukseksi $s=\Mod(h(a)^{d_A},n_A)$.
• A lähettää $b$:n ja $s$:n B:lle.
• B purkaa $b$:n yksityisellä avaimellaan $(n_B,d_B)$ ja saa tulokseksi $a$:n.
• B laskee tiivisteen $h(a)$:n ja purkaa $s$:n A:n julkisella avaimella $(n_A,k_A)$ ja jos tulos on sama kuin $h(a)$ niin hän tulee vakuuttuneeksi siitä, että viesti $a$ todella on peräisin $A$:lta koska kukaan muu ei pysty salaamaan $h(a)$:ta $A$:n yksityisellä avaimella $(n_A,d_A)$.

Koska $[k]_{m}=[d]_{m}^{-1}$ niin viesti joka on salattu yksityisellä avaimella voidaan purkaa julkisella avaimella.

Esimerkki [+]

A haluaa lähettää B:lle viestin $9$ ja lisätä siihen allekirjoituksen, jotta B voi olla varma siitä, että A todella on viestin lähettäjä.

Jos nyt A:n julkinen RSA-avain on $(n_A,k_A)=(91,11)$, yksityinen avain on $(n_A,d_A)=(91,59)$ ja vastaavasti B:n julkinen avain on $(n_B,k_B)=(55,23)$ ja yksityinen avain $(n_B,d_B)=(55,7)$ ja hajautusfunktiona käytetään $h(x)= \lfloor 2^{6}\cdot \Mod(x\cdot (\sqrt{5}-1)/2,1)\rfloor$ niin A ja B suorittavat seuraavat laskut:

• A salaa viestin $9$ B:n julkisella avaimella ja saa tulokseksi $\Mod(9^{k_B},n_B)=\Mod(9^{23},55)=14$
• A laskee tiivisteen $h(9)=35$.
• A salaa allekirjoituksen omalla yksityisellä avaimellaan ja saa tulokseksi allekirjoituksen $\Mod(35^{d_A},n_A)=\Mod(35^{11},91)=42$.
• A lähettää luvut $14$ ja $42$ B:lle.
• B purkaa viestin salauksen omalla yksityisellä avaimella ja saa tulokseksi $\Mod(14^{d_B},n_B)=\Mod(14^7,55)= 9$.
• B laskee tiivisteen $h(9)=35$.
• B purkaa A:n lähettämän allekirjoituksen A:n julkisella avaimella ja saa tulokseksi $\Mod(42^{k_A},n_A)=\Mod(42^{59},91) =35$.
• Koska tulos on $h(9)$ niin B luottaa siihen, että A on viestin lähettäjä.