RSA šifrēšanas algoritms

Šis raksts ir par algoritmu. Par citām jēdziena RSA nozīmēm skatīt nozīmju atdalīšanas lapu.

RSA šifrēšanas algoritms ir mūsdienās visplašāk lietotais asimetriskās šifrēšanas algoritms. Tas pirmo reizi tika aprakstīts 1977. gadā un ir vēsturiski pirmais plaši lietotais asimetriskās šifrēšanas algoritms.

Nosaukums RSA ir veidots no tā izgudrotāju uzvārdu pirmajiem burtiem (Rivest, Shamir, Adleman).

RSA algoritmā tiek lietotas divas atslēgas: privātā atslēga un publiskā atslēga. Datus, kas nošifrēti ar vienu atslēgu, atšifrēt var tikai ar otru. Abas atslēgas ir savā starpā saistītas, bet no vienas aprēķināt otru ir gandrīz neiespējami (šī darbība ir atslēgas atlaušana). Privāto atslēgu tur slepenībā. Publisko atslēgu izplata visiem, kam var būt nepieciešamība nosūtīt šifrētus datus privātās atslēgas turētājam.

• Variantu, kur datus šifrē ar publisko atslēgu (un var atšifrēt ar privāto), lieto datu šifrēšanai.
• Variantu, kur datus šifrē ar privāto atslēgu (un var atšifrēt ar publisko), lieto elektroniskajam parakstam.

Asimetriskie algoritmi (kā RSA) ir ievērojami lēnāki kā simetriskie (kā AES), tāpēc, ja ir jānošifrē liels daudzums datu, ar RSA šifrē tikai simetrisko atslēgu, un pašus datus šifrē ar simetrisko šifrēšanu. Asimetriskajiem algoritmiem, lai sasniegtu tādu pašu drošības līmeni, ir nepieciešamas ievērojami garākas atslēgas (AES simetriskās šifrēšanas algoritmam kaut cik drošs atslēgas garums ir 128 biti, RSA vajag vismaz 1024.) RSA atslēgu drošība (tas, cik daudz laika nepieciešams tās atlaušanai (pie noteiktas skaitļošanas jaudas)), ir atkarīga no atslēgas garuma. Garākas atslēgas ir drošākas, bet visas darbības ar tām ir lēnākas. Pietiekoši garu atslēgu (4096 un vairāk) atlaušanai ar klasiskajiem datoriem vajadzētu miljardiem gadu, taču uzskata, ka tādas varētu atlauzt ievērojami īsākā laikā ar kvantu datoru. Pagaidām pietiekoši jaudīgi kvantu datori nav uzbūvēti. Līdz šim (2020. gada marts) garākā publiski zināmā atlauztā RSA atslēga ir 829 bitus gara un to atlauza 2020. gada 28. februārī. Tam tika patērēti 2700 procesora kodolu gadi (core-years).

Darbība

RSA algoritmam ir 3 funkcijas: atslēgu ģenerēšana, šifrēšana un atšifrēšana. Procesus, kur šifrē ar privāto atslēgu un atšifrē ar publisko atslēgu, parasti sauc par parakstīšanu un paraksta pārbaudi. Atslēgas ir saistītu skaitļu kopas.

Atslēgu ģenerēšana

RSA lieto 2 atslēgas: privāto atslēgu un publisko atslēgu. Tās ir saistītas savā starpā un tās ģenerē kā vienu pāri (keypair).

Atslēgu ģenerēšana:

1. Izvēlas 2 lielus pirmskaitļus: p un q
   • Vēlams lai tie būtu līdzīga lieluma. Parasti izmanto lielus gadījumskaitļus.
2. Aprēķina n=p*q
   • Skaitli n lieto par publiskās un privātās atslēgas moduli (tas lielais skaitlis, kas parasti apzīmē atslēgas garumu, piem., 1024 biti)
