RSA algoritmas

Pranešimo šifravimas

Alisa perduoda savo viešąjį raktą ( n {\displaystyle n\,} & e {\displaystyle e\,} ) Bobui, o savo privatųjį raktą laiko paslaptyje. Bobas nori išsiųsti žinutę M Alisai.

Pirmiausia jis paverčia M skaičiumi m {\displaystyle m} mažesniu už n {\displaystyle n} , naudodamas sutartą grįžtamąjį protokolą, vadinamą užpildymo schema. Tada jis apskaičiuoja šifro tekstą c {\displaystyle c\,} , atitinkantį:

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

Tai galima padaryti greitai, taikant eksponentavimo kvadratu metodą. Tada Bobas siunčia c {\displaystyle c\,} Alisai.

Pranešimo iššifravimas

Alisa gali atkurti m {\displaystyle m\,} iš c {\displaystyle c\,} naudodama savo privatų raktą d {\displaystyle d\,} toliau nurodyta tvarka:

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

Turėdama m {\displaystyle m\,} , ji gali atgauti pradinius skirtingus pirminius skaičius, o pritaikiusi kinų liekanų teoremą šioms dviem kongruencijoms gausime

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

Taigi,

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

Praktinis pavyzdys

Pateikiame RSA šifravimo ir dešifravimo pavyzdį. Čia naudojami dirbtinai maži parametrai, bet taip pat galite naudoti OpenSSL, kad sugeneruotumėte ir patikrintumėte tikrą raktų porą.

1. Pasirinkite du atsitiktinius pirminius skaičius.
2.  : p = 61 {\displaystyle p=61} ir q = 53 ; {\displaystyle q=53;} Apskaičiuokite n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}
4. Apskaičiuokite totientą ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)\,}
5.  : ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120}
6. Pasirinkite e > 1 {\displaystyle e>1} koprima 3120
7.  : e = 17 {\displaystyle e=17}
8. Pasirinkite d {\displaystyle d\,} , kad d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}}\equiv 1\,}
9.  : d = 2753 {\displaystyle d=2753}
10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

Viešasis raktas yra ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Šifravimo funkcija c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} tampa šifravimo funkcija m {\displaystyle m\,} :

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

Privatusis raktas yra ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Dešifravimo funkcija m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} tampa:

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

Pavyzdžiui, norėdami užšifruoti m = 123 {\displaystyle m=123} apskaičiuojame

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

Iššifruoti c = 855 {\displaystyle c=855} apskaičiuojame

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

Abu šie skaičiavimai gali būti efektyviai apskaičiuoti naudojant kvadrato ir daugybos algoritmą moduliniam eksponentizavimui [lt].

RSA lygties išvedimas iš Eulerio teoremos

RSA galima lengvai išvesti naudojant Eulerio teoremą ir Eulerio totiento funkciją.

Pradėkime nuo Eulerio teoremos,

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

turime įrodyti, kad iššifravus užšifruotą pranešimą, naudojant tinkamą raktą, bus gautas originalus pranešimas. Turint užšifruotą pranešimą m, šifro tekstas c apskaičiuojamas taip

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

Įterpdami į dešifravimo algoritmą, turime

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

Norime parodyti, kad ši reikšmė taip pat sutampa su m. E ir d reikšmės buvo pasirinktos taip, kad būtų sotios,

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

Vadinasi, egzistuoja tam tikras sveikasis skaičius k, kad

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

Dabar mes pakeičiame užšifruotą ir iššifruotą pranešimą,

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

Taikome Eulerio teoremą ir gauname rezultatą.

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

Užpildymo schemos

Naudojant RSA praktikoje, ji turi būti derinama su tam tikra užpildymo schema, kad nė viena M reikšmė nesukeltų nesaugių šifrogramų. Kai kurios problemos gali kilti naudojant RSA be užpildų:

• Dėl eksponentiškumo savybių, kai m = 0 arba m = 1, šifro tekstai visada yra lygūs atitinkamai 0 arba 1.
• Kai šifruojama naudojant mažus šifravimo eksponentus (pvz., e = 3) ir mažas m reikšmes, (nemodulinis) rezultatas m e {\displaystyle m^{e}} gali būti griežtai mažesnis už modulį n. Tokiu atveju šifravimo tekstai gali būti lengvai iššifruojami imant šifravimo teksto et šaknį, neatsižvelgiant į modulį.
• RSA šifravimas yra deterministinis šifravimo algoritmas. Jame nėra atsitiktinio komponento. Todėl užpuolikas gali sėkmingai surengti pasirinkto grynojo teksto ataką prieš kriptosistemą. Jie gali sudaryti žodyną užšifruodami tikėtinus atvirus tekstus pagal viešąjį raktą ir saugodami gautus šifrografinius tekstus. Tada užpuolikas gali stebėti ryšio kanalą. Kai tik jie pamato šifruotus tekstus, atitinkančius jų žodyne esančius tekstus, užpuolikai gali pasinaudoti šiuo žodynu, kad sužinotų pranešimo turinį.

