Naloga: Algoritem za zakrivanje z javnim ključem

Iz MaFiRaWiki

Vsebina

O RSA algoritmu

Danes najbolj znani algoritem za zakrivanje z javnim ključem RSA so ustvarili Ron Rivest, Adi Shamir in Leonard Adelman leta 1978 na ameriškem inštitutu MIT.
Algoritem temelji na celoštevilski algebri in izkorišča lastnosti velikih praštevil.
Šibka točka algoritma je počasnost.
Vzrok je izračun šifriranja in dešifriranja, saj gre za potenciranje dveh zelo velikih števil, operacija je zato računsko zahtevna in zato tudi počasna.
Algoritem je zatorej primeren za skrivanje krajših sporočil.

Ideja RSA algoritma

RSA ima dva ključa in sicer javni in privatni ključ.
Javni ključ je torej lahko znan vsem (sporočili so ga po radiu) in se uporablja za šifriranje.
Sporočilo šifrirano z javnim ključem je lahko dešifrirano samo z privatnim ključem.
Javni in privatni ključ generiramo na naslednji način:
1. korak
izberemo si dve veliki praštevili p in q, p \neq q (n se uporablja kot modul za javni in privatni ključ)
2. korak
izračunamo n = pq
3. korak
izračunamo \varphi(n)=(p-1)(q-1)
4. korak
izberemo si naravno število e, 1<e< \varphi(n) in veljati mora, da je največji skupni delitelj števil e in \varphi(n) enak 1, torej D(e, \varphi(n))=1 (e je javni eksponent)
5. korak
izračunajmo d tako, da bo zadostoval enačbi de \equiv 1 (mod\ \varphi(n)) oz. de=1+k \varphi(n), kjer je k \in \mathbb{Z} (d je privatni eksponent)

Šifriranje

Pošiljatelj A stori sledeče:
(1) sprejme prejemnikov javni ključ (n,e)
(2) sporočilo predstavi kot naravno število m
(3) izračuna c=m^{e} (mod\ n)
(4) c pošlje prejemniku

Dešifriranje

Prejemnik B stori sledeče:
(1) privatni ključ (n,d) uporabi, da izračuna m=c^{d} (mod\ n)
(2) iz m izvleče sporočilo, ki ga ta predstavlja

Rešitev

Osebna orodja