Kriptografski algoritem RSA

11 minutno branje Zadnja sprememba:

Poklon RSA algoritmu
Kazalo

Uporaba RSA algoritma je v zatonu. Vzdrževana seznama priporočil Thomasa H. Ptacka Cryptographic Right Answers ali Aarona Toponce-a Cryptographic Best Practices sta verjetno primerna referenca za izbiro namenskega kriptografskega algoritma.


xkcd 538 - Varnost

xkcd 538 - Varnost


1. Uvod

RSA je kriptografski algoritem, ki se uporablja v mnogih internetnih protokolih, ki vključujejo kriptografijo, kot npr. SSL/TLS osnovani protokoli. Uporabljajo jo tudi TrueCrypt, PGP in mnogi drugi programi. Uporabljate jo torej vsakič ko uporabite vpn, https, ssh… Z RSA-o se načeloma kriptirajo ključi. O kriptografiji bom pisala enkrat drugič, ko mi bo čas dovoljeval.

Z RSA algoritmom sva kolegici že več kot 10 let in sva v tem času razvili prav poseben odnos. V tem času me nikoli ni pustila na cedilu, je moja zvesta spremljevlka. Redno jo uporabljam, tako kot vsi vi ostali, ki se mogoče tega niti ne zavedate, in redno spremljam kaj se z njo dogaja. Vsake toliko časa se pojavi novica o njenem razbitju, ki se izkaže za neresnico in gre v bistvu za napade na generacijo ključev ali prisluškovanje na virtualnih sistemih, kjer si več sistemov deli isti CPU itd… Več si lahko preberete: Dvajset let napadov na RSA.

Vsekakor pa jo bodo enkrat razbili in že napovedujejo njene naslednike ECC (Elliptic Curve Cryptography) in nekoč v prihodnosti kvantno kriptografijo. Preden pa se to zgodi, ji bom namenila ta tekst, kot znak mojega spoštovanja. Oglejmo si torej osnovni matematični koncept RSA-e, kriptografskega algoritma, ki temelji na zelo velikih praštevilih. Z implementacijo RSA v protokole in sisteme se ne bom ukvarjala. Prav tako se ne bom ukvarjala z možnimi načini razbitja tega algoritma.

Algoritem je dobil ime po svojih “mentorjih”: Ron Rivest, Adi Shamir in Leonard Adleman (Adi Shamir je leta 1984 popolnoma razbil konkurenčni algoritem Merkle-Hellman Knapsack), ki so ga prvi javno objavili leta 1977. Črke RSA so začetnice njihovih imen. Ekvivalenten sistem je že leta 1973 predstavil angleški matematik Clifford Cocks, zaposlen pri GCHQ (Government Communications Headquarters), ki pa ga ni mogel javno objaviti. Zelo blizu odkritja tega algoritma je bil že Leonhard Paul Euler (1707 - 1783). /Saj se spomnite, da smo se učili o Eulerjevem številu, ne?/ V njegovih časih pa ni bilo potrebe po takem algoritmu, pa tudi računanje s svinčnikom in papirjem je bilo zamudno. RSA algoritem je zanimiv primer, kako najbolj abstraktne matematične strukture najdejo uporabno vrednost v realnem svetu.


2. Potrebna predznanja

Za razumevanje delovanja RSA so potrebna nekatera matematična predznanja.


2.1. Osnovni izrek o deljenju

Za vsako celo število m in neničelno število n obstajata enolično določeni celi števili k in r, da velja


$$m = kn + r ;\quad 0 \leq r \le |n|$$

Število k je količnik in r ostanek pri deljenju števila m s številom n.

Osnovni izrek o deljenju apliciramo na končna polja. Neskončna polja poznate, v njih vedno računate. To so \(\mathbb{N}, \mathbb{Z}, \mathbb{R}, \mathbb{Q}, \dots \) Tukaj pa se bomo ukvarjali s končnimi polji, torej polji s končnim številom elementov. Na primer: \(\mathbb{F}_2=\lbrace 0, 1\rbrace\).

Opomba: V tekstu veliko uporabljam besedo polje, zato je primerno, da polje definiram. Polje je komutativni obseg. Torej algebrska struktura, v kateri množimo, delimo, seštevamo in odštevamo na nam običajen način.

