[Powered by Google Translate] [RSA] [Rob Bowden] [Tommy MacWilliam] [Harvard University] [Esta es CS50.] [CS50.TV] Vamos a echar un vistazo a RSA, un algoritmo utilizado para cifrar datos. Los algoritmos de cifrado como César y sistemas de cifrado Vigenère no son muy seguras. Con el cifrado César, un atacante sólo necesita tratar 25 diferentes claves para obtener texto sin formato del mensaje. Mientras que el sistema de cifrado Vigenère es más seguro que el cifrado César por el espacio de búsqueda grande para las llaves, una vez que un atacante conoce la longitud de la clave en un sistema de cifrado Vigenère, que se puede determinar a través de un análisis de los patrones en el texto cifrado, el cifrado Vigenère no es mucho más seguro que el cifrado César. RSA, por otra parte, no es vulnerable a los ataques de este tipo. El cifrado César y cifrado Vigenère utilizar la misma clave para cifrar y descifrar un mensaje. Esta propiedad hace que estos algoritmos cifrados simétricos clave. Un problema fundamental con algoritmos de clave simétrica es que se basan en la codificación y el envío del mensaje y el que recibe y descifra el mensaje que ya han acordado por adelantado en la llave que ambos utilizan. Pero tenemos un poco de un problema de inicio aquí. ¿Cómo dos equipos que quieren comunicar establecer una clave secreta entre ellos? Si la clave tiene que ser secreto, entonces necesitamos una manera de cifrar y descifrar la clave. Si todo lo que tenemos es la criptografía de clave simétrica entonces he regresado al mismo problema. RSA, por otra parte, utiliza un par de claves, una para encriptación y otro para desencriptación. Uno se llama la clave pública, y el otro es la clave privada. La clave pública se utiliza para cifrar mensajes. Como se puede adivinar por su nombre, podemos compartir nuestra clave pública con cualquier persona que quiera sin comprometer la seguridad de un mensaje cifrado. Los mensajes cifrados con una clave pública sólo se puede descifrar con su clave privada correspondiente. Mientras que usted puede compartir su clave pública, siempre se debe mantener en secreto su clave privada. Dado que la clave privada debe ser mantenido en secreto y sólo la clave privada se puede utilizar para descifrar los mensajes, si 2 usuarios desean enviar mensajes encriptada con RSA de ida y vuelta tanto los usuarios necesitan tener su propio par de claves pública y privada. Mensajes de usuario a usuario 2 1 sólo uso par de claves 2 usuario, y los mensajes de usuario a usuario 2 1 sólo uso 1 usuario par de claves. El hecho de que hay 2 teclas separadas para cifrar y descifrar mensajes RSA hace un algoritmo de clave asimétrica. No necesitamos para cifrar la clave pública con el fin de enviar a otro ordenador ya que la clave pública es de todos modos. Esto significa que RSA no tiene el mismo problema de inicio como un algoritmo de clave simétrica. ¿Cómo dos equipos que quieren comunicar establecer una clave secreta entre ellos? Si la clave tiene que ser secreto, entonces necesitamos una manera de cifrar y descifrar la clave. Si todo lo que tenemos es la criptografía de clave simétrica entonces que acabamos de volver al mismo problema. RSA, por otra parte, utiliza un par de claves, una para encriptación y otro para desencriptación. Uno se llama la clave pública, y el otro es la clave privada. La clave pública se utiliza para cifrar mensajes. Como se puede adivinar por su nombre, podemos compartir nuestra clave pública con quien queramos sin comprometer la seguridad de un mensaje cifrado. Los mensajes cifrados con una clave pública sólo pueden ser descifrados con su clave privada correspondiente. Mientras que usted puede compartir su clave pública, siempre se debe mantener en secreto su clave privada. Dado que la clave privada debe ser mantenido en secreto y sólo la clave privada se puede utilizar para descifrar los mensajes 2 usuarios si desea enviar mensajes de cifrado con RSA de ida y vuelta los usuarios necesitan tener su propio par de claves pública y privada. Mensajes de usuario 1 a usuario 2 sólo utilizan par de claves de usuario 2, y los mensajes de usuario a usuario 2 1 sólo utilizan un par de claves de usuario. El hecho de que hay 2 teclas separadas para cifrar y descifrar mensajes RSA hace un algoritmo de clave asimétrica. No necesitamos para cifrar la clave pública con el fin de enviar a otro ordenador ya que la clave pública es de todos modos. Esto significa que RSA no tiene el mismo problema de inicio como los algoritmos de clave simétrica. Así que si quiero enviar un mensaje utilizando cifrado RSA a Rob, primero tendrás la clave pública de Rob. Para generar un par de claves, Rob tiene que escoger dos números primos grandes. Estos números se utilizan tanto en las llaves públicas y privadas, pero la clave pública sólo se utiliza el producto de estos números 2, no los propios números. Una vez que haya cifrado el mensaje con la clave pública de Rob Puedo enviar el mensaje a Rob. Para un equipo, los números de factoring es un problema difícil. La clave pública, recuerda, utiliza el producto de dos números primos. Este producto debe tener sólo 2 factores, que resultan ser los números que componen la clave privada. Con el fin de descifrar el mensaje, RSA se utiliza esta clave privada o los números multiplicados entre sí en el proceso de creación de la clave pública. Debido a que es computacionalmente difícil factorizar el número utilizado en una clave pública en los 2 números utilizados en la clave privada es difícil para un atacante descifrar la clave privada que será necesario para descifrar el mensaje. Ahora vamos a entrar en algunos detalles de menor nivel de RSA. Primero vamos a ver cómo podemos generar un par de claves. En primer lugar, vamos a necesitar dos números primos. Vamos a llamar a estos números 2 p y q. Con el fin de recoger p y q, en la práctica seudoaleatoria generaría grandes cantidades y luego usar una prueba para determinar si existe o no esos números son probablemente mejor momento. Podemos mantener la generación de números aleatorios y otra vez hasta que tengamos dos primos que podemos utilizar. Aquí vamos a escoger p = q = 23 y 43. Recuerde, en la práctica, p y q debe ser un número mucho mayor. Por lo que sabemos, cuanto mayores sean los números, más difícil será para romper un mensaje cifrado. Pero también es más caro para cifrar y descifrar mensajes. Hoy en día es a menudo se recomienda que p y q son al menos 1024 bits, que pone a cada número en más de 300 dígitos decimales. Pero vamos a recoger estos pequeños números de este ejemplo. Ahora vamos a multiplicar p y q en conjunto para obtener un número de 3 º, que llamaremos n. En nuestro caso, n = 23 * 43, que = 989. Tenemos n = 989. A continuación vamos a multiplicar p - 1 con q - 1 para obtener un número de cuarto, que llamaremos m. En nuestro caso, m = 22 * ​​42, que = 924. Contamos con m = 924. Ahora vamos a necesitar un número e que es primo con m y menos de m. Dos números son primos relativos o primos entre sí, si el número entero único positivo que los divide de manera uniforme tanto: 1. En otras palabras, el máximo común divisor de e y m debe ser 1. En la práctica, es común que e sea el número primo 65537 siempre y cuando este número no pasa de ser un factor de m. Para las llaves, vamos a recoger e = 5 ya que 5 es primo con 924. Por último, vamos a necesitar un número más, que llamaremos d. D debe ser un valor que satisface la ecuación de = 1 (mod m). Este mod m significa que vamos a usar algo llamado aritmética modular. En la aritmética modular, una vez que recibe un número más alto que algunas límite superior que bajara a 0. Un reloj, por ejemplo, utiliza la aritmética modular. Un minuto después de 1:59, por ejemplo, es 2:00, no 1:60. El minutero se ha envuelto alrededor de 0 al llegar a un límite superior de 60. Por lo tanto, podemos decir que 60 es equivalente a 0 (mod 60) y 125 es equivalente a 65 es equivalente a 5 (mod 60). Nuestra clave pública será el par electrónico y n donde en este caso e es 5 y n es 989. Nuestra llave privada será el par d y n, que en nuestro caso es de 185 y 989. Observe que nuestro original de números primos p y q no aparecen en cualquier parte de nuestras claves privadas o públicas. Ahora que tenemos nuestro par de llaves, vamos a echar un vistazo a cómo podemos cifrar y descifrar un mensaje. Quiero enviar un mensaje a Rob, por lo que será el de generar este par de claves. Entonces voy a pedir Rob por su clave pública, que voy a utilizar para cifrar un mensaje para enviar a él. Recuerda, es totalmente aceptable para Rob para compartir su clave pública conmigo. Pero no estaría bien compartir su clave privada. No tengo ni idea de lo que su clave privada. Podemos dividir nuestro mensaje m para arriba en varios trozos todo menor que n y luego encriptar cada uno de los trozos. Vamos a cifrar la cadena CS50, que podemos dividir en 4 trozos, uno por cada letra. Para encriptar mi mensaje, voy a tener que convertirlo en algún tipo de representación numérica. Vamos a concatenar los valores ASCII con los personajes de mi mensaje. Con el fin de cifrar un mensaje dado m Voy a tener que calcular c = m al E (mod n). Pero m debe ser menor que n, o bien el mensaje completo no puede ser expresado módulo n. Podemos romper m hasta en varios trozos, todos los cuales son más pequeñas que n, y cifrar cada uno de esos trozos. Cifrado de cada uno de estos trozos, obtenemos c1 = 67 a la 5 (mod 989) que = 658. Para nuestro segundo fragmento que tenemos 83 a la 5 (mod 989) que = 15. Para nuestro trozo tercera tenemos 53 a la 5 (mod 989) que es = 799. Y por último, para nuestro trozo fin tenemos 48 a la 5 (mod 989) que = 975. Ahora podemos enviar a través de estos valores cifrados a Rob. Aquí tienes, Rob. Mientras que nuestro mensaje está en vuelo, vamos a echar otro vistazo en cómo hemos llegado hasta ese valor para d. Nuestro número d necesaria para satisfacer 5d = 1 (mod 924). Esto hace que d el inverso multiplicativo de 5 modulo 924. Dado 2 enteros, A y B, el algoritmo de Euclides extendido se puede utilizar para encontrar el máximo común divisor de estos 2 números enteros. También nos dan 2 otros números, x e y, que satisfacen la ecuación ax + by = el máximo común divisor de a y b. ¿Cómo nos ayuda? Bueno, conectar e = 5 para una y m = 924 para b ya sabemos que estos números son primos entre sí. Su máximo común divisor es 1. Esto nos da 5x + 924y = 1 o 5x = 1 - 924y. Pero si sólo se preocupan por todo modulo 924 entonces podemos abandonar la - 924y. Piense en el reloj. Si el minutero está en 1 y luego pasar exactamente 10 horas, sabemos que la manecilla de los minutos todavía estará en el 1. Aquí empezamos a 1 y luego envolver veces exactamente de y, por lo que todavía va a estar en 1. Tenemos 5x = 1 (mod 924). Y aquí esta x es el mismo que el d buscábamos antes, por lo que si se utiliza el algoritmo de Euclides extendido para obtener este número x, que es el número que debe usar como nuestro d. Ahora vamos a ejecutar el algoritmo extendido de Euclides para a = 5 y b = 924. Vamos a utilizar un método llamado el método de la tabla. La mesa contará con 4 columnas, x, y, d, k. Nuestra mesa comienza con 2 filas. En la primera fila tenemos 1, 0, entonces nuestro valor de a, que es 5, y nuestra segunda fila es 0, 1, y nuestro valor de b, que es 924. El valor de la columna cuarta, k, será el resultado de dividir el valor de d en la fila de arriba con el valor de d en la misma fila. Tenemos 5 dividido por 924 es 0 con algún resto. Eso significa que tenemos k = 0. Ahora el valor de todas las demás células será el valor de la celda 2 filas por encima de lo menos el valor de la fila por encima de ella k veces. Vamos a empezar con d en la 3 ª fila. Tenemos 5 a 924 * 0 = 5. Siguiente tenemos 0 - 1 * 0 que es 0 y 1 - 0 * 0 que es 1. No está mal, así que vamos a pasar a la siguiente fila. En primer lugar tenemos nuestro valor de k. 924 dividido por 5 = 184 con algún resto, por lo que nuestro valor de k es 184. Ahora 924 a 5 * 184 = 4. 1 a 0 * 184 es 1 y 0 - 1 * 184 es -184. Muy bien, vamos a hacer la siguiente fila. Nuestro valor de k será 1 porque 5 dividido por 4 = 1 con algún resto. Vamos a llenar las otras columnas. 5-4 * 1 = 1. 0 a 1 * 1 = -1. Y 1 - 184 * 1 es 185. Vamos a ver lo que nuestro siguiente valor de k sería. Bueno, parece que tenemos 4 dividido por 1, que es 4. En este caso en el que estamos dividiendo por 1 tal que k es igual a el valor de d en la fila de arriba significa que hemos terminado con nuestro algoritmo. Podemos ver aquí que tenemos x = 185 ey = -1 en la última fila. Ahora vamos a volver a nuestra meta original. Hemos dicho que el valor de x, como resultado de la ejecución de este algoritmo sería el inverso multiplicativo de un (b mod). Esto significa que 185 es el inverso multiplicativo de 5 (mod 924) lo que significa que tienen un valor de 185 para d. El hecho de que d = 1 en la última fila verifica que el correo fue primos entre sí a m. Si no fuera 1, entonces tendríamos que escoger un correo nuevo. Ahora vamos a ver si Rob ha recibido mi mensaje. Cuando alguien me envía un mensaje cifrado siempre que he mantenido mi clave privada en secreto Yo soy la única persona que puede descifrar el mensaje. Para descifrar un pedazo c puedo calcular el mensaje original es igual a la cantidad de potencia d (mod n). Recuerde que d y n son de mi clave privada. Para obtener un mensaje lleno de sus fragmentos que descifrar cada bloque y concatenar los resultados. Exactamente qué tan seguro es RSA? La verdad es que no lo sé. La seguridad se basa en el tiempo que le tomaría a un atacante descifrar un mensaje encriptada con RSA. Recuerde que un atacante tiene acceso a su clave pública, que contiene tanto e y n. Si el atacante consigue factorizar n en sus 2 primos, p y q, entonces podría calcular d usando el algoritmo de Euclides extendido. Esto le da la clave privada, que se puede utilizar para descifrar cualquier mensaje. Pero la rapidez podemos factorizar enteros? Una vez más, no lo sé. Nadie ha encontrado una manera rápida de hacerlo, lo que significa que dado n suficientemente grande que llevaría a un atacante irrealmente largo factorizar el número. Si alguien revela una forma rápida de factorizar enteros RSA se rompería. Pero incluso si factorización de enteros es inherentemente lento el algoritmo RSA todavía podría tener algún defecto en ella que permite la fácil descifrado de mensajes. Nadie ha encontrado y revela una falla, sin embargo, pero eso no significa que no existe uno. En teoría, alguien podría estar por ahí leyendo todos los datos cifrados con RSA. Hay otro poco de un problema de privacidad. Si Tommy encripta algún mensaje con mi clave pública y un atacante cifra el mensaje mismo con mi clave pública el atacante se verá que los dos mensajes son idénticos y así saber lo que Tommy cifrado. A fin de evitar esto, los mensajes son típicamente rellenado con bits aleatorios antes de ser cifrados para que el mismo mensaje cifrado múltiples veces será diferente, siempre y cuando el relleno en el mensaje es diferente. Pero recuerda cómo tenemos que dividir los mensajes en trozos de modo que cada fragmento es menor que n? Relleno los trozos significa que tengamos que dividir las cosas en trozos aún más desde el trozo acolchado debe ser menor que n. El cifrado y descifrado son relativamente caros con RSA, y por lo tanto necesidad de romper un mensaje en trozos muchos puede ser muy costoso. Si un gran volumen de datos tiene que ser cifrados y descifrados podemos combinar los beneficios de algoritmos de clave simétrica con los de RSA para obtener la seguridad y la eficiencia. Aunque no voy a entrar en ello aquí, AES es un algoritmo de clave simétrica como el cifrado Vigenère y César pero mucho más difícil de roer. Por supuesto, no podemos usar AES sin establecer una clave secreta compartida entre los 2 sistemas y vimos el problema con eso antes. Pero ahora podemos utilizar RSA para establecer la clave secreta compartida entre los 2 sistemas. Llamaremos a la computadora que envía los datos del remitente y el equipo que recibe los datos del receptor. El receptor tiene un par de claves RSA y envía la clave pública al remitente. El emisor genera una clave de AES, cifra con la clave pública RSA del receptor, y envía la clave AES para el receptor. El receptor descifra el mensaje con su clave privada RSA. Tanto el emisor como el receptor tienen ahora una clave compartida AES entre ellos. AES, que es mucho más rápido en el cifrado y descifrado de RSA, Ahora se puede utilizar para cifrar los grandes volúmenes de datos y enviarlos al receptor, que puede descifrar utilizando la misma clave. AES, que es mucho más rápido en el cifrado y descifrado de RSA, Ahora se puede utilizar para cifrar los grandes volúmenes de datos y enviarlos al receptor, que puede descifrar utilizando la misma clave. Sólo necesitábamos RSA para transferir la clave compartida. Ya no necesita usar RSA en absoluto. Parece que tengo un mensaje. No importa si alguien lee lo que hay en el avión de papel antes de que me llamó porque yo soy el único que tiene la clave privada. Vamos a descifrar cada uno de los trozos en el mensaje. El primer trozo, 658, elevamos a la potencia d, que es de 185, mod n, que es 989, es igual a 67, que es la letra C en ASCII. Ahora, en el segundo fragmento. El segundo fragmento tiene un valor 15, que elevamos a la potencia 185a, mod 989, y esto es igual a 83 que es la letra S en ASCII. Ya por el trozo tercero, que tiene un valor 799, elevamos a 185, mod 989, y esto es igual a 53, que es el valor del carácter ASCII en 5. Ahora, para el último fragmento, que tiene un valor 975, elevamos a 185, mod 989, y esto es igual a 48, que es el valor de 0 en el carácter ASCII. Mi nombre es Rob Bowden, y esto es CS50. [CS50.TV] RSA en absoluto. RSA en absoluto. [Risas] En todas.