0:00:00.000,0:00:03.574
No último segmento, vimos que a[br]Sistema de criptografia de chave pública ElGamal é

0:00:03.574,0:00:07.525
escolhida texto cifrado seguro sob um pouco[br]suposição estranha. Neste segmento, estamos

0:00:07.525,0:00:11.146
vai olhar para as variantes de ElGamal que[br]tem um texto cifrado muito melhor escolhido

0:00:11.146,0:00:14.909
análise de segurança. Agora, devo dizer que[br]na última década, tem havido uma tonelada

0:00:14.909,0:00:18.766
de pesquisas sobre a construção de chave pública[br]criptografias que são escolhidos texto cifrado

0:00:18.766,0:00:22.387
seguro. Eu realmente debatido por algum tempo[br]sobre a melhor forma de apresentar este aqui. E

0:00:22.387,0:00:26.197
finalmente, decidi tipo de mostrar um[br]levantamento dos principais resultados do último

0:00:26.197,0:00:29.960
décadas, especificamente como eles se aplicam ao[br]Sistema ElGamal. E, em seguida, no final da

0:00:29.960,0:00:33.770
o módulo, sugiro uma série de documentos[br]que você pode olhar para outras leituras.

0:00:33.770,0:00:38.332
Então deixe-me começar por lembrar que a forma como o[br]Sistema de criptografia ElGamal funciona. Tenho certeza de que

0:00:38.332,0:00:42.783
agora você se lembrar de como tudo funciona ElGamal,[br]mas apenas para ser seguro, deixe-me lembrá-lo

0:00:42.783,0:00:47.623
que a geração de chave no ElGamal escolhe um[br]gerador aleatório, um expoente aleatório de ZN

0:00:47.623,0:00:51.963
e, em seguida, a chave pública é simplesmente o[br]gerador de g e este elemento ao a,

0:00:51.963,0:00:56.332
ao passo que a chave secreta é simplesmente o[br]logaritmo discreto de h base de g. Este valor A.

0:00:56.332,0:01:01.255
Agora, a nossa forma de criptografar é que escolher um aleatório[br]expoente B de ZN. Calculamos o hash

0:01:01.255,0:01:05.947
G para a B e H para a B. E eu vou[br]Lembramos que H para o B é o Diffie

0:01:05.947,0:01:10.233
Hellman segredo, G para a AB. E então nós[br]realmente criptografar uma mensagem usando um

0:01:10.233,0:01:15.156
sistema de criptografia simétrica com a chave K[br]que é derivada da função hash. E

0:01:15.156,0:01:19.731
finalmente, a saída de texto cifrado é a G[br]a B, e o texto cifrado simétrico. O

0:01:19.731,0:01:24.654
nossa forma de descriptografar é que você sabe, como vimos[br]antes, basicamente, através de hash U ea

0:01:24.654,0:01:28.940
Diffie Hellman segredos, descriptografar o[br]sistema simétrico, e produzir o

0:01:28.940,0:01:33.645
mensagem M. Agora, no último segmento dissemos[br]ElGamal que é escolhido cifrado seguro sob

0:01:33.645,0:01:37.881
este interativo engraçado Diffie-Hellman[br]suposição. Eu não vou lembrá-lo que

0:01:37.881,0:01:42.447
o pressuposto é aqui, mas eu também vou dizer[br]que este tipo teorema de suscita duas muito

0:01:42.447,0:01:46.683
questões naturais. A primeira pergunta é[br]podemos provar CCA segurança de

0:01:46.683,0:01:50.864
ElGamal apenas com base no padrão[br]Pressuposto de Diffie-Hellman computacional,

0:01:50.864,0:01:55.011
a saber, a G para A, G para o B,[br]não pode calcular G para a AB. Podemos provar

0:01:55.011,0:01:59.259
escolhido-texto cifrado de segurança apenas com base em[br]isso? E a verdade é que existem dois

0:01:59.259,0:02:03.454
maneiras de fazer isso. A primeira opção é usar[br]um grupo onde o Diffie computacional

