Kas ir RSA algoritms — publiskās atslēgas šifrēšanas princips

RSA (Rivest-Shamir-Adleman) ir algoritms, ko mūsdienu datori izmanto ziņojumu šifrēšanai un atšifrēšanai. Tas ir asimetrisks kriptogrāfijas algoritms. Asimetrisks nozīmē, ka ir divas dažādas atslēgas. To sauc arī par publiskās atslēgas kriptogrāfiju, jo vienu no atslēgām var nodot jebkurai personai. Otra atslēga ir jāglabā privāta. Algoritma pamatā ir fakts, ka atrast liela salikta skaitļa faktorus ir sarežģīti: ja faktori ir pirmskaitļi, šo problēmu sauc par pirmfaktorializāciju. Tas ir arī atslēgu pāra (publiskās un privātās atslēgas) ģenerators.

Kā RSA darbojas — galvenie soļi

Atslēgu ģenerēšana:
- Izvēlas divus lielus nejaušus pirmskaitļus p un q.
- Aprēķina n = p × q — modulis, ko izmanto gan publiskajā, gan privātajā atslēgā.
- Aprēķina φ(n) = (p − 1)(q − 1) (Eilera totienta funkcija).
- Izvēlas publisko eksponentu e tā, lai 1 < e < φ(n) un gcd(e, φ(n)) = 1 (bieži izmantoti e = 65537 vai e = 3/17 historiski).
- Aprēķina privāto eksponentu d kā e multiplikatīvo inversu mod φ(n): d × e ≡ 1 (mod φ(n)).
- Publiskā atslēga: (n, e). Privātā atslēga: (n, d) (vai (p, q, d, u) CRT formātā).
Šifrēšana: ja sūtītājs vēlas nosūtīt ziņojumu m (kurš tiek kodēts kā skaitlis mazāks par n),
šifrtekst c = m^e mod n.
Atšifrēšana: saņēmējs izmanto d, lai atjaunotu m:
m = c^d mod n.

Neliels piemērs (ilustrācijai)

Šis piemērs izmanto mazas vērtības tikai izpratnei (nekad nelietot šīs vērtības reālai drošībai): p = 61, q = 53 → n = 3233; φ(n) = 3120. Izvēlas e = 17, tad d = 2753. Ja m = 65, tad c = 65^17 mod 3233 = 2790; atšifrējot c^d mod 3233 atgriežas m = 65.

Drošība un ierobežojumi

RSA drošība balstās uz to, ka nozināma n = p×q faktorizācija ir grūta, ja p un q ir pietiekami lieli.
Mūsdienās ieteicamie atslēgu garumi ir vismaz 2048 bitu (dažkārt 3072 vai 4096 bitu atkarībā no nepieciešamās ilgtermiņa drošības).
Bez pareiza pakojuma (padding) RSA ir pakļauts dažādām uzbrukumu formām (piem., izvēlētā tekstā balstīti uzbrukumi). Tādēļ praktiskā lietošanā izmanto standarta pakošanas shēmas, piemēram, OAEP šifrēšanai un PKCS#1 v2.1 signatūrām.
Ar kvantu datoriem (ja praktiski darbināmi kvantu datori tiks izveidoti) RSA var tikt ātri salauzts, izmantojot Shor algoritmu. Tas nozīmē, ka ilgtermiņa datu aizsardzībai jāplāno pāreja uz post‑kvantu kriptogrāfiju.
Praktiskie uzbrukumi var ietvert arī puses kanālu uzbrukumus (side‑channel), slikti ģenerētas nejaušības, atkārtoti izmantotas vai pārāk mazas atslēgas, kā arī ļaunprātīgu pakojuma izmantošanu.

Lietojumi un labākā prakse

RSA plaši izmanto: TLS/HTTPS savienojumu autentifikācijai un atslēgu apmaiņai, digitālām parakstiem (piem., e‑paraksti), drošai e‑pasta apmaiņai (S/MIME) un sertifikātu sistēmās (X.509).
RSA ir lēnāks nekā simetriskie algoritmi; praksē bieži izmanto hibrīdu pieeju — RSA šifrē tikai simetriskās atslēgas (piem., AES), bet pašu datu šifrē ar ātrāku simetrisko algoritmu.
Izmantojiet pārbaudītas kriptogrāfijas bibliotēkas (OpenSSL, libsodium, BouncyCastle u.c.) un atjauniniet tās. Neizdomājiet savu realizāciju.
Izmantojiet drošus nejaušības avotus pirmskaitļu ģenerēšanai un pārbaudiet pirmskaitļu primaritāti ar uzticamiem testiem (piem., Miller‑Rabin).
Privātā atslēga jāglabā droši — šifrēta ar spēcīgu paroli, glabāta aparatūras drošības moduļos (HSM) vai drošos atslēgu krātuvēs. Ierobežojiet piekļuvi un regulāri mainiet/atsauciet atslēgas, ja nepieciešams.

