No último segmento, vimos que a Sistema de criptografia de chave pública ElGamal é escolhida texto cifrado seguro sob um pouco suposição estranha. Neste segmento, estamos vai olhar para as variantes de ElGamal que tem um texto cifrado muito melhor escolhido análise de segurança. Agora, devo dizer que na última década, tem havido uma tonelada de pesquisas sobre a construção de chave pública criptografias que são escolhidos texto cifrado seguro. Eu realmente debatido por algum tempo sobre a melhor forma de apresentar este aqui. E finalmente, decidi tipo de mostrar um levantamento dos principais resultados do último décadas, especificamente como eles se aplicam ao Sistema ElGamal. E, em seguida, no final da o módulo, sugiro uma série de documentos que você pode olhar para outras leituras. Então deixe-me começar por lembrar que a forma como o Sistema de criptografia ElGamal funciona. Tenho certeza de que agora você se lembrar de como tudo funciona ElGamal, mas apenas para ser seguro, deixe-me lembrá-lo que a geração de chave no ElGamal escolhe um gerador aleatório, um expoente aleatório de ZN e, em seguida, a chave pública é simplesmente o gerador de g e este elemento ao a, ao passo que a chave secreta é simplesmente o logaritmo discreto de h base de g. Este valor A. Agora, a nossa forma de criptografar é que escolher um aleatório expoente B de ZN. Calculamos o hash G para a B e H para a B. E eu vou Lembramos que H para o B é o Diffie Hellman segredo, G para a AB. E então nós realmente criptografar uma mensagem usando um sistema de criptografia simétrica com a chave K que é derivada da função hash. E finalmente, a saída de texto cifrado é a G a B, e o texto cifrado simétrico. O nossa forma de descriptografar é que você sabe, como vimos antes, basicamente, através de hash U ea Diffie Hellman segredos, descriptografar o sistema simétrico, e produzir o mensagem M. Agora, no último segmento dissemos ElGamal que é escolhido cifrado seguro sob este interativo engraçado Diffie-Hellman suposição. Eu não vou lembrá-lo que o pressuposto é aqui, mas eu também vou dizer que este tipo teorema de suscita duas muito questões naturais. A primeira pergunta é podemos provar CCA segurança de ElGamal apenas com base no padrão Pressuposto de Diffie-Hellman computacional, a saber, a G para A, G para o B, não pode calcular G para a AB. Podemos provar escolhido-texto cifrado de segurança apenas com base em isso? E a verdade é que existem dois maneiras de fazer isso. A primeira opção é usar um grupo onde o Diffie computacional Pressuposto de Hellman é difícil. Mas é comprovadamente equivalente ao interativo Diffie Hellman suposição. E acontece fora não é realmente difícil de construção de tais grupos. Estes grupos são chamados grupos bilineares. E de tal grupos, sabemos que o sistema é ElGamal texto cifrado escolhido seguro, estritamente baseadas sob a Computational Diffie Hellman suposição, pelo menos no oráculo aleatório modelo. Eu vou te dizer que estes bi-linear grupos são realmente construídos a partir de muito especiais curvas elípticas. Portanto, há um pouco mais estrutura algébrica que permite-nos para provar esta equivalência de IDH e CDH. Mas, em geral, quem sabe, talvez não quer usar grupos curvas elípticas, talvez você quer usar estrela ZP por algum motivo. Então é uma pergunta muito natural perguntar. Podemos mudar o sistema de tal forma que ElGamal cifrado escolhido segurança de ElGamal agora pode ser provado, directamente com base no CDH, para qualquer grupo CDH onde é difícil? [Agora com isso??] Assumindo qualquer estrutura adicional sobre o grupo, E acontece que a resposta é sim. E há um tipo de uma construção elegante chamado ElGamal gêmeo, então deixe-me mostrar-lhe como gêmeo obras ElGamal. É uma forma muito simples variação de ElGamal que faz o sequência. Mais uma vez, na geração de chaves, nós escolher um gerador aleatório. Mas, desta vez, vamos escolher dois expoentes, A1 e A2 como a chave secreta. Portanto, a chave é segredo vai consistir desses dois expoentes, A1 e A2. Conhece a chave pública do curso se vai consistir em nosso gerador. E então nós vamos liberar G para a A1 e G para a A2. Então lembre-se que em regular ElGamal que a chave pública é simplesmente g para o A e é isso. Aqui temos dois expoentes A1 e A2 e, portanto, nós, nós solte G para a A1 e G para a A2. Agora, a nossa forma de criptografar, você vai notar a chave pública é aqui um elemento de mais de ElGamal regular. A forma como criptografar usando esta chave pública é realmente muito semelhante para ElGamal regular. Nós escolhemos um B aleatória, e agora o que vamos hash é, na verdade, não G apenas para a B e H1 para o B, mas, de facto, para o G B, H1 para a B, e H2 para o B. Ok então nós basicamente hash três elementos em vez de dois elementos e então nós basicamente criptografar a mensagem usando a chave de criptografia simétrica derivada e como de costume, a saída para o g b e c como o nosso último texto cifrado. Como podemos decifrar? Bem, agora a chave secreta consiste em esses dois expoentes, A1 e A2. E a texto cifrado consiste em U, e a simétrica texto cifrado C. Então deixe-me perguntar-lhe um quebra-cabeça, e veja se você pode descobrir como obter a chave de criptografia simétrica K, dado apenas a chave secreta eo valor U. Então, é uma espécie de quebra-cabeça bonito e eu espero que todos trabalhados, a solução que é basicamente o que podemos fazer é que U pode levar à potência de A1, e que é G basicamente à A1 B e U para a A2 que é G para a A2 B. E que, basicamente, nos dá exatamente os mesmos valores, como a H1 o B e H2 para a B. Portanto, a forma como este decryptor chega à mesma simétrica chave que o codificador fez. Então, ele decifra o texto cifrado com o sistema simétrico e, finalmente, gera a mensagem M. Então você Note que isto é uma modificação muito simples para ElGamal regular. Tudo o que fazemos é ficar mais um elemento para a chave pública. Quando nós fazemos o hash, que um hash mais elemento, em vez de apenas dois elementos. Nós hash de três elementos. E da mesma forma, nós descriptografia fazer fazendo, e nada mais mudanças. O texto cifrado é o mesmo comprimento como antes, e é isso, agora o coisa surpreendente é que esta simples modificação permite-nos agora provar escolhido segurança texto cifrado diretamente com base em padrão computacional Diffie-Hellman suposição, ok? Ainda vamos precisa assumir que temos uma simétrica sistema de criptografia que nos fornece autenticada criptografia e que o hash função que estamos usando é um hash ideal função no que chamamos de um oráculo aleatório Mas, no entanto, dado que, o que pudermos provar a segurança da cifra escolhida texto estritamente baseado numa Computational Diffie-Hellman suposição. Então agora o que é o custo disso? Claro, se você pensar sobre isso, durante criptografia e descriptografia, criptografia tem fazer mais uma exponenciação, eo decodificação tem que fazer mais uma exponenciação. Assim, o codificador faz agora exponenciações três em vez de dois, e o decoder faz duas exponenciações em vez de um. Então a questão é agora, agora é uma questão filosófica. É este o esforço extra vale a pena? Então você faz um trabalho mais durante a criptografia e descriptografia. E sua chave pública é um pouco maior, mas que realmente não importa. O trabalho durante a criptografia e descriptografia é mais significativo. E, como resultado você começa cifrado escolhido segurança baseado em espécie de uma hipótese mais natural, ou seja, Computational Diffie-Hellman em oposição a estes interativo de aparência estranha Diffie-Hellman suposição. Mas vale a pena isso? Tipo de questão é que existem grupos onde CDH detém IDH, mas não segurar? Se houvesse tais grupos, então seria definitivamente vale a pena, porque esses grupos, o ElGamal duplo seria seguro, mas o ElGamal regular não CCA ser seguro. Mas, infelizmente, nós não saber se existe qualquer desses grupos e em fato de, tanto quanto sabemos, é certamente possível que qualquer grupo que detém CDH, IDH também tem. Portanto, a resposta é, realmente, não sabemos se o custo extra é vale a pena ou não, mas, em seguida, no entanto, é um resultado bonito que mostra que se você quiser para atingir cifrado escolhido segurança diretamente da CDH, você pode fazer TI sem muitas mudanças para o ElGamal sistema. A próxima pergunta é se nós pode se livrar deste pressuposto de que o função hash é uma função ideal de hash principalmente que é um oráculo aleatório. E esta é realmente um grande tema. Há um monte de trabalhar nesta área, sobre como construir eficientes sistemas de criptografia de chave pública que são escolhidos cifrado seguro sem oráculos aleatórios. Esta é uma área muito ativa de pesquisa, como eu disse na última década e ainda mais tempo. E eu vou falar que, como isto aplica-se a ElGamal, eles são, basicamente, novamente duas famílias de construções. O primeira construção é uma construção que usa esses grupos especiais chamados estes grupos bilineares que acabei de mencionar antes. Acontece que a estrutura extra desses grupos bilineares permite construir muito eficiente escolhido cifrado sistemas seguros sem referindo-se ao acaso oráculos e como eu disse no final do módulo, eu apontar para uma série de documentos que explicar como fazer isso. Este é um grande construção interessante. Mas vai demorar me várias horas para o tipo de explicar como obras. A outra alternativa é efectivamente usar grupos, onde uma forte hipótese denominada decisão suposição Diffie-Hellman mantém. Mais uma vez, eu não vou definir esta suposição aqui. Vou apenas dizer-lhe que esta hipótese, na verdade, tem em subgrupos de ZP estrela, em particular se olhar para a forma principal de um subgrupo de ZP estrela. A decisão Diffie-Hellman suposição parece ter nesses grupos e, em seguida, os grupos que podemos realmente construir uma variante de ElGamal, chamado sistema Cramer Shoup que é escolhido cifrado seguro ea decisão Diffie-Hellman suposição sem aleatório oráculos. Mais uma vez, este é um belo belo resultado, mas novamente seria necessário um par de horas para explicar e por isso não tenho vou fazer isso aqui. Este é provavelmente um essas coisas que eu vou deixar para tanto os tópicos avançados ou para fazer uma curso avançado de modo que nós vamos fazê-lo em um depois do tempo. Mas, novamente eu aponta para um papel no final do módulo apenas um caso em que você quiser ler mais sobre isso. Então aqui vai uma lista de documentos que proporciona uma leitura mais material. Então se você quer ler sobre Suposições Diffie Hellman, eu acho que escreveu um artigo sobre isso há muito tempo, que fala sobre várias suposições relacionado, a Diffie Hellman. E em particular, estudos Diffie decisão Suposição Hellman. E se você quer aprender sobre como construir escolhida texto cifrado sistema seguro de decisão Diffie-Hellman e premissas gostar. Há um muito papel bonito por volta Kramer e Shoup a partir de 2002 que mostra como fazê-lo. Isto é mais uma vez um papel muito bem recomendado. Se você quer aprender a construir escolhido cifrado segurança destas grupos bilineares, em seguida, o papel é para ler a um, aqui citados, que, na verdade, usa um mecanismo geral chamada Identidade Baseado Criptografia que muito surpreendentemente, Acontece que realmente nos dá escolhido cifrado segurança quase de graça. Assim, uma vez que construímos baseado em identidade criptografia escolhido cifrado segurança cai imediatamente. E isso é abordado neste papel que eu, que eu descrevê-la. O Dupla construção Diffie-Hellman e sua prova é descrito neste trabalho que eu referência aqui E, finalmente, se você meio que quero ver um papel muito recente. Que dá um quadro muito geral para construção de sistemas de texto cifrado, escolhidos segura, utilizando o que é chamado de hash que extraíveis provas é mais uma vez um papel bonito por Hoeteck Wee, que foi recentemente publicado. Eu definitivamente recomendo a leitura de tudo, tudo tem idéias muito, muito elegantes eles. Eu gostaria de poderia cobrir todos eles no básico claro, mas eu vou ter que deixar algumas de estes para o curso mais avançado ou talvez os tópicos mais avançados no final do curso. Ok, então eu vou parar aqui e no segmento seguinte, eu vou amarrar Criptografia RSA e ElGamal em conjunto para que você veja como o tipo dois de acompanhamento de um princípio mais geral.