RSA

Per a atres usos d'este terme vore RSA (desambiguació).

En criptografia, RSA (Rivest, Shamir i Adleman) és un sistema criptográfico de clau pública desenrollat en 1977, que utilisa factorización d'número entero. És el primer i més utilisat algoritme d'este tipo i és vàlit tant per a sifrar com para firmar digitalment.

La seguritat d'este algoritme radica en el problema de la factorización de número entero. Els mensages enviats es representen per mig de números, i el funcionament es basa en el producte, conegut, de dos número primo grans elegits a l'encert i mantinguts en secret. Actualment estos cosins són de l'orde de $1 0^{300}$ , i es preveu que el seu tamany sempre creixca en l'aument de la capacitat de càlcul dels ordenadors.

Com en tot sistema de clau pública, cada usuari posseïx dos claus de sifrat: una pública i una atra privada. Quan es vol enviar un mensage confidencial, l'emissor busca la clau pública del receptor, sifra el seu mensage en eixa clau, i una volta que el mensage sifrat aplega al receptor, este s'ocupa de dessifrar-ho usant la seua clau privada.

En el cas de voler firmar (propietats d'autenticitat, integritat i no repudie), l'emissor obté un hash del mensage a firmar i ho processa en la seua clau privada obtenint aixina la firma; s'envia el mensage i la firma; el receptor recalcula el hash i dessifra el hash original en la clau pública de l'emissor, validant aixina (o no) la firma del mensage.

Es creu que RSA serà segur mentres no es coneguen formes ràpides de descompondre un número gran en producte de cosins. Encara que es creu que la computació quàntica podria proveir d'una solució al problema d'factorización, existixen investigadors que dubten que dits alvanços vagen a tornar obsolets estos algoritmes.^[1]

Història

Archiu:Adi Shamir 2009 crop.jpg

Adi Shamir, un dels tres inventors de RSA (els atres dos són Ron Rivest i Leonard Adleman).

L'algoritme va ser descrit en 1977 per Ron Rivest, Adi Shamir i Leonard Adleman, del Institut Tecnològic de Massachusetts (MIT); les lletres RSA són les inicials dels seus llinages. Clifford Cocks, un matemàtic britànic que treballava per a l'agència d'inteligència britànica GCHQ, havia descrit un sistema equivalent en un document intern en 1973. Per l'elevat cost de les computadores necessàries per a implementar-ho en l'época la seua idea no va transcendir. El seu descobriment, no obstant, no va ser revelat fins a 1997 ya que era confidencial, per lo que Rivest, Shamir i Adleman varen desenrollar RSA de forma independent.

L'algoritme va ser patentat pel MIT en 1983 en Estats Units en el número 4.405.829. Esta palesa va expirar el 21 de setembre de 2000. Com l'algoritme va ser publicat abans de patentar l'aplicació, açò va impedir que es poguera patentar en atres llocs del món. Ya que Cocks va treballar en un organisme governamental, una palesa en Estats Units tampoc haguera segut possible.

És un algoritme purament asimètric, junt en DSA. Este algoritme com el seu nom ho indica, servix per a firmar (autenticar) i per a sifrar informació. Una desventaja de l'algoritme DSA és que requerix molt més temps de còmput que RSA.

Sifrat RSA

Est consta de tres passos: generació de claus, sifrat i dessifrat

Idea del sifrat

Supongam que Bob vol enviar a Alicia un mensage secret que solament ella puga llegir.

Alicia envia a Bob una caixa en un candat obert, del que solament Alicia té la clau. Bob rep la caixa, escriu el mensage, ho posa en la caixa i la tanca en el seu candat (ara Bob no pot llegir el mensage). Bob envia la caixa a Alicia i ella l'obri en la seua clau. En este eixemple, la caixa en el candat (obert) és la «clau pública» d'Alicia, i la clau del candat és la seua «clau privada».

Tècnicament, Bob envia a Alicia un «mensage pla» $M$ en forma d'un número $m$ menor que un atre número $n$ , per mig d'un protocol reversible conegut com padding scheme («patró de farcidura»). A continuació genera el «mensage sifrat» $c$ per mig de la següent operació:

c = m^{e} (\mod n)

,

a on $e$ és la clau pública d'Alicia.

Ara Alicia dessifra el mensage en clau $c$ per mig de l'operació inversa donada per

m = c^{d} (\mod n)

,

a on $d$ és la clau privada que solament Alicia coneix.

Generació de claus

S'elegixen dos número primo distints p i q .
- Per motius de seguritat, estos números deuen triar-se de forma aleatòria i deuen tindre una llongitut en bits pareguda. Es poden trobar cosins fàcilment per mig de test de primalidad.
Es calcula n=p⋅q .
- $n$ s'usa com el mòdul para abdós claus, pública i privada.
En φ és la funció φ de Euler calcula φ(n)=(p−1)⋅(q−1) aprofitant les dos propietats de la funció de Euler següents:
- $φ (p) = p - 1$ si $p$ és primer.
Si a i b són cosins entre sí, llavors $φ (a b) = φ (a) φ (b)$ .
Es tria un sancer positiu e menor que φ(n), que siga coprimo en φ(n).
- $e$ es dona a conéixer com l'exponent de la clau pública.
- Si es tria un $e$ en una suma encadenada curta, el sifrat serà més efectiu. Un exponent $e$ molt chicotet (p. eix. $e = 3$ ) podria supondre un risc per a la seguritat.
Es determina un d (per mig d'aritmètica modular) que satisfaça la congruència e⋅d≡1(modφ(n)), és dir, que d siga el multiplicador modular invers de emodφ(n)
- Expressat d'una atra manera, $d \cdot e - 1$ és dividit exactament per $φ (n) = (p - 1) \cdot (q - 1)$ .
- Açò sol calcular-se per mig del algoritme de Euclides estés.
- $d$ es guarda com l'exponent de la clau privada.

La clau pública és

(n, e)

, açò és, el mòdul i l'exponent de sifrat. La clau privada és

(n, d)

, açò és, el mòdul i l'exponent de dessifrat, que deu mantindre's en secret.

Usant les propietats de la funció de Euler, el Teorema de Euler i el Teorema del restant chinenc es pot demostrar que

x \equiv x^{e d} (\mod n), \forall x \in 𝐙_{n}

^[2]^[3]

Notes

PKCS#1 v2.0 i PKCS#1 v2.1 s'especifiquen per mig de la funció de Carmichael $λ (n) = m c m (p - 1, q - 1)$ en lloc de la funció $φ$ de Euler, a on $m c m$ indica el mínim comú múltiple.
Per a una major eficiència els següents valors es calculen de bestreta i s'almagasenen com a part de la clau privada:
- $p$ i $q$ : els cosins per a la generació de les claus,
- $d mod (p - 1)$ i $d mod (q - 1)$ ,
- $q^{- 1} mod (p)$ .

Sifrat

Alicia comunica la seua clau pública $(n, e)$ a Bob i Alicia manté la seua pròpia clau privada en secret. Ara Bob desija enviar un mensage $M$ a Alicia.

Primer, Bob convertix $M$ en un número entero $m$ menor que $n$ . Després calcula el text sifrat $c$ per mig de l'operació

c \equiv m^{e} (\mod n)

.

Açò pot fer-se ràpit per mig del método d'exponenciación binaria. Ara Bob transmet $c$ a Alicia.

Dessifrat

Alicia pot recuperar $m$ a partir de $c$ usant el seu exponent $d$ de la clau privada per mig del següent càlcul:

m \equiv c^{d} (\mod n)

.

Ara que té $m$ en el seu poder, pot recuperar el mensage original $M$ invertint el padding scheme.

El procediment anterior funciona perque

c^{d} = (m^{e})^{d} \equiv m^{e d} (\mod n)

.

Açò és aixina perque, com hem elegit $d$ i $e$ de manera que $e d = 1 + k φ (n)$ , es complix

m^{e d} = m^{1 + k φ (n)} = m (m^{φ (n)})^{k} \equiv m (\mod n)

.

L'última congruència se seguix directament del teorema de Euler quan $m$ és coprimo en $n$ . Pot demostrar-se que les equacions es complixen per a tot $m$ usant congruència i el teorema chinenca del restant.

Açò mostra que s'obté el mensage original:

m = c^{d} (\mod n)

.

Vore també

Referències

Notes al peu

↑ Post-Quàntum Cryptography.Springer, Cham.
311–329.doi:10.1007/978-3-319-59879-6_18.Consultat el 17 d'abril de 2018.
↑ Una introducció a la criptografia de clau pública. Segona Edició. Wolfgag Willems et al. Edicions Uninorte 2010
↑ RSA Proof of Correctness

Bibliografia

R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, Vol. 21 (2), pp.120–126. 1978. Previously released as an MIT "Technical Memo" in April 1977. Initial publication of the RSA scheme.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.7: The RSA public-key cryptosystem, pp.881–887.
Wing H. Wong. Timing Attacks on RSA: Revealing Your Secrets through the Fourth Dimensió
An Attack on RSA Digital Signature
Behrends,Ehrhard Five-Minute Mathematics, American Mathematical Society, pp. 86-91. ISBN 978-0-8218-4348-2.

Referències

Este artícul conté una traducció derivada de «RSA» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Post-Quàntum Cryptography.Springer, Cham.
311–329.doi:10.1007/978-3-319-59879-6_18.Consultat el 17 d'abril de 2018.

[2] Una introducció a la criptografia de clau pública. Segona Edició. Wolfgag Willems et al. Edicions Uninorte 2010

[3] RSA Proof of Correctness

[1]

[2]

[3]