3. Aprēķina φ(n)=(p – 1)*(q – 1), kur φ ir Eilera funkcija
4. Izvēlas veselu skaitli e, kas atbilst kritērijiem 1<e<φ(n) un gcd(e,φ(n)), t.i., e un n ir savstarpēji pirmskaitļi.
   • e lieto par publiskās atslēgas eksponentu
   • e parasti ir mazs skaitlis, visbiežāk lieto 65537, dažreiz lieto 3. Ar mazākiem e šifrēšanas procesi notiek ātrāk, bet noteiktos apstākļos rezultāts var būt vieglāk atlaužams.
5. Aprēķina d = e^–1 mod φ(n) tas ir (e*d)mod φ(n)=1
   • Bieži vien d aprēķina ar citām metodēm.
   • d lieto par privātās atslēgas eksponentu.

Publiskā atslēga sastāv no n un e. Privātā atslēga satur d. Parasti privātās atslēgas satur visus datus (n, e, d) un no tādas privātās atslēgas var izveidot publisko atslēgu izmetot slepenos datus (d). Privātā atslēga bieži vien satur vairākus citus komponentus (skaitļus), kas nav nepieciešami šifrēšanai vai atšifrēšanai, bet kurus lietojot var izmantot efektīvākas šifrēšanas un atšifrēšanas metodes.

Šifrēšana

Šifrēšana ar publisko atslēgu. Šifrējamos datus var uztvert kā bitu virkni, kas arī ir skaitlis M. Parasti M ir mazāks par n. M pārveido par m, kur 0<m<n (tomēr saglabājot tuvu n). Šis process ir padding scheme. Vienkāršākajos gadījumos M pievieno galā random bitus, lai dabūtu tuvu n. Pēc tam šifrē:

c = m^e (mod n),

kur c ir nošifrētie dati. Skaitlis c ir mazāks par n un parasti apmēram tikpat liels (apmēram = pāris simtu reižu lielāks vai mazāks) kā m.

Atšifrēšana

Atšifrēšana ar privāto atslēgu. m no c var aprēķināt:

m = c^d (mod n),

m var pārveidot uz M, jo tas process ir atgriezenisks. (Ja sākumā skaitlim galā tika pielikti random biti, tad tagad tos vienkārši atmet.)

Parakstīšana

(Digitālais paraksts ar RSA) Šifrēšana ar privāto atslēgu. Šifrējamie (parakstāmie) dati te ir zināmi un nav slepeni. Parasti jebkuram lielam parakstāmo datu blokam (kam var būt liels un mainīgs lielums), aprēķina hash (kas ir relatīvi īss un konstantā garumā). To hash tad izmanto par M. M apstrādā ar padding scheme un iegūst m, kuru šifrē:

c=m^d (mod n)

c ir galā iegūtais digitālais paraksts.

Paraksta pārbaude

Atšifrēšana ar publisko atslēgu.

m = c^e (mod n)

To m pēc tam pārveido atpakaļ uz M un salīdzina ar no parakstītā datu bloka iegūto hash. (Digitālais paraksts neizmaina parakstāmos datus, tas tikai izveido atsevišķu datu bloku). Ja tie ir vienādi, tad ir zināms, ka tas ir tas pats datu bloks kas tika parakstīts.

Algoritma ievainojamības

• Ja šifrē ar atslēgu kurai ir mazs publiskais eksponents (e), piemēram, 3, un ir mazs m (m<n^1/e), iegūtais rezultāts m^e ir ievērojami mazāks par moduli n. Šajā gadījumā m var iegūt, izvelkot e-tās pakāpes sakni. Tāpēc vajag, lai m būtu līdzīga izmēra kā n.
• Ja vienu un to pašu datu bloku m šifrē ar dažādām atslēgām, kam ir vienāds e (bet dažādi p, q un n), var būt iespējams atšifrēt m, nezinot nevienu no privātajām atslēgām (d). Tāpēc, ja iespējams, nevajag vienu un to pašu informāciju šifrēt ar vairākām atslēgām. (Parasti, šifrējot ar publisko atslēgu, M ir simetriskā šifra atslēga, kas katrai šifrēšanas reizei tiek uzģenerēta no jauna)