CRIPTOGRAFÍA

CRIPTOGRAFÍA CLASE 1

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 envíen 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 más allá de eso, es solo eso una clave compartida, de hecho Alice podría saber que ella está hablando con Bob y Bob podría saber que él está hablando con Alice.

Pero un atacante primerizo que escuche esta conversación no tiene idea de cuál es la clave compartida. Y veremos más 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 encriptación que nos permitirán hacerlo de tal forma que un atacante no se podría imaginar que mensajes se están 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 más 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ándar, 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 multiplicándose 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, todo el 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 qué 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.

...