RSA: asimetrični algoritem za šifriranje in kriptografijo z javnim ključem

RSA: asimetrični algoritem za varno šifriranje in kriptografijo z javnim ključem — osnovni principi, generiranje ključev, pomen faktorizacije in praktične uporabe.

Avtor: Leandro Alegsa

14-12-2025 15:22

RSA (Rivest-Shamir-Adleman) je algoritem, ki ga sodobni računalniki uporabljajo za šifriranje in dešifriranje sporočil. Je asimetrični kriptografski algoritem. Asimetrični pomeni, da obstajata dva različna ključa. To se imenuje tudi kriptografija z javnim ključem, saj lahko enega od ključev dobi kdor koli. Drugi ključ mora biti zasebni. Algoritem temelji na dejstvu, da je iskanje faktorjev velikega sestavljenega števila težavno: kadar so faktorji praštevila, se problem imenuje prafaktorizacija. Je tudi generator ključnih parov (javnega in zasebnega ključa).

Osnovni princip in zgodovina

RSA sta leta 1977 razvila Ron Rivest, Adi Shamir in Leonard Adleman. Temelji na enostranski naravi operacij modularne eksponentacije: izračun c = m^e mod n je enostaven, medtem ko je obratna operacija — pridobivanje m iz c brez poznavanja zasebnega eksponenta — težavna, če je n produkt dveh velikih praštevil. Ključna varnostna predpostavka algoritma je, da je faktorizacija velikega sestavljenega števila n (n = p × q) računsko nepraktična z današnjimi metodami, če sta p in q dovolj veliki.

Ustvarjanje ključev (načeloma)

Osnovni koraki za generiranje para ključev so:

Izberemo dve veliki praštevili p in q (običajno vsaj nekaj sto bitov vsako, skupaj za moderno varnost 2048–4096 bitov za n).
Izračunamo n = p × q — to je modulus, ki je del javnega in zasebnega ključa.
Izračunamo φ(n) = (p−1)(q−1) (Eulerjeva funkcija) ali alternativno Carmichaelovo funkcijo λ(n).
Izberemo javni eksponent e, kjer 1 < e < φ(n) in gcd(e, φ(n)) = 1 (pogostečno se uporablja e = 65537 zaradi učinkovite implementacije in varnosti).
Izračunamo zasebni eksponent d kot multiplikativni inverz e modulo φ(n), torej d taki, da e·d ≡ 1 (mod φ(n)).
Par ključa: javni ključ je (n, e), zasebni ključ je (n, d) — zasebni ključ morate varovati.

Šifriranje in dešifriranje

Če želimo sporočilo m šifrirati z javnim ključem (n, e), izračunamo c = m^e mod n. Dešifriranje s zasebnim ključem (n, d) je m = c^d mod n. V praksi mora biti sporočilo najprej ustrezno kodirano/paddingirano (npr. OAEP) in pretvorjeno v številsko vrednost manjšo od n.

Uporabe

Varnost komunikacij v internetu (npr. pri vzpostavitvi TLS povezav) — pogosto RSA uporablja za zaščito izmenjave simetričnih ključev.
Digitalni podpisi — preverjanje pristnosti in integritete sporočil ali programske opreme. Podpis se izvede z zasebnim ključem, preverjanje s javnim ključem.
Infrastrukture javnih ključev (PKI), certifikati X.509 in sistemi upravljanja ključev.

Varnost, ranljivosti in dobre prakse

RSA je varen, če so izpolnjeni določenih pogoji. Pomembne točke:

Velikost ključa: priporočena dolžina je danes vsaj 2048 bitov; za višjo varnost (daljša življenjska doba) se uporablja 3072 ali 4096 bitov.
Puffanje in sheme zapolnitve (padding): vedno uporabite varne sheme (npr. OAEP za šifriranje, PSS za podpise). Nezaščiteno izravnanje ali uporaba surovega RSA je ranljiva na napade (npr. chosen-ciphertext).
Izogibanje ponovnim izkoristkom malih eksponentov in slabo izbranih parametrov; e = 65537 je danes standardna izbira.
Stran-kanalni napadi: zaščititi implementacije pred šumenjem, merjenjem porabe energije, časovnimi razlikami ipd.
Varovanje zasebnega ključa: uporaba HSM-jev, šifriranih ključnic, strojne podpore in omejitev dostopa.
Kvadratno-skoristni učinki kvantnih računalnikov: Shorov algoritem bi faktorizacijo narediti učinkovito, zato je za prihodnost potrebna selitev na post-kvantne algoritme, vendar danes je RSA še vedno široko v uporabi.

