Ahora que hemos visto algunos ejemplos de cifrados históricos, todos los cuales son fáciles de romper, vamos a cambiar y hablar de cifrados mucho mejor diseñados. Pero antes de hacerlo, quiero en primer lugar, definir más precisamente lo que un cifrado es. Así que ante todo, una cifrado es, recordemos que un cifrado se compone de dos algoritmos. Existe un algoritmo de cifrado y un algoritmo de descifrado. Pero de hecho, un cypher se define sobre un triple. Así el conjunto de todas las claves posibles, que voy a denotar por K, a la que llamaré "espacio de claves", es el conjunto de todas las claves posibles. Este es el conjunto de posibles mensajes y este, el conjunto de todos los posibles textos cifrados. Muy bien, así que este triplete define el medio ambiente sobre el cual se define el cifrado. Y entonces el cifrado en sí es un par de algoritmos eficientes E y D. E es el algoritmo de cifrado; d es el algoritmo de descifrado. Por supuesto, E toma claves y mensajes y obtiene textos cifrados. Y el algoritmo de descifrado toma claves y textos cifrados y obtienes mensajes sin cifrar. Y los únicos requisitos es que estos algoritmos sean consistentes. Cumplen lo que se llama la propiedad de consistencia. Así que para cada mensaje en el espacio de mensajes. Y cada clave en el espacio de claves, si cifro el mensaje con la clave k y luego descifro utilizando la misma clave k, debería obtener el mensaje original con el que empecé. Por lo que esta ecuación de aquí es lo que se denomina ecuación de consistencia y cada cifrado tiene que satisfacerla para ser un cifrado, de lo contrario no es posible descifrar. Una cosa que quería señalar es que he puesto la palabra eficaz entre comillas. Y la razón por la que lo hago es porque eficiente significa cosas diferentes para personas diferentes. Si está más inclinado hacia la teoría, eficiente significa que se ejecuta en tiempo polinómico. Así que los algoritmos D y E deben ejecutarse en un tiempo polinómico en el tamaño de sus inputs. Si eres más práctico, eficiente significa que se ejecuta dentro de un cierto período de tiempo. Así, por ejemplo, el algoritmo E podría tener que tardar menos de un minuto en cifrar un gigabyte de datos. De cualquier manera, la palabra eficiente engloba ambas nociones y puedes interpretarlo como prefieras. Yo voy a referirme a eficiente y poniendo comillas´, así que si estás más inclinado a la teoría, piensa en ello como tiempo polinomial. Y si no, piensa en límites de tiempo. Otro comentario que quiero hacer es sobre el algoritmo E. A menudo es un algoritmo aleatorio. Lo significa que cuando cifras mensajes, el algoritmo E va a generar bits aleatorios para sí mismo y va a utilizar los bits aleatorios para cifrar los mensajes que recibe. Por el contrario, el algoritmo de descifrado otra es siempre determinístico. En otras palabras, dadas la clave y el texto cifrado, la salida es siempre la misma. No depende de ninguna aleatoriedad utilizada por el algoritmo. Está bien, ahora que entendemos mejor lo que es un cifrado, quiero mostraros el primer ejemplo de un cifrado seguro. Se llama "libreta de un solo uso" y fue diseñado por Vernam a principios del siglo XX. Antes de explicar realmente lo que es el cifrado, vamos a escribirlo en la terminología que acabamos de ver. Así que el espacio de mensajes para el cifrado de Vernam es el mismo que el espacio de textos cifrados, que es justamente el conjunto de todas las cadenas binarias. Esto sólo significa todas las secuencias de bits, de caracteres cero uno. El espacio de claves es básicamente el mismo que el espacio de mensajes, que de nuievo es simplemente el conjunto de cadenas binarias. Por lo tanto, una libreta de un solo uso es simplemente una cadena aleatoria grande, es una secuencia aleatoria de bits. Es tan larga como el mensaje a cifrar, tanto como el mensaje. Bueno, ahora que hemos especificado los espacios sobre los que se define el cifrado, podemos ver cómo trabaja el cifrado, y es realmente simple. Esencialmente, el texto cifrado, que es el resultado de cifrar un mensaje con una clave particular, es simplemente el XOR de los dos. Simplemente K XOR M. Veamos un ejemplo rápido de esto. Hay que recordar que XOR, este + con un círculo, XOR significa suma módulo 2. Así que si tomo un mensaje determinado, digamos, 0110111. Y una clave particular, por ejemplo 1011001. Cuando cifro el mensaje usando la clave, todo lo que hago es el XOR de las dos cadenas. En otras palabras, sumo módulo dos bit a bit. Así, obtengo uno, uno, cero, uno, uno, uno, cero. Es un texto cifrado. ¿Y ahora, cómo lo descifro? Presumo que haciendo lo mismo. Así que desciframos el texto cifrado usando una clave particular. Hago XOR de nuevo sobre la clave y el texto cifrado. Y así, todo lo que debo verificar es que satisface los requisitos de consistencia. Y vamos a verlo despacio una vez, y desde ahora, asumiremos todo esto, para que lo veáis. Por lo que vamos a hacer, vamos a asegurarnos de que si descifro un mensaje cifrado, que se cifró mediante una clave particular, obtendré el texto original M. Así que, ¿qué pasa aquí? Veámoslo. Si miro el cifrado de K y M, es simplemente K XOR M por definición. ¿Cuál es el descifrado de K XOR M usando K? Es simplemente K XOR (K XOR M). Y como ya he dicho que XOR es la suma módulo 2, la suma es asociativa, así que esto es igual a (K XOR K) XOR M, y como K XOR K es 0, entonces 0 XOR M es simplemente M. Bien, así que esto realmente demuestra que la libreta de un solo uso es realmente un cifrado, pero no dice nada acerca de la seguridad del cifrado. Y hablaremos acerca de la seguridad del cifrado en un momento. En primer lugar, voy a haceros rápidamente una pregunta, solo para asegurarme de que estamos todos sincronizados. Supongamos que tenemos un mensaje m y el cifrado del mensaje utilizando una libreta de un solo uso. Por lo tanto, todo lo que tenéis es el mensaje y el mensaje cifrado. Mi pregunta es, teniendo en cuenta este par m y c, ¿se puede saber la libreta de un solo uso utilizada en la obtención de c a partir de m? Espero que todos os hayáis dado cuenta de que, dado el mensaje cifrado, es muy fácil recuperar la clave. En particular, la clave es simplemente m XOR c. A continuación, vamos a ver que si no es inmediatamente obvio que veremos ver por qué que el caso, un poco más tarde en la charla, en la Conferencia. Esta bien bueno por lo que el pad 1-tiempo es un lugar realmente fresco desde un punto de vista de rendimiento todo lo que estás haciendo es exo anillo la clave en el mensaje por lo que es un súper, súper rápido. Cypher para cifrar y descifrar muy largos mensajes. Lamentablemente es muy difícil de utilizar en la práctica. La razón es difícil utilizar es que las claves son esencialmente tanto tiempo como el mensaje. Así que si Alice y Bob desea comunicarse segura, para que sepa Alice quiere enviar un final de mensaje a Bob, antes de que ella comience incluso enviar el primer bit del mensaje, ella tiene que transmitir una clave a Bob que es como durante mucho tiempo como ese mensaje. Bueno, si ella tiene una forma de transmitir una clave segura a Bob que como el mensaje, ella también podría utilizar ese mismo mecanismo también transmitir el mensaje en sí. Por lo tanto el hecho de que la clave es tan larga como el mensaje es bastante problemática y hace muy difícil de utilizar en la práctica la libreta. Aunque veremos que la idea de la libreta es realmente muy útil y vamos a ver un poco más tarde. Pero por ahora quiero enfocarme un poco por seguridad. Entonces las preguntas obvias son, usted sabe, ¿por qué es seguro la libreta? ¿Por qué es una buena cifra? Entonces para responder a esa pregunta, lo primero que tenemos que respuesta es, ¿qué es un cifrado seguro para empezar con? ¿Qué es, qué hace cifrado ¿seguro? Vale, por lo que el estudio, la seguridad de cifrados, tenemos que hablar un poco acerca de la teoría de la información. Y de hecho la primera persona, para estudiar la seguridad de los cifrados rigurosamente. Es muy famoso, ustedes saben, el padre de la teoría de la información, Claude Shannon y él publicaron un libro famoso en 1949, donde analiza la seguridad de la libreta. Por eso la idea de la definición de Shannon de seguridad el siguiente. Básicamente, si todos llegas a ver es el texto cypher, entonces debe aprender absolutamente nada sobre el texto. En otras palabras, el texto de cypher no debería revelar ninguna información sobre el texto. Y ver por qué tomó alguien inventó la teoría de la información para llegar a esta idea porque tienes formulize, formalmente explicar lo que hace realmente información sobre el texto Media. Bueno, eso es lo que hizo Shannon y así lemme mostrar definición de Shannon, Voy, voy a escribirlo primero lentamente. Así lo dijo Shannon es sabes suponga tienen un cypher D E que se define sobre triple K M y c igual que antes. Así KM y C definir el espacio de claves, el espacio de mensaje y el espacio de texto cypher. Y cuando decimos que el texto de cypher lo siento decir que el cypher tiene secreto perfecto si la sostiene la siguiente condición. Así sucede para cada dos mensajes m cero y M1 en el espacio de mensaje. Para cada dos mensajes el único requisito me vas a poner en estos mensajes es que tienen la misma longitud. Sí por lo que estamos sólo, vamos a ver por qué Este requisito es necesario en tan sólo un minuto. Y para cada cyphertext, en el cyphertext espacial. ¿Vale? Para cada par de mensajes de método y para cada cifrado texto, tuvo mejor sería el caso de que, si pregunto, ¿cuál es la probabilidad de que, N cifrado cero con K, woops. Cifrado n cero con k da C, ¿vale? Por lo tanto ¿la probabilidad es, si tenemos una clave aleatoria? La probabilidad es que cuando ciframos n cero, obtenemos C. Esa probabilidad debe ser el mismo que cuando ciframos N1. Muy bien, por lo que la probabilidad de cifrar una n y c es exactamente el mismo que el probabilidad de cifrado cero n y c. Y justo como se ha dicho que el clave, la distribución, es sobre la distribución de la clave. Por lo tanto, la clave es uniforme en el espacio de claves. Por lo tanto k es uniforme en k. Y a menudo voy a escribir flecha k con r un poco por encima de ella para denotar el hecho de que k es una variable aleatoria que muestrea uniformemente en el espacio de claves k. Okay, esta es la parte principal del Shannon definición. Y vamos a pensar un poco sobre esta definición de lo que realmente dice. Así que ¿qué significa que estas dos probabilidades son las mismas? Pues bien, lo que dice es que si soy un atacante y interceptar un particular cypher texto c, entonces en realidad, es la probabilidad de que el texto de cypher es el cifrado de cero n exactamente lo mismo que la probabilidad de que sea el incryption de n uno. Porque las probabilidades son iguales. Así que si tengo, todo lo que tengo el texto cypher c que todos he interceptado de no tengo ni idea si el texto de cypher provenía de cero m o el texto cypher provenía de una m porque una vez más es la probabilidad de obtener c Igualmente es probable que si se cifra cero m o m uno se cifra. Por lo tanto aquí tenemos la definición declaró nuevamente. Y just Wanna escribo estas propiedades otra vez más precisamente. Así que vamos a escribir esto otra vez. Así que qué definición [inaudible] significa es que si estoy habida cuenta de un texto cifrado concreto, no puedo decir donde llegó De. No puedo decir si es, si el mensaje cifrado. Es cero n o n uno y de hecho, esta propiedad es true para todos los mensajes. Para todos estos cero N, para todos n cero y n ones. Así que no sólo no puedo decir if'c' provenía de n cero o N, No puedo decir de si venía n dos o n tres o n cuatro o cinco n porque todos ellos son igualmente probables producir el cypher text'c'. Así que lo que esto significa realmente es que si está cifrando mensajes con un tiempo de una almohadilla luego de hecho la mayoría poderoso adversario, realmente no me importa cómo inteligente eres, el más poderoso adversario. Puede aprender nada sobre el texto, aprende nada sobre la llanura texto. En el texto de cypher. Para decirlo de una manera más, básicamente lo que esta demuestra es que no, no hay ningún ataque cypher sólo texto en una cifra que tiene secreto perfecto. Ahora, los ataques cypher realmente no los ataques sólo posibles. Y de hecho, pueden otros ataques, otros ataques pueden ser posibles. Muy bien. Ahora que comprendemos qué secreto perfecto, los medios, la pregunta es, podemos ¿construir cifrados que realmente tengan secreto perfecto? Y resulta que no hay que mirar muy lejos, una vez hecho patrón tiene secreto perfecto. Así que me quieren probar que se trata de primeros resultados de China y Wanna demostrar este hecho a usted, es muy simple prueba así vamos a ir por delante y mira que y simplemente lo hacen. Por lo tanto nos que tipo de interpretar lo que hace que significan, lo que es esta probabilidad que E K M Z es igual a C. Por lo que es realmente no tan difícil ver que para cada mensaje y cada cyphertext la probabilidad de que el cifrado de n bajo una clave k el probabilidad de que, que es igual a C, la probabilidad de que nuestra elección al azar de clave por definición. Todo es básicamente el número de claves. Kay, instruir a Kay. Tal que bien. Si cifrar. Y con k me sale c. Por lo tanto cuento literalmente el número de claves y divide por el número total de claves. ¿Verdad? Eso es lo que significa, Si elijo una clave aleatoria, esa clave mapas m c. derecho. Así que básicamente es el número de clave asigne n c dividido por el número total de claves. Esta es su probabilidad. Supongamos ahora que tuvimos una cifra tal que para todos los mensajes y todos Cypher textos, resulta que si miro este número, el número de k, k y k, tal que e, k, m es igual a c. En otras palabras, estoy mirando el número de claves Mapa m c. supongamos que este número pasa a ser una constante. Eso lo dicen pasa a ser dos, tres, o diez o quince. Acaba de hap, pasa a ser un Constanza absoluta. Si ese es el caso, entonces por definición, todos n0 y n1 y c todos, esta probabilidad tiene que ser lo mismo porque el denominador es el mismo, el numerador es el mismo, es justo como constante y por lo tanto, la probabilidad es siempre la misma para todos n y c. Así que si esta propiedad es true, la cifra ha han, la cifra tiene un secreto perfecto. Vale, por lo que permite ver lo que podemos decir acerca de Esta cantidad de una tiempo almohadilla. Por lo que la sec-, por lo tanto, la pregunta es, si me tiene un mensaje en un texto cifrado, claves de pastillas de una vez cuántos existen [inaudibles] ¿Mapa, termina este mensaje, así que la C [inaudible]? Por lo tanto, en otras palabras, cuántas claves son ¿allí, tal que M, X o k es igual a C? Así que espero que haya todo respondió uno. Y vamos a ver qué es el caso. La almohadilla de tiempo, si tenemos que, el cifrado K de m bajo k es igual a C. Pero básicamente, bien, por definición, que implica que K, X o m es igual a C. Pero que también simplemente dice que k tiene igual m, X, o, C. Sí, yo solo x a ambos lados por m y conseguir que deberá ser igual al k la ¿M, X o C. Okay? Así que lo que dice es que, por el una momento almohadilla, de hecho, la número de claves, en K, muestra el EKM es igual a C. Simplemente eso y este se cumple para todos los mensajes de texto cifrado. Y así, una vez más, por lo que hemos dicho antes, sólo dice una vez tiene el pad, secreto perfecto. Secreto perfecto y finaliza la prueba de este simple muy, muy [inaudible]. Muy, muy simple [inaudible]. Ahora lo curioso es que aunque este [inaudible] tan simple demostrar en realidad demuestra nuevamente una declaración bastante potente. Esto dice básicamente para el una vez [inaudible] no hay cypher texto sólo atacar. Así, a diferencia de la cifrado de sustitución, o el cifrado de Vigenère o las máquinas de rodillos, todos aquellos podría ser roto por ataque sólo texto cifrado. Sólo hemos demostrado para la única Pad, es simplemente imposible. Dado el cyphertext, simplemente aprende nada acerca de el texto en claro. Sin embargo, como podemos ver, esto simplemente no es el final de la historia. ME ¿quiere decir que nos hemos hechos? Es decir, básicamente, estamos hecho con el curso ahora, cuz nos tienen una forma. Para cifrar, por lo que el atacante no puede recuperar nada sobre nuestra método. Así que quizá estamos hechos con el curso. Pero de hecho, como veremos, hay son otros ataques. Y, de hecho, el una vez [inaudible] en realidad no es tal una cifrado seguro. De hecho, hay otros ataques que son posibles y veremos ver poco. ¿Vale? Nuevamente insisto en el hecho de que tiene secreto perfecto does no significa que una vez pad es el cypher seguro para usar. Muy bien. Pero como hemos dicho el problema con el un tiempo pad es que la clave secreta es realmente larga. Si tenías una manera de. Comunicando la clave secreta al otro lado. Usted puede así utilizar este mismo método exacto también comunicar el mensaje al otro lado, en cuyo caso no necesitan comenzar con una cifra. ¿Vale? Por lo tanto el problema nuevamente es el momento de una almohadilla tenía llaves realmente largos y por lo que la pregunta obvia es existen ¿otras cifras que tiene secreto perfecto y posiblemente claves mucho, mucho más cortas? Bueno, por lo que la mala noticia es el Shannon, después de probar que la libreta tiene secreto perfecto, resultado otro teorema que dice que en realidad si tiene un cypher secreto perfecto, el número de claves en la cifra debe ser al menos el número de mensajes que puede manejar el cypher. Está bien, así que en particular, lo que esto significa es si me tienen secreto perfecto. Entonces necesariamente el número de claves, o más bien la longitud de mi clave, debe ser mayor que la longitud del mensaje. Así que, de hecho, desde el almohadilla de tiempo nos satisface con la igualdad, una vez pad es un óptimo, cifrado tiene secreto perfecto, ¿vale? Así que, básicamente, lo que esto muestra es que ésta es una idea interesante. Una vez pad es un interesante cifrado. Pero, de hecho, en la realidad, es realmente muy difícil de utilizar. Es difícil de utilizar en la práctica, una vez más, debido a estas claves largas. Así que esta noción de secreto perfecto, incluso aunque es bastante interesante, básicamente dice que realmente no decirnos la cifras concretas va a ser seguro. Y nos va a ver, pero, como hemos dicho, la idea [inaudible] es bastante buena. Y vamos a ver, en la próxima Conferencia, Cómo hacer en una práctica [inaudible].