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.