RSA (algoritëm)

RSA është një kriptosistem me çelës publik që përdoret gjerësisht për transmetim të sigurt të të dhënave. Akronimi "RSA" vjen nga inicialet mbiemrave të Ron Rivest, Adi Shamir dhe Leonard Adleman, të cilët e përshkruan publikisht algoritmin në vitin 1977. Një sistem ekuivalent u zhvillua fshehurazi, në vitin 1973 në GCHQ (agjencia e inteligjencës britanike), nga matematikanti anglez Cocks Clifford. Ky sistem u deklasifikua në vitin 1997.^[1]

Në një kriptosistem me çelës publik, çelësi i enkriptimit është publik dhe i ndryshëm nga çelësi i deshifrimit(dekriptimit), i cili mbahet sekret (privat). Një përdorues i RSA-së krijon dhe publikon një çelës publik bazuar në dy numra të mëdhenj të thjeshtë, së bashku me një vlerë ndihmëse. Numrat e thjeshtë mbahen sekret. Mesazhet mund të enkriptohen nga gjithkush duke përdorur një kopje të çelësit publik, por mund të deshifrohen vetëm nga dikush që njeh numrat e thjeshtë që janë përdorur.^[2]

RSA është një algoritëm relativisht i ngadalshëm. Për shkak të kësaj, nuk përdoret zakonisht për të enkriptuar drejtpërdrejt të dhënat e përdoruesit. Më shpesh, RSA përdoret për të transmetuar çelësa të përbashkët për kriptografinë me çelës simetrik, të cilat pastaj përdoren për enkriptuar dhe deshifruar të dhënat me masë.

Aplikimi i algoritmit

Algoritmi RSA përfshin katër hapa: gjenerimin e çelësit, shpërndarjen e çelësit, enkriptimin dhe deshifrimin.

Një parim bazë prapa RSA është vrojtimi se është praktike të gjenden tre numra të plotë pozitivë shumë të mëdhenj e, d dhe n, të tillë që me fuqizim modular për të gjithë numrat e plotë m (për 0 ≤ m < n) vlen:

$(m^{e})^{d}\equiv m{\pmod {n}}$

dhe se njohja e dhe n, apo edhe m, mund të jetë jashtëzakonisht e vështirë për të gjetur d. Barazimi i trefishtë (≡) këtu nënkupton kongruencë modulare.

Përveç kësaj, për disa veprime është e përshtatshme që rendi i dy fuqive të mund të ndryshohet dhe se ky relacion nënkupton gjithashtu

$(m^{d})^{e}\equiv m{\pmod {n}}.$

RSA përfshin një çelës publik dhe një çelës privat. Çelësi publik mund të njihet nga të gjithë dhe përdoret për enkriptimin e mesazheve. Synimi është që mesazhet e enkriptuara me çelës publik mund të deshifrohen në një kohë të arsyeshme vetëm duke përdorur çelësin privat. Çelësi publik përfaqësohet nga numrat e plotë n dhe e, dhe çelësi privat nga numri i plotë d (edhe pse n përdoret gjithashtu gjatë procesit të deshifrimit, kështu që mund të konsiderohet gjithashtu si pjesë e çelësit privat). m përfaqëson mesazhin (i përgatitur më parë me një teknikë të caktuar të shpjeguar më poshtë).

Gjenerimi i çelësit

Çelësat për algoritmin RSA gjenerohen në mënyrën e mëposhtme:

Zgjedhen dy numra të thjeshtë të ndryshëm p dhe q.
- Për qëllime sigurie, numrat e plotë p dhe q duhet të zgjidhen në mënyrë të rastësishme dhe duhet të jenë të ngjashëm në madhësi, por të ndryshojnë në gjatësi për disa shifra për ta bërë faktorizimin më të vështirë.^[2]
- p dhe q mbahen sekret.
Llogaritet n = pq.
- n përdoret si moduli për çelësat publik dhe privat. Gjatësia e tij, zakonisht e shprehur në bit, është gjatësia e çelësit.
- n shpërndahet si pjesë e çelësit publik.
Llogaritet λ(n), ku λ është funksioni λ i Karmikelit(ang. Carmichael). Pasiqë n = pq, λ(n) = shmvp(λ(p), λ(q)), dhe pasiqë nga p dhe q janë numra të thjeshtë, λ(p) = φ(p) = p - 1, dhe po ashtu λ(q) = q - 1. Prandaj λ(n) = shmvp(p - 1, q - 1).
- λ(n) mbahet sekret.
Zgjidhet një numër i plotë e i tillë që 1 < e < λ(n) dhe pmmp(e, λ(n)) = 1; d.m.th. e dhe λ(n) janë relativisht të thjeshtë.
- e në qoftë se ka gjatësi të shkurtër bitësh dhe peshë të vogël të Hammingut(ang. Hamming weight) rezulton në enkriptim më efikas - vlera më së shpeshti e zgjedhur për e është $2^{16}+1=65537$ . Vlera më e vogël (dhe më e shpejtë) e mundshme për e është 3, por një vlerë kaq e vogël për e është treguar të jetë më pak e sigurt në disa mjedise.^[3]
- e shpërndahet si pjesë e çelësit publik.
Përcaktohet d si $d\equiv e^{-1}{\pmod {\lambda {(n)}}}$ $d\equiv e^{-1}{\pmod {\lambda {(n)}}}$ ; d.m.th. , d është inversi multiplikativ i e modul λ(n).
- Kjo do të thotë: llogaritet për d ekuacioni $d*e\equiv 1{\pmod {\lambda {(n)}}}$ .
- d mbahet sekret si eksponent i çelësit privat.

Çelësi publik përbëhet nga moduli n dhe eksponenti publik (ose enkriptues) e. Çelësi privat përbëhet nga eksponenti privat (ose deshifrues) d, i cili duhet të mbahet sekret. p, q, dhe λ(n) duhet gjithashtu të mbahen sekrete sepse ato mund të përdoren për të llogaritur d. Në fakt, të gjitha mund të fshihen pasi të jetë llogaritur d.^[4]

Shpërndaja e çelësave

Supozojmë se Fati dëshiron të dërgojë informacion Erikës. Nëse ata vendosin të përdorin RSA, Fati duhet të dijë çelësin publik të Erikës për të enkriptuar mesazhin, dhe Erika duhet të përdorë çelësin e saj privat për të deshifrurar mesazhin.

Për të mundësuar Fatin të dërgojë mesazhet e tij të enkriptuara, Erika i dërgon çelësin e saj publik (n, e) Fatit nëpërmjet një linje të besueshme por jo domosdoshmërisht sekrete. Çelësi privat i Erika (d) nuk shpërndahet kurrë.

Enkriptimi

Pasi Fati merr çelësin publik të Erikës, ai mund të dërgojë një mesazh $M$ Erikës.

Për ta bërë këtë, ai së pari e kthen $M$ (tekstin e thjeshtë) në një numër të plotë $m$ (tekstin e "përbërë"), ashtu që $0 \leq m < n$ duke përdorur një protokoll të rimbursuar të njohur si një mbushje skemë. Ai pastaj llogarit tekstin e enkriptuar $c$ , duke përdorur çelësin publik të Erikës $e$ , që korrespondon me

$c\equiv m^{e}{\pmod {n}}.$

Kjo mund të bëhet mjaft shpejt, madje edhe për numra shumë të mëdhenj, duke përdorur eksponentim modular. Fati pastaj i dërgon $c$ Erikës. Vini re se të paktën nëntë vlera të $m$ do të japin një tekst të enkriptuar $c$ të barabartë me $m$ ,^[5] por kjo nuk ka gjasa të ndodhë në praktikë.

Dekriptimi

Erika mund të rimarrë $m$ nga $c$ duke përdorur eksponentin çelësit privat të saj d nga llogaritja

$c^{d}\equiv (m^{e})^{d}\equiv m{\pmod {n}}.$

