Algoritem RSA

Šifriranje sporočila

Alica svoj javni ključ ( n {\displaystyle n\,} & e {\displaystyle 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\,} , ki ustreza:

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

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

Dešifriranje sporočila

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

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

Glede na m {\displaystyle 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}}} .

Tako,

c d ≡ m mod n {\displaystyle 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.

1. Izberite dve naključni praštevili.
2.  : p = 61 {\displaystyle p=61} in q = 53 ; {\displaystyle q=53;} Izračunajte n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}
4. Izračunajte 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. Izberite e > 1 {\displaystyle e>1} koprime 3120
7.  : e = 17 {\displaystyle e=17}
8. Izberite d {\displaystyle d\,} , da bo 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} .

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

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

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

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

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

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

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

m = 855 2753 mod 3 233 = 123 {\displaystyle 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}}}

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

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

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

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

e d = k × ϕ ( n ) + 1 {\displaystyle 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}}}

Uporabimo Eulerjev izrek in dobimo rezultat.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle 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}} 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.