Kopā — kad izmantot RSA

RSA ir robusts un pārbaudīts rīks publiskās atslēgas kriptogrāfijā, piemērots atslēgu apmaiņai, parakstiem un autentifikācijai, ja tiek ievērotas mūsdienīgas drošības prasības: pietiekami garas atslēgas, pareizi pakojumi (OAEP, PSS), droša atslēgu ģenerēšana un aizsardzība pret puses kanālu uzbrukumiem. Lai nodrošinātu drošību ilgtermiņā, jāseko attīstībai kvantu kriptogrāfijā un jāplāno pāreja uz post‑kvantu algoritmiem, kad tas būs nepieciešams.

Ziņojuma šifrēšana

Alise nodod savu publisko atslēgu ( n {\displaystyle n\,} $n\,$ & e {\displaystyle e\,} $e\,$ ) Bobam un patur savu privāto atslēgu noslēpumā. Bobs vēlas nosūtīt ziņu M Alisei.

Vispirms viņš pārvērš M par skaitli m {\displaystyle m} , kas ir mazāks par n {\displaystyle n} , izmantojot saskaņotu atgriezenisku protokolu, kas pazīstams kā pildījuma shēma. Tad viņš aprēķina šifrtekstu c {\displaystyle c\,} $c\,$ , kas atbilst:

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

To var izdarīt ātri, izmantojot eksponentizācijas metodi ar kvadrātu. Pēc tam Bobs nosūta c {\displaystyle c\,} $c\,$ Alisei.

Ziņojuma atšifrēšana

Alise var atgūt m {\displaystyle m\,} $m\,$ no c {\displaystyle c\,} $c\,$ , izmantojot savu privāto atslēgu d {\displaystyle d\,} $d\,$ , izmantojot šādu procedūru:

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

Ņemot vērā m {\displaystyle m\,} $m\,$ , viņa var atgūt sākotnējos atšķirīgos pirmskaitļus, un, piemērojot ķīniešu atlikušo skaitļu teorēmu šīm divām sakritībām, iegūst.

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

Tādējādi,

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

Darba piemērs

Šeit ir RSA šifrēšanas un atšifrēšanas piemērs. Šeit izmantotie parametri ir mākslīgi mazi, bet jūs varat izmantot arī OpenSSL, lai ģenerētu un pārbaudītu īstu atslēgu pāri.

Izvēlieties divus nejaušus pirmskaitļus.
: p = 61 {\displaystyle p=61} $p=61$ un q = 53 ; {\displaystyle q=53;} $q=53;$ Aprēķiniet n = p q {\displaystyle n=pq\,} $n=pq\,$
: n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233} $n=61*53=3233$
Aprēķina totientu ϕ ( 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$
Izvēlieties e > 1 {\displaystyle e>1} $e>1$ koprimē 3120
: e = 17 {\displaystyle e=17} $e=17$
Izvēlieties d {\displaystyle d\,} $d\,$ , lai apmierinātu 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$ .

Publiskā atslēga ir ( n = 3233 {\displaystyle n=3233} $n=3233$ , e = 17 {\displaystyle e=17} $e=17$ ). Šifrēšanas funkcija c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} $c=m^{e}{\bmod {n}}$ kļūst par šifrēšanas funkciju m {\displaystyle m\,} $m\,$ :

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

Privātā atslēga ir ( n = 3233 {\displaystyle n=3233} $n=3233$ , d = 2753 {\displaystyle d=2753} $d=2753$ ). Dešifrēšanas funkcija m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} $m=c^{d}{\bmod {n}}$ kļūst:

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

Piemēram, lai šifrētu m = 123 {\displaystyle m=123} $m=123$ , mēs aprēķinām

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

Lai atšifrētu c = 855 {\displaystyle c=855} $c=855$ , mēs aprēķinām

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

Abus šos aprēķinus var efektīvi aprēķināt, izmantojot modulārās eksponentizācijas algoritmu "kvadrāts un reizinājums" [lv].