Navajam definicijo polja po Clarku v Elements of abstract algebra, da ne bo pomote:

Polje je množica \(\mathbb{F}\) z dvema operacijama (seštevanje in množenje), ki dodelita vsakemu urejenemu paru (a, b) elementov iz \(\mathbb{F}\) dva elementa v \(\mathbb{F}\), imenovana vsota, a + b, in produkt, ab, na tak način, da velja:
1. \(\mathbb{F}\) je abelska grupa za seštevanje (z identiteto 0);
2. \(\mathbb{F}^{\ast}\), množica neničelnih elementov \(\mathbb{F}\), je abelska grupa za množenje;
3. za poljubne \(a, b, c \in F\) velja: \(a(b+c)=ab+ac\) in \((a+b)c=ac+bc\).

2.2. Računanje po modulih

Osnovni izrek o deljenju apliciramo na končna polja s pomočjo modulov. Vzemimo za primer polje z 12 elementi. V tem polju imamo števila \(\lbrace 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\rbrace\). Kako naj torej zapišem število 16? Preprosto. Štejemo znova. 12 postane 0, 13=1, 14=2, 15=3 in 16 je torej 4. Zapišemo \(16\equiv 4 \pmod{12}\). 4 je v bistvu ostanek pri deljenju števila 16 s številom 12. S pomočjo osnovnega izreka o deljenju lahko zapišemo: \(16 =1\cdot 12 +4\).

Še en primer:

\(9835\equiv 7 \pmod{12}\), saj lahko zapišemo: \(9835 = 819\cdot 12 + 7\) ali 7 je ostanek pri deljenju števila 9835 s številom 12.
\(1176\equiv 0 \pmod{12}\), ker je \(1176 = 98\cdot 12 +0\).
\(9835 + 1176 = 7 + 0 = 7 \pmod{12}\).

V izogib dolgotrajnem računanju na roke, sem si za ta tekst napisala kratek program v Pythonu. Omejila sem se na potenciranje, saj bom to počela v nadaljevanju. Če ga želite uporabiti, si skopirajte kodo s pomočjo kakega tekstovnega editorja, ga shranite kot, na primer mod.py in ga izvedite: python mod.py v terminalu. Za winse pa nimam pojma. o.O Se boste že znajdli, Google vse ve.

#!/usr/bin/env python
# mod.py

a=int(input("Vpiši število:"))
b=int(input("Vpiši eksponent:"))
c=int(input("Vpiši modul:"))
print("Rezultat je")
print (a**b%c)
Pri programiranju je % zelo prikladen operator za računanje po modulih. Je neumestno, vendar si ne morem pomagati. Ko omenim %, se vedno spomnim na kolegovo izjavo: "% is the Devils' operator!"

To točko sem malo poenostavila. Relacija o kateri sem govorila se imenuje kongruenca, več o njej si lahko preberete na Wikipediji.


2.3. Osnovni izrek aritmetike

Vsako naravno število večje od ena lahko zapišemo na en sam način kot produkt potenc s praštevilskimi osnovami.

\[n = p_1^{m_1}\cdot p_2^{m_2}\cdot p_3^{m_3}\cdots p_k^{m_k}\]

Primer:

\(1176=2\cdot 2\cdot 2\cdot 3\cdot 7\cdot 7 = 2^3 \cdot 3^1\cdot 7^2\)

Števila 1176 se ne da drugače zapisati kot produkt potenc s praštevilskimi osnovami in če te potence množimo bomo vedno dobili 1176.


2.4. Tuje število

Tuji števili sta dve celi števili a in b, ki nimata skupnega deljitelja razen 1 in -1, oziroma enakovredno, katerih največji skupni deljitelj je enak 1. \(D(a, b) = 1\)

Primer:

\(D(15, 10) = 5\), saj lahko zapišemo \(10 = 2\cdot 5\) in \(15 =3\cdot 5\). Število 5 torej deli obe števili. Števili 15 in 10 si nista tuji.

\(D(21, 10) = 1\), saj lahko zapišemo \(21 = 3\cdot 7\) in \(10 = 2\cdot 5\). Števili 21 in 10 nimata nobenega skupnega deljitelja razen 1. Sta torej tuji števili.


