What is cryptography? (15 min)

Qué es la criptografía?. (15 min)

Antes de comenzar con el material técnico , quiero darles un rápido

resumen de que es la Criptografía y las diferentes áreas de la misma. De esta forma

el centro de la criptografía es por supuesto la comunicación segura que esencialmente

consiste de dos partes. La primera es el establecimiento de una clave segura y luego cómo

nos comunicamos de forma segura una vez que tenemos una clave compartida. Ya dijimos que

el establecimiento de una clave segura importa mucho a Alice y Bob para que se envien mensajes el uno al otro

de tal forma que en el extremo de este protocolo, hay una clave compartida

que ambos han aceptado, la clave compartida K, y mas alla de eso, es solo eso una clave compartida, de hecho

Alice podria saber que ella esta hablando con Bob y Bob podria saber que el esta hablando

con Alice. Pero un atacante primerizo que escuche esta conversación no tiene idea de cual

es la clave compartida. Y veremos mas adelante en este curso como hacerlo. Ahora una vez que ellos

tienen una clave compartida, ellos van a querer intercambiar mensajes de forma segura usando esta clave, y

hablaremos de esquemas de encriptacion que nos permitiran hacerlo de tal forma que

un atacante no se podria imaginar que mensajes se estan enviando de un lado para otro. Y

es más un asaltante incluso no puede manipular indebidamente este tráfico sin ser detectado.

En otras palabras, estos esquemas de código proveen tanto confidencialidad e

integridad. Pero la criptografía hace mucho más, mucho mas que sólo esas dos

cosas. Y quiero darles unos cuantos ejemplos de eso. Así el primer ejemplo que

quiero darles es lo que se llama una firma digital. Así una firma digital ,

básicamente, es el análogo de una firma en el mundo físico. En el mundo

físico, recuerden cuando firman un documento, esencialmente, ustedes escriben su firma en

ese documento y su firma es siempre la misma. Ustedes siempre escriben la misma

firma en todos los documentos que ustedes quieran firmar. En el mundo digital, esto no puede

trabajar probablemente porque si el atacante obtiene un documento firmado por mí, él

puede cortar y pegar mi firma sobre otro documento que yo no podría haber

querido firmar.Y bien , no es simplemente posible en un mundo digital que mi

firma sea la misma para todos los documentos que quiera firmar. Nosotros hablaremos

de cómo construir firmas digitales en la segunda parte de este curso. Es

realmente una primitiva muy interesante y veremos exactamente cómo hacerlo. Sólamante para

darles un indicio, la forma en que la firma digital trabaja es básicamente haciendo la

firma digital via una función del contenido que será firmado. Así un atacante que

intente copiar mi firma desde un documento a otro no tendrá exito

debido a la firma. En el nuevo documento no va a estar la función correcta en base a los

datos en el nuevo documento, y como resultado, la firma no podrá verificarse. Y como dije

veremos exactamente como construir firmas digitales mas adelante y sobre eso

probaremos que esas construcciones son seguras.
Otra aplicación de la criptografía que

quiero mencionar, es la comunicación anónima. Así imagina a la usuaria

Alice que quiere hablar de algo a traves de una servidor de chat con Bob. Y, si quizás quiere hablar acerca de

una condición médica, y por eso quiere hacerlo anónimamente, de modo que el

servidor de chat no sabe quien es ella en ese momento. Bien, hay un método estándard, llamado

Mixnet, que permite a Alice comunicarse sobre el internet público con Bob. A traves de

una secuencia de proxies de tal forma que al otro lado de la comunicación Bob no tiene idea de quien

quiere hablarle. La forma de hacer este trabajo es que a medida que Alice envía sus mensajes

a Bob a través de una secuencia de proxies, esos mensajes son encriptados. Y ellos

son desencriptados apropiadamente de tal manera que Bob no tiene idea de con quíen esta hablando y

los mismos proxies no saben que Alice esta hablando con Bob, o realmente

quien esta hablando a quien de forma general. Una cosa interesante acerca de este

canal de comunicación anónima es, que este es bi-direccional. En otras palabras,

aún cuando Bob no tenga idea de con quien esta hablando, él aún así puede responder a Alice y

Alice recibirá esos mensajes. Una vez que tenemos comunicación anónima, podemos construir

otros mecanismos de privacidad. Y quiero darles un ejemplo de lo que es llamado

dinero digital. Recuerden que en el mundo físico si yo tengo un

dólar físico, puedo ir a la librería y comprar un libro y el comerciante puede no tener

idea de quien soy. la pregunta es si podemos hacer lo mismo en el mundo digital

en el mundo digital, basicamente, Alicia podria tener un dolar digital,

