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.