WEBVTT 00:00:00.000 --> 00:00:03.574 No último segmento, vimos que a Sistema de criptografia de chave pública ElGamal é 00:00:03.574 --> 00:00:07.525 escolhida texto cifrado seguro sob um pouco suposição estranha. Neste segmento, estamos 00:00:07.525 --> 00:00:11.146 vai olhar para as variantes de ElGamal que tem um texto cifrado muito melhor escolhido 00:00:11.146 --> 00:00:14.909 análise de segurança. Agora, devo dizer que na última década, tem havido uma tonelada 00:00:14.909 --> 00:00:18.766 de pesquisas sobre a construção de chave pública criptografias que são escolhidos texto cifrado 00:00:18.766 --> 00:00:22.387 seguro. Eu realmente debatido por algum tempo sobre a melhor forma de apresentar este aqui. E 00:00:22.387 --> 00:00:26.197 finalmente, decidi tipo de mostrar um levantamento dos principais resultados do último 00:00:26.197 --> 00:00:29.960 décadas, especificamente como eles se aplicam ao Sistema ElGamal. E, em seguida, no final da 00:00:29.960 --> 00:00:33.770 o módulo, sugiro uma série de documentos que você pode olhar para outras leituras. 00:00:33.770 --> 00:00:38.332 Então deixe-me começar por lembrar que a forma como o Sistema de criptografia ElGamal funciona. Tenho certeza de que 00:00:38.332 --> 00:00:42.783 agora você se lembrar de como tudo funciona ElGamal, mas apenas para ser seguro, deixe-me lembrá-lo 00:00:42.783 --> 00:00:47.623 que a geração de chave no ElGamal escolhe um gerador aleatório, um expoente aleatório de ZN 00:00:47.623 --> 00:00:51.963 e, em seguida, a chave pública é simplesmente o gerador de g e este elemento ao a, 00:00:51.963 --> 00:00:56.332 ao passo que a chave secreta é simplesmente o logaritmo discreto de h base de g. Este valor A. 00:00:56.332 --> 00:01:01.255 Agora, a nossa forma de criptografar é que escolher um aleatório expoente B de ZN. Calculamos o hash 00:01:01.255 --> 00:01:05.947 G para a B e H para a B. E eu vou Lembramos que H para o B é o Diffie 00:01:05.947 --> 00:01:10.233 Hellman segredo, G para a AB. E então nós realmente criptografar uma mensagem usando um 00:01:10.233 --> 00:01:15.156 sistema de criptografia simétrica com a chave K que é derivada da função hash. E 00:01:15.156 --> 00:01:19.731 finalmente, a saída de texto cifrado é a G a B, e o texto cifrado simétrico. O 00:01:19.731 --> 00:01:24.654 nossa forma de descriptografar é que você sabe, como vimos antes, basicamente, através de hash U ea 00:01:24.654 --> 00:01:28.940 Diffie Hellman segredos, descriptografar o sistema simétrico, e produzir o 00:01:28.940 --> 00:01:33.645 mensagem M. Agora, no último segmento dissemos ElGamal que é escolhido cifrado seguro sob 00:01:33.645 --> 00:01:37.881 este interativo engraçado Diffie-Hellman suposição. Eu não vou lembrá-lo que 00:01:37.881 --> 00:01:42.447 o pressuposto é aqui, mas eu também vou dizer que este tipo teorema de suscita duas muito 00:01:42.447 --> 00:01:46.683 questões naturais. A primeira pergunta é podemos provar CCA segurança de 00:01:46.683 --> 00:01:50.864 ElGamal apenas com base no padrão Pressuposto de Diffie-Hellman computacional, 00:01:50.864 --> 00:01:55.011 a saber, a G para A, G para o B, não pode calcular G para a AB. Podemos provar 00:01:55.011 --> 00:01:59.259 escolhido-texto cifrado de segurança apenas com base em isso? E a verdade é que existem dois 00:01:59.259 --> 00:02:03.454 maneiras de fazer isso. A primeira opção é usar um grupo onde o Diffie computacional 00:02:03.454 --> 00:02:07.306 Pressuposto de Hellman é difícil. Mas é comprovadamente equivalente ao interativo 00:02:07.306 --> 00:02:11.227 Diffie Hellman suposição. E acontece fora não é realmente difícil de 00:02:11.227 --> 00:02:15.147 construção de tais grupos. Estes grupos são chamados grupos bilineares. E de tal 00:02:15.147 --> 00:02:19.544 grupos, sabemos que o sistema é ElGamal texto cifrado escolhido seguro, estritamente baseadas 00:02:19.544 --> 00:02:23.782 sob a Computational Diffie Hellman suposição, pelo menos no oráculo aleatório 00:02:23.782 --> 00:02:28.983 modelo. Eu vou te dizer que estes bi-linear grupos são realmente construídos a partir de muito 00:02:28.983 --> 00:02:33.715 especiais curvas elípticas. Portanto, há um pouco mais estrutura algébrica que permite-nos 00:02:33.715 --> 00:02:38.404 para provar esta equivalência de IDH e CDH. Mas, em geral, quem sabe, talvez não 00:02:38.404 --> 00:02:42.928 quer usar grupos curvas elípticas, talvez você quer usar estrela ZP por algum motivo. 00:02:42.928 --> 00:02:47.817 Então é uma pergunta muito natural perguntar. Podemos mudar o sistema de tal forma que ElGamal 00:02:47.817 --> 00:02:52.828 cifrado escolhido segurança de ElGamal agora pode ser provado, directamente com base no CDH, para qualquer grupo 00:02:52.828 --> 00:02:57.840 CDH onde é difícil? [Agora com isso??] Assumindo qualquer estrutura adicional sobre o grupo, 00:02:57.840 --> 00:03:02.132 E acontece que a resposta é sim. E há um tipo de uma construção elegante 00:03:02.132 --> 00:03:06.696 chamado ElGamal gêmeo, então deixe-me mostrar-lhe como gêmeo obras ElGamal. É uma forma muito simples 00:03:06.696 --> 00:03:10.607 variação de ElGamal que faz o sequência. Mais uma vez, na geração de chaves, nós 00:03:10.607 --> 00:03:14.954 escolher um gerador aleatório. Mas, desta vez, vamos escolher dois expoentes, A1 e 00:03:14.954 --> 00:03:19.409 A2 como a chave secreta. Portanto, a chave é segredo vai consistir desses dois expoentes, A1 00:03:19.409 --> 00:03:23.783 e A2. Conhece a chave pública do curso se vai consistir em nosso gerador. E 00:03:23.783 --> 00:03:28.340 então nós vamos liberar G para a A1 e G para a A2. Então lembre-se que em regular 00:03:28.340 --> 00:03:32.840 ElGamal que a chave pública é simplesmente g para o A e é isso. Aqui temos dois 00:03:32.840 --> 00:03:37.340 expoentes A1 e A2 e, portanto, nós, nós solte G para a A1 e G para a A2. 00:03:37.340 --> 00:03:42.297 Agora, a nossa forma de criptografar, você vai notar a chave pública é aqui um elemento de mais de 00:03:42.297 --> 00:03:47.137 ElGamal regular. A forma como criptografar usando esta chave pública é realmente muito semelhante 00:03:47.137 --> 00:03:51.859 para ElGamal regular. Nós escolhemos um B aleatória, e agora o que vamos hash é, na verdade, não 00:03:51.859 --> 00:03:56.522 G apenas para a B e H1 para o B, mas, de facto, para o G B, H1 para a B, e H2 00:03:56.522 --> 00:04:01.691 para o B. Ok então nós basicamente hash três elementos em vez de dois elementos e 00:04:01.691 --> 00:04:06.642 então nós basicamente criptografar a mensagem usando a chave de criptografia simétrica derivada 00:04:06.642 --> 00:04:11.410 e como de costume, a saída para o g b e c como o nosso último texto cifrado. Como podemos decifrar? 00:04:11.410 --> 00:04:16.027 Bem, agora a chave secreta consiste em esses dois expoentes, A1 e A2. E a 00:04:16.027 --> 00:04:20.584 texto cifrado consiste em U, e a simétrica texto cifrado C. Então deixe-me perguntar-lhe 00:04:20.584 --> 00:04:25.501 um quebra-cabeça, e veja se você pode descobrir como obter a chave de criptografia simétrica 00:04:25.501 --> 00:04:31.934 K, dado apenas a chave secreta eo valor U. Então, é uma espécie de quebra-cabeça bonito e eu 00:04:31.934 --> 00:04:37.250 espero que todos trabalhados, a solução que é basicamente o que podemos fazer é que 00:04:37.250 --> 00:04:42.566 U pode levar à potência de A1, e que é G basicamente à A1 B e U para a A2 00:04:42.566 --> 00:04:48.012 que é G para a A2 B. E que, basicamente, nos dá exatamente os mesmos valores, como a H1 00:04:48.012 --> 00:04:53.069 o B e H2 para a B. Portanto, a forma como este decryptor chega à mesma simétrica 00:04:53.069 --> 00:04:58.515 chave que o codificador fez. Então, ele decifra o texto cifrado com o sistema simétrico 00:04:58.515 --> 00:05:03.389 e, finalmente, gera a mensagem M. Então você Note que isto é uma modificação muito simples 00:05:03.389 --> 00:05:07.802 para ElGamal regular. Tudo o que fazemos é ficar mais um elemento para a chave pública. Quando 00:05:07.802 --> 00:05:11.888 nós fazemos o hash, que um hash mais elemento, em vez de apenas dois elementos. 00:05:11.888 --> 00:05:16.246 Nós hash de três elementos. E da mesma forma, nós descriptografia fazer fazendo, e nada mais 00:05:16.246 --> 00:05:20.491 mudanças. O texto cifrado é o mesmo comprimento como antes, e é isso, agora o 00:05:20.491 --> 00:05:24.647 coisa surpreendente é que esta simples modificação permite-nos agora provar escolhido 00:05:24.647 --> 00:05:28.640 segurança texto cifrado diretamente com base em padrão computacional Diffie-Hellman 00:05:28.640 --> 00:05:32.795 suposição, ok? Ainda vamos precisa assumir que temos uma simétrica 00:05:32.795 --> 00:05:36.897 sistema de criptografia que nos fornece autenticada criptografia e que o hash 00:05:36.897 --> 00:05:41.430 função que estamos usando é um hash ideal função no que chamamos de um oráculo aleatório 00:05:41.430 --> 00:05:45.747 Mas, no entanto, dado que, o que pudermos provar a segurança da cifra escolhida texto estritamente 00:05:45.747 --> 00:05:49.803 baseado numa Computational Diffie-Hellman suposição. Então agora o que é o custo disso? 00:05:49.803 --> 00:05:53.966 Claro, se você pensar sobre isso, durante criptografia e descriptografia, criptografia tem 00:05:53.966 --> 00:05:57.418 fazer mais uma exponenciação, eo decodificação tem que fazer mais uma 00:05:57.418 --> 00:06:01.581 exponenciação. Assim, o codificador faz agora exponenciações três em vez de dois, e 00:06:01.581 --> 00:06:05.490 o decoder faz duas exponenciações em vez de um. Então a questão é agora, 00:06:05.490 --> 00:06:09.965 agora é uma questão filosófica. É este o esforço extra vale a pena? Então você faz um trabalho mais 00:06:09.965 --> 00:06:14.228 durante a criptografia e descriptografia. E sua chave pública é um pouco maior, mas 00:06:14.228 --> 00:06:18.331 que realmente não importa. O trabalho durante a criptografia e descriptografia é mais 00:06:18.331 --> 00:06:22.434 significativo. E, como resultado você começa cifrado escolhido segurança baseado em espécie 00:06:22.434 --> 00:06:26.644 de uma hipótese mais natural, ou seja, Computational Diffie-Hellman em oposição a 00:06:26.644 --> 00:06:30.480 estes interativo de aparência estranha Diffie-Hellman suposição. Mas vale a pena 00:06:30.480 --> 00:06:34.743 isso? Tipo de questão é que existem grupos onde CDH detém IDH, mas não 00:06:34.743 --> 00:06:38.815 segurar? Se houvesse tais grupos, então seria definitivamente vale a pena, porque 00:06:38.815 --> 00:06:43.050 esses grupos, o ElGamal duplo seria seguro, mas o ElGamal regular não 00:06:43.050 --> 00:06:47.508 CCA ser seguro. Mas, infelizmente, nós não saber se existe qualquer desses grupos e em 00:06:47.508 --> 00:06:51.383 fato de, tanto quanto sabemos, é certamente possível que qualquer grupo que detém CDH, 00:06:51.383 --> 00:06:55.307 IDH também tem. Portanto, a resposta é, realmente, não sabemos se o custo extra é 00:06:55.307 --> 00:06:59.530 vale a pena ou não, mas, em seguida, no entanto, é um resultado bonito que mostra que se você quiser 00:06:59.530 --> 00:07:03.256 para atingir cifrado escolhido segurança diretamente da CDH, você pode fazer 00:07:03.256 --> 00:07:08.051 TI sem muitas mudanças para o ElGamal sistema. A próxima pergunta é se nós 00:07:08.051 --> 00:07:12.230 pode se livrar deste pressuposto de que o função hash é uma função ideal de hash 00:07:12.230 --> 00:07:16.617 principalmente que é um oráculo aleatório. E esta é realmente um grande tema. Há um monte de 00:07:16.617 --> 00:07:20.482 trabalhar nesta área, sobre como construir eficientes sistemas de criptografia de chave pública 00:07:20.482 --> 00:07:24.922 que são escolhidos cifrado seguro sem oráculos aleatórios. Esta é uma área muito ativa 00:07:24.922 --> 00:07:29.192 de pesquisa, como eu disse na última década e ainda mais tempo. E eu vou falar que, como 00:07:29.192 --> 00:07:33.379 isto aplica-se a ElGamal, eles são, basicamente, novamente duas famílias de construções. O 00:07:33.379 --> 00:07:37.515 primeira construção é uma construção que usa esses grupos especiais chamados estes 00:07:37.515 --> 00:07:41.599 grupos bilineares que acabei de mencionar antes. Acontece que a estrutura extra 00:07:41.599 --> 00:07:45.682 desses grupos bilineares permite construir muito eficiente escolhido cifrado 00:07:45.682 --> 00:07:50.128 sistemas seguros sem referindo-se ao acaso oráculos e como eu disse no final do 00:07:50.128 --> 00:07:54.367 módulo, eu apontar para uma série de documentos que explicar como fazer isso. Este é um grande 00:07:54.367 --> 00:07:58.876 construção interessante. Mas vai demorar me várias horas para o tipo de explicar como 00:07:58.876 --> 00:08:03.434 obras. A outra alternativa é efectivamente usar grupos, onde uma forte hipótese 00:08:03.434 --> 00:08:07.830 denominada decisão suposição Diffie-Hellman mantém. Mais uma vez, eu não vou definir esta 00:08:07.830 --> 00:08:11.798 suposição aqui. Vou apenas dizer-lhe que esta hipótese, na verdade, tem em 00:08:11.798 --> 00:08:16.141 subgrupos de ZP estrela, em particular se olhar para a forma principal de um subgrupo de 00:08:16.141 --> 00:08:19.812 ZP estrela. A decisão Diffie-Hellman suposição parece ter nesses grupos 00:08:19.812 --> 00:08:23.852 e, em seguida, os grupos que podemos realmente construir uma variante de ElGamal, chamado 00:08:23.852 --> 00:08:27.141 sistema Cramer Shoup que é escolhido cifrado seguro ea decisão 00:08:27.141 --> 00:08:30.665 Diffie-Hellman suposição sem aleatório oráculos. Mais uma vez, este é um belo 00:08:30.665 --> 00:08:34.659 belo resultado, mas novamente seria necessário um par de horas para explicar e por isso não tenho 00:08:34.659 --> 00:08:38.324 vou fazer isso aqui. Este é provavelmente um essas coisas que eu vou deixar para 00:08:38.324 --> 00:08:42.083 tanto os tópicos avançados ou para fazer uma curso avançado de modo que nós vamos fazê-lo em um 00:08:42.083 --> 00:08:46.335 depois do tempo. Mas, novamente eu aponta para um papel no final do módulo apenas um caso em que você 00:08:46.335 --> 00:08:50.626 quiser ler mais sobre isso. Então aqui vai uma lista de documentos que proporciona uma leitura mais 00:08:50.626 --> 00:08:54.208 material. Então se você quer ler sobre Suposições Diffie Hellman, eu acho que 00:08:54.208 --> 00:08:58.036 escreveu um artigo sobre isso há muito tempo, que fala sobre várias suposições 00:08:58.036 --> 00:09:01.716 relacionado, a Diffie Hellman. E em particular, estudos Diffie decisão 00:09:01.716 --> 00:09:05.685 Suposição Hellman. E se você quer aprender sobre como construir escolhida texto cifrado 00:09:05.685 --> 00:09:10.098 sistema seguro de decisão Diffie-Hellman e premissas gostar. Há um muito 00:09:10.098 --> 00:09:14.563 papel bonito por volta Kramer e Shoup a partir de 2002 que mostra como fazê-lo. Isto é 00:09:14.563 --> 00:09:18.618 mais uma vez um papel muito bem recomendado. Se você quer aprender a construir escolhido 00:09:18.618 --> 00:09:22.672 cifrado segurança destas grupos bilineares, em seguida, o papel é para ler 00:09:22.672 --> 00:09:26.983 a um, aqui citados, que, na verdade, usa um mecanismo geral chamada Identidade Baseado 00:09:26.983 --> 00:09:30.884 Criptografia que muito surpreendentemente, Acontece que realmente nos dá escolhido 00:09:30.884 --> 00:09:34.638 cifrado segurança quase de graça. Assim, uma vez que construímos baseado em identidade 00:09:34.638 --> 00:09:38.486 criptografia escolhido cifrado segurança cai imediatamente. E isso é abordado neste 00:09:38.486 --> 00:09:42.283 papel que eu, que eu descrevê-la. O Dupla construção Diffie-Hellman e sua 00:09:42.283 --> 00:09:46.381 prova é descrito neste trabalho que eu referência aqui E, finalmente, se você meio que 00:09:46.381 --> 00:09:50.135 quero ver um papel muito recente. Que dá um quadro muito geral para 00:09:50.135 --> 00:09:54.345 construção de sistemas de texto cifrado, escolhidos segura, utilizando o que é chamado de hash que extraíveis provas 00:09:54.345 --> 00:09:58.506 é mais uma vez um papel bonito por Hoeteck Wee, que foi recentemente publicado. Eu definitivamente 00:09:58.506 --> 00:10:02.416 recomendo a leitura de tudo, tudo tem idéias muito, muito elegantes eles. Eu gostaria de 00:10:02.416 --> 00:10:06.426 poderia cobrir todos eles no básico claro, mas eu vou ter que deixar algumas de 00:10:06.426 --> 00:10:10.436 estes para o curso mais avançado ou talvez os tópicos mais avançados no 00:10:10.436 --> 00:10:14.446 final do curso. Ok, então eu vou parar aqui e no segmento seguinte, eu vou amarrar 00:10:14.446 --> 00:10:18.506 Criptografia RSA e ElGamal em conjunto para que você veja como o tipo dois 00:10:18.506 --> 00:10:20.512 de acompanhamento de um princípio mais geral.