El rsa...

ALGORITMO RSA

El algoritmo RSA fue desarrollado en el MIT por Rivest-Shamir-Adleman (1978).
Es un algoritmo sencillo:

GENERACION DE CLAVES
1. Se seleccionan dos números primos suficientemente grandes: p y q
2. Se calcula su producto: n=pxq (n debe ser computacionalmente imposible de factorizar).
3. Se selecciona un entero d que cumpla: gcd(T(n),d)=1T(n) es la llamada función totiente, y su valor es la cantidad de números primos relativos a n y que sean menores que n.
4. Calculamos e: e=d-1 mod T(n)
5. La clave publica es: KU=(e,n)
6. La clave privada es: KR=(d,n)
Toda la fuerza del algoritmo se basa en la dificultad de factorizar n
PROCESO DE CIFRADO
Si el texto plano es M, el texto cifrado es: C=Me(mod n)PROCESO DE DESCIFRADO
Si el texto cifrado es C, el texto descifrado es: M=Cd(mod n)

Algoritmos de clave asimétrica
Algoritmo Rivest-Shamir-Adleman (RSA)
El algoritmo RSA se fundamenta en el hecho de que la factorización de números primos es un problema de resolución computacionalmente difícil.
Algoritmo
El algoritmo RSA está descrito en infinidad de sitios y es extremadamente simple:Primero es necesario calcular las claves:
1. encontrar dos números primos grandes (de 100 cifras o más), p y q.
2. definir n (conocido como módulo) como:
n = pq
3. definir z como:
z = (p-1)(q-1)
4. encontrar un número primo aleatorio e menor que el módulo y tal que e y z sean primos entre sí.
5. determinar un valor d tal que secumpla que (de - 1) es divisible entre z (d existe y es único).
El cifrado del mensaje M se obtendrá según la siguiente operación:
C = Me (mod n)
Y el descifrado mediante la siguiente:
M = Cd (mod n)
Por tanto, la clave pública estará constituida por el par (n,e), mientras que la clave privada la constituirán (n,d).
Ejemplo
Supongamos p=47 y q=57
Por tanto, n=pq=2773
De estos datos, secalcula (p-1)(q-1)=2668
Eligiendo e=17, calculamos d utilizando algoritmos de factorización (d=157)
Por tanto, la clave pública P será el par (17, 2773), mientras que la privada, S, la constituirá el par (157, 2773).
Funcionamiento
Como ya hemos señalado, el algoritmo RSA se fundamenta en el hecho de que factorizar números muy grandes es un problema de difícil resolución. Si un intruso que quisieraquebrar el algoritmo fuese capaz de factorizar n (parte de la clave pública), entonces podría utilizar estos factores para deducir rápidamente e y d. Por lo tanto, si fuese fácil factorizar números grandes, sería fácil romper RSA. Lo contrario, es decir, si por ser difícil factorizar números muy grandes es difícil romper RSA no se ha demostrado (de hecho, tampoco se ha demostrado que factorizarnúmeros muy grandes sea en realidad un problema difícil).
Para lograr la máxima seguridad, es necesario utilizar enteros de más de 100 dígitos de longitud, pues factorizar números más pequeños es posible. Según asegura Bruce Schneier en Applied Cryptography, en 1996, un número de 129 dígitos decimales está en el borde de la tecnología factorizadora. Además, se debe asegurar que el producto(p-1)(q-1) no tiene factores primos pequeños.
Rapidez
Fruto de los requerimientos para hacer seguro RSA, surge su principal problema: su lentitud. En general, se elige como clave pública el menor de los dos exponentes a fin de conseguir que el proceso de cifrado sea el más rápido (más que el descifrado, el cual, a su vez lo es más que la generación de claves). El cifrado, que utiliza la clave pública,tiene una complejidad de O(k2), el descifrado O(k3) y la generación de claves O(k4), en donde k es la longitud en bits del módulo.
Una práctica habitual es elegir como clave pública un exponente pequeño, típicamente 1001 ó 10001, variando el módulo.
Patentes
Como consecuencia de la precipitada publicación del algoritmo RSA (ante el temor de que la administración de seguridad de EE.UU. no...