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* (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ë. 
#* *e* shpërndahet si pjesë e çelësit publik. 
# Përcaktohet *d* si 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*.

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

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  Erikës. Vini re se të paktën nëntë vlera të **' do të japin një tekst të enkriptuar  të barabartë me ''*, 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

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

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.

## 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=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 = 17
* Përcaktohet *d* si d \equiv e^{-1} \pmod{\lambda{(n)}}. 
```python3
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).
```python3
>>> 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}.
```python3
>>> 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).
```python3
>>> "".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.

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