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.