Omejitve in zmogljivost

RSA je veliko počasnejši od simetričnih algoritmov (AES ipd.), zato se v praksi pogosto uporablja le za varno izmenjavo simetričnega ključa, medtem ko dejanske podatkovne tokove šifrira simetrični algoritem. Učinkovitost implementacije je odvisna od velikosti ključa in optimizacij modularne aritmetike (CRT pri dešifriranju z zasebnim ključem, kjer se uporablja razcep po p in q, znatno pohitri operacijo).

Priporočila za uporabo

Vedno uporabljajte dobro vzdrževane in preizkušene kriptografske knjižnice (OpenSSL, libsodium, Bouncy Castle ipd.).
Uporabljajte varne načine zapolnitve (npr. OAEP, PSS) in primerno dolžino ključa glede na zahtevano stopnjo varnosti.
Redno obnavljajte in zavračajte stare ključe ter zaščitite zasebni ključ z ustreznimi postopki upravljanja.
Za sisteme, kjer je pričakovana dolga življenjska doba varnosti ali visoko tveganje kvantnih napadov, načrtujte prehod na post-kvantne algoritme.

RSA je temelj sodobne kriptografije z javnim ključem in ostaja široko uporabljen zaradi svoje preprostosti, formalne osnove in podpore v protokolih in standardih. Kljub temu njegova varnost ni samoumevna — pravilna uporaba, ustrezna velikost ključa in varne implementacije so ključni za ohranjanje zaupnosti in integritete komunikacij.

Šifriranje sporočila

Alica svoj javni ključ ( n {\displaystyle n\,} $n\,$ & e {\displaystyle e\,} $e\,$ ) izroči Bobu, svoj zasebni ključ pa ohrani v tajnosti. Bob želi Alici poslati sporočilo M.

Najprej z dogovorjenim reverzibilnim protokolom, znanim kot shema za polnjenje, spremeni M v število m {\displaystyle m} , manjše od n {\displaystyle n} . Nato izračuna šifrirano besedilo c {\displaystyle c\,} $c\,$ , ki ustreza:

c = m e mod n {\displaystyle c=m^{e}\mod {n}} $c=m^{e}\mod {n}$

To lahko hitro storite z metodo eksponentnega računanja s kvadratom. Bob nato pošlje c {\displaystyle c\,} $c\,$ Alici.

Dešifriranje sporočila

Alica lahko obnovi m {\displaystyle m\,} $m\,$ iz c {\displaystyle c\,} $c\,$ z uporabo svojega zasebnega ključa d {\displaystyle d\,} $d\,$ v naslednjem postopku:

m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} $m=c^{d}{\bmod {n}}$

Glede na m {\displaystyle m\,} $m\,$ , lahko obnovi prvotna različna praštevilska števila, če za ti dve kongruenci uporabi kitajski stavek o preostanku, dobi

m e d ≡ m mod p q {\displaystyle m^{ed}\equiv m{\bmod {pq}}} $m^{ed}\equiv m{\bmod {pq}}$ .

Tako,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} $c^{d}\equiv m{\bmod {n}}$ .

Delovni primer

Tukaj je primer šifriranja in dešifriranja RSA. Tu uporabljeni parametri so umetno majhni, vendar lahko s programom OpenSSL ustvarite in preverite pravi par ključev.

Izberite dve naključni praštevili.
: p = 61 {\displaystyle p=61} $p=61$ in q = 53 ; {\displaystyle q=53;} $q=53;$ Izračunajte n = p q {\displaystyle n=pq\,} $n=pq\,$
: n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233} $n=61*53=3233$
Izračunajte totient ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,} $\phi (n)=(p-1)(q-1)\,$
: ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120} $\phi (n)=(61-1)(53-1)=3120$
Izberite e > 1 {\displaystyle e>1} $e>1$ koprime 3120
: e = 17 {\displaystyle e=17} $e=17$
Izberite d {\displaystyle d\,} $d\,$ , da bo d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,} $de{\bmod {\phi (n)}}\equiv 1\,$
: d = 2753 {\displaystyle d=2753} $d=2753$
: 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} $17*2753=46801=1+15*3120$ .

Javni ključ je ( n = 3233 {\displaystyle n=3233} $n=3233$ , e = 17 {\displaystyle e=17} $e=17$ ). Za podtaknjeno sporočilo m {\displaystyle m\,} $m\,$ šifrirna funkcija c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} $c=m^{e}{\bmod {n}}$ postane:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{\bmod {3}}233\,} $c=m^{17}{\bmod {3}}233\,$

