RSA (kriptado)

**RSA** estas la unua malsimetria ĉifro, tio signifas, ke oni uzas diversajn ŝlosilojn por ĉifri kaj malĉifri. La sistemo ebligas uzadon de du ŝlosiloj: ŝlosilo publika kaj ŝlosilo kaŝa. Pretty Good Privacy estas programo kiu implementas RSA.

Unu nokton en aprilo 1977, Ron Rivest, sendorma pro kapdoloro, inventis la algoritmon de RSA, la unua sukcesa ĉifro de publika ŝlosilo. La nomo "RSA" devenas de la nomoj de la tri inventistoj: Rivest, Adi Shamir kaj Leonard Adleman de MIT. Ĝi estis priskribita en septembro 1977 en Scientific American.

RSA uzas du ŝlosilojn, unu publika ŝlosilo kaj unu kaŝa ŝlosilo. Avantaĝo de RSA kompare al AES aŭ DES estas ke la kaŝa ŝlosilo ne estas sendata aŭ eĉ sciigata de aliaj. Aliflanke, la algoritmo de RSA estas 1000-oble pli malrapida ol AES aŭ DES.

RSA estas usona patento #4405829, sed neniu, ne eĉ Philip Zimmermann, estis procesita sub la patento, tial ĝi
estas neprovita en tribunalo. RSA ne estas patentita ekster Usono kaj Kanado.

Ĉiu TTT-servilo kaj TTT-legilo de Microsoft, Sun, Netscape, Oracle, ktp, uzas RSA-on en ia formo. Netscape 4.0 uzas ĝin por
sendi retpoŝton. La legilo de Netscape sendas datumon ĉifritan kiam la bildo de ŝlosilo (en la maldekstra fundo) ne estas rompita.

## Algoritmo 
Por klarigo de la baza logiko de RSA, legu la jenon:

Elektu du malsamajn primojn, **p** kaj **q**.
 Kalkulu la produton de *p* kaj *q*: **n** = *pq*
 Kalkulu la eŭleran φ-funkcion de *n*:  \varphi(n) = (p-1)(q-1)

Elektu nombron **e** tiel, ke 3 kaj *e* kaj \varphi(n) estas
reciproke primaj, t.e. la plej granda komuna divizoro de *e* kaj \varphi(n)  estas 1.

 Solvu por *d* la kongruecon \ de  \equiv 1 \pmod{\varphi(n)}.

Nun, **por ĉifri** la mesaĝon, konvertu ĝin al nombro **M**
kaj diru:

C = Me mod n

kie **C** estas la mesaĝo ĉifrita.

**Por malĉifri** diru:

M = Cd mod n

La **publika ŝlosilo** estas (e, n) kaj la **kaŝa ŝlosilo** estas (d, n). Kiun unu ŝlosilo ĉifras, tiun la alia povas malĉifri. La ĉifrado (#6) kaj malĉifrado (#7) estas relative rapida, sed la kreo de ŝlosiloj (#1-#5) estas malrapida. Aliflanke, La kreo de ŝlosiloj ne ofte
okazas.

**Ekzemplo:** se p=5, q=11 kaj e=7, tiam n=55, \varphi(n)=40 kaj d=23. Tial mesaĝo de 2 estas ĉifrita kiel 18.

**Por programi** la algoritmon, vi unue bezonos programojn povas:

provi primon
generi hazardan nombron
multipliki, adicii, ktp, grandegajn nombrojn

**Por rompi la ĉifron**, vi devas kalkuli la kaŝan ŝlosilon
el la publika:

d = (1 mod j) / e

Sed \varphi(n) estas (p-1)(q-1), kaj p kaj q estas la primaj faktoroj de n. Sed por n sufiĉe granda, la faktorigado estos praktike nekomputebla. Ekzemple, por
faktorigi nombron de 664 bitoj, komputilo, programita laŭ nuna scio, bezonus almenaŭ 1023 da cikloj—t.e., gigaherca komputilo bezonus pli
ol miliono da jaroj! Aliflanke, ĉar la rapideco de komputiloj duobliĝas ĉiu 18 monatoj (la Leĝo de Moore), la vulgara komputilo de la jaro 2020
povos faktorigi tiun nombron post kelkaj sekundoj!

**Alivorte**, RSA funkcias ĉar p x q ⇒ n estas facila, sed la inverso, n ⇒ p x q, estas tre malfacilega por grandega n.

**Notu:** Se iu eltrovas algoritmon kiu multe faciligas faktorigdon, la sekureco de RSA (kaj PGP) forfandos.

Kategorio:Interreto
Kategorio:Komputiko
Kategorio:Kriptografio