Lankide:Joseba.makazaga/Proba orria

4.1.2 Zatigarritasuna. Zenbaki lehenak

${\textstyle \mathbb {Z} ^{*}}$ multzoa ${\textstyle /}$ zatiketarako itxia ez bada ere, badira kasu batzuk non zenbaki oso batek beste bat zehazki zatitzen duen. Esaterako, ${\textstyle 4}$-ak ${\textstyle 12}$-a zehazki zatitzen du (${\textstyle 12=3\cdot 4}$). Hau da, ${\textstyle 12}$ zati 4 egitean, zatiduratzat ${\textstyle 3}$ zenbaki osoa eta hondartzat ${\textstyle 0}$ lortuko ditugu.

Definizioa. ${\textstyle a,b\in \mathbb {Z} }$ zenbakiak emanik, ${\textstyle a\neq 0}$ izanik, esango dugu ${\textstyle a}$ zenbakiak ${\textstyle b}$ zenbakia zatitzen duela, eta ${\textstyle a\mid b}$ adieraziko dugu, baldin $$\exists k\in \mathbb {Z} \;{\mbox{ non }}\;b=ka{\mbox{ den }}$$ Hori gertatzen denean, esango dugu ${\textstyle a}$ zenbakia ${\textstyle b}$ zenbakiaren zatitzaile bat dela, edo ${\textstyle b}$ zenbakia ${\textstyle a}$ zenbakiaren multiplo bat dela.
Hitzarmena. ${\textstyle a\mid b}$ idazten dugunean, ${\textstyle a\neq 0}$ dela suposatuko dugu.

• ${\textstyle a,b\in \mathbb {Z} ^{+}}$ bada, berehala egiazta daiteke emaitza hau: $$a\mid b\;\Rightarrow \;a\leq b$$

Ondoko teoreman zatigarritasunaren propietate batzuk frogatuko ditugu.

Teorema. [propietateak] ${\textstyle a,b,c\in \mathbb {Z} }$ emanik,

1. ${\textstyle 1\mid a}$; ${\textstyle a\mid a}$; ${\textstyle a\mid 0}$. (${\textstyle a\neq 0}$)
2. ${\textstyle (a\mid b)\;\wedge \;(b\mid a)\;\Rightarrow \;a=b\;\vee \;a=-b}$. (${\textstyle a\neq 0,b\neq 0}$)
3. ${\textstyle (a\mid b)\;\wedge \;(b\mid c)\;\Rightarrow \;a\mid c}$. (${\textstyle a\neq 0,b\neq 0}$)
4. ${\textstyle a\mid b\;\Rightarrow \;(\forall x\in \mathbb {Z} )\;\;a\mid xb}$. (${\textstyle a\neq 0}$)
5. ${\textstyle (a\mid b)\wedge (a\mid c)\;\Rightarrow \;(\forall x,y\in \mathbb {Z} )\;\;a\mid xb+yc}$. (${\textstyle a\neq 0}$)

Froga.

