RSA algoritm

Sõnumi krüpteerimine

Alice annab oma avaliku võtme ( n {\displaystyle n\,} & e {\displaystyle e\,} ) Bobile ja hoiab oma isikliku võtme salajas. Bob soovib saata Alice'ile sõnumi M.

Kõigepealt muudab ta M arvuks m {\displaystyle m} , mis on väiksem kui n {\displaystyle n} , kasutades selleks kokkulepitud pöörduvat protokolli, mida nimetatakse polsterdusskeemiks. Seejärel arvutab ta salakirja c {\displaystyle c\,} , mis vastab:

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

Seda saab kiiresti teha, kasutades ruutkeskmise meetodit. Seejärel saadab Bob Alice'ile c \displaystyle c\,} .

Sõnumi dekrüpteerimine

Alice saab m {\displaystyle m\,} taastada c {\displaystyle c\,} , kasutades oma isiklikku võtit d {\displaystyle d\,} järgmises menetluses:

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

Arvestades m {\displaystyle m\,} , saab ta taastada algsed erinevad algsed algarvud, kohaldades Hiina jäägite teoreemi nende kahe kongruentsuse suhtes, saadakse

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

Seega,

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

Töötav näide

Siin on näide RSA krüpteerimise ja dekrüpteerimise kohta. Siin kasutatud parameetrid on kunstlikult väikesed, kuid te võite kasutada OpenSSL-i ka tõelise võtmepaari genereerimiseks ja uurimiseks.

1. Valige kaks juhuslikku algarvu.
2.  : p = 61 {\displaystyle p=61} ja q = 53 ; {\displaystyle q=53;} Arvuta n = p q {\displaystyle n=pq\,}
3.  : n = 61 ∗ 53 = 3233 {\displaystyle n=61*53=3233}
4. Arvutatakse 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. Vali e > 1 {\displaystyle e>1} coprime to 3120
7.  : e = 17 {\displaystyle e=17}
8. Valige d {\displaystyle d\,} nii, et d e mod ϕ ( n ) ≡ 1 {\displaystyle de{\bmod {\phi (n)}\equiv 1\,} rahuldab.}
9.  : d = 2753 {\displaystyle d=2753}
10.  : 17 ∗ 2753 = 46801 = 1 + 15 ∗ 3120 {\displaystyle 17*2753=46801=1+15*3120} .

Avalik võti on ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Täidetud sõnumi m {\displaystyle m\,} puhul saab krüpteerimisfunktsioon c = m e mod n {\displaystyle c=m^{e}{\bmod {n}}} :

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

Privaatne võti on ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). Dekrüpteerimisfunktsioon m = c d mod n {\displaystyle m=c^{d}{\bmod {n}}} saab:

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

Näiteks, et krüpteerida m = 123 {\displaystyle m=123} arvutame

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

C = 855 {\displaystyle c=855} dekrüpteerimiseks. arvutame

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

Mõlemaid arvutusi saab tõhusalt arvutada, kasutades modulaarse korrutamise ruut- ja korrutamisalgoritmi [en].

RSA võrrandi tuletamine Euleri teoreemi põhjal

RSA saab hõlpsasti tuletada Euleri teoreemi ja Euleri totaalfunktsiooni abil.

Alustades Euleri teoreemiast,

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

peame näitama, et krüpteeritud sõnumi dekrüpteerimine õige võtmega annab algse sõnumi. Kui on antud täiendatud sõnum m, siis arvutatakse salastatud tekst c järgmiselt.

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

Asendades dekrüpteerimisalgoritmi, saame järgmise tulemuse

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

Tahame näidata, et see väärtus on samuti kongruentne m-ga. e ja d väärtused valiti nii, et need rahuldaksid,

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

See tähendab, et on olemas mingi täisarv k, mis on selline, et

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

Nüüd asendame krüpteeritud ja seejärel dekrüpteeritud sõnumi,

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

Rakendame Euleri teoreemi ja saavutame tulemuse.

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

Padding skeemid

Kui RSA-d kasutatakse praktikas, tuleb seda kombineerida mingisuguse polsterdusskeemiga, nii et M-i väärtused ei annaks ebaturvalist salastusteksti. Ilma polsterduseta kasutataval RSA-l võib olla mõningaid probleeme:

• Väärtused m = 0 või m = 1 annavad alati vastavalt 0 või 1 väärtusega šifreeritud tekstid, mis tulenevad eksponentsuse omadustest.
• Kui krüpteeritakse väikeste krüpteerimiseksponentidega (nt e = 3) ja väikeste m väärtustega, võib m e {\displaystyle m^{e}} (mittemodulaarne) tulemus olla rangelt väiksem kui moodul n. Sellisel juhul võib salakirju kergesti dekrüpteerida, võttes salakirju eetrijuure, võtmata arvesse moodulit.
• RSA krüpteerimine on deterministlik krüpteerimisalgoritm. Sellel puudub juhuslik komponent. Seetõttu saab ründaja edukalt käivitada valitud lihtteksti rünnaku krüptosüsteemi vastu. Nad võivad koostada sõnastiku, krüpteerides tõenäolisi lihtsaid tekste avaliku võtme all ja salvestades saadud šifreeritud tekstid. Seejärel saab ründaja jälgida sidekanalit. Niipea kui nad näevad salakirjatekste, mis vastavad nende sõnastikus olevatele tekstidele, saavad ründajad kasutada seda sõnastikku, et teada saada sõnumi sisu.

Praktikas võivad lühikeste ASCII-sõnumite saatmisel tekkida kaks esimest probleemi. Sellistes sõnumites võib m olla ühe või mitme ASCII-kodeeritud tähemärgi aheldamine. Sõnum, mis koosneb ühest ASCII-märgist NUL (mille numbriline väärtus on 0), kodeeritakse m = 0, mis annab salakirjasõnumi 0, olenemata sellest, milliseid e ja N väärtusi kasutatakse. Samamoodi annab üks ASCII SOH (mille numbriline väärtus on 1) alati salakirjateksti väärtusega 1. Süsteemides, kus tavapäraselt kasutatakse väikeseid e väärtusi, näiteks 3, oleksid kõik selle skeemi abil kodeeritud ühe tähemärgiga ASCII-sõnumid ebaturvalised, sest suurima m väärtus oleks 255 ja 255³ on väiksem kui mis tahes mõistlik moodul. Selliseid salakirju saaks taastada, võttes lihtsalt salakirjastusteksti kuupjuurt.

Nende probleemide vältimiseks on praktilised RSA rakendused tavaliselt enne krüpteerimist väärtusele m mingi struktureeritud, randomiseeritud polsterdus. See täitmine tagab, et m ei kuulu ebaturvaliste algtekstide hulka ja et antud sõnum, kui see on täidetud, krüpteeritakse üheks paljudest erinevatest võimalikest salakirjadest. Viimane omadus võib suurendada sõnastikurünnaku maksumust üle mõistliku ründaja võimete.

Sellised standardid nagu PKCS on hoolikalt kavandatud sõnumite turvaliseks polsterdamiseks enne RSA-krüpteerimist. Kuna need skeemid täidavad lihtteksti m teatud arvu lisabittidega, peab täiendamata sõnumi M suurus olema mõnevõrra väiksem. RSA-skeemid peavad olema hoolikalt kavandatud, et vältida keerulisi rünnakuid. Seda võib lihtsustada prognoositav sõnumite struktuur. PKCS-standardi varajased versioonid kasutasid ad-hoc-konstruktsioone, mis hiljem leiti, et need on haavatavad praktilise adaptiivse valitud salastusteksti rünnaku suhtes. Kaasaegsed konstruktsioonid kasutavad sõnumite kaitsmiseks turvalisi tehnikaid, nagu optimaalne asümmeetriline krüpteerimine (Optimal Asymmetric Encryption Padding, OAEP), mis takistab selliseid rünnakuid. PKCS-standardis on ka töötlemisskeemid, mis on mõeldud RSA allkirjade täiendava turvalisuse tagamiseks, nt RSA-pSS (Probabilistic Signature Scheme for RSA).

Sõnumite allkirjastamine

Oletame, et Alice kasutab Bobi avalikku võtit, et saata talle krüpteeritud sõnum. Sõnumis võib ta väita, et ta on Alice, kuid Bobil ei ole võimalik kontrollida, kas sõnum on tegelikult Alice'ilt, sest igaüks võib kasutada Bobi avalikku võtit, et saata talle krüpteeritud sõnumeid. Seega saab sõnumi päritolu kontrollimiseks kasutada RSA-d ka sõnumi allkirjastamiseks.

Oletame, et Alice soovib saata allkirjastatud sõnumi Bobile. Ta koostab sõnumi hash-väärtuse, tõstab selle d mod n-i potentsile (nagu sõnumi dekrüpteerimisel) ja lisab selle sõnumi "allkirjaks". Kui Bob saab allkirjastatud sõnumi, tõstab ta allkirja potentsile e mod n (nagu sõnumi krüpteerimisel) ja võrdleb saadud riivimisväärtust sõnumi tegeliku riivimisväärtusega. Kui need langevad kokku, teab ta, et sõnumi autoril oli Alice'i salajane võti ja et sõnumit ei ole pärast seda muudetud.

Pange tähele, et turvalised polsterdusskeemid, nagu RSA-PSS, on sõnumi allkirjastamise turvalisuse seisukohalt sama olulised kui sõnumi krüpteerimisel, ning et sama võtit ei tohiks kunagi kasutada nii krüpteerimiseks kui ka allkirjastamiseks.