History of cryptography (19 min)

Antes de comenzar con el material técnico, quisiera hablarles un poco

acerca de la historia de la criptografia. Hay un hermoso libro sobre este tema escrito por David

Kahn llamado "the codebreakers". Abarca la historia de la criptografia, todo el camino

desde la era Babilonica hasta el presente . Aqui, solo dare

algunos ejemplos de sistemas de cifrado históricos, todos los cuales son ineficaces. Así que para hablar

acerca de sistemas de cifrado lo primero que voy a hacer es introducir a nuestros amigos Alice y Bob,

quiénes van a estar con nosotros durante el resto del trimestre. Así que Alice y Bob están tratando de

comunicarse de forma segura y hay un atacante que está tratando de espiar

su conversación. Entonces para comunicarse de forma segura, ellos van compartir una clave secreta

la cual denotare con 'K'. Ambos conocen la clave secreta, pero el atacante no

sabe nada acerca de esta clave "K". Así que ahora van a usar un sistema de cifrado, el cual

es un par de algoritmos, el de encriptación señalado por E y el de

desencriptación señalado por D. Estos algoritmos trabajan de la siguiente manera. El algoritmo de encriptación

E toma como entradas el mensaje m y la clave secreta k. Nosotros vamos a

poner una marca ^ encima de la clave, esto para denotar el hecho de que esta entrada es

realmente la clave de entrada. Y entonces se genera un texto cifrado, el cuál es la codificación de

el mensaje m usando la clave k. Siempre voy a escribir la clave primero. Ahora, y cuando

escriba: = lo que quiero decir es que la expresión define lo que

la variable c representa. Ahora, el texto cifrado se transmite a través de Internet a Bob,

de alguna manera. En realidad, podría ser transmitido a través de Internet. Podría ser transmitida

utilizando un sistema de ficheros cifrado, que en realidad no importa, pero cuando el texto cifrado

llega a Bob, se puede conectar en el algoritmo de descifrado y dar al

algoritmo de descifrado la misma clave K. Una vez más, voy a poner una marca ^ para

denotar la clave de entrada y el algoritmo de descifrado emite el texto original del

mensaje. Ahora, la razón por la que dicen que son cifrados simétricos es que tanto el

cifrado y descifrado utilizan la misma clave K. Como veremos más adelante

en el curso, hay sistemas de cifrado donde el cifrador utiliza una clave y el descifrador

utiliza una diferente. Pero aquí sólo vamos a centrarnos en el cifrado simétrico donde

ambos lados utilizan la misma clave. Bien, así que voy a dar algunos ejemplos históricos de

cifrados. El primer ejemplo de lo más simple se llama el cifrado de sustitución.

Estoy seguro de que todos ustedes jugaron el cifrado de sustitución cuando estaban en el jardín de niños.

Básicamente, una clave para un cifrado de sustitución es una tabla de sustitución que, básicamente,

dice la forma de asignar nuestras letrass. Así que aquí, por ejemplo, la letra A se asigna a C,

la letra B se asigna a W, la letra C se asigna a N y así sucesivamente

y luego la letra Z se asigna a A. Así que este es un ejemplo

de una clave por un cifrado de sustitución. Sólo para practicar la notación que introdujimos

antes, el cifrado de cierto mensaje usando esta clave, digamos que el

mensaje es bcza, el cifrado de este mensaje usando esta clave aquí, debe ser, esta

dado al sustituir una letra al tiempo. Asi b se convierte en w, c se convierte en n, z se convierte en a,

y a se convierte en c. Asi el cifrado de bcza es wnac, y esto define el texto cifrado

Similarmente podemos ver el cifrado del texto cifrado usando la misma clave y por supuesto

tendremos de regreso el mensaje original. Bien, Solo por razones

históricas, hay un ejemplo de algo relacionado con los cifrados de sustitución

llamado el cifrado cesar. El cifrado Cesar, actualmente, no es realmente un cifrado

