Antes de começarmos com o material técnico, eu quero dar-lhe uma rápida visão geral do que é a criptografia e as diferentes áreas de criptografia. O núcleo de criptografia do curso é a comunicação segura que, essencialmente, consiste de duas partes. O primeira é estabelecer uma chave segura e, então, como fazer a comunicação de forma segura, já que temos a chave compartilhada. Já dissemos que o estabelecimento da chave segura equivale a Alice e Bob enviarem mensagens de um ao outro, de forma que, ao final deste protocolo, haja uma chave compartilhada que ambos concordam, compartilhada chave K e, além disso, além de apenas uma chave compartilhada, de fato Alice saberia que ela está falando com Bob e Bob sabe que ele está falando com Alice. Mas um atacante pobre que escuta em conversa sobre isso não tem idéia do que a chave compartilhada é. E vamos ver como fazer isso mais tarde no curso. Agora, uma vez que têm uma chave compartilhada, eles querem trocar mensagens de forma segura, utilizando esta chave, e falaremos sobre esquemas de criptografia que lhes permitem fazer isso de tal maneira que atacante não pode descobrir o que as mensagens estão sendo enviadas e recebidas. E , além disso, um atacante não pode mesmo mexer com esse tráfego sem ser detectado. Em outras palavras, estes esquemas de criptografia fornecer confidencialidade e integridade. Mas a criptografia faz muito, muito, muito mais do que apenas estes dois coisas. E eu quero dar-lhe alguns exemplos de que. Assim, o primeiro exemplo que eu quero dar a você é que é chamado de assinatura digital. Assim, uma assinatura digital, , basicamente, é o análogo da assinatura no mundo físico. Na física mundo, lembre-se quando você assina um documento, essencialmente, você escrever sua assinatura em que documento ea sua assinatura é sempre a mesma. Você sempre escreve a mesma assinatura em todos os documentos que você quer assinar. No mundo digital, isso não pode possivelmente trabalhar porque se o atacante apenas obtido um documento assinado por mim, ele pode cortar e colar a minha assinatura até algum outro documento que eu não poderia ter quis assinar. E assim, simplesmente não é possível em um mundo digital que o meu assinatura seja a mesma para todos os documentos que eu quero assinar. Então falaremos sobre como construir as assinaturas digitais, na segunda metade do curso. É realmente um primitivo interessante e vamos ver exatamente como fazê-lo. Apenas para lhe dar uma dica, a forma de trabalho é, basicamente, assinaturas digitais, tornando o assinatura digital via função do conteúdo a ser assinado. Assim, um atacante que tenta copiar a minha assinatura de um documento para outro não vai ter sucesso porque a assinatura. No novo documento não vai ser o bom funcionamento do dados no documento novo, e como resultado, a assinatura não irá verificar. E como eu disse, vamos ver exatamente como a construção de assinaturas digitais, mais tarde, e então nós provar que essas construções são seguras. Outra aplicação de criptografia que eu queria mencionar, é a comunicação anônima. Então, aqui, imagine usuário Alice quer falar com algum servidor de bate-papo, Bob. E, talvez, ela quer falar sobre uma condição médica, e por isso ela quer fazer isso anonimamente, para que o bate-papo servidor não sabem realmente quem ela é. Bem, há um método padrão, chamado de mixnet, que permite que Alice se comunicar através da internet pública com Bob através de uma seqüência de proxies de tal forma que no final do Bob comunicação não tem idéia de quem ele apenas falado. A forma de trabalhar mixnets é basicamente como Alice envia suas mensagens para Bob através de uma seqüência de procurações, estas mensagens encriptadas e obter decifrada apropriadamente de modo que Bob não tem idéia de quem ele falou e os proxies se nem sequer sabe que Alice está falando com Bob, ou que realmente quem é falando com quem mais geral. Uma coisa interessante sobre este anônimo canal de comunicação é, este é bi-direcional. Em outras palavras, mesmo que Bob não tem idéia de quem ele está falando, ele ainda pode responder a Alice e Alice vai ter essas mensagens. Uma vez que temos uma comunicação anônima, podemos construir outros mecanismos de privacidade. E eu quero te dar um exemplo que é chamado anônimo dinheiro digital. Lembre-se que no mundo físico se eu tenho um físico dólar, eu posso entrar numa livraria e comprar um livro eo comerciante não teria idéia de quem eu sou. A questão é se podemos fazer exatamente a mesma coisa no mundo digital mundo. No mundo digital, basicamente, Alice pode ter um dólar digital, uma moeda de dólar digital. E ela pode querer gastar esse dólar digital em alguns on-line comerciantes, talvez alguma livraria on-line. Agora, o que nós gostaríamos de fazer é torná-lo tão que quando Alice passa sua moeda na livraria, a livraria não teria idéia de quem é Alice. Então, nós fornecemos o mesmo anonimato que nós temos de dinheiro físico. Agora o problema é que no mundo digital, Alice pode levar a moeda que ela tinha, esta moeda de um dólar, e antes que ela passou, ela pode realmente fazer cópias dele. E então, de repente, em vez de apenas ter apenas uma moeda de um dólar agora tudo de repente ela tem três moedas do dólar e eles são todos iguais, é claro, e não há nada impedindo-a de tomar essas réplicas de uma moeda de dólar e gastá-lo em outros comerciantes. E assim a questão é como vamos fornecer anônimo dinheiro digital? Mas ao mesmo tempo, também impedir Alice de gastar o dobro moeda do dólar em estabelecimentos comerciais diferentes. Em certo sentido, há aqui um paradoxo onde anonimato está em conflito com segurança, pois se temos dinheiro anônimo há nada para impedir Alice de dobrar os gastos da moeda e porque a moeda é anônimo não temos nenhuma maneira de dizer que cometeu essa fraude. E assim a questão é como vamos resolver essa tensão. E ao que parece, é completamente factível. E vamos falar sobre dinheiro digital anónimo mais tarde. Só para lhe dar uma dica, eu vou dizer que a forma como o fazemos é basicamente, certificando-se que, se Alice passa da moeda uma vez e depois ninguém sabe quem ela é, mas se ela passa a moeda mais de uma vez, todos repente, sua identidade é completamente exposta e, em seguida, ela poderia estar sujeito a tipos todos de problemas legais. E isso é como anônimo dinheiro digital seria trabalho a um nível elevado e vamos ver como implementá-lo mais tarde no curso. Outro aplicativo de criptografia tem a ver com os protocolos mais abstratas, mas antes de eu falar o resultado geral, eu quero te dar dois exemplos. Assim, o primeiro exemplo tem a ver com os sistemas eleitorais. Então aqui está o problema da eleição. Suponha ... temos dois partidos, o partido de zero e um partido. E os eleitores votam para estes partes. Assim, por exemplo, esse eleitor poderia ter votado para a festa de zero, este eleitor votou um partido. E assim por diante. Assim, nesta eleição, o partido tem três votos a zero e dois do partido obteve dois votos. Assim, o vencedor da eleição, é claro, é parte zero. Mas mais geral, o vencedor da eleição é o partido que recebe a maioria dos dos votos. Agora, o problema de votação é o seguinte. Os eleitores de alguma forma como para calcular a maioria dos votos, mas fazê-lo de tal modo que nada mais, tais é revelado sobre seus votos individuais. Ok? Então a questão é como fazer isso? E para isso, vamos introduzir um centro eleitoral que vai nos ajudar calcular a maioria, mas manter os votos de outra forma secreta. E o que as partes vai fazer é cada um irá enviar a criptografia engraçado de seus votos para a eleição centro de tal maneira que, no final da eleição, o centro de eleição é capaz para calcular e emitir o vencedor da eleição. No entanto, à excepção do vencedor da eleição, nada mais é revelado sobre os votos individuais. O indivíduo votos caso contrário permanecem completamente privado. Claro que o centro de eleição é também vai verificar que este eleitor, por exemplo, é permitido votar e que o eleitor tem só votou uma vez. Mas diferente do que centro de informação da eleição e da resto do mundo aprendeu nada sobre o voto do eleitor que não seja o resultado da eleição. Portanto, este é um exemplo de um protocolo, que envolve seis partes. Neste caso, há cinco eleitores em um centro de eleição. Estes partes computar entre si. E no final da computação, o resultado da eleição é conhecida, mas nada é revelado sobre as entradas individuais. Agora um problema semelhante surge no contexto de leilões particulares. Então, em uma privada leilão cada licitante tem a sua própria candidatura que ele quer dar um lance. E agora suponha que o mecanismo de leilão que está sendo usado é o que é chamado de leilão onde o Vickrey definição de um leilão de Vickrey é que o vencedor é o maior lance. Mas o montantes que o vencedor paga é realmente o segundo maior lance. Assim, ele paga o segundo lance mais alto. Ok, então este é um mecanismo de leilão padrão chamado leilão Vickrey. E agora o que nós gostaríamos de fazer é basicamente permitir aos participantes computação, para descobrir quem é o maior lance e quanto ele deveria salário, mas além disso, todas as outras informações sobre os lances individuais deve permanecer secreta. Assim, por exemplo, a quantidade real que o maior lance licitante deve permanecer secreta. A única coisa que deve se tornar público é o segundo maior oferta ea identidade de quem pagasse mais. Então, novamente agora, o caminho que vamos fazer que é vamos introduzir uma lota, e de um modo semelhante, essencialmente, todo mundo irá enviar suas propostas criptografadas para a lota. O centro de leilão calcular a identidade do vencedor e, de facto, ele será também calcular a segunda lance mais alto, mas outros do que estes dois valores, nada mais é revelado sobre o lances individuais. Agora, este é realmente um exemplo de um problema muito mais geral chamada computação multi-partidário seguro. Deixe-me explicar o que seguro multi-partido cálculo é sobre. Então, aqui, basicamente, abstratamente, os participantes têm um segredo entradas para si. Assim, no caso de uma eleição, as entradas seria o votos. No caso de um leilão, as entradas seriam as propostas secretos. E, em seguida que eles gostariam de fazer é calcular algum tipo de função de seus insumos. Novamente, no caso de uma eleição, a função é uma maioria. No caso de leilão, a função passa a ser o segundo maior maior número, entre um x para x quatro. E a pergunta é, como podem fazer isso, de tal forma que o valor do função é revelado, mas nada é revelado sobre os votos individuais? Assim deixe-me mostrar-lhe uma espécie de caminho, mudo de fazê-lo inseguro. O que fazemos é introduzir um confiança do partido. E então, essa autoridade confiável basicamente recolhe indivíduo entradas. E isso meio que promete manter as entradas individuais segredo, para que ele só saberia o que são. E, em seguida, publica o valor da função, para mundo. Assim, a ideia é agora que o valor da função tornou-se público, mas nada mais é revelado sobre as entradas individuais. Mas, é claro, você tem esta confiável autoridade que você tem que confiar, e se por algum motivo não é confiável, então você tem um problema. E assim, há um teorema muito central em criptografia e é realmente muito um fato surpreendente. Que diz que qualquer computação que você gostaria de fazer, qualquer função F que você gostaria de calcular, que você pode de computação com uma autoridade confiável, você também pode fazer sem uma autoridade confiável. Deixe-me a um nível elevado explicar o que isso significa. Basicamente, o que vamos fazer, é nós vamos nos livrar da autoridade. Assim, as partes são, na verdade não vai enviar suas entradas para a autoridade. E, de fato, não há mais vai ser um autoridade no sistema. Em vez disso, o que os partidos vão fazer, é que vamos conversa um ao outro usando algum protocolo. De tal modo que no final do protocolo de todos de um valor a súbita da função torna-se conhecida por todos. E ainda nada mais do que o valor da função é revelado. Em outras palavras, o entradas individuais ainda é mantido em segredo. Mas, novamente não há autoridade, não há apenas uma maneira para que eles conversem entre si de tal forma que o resultado final é revelado. Assim este é um resultado bastante geral, é uma espécie de fato surpreendente de que é em tudo factível. E de fato é e para o final da aula, vamos ver realmente como fazer isso acontecer. Agora, existem algumas aplicações de criptografia que eu não posso classificar de outra maneira que não quer dizer que eles são puramente mágico. Deixe-me dar -lhe dois exemplos disso. Assim, o primeiro é o que é chamado de terceirização privada computação. Então eu vou lhe dar um exemplo de uma busca no Google apenas para ilustrar a ponto. Então, imagine Alice tem uma consulta de pesquisa que ela quer emitir. Acontece que existem esquemas de criptografia muito especiais, que Alice pode enviar uma criptografia de consulta-la para o Google. E, em seguida, por causa da propriedade de o esquema de criptografia Google pode realmente calcular os valores criptografados sem saber o que o textos simples são. Então, o Google pode realmente executar seu algoritmo de busca em massa no consulta criptografado e recuperar no resultado criptografados. Okay. Google irá enviar a resultados criptografado de volta para Alice. Alice irá descriptografar e, em seguida, ela receberá o resultados. Mas a magia aqui é tudo serra Google era apenas criptografias de suas consultas e nada mais. E assim, o Google como um resultado não tem idéia do que Alice apenas procurado e, no entanto, Alice realmente aprendi exatamente o que ela queria aprender. Ok então, estes são uma espécie mágica de esquemas de criptografia. Eles são relativamente recente, este é apenas o desenvolvimento de uma nova cerca de dois ou três anos atrás, que nos permite calcular em dados criptografados, mesmo que nós realmente não sabemos o que está dentro da criptografia. Agora, antes de correr e pensar sobre a implementação isso, devo avisar que este é realmente neste momento apenas teórica, em o sentido que a execução de uma pesquisa no Google sobre dados de encriptação provavelmente levaria um bilhões de anos. Mas, no entanto, só o fato de que isso é factível já está realmente surpreendente, e já é bastante útil para cálculos relativamente simples. Assim, em fato, veremos algumas aplicações deste mais tarde. O outro aplicativo mágico que eu quero lhe mostrar é o que chamamos de conhecimento nulo. E, em particular, eu vou dizer sobre algo chamado de prova de conhecimento nulo do conhecimento. Então, aqui ... o que acontece é que há um certo número N, o que Alice conhece. E o caminho o número N foi construído é como um produto de dois números primos de grandes dimensões. Então, imagine aqui temos dois primos, P e Q. Cada um pode pensar nisso como como 1000 dígitos. E você provavelmente sabe que a multiplicação de dois mil dígitos é bastante fácil. Mas se eu apenas dar-lhe o seu produto, descobrir a sua fatoração em números primos é realmente muito difícil. E, de fato, nós vamos usar o fato que o factoring é difícil construir encriptação com chave pública no segundo semestre do curso. Ok, então Alice acontece de ter este número N, e ela também sabe que a fatoração de N. Agora Bob só tem o número N. Ele na verdade não sei a fatoração. Agora, o fato de mágico sobre a prova de conhecimento nulo do conhecimento, é que Alice pode provar a Bob que ela sabe que a fatoração de N. Sim, você pode realmente dar esta prova para Bob, que Bob pode verificar, e tornar-se convencido de que Alice sabe a fatoração de N, no entanto Bob aprende nada. Sobre os fatores P e Q, e isso é demonstrável. Bob descobre absolutamente nada sobre o fatores P e Q. E a declaração é realmente muito, muito geral. Isto é não apenas para provar a fatoração de N. Na verdade, quase qualquer quebra-cabeça que você quer provar que você sabe a resposta, você pode provar que é o seu conhecimento. Então, se você tem um jogo de palavras cruzadas que você resolveu. Bem, talvez as palavras cruzadas não é o melhor exemplo. Mas se você tem como um puzzle Sudoku, por exemplo, que você quer para provar que você resolveu, você pode provar a Bob em uma maneira que Bob iria aprender nada sobre a solução, e ainda Bob estaria convencido de que você realmente ter uma solução para este enigma. Okay. Portanto, estas são o tipo de aplicações mágicas. E assim, a última coisa que eu quero dizer é que a criptografia moderna é muito ciência rigorosa. E, de fato, todo conceito que vamos descrever é vai seguir três passos muito rigorosos, ok, e vamos ver estas três etapas novo e de novo e de novo assim que eu quero explicar o que são. Então a primeira coisa vamos fazer quando introduzimos uma nova primitiva como uma assinatura digital é vamos especificar exatamente o que o modelo de ameaça é. Ou seja, o que pode um atacante fazer para atacar uma assinatura digital e qual é o seu objetivo na formação assinaturas? Ok, então vamos definir exatamente o que isso significa para uma assinatura por exemplo, para ser falsificável. Falsificáveis. Ok, e eu estou dando digitais assinaturas apenas como um exemplo. Para cada primitiva descrevemos nós vamos definir precisamente o que o modelo de ameaça é. Então, vamos propor uma construção e depois vamos dar uma prova de que qualquer atacante que é capaz de atacar o construção sob este modelo de ameaça. Que atacante pode também ser usado para resolver alguns problema subjacente rígido. E, como resultado, se o problema realmente é rígido, que realmente prova que nenhum atacante pode quebrar a construção sob o modelo de ameaça. Ok. Mas estes três passos são realmente muito importante. No caso de assinaturas, vamos definir o que significa para uma assinatura para ser, à prova de falsificação, então nós dar uma construção, e, em seguida, por exemplo, vamos dizer que qualquer um que pode quebrar o nosso construção pode então ser usado para dizer inteiros de factores, que se crê ser um problema difícil. Ok, então vamos seguir estes três passos por toda parte, e então você vai ver como isso realmente acontece. Ok, então este é o fim do segmento. E então, o próximo segmento nós vamos falar um pouco sobre a história de criptografia.