En primer lugar, como se mencionó en el mensaje cifrado del sistema RSA es un cifrado de clave pública y se aprovecha de las propiedades de los números primos. Por otra parte, la aritmética utilizada (en los cálculos) no es lo común, pero lo finito llamado o modular artirmetica. Vamos a empezar desde el último a proceder paso a paso en la implementación de la encriptación RSA.
La aritmética más, como su nombre indica, un conjunto de números es finito. Un ejemplo ilustrativo de que hará todo muy claro, es el ordenador para ver. Tome un reloj clásico con las manos que todos estamos acostumbrados. Se trata de un sistema finito como la hora se muestra en el dial de 12. The Lancet, de hecho, cada vuelta volverá - tarde o temprano - la misma posición. Se da la circunstancia de que 3 +12 = 3 en nuestro ordenador para ver. Más precisamente, las operaciones aritméticas de suma y multiplicación llevará a cabo durante la misma manera dell'aritmentica común, excepto que el resultado final que hacer por módulo (mod a menudo se refiere y está presente en todos los lenguajes de programación , C, Javascript o PHP es el símbolo%). En el caso de nuestro reloj de 12 horas, de hecho, la operación de suma está a sólo 3 12 = 15 mod 12, lo que dará como resultado 3 - visualmente como estamos acostumbrados.
En la práctica - en relación con el reloj - sólo hacemos esto, aunque no de manera consciente. El funcionamiento del módulo 12, para entender, para corresponder a dividir un número entre 12 y tomar el resto de la división:
Por ejemplo, 15 mod 12 = 15/12 = (descanso 15-12) = 3
Por ejemplo, 24 mod 12 = 24/12 = (el resto, 0) = 0
Por ejemplo, 26 mod 12 = 26/12 = (descanso 14-12) = 2
El número de horas en qudrante puede ser cualquier número, 12, 24, 5, 128, ...
Sin embargo, se descubrió que la elección de un número primo, ya que el número de horas, tuvimos una característica de gran alcance. En primer lugar cuando se elige un número primo nunca nos encontramos con un resultado de cero. Además, cualquier número de un cuadrante formado por un número primo grande elegido como el primer número siempre devuelve el número de horas determinado. Por ejemplo si tenemos un reloj con 5 horas en el dial y que nos plantean, por ejemplo 2 5 2 otra vez, el número de partida:
2 5 = 32 mod 5 = 2
Que se traduce en:
x p = x (mod p)
Pierre de Fermat , el matemático que se dio cuenta de este comportamiento, se dio cuenta de que la manecilla del reloj parecían dibujar un patrón repetitivo. En la práctica, en nuestro caso, después de cinco pasos al puntero hasta la posición inicial.
| Potencias de 2 | 1 2 | 2 2 | 2 3 | 2 4 | 2 5 | 2 6 | 2 7 | 2 8 | 2 9 | 2 10 |
| Operación ordinaria | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 |
| Módulo 5 | 2 | 4 | 3 | 1 | 2 | 4 | 3 | 1 | 2 | 4 |
Con un reloj de 13 horas (para intentar que 3 13) se obtiene:
3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3
A diferencia de nuestra primera parte no se detiene en todos los números posibles, pero la tendencia parece demasiado repetitivo y, en este caso, la mano se vuelva al paso 3 después de 3 se ha multiplicado por sí mismo 13 veces!
En 1736, Leonhard Euler fue capaz de extender esta característica, así como para dar una explicación. Él demostró que, dada una hora de reloj en el dial con N, donde N = p * q es el producto de dos números primos p y q, la actuación comenzará a repetirse después de (p-1) * (q-1) 1 pasos.
Esta característica es la base de cifrado RSA. Se entendió que este patrón cíclico podría - en realidad - a desaparecer por arte de magia y luego llevar la información a la luz. Vemos que N es el producto de dos números primos p y q, este artificio será capaz de publicar y mantener N p y q secreto.
En la práctica, por lo tanto, lo que recuerda es hacer un truco de cartas. Imaginemos que tenemos un montón formado por un gran número de tarjetas, tan grande que tendría que escribir por lo menos cien dígitos. El código que queremos encriptar es una de estas tarjetas, después de estar en la parte superior de la cubierta, se mezcla con el fin de perder - al parecer - la ubicación de nuestro trabajo (el mensaje). Con la aritmética del reloj, en la práctica, es muy fácil deshacerse del papel, pero no es tan fácil que vuelva a aparecer, a menos que sepa el número exacto de los movimientos que deben figurar en la cubierta de tal manera que se re-establecer el papel encima de él.
A continuación, ejemplo completo, para que pueda ver todas las fórmulas necesarias para crear este tipo de magia.
En nuestro ejemplo vamos a utilizar un número reducido sólo para entender el mecanismo y el imaginar tener que enviar a nuestro número de tarjeta de crédito a un sitio Web
PASO 1
El sitio web se comunica - en nuestros navegadores - la primera clave pública, calculado como N = p * q (el sitio Web celosamente si los números p y q, sólo el producto se hace pública), que representa el número de horas de uso en nuestro reloj. Tenga en cuenta que en realidad el número p y q son por lo menos 60 dígitos! Vamos a utilizar un número más humano:
N = p * q = 5 * 11 = 55
Cincuenta y cinco es nuestra clave pública, gracias a la seguridad del código, el sitio Web puede ser distribuida fácilmente y por igual a todos sus clientes. A pesar de que se hizo público el número N, los factores principales que componen p y q son secretos, descifrar el número de nuestra tarjeta de crédito!
PASO 2
En este punto, y recibir un segundo número, llamado número de codificación. Este número es el mismo para todos los públicos y también, del mismo modo que N. A través de nuestro navegador podemos codificar el número de nuestra tarjeta de crédito C, en la práctica, barajar los naipes, y representa el número de barajar los naipes:
C E (Formulario N)
Y el número es generalmente pequeña y se calcula a partir de la fórmula que nos encontramos cuando vimos que en un reloj con un número de horas que consta de un número primo, hay una secuencia que se repitió más tarde (p-1) * ( q-1) +1 pasos (para más información haga clic aquí )!
En primer lugar se calcula un número b:
b = (p-1) * (q-1) = (5-1) * (11-1) = (4) * (10) = 40
Y el número debe ser un número primo que no tiene divisores con b, mcd (e, b) = 1
Para simplificar vamos a intentos - esistone diferentes técnicas para ello:
Si E = 2, entonces mcd (2, 40) = 2 no es bueno
Si E = 3, entonces mcd (3, 40) = 1 es bueno
En este punto, podemos cifrar nuestro número de tarjetas de crédito C. Si C es de 32 y tiene, por ejemplo:
Mod N y C = 32 3 mod 55 = 43 C = cf
Cool, de 43 años es nuestro número de tarjeta de crédito cifrado! Podemos enviarlo!
PASO 3
El sitio web recibe nuestro número de tarjeta de crédito C cf cifrados, o 43. En este punto se utiliza la siguiente propiedad :
Cf. C = C d mod N
El número d es la inversa de la aritmética y el número finito de b orden, nuestra aritmética del reloj. Esto se calcula por la simplicidad de modo que d * e mod b = 1
Va a tentar a descubrir que:
Para d = 1 tiene que ser 1 * 3 mod 40 = 3 mod 40 = 3 - no es bueno
Para d = 2 y tiene 2 * 3 = 6 mod 40 mod 40 = 6 - no es bueno
Para d = 3 y tiene 3 * 3 = 9 mod 40 mod 40 = 9 - no es bueno
....
Para d = 27 es de 27 * 3 = 81 mod 40 mod 40 = 1 - encontrado!
Ahora el sitio web es capaz de barajar los naipes con el fin de reaparecer en nuestro número de tarjeta de crédito:
Cf. C = C d mod n = 43 27 mod 55 = 32
En resumen
| Variable | Tipo | Fórmula | Valor |
N | Público | p * q | 5 * 11 = 55 |
b | Privado | (P-1) * (q -1) | (5-1) * (11-1) = (4) * (10) = 40 |
Lo | Público | Mcd (e, b) = 1 | Mcd (3, 40) = 1, 40 |
d | Privado | Y b * d = 1 mod | 3 27 * 27 mod 40 = 1 entonces |
C | Número de tarjeta de crédito | - | 32 |
Cf. C | Encriptados | Mod N C E | 32 3 mod 55 = 43 |
C | Descifrado | Cf. C = C d mod N | 43 27 mod 55 = 32 |
Si desea experimentar con números elegidos al azar , haga clic aquí .
Además, como se explicó en el mismo sitio de la RSA:
Supongamos que Alicia quiere enviar un mensaje m de Bob. Alice el texto cifrado c por exponentiating Crea c = m e mod n, y dónde y n son la clave pública de Bob. Ella envía c a Bob. Para descifrar, Bob exponencia también: m = c d mod n, y d, y la relación entre Asegura que Bob se recupera correctamente m. Ya que sólo sabe d Bob, Bob sólo puede descifrar este mensaje.
Los hackers y la seguridad
Nuestro número de tarjeta de crédito, cifrado, que viaja en la red y que cualquier hacker podría leerlo. Lo que se necesita para un hacker para romper el código es un número que, multiplicado por sí mismo y, a veces la computadora para ver la hora de N, da el número de tarjeta de crédito cifrada (cf C = C e mod n). Además de un ordenador normal el resultado de multiplicar una serie de autmenta progresivamente, lo que no ocurre en un ordenador para ver, donde el punto de partida de la vista se pierde muy rápidamente, ya que el tamaño de los resultados no tienen nada que ver con la posición de donde empezó. Por otra parte, en casos reales, el número N tiene más de un centenar de personalidades, hay más horas en la esfera de la computadora para ver los átomos en el universo. Es sólo por el número de decodificación de la página web se puede recuperar el número de tarjeta de crédito, pero este número d es recuperable sólo si usted sabe P y Q. A pesar del número N = p * q es público, la dificultad de factorizar N hace que sea prácticamente imposible de descifrar el código.
Sin embargo, nadie ha demostrado que existe un algoritmo matemático que puede hacer un gran número se descomponen rápidamente mediante el uso de una computadora. Si esto llegara a suceder sería arruinar la economía de los países desarrollados en ningún momento a todos.
Bibliografía
- Colin Bruce, conejos de Schrödinger - qunatistica física y los universos paralelos , Raffaello Cortina Editore
- Marcus Du Sautoy, La música de los números primos. La hipótesis de Riemann, el mayor misterio de las matemáticas , BUR
- Simon Singh, el último teorema de Fermat. La aventura de un genio, un problema matemático y el hombre que ha resuelto , Rizzoli
- Liceo Foscarini - Venecia http://www.liceofoscarini.it/studenti/crittografia/
- RSA: http://www.rsasecurity.com/
[...] 13) El cifrado RSA - 808 [...]
hola .. Me gustaría hacer un programa en C (una para un bob y alice) ... que es una RSA que descifrar y descifrar un mensaje que uno .. usted tiene alguna idea?
@ Daniel: Si te refieres a que el algoritmo se explica en el mensaje. Ver los enlaces relacionados que contienen las páginas de demostración en línea, si se le puede ayudar. De lo contrario, se refiere a algo en particular?
[...] Decir que la operación del módulo es un tema muy amplio, que traté en el cifrado RSA! Esta vez, sin embargo, hablar de códigos o cifrados, pero mucho más útil y lo [...]
La mejor explicación que he leído. Finalmente entendí algo de la aritmética modular ... Gracias!
Hola chicos,
Así cifrado RSA debe tener muy larga vida ... un nuevo giro puede provenir de la computadora cuántica capaz de factorizar números grandes rápidamente. En términos prácticos el enlace para ver el Dwave sistemas .
¿Qué te parece? Hay que pasar a otros sistemas de clave pública antes? RSA, sin embargo, no es "el único algoritmo de clave pública ...
Saludos
Maximiliano Monittola