una moneda de un dolar digital. Y ella podria querer gastar ese dolar en algo en un comercio

en linea, quizas alguna librería en linea. Ahora, lo que nos gustaría hacer es que así sea

cuando Alice gaste su moneda en la libreria, la libreria no tiene

idea de quien es Alice. Nosotros brindamos el mismo anonimato que cuando usamos dinero fisico

Ahora el problema es que en el mundo digital, Alice puede tomar la moneda que

tuvo, esta moneda de un dolar, y antes de gastarlo, puede hacer copias de esta.

y de repente en vez de tener solo una moneda ahora

de repente tendra tres monedas de un dolar y todas ellas seran iguales por supuesto, y

no hay nada que le impida tomar las replicas de las monedas y

gastar con ellas otras mercaderias. La pregunta es como dar

dinero digital anónimo? Pero al mismo tiempo, también prevenir el doble gasto de monedas

de un dolar en diferentes comercios. En algún sentido existe una paradoja aquí donde

el anonimato esta en conflicto con la seguridad porque si tenemos dinero anónimo no hay

nada para impedir que Alice gaste el doble de monedas porque la moneda es

anónima, no hay manera de saber si se cometio este fraude. Así que la pregunta

es como resolver este conflicto. Y resulta que es totalmente factible. Y

hablaremos de dinero digital anónimo más adelante. Sólo para darle una pista, voy a

decir que la forma en que lo haremos, básicamente es asegurándose de que si Alicia gasta la moneda

una vez, entonces nadie sabe quién es, pero si se pasa la moneda más de una vez.

de repente, su identidad está totalmente expuesta y entonces podría ser objeto de

todo tipo de problemas legales. Y así es como el dinero digital anónimo se

trabaja en un alto nivel y vamos a ver cómo ponerlo en práctica más tarde en el curso.

otras aplicaciones de criptografía usan protocolos más abstractos, pero.

antes de hablar de resultados generales, deseo dar dos ejemplos. Así el

primer ejemplo tiene que ver con los sistemas electorales. Aquí esta el problema de las elecciones

Supongamos ... tenemos dos partidos, el partido cero y el partido uno. Y los electores votan por estos

partidos. Por ejemplo, este elector pudo votar por el partido cero y otro elector por el

partido uno. Y asi sucesivamente. En esta elección, el partido cero obtuvo tres votos y el partido dos

obtuvo 2 votos. Entonces el ganador de esta elección, por supuesto es el partido cero. Pero

pero generalmente, el ganador de la elección es el partido que recibe la mayoria de

votos. Ahora, el problema de las elecciones es el siguiente. Los electores les gustaría de alguna manera

computar la mayoria de los votos, pero hacerlo de una manera tal que nada

es revelado acerca de los votos individuales. Ok? Así que la pregunta es como hacer eso?

Y para ello, vamos a introducir un centro de eleccion que nos va a ayudar a

calcular la mayoría, pero manteniendo los votos del contrario secretos. Y lo que las partidos

van a hacer es que cada uno envíe sus votos cifrados al centro

de elección de tal manera que al final de la elección, el centro de las elecciones es capaz de

calcular y sacar un ganador de la elección. Sin embargo, aparte del ganador

de la elección, nada es revelado de los votos individuales. Los votos

individuales del contrario permanecerán completamente privados. Por supuesto, el centro de elecciones también

va a verificar que este elector, por ejemplo, se le permita votar y que el votante

sólo votara una vez. Pero aparte de esa información de las elecciones en el centro de elecciones en el

resto del mundo supieran nada mas acerca del otro voto que el

resultado de la eleccion. Así que esto es un ejemplo de un protocolo que implica seis

partidos. En este caso, hay cinco votantes en un centro de elecciones. Estos

partidos calculan entre ellos mismos. Y al final del cálculo, el resultado de

la elección es conocido pero no es otra cosa que revelar las entradas individuales. Ahora

un problema similar surge en el contexto de las subastas privadas. Así que en una subasta

privada cada postor tiene su propia oferta. Y ahora supongamos que el

mecanismo de subasta que está siendo utilizado es llamado subasta Vickrey donde la

definición de una subasta Vickrey es que el ganador es el mejor postor. Pero la

cantidades que el ganador paga es en realidad la segunda mejor oferta. Así que paga la

segunda oferta más alta. ? OKay, por lo que este es un mecanismo de subasta estándar llamada

subasta Vickrey. Y ahora lo que nos gustaría hacer es, básicamente permitir a los participantes

calcular, averiguar quién es elmás alto postor y cuanto se supone que hay que

pagar, pero aparte de eso, toda la otra información sobre las ofertas individuales

deben permanecer en secreto. Así, por ejemplo, la cantidad real de que el mejor postor oferta