1. ${\textstyle a=1a.}$ Hortaz,   ${\textstyle 1\mid a}$ eta ${\textstyle a\mid a}$. Bestalde, ${\textstyle 0=0a.}$ Hortaz,   ${\textstyle a\mid 0}$.
2. Hasteko daukagu, ${\textstyle (a\mid b)\;\wedge \;(b\mid a)}$, hau da, $$\left.{\begin{array}{c}a\mid b\\\wedge \\b\mid a\end{array}}\right\}\;\Rightarrow \;\left.{\begin{array}{c}b=k_{1}a,\;k_{1}\in \mathbb {Z} {\mbox{ izanik}}\\\wedge \\a=k_{2}b,\;k_{2}\in \mathbb {Z} {\mbox{ izanik}}\end{array}}\right\}\;\Rightarrow \;b=k_{1}(k_{2}b)=(k_{1}k_{2})b,$$ $$k_{1},k_{2}\in \mathbb {Z} {\mbox{ izanik}}\Rightarrow \;k_{1}k_{2}=1,\;k_{1},k_{2}\in \mathbb {Z} {\mbox{ izanik}}\;\Rightarrow \;\left.{\begin{array}{c}k_{1}=k_{2}=1\\\vee \\k_{1}=k_{2}=-1\end{array}}\right\}\;\Rightarrow \;\left.{\begin{array}{c}a=b\\\vee \\a=-b.\end{array}}\right.$$
3. Kasu honetan ${\textstyle (a\mid b)\;\wedge \;(b\mid c)}$ daukagu, $$\left.{\begin{array}{c}a\mid b\\\wedge \\b\mid c\end{array}}\right\}\;\Rightarrow \;\left.{\begin{array}{c}b=k_{1}a,\;k_{1}\in \mathbb {Z} {\mbox{ izanik}}\\\wedge \\c=k_{2}b,\;k_{2}\in \mathbb {Z} {\mbox{ izanik}}\end{array}}\right\}\;\Rightarrow \;c=k_{2}(k_{1}a)=(k_{2}k_{1})a,$$ ${\textstyle k_{2}k_{1}\in \mathbb {Z} {\mbox{ izanik }}\;\Rightarrow a\mid c}$.
4. Edozein ${\textstyle x\in \mathbb {Z} }$ emanik, $$a\mid b\;\Rightarrow \;b=ka,\;k\in \mathbb {Z} {\mbox{ izanik}}\;\Rightarrow \;xb=x(ka)=(xk)a,\;xk\in \mathbb {Z} {\mbox{ izanik}}\;\Rightarrow \;a\mid xb.$$
5. Edozein ${\textstyle x,y\in \mathbb {Z} }$ emanik, $$\left.{\begin{array}{c}a\mid b\\\wedge \\a\mid c\end{array}}\right\}\;\Rightarrow \;\left.{\begin{array}{c}b=k_{1}a,\;k_{1}\in \mathbb {Z} {\mbox{ izanik}}\\\wedge \\c=k_{2}a,\;k_{2}\in \mathbb {Z} {\mbox{ izanik}}\end{array}}\right\}\;\Rightarrow xb+yc=x(k_{1}a)+y(k_{2}a)=$$ $$=(xk_{1}+yk_{2})a,\;xk_{1}+yk_{2}\in \mathbb {Z} {\mbox{ izanik }}\;\Rightarrow \;a\mid xb+yc.$$ ${\textstyle \Box }$

• ${\textstyle b,c\in \mathbb {Z} }$ emanik, $$xb+yc,\quad x,y\in \mathbb {Z} {\mbox{ izanik}},$$ adierazpenari ${\textstyle b,c\in \mathbb {Z} }$ zenbakien konbinazio lineal deituko diogu.

  ${\textstyle a}$ zenbakiak ${\textstyle b}$ eta ${\textstyle c}$ zenbakiak zatitzen baditu, [propietateak]-5 Teoremaren arabera, ${\textstyle a}$ zenbakiak ${\textstyle b}$ eta ${\textstyle c}$ zenbakien edozein konbinazio lineal zatituko du. Propietate hori zabal daiteke honela:

• ${\textstyle b_{1},\cdots ,b_{n}\in \mathbb {Z} }$ emanik, $$x_{1}b_{1}+\cdots +x_{n}b_{n},\quad x_{1},\ldots ,x_{n}\in \mathbb {Z} {\mbox{ izanik}},$$ adierazpenari ${\textstyle b_{1},\ldots ,b_{n}}$ zenbakien konbinazio lineal deituko diogu.

  ${\textstyle a}$ zenbakiak ${\textstyle b_{1},\ldots ,b_{n}}$ zenbakiak zatitzen baditu, ${\textstyle a}$ zenbakiak ${\textstyle b_{1},\ldots ,b_{n}}$ zenbakien edozein konbinazio lineal zatituko du: $$a\mid b_{i},\;i=1,\cdots ,n\;\Rightarrow \;(\forall x_{1},\cdots ,x_{n}\in \mathbb {Z} )\quad a\mid x_{1}b_{1}+\cdots +x_{n}b_{n}.$$

Adibidea. [Grimaldi4.20] Ba al daude ${\textstyle 5x+10y+20z=1003}$ ekuazioa betetzen duten zenbaki osoak?

Demagun ${\textstyle x,y,z}$ zenbaki oso horiek daudela. ${\textstyle 5\mid 5}$, ${\textstyle 5\mid 10}$ eta ${\textstyle 5\mid 20}$ betetzen direnez, ${\textstyle 5\mid 1003}$ ere beteko litzateke; baina hori ez da gertatzen. Hortaz, ez daude ekuazioa betetzen duten ${\textstyle x,y,z}$ zenbaki osoak.
Definizioa. Izan bedi ${\textstyle n\in \mathbb {Z} ^{+}}$, ${\textstyle n>1}$.

