Information theoretic security and the one time pad (19 min)

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