RSA vienādojuma atvasināšana no Ēlera teorēmas

RSA var viegli iegūt, izmantojot Ēlera teorēmu un Ēlera totienta funkciju.

Sākot ar Ēlera teorēmu,

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

mums ir jāparāda, ka šifrēta ziņojuma atšifrēšana ar pareizo atslēgu ļaus iegūt sākotnējo ziņojumu. Ņemot vērā, ka ziņojums m ir aizpildīts, šifrtekstu c aprēķina šādi.

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

Ievietojot atšifrēšanas algoritmā, iegūstam šādu rezultātu

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}}$

Mēs vēlamies parādīt, ka arī šī vērtība ir kongruenta ar m. Vērtības e un d tika izvēlētas tā, lai apmierinātu,

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

Tas nozīmē, ka eksistē kāds vesels skaitlis k, lai

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

Tagad mēs aizstājam šifrēto un pēc tam atšifrēto ziņojumu,

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^{k\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}}$

Piemērojam Ēlera teorēmu un iegūstam rezultātu.

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

Papildināšanas shēmas

Lietojot RSA praksē, RSA ir jāapvieno ar kāda veida polsterēšanas shēmu, lai neviena M vērtība neradītu nedrošus šifrtekstus. RSA, ko izmanto bez polsterējuma, var radīt zināmas problēmas:

Vērtības m = 0 vai m = 1 vienmēr rada šifrtekstus, kas ir attiecīgi 0 vai 1, pateicoties eksponenciācijas īpašībām.
Šifrējot ar maziem šifrēšanas eksponentiem (piemēram, e = 3) un mazām m vērtībām, (nemodulārais) rezultāts m e {\displaystyle m^{e}}} $m^{e}$ var būt stingri mazāks par moduli n. Šādā gadījumā šifrētus tekstus var viegli atšifrēt, ņemot šifrētā teksta eta sakni, neņemot vērā moduli.
RSA šifrēšana ir deterministisks šifrēšanas algoritms. Tam nav nejaušības komponenta. Tāpēc uzbrucējs var sekmīgi veikt izvēlētā atklātā teksta uzbrukumu kriptosistēmai. Viņi var izveidot vārdnīcu, šifrējot iespējamus atklātos tekstus ar publisko atslēgu un saglabājot iegūtos šifrtekstus. Pēc tam uzbrucējs var novērot saziņas kanālu. Tiklīdz uzbrucējs redz šifrtekstus, kas atbilst viņa vārdnīcā iekļautajiem, viņš var izmantot šo vārdnīcu, lai uzzinātu ziņojuma saturu.

Praksē pirmās divas problēmas var rasties, ja tiek sūtīti īsi ASCII ziņojumi. Šādos ziņojumos m var būt viena vai vairāku ASCII kodētu rakstzīmju sakopojums. Ziņojums, kas sastāv no vienas ASCII NUL zīmes (kuras skaitliskā vērtība ir 0), tiktu kodēts kā m = 0, kas rada šifrtekstu 0 neatkarīgi no tā, kādas e un N vērtības tiktu izmantotas. Līdzīgi arī viens ASCII SOH (kura skaitliskā vērtība ir 1) vienmēr dotu šifrtekstu 1. Sistēmās, kurās parasti izmanto mazas e vērtības, piemēram, 3, visi ASCII ziņojumi, kas kodēti, izmantojot šo shēmu, būtu nedroši, jo lielākā m vērtība būtu 255, un 255³ ir mazāk nekā jebkurš saprātīgs modulis. Šādus atklātos tekstus varētu atgūt, vienkārši iegūstot ciperteksta kubisko sakni.

Lai izvairītos no šīm problēmām, praktiskās RSA implementācijās pirms vērtības m šifrēšanas tajā parasti iestrādā kādu strukturētu, randomizētu pildījumu. Šis polsterējums nodrošina, ka m neietilpst nedrošu atklātās teksta vērtības diapazonā un ka konkrētais ziņojums pēc polsterējuma tiks šifrēts ar vienu no daudziem iespējamiem šifrtekstiem. Pēdējā īpašība var palielināt vārdnīcas uzbrukuma izmaksas, pārsniedzot saprātīga uzbrucēja iespējas.