0:02:03.454,0:02:07.306
Pressuposto de Hellman é difícil. Mas é[br]comprovadamente equivalente ao interativo

0:02:07.306,0:02:11.227
Diffie Hellman suposição. E acontece[br]fora não é realmente difícil de

0:02:11.227,0:02:15.147
construção de tais grupos. Estes grupos são[br]chamados grupos bilineares. E de tal

0:02:15.147,0:02:19.544
grupos, sabemos que o sistema é ElGamal[br]texto cifrado escolhido seguro, estritamente baseadas

0:02:19.544,0:02:23.782
sob a Computational Diffie Hellman[br]suposição, pelo menos no oráculo aleatório

0:02:23.782,0:02:28.983
modelo. Eu vou te dizer que estes bi-linear[br]grupos são realmente construídos a partir de muito

0:02:28.983,0:02:33.715
especiais curvas elípticas. Portanto, há um pouco[br]mais estrutura algébrica que permite-nos

0:02:33.715,0:02:38.404
para provar esta equivalência de IDH e CDH.[br]Mas, em geral, quem sabe, talvez não

0:02:38.404,0:02:42.928
quer usar grupos curvas elípticas, talvez[br]você quer usar estrela ZP por algum motivo.

0:02:42.928,0:02:47.817
Então é uma pergunta muito natural perguntar.[br]Podemos mudar o sistema de tal forma que ElGamal

0:02:47.817,0:02:52.828
cifrado escolhido segurança de ElGamal agora pode ser provado, directamente com base no CDH, para qualquer grupo

0:02:52.828,0:02:57.840
CDH onde é difícil? [Agora com isso??] Assumindo[br]qualquer estrutura adicional sobre o grupo,

0:02:57.840,0:03:02.132
E acontece que a resposta é sim. E[br]há um tipo de uma construção elegante

0:03:02.132,0:03:06.696
chamado ElGamal gêmeo, então deixe-me mostrar-lhe[br]como gêmeo obras ElGamal. É uma forma muito simples

0:03:06.696,0:03:10.607
variação de ElGamal que faz o[br]sequência. Mais uma vez, na geração de chaves, nós

0:03:10.607,0:03:14.954
escolher um gerador aleatório. Mas, desta vez,[br]vamos escolher dois expoentes, A1 e

0:03:14.954,0:03:19.409
A2 como a chave secreta. Portanto, a chave é segredo[br]vai consistir desses dois expoentes, A1

0:03:19.409,0:03:23.783
e A2. Conhece a chave pública do curso[br]se vai consistir em nosso gerador. E

0:03:23.783,0:03:28.340
então nós vamos liberar G para a A1 e G[br]para a A2. Então lembre-se que em regular

0:03:28.340,0:03:32.840
ElGamal que a chave pública é simplesmente g[br]para o A e é isso. Aqui temos dois

0:03:32.840,0:03:37.340
expoentes A1 e A2 e, portanto, nós, nós[br]solte G para a A1 e G para a A2.

0:03:37.340,0:03:42.297
Agora, a nossa forma de criptografar, você vai notar a[br]chave pública é aqui um elemento de mais de

0:03:42.297,0:03:47.137
ElGamal regular. A forma como criptografar usando[br]esta chave pública é realmente muito semelhante

0:03:47.137,0:03:51.859
para ElGamal regular. Nós escolhemos um B aleatória,[br]e agora o que vamos hash é, na verdade, não

0:03:51.859,0:03:56.522
G apenas para a B e H1 para o B, mas,[br]de facto, para o G B, H1 para a B, e H2

0:03:56.522,0:04:01.691
para o B. Ok então nós basicamente hash[br]três elementos em vez de dois elementos e

0:04:01.691,0:04:06.642
então nós basicamente criptografar a mensagem[br]usando a chave de criptografia simétrica derivada

0:04:06.642,0:04:11.410
e como de costume, a saída para o g b e c como o nosso[br]último texto cifrado. Como podemos decifrar?

