O que é criptografia? (15 min)

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.