Tādi standarti kā PKCS ir rūpīgi izstrādāti, lai droši aizsargātu ziņojumus pirms RSA šifrēšanas. Tā kā šajās shēmās atklātajam tekstam m ir noteikts skaits papildu bitu, tad nepapildinātā ziņojuma M izmēram jābūt nedaudz mazākam. RSA polsterēšanas shēmām jābūt rūpīgi izstrādātām, lai novērstu sarežģītus uzbrukumus. To var atvieglot paredzama ziņojuma struktūra. PKCS standarta agrīnajās versijās tika izmantotas ad hoc konstrukcijas, kuras vēlāk tika atzītas par neaizsargātām pret praktisku adaptīvu izvēlētā šifrteksta uzbrukumu. Mūsdienu konstrukcijās tiek izmantotas drošas metodes, piemēram, optimālā asimetriskā šifrēšanas papildināšana (OAEP), lai aizsargātu ziņojumus, vienlaikus novēršot šos uzbrukumus. PKCS standartā ir arī apstrādes shēmas, kas izstrādātas, lai nodrošinātu papildu drošību RSA parakstiem, piemēram, RSA varbūtiskā paraksta shēma (RSA-PSS).

Ziņojumu parakstīšana

Pieņemsim, ka Alise izmanto Boba publisko atslēgu, lai nosūtītu viņam šifrētu ziņojumu. Ziņojumā viņa var apgalvot, ka ir Alise, bet Bobam nav iespējams pārbaudīt, vai ziņojums patiešām ir no Alises, jo jebkurš var izmantot Boba publisko atslēgu, lai nosūtītu viņam šifrētu ziņojumu. Tātad, lai pārbaudītu ziņojuma izcelsmi, RSA var izmantot arī ziņojuma parakstīšanai.

Pieņemsim, ka Alise vēlas nosūtīt parakstītu ziņojumu Bobam. Viņa izveido ziņojuma hash vērtību, palielina to līdz d mod n varai (tāpat kā atšifrējot ziņojumu) un pievieno to kā "parakstu" ziņojumam. Kad Bobs saņem parakstīto ziņojumu, viņš parakstu palielina līdz e mod n (tāpat kā šifrējot ziņojumu) un salīdzina iegūto hash vērtību ar ziņojuma faktisko hash vērtību. Ja abas vērtības sakrīt, viņš zina, ka ziņojuma autora rīcībā ir Alises slepenā atslēga un ka ziņojums kopš tā laika nav ticis falsificēts.

Ņemiet vērā, ka drošas pildīšanas shēmas, piemēram, RSA-PSS, ir tikpat svarīgas ziņojumu parakstīšanas drošībai kā ziņojumu šifrēšanai un ka vienu un to pašu atslēgu nekad nedrīkst izmantot gan šifrēšanai, gan parakstīšanai.

Jautājumi un atbildes

J: Kas ir RSA?

A: RSA (Rivest-Shamir-Adleman) ir algoritms, ko mūsdienu datori izmanto ziņojumu šifrēšanai un atšifrēšanai. Tas ir asimetrisks kriptogrāfijas algoritms.

J: Ko nozīmē asimetrisks?

A: Asimetriskais nozīmē, ka ir divas dažādas atslēgas - publiskā atslēga un privātā atslēga.

J: Kas ir RSA algoritma pamatā?

A: Algoritma pamatā ir fakts, ka atrast liela salikta skaitļa faktorus ir grūti - ja faktori ir pirmie skaitļi, šo problēmu sauc par pirmreizējo faktorizāciju.

J: Kā darbojas RSA?

A.: RSA algoritmā ir publiskā atslēga un privātā atslēga. Publisko atslēgu var zināt ikviens - to izmanto ziņojumu šifrēšanai. Ziņojumus, kas šifrēti, izmantojot publisko atslēgu, var atšifrēt tikai ar privāto atslēgu, kas ir jāglabā slepenībā. Privātās atslēgas aprēķināšana no publiskās atslēgas ir ļoti sarežģīta.

Vai ir vēl kāds cits nosaukums šim kriptogrāfijas veidam?

A: Šo kriptogrāfijas veidu sauc arī par publiskās atslēgas kriptogrāfiju, jo vienu no atslēgām var nodot jebkurai personai, bet otru atslēgu var saglabāt privātu.

J: Vai RSA ģenerē atslēgu pāri?

A: Jā, RSA ģenerē atslēgu pāri - publisko un privāto atslēgu -, ko izmanto attiecīgi šifrēšanai un atšifrēšanai.