debe permanecer en secreto. Lo único que debe convertirse en público es la segunda más alta

oferta y la identidad del mejor postor. Así que de nuevo ahora, la forma en que vamos a hacerlo

es vamos a introducir una centro de subasta en una forma similar. En esencia, todo el mundo

enviarán sus ofertas encriptadas al centro de subasta . El centro de subasta

calculara la identidad del ganador y de hecho el también calculara la segunda

mejor oferta pero aparte de estos dos valores, nada más es revelado las

ofertas individuales. Ahora bien, esto es en realidad un ejemplo de un problema mucho más general

llamado secure multi-party computation. Permítanme explicarle de que trata secure multi-party

computation. Así que aquí, básicamente de manera abstracta, los participantes tienen un secreto

entradas a sí mismos. Así, en el caso de una elección, las entradas deberian ser los

votos. En el caso de una subasta, la entradas serían las ofertas secretas. Y entonces

lo que les gustaría hacer es calcular algún tipo de una función. De sus entradas

De nuevo, en el caso de una elección, la función es una mayoría. En el caso de

subasta, la función pasa a ser el el segundo más alto, mayor número entre los x 1

a x 4. Y la pregunta es, ¿cómo puede hacer eso, de tal manera que el valor de la

la función es revelada, pero no es otra cosa que revelar acerca de los votos individuales? Así que

permítanme enseñarles una especie de una muda, insegura
forma de hacerlo. Lo que hacemos es introducir un

partido de confianza. Y luego, autoridad de confianza básicamente recoge entradas

individuales. Y un poco se compromete en mantener en
secreto las entradas individuales, por lo que sólo

sabría lo que son. Y entonces, se publica el valor de la función, al

mundo. Por lo tanto, la idea ahora es que el valor de la función se hizo público, pero

nada más se revela las entradas individuales. Pero, por supuesto, tienes

la autoridad de confianza que se tiene que confiar, y si por alguna razón no es

digno de confianza, entonces usted tiene un problema. Y así que, hay un teorema muy central en la

[Inaudible] y en realidad es un hecho poco sorprendente . Que dice que cualquier

cálculo que le gustaría hacer, cualquier función F que le gustaría calcular, que pueda

calcular con una autoridad de confianza, también puedo hacerlo sin una autoridad de confianza.

[Inaudible] de alto nivel a explicar lo que esto significa. Básicamente, lo que vamos a hacer, es

vamos a deshacernos de la autoridad. Así que los partidos son en realidad no van a enviar

sus entradas a la autoridad. Y, en hecho, no va a ser una

autoridad en el sistema. En su lugar, lo que los partidos van a hacer, es que van a

hablar entre sí usando algún protocolo. Tal que al final del protocolo

de repente el valor de la función se da a conocer a todos. Y sin embargo,

nada que no sea el valor de la función se ha revelado. En otras palabras,

las entradas individuales se mantiene en secreto. Pero de nuevo no hay autoridad, hay

sólo una forma para ellos de hablar el uno al otro de tal manera que la salida final se revela. Así

este es un resultado bastante general, es una especie de un factor sorprendente, esto es en absoluto

factible. Y, de hecho, que es y hacia el final de la clase que en realidad va a ver cómo

hacer que esto suceda. Ahora, hay algunos aplicaciones de la criptografía que no puedo

clasificar cualquier otra forma que decir que son puramente mágico. Permítanme dar a

ustedes dos ejemplos de ello. Así, el primero es lo que se llama outsourcing privado.

computation. Así que les voy a dar un ejemplo de una búsqueda de Google sólo para ilustrar el

punto. Así que imagínate Alice tiene una consulta de búsqueda. Resulta que
que quiere emitir. Resulta que

existen esquemas de encriptación muy especiales de tal manera que Alice puede enviar un cifrado de

su consulta a Google. Y entonces, debido a la propiedad del esquema de encriptación

Google realmente puede calcular en los valores encriptados sin saber lo que los

textos claramente son. Así que Google realmente puede
ejecuta su algoritmo de búsqueda masiva en la

consulta cifrada y recuperar en resultados cifrados. Muy bien. Google enviará los

resultados cifrados de nuevo a Alice. Alice descifrará y luego recibirá los

resultados. Pero la magia aquí es todo lo que Google vio sólo cifrados de las investigaciones de Alice

y nada más. Y así, Google como resultado no tiene idea de lo que Alice acabo de

buscar y Alice, sin embargo realmente aprendío, aprendío exactamente lo que ella

quería aprender. Bueno por lo que, se trata de un tipo de magia de los esquemas de encriptación. Son

bastante reciente, esto es sólo un nuevo desarrollo de aproximadamente dos o tres años