en realidad. Y la razón es que no tiene clave. ¿Que es un cifrado cesar?, es

básicamente un cifrado de sustitución donde la sustitución es fija. Es decir, es un

cambio por tres. Así, a se convierte en d, b se convierte en e, c se convierte en f y así sucesivamente y sucesivamente.

Eso es, y se convierte en b y z se convierte en c. Es una sustitución fija se aplica

a todo el mensaje de texto plano. Así, de nuevo, esto no es un cifrado, porque no hay

clave, la clave es fija. Entonces si un atacante conoce como funciona nuestro esquema de trabajo, el

puede descifrar fácilmente el mensaje. La clave no es variable, y por lo tanto, descifrarlo es

muy fácil una vez que entiendes cómo funciona el esquema actual. Bien, así ahora, vamos

atrás al cifrado de sustitución, donde las claves son elegidas variables, las

tablas de sustitución son elegidas al azar. Y vamos a ver cómo romper este

cifrado de sustitución. Resulta ser muy facil de romper. La primera pregunta es, ¿Qué

tan grande es la clave? ¿Cuántas claves diferentes hay, asumiendo que tenemos 26

letras? Asia, yo espero todos uds dijeron que el numero de claves es 26 factorial

porque, una clave, una sustitución de clave, es simplemente una tabla, una permutación de todas las 26

letras. El numero de permutaciones de 26 letras es 26 factorial. Si calculaste

esto, 26 factorial es alrededor de 2 a la 88, lo cual significa que

describiendo una clave en un cifrado de sustitución lleva alrededor de 88 bits. Así, cada clave es

representada por cerca de 88 bits. Ahora, esto es un tamaño perfectamente fino para un espacio de clave. En

efecto, vamos a ver cifrados que son perfectamente seguros, o, tu sabes, que

son adecuadamente seguros, con espacios de clave que son aproximadamente de este tamaño. Sin embargo,

aunque el cifrado de sustitución tiene un espacio largo de clave de tamaño 2^88. Es

aun terriblemente inseguro. Así vamos a ver como romperlo. Y para romperlo, vamos

a usar frecuencia de letras. Entonces la primera pregunta es: ¿Cuál es la letra

mas frecuente en textos en ingles? Me imaginé que todos uds saben que, en efecto, E

es la letra mas común. Y eso vamos, si nosotros lo hacemos cuantificable, eso

va a ayudarnos a romper un cifrado de sustitución. Así solo con el texto cifrado, podemos

recuperar completamente el texto plano. Entonces el modo que haremos es, primero que todo, usando

frecuencias de letras en ingles. Así es como funciona. Si tú me das un

mensaje cifrado, usando el cifrado de sustitución. Lo que sé es que el texto plano

es en inglés y sé que la letra mas frecuente en inglés es e.

En efecto, aparece 12.7% de las veces en los textos estándar en inglés. Así

lo que hago es mirar el texto cifrado que me diste y voy a contar

cuántas veces aparece cada letra. Ahora la letra más común en el texto cifrado

va a ser el cifrado de la letra e con una muy alta probabilidad, Así

ahora soy capaz de recuperar una entrada en la tabla de la clave. Principalmente la letra, principalmente ahora

sé a qué letra pertenece la e. La siguiente letra más común en inglés es la

letra t, que aparece alrededor del 9.1% de las veces. Así ahora otra vez, cuento cuántas

veces aparece la letra en el texto cifrado. Y la segunda letra más

frecuente es muy probable que sea el cifrado de la letra t. Así he recuperado una

segunda entrada en la tabla de la clave. Y puedo continuar de esta manera. En efecto, la letra a

es la siguiente letra más común. Ésta aparece 8.1% de las veces. Entonces ahora puedo

suponer que la tercera letra más común en el texto cifrado es el cifrado de la

letra a. Y ahora he recuperado tres entradas de clave en la tabla de la clave. Bien, entonces ahora

