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.