Esango dugu ${\textstyle n}$ zenbaki lehena dela bere zatitzaile positibo bakarrak ${\textstyle n}$ eta ${\textstyle 1}$ badira: $$m\mid n,\quad m\in \mathbb {Z} ^{+}\,\Longrightarrow \,m=1\,\vee \,m=n;$$ eta esango dugu ${\textstyle n}$ zenbaki konposatua dela ez bada lehena: $$\exists m_{1},m_{2}\in \mathbb {Z} ^{+}\;{\mbox{ non }}\;n=m_{1}m_{2},\,\quad 1<m_{1}<n,\;1<m_{2}<n.$$
Adibidea. ${\textstyle 12}$ zenbaki konposatua da, ${\textstyle 12>1}$ delako eta ${\textstyle 1}$, ${\textstyle 2}$, ${\textstyle 3}$, ${\textstyle 4}$, ${\textstyle 6}$ eta ${\textstyle 12}$ zatitzaileak dituelako.

${\textstyle 11}$ zenbaki lehena da, ${\textstyle 11>1}$ delako eta bere zatitzaile positibo bakarrak ${\textstyle 1}$ eta ${\textstyle 11}$ direlako.
Hurrengo Teoreman zenbaki lehenen eta konposatuen arteko erlazio bat frogatuko dugu.

Teorema. [lekon] Zenbaki konposatu orok zatitzaile lehenen bat dauka. Hau da, ${\textstyle n\in \mathbb {Z} ^{+}}$, ${\textstyle n>1}$ emanik, $$n\,{\mbox{ konposatua }}\,\Longrightarrow \exists p\in \mathbb {Z} ^{+},\,p\,{\mbox{ lehena eta }}\,p\mid n.$$

Froga.

Izan bedi ${\textstyle S}$ zatitzaile lehenik ez duten zenbaki oso konposatu guztien multzoa: $$S=\{x\in \mathbb {Z} ^{+}\;:\;x\;{\mbox{ konposatua da eta ez du zatitzaile lehenik}}\}.$$ Frogatuko dugu, absurdora eramanez, ${\textstyle S=\emptyset }$ dela.

Demagun ${\textstyle S\neq \emptyset }$ dela. ${\textstyle S}$ multzoa ${\textstyle \mathbb {Z} ^{+}}$ multzoaren azpimultzo ez-hutsa denez, ordena onaren printzipioaren arabera, ${\textstyle S}$ multzoak lehen elementua izango du, ${\textstyle m}$.

${\textstyle m\in S}$ denez, ${\textstyle m}$ konposatua da; beraz, ${\textstyle m_{1},m_{2}\in \mathbb {Z} ^{+}}$ badaude, non ${\textstyle m=m_{1}m_{2}}$ den, ${\textstyle 1<m_{1}<m,\;1<m_{2}<m}$ izanik.

${\textstyle m}$ da ${\textstyle S}$ multzoaren minimoa eta ${\textstyle m_{1}<m}$ da; beraz, ${\textstyle m_{1}\not \in S}$ beteko da. Hortaz, ${\textstyle m_{1}}$ lehena da edo zatitzaile lehenen bat dauka.

${\textstyle m_{1}}$ lehena bada, ${\textstyle m_{1}}$ lehena da eta ${\textstyle m_{1}\mid m}$ betetzen da.

${\textstyle m_{1}}$ zenbakiak ${\textstyle p}$ zatitzaile lehen bat badauka, ${\textstyle p}$ lehena da eta ${\textstyle p\mid m_{1}}$ eta ${\textstyle m_{1}\mid m}$; hortaz, ${\textstyle p\mid m}$.

Bi kasuetan kontraesan bat aurkitu dugu, ${\textstyle m}$ zenbakiak ez baitauka zatitzaile lehenik. Hortaz, ${\textstyle S=\emptyset }$ da, eta zenbaki konposatu orok zatitzaile lehenen bat badauka. ${\textstyle \Box }$

Teorema. (Euklides, Elementuak, IX, 20)

Infinitu zenbaki lehen daude.

Froga.

Absurdora eramanez frogatuko dugu.

Suposa dezagun zenbaki lehenen kopurua finitua dela: ${\textstyle p_{1},\ldots ,p_{k}}$.

Izan bitez ${\textstyle a=p_{1}\ldots p_{k}}$ eta ${\textstyle A=a+1}$.