Praktikoje pirmosios dvi problemos gali kilti siunčiant trumpus ASCII pranešimus. Tokiuose pranešimuose m gali būti vieno ar daugiau ASCII koduotų simbolių junginys. Pranešimas, kurį sudaro vienas ASCII NUL simbolis (kurio skaitinė vertė yra 0), būtų užkoduotas kaip m = 0, todėl šifro tekstas būtų 0, nesvarbu, kokios e ir N vertės būtų naudojamos. Panašiai, naudojant vieną ASCII SOH (kurio skaitinė vertė yra 1), šifro tekstas visada būtų 1. Sistemose, kuriose įprastai naudojamos mažos e reikšmės, pavyzdžiui, 3, visi pagal šią schemą užkoduoti vieno ASCII simbolio pranešimai būtų nesaugūs, nes didžiausia m reikšmė būtų 255, o 255³ yra mažesnė už bet kokį priimtiną modulį. Tokius atvirus tekstus būtų galima atkurti paprasčiausiai išvedus šifro teksto kubinę šaknį.

Kad būtų išvengta šių problemų, praktinės RSA realizacijos paprastai prieš užšifruojant vertę m į ją įterpia tam tikrą struktūrizuotą, atsitiktinai parinktą užpildą. Šis užpildas užtikrina, kad m nepateks į nesaugių paprastųjų tekstų intervalą ir kad tam tikras pranešimas po užpildymo bus užšifruotas į vieną iš daugelio galimų šifro tekstų. Pastaroji savybė gali padidinti žodyno atakos sąnaudas, viršijančias protingo užpuoliko galimybes.

Tokie standartai, kaip PKCS, buvo kruopščiai sukurti taip, kad prieš RSA šifravimą pranešimai būtų saugiai užpildomi. Kadangi šiose schemose atvirasis tekstas m užpildomas tam tikru papildomų bitų skaičiumi, neužpildyto pranešimo M dydis turi būti šiek tiek mažesnis. RSA užpildymo schemos turi būti kruopščiai suprojektuotos, kad būtų išvengta sudėtingų atakų. Tai padaryti gali būti lengviau, jei pranešimo struktūra yra nuspėjama. Ankstyvosios PKCS standarto versijos naudojo ad-hoc konstrukcijas, kurios, kaip vėliau paaiškėjo, buvo pažeidžiamos praktiškai pritaikomos pasirinkto šifro teksto atakos. Šiuolaikinėse konstrukcijose naudojami saugūs metodai, pavyzdžiui, optimalus asimetrinis šifravimo užpildymas (angl. Optimal Asymmetric Encryption Padding, OAEP), siekiant apsaugoti pranešimus ir kartu išvengti šių atakų. PKCS standarte taip pat yra apdorojimo schemų, sukurtų siekiant užtikrinti papildomą RSA parašų saugumą, pavyzdžiui, RSA tikimybinė parašo schema (RSA-PSS).

Pranešimų pasirašymas

Tarkime, kad Alisa, naudodama Bobo viešąjį raktą, siunčia jam užšifruotą pranešimą. Žinutėje ji gali teigti, kad yra Alisa, tačiau Bobas neturi galimybės patikrinti, ar žinutė iš tikrųjų atėjo iš Alisos, nes bet kas gali pasinaudoti Bobo viešuoju raktu ir siųsti jam užšifruotas žinutes. Taigi, norint patikrinti pranešimo kilmę, RSA taip pat galima naudoti pranešimui pasirašyti.

Tarkime, kad Alisa nori nusiųsti pasirašytą pranešimą Bobui. Ji sukuria pranešimo hash reikšmę, padidina ją iki d mod n galios (kaip ir dešifruodama pranešimą) ir prideda ją prie pranešimo kaip "parašą". Gavęs pasirašytą pranešimą, Bobas pakelia parašą iki e mod n galios (kaip ir užšifruodamas pranešimą) ir palygina gautą hash vertę su tikrąja pranešimo hash verte. Jei jos sutampa, Bobas žino, kad pranešimo autorius turėjo slaptąjį Alisos raktą ir kad pranešimas nuo to laiko nebuvo suklastotas.

Atkreipkite dėmesį, kad saugios užpildymo schemos, tokios kaip RSA-PSS, yra tokios pat svarbios pranešimų pasirašymo saugumui, kaip ir šifravimo saugumui, ir kad tas pats raktas niekada neturėtų būti naudojamas ir šifravimo, ir pasirašymo tikslais.