Neste segmento, nós vamos olhar para o protocolo Diffie-Hellman, que é nosso
mecanismo primeira troca prático chave. Então deixe-me lembrá-lo das configurações. Nosso
amigos aqui, Alice e Bob, nunca se encontraram e ainda eles querem uma troca compartilhada
chave secreta que eles podem então usar para comunicar de forma segura com o outro.
Nesse segmento e no próximo, estamos só vai estar a olhar para escutas
segurança. Em outras palavras, estamos preocupados apenas com os bisbilhoteiros. Os atacantes são
na verdade, não permitiu a mexer com os dados na rede. Eles não estão autorizados a
injetar pacotes. Eles não estão autorizados a mudar os pacotes de forma alguma. Tudo o que fazem é
apenas para espionar o tráfego. E no final do protocolo, a troca da chave
protocolo nossos amigos Alice e Bob deve ter uma chave secreta compartilhada, mas o atacante
ou seja, o intruso não tem idéia do que essa chave que vai ser. No anterior
segmento olhamos para um segmento-chave chamados puzzles Merkle. Isso é apenas usando bloco
cifras ou funções de hash. E mostrei-lhe que há que, basicamente, o atacante
tem uma diferença de quadrática em comparação com os participantes. Em outras palavras, se o
participantes passou um tempo proporcional a N o atacante pode quebrar o protocolo em
tempo proporcional a N quadrado. E, como resultado desse protocolo é inseguro para ser
considerado prático. Neste segmento nós vamos perguntar se podemos fazer o
mesma coisa, mas agora gostaríamos de alcançar uma lacuna entre o exponencial do atacante
trabalho acabou no trabalho do participante. Em outras palavras, Alice e Bob pode fazer
trabalho proporcional a N, mas para quebrar o protocolo que o atacante vai ter que fazer
trabalho proporcional a alguma exponencial em N. Então agora há uma lacuna exponencial
entre o trabalho participantes eo trabalho do atacante. Então, como eu disse no
segmento anterior não podemos alcançar esta lacuna exponencial a partir de cifras do blog como AES
ou SHA-256. Temos que usar os problemas difíceis que têm mais estrutura do que apenas aqueles
primitivas simétricas. E assim, em vez o que vamos fazer é usar um pouco de álgebra.
Nesse segmento eu vou descrever o protocolo Diffie-Hellman muito
concreta e um pouco informal. Quando nós vamos voltar a Diffie-Hellman na próxima semana
e nós vamos descrever o protocolo de forma mais abstrata e nós vamos fazer um mais muito
análise de segurança rigoroso do presente protocolo. Ok, então como é Diffie-Hellman
trabalho? O que vamos fazer é, em primeiro lugar, nós vamos corrigir alguns principal grande
que eu vou chamar p. Na verdade p eu costumo usar para designar primos. E você
deve estar pensando de primos realmente gigantescas. Como, primos que são compostas de
600 dígitos são assim. E apenas para aqueles de vocês que gostam de pensar em binário, a 600
primeiro dígito corresponde aproximadamente a cerca de 2000 bits. Então, basta escrever o primeiro
leva cerca de dois bits quilo de dados. E então nós estamos também vai corrigir um inteiro g
que acontece a viver na faixa de um a p. Assim, estes valores p e g são parâmetros
do protocolo Diffie-Hellman. Eles são escolhidos uma vez e eles estão fixados para sempre. Agora
protocolo funciona da seguinte forma. Então aqui está o nosso amigos Alice e Bob. Então, o que Alice
vai fazer é ela vai começa por escolher um número aleatório um na faixa de 1 a p-1
E então ela vai calcular o g número à potência de um modulo p.
Ok, então ela calcula este exponention, e reduz o resultado modular o primo p.
E nós estamos realmente indo para ver como calcular isso de forma eficiente o módulo seguinte,
para agora, apenas acredite que este cálculo pode ser feito de forma eficiente.
Agora, vamos chamá-capital de um resultado deste valor. Então, o que Alice vai fazer é que ela vai
enviar maiúsculo sobre a Bob. Agora Bob vai fazer a mesma coisa. Ele vai
escolher um número aleatório b na gama de 1 a p-1. Ele vai calcular g para
módulo de b p e vamos chamar esse número B e vai para enviar esta
B número sobre para Alice. Então, Alice envia para Bob A. Bob envia B. Para Alice. E agora
eles afirmam que podem gerar uma chave secreta compartilhada. Então, o que é uma chave secreta compartilhada?
Bem, ele é definido como. Vamos chamá-lo K_AB. E é basicamente definida como a
g valor para a energia de um b vezes. Agora, a observação surpreendente de Diffie-Hellman teve
em 1976 é que, de facto, ambas as partes podem calcular este valor para o g ab.
Então vamos ver, Alice pode calcular este valor, porque ela pode levá-la B valor que ela
recebeu de Bob. Ela pode tomar este valor B, aumentá-lo para o poder de um e, vamos
ver, o que ela vai conseguir é g a b para o poder do b. E pelas regras do
exponenciação, g para o poder de b para o poder de a é igual a G para o ab. Prumo
despeja, pode fazer algo semelhante, por isso seu objetivo é calcular g para o um a b,
que por sua vez, é g ao ab, então Alice e Bob terá computadorizada K_AB, e
deixe-me perguntar, como é que Bob realmente calcular esta quantidade g para a ab?
Bem por isso tudo que ele faz é que ele leva o valor de que ele recebeu de Alice e ele levanta-lo para
seu b próprio segredo e que lhe dá o g secreta compartilhada para o ab. Assim você pode ver
agora que ambas as partes, embora aparentemente calculado valores diferentes. Em
fato de que ambos acabam com o mesmo valor ou seja, g ab módulo p. Devo mencionar por
maneira que Martie Hellman e Diffiie peruca veio com este protocolo de volta
1976. Martie Hellman foi um professor aqui na Universidade de Stanford e Diffie peruca era o seu
estudante de graduação. Eles vieram com este protocolo e este protocolo realmente mudou
mundo. Em que introduziu nesta nova era em criptografia. Onde está agora não é apenas
sobre o desenvolvimento de cifras de bloco mas na verdade é sobre o projeto algébrica
protocolos que têm imóveis como o que vemos aqui. Então você percebe que o que
faz este protocolo funciona é basicamente propriedades da exponenciação. Ou seja, que,
g para o b para a potência de um é o mesmo que para o g uma à potência de b, bem?
Estes são apenas propriedades de exponenciações. Agora, quando eu descrever um
protocolo como o que acabei de mostrar. A verdadeira questão que deve estar no seu
mente não é por isso que o protocolo funciona. Em outras palavras, é muito fácil de verificar
que, de fato, Alice e Bob acabar com a mesma chave secreta. Quanto maior
questão é porque é que este protocolo seguro? Em outras palavras, por que é que um
eavesdropper não consigo descobrir a mesma chave compartilhada devido à AB que tanto Alice
e Bob calculado por eles próprios? Então vamos analisar isso um pouco, então, como eu
disse, vamos fazer um mais muito na análise aprofundada na próxima semana. Mas, vamos, para já,
apenas ver intuitivamente por isso que este protocolo vai ser seguro. Bem, o que faz o
eavesdropper ver? Bem, ele vê o primo eo gerador. Estes são apenas fixada
para sempre e todo mundo sabe quem eles são. Ele também vê o valor que Alice enviou para
Bob, ou seja, esta A. capital e vê o valor que Bob enviado para Alice, a saber
este capital de B. E a pergunta é, pode, pode a eavesdropper calcular g para o
ab dado apenas esses quatro valores? Então, mais genericamente, o que podemos fazer é que podemos definir
esta função Diffie-Hellman. Então, vamos dizer que a função Diffie-Hellman é definido
com base em alguma g valor. E a pergunta é dada g para a, e g a b. Você pode
computação g para a ab? E o que estamos pedindo é como é que é difícil calcular essa
módulo de função durante muito grande p primo. Lembre-se de p era algo como 600 dígitos.
Então, a verdadeira questão que precisamos responder é o quão difícil é este, é este Diffie-Hellman
função? Então deixe-me mostrar-lhe o que sabe sobre isso. Assim, suponha que o principal acontece
para ser n bits de comprimento. Ok, então no nosso caso dizem que n é de 2.000 bits. Acontece que o melhor
algoritmo conhecido para calcular a função de Diffie-Hellman. É realmente um
mais algoritmo geral que calcula a função de log discreto, que nós vamos
falar na próxima semana. Mas, por enquanto, vamos apenas dizer que este algoritmo calcula um
Diffie-Hellman função. O algoritmo é chamado um peneiro campo geral número. Eu sou
não vou descrever como funciona, mas se você gostaria de saber como ele funciona, deixe-me
sabe, e que pode ser um dos tópicos especiais que cobrem no final do
curso. Mas o interessante é que ele está correndo o tempo é exponencial
aproximadamente a raiz cúbica de n. Em outras palavras, o tempo de execução é aproximadamente e para
o poder de o de raiz cúbica de n. Então, na verdade a expressão exata para a execução
hora, desse algoritmo é muito mais complicado do que isso. Eu estou deliberadamente
simplificando-o aqui só para obter o tipo de ponto de vista. O ponto que eu quero
enfatizar é que, na verdade, isso não é bem um algoritmo de tempo exponencial.
exponencial seria e à potência de n. Isso às vezes é chamado de sub-exponencial
algoritmo porque o expoente é apenas proporcional à raiz cúbica de n,
em oposição a n lineares. O que isto diz é que mesmo que este problema é bastante
difícil, não é realmente um problema de tempo exponencial. O tempo de execução na
expoente vai ser apenas proporcional à raiz cúbica de n. Então, vamos olhar para alguns
exemplos. Suponha que eu acontecer de estar a olhar para um módulo que passa a ser sobre um
mil bits de comprimento. O que este algoritmo diz é que podemos resolver o
problema Diffie-Hellman no tempo, que é aproximadamente e para a raiz qube de 1.024.
Agora, isso não é realmente correto, na verdade, existem mais constantes no expoente.
Mas, novamente, apenas para começar, o ponto de vista, podemos dizer que o tempo de execução seria
cerca e à raiz qube de 1.024, o que é realmente muito pequena, cerca de e para o 10.
Portanto, o exemplo simples mostra que se você tiver um algoritmo sub-exponencial,
você ver que mesmo se o problema é muito grande, como 1000 bits. Devido à
efeito raiz cúbica o expoente na verdade não é tão grande como um todo. Agora, para ser honesto, eu sou
realmente mentindo aqui. Peneira campo Geral Número realmente tem muitos outros
constantes dos expoentes assim, de facto, isso não vai ser 10 em tudo. É
realmente vai ser algo como 80. Por causa de várias constantes do
expoentes. Mas mesmo assim, mas você vê o problema é muito mais difícil do que dizer de 2 a
1000 a. Apesar de descrever leva 1.000 bits, resolução de não ter tempo
para a 1.000. Então aqui eu rolar a tabela que tipo de mostra-lhe o áspero
dificuldade de quebrar o protocolo de Diffie-Hellman em comparação com o
dificuldade de quebrar uma cifra com um número apropriado de bits. Por exemplo,
se o seu cifra tem 80 teclas de bits. Isso seria mais ou menos comparável ao uso de 1.000 bit
módulos. Em outras palavras, quebrando uma cifra com 80 teclas de bit demora cerca de 2 a 80
, o que significa que a quebra se você tiver Diffie-Hellman função com 1.000
módulo terá pouco tempo de 2 à 80.
Se o seu cifra usa chaves de 128 bits como AES, você deve estar realmente usando um módulo bit 3.000,
, embora ninguém realmente faz isso. Na realidade, as pessoas usariam 2.000 módulo bit. E
, em seguida, se a sua chave é muito grande, como se estivéssemos usando uma chave AES de 256 bits, em seguida,
fato de seu módulo precisa ser muito, muito grande. Novamente, você, você pode realmente ver o
efeito raiz cúbica aqui. Nós duplicou o tamanho da nossa chave e por causa da raiz cubo
efeito, o que isso significa é que temos que aumentar o tamanho, do nosso módulo por um
fator de dois cubos, ou seja, um fator de oito, que é onde esta 15.000 vem.
a partir de. E mais uma vez devo mencionar que não há exatamente um fator de oito por causa de
as constantes extra no expoente. Portanto, este é um belo quadro que mostra que
, se você está indo estar usando Diffie-Hellman para troca, uma chave de sessão. E que a sessão
chave vai ser utilizado para uma codificação de bloco com um tamanho de chave determinado, esta tabela mostra
qual o tamanho modular você precisa usar para que a segurança da troca de chaves
protocolo é comparável com a segurança da cifra de bloco você vai estar usando depois.
Agora, esta última linha deve ser realmente preocupante para você. Eu deveria dizer
você que trabalha com esse módulo de um grande é muito problemática. Esta é realmente
vai ser bastante lenta, e então a questão é se existe algo melhor que
podemos fazer? E acontece que há. Na verdade, a maneira que eu descrever o Diffie-Hellman
função é que eu descrevê-la com a forma como Diffie e Hellman descrito em 1976
módulo usando aritmética dos números primos. O problema com números primos aritmética modular é
que a função de Diffie-Hellman é difícil de calcular, mas não é tão duro como você
como. Não há este efeito raiz cúbica que o torna um pouco mais fácil do que o que você
realmente gosto. E então a questão é que podemos executar o protocolo Diffie-Hellman em outro
configurações. E acontece que a resposta é sim. Na verdade, podemos traduzir literalmente
o protocolo de Diffie-Hellman a partir de um modelo de aritmética de números primos para um diferente
tipo de objeto algébrico e resolver o problema Diffie-Hellman em que outro
objeto algébrico é muito, muito mais difícil. Este outro objeto algébrico é o que é
chamado uma curva elíptica. E como eu disse, o cálculo da função de Diffie-Hellman em
essas curvas elípticas é muito mais difícil do que calcular os números primos Diffie-Hellman modulo.
Porque o problema é muito mais difícil, agora podemos usar objetos muito menores em
particular, você sabe que estaria usando números primos que são apenas uma de 160 bits ou 80 bits ou chaves
apenas 512 bits para 256 bits chaves. Então, porque estes módulo não crescem como
rápido em curvas elípticas, há geralmente uma transição lenta de distância usando o módulo
aritmética, ao uso de curvas elípticas. Eu não vou descrever curvas elípticas
agora para você, mas se isso é algo que você gostaria de aprender sobre o que posso
fazer isso na última semana do curso, quando discutimos mais avançado
tópicos. Mas na verdade, quando voltamos para Diffie-Hellman na próxima semana eu vou descrevê-lo
mais abstrata, para que isso realmente não importa qual você usa estrutura algébrica
se você usar o modelo aritmética dos números primos, ou se você usar uma curva elíptica que
pode meio abstrato questão que todo fora e use o conceito de Diffie-Hellman para um
troca de chaves e outras coisas também. E como eu disse, vamos ver que mais
abstratamente na próxima semana. Então, como de costume, eu quero mostrar que este protocolo bonita que eu
apenas mostrei, o protocolo Diffie-Hellman, é como é, na verdade é completamente inseguro
contra um ataque ativo. Ou seja, é completamente inseguro contra o que é chamado
o homem no meio ataque. Precisamos fazer algo mais do que este protocolo para
fazer é segura contra o homem no meio. E mais uma vez vamos voltar a Diffie
Hellman e torná-la segura contra o homem no meio da semana seguinte. Okay. Então vamos ver
porque o protocolo que eu mostrei é inseguro contra ataques ativos. Bem
suponha que temos esse homem no meio que está tentando espionar o
conversa entre Alice e Bob. Bem assim, o protocolo começa com Alice enviando
g ao longo de um para Bob. Bem, então o homem no meio é que vai interceptar e
ele vai levar a mensagem de que Alice enviou e ele vai substituí-lo com a sua
própria mensagem. Então, ele é chamado a ', e vamos escrever que é g a um ".
Ok? Então o homem no meio escolhe o seu "um próprio eo que ele envia para Bob é
realmente g para a 'a. Agora pobre Bob não sabe que o homem no meio
realmente fez alguma coisa para esse tráfego, tudo o que ele vê é que ele tem o valor de A '. Como
até onde ele sabe, que o valor veio de Alice. Então, o que é que ele vai fazer em resposta?
Bem, ele vai mandar de volta o seu valor B para fora que é g a b volta para Alice. Bem
novamente o homem no meio vai interceptar este B. Ele vai gerar o seu
b própria "e que ele realmente envia de volta para Alice é B", que é g a b '.
Ok, agora o que acontece? Bem Alice vai calcular a sua parte do
chave secreta e ela vai ficar g para o ab '. Bob vai calcular a sua parte
chave secreta e ele vai ficar g para os tempos de um 'b. Ok, estes agora você
aviso estas não são as mesmas teclas. No homem no meio, porque ele sabe tanto "A
e B ", ele pode calcular tanto para o g ab 'e g a ba'. Sim, é
não é difícil de ver o homem no meio sabe os dois valores. E, como resultado, agora ele
pode basicamente jogar este homem no meio e quando Alice envia uma mensagem criptografada
de Bob o homem no meio pode simplesmente decifrar esta mensagem, porque ele sabe o
chave secreta que Alice mensagem criptografada com, re-criptografá-la utilizando a chave de Bob. E
, em seguida, enviar a mensagem sobre sobre a Bob. E desta forma Alice enviou a mensagem, Bob
recebido a mensagem. Bob acredita que a mensagem é segura. Mas, de facto, que
mensagem foi enviada através do homem no meio. O homem no meio descriptografados
-lo, re-codificado-lo para Bob. Ao mesmo tempo que era capaz de completamente lê-lo,
modificá-lo, se ele quer, e assim por diante. Assim, o protocolo torna-se completamente inseguro
dar nd homem no meio. E assim como eu disse nós vamos ter para melhorar a
protocolo de alguma forma para se defender contra os homens no meio, mas acontece que é
na verdade não tão difícil de melhorar e impedir o homem no meio ataques.
E nós vamos voltar a isso e ver que em uma semana ou duas. O último acho que eu quero
fazer é mostrar-lhe uma propriedade interessante do protocolo Diffie-Hellman. Na verdade, eu
quero mostrar a você que este protocolo pode ser visto como um protocolo não-interativo. Assim,
o que quero dizer com isso? Então, imagine que temos um monte de usuários, você sabe, milhões
de usuários. Vamos chamá-los de Alice, Bob, Charlie, David e assim por diante e assim por diante.
Cada um deles vai escolher um valor aleatório, segredo, e, em seguida, em seu
perfis do Facebook, eles vão escrever, sua contribuição para o
Diffie-Hellman protocolo. Tudo bem, então todo mundo só escreve você sabe g para
a um, g para o b, g para o C e assim por diante. Agora a coisa interessante sobre isso é,
se dizem Alice e Charlie quer estabelecer uma chave compartilhada eles não precisam se comunicar
de todo. Basicamente Alice iria ler e perfil público de Charlie. Charlie iria
e ler o perfil de Alice público. E agora, boom, têm imediatamente uma chave secreta.
Ou seja, agora, Alice sabe, g a c e a. Charlie sabe g à uma e с. E como
um resultado, ambos podem calcular п à AC. Então, em certo sentido, uma vez que eles
postou suas contribuições para o protocolo Diffie-Hellman para seu público
os outros em tudo para criar uma chave compartilhada.
têm imediatamente uma chave compartilhada e agora eles podem começar a se comunicar
de forma segura através do Facebook ou não um com o outro. E notem que isto é verdade para
qualquer usuário do Facebook. Assim, logo que li o perfil público de alguém, eu imediatamente
têm uma chave compartilhada com eles, sem nunca se comunicar com eles. Esta propriedade é
às vezes chamado de uma propriedade não-interativo do Diffie-Hellman. Então agora, vamos
me mostrar-lhe um problema em aberto. E este é um problema em aberto que tem sido aberto para as idades
e eras e eras. Por isso, seria muito legal se um de vocês pode realmente resolvê-lo. O
questão é, podemos fazer isso por mais de duas partes? Em outras palavras, dizer que temos
quatro partes. Todos eles postam seus valores para seus perfis do Facebook. E agora
gostaríamos de fazê-lo que apenas lendo perfis no Facebook, todos eles podem configurar
palavras, é Alice, que ela vai, ela vai fazer é ela só vai
ler os perfis do público, os três amigos, Bob, Charlie e David. E
ela já pode calcular a chave compartilhada com eles. E da mesma forma David está apenas indo
ler o perfil público de Charlie. Bob e Alice. E já que ele tem uma chave compartilhada
com todos os quatro deles. Ok, então a questão é se podemos tipo de configuração
não-interativamente estes, estas chaves compartilhadas para grupos que são maiores do que apenas dois
pessoas. Então, como eu disse, para n igual a dois, este é apenas um protocolo Diffie-Hellman. Em
outras palavras, se apenas dois partidos querem criar uma chave compartilhada sem comunicar
um com o outro, isso é apenas Diffie-Hellman. Acontece que, para N igual a
três, nós também sabemos como fazê-lo, há um protocolo conhecido, é chamado de protocolo devido
de Joux. Ela já usa matemática muito, muito chique, muito mais complicado
matemática do que aquilo que acabei de mostrar. E para N igual a quatro, ou cinco, ou
nada acima deste, acima de quatro, este problema é completamente aberta. Quase o
caso em que quatro pessoas postar algo para os perfis públicos e então todos
pessoa lê o perfil público e eles têm uma chave comum compartilhado, isto é
algo que não sei como fazer, mesmo para quatro pessoas. E este é um problema que é
sido aberto por eras e eras, é um tipo de problema legal pensar e assim ver se
você pode resolvê-lo, se quiser, é a fama instantânea no mundo crypto. Ok, então
Vou parar por aqui, e vamos continuar com um outro mecanismo de troca de chaves no próximo segmento.