Orduan, ${\textstyle p_{i}\mid a}$, ${\textstyle i=1,\ldots ,k}$ dugu eta, hortaz, ${\textstyle a\geq p_{i}}$, ${\textstyle i=1,\ldots ,k}$; hortik ${\textstyle A\neq p_{i}}$, ${\textstyle i=1,\ldots ,k}$ aterako dugu. Beraz, ${\textstyle A}$ konposatua da. [lekon] Teoremaren arabera, badago ${\textstyle p_{j}\in \{p_{1},\ldots ,p_{k}\}}$ zenbaki lehenen bat, non ${\textstyle p_{j}\mid A}$ betetzen den.

Orduan, ${\textstyle p_{j}\mid A}$ eta ${\textstyle p_{j}\mid a}$ betetzen dira; hortaz, ${\textstyle p_{j}\mid 1A+(-1)a}$ ere beteko da. Baina ${\textstyle 1A+(-1)a=A-a=1}$ dugu; beraz, ${\textstyle p_{j}\mid 1}$ dugu; eta hori ezinezkoa da ${\textstyle p_{j}>1}$ delako.

Beraz, zenbaki lehenen kopuruak ezin du kopuru finitua izan. Hau da, infinitu zenbaki lehen daude. ${\textstyle \Box }$

4.3 RSA algoritmoa

Mezuak zifratzeko erabiltzen den sistema ezaguna da RSA algoritmoa eta aritmetika modularraren aplikaziotzat har daiteke.

Zenbaki handien faktorizazioa lan nekeza da, hau da, zenbaki handi baten zatitzaile diren zenbaki lehenak zein diren ezagutzeko ez dago algoritmo azkarrik, ondorioz, lehenak diren zenbakiak banan banan hartu eta zenbaki handiaren zatitzaile diren ala ez begiratzea beste erremediorik ez dago. RSA algoritmoaren segurtasuna horretantxe oinarritzen da: zenbaki oso handia aukeratzen du algoritmoak, eta bere zatitzaile diren zenbaki lehenenetatik eratorritako aritmetika modularreko eragiketak baliatzen ditu mezuak zifratzeko.

RSA algoritmoaren jatorria

1977. Urtean Ronald Rivest, Adi Shamir eta Leonard Adleman-ek sortutako kriptografia-sistema da RSA. Zenbaki handien faktorizazioa eragiketa motela den heinean kriptografia-sistema segurua da eta, lehen esan bezala, Zenbaki-Teorian eta Aritmetika Modularrean oinarritzen da. Terminologia aldetik esan behar da enkriptatzea eta zifratzea sinonimotzat erabili ohi direla. Mezu zifratua (enkriptatua) mezua jaso behar duenak bakarrik ulertuko du, eta ulertezina izango da gainerakoentzat. Gakoetan oinarritutako zifratze sistema da, eta bi gako ezberdin erabiltzen ditu, bata publikoa da eta zifratzeko erabiltzen da. Bestea, ordea, sekretua da, eta deszifratzeko beharrezkoa da. Beraz sistema asimetrikoa da.

Mezua jaso behar duenak sortu behar ditu gakoak. Hartzailearen gakoak dira, beraz, prozesuan erabiliko diren gakoak.

RSA algoritmoaren oinarri teorikoak

Zifratze-deszifratze prozesuaren oinarrian Euler-Fermat teorema dagoela esan dezakegu, bai eta Eulerren $\phi (n)$ funtzioaren propietate bat ere. Eta horrez gain, zenbaki baten alderantziko modularraren adierazpena ere kontuan izan behar da eta sistema eraginkorra izan dadin berreketa modularra era eraginkorrean programatzea komeni da.

Teorema. Izan bedi $n=p*q$ non $p$ eta $q$ zenbaki lehenak diren, eta izan bedi $r=s^{-1}{\mbox{mod }}_{\phi (n)}$ eta izan bedi $a<\min(p,q)$, orduan beteko da $a^{r*s}=a$.

Froga.

