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.

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.

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:

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

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ë. 
 p dhe q mbahen sekret. 
 Llogaritet .
 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ë . 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. 
 e shpërndahet si pjesë e çelësit publik. 
 Përcaktohet d si ; d.m.th. , d është inversi multiplikativ i e modul λ(n).
 Kjo do të thotë: llogaritet për d ekuacioni . 
 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.Applied Cryptography, John Wiley & Sons, New York, 1996. Bruce Schneier, p. 467.

 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  Erikës.

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

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  Erikës. Vini re se të paktën nëntë vlera të  do të japin një tekst të enkriptuar  të barabartë me ,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ë  ose  respektivisht. por kjo nuk ka gjasa të ndodhë në praktikë.

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

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

Mund të krahasojmë vlerën e fituar  me mesazhin original  dhe duhet të jenë të ngjashme që të verifikohet që dekriptimi është operacion invers me kriptimin.Cristoph Paar,Jan Pelzl,"Understanding Cryptography", 372 faqe

 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.

 Llogaritet .

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

 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.

 Përcaktohet d si . 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 .

Deri tani kemi vlerat  , ku  është çelësi publik ndërsa  është çelësi privat.

 Enkriptimi 
Për të enkriptuar mesazhin tonë "76 - 73 - 78 - 85 - 88" përdorim formulën  e cila në Python mund të shprehet si .>>> 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_ = [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 .>>> "".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.Casteivecchi, Davide, Quantum-computing pioneer warns of complacency over Internet security, Nature, October 30, 2020 interview of Peter Shor.

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.

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

 Botan
 Bouncy Castle
 cryptlib
 Crypto++
 Libgcrypt
 Nettle
 OpenSSL
 wolfCrypt
 GnuTLS
 mbed TLS
 LibreSSL

 Shih edhe 
 HASH Algoritmi
 Steganografia digjitale
 Nënshkrimi dixhital
 Kriptimi simetrik

 Referime 

Kategoria:Inxhineri Kompjuterike
Kategoria:Siguri e të dhënave