0:04:11.410,0:04:16.027
Bem, agora a chave secreta consiste em[br]esses dois expoentes, A1 e A2. E a

0:04:16.027,0:04:20.584
texto cifrado consiste em U, e a[br]simétrica texto cifrado C. Então deixe-me perguntar-lhe

0:04:20.584,0:04:25.501
um quebra-cabeça, e veja se você pode descobrir[br]como obter a chave de criptografia simétrica

0:04:25.501,0:04:31.934
K, dado apenas a chave secreta eo valor[br]U. Então, é uma espécie de quebra-cabeça bonito e eu

0:04:31.934,0:04:37.250
espero que todos trabalhados, a solução[br]que é basicamente o que podemos fazer é que

0:04:37.250,0:04:42.566
U pode levar à potência de A1, e que é[br]G basicamente à A1 B e U para a A2

0:04:42.566,0:04:48.012
que é G para a A2 B. E que, basicamente,[br]nos dá exatamente os mesmos valores, como a H1

0:04:48.012,0:04:53.069
o B e H2 para a B. Portanto, a forma como este[br]decryptor chega à mesma simétrica

0:04:53.069,0:04:58.515
chave que o codificador fez. Então, ele decifra[br]o texto cifrado com o sistema simétrico

0:04:58.515,0:05:03.389
e, finalmente, gera a mensagem M. Então você[br]Note que isto é uma modificação muito simples

0:05:03.389,0:05:07.802
para ElGamal regular. Tudo o que fazemos é ficar[br]mais um elemento para a chave pública. Quando

0:05:07.802,0:05:11.888
nós fazemos o hash, que um hash mais[br]elemento, em vez de apenas dois elementos.

0:05:11.888,0:05:16.246
Nós hash de três elementos. E da mesma forma, nós[br]descriptografia fazer fazendo, e nada mais

0:05:16.246,0:05:20.491
mudanças. O texto cifrado é o mesmo[br]comprimento como antes, e é isso, agora o

0:05:20.491,0:05:24.647
coisa surpreendente é que esta simples[br]modificação permite-nos agora provar escolhido

0:05:24.647,0:05:28.640
segurança texto cifrado diretamente com base em[br]padrão computacional Diffie-Hellman

0:05:28.640,0:05:32.795
suposição, ok? Ainda vamos[br]precisa assumir que temos uma simétrica

0:05:32.795,0:05:36.897
sistema de criptografia que nos fornece[br]autenticada criptografia e que o hash

0:05:36.897,0:05:41.430
função que estamos usando é um hash ideal[br]função no que chamamos de um oráculo aleatório

0:05:41.430,0:05:45.747
Mas, no entanto, dado que, o que pudermos[br]provar a segurança da cifra escolhida texto estritamente

0:05:45.747,0:05:49.803
baseado numa Computational Diffie-Hellman[br]suposição. Então agora o que é o custo disso?

0:05:49.803,0:05:53.966
Claro, se você pensar sobre isso, durante[br]criptografia e descriptografia, criptografia tem

0:05:53.966,0:05:57.418
fazer mais uma exponenciação, eo[br]decodificação tem que fazer mais uma

0:05:57.418,0:06:01.581
exponenciação. Assim, o codificador faz agora[br]exponenciações três em vez de dois, e

0:06:01.581,0:06:05.490
o decoder faz duas exponenciações[br]em vez de um. Então a questão é agora,

0:06:05.490,0:06:09.965
agora é uma questão filosófica. É este o[br]esforço extra vale a pena? Então você faz um trabalho mais

0:06:09.965,0:06:14.228
durante a criptografia e descriptografia. E sua[br]chave pública é um pouco maior, mas

0:06:14.228,0:06:18.331
que realmente não importa. O trabalho[br]durante a criptografia e descriptografia é mais

0:06:18.331,0:06:22.434
significativo. E, como resultado você começa[br]cifrado escolhido segurança baseado em espécie