Teoreman zehaztu da $n$ zenbakia $p$ eta $q$ bi zenbaki lehenen biderketa dela, beraz, badakigu $\phi (n)=(p-1)*(q-1)$ dela. Bestalde, $r=s^{-1}{\mbox{mod }}\phi (n)$ denez, alderantziako modularraren definizioaren arabera $r*s{\mbox{ mod }}_{\phi (n)}=1$ izango da, eta ondorioz, badakigu badagoela $k\in \mathbb {Z}$ zeinarentzat beteko den $r*s=1+k*\phi (n)$, eta beraz, $a^{r*s}=a^{1+k*\phi (n)}$ beteko da. Berdintza horretako bi aldeeetan $n$ modulua kalkulatzen badugu: $$a^{r*s}{\mbox{mod }}_{n}=a^{1+k*\phi (n)}{\mbox{ mod}}_{n}=a*(a^{\phi (n)})^{k}{\mbox{ mod}}_{n}.$$ Badakigu, ordea, euler-Fermat teoremaren arabera, $a$ eta $n$ lehen erlatiboak badira, orduan, $a^{\phi (n)}{\mbox{mod }}_{n}=1$ dela. Kontuan izan behar da, $a<\min(p,q)$ dela eta, beraz, ez dago zatitzaile komunik $a$ eta $n$ zenbakien artean, ondorioz, bi zenbakiak lehen erlatiboak dira eta Euler-Fermaten teorema aplikatuz iritsiko gara bila genbiltzan berdintzara: $a^{r*s}{\mbox{mod }}_{n}=a$.

Teorema horretan oinarritzen da RSA algoritmoa: $a$ mezua bidali beharrean $z=a^{r}{\mbox{mod }}_{n}$ mezu zifratua bidaltzea proposatzen du algoritmoak, eta hori deszifratzeko $z^{s}{\mbox{mod }}_{n}$ kalkulatzea nahikoa da, bai baitakigu $z^{s}{\mbox{mod }}_{n}=a^{r*s}{\mbox{mod }}_{n}=a$ dela.

Gako publikoa eta gako pribatua

Demagun $a$ kodeak adierazten duela zifratu nahi dugun mezua. RSA algoritmoaren oinarriak kontuan hartuz, berreketa modularra erabiliz $$z=a^{r}{\mbox{ mod}}_{n}$$ kalkulatu beharko luke mezua bidali nahi duenak. Beraz, $(n,r)$ zenbakiek ezagunak izan behar dute. Hain zuzen ere gako publikoak bi zenbaki horiexek dira.

Mezua deszifratzeko $z^{s}{\mbox{ mod}}_{n}$ kalkulatu beharko du mezua jaso duenak. Izan ere, badakigu Euler-Fermat-en teoremaren eta alderantzizko modularraren definizioaren ondorioz, $$z^{s}{\mbox{ mod}}_{n}=(a^{r})^{s}{\mbox{ mod}}_{n}=a^{1+k*\phi (n)}{\mbox{ mod}}_{n}a$$ dela, non $k\in \mathbb {Z}$. Beraz, mezu zifratua deszifratzeko behar den informazioa $(n,s)$ zenbakiek osatzen dute; gako pribatua horixe da hain zuzen ere.

Gako publikoa ezagutzera ematen bada, alegia $(n,r)$ zenbakiakak publikoak badira, $n$ zenbakiaren deskonposaketa eginez $p$ eta $q$ zenbakiak ezagutu daitezke, eta ondorioz $\phi (n)=(p-1)*(q-1)$ ere ezagutzea lortuko genuke. Hori guztia ezagutuz, deszifratzeko falta zaigun bakarra $s$ zenbakia da, eta $r=s^{-1}{\mbox{mod }}\phi (n)$ denez, hori ere ezagutzea lortuko genuke. Hau da, gako publikoa ezagutzera emanaz gako pribatua ezagutzeko bidea ematen da. Nola esango dugu, bada, mezua sekretua dela? Sekretu izaera $s$ zenbaki sekretua kalkulatzeko behar den denborak ematen dio: lehen esan bezala, $n$ zenbakia oso handia bada, bere faktorizazioa egiteak eskatzen duen denbora ikaragarria da. Alegia, gako publikoak argitaratu arren bere faktorizazioa egin beharko litzateke eta horrek denbora gehiegi behar du. Ondorioz, $p$, $q$ eta $\phi (n)$ ezezagunak izango dira, eta ezin izango da $s$ kalkulatu.

Esandakoaren arabera, $n$ zenbakia ezagutu arren, $p$ eta $q$ ezkutuan geratzen dira, bai eta $\phi (n)$ ere, ondorioz $r$ ezagutzera eman arren $s$ ezkutuan gordetzen da, izan ere $s$ ezagutzeko $Z_{\phi (n)}^{*}$ multzoan $r$-ren alderantzizkoa kalkulatu beharko genuke, baina multzo hori ezkutuan geratu da.

Gako publikoak eta pribatuak sortzeko prozesua

