Generador RSA

Breve explicacion del algoritmo RSA:

RSA asume que hay alguna forma de convertir las letras y símbolos en números y viceversa. Esto lo podemos hacer usando una tabla de conversión como la que se muestra arriba (tabla ASCII), donde A corresponde a 11, B a 12, etc. Por ejemplo la palabra Attack! Sería transformada en 115656373947.

Luego de convertir la palabra en un número entero, encriptar y desencriptar se convierte en un asunto de cálculo simple entre grandes números enteros.

Sean p y q dos números primos muy grandes, se multiplican obteniendo
N = pq.

Sea e un entero positivo que no tenga factores en común con (p-1)(q-1).

Sea d un entero positivo tal que ed - 1 es divisible por (p-1)(q-1).

Y sean:
f(x) = x^e mod N (esto significa "divida N por x^e y tome el resto")
g(x) = x^d mod N (idem)

Use f(x) para encriptar y g(x) para desencriptar.

e es elmensaje encriptado, N es la clave pública que cualquiera puede conocer y puede usarse para encriptar un mensaje, en cambio d es el mensaje desencriptado. p y q son la clave privada que solo conoce el destinatario y le sirve para desencriptar el mensaje.

¿Por que el RSA es tan difícil de romper? Pensemos que hace Alice para recibir mensajes secretos. Primero genera los grandes números primos p y q, luego escoge e. Finalmente resuelve la ecuación para encontrar d:
ed + (p-1)(q-1)y = 1

Donde todas estas variables son números enteros. Alice publica e y N. Es todo lo que necesita para que cualquiera le envíe mensajes secretos.

Ahora veamos al malvado Bob que conoce N y quiere desencriptar los mensajes de Alice. Para esto necesita conocer los factores de N, p y q de modo de resolver la ecuación. Luego resuelve la ecuación para encontrar d, lo que equivale a desencriptar el mensaje de Alice. El problema es que para factorizar (o sea encontrar p y q que multiplicados hacen N) le tomaría una enorme cantidad de tiempo computacional -para valores de p y q suficientemente grandes- podría tomar millones de años con el conocimiento y tecnologías actuales. Brief explanation of the RSA algorithm:

RSA assumes there any way to convert the letters and symbols in numbers and vice versa. This can be done using a conversion table as shown above (ASCII table), where A corresponds to 11, B 12, etc. For example the word Attack! Would be transformed into 115,656,373,947.

After converting an integer word, encrypt and decrypt it becomes a matter of simple calculation between large integers.

P and q are two very large prime numbers, multiply obtaining
N = pq.

Is a positive integer and has no common factors with (p-1) (q-1).

D is a positive integer such that ed - 1 is divisible by (p- 1) (q-1).

They are:
f (x) = x ^ e mod N (this means "divide by N ^ x and y take the rest")
g (x) = x ^ d mod N (idem)

Use f (x) to encrypt and g (x) to decrypt.

elmensaje is encrypted and, N is the public key that anyone can know and can be used to encrypt a message, whereas d is the decrypted message. p and q are the private key known only to the recipient and serves to decrypt the message.

Why does the RSA is so hard to break? Consider that makes Alice to receive secret messages. First generate large primes p and q, then choose e. Finally solve the equation to find d:
ed + (p-1) (q-1) y = 1

Where all these variables are integers. Alice publishes N. ey is all you need for anyone to send secret messages.

Now let the evil Bob knows N and wants Alice decrypt messages. For this you need to know the factors of N, p and q in order to solve the equation. Then solve the equation to find d, equivalent to decrypt the message from Alice. The problem is that to factor (ie multiplied find p and q that make N) it would take an enormous amount of computational time -to values ​​of p and q sufficiently large ones could take millions of years with the knowledge and technologies.