0:06:22.434,0:06:26.644
de uma hipótese mais natural, ou seja,[br]Computational Diffie-Hellman em oposição a

0:06:26.644,0:06:30.480
estes interativo de aparência estranha[br]Diffie-Hellman suposição. Mas vale a pena

0:06:30.480,0:06:34.743
isso? Tipo de questão é que existem[br]grupos onde CDH detém IDH, mas não

0:06:34.743,0:06:38.815
segurar? Se houvesse tais grupos, então[br]seria definitivamente vale a pena, porque

0:06:38.815,0:06:43.050
esses grupos, o ElGamal duplo seria[br]seguro, mas o ElGamal regular não

0:06:43.050,0:06:47.508
CCA ser seguro. Mas, infelizmente, nós não[br]saber se existe qualquer desses grupos e em

0:06:47.508,0:06:51.383
fato de, tanto quanto sabemos, é certamente[br]possível que qualquer grupo que detém CDH,

0:06:51.383,0:06:55.307
IDH também tem. Portanto, a resposta é, realmente,[br]não sabemos se o custo extra é

0:06:55.307,0:06:59.530
vale a pena ou não, mas, em seguida, no entanto, é[br]um resultado bonito que mostra que se você quiser

0:06:59.530,0:07:03.256
para atingir cifrado escolhido[br]segurança diretamente da CDH, você pode fazer

0:07:03.256,0:07:08.051
TI sem muitas mudanças para o ElGamal[br]sistema. A próxima pergunta é se nós

0:07:08.051,0:07:12.230
pode se livrar deste pressuposto de que o[br]função hash é uma função ideal de hash

0:07:12.230,0:07:16.617
principalmente que é um oráculo aleatório. E esta[br]é realmente um grande tema. Há um monte de

0:07:16.617,0:07:20.482
trabalhar nesta área, sobre como construir[br]eficientes sistemas de criptografia de chave pública

0:07:20.482,0:07:24.922
que são escolhidos cifrado seguro sem[br]oráculos aleatórios. Esta é uma área muito ativa

0:07:24.922,0:07:29.192
de pesquisa, como eu disse na última década[br]e ainda mais tempo. E eu vou falar que, como

0:07:29.192,0:07:33.379
isto aplica-se a ElGamal, eles são, basicamente,[br]novamente duas famílias de construções. O

0:07:33.379,0:07:37.515
primeira construção é uma construção que[br]usa esses grupos especiais chamados estes

0:07:37.515,0:07:41.599
grupos bilineares que acabei de mencionar[br]antes. Acontece que a estrutura extra

0:07:41.599,0:07:45.682
desses grupos bilineares permite[br]construir muito eficiente escolhido cifrado

0:07:45.682,0:07:50.128
sistemas seguros sem referindo-se ao acaso[br]oráculos e como eu disse no final do

0:07:50.128,0:07:54.367
módulo, eu apontar para uma série de documentos que[br]explicar como fazer isso. Este é um grande

0:07:54.367,0:07:58.876
construção interessante. Mas vai demorar[br]me várias horas para o tipo de explicar como

0:07:58.876,0:08:03.434
obras. A outra alternativa é efectivamente[br]usar grupos, onde uma forte hipótese

0:08:03.434,0:08:07.830
denominada decisão suposição Diffie-Hellman[br]mantém. Mais uma vez, eu não vou definir esta

0:08:07.830,0:08:11.798
suposição aqui. Vou apenas dizer-lhe que[br]esta hipótese, na verdade, tem em

0:08:11.798,0:08:16.141
subgrupos de ZP estrela, em particular se[br]olhar para a forma principal de um subgrupo de

0:08:16.141,0:08:19.812
ZP estrela. A decisão Diffie-Hellman[br]suposição parece ter nesses grupos

0:08:19.812,0:08:23.852
e, em seguida, os grupos que podemos realmente[br]construir uma variante de ElGamal, chamado

0:08:23.852,0:08:27.141
sistema Cramer Shoup que é escolhido[br]cifrado seguro ea decisão