Duke pasur $m$ , ajo mund të rimarrë mesazhin origjinal $M$ duke përmbysur skemën e mbushjes.

Mund të krahasojmë vlerën e fituar $m$ me mesazhin original $m$ dhe duhet të jenë të ngjashme që të verifikohet që dekriptimi është operacion invers me kriptimin.^[6]

Shembull

Më poshtë do të enkriptojmë (dhe deshifrojmë) një mesazh duke përdorur algoritmin RSA. Do të përdorim gjuhën programuese Python për ti kryer disa llogaritje.

Si mesazh kemi fjalën "LINUX" që sipas enkodimit ASCII do të jetë "76 - 73 - 78 - 85 - 88".

Gjenerimi i çelësit

Zgjedhen dy numra të thjeshtë të ndryshëm p dhe q. $p=19;q=29$

Llogaritet n = pq. $n=p*q=19*29=551$

Llogaritet λ(n), ku λ(n) = shmvp(p - 1, q - 1).

$\lambda {(n)}=shmvp(18,28)=252$

Zgjidhet një numër i plotë e, ashtu që 1 < e < λ(n)=252. Që të mbajmë shembullin të thjeshtë do të zgjedhim një e të vogël.

$e=17$

Përcaktohet d si

d\equiv e^{-1}{\pmod {\lambda {(n)}}}

.

import itertools

# tot - funksioni λ i Karmikelit
def gjej_d(e, tot):
    for i in itertools.count(start=int(tot / e)):
        if (e * i) % tot == 1:
            break
    return(i)

print(gjej_d(17,252))

Duke përdorur kodin e mësipërm gjejmë se

d=89

.

Deri tani kemi vlerat $p=19;q=29;n=551;\lambda {(n)}=252;e=17;d=89$ , ku $e=17$ është çelësi publik ndërsa $d=89$ është çelësi privat.

Enkriptimi

Për të enkriptuar mesazhin tonë "76 - 73 - 78 - 85 - 88" përdorim formulën $c\equiv m^{e}{\pmod {n}}$ e cila në Python mund të shprehet si $pow(m,e,n)$ .

>>> p, q, n, tot, e, d = 19, 29, 551, 252, 17, 89
>>> m = [76, 73, 78, 85, 88]
>>> c = [pow(i, e, n) for i in m]
>>> print(c)
[171, 424, 257, 530, 407]

Këtu kemi llogaritur dhe afishuar mesazhin e enkriptuar "171 - 424 - 257 - 530 - 407".

Denkriptimi

Për të deshifruar mesazhin e enkriptuar "171 - 424 - 257 - 530 - 407", atëherë përdorim formulën $m\equiv c^{d}{\pmod {n}}$ .^[7]

>>> m_ = [pow(i, d, n) for i in c]
>>> print(m_)
[76, 73, 78, 85, 88]

Mund të vërejmë se mesazhi i deshifruar "76 - 73 - 78 - 85 - 88", është i njëjtë me mesazhin fillestar. Mesazhin e enkoduar sipas ASCII mund ta kthejmë në shkronja me funksionin e Python-it $chr(x)$ .

>>> "".join(chr(i) for i in m_)
'LINUX'

Siguria

Siguria e RSA mbështetet në vështirësinë praktike të faktorimit të produktit të dy numrave të mëdhenj të thjeshtë, "problemi i faktorizimit". Thyerja e kodimit RSA është e njohur si problemi i RSA. Nëse është aq e vështirë sa problemi i faktorimit është një pyetje e hapur. Nuk ka metoda të publikuara për të mposhtur sistemin nëse përdoret një çelës i mjaftueshëm i mjaftueshëm.^[8]

Një gjenerator i numrave të rastësishëm kriptografisht i fortë, i cili është "mbjellë" siç duhet me entropinë adekuate, duhet të përdoret për të gjeneruar numrat p dhe q. Një analizë që krahason miliona çelësa publik të mbledhura nga interneti u bë në fillim të vitit 2012 nga Arjen K. Lenstra, James P. Hughes, Maxime Avier, Joppe W. Bos, Thorsten Kleinjung dhe Christophe Wachter. Ata ishin në gjendje të faktorizonin 0.2% të çelësave duke përdorur vetëm algoritmin e Euklidit.^[9]