Adierazi dugun bezala, $r=s^{-1}{\mbox{ mod}}_{\phi (n)}$ bete behar da, horrek ziurtatzen baitu $r*s=1+k*\phi (n)$, non $k\in \mathbb {Z}$.

Gako publikoa $(n,r)$ zenbakiek osatzen dute, Beraz, $n$ zenbakia zehaztu eta ezagutzera eman behar da. Baina $\phi (n)$ ezezaguna izan dadin, aukeratu behar den $n$ zenbakiak oso handia izan behar du, bestela, bere faktorizazioa denbora onargarrian egin ahal izango litzateke eta ondorioz $\phi (n)$ kalkulatu ahal izango litzateke.

Hori gerta ez dadin, $n=p*q$ oso handia aukeratu behar da, hau da, bai $p$ eta bai $q$ zenbaki lehenak izateaz gain zenbaki oso handiak aukeratu behar dira. Horrela, $\phi (n)=(p-1)*(q-1)$ ezin izango da denbora laburrean kalkulatu. Kontuan izan behar da faktorizazioa beti egin daitekeela, alegia, $n$ ezaguna bada, faktorizazioa egin daiteke, baina handia den heinean, faktorizazio horrek denbora luzea hartuko du.

Beraz, $n$ zenbakia zehazteko, $p,q$ zenbaki lehenak aukeratu behar izan ditugu, eta bi zenbaki horiexek zehazten dute $\phi (n)$ zenbakia, bai eta $\mathbb {Z} _{\phi (n)}^{*}$ multzoa ere.

Orain $r$ eta $s$ zenbakiak aukeratu behar dira. Bete behar duten baldintza da $r=s^{-1}{\mbox{ mod}}_{\phi (n)}$. Eta horretarako, $s$ eta $\phi (n)$ zenbakiek elkarren artean lehen erlatiboak izan behar dute, alegia, ${\mbox{zkh}}(\phi (n),s)=1$ bete behar da.

Laburbilduz, prozesuak urrats hauek ditu:

1. Aukeratu $p,q$ zenbaki lehenak eta oso handiak
2. Aukeratu $\phi (n)=(p-1)*(q-1)$ zenbakiaren lehen erlatiboa izango den $s$ zenbakia.
3. Kalkulatu $r=s^{-1}{\mbox{ mod}}_{\phi (n)}$ zenbakia
4. Publikatu $(n,r)$ gako publikoak eta ondo jaso $(n,s)$ gako pribatuak.

Mezu zifratua bidaltzeko prozesua

Norbaiti, demagun Jasoneri, RSA algoritmoa erabiliz mezu zifratua bidali nahi badiogu, Jasonek bere RSA gakoak aukeratuta izan behar ditu, eta gako publikoak ezagutzera emanda izan behar ditu. Jasonek lan hori egina baldin badauka, bere $(n,r)$ gako publikoak ezagunak izango dira, eta ondorioz, guk gure mezua Jasonek deszifratzeko moduan zifratu ahal izango dugu.

Guk mezuari dagokion kodea zifratu behar dugu, hau da, gure mezuari dagokion kodea $a$ baldin bada, $$z=a^{r}{\mbox{ mod}}_{n}$$ kalkulatu behar dugu eta Jasoneri $z$ bidaliko diogu.

Jasonek, beraz, $z$ mezua jasoko du, eta mezua deszifratzeko $z^{s}{\mbox{ mod}}_{n}$ kalkulatu beharko du. Baina badakigu eragiketa horren emaitza $a$ dela. Hau da, gure mezuari dagokion kodea kalkulatuko du Jasonek.

Mezu ziurtatua bidaltzeko prozesua

Gako publikoak eta pribatuak beste erabilera bat ere badute: mezu ziurtatua bidaltzeko aukera ere ematen dute. Alegia mezua bidali duena nor izan den ziurtatzeko aukera ematen dute.

Horretarako, Jasonek mezua bere gako pribatuarekin zifratu behar du, eta guk, bere gako publikoarekin deszifratu behar dugu: Jasonek $a$ mezua bere gako pribatuarekin zifratuta $$z=a^{s}{\mbox{ mod}}_{n}$$ lortuko du $z$ mezu ziurtatua, eta hori bidaliko baligu, guk $$a=z^{r}{\mbox{ mod}}_{n}$$ kalkulatu beharko genuke, eta horrela lortutako $a$ mezuak zentzurik balu, esan ahal izango genuke Jasonek sortutako mezua dela (edo Jasoneren gako pribatua ezagutzen duen norbaitek sortutakoa).