0:08:27.141,0:08:30.665
Diffie-Hellman suposição sem aleatório[br]oráculos. Mais uma vez, este é um belo

0:08:30.665,0:08:34.659
belo resultado, mas novamente seria necessário um[br]par de horas para explicar e por isso não tenho

0:08:34.659,0:08:38.324
vou fazer isso aqui. Este é provavelmente um[br]essas coisas que eu vou deixar para

0:08:38.324,0:08:42.083
tanto os tópicos avançados ou para fazer uma[br]curso avançado de modo que nós vamos fazê-lo em um

0:08:42.083,0:08:46.335
depois do tempo. Mas, novamente eu aponta para um papel[br]no final do módulo apenas um caso em que você

0:08:46.335,0:08:50.626
quiser ler mais sobre isso. Então aqui vai uma[br]lista de documentos que proporciona uma leitura mais

0:08:50.626,0:08:54.208
material. Então se você quer ler sobre[br]Suposições Diffie Hellman, eu acho que

0:08:54.208,0:08:58.036
escreveu um artigo sobre isso há muito tempo,[br]que fala sobre várias suposições

0:08:58.036,0:09:01.716
relacionado, a Diffie Hellman. E em[br]particular, estudos Diffie decisão

0:09:01.716,0:09:05.685
Suposição Hellman. E se você quer aprender[br]sobre como construir escolhida texto cifrado

0:09:05.685,0:09:10.098
sistema seguro de decisão Diffie-Hellman[br]e premissas gostar. Há um muito

0:09:10.098,0:09:14.563
papel bonito por volta Kramer e Shoup[br]a partir de 2002 que mostra como fazê-lo. Isto é

0:09:14.563,0:09:18.618
mais uma vez um papel muito bem recomendado. Se[br]você quer aprender a construir escolhido

0:09:18.618,0:09:22.672
cifrado segurança destas[br]grupos bilineares, em seguida, o papel é para ler

0:09:22.672,0:09:26.983
a um, aqui citados, que, na verdade, usa um[br]mecanismo geral chamada Identidade Baseado

0:09:26.983,0:09:30.884
Criptografia que muito surpreendentemente,[br]Acontece que realmente nos dá escolhido

0:09:30.884,0:09:34.638
cifrado segurança quase de graça.[br]Assim, uma vez que construímos baseado em identidade

0:09:34.638,0:09:38.486
criptografia escolhido cifrado segurança cai[br]imediatamente. E isso é abordado neste

0:09:38.486,0:09:42.283
papel que eu, que eu descrevê-la. O[br]Dupla construção Diffie-Hellman e sua

0:09:42.283,0:09:46.381
prova é descrito neste trabalho que eu[br]referência aqui E, finalmente, se você meio que

0:09:46.381,0:09:50.135
quero ver um papel muito recente. Que[br]dá um quadro muito geral para

0:09:50.135,0:09:54.345
construção de sistemas de texto cifrado, escolhidos segura, utilizando[br]o que é chamado de hash que extraíveis provas

0:09:54.345,0:09:58.506
é mais uma vez um papel bonito por Hoeteck Wee, que[br]foi recentemente publicado. Eu definitivamente

0:09:58.506,0:10:02.416
recomendo a leitura de tudo, tudo tem[br]idéias muito, muito elegantes eles. Eu gostaria de

0:10:02.416,0:10:06.426
poderia cobrir todos eles no básico[br]claro, mas eu vou ter que deixar algumas de

0:10:06.426,0:10:10.436
estes para o curso mais avançado ou[br]talvez os tópicos mais avançados no

0:10:10.436,0:10:14.446
final do curso. Ok, então eu vou parar[br]aqui e no segmento seguinte, eu vou amarrar

0:10:14.446,0:10:18.506
Criptografia RSA e ElGamal[br]em conjunto para que você veja como o tipo dois

0:10:18.506,0:10:20.512
de acompanhamento de um princípio mais geral.