2.5. Eulerjeva \(\phi\) funkcija

Eulerjeva funkcija \(\phi(n)\) je preslikava iz naravnih števil nase:

\[\phi(n)=;|;{k \in \mathbb{N}_0 ;|; 0 \leq k \leq n-1,; (k,n) = 1};|; .\]

Za praštevilo n je očitno \(\phi(n)=n-1\). Če je n produkt dveh praštevil, v našem primeru \(n=p\cdot q\), pa velja \(\phi(p\cdot q)=(p-1)(q-1)\). Dokaza ne navajam.

Povedano drugače: Eulerjeva \(\phi\) funkcija je multiplikativna aritmetična funkcija poljubnega celega števila n in da skupno število pozitivnih celih števil, ki ne presegajo n, in so n tuja.

Primer:

\(\phi(8)=4\), ker so štiri števila (1, 3, 5 in 7) tuja številu 8.


3. Teorija

Obnovili smo vsa potrebna predznanja in sedaj se lahko lotimo algoritma samega.

Algoritem je asimetričen, kar pomeni, da sta ključa za šifriranje in dešifriranje različna. Delovanje algoritma RSA temelji na zelo velikih praštevilih. Dve praštevili p in q pomnožimo, da dobimo n = pq. Nato moramo izbrati naravno število e, ki je manjše od n in nima s produktom (p-1)(g-1) nobenega skupnega delitelja, razen 1. Sedaj poiščemo še takšno število d, da bo izraz (ed-1) deljiv z z izrazom (p-1)(q-1). Vrednosti e in d tako pomenita javni in zasebni komponenti. Šele par n in e tvorita pravi javni ključ, par n in d pa zasebnega. Števili p in q lahko preprosto zbrišemo ali ju shranimo skupaj z zasebnim ključem, nikakor pa ne z javnim. V tem primeru lahko s pomočjo praštevil in javnega ključa kaj hitro razdrejo šifrirano sporočilo. Vrednost praštevila d je praktično nemogoče razvozlati samo iz javnega ključa, torej iz števil n in e.

Povzemimo na hitro:

  1. Izberemo praštevili p in q tako da velja \(p\not= q\).
  2. Izračunamo \(n = p\cdot q\).
  3. Izračunamo vrednost Eulerjeve \(\phi\) funkcije. Torej \(\phi(n)=(p-1)(q-1)\).
  4. Izberemo celo število e, tako da velja \(1 < e < \phi(n)\), ki je tuje številu \(\phi(n)\).
  5. Izračunamo d, tako da velja \(d\cdot e\equiv 1\pmod{\phi(n)}\). Torej \(d\cdot e = 1 + k\phi(n)\) za celoštevilčno vrednost k.
  6. Kodiramo in dekodiramo z \(w^e\equiv z\pmod n\) in \(z^d\equiv w\pmod n\).

4. Primer

Poglejmo si poenostavljen primer pošiljanja sporočila.

Denimo, da si želiva s prijateljem poslati sporočilo EOF (end of file). Gremo po zgornjih točkah. Torej:


4.1. korak

Izberemo praštevili p in q. Izbrali bomo primerno majhna števila, da lahko z njimi računamo tudi brez računalnika. Naj bo \(p = 5\) in \(q = 7\).


4.2. korak

Izračunamo \(n = p\cdot q\), torej \(n = 5\cdot 7 = 35\).


4.3. korak

Izračunamo vrednost Eulerjeve funkcije. Torej število tujih števil številu 35. \(\phi(n) = (p-1)\cdot (q-1)\). Dobimo: \(\phi(35)=(5-1)\cdot (7-1)=4\cdot 6 =24\).


4.4. in 4.5. korak

Določimo števili e in d, ki nista enaki in sta različni od 1. Števili e in n tvorita javni ključ, števili d in n pa privatni ključ. Ti dve stopnji bomo združili, da si olajšamo delo. Iščemo torej dve taki števili, da velja: \(d\cdot e= 1 +k\phi(n)\). Naš \(\phi(n)=\phi(35)=24\). Gremo po vrsti za k= 1, 2, 3, 4…:

\(k=1\): \(1+1\cdot 24=25=5\cdot 5\); Števili ne ustrezata kriterijem, saj sta enaki. e in d bi bila v tem primeru 5. Gremo dalje.
\(k=2\): \(1+2\cdot 24=49=7\cdot 7\); e=d=7, torej tudi ne ustrezata. Dalje.
\(k=3\): \(1+3\cdot 24= 73=73\cdot 1\); Tudi ne ustrezata kriterijem, saj bi bil e=1.
\(k=4\): \(1+4\cdot 24=97=97\cdot 1\); Ne ustrezata kriterijem. Glej prejšnji primer.
\(k=5\): \(1+5\cdot 24=121=11\cdot 11\); Zopet ne ustrezata kriterijem. Glej zgoraj.
\(k=6\): \(1+6\cdot 24=145=5\cdot 29\); Imamo prvi par, ki zadosti kriterijem. Lahko bi šli dalje in iskali še kakšnega. Vendar se bomo za naš primer ustavili tukaj. Izberemo \(e= 5\) in \(d =29\).

Tem kalkulacijam se ognemo z uporabo spodnje skripte.

Za silo deluje. Napišete si lahko tudi svojo, bolj optimizirano. Uporabite jo tako kot sem opisala pri zgornji rsa.py skripti.

Če vpišem za število 5 in za modul \(\phi(35)=24\), dobim kot možne kandidate 5, 29, 53, 77, saj sem zgornjo mejo postavila na 100. Število 5 moram seveda izločiti, saj ne zadosti kriterijem. Mi smo izbrali število 19. Seveda bi lahko poiskali tudi čisto drugi števili: npr. 7 in 31 ali 11 in 35…

#!/usr/bin/env python
# rsa_r.py

a=int(input("Vpiši število:"))
b=int(input("Vpiši modul:"))

for i in range(1,100):
r=a*i%b
if r==1:
print("Rezultat je:")
print(i)

4.6. korak

Številom manjšim in tujim našemu n bomo dodelili črke. Naš n je 35. Izločiti torej moram: 1, 5, 7, 10, 14, 15, 20, 21, 25, 28, 30 in 35. Ostane nam 23 števil s katerimi lahko operiramo. Slovenska abeceda ima 25 črk, zato sem jo malo prilagodila za naš primer. Črkam priredim številke nekako takole:

ABCDEFGHIJKL
234689111213161718
MNOPRSŠTUVZ
1922232426272931323334

Torej je \(E = 8\), \(O = 23\) in \(F = 9\). Začnimo s kodiranjem, torej računajmo \(w^e\equiv z \pmod n\). Sama si bom pomagala z zgornjim programom, saj se mi ne da preveč množit in delit na roke. Sicer pa gre tako, kot smo povedali pri osnovnem izreku o deljenju in pri računanju po modulu. Dobro naj vam bo, tako kot vedno se vas usmilim. E bom zakodirala na roke.

\(E=8\). Torej računam \(8^5=32768\) v desetiškem sistemu. Sedaj pa moram to število pretvoriti po modulu 35. Poiskat moram torej ostanek pri deljenju števila 32768 s številom 35. Uporabim osnovni izrek o deljenju in dobim \(32768=35\cdot 936+8\). 8 se torej zakodira v 8 in naš E ostane E. Isti postopek ponovimo še za števili 23 in 9.

\(8^5\equiv 8\pmod{35}\)
\(23^5\equiv 18\pmod{35}\)
\(9^5\equiv 4\pmod{35}\)

Glede na zgornjo tabelo smo torej dobili:

\(E=8\Rightarrow 8=E\)
\(O=23\Rightarrow 18=L\)
\(F=9\Rightarrow 4=C\)

Iz EOF smo dobili ELC. Šifrirano sporočilo se torej glasi ELC.

Dekodirajmo sedaj to sporočilo s potenciranjem na 29, ki je naš d. \(z^d\equiv w\pmod{35}\)

\(8^{29}\equiv 8\pmod{35}\)
\(18^{29}\equiv 23\pmod{35}\)
\(4^{29}\equiv 9\pmod{35}\).

Iz števil 8, 23, 9 razberemo EOF s pomočjo zgornje tabele.


Dodatna gradiva


Viri


EOF