Implementime

Disa biblioteka të kriptografisë që ofrojnë mbështetje për RSA përfshijnë:

Shih edhe

Referime

^ Smart, Nigel (19 shkurt 2008). "Dr Clifford Cocks CB". University of Bristol (në anglisht). Marrë më 25 janar 2022.{{cite web}}: Mirëmbajtja CS1: Gjendja e adresës (lidhja)
^ ^a ^b Rivest, R.L.; Shamir, A.; Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (në anglisht). fq. 5–15.
^ Boneh, Dan (1999). "Twenty Years of attacks on the RSA Cryptosystem". Notices of the American Mathematical Society (në anglisht). 46 (2): 203–213.
^ Applied Cryptography, John Wiley & Sons, New York, 1996. Bruce Schneier, p. 467.
^ Domethënë, vlerat e m të cilat janë të barabarta me −1, 0, ose 1 modul p përderisa gjithashtu të barabarta me −1, 0, ose 1 modul q. Ka më shumë vlera të m ashtu që c = m nëse p − 1 ose q − 1 kanë plotpjesëtues të përbashkët me e − 1 perveq 2 sepse kjo i jep më shume vlera m ashtu që $m^{e-1}{\bmod {p}}=1$ ose $m^{e-1}{\bmod {q}}=1$ respektivisht.
^ Cristoph Paar,Jan Pelzl,"Understanding Cryptography", 372 faqe
^ "RSA Algorithm". RSA Algorithm (në anglisht). Marrë më 25 janar 2022.{{cite web}}: Mirëmbajtja CS1: Gjendja e adresës (lidhja)
^ Casteivecchi, Davide, Quantum-computing pioneer warns of complacency over Internet security, Nature, October 30, 2020 interview of Peter Shor.
^ Markoff, John (14 shkurt 2012). "Flaw Found in an Online Encryption Method". The New York Times. {{cite news}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[1] Smart, Nigel (19 shkurt 2008). "Dr Clifford Cocks CB". University of Bristol (në anglisht). Marrë më 25 janar 2022.{{cite web}}: Mirëmbajtja CS1: Gjendja e adresës (lidhja)

[:0-2] Rivest, R.L.; Shamir, A.; Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (në anglisht). fq. 5–15.

[Boneh99-3] Boneh, Dan (1999). "Twenty Years of attacks on the RSA Cryptosystem". Notices of the American Mathematical Society (në anglisht). 46 (2): 203–213.

[4] Applied Cryptography, John Wiley & Sons, New York, 1996. Bruce Schneier, p. 467.

[5] Domethënë, vlerat e m të cilat janë të barabarta me −1, 0, ose 1 modul p përderisa gjithashtu të barabarta me −1, 0, ose 1 modul q. Ka më shumë vlera të m ashtu që c = m nëse p − 1 ose q − 1 kanë plotpjesëtues të përbashkët me e − 1 perveq 2 sepse kjo i jep më shume vlera m ashtu që $m^{e-1}{\bmod {p}}=1$ ose $m^{e-1}{\bmod {q}}=1$ respektivisht.

[gjeneruar_automatikisht1-6] Cristoph Paar,Jan Pelzl,"Understanding Cryptography", 372 faqe

[7] "RSA Algorithm". RSA Algorithm (në anglisht). Marrë më 25 janar 2022.{{cite web}}: Mirëmbajtja CS1: Gjendja e adresës (lidhja)

[8] Casteivecchi, Davide, Quantum-computing pioneer warns of complacency over Internet security, Nature, October 30, 2020 interview of Peter Shor.

[9] Markoff, John (14 shkurt 2012). "Flaw Found in an Online Encryption Method". The New York Times. {{cite news}}: Mungon ose është bosh parametri |language= (Ndihmë!)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]