O protocolo Diffie-Hellman (19 min)

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.