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].