¿Qué voy a hacer? Las letras restantes en inglés aparecen aproximadamente la misma cantidad de

veces, algunas letras raras como q y x. Pero estamos como estancados con este

punto. Descubrimos tres entradas en la tabla de encriptación, pero, ¿qué hacemos después? Así,

la siguiente idea es usar frecuencias de pares de letras. A veces éstas son

llamadas diagramas. Entonces, lo que haré es, contaré cuántas veces aparece cada par de

letras en el texto cifrado, y, sé que en inglés, los pares más comunes de

letras son cosas como: , he, an, in, Supongo que th es otro par común de

letras. Y sé que el par mas común de letras en el texto cifrado

probablemente sea la encriptación de una de estos cuatro pares. Y así por prueba y

error. Puedo descifrar más entradas y más elementos en la tabla de la clave y de nuevo

por más prueba y error. Me convenzo por mirar los tria-gramas. Puedo actualmente descifrar

la entrada de la tabla de claves. Así en pocas palabras aquí es que en efecto el cifrado

de sustitución es vulnerable al peor tipo de ataque posible llamado un ataque de texto cifrado

solamente. Sólo dando el texto cifrado el ataque puede recuperar la clave de descifrado

y así sucesivamente recuperar el texto plano original. Así que realmente no hay razón en

cifrar nada usando el cifrado de sustitución, porque el atacante fácilmente puede

descifrarlo todo. Es lo mismo que envíes tu texto plano completamente limpio.

Así, ahora vamos a avanzar rápidamente hasta el renacimiento, y supongamos nos movemos

desde la época romana al renacimiento, y miramos a un cifrado designado por un compañero

llamado Vigenere, quien vivió en el sigo XVI. Él diseñó un par

de cifrados. Aquí voy a mostrarte una variante de uno de estos cifrados. Este es

llamado cifrado vigenere. Así, en un cifrado vigenere, la clave es a, una

palabra. En este caso la palabra, es crypto. Tiene seis letras en ella. Y así

cifra un mensaje. Lo que harás es escribir el mensaje bajo la clave. Entonces en

este caso el mensaje es -was a nice day today- y asi replicas la llave tantas

veces como sea necesario para cubrir el mensaje. Y entonces la forma en que encriptas es básicamente

agregas las letras de la llave al mensaje de letras módulo 26. Entonces solo para darte

un ejemplo aqui. por ejemplo: si agregas Y y A, obtienes Z. Si agregas T y

A, obtienes U. Y haces esto para todas las letras. Y recuerda, cuando añades,

añades a un modelo hasta 26. Asi si pasas z, vas de nuevo a A. Entones, eso es el

cifrado vigenere. Y en efecto, descifrarlo es tan fácil como cifrarlo

Básicamente, la forma de descifrarlo es, otra vez, debes escribir el texto cifrado

debajo de la clave. Replicarías la clave y luego sustraerías la clave desde

el texto encriptado para conseguir el texto del mensaje original. Entonces, "romper" el cifrado

Vigenere es en realidad bastante fácil. Déjame mostrarte cómo hacerlo. Lo primero que

necesitamos hacer es asumir que sabemos la longitud de la clave. Así que

supongamos que conocemos eso. En este caso, la longitud de la clave es seis. Y entonces lo

que hacemos es que fraccionamos el texto en grupos de seis letras cada uno, ¿ok? Entonces vamos a

conseguir un montón, un montón de grupos como éste. Cada uno contiene seis letras. Y entonces

vamos a mirar a la primera letra de cada grupo, ¿Ok? Entonces, en este caso, sí,

estamos mirando la primera letra, cada seis caracteres. Ahora, ¿qué sabemos de

estas seis letras? Sabemos que, de hecho, están todas encriptadas usando la misma

letra en el texto cifrado. Todas éstas están encriptadas usando la letra "c". En otras

palabras. "z", "L", "W" es un desplazamiento por tres de las letras del texto original. Así que si recolectamos todas

estas letras, resulta que la letra más común en el set