RSA

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

RSAviešojo rakto kriptosistema, kurios algoritmą 1977 metais sukūrė Ronald Rivest, Adi Shamir ir Leonard Adleman.

Raktų parinkimo algoritmas[taisyti | redaguoti kodą]

Pasirenkame du pirminius skaičius p \, ir q \, (jie turi būti pakankamai ilgi), p \ne q; sudauginame juos: n = p q \,. Pasirenkame natūralųjį skaičių e = e_A \, taip, kad jis būtų santykinai pirminis su \phi(n)=(p-1)(q-1) \,, t. y. (e,\phi(n))=1 \,.

Naudojantis Euklido algoritmu surandame skaičių d=d_A \,, kad būtų d e \equiv 1 \pmod{\phi(n)}.

Sudarome raktus: viešąjį K_v=(e,n) \, ir privatųjį K_p=(d) \,.

Šifravimas/Dešifravimas[taisyti | redaguoti kodą]

Pranešimai, kuriuos norime siųsti yra aibės \hat{M}=\{1,2,...,n\} \, skaičiai. Šifravimas apibrėžiamas lygybe:

C = e(M, e_A) =M^{e_A} \pmod{n},

 C \, – pranešimo M \, šifras C \, (M \, yra skaičius iš aibės \hat{M} \,, tad  M < n \,)

Dešifravimo algoritmas visiškai toks pat, kaip ir šifravimo:

M=d(C, d_A) = C^{d_A} \pmod{n}

RSA Iššūkis[taisyti | redaguoti kodą]

Duotajam n \, surasti pirminius p \, ir q \,, kad n = p q \,, laikoma labai sunkia matematine užduotimi. Visas RSA kriptosistemos saugumas remiasi šiuo faktu. RSA Laboratories paskelbė konkursą, kurio esmė yra surasti p \, ir q \, duotajam n \,. Pavyzdžiui, surasti p \, ir q \, skaičiui

n=13506641086599522334960321627880596993888147560566702752448514385152 \,
651060485953383394028715057190944179820728216447155137368041970396419174 \,
304649658927425623934102086438320211037295872576235850964311056407350150 \,
818751067659462920556368552947521350085287941637732853390610975054433499 \,
9811150056977236890927563 \,.

Nuo 2007 m. RSA Laboratories šių konkursų neberengia.

Nuorodos[taisyti | redaguoti kodą]