atrás, que nos permite calcular en datos encriptados, a pesar de que en realidad no saben

lo que hay dentro de la encriptación. Ahora, antes de salir corriendo y pensar acerca de esta implementación

debos advertirle que esto en este momento es realmente sólo teoria, en

el sentido de la ejecución de una búsqueda en Google el cifrado de datos es probable que tome unos

mil millones de años. Pero, sin embargo, sólo el hecho de que esto es factible es realmente

sorprendente, y es bastante útil para los cálculos relativamente simples. Así,

de hecho, vamos a ver algunas aplicaciones de este mas adelante. La otra aplicación mágica que

quiero enseñarles es lo que se llama zero knowledge. Y en particular, se los diré

acerca de algo que se llama the zero knowledge proof of knowledge. Así que aquí.

Bueno, lo que pasa es que hay un cierto número N, el que Alice lo sabe. Y la forma

el número N se construyó como un producto de dos números primos grandes. Así que imagina

aquí tenemos dos números primos, P y Q. Cada uno de ellos se puede pensar como 1000 dígitos.

Y usted probablemente sabe que están multiplicandose con
2000 números de dos dígitos es bastante fácil. Pero si

Les acabo de dar sus productos. Averiguar su factorización en números primos es

en realidad muy difícil. Y, de hecho, vamos a utilizar el hecho de que factorizar es

difícil para construir sistemas [inaudible] públicos en la segunda mitad del curso.

Muy bien, así que Alice pasa a tener este número N, y ella también conoce la factorización de

N. Ahora Bob sólo tiene el número N.en realidad no sabe la factorización.

Ahora bien, el hecho mágico enthe zero knowledge proof of knowledge, es que

Alice puede probar a Bob que ella sabe la factorización de N. Sí, en realidad puedes

darle esta prueba a Bob, que Bob puede comprobar y convencerse de que Alice

conoce la factorización de N, sin embargo Bob no aprende nada en absoluto. Acerca de los factores de P

y Q, y esto es demostrable. Bob absolutamente no aprende nada en absoluto sobre los

factores P y Q. Y la declaración en realidad es muy, muy general. Es

no sólo de probar la factorización de N. De hecho, casi cualquier rompecabezas que

quieran demostrar que sabes la respuesta , se puede demostrar que es su conocimiento. Así que si

usted tiene un crucigrama que ha resuelto. Bueno, tal vez los crucigramas no es el

mejor ejemplo. Pero si usted tiene un rompecabezas de Sudoku, por ejemplo, que desea

demostrar que lo has resuelto, puede probar a Bob en una forma que, Bob quiere aprender

nada en absoluto sobre la solución, y sin embargo Bob se convenció de que realmente

tiene una solución a este rompecabezas. Muy bien. Esos son los tipos de aplicaciones mágicas.

Y así, la última cosa que quiero decir es que la criptografía moderna es una

ciencia muy rigurosa. Y de hecho, todos los concepto que vamos a describir va a

seguir tres pasos muy rigurosos,de acuerdo,
y vamos a ver a estos tres pasos

una y otra vez y otra vez así que quiero explicar lo que son. Así que lo primero

que vamos a hacer cuando se introduce una nueva primitiva como lo es una firma digital

vamos a especificar con precisión lo que es el
modelo de amenazas. Es decir, qué puede hacer un

atacante para atacar a una firma digital y cuál es su objetivo en la forzar las

firmas?.Bueno, por lo que vamos a definir exactamente que significa para una firma

por ejemplo, para ser infalsificable.Infalsificable. Muy bien y me estoy dando firmas

digitales solo como un ejemplo. Por cada primitiva que describimos vamos a

definir con precisión lo que el modelo de amenazas es. A continuación, vamos a proponer una construcción

y luego vamos a dar una prueba de que cualquier atacante que es capaz de atacar a la

construcción bajo este modelo de amenaza. Que atacante también puede utilizarlos para resolver algunos

que subyace problemas difíciles. Y como resultado,
si el problema realmente es difícil, que en

realidad demuestra que ningún atacante puede romper la construcción bajo el modelo de amenaza.

Muy bien. Pero estos tres pasos son en realidad bastante importante. En el caso de

firmas, vamos a definir lo que significa para una firma ser falsificable, entonces vamos a

dar una construcción y, a luego por ejemplo vamos a decir que cualquiera que pueda romper nuestra

construcción puede luego ser utilizada para decir factores enteros , que se cree que es un

problema difícil. Bueno, por lo que vamos a seguir estos tres pasos en todo, y

entonces usted verá cómo esto se ve aproximadamente. Bien, así que este es el final del

segmento. Y a continuación, en el siguiente segmento vamos a hablar un poco sobre la historia

de la criptografía.