Zasebni ključ je ( n = 3233 {\displaystyle n=3233} $n=3233$ , d = 2753 {\displaystyle d=2753} $d=2753$ ). Dešifrirna funkcija m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} $m=c^{d}{\bmod {n}}$ postane:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233\,} $m=c^{2753}{\bmod {3}}233\,$

Na primer, za šifriranje m = 123 {\displaystyle m=123} $m=123$ izračunamo

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{\bmod {3}}233=855} $c=123^{17}{\bmod {3}}233=855$

Za dešifriranje c = 855 {\displaystyle c=855} $c=855$ izračunamo

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}}233=123} $m=855^{2753}{\bmod {3}}233=123$

Oba izračuna je mogoče učinkovito izračunati z algoritmom square-and-multiply za modularno eksponentno računanje [sl].

Izpeljava enačbe RSA iz Eulerjevega izreka

RSA je mogoče preprosto izpeljati z uporabo Eulerjevega izreka in Eulerjeve funkcije totient.

Začnimo z Eulerjevim izrekom,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}} $m^{\phi (n)}\equiv 1{\pmod {n}}$

pokazati moramo, da z dešifriranjem šifriranega sporočila s pravilnim ključem dobimo izvirno sporočilo. Če je podano šifrirano sporočilo m, se šifrirano besedilo c izračuna z

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{\pmod {n}}} $c\equiv m^{e}{\pmod {n}}$

Z zamenjavo v algoritmu za dešifriranje dobimo

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}} $c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}$

Pokazati želimo, da je tudi ta vrednost kongruentna z m. Vrednosti e in d sta bili izbrani tako, da sta se ujemali,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}} $ed\equiv 1{\pmod {\phi (n)}}$

To pomeni, da obstaja neko celo število k, tako da

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1} $ed=k\times \phi (n)+1$

Zdaj v šifrirano in nato dešifrirano sporočilo vnesemo nadomestek,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}} ${\begin{aligned}m^{ed}&\equiv m^{k\phi (n)+1}\\&\equiv m\times m^{k\phi (n)}\\&\equiv m\times \left(m^{\phi (n)}\right)^{k}{\pmod {n}}\end{aligned}}$

Uporabimo Eulerjev izrek in dobimo rezultat.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}} $m\times (1)^{k}\equiv m{\pmod {n}}$

Sheme polnila

Pri praktični uporabi je treba sistem RSA kombinirati z neko obliko sheme oblazinjenja, tako da nobena vrednost M ne povzroči nezanesljivih šifrirnih besedil. RSA, ki se uporablja brez oblazinjenja, ima lahko nekaj težav:

Vrednosti m = 0 ali m = 1 zaradi lastnosti eksponentnosti vedno ustvarijo šifrirna besedila, ki so enaka 0 oziroma 1.
Pri šifriranju z majhnimi šifrirnimi eksponentami (npr. e = 3) in majhnimi vrednostmi m je lahko (nemodularni) rezultat m e {\displaystyle m^{e}} $m^{e}$ strogo manjši od modula n. V tem primeru je mogoče šifrirne tekste enostavno dešifrirati tako, da vzamemo etni koren šifrirnega teksta brez upoštevanja modula.
Šifriranje RSA je deterministični algoritem za šifriranje. Nima naključne komponente. Zato lahko napadalec uspešno izvede napad z izbranim navadnim besedilom na kriptosistem. Slovar lahko izdela tako, da pod javnim ključem šifrira verjetne odprte tekste in shranjuje dobljene šifrirne tekste. Napadalec lahko nato opazuje komunikacijski kanal. Takoj ko opazi šifrirne tekste, ki se ujemajo s tistimi v njegovem slovarju, lahko napadalec uporabi ta slovar, da izve vsebino sporočila.

V praksi se prvi dve težavi lahko pojavita pri pošiljanju kratkih sporočil ASCII. V takih sporočilih je lahko m sestavljen iz enega ali več znakov, kodiranih v ASCII. Sporočilo, sestavljeno iz enega samega znaka ASCII NUL (katerega številčna vrednost je 0), bi bilo kodirano kot m = 0, kar bi povzročilo šifrirano besedilo 0, ne glede na to, katere vrednosti e in N se uporabijo. Podobno bi en sam znak ASCII SOH (katerega številčna vrednost je 1) vedno ustvaril šifrirano besedilo 1. Za sisteme, ki običajno uporabljajo majhne vrednosti e, kot je 3, bi bila vsa sporočila z enim znakom ASCII, kodirana s to shemo, nezanesljiva, saj bi imel največji m vrednost 255, 255³ pa je manj kot kateri koli razumni modul. Takšna odprta besedila bi lahko obnovili tako, da bi preprosto vzeli kubični koren iz šifriranega besedila.

