RSA algoritms

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.

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.