Da bi se izognili tem težavam, praktične implementacije RSA v vrednost m pred šifriranjem običajno vgradijo neko obliko strukturiranega, naključno izbranega polnila. To polnilo zagotavlja, da m ne spada v območje nezanesljivih navadnih besedil in da bo določeno sporočilo, ko bo enkrat polnjeno, šifrirano v eno od velikega števila različnih možnih šifrirnih besedil. Slednja lastnost lahko poveča stroške slovarskega napada nad zmožnosti razumnega napadalca.

Standardi, kot je PKCS, so bili skrbno zasnovani tako, da so pred šifriranjem RSA varno obložili sporočila. Ker te sheme podlagajo odprto besedilo m z določenim številom dodatnih bitov, mora biti velikost nepodloženega sporočila M nekoliko manjša. Sheme za polnjenje RSA morajo biti skrbno načrtovane, da se preprečijo prefinjeni napadi. To lahko olajša predvidljiva struktura sporočila. Zgodnje različice standarda PKCS so uporabljale ad-hoc konstrukcije, za katere se je pozneje izkazalo, da so ranljive za praktični prilagodljivi napad z izbranim šifrirnim besedilom. Sodobne konstrukcije uporabljajo varne tehnike, kot je optimalno asimetrično šifriranje (Optimal Asymmetric Encryption Padding - OAEP), ki ščitijo sporočila in hkrati preprečujejo te napade. Standard PKCS vsebuje tudi sheme obdelave, ki so zasnovane za zagotavljanje dodatne varnosti za podpise RSA, npr. verjetnostno podpisno shemo za RSA (RSA-PSS).

Podpisovanje sporočil

Predpostavimo, da Alica uporabi Bobov javni ključ in mu pošlje šifrirano sporočilo. V sporočilu lahko trdi, da je Alica, vendar Bob ne more preveriti, ali je sporočilo dejansko poslala Alica, saj lahko vsakdo uporabi Bobov javni ključ za pošiljanje šifriranih sporočil. Da bi preverili izvor sporočila, lahko torej RSA uporabimo tudi za podpis sporočila.

Predpostavimo, da želi Alica poslati podpisano sporočilo Bobu. Izdela vrednost hash sporočila, jo poviša na moč d mod n (tako kot pri dešifriranju sporočila) in jo kot "podpis" priloži sporočilu. Ko Bob prejme podpisano sporočilo, dvigne podpis na moč e mod n (tako kot pri šifriranju sporočila) in primerja dobljeno vrednost hash z dejansko vrednostjo hash sporočila. Če se vrednosti ujemata, Bob ve, da je imel avtor sporočila v posesti Alicin skrivni ključ in da sporočilo od takrat ni bilo spremenjeno.

Upoštevajte, da so sheme varnega polnjenja, kot je RSA-PSS, enako pomembne za varnost podpisovanja sporočil kot za njihovo šifriranje in da se isti ključ nikoli ne sme uporabljati za šifriranje in podpisovanje.

Vprašanja in odgovori

V: Kaj je RSA?

O: RSA (Rivest-Shamir-Adleman) je algoritem, ki ga sodobni računalniki uporabljajo za šifriranje in dešifriranje sporočil. Je asimetrični kriptografski algoritem.

V: Kaj pomeni asimetrični?

O: Asimetrični pomeni, da obstajata dva različna ključa - javni in zasebni ključ.

V: Na čem temelji algoritem RSA?

O: Algoritem temelji na dejstvu, da je iskanje faktorjev velikega sestavljenega števila težavno - če so faktorji praštevila, se ta problem imenuje prafaktorizacija.

V: Kako deluje algoritem RSA?

O: RSA vključuje javni in zasebni ključ. Javni ključ lahko pozna vsakdo - uporablja se za šifriranje sporočil. Sporočila, šifrirana z javnim ključem, je mogoče dešifrirati le z zasebnim ključem, ki ga je treba ohraniti v tajnosti. Izračunati zasebni ključ iz javnega ključa je zelo težko.

V: Ali za to vrsto kriptografije obstaja še kakšno drugo ime?

O: Ta vrsta kriptografije se imenuje tudi kriptografija z javnim ključem, ker je enega od ključev mogoče dati komur koli, medtem ko drugi ključ ostane zasebni.

V: Ali RSA ustvari par ključev?

O: Da, RSA ustvari par ključev - javni in zasebni ključ - ki se uporabljata za šifriranje oziroma dešifriranje.

Iskati