1
00:00:00,000 --> 00:00:03,574
No último segmento, vimos que a
Sistema de criptografia de chave pública ElGamal é

2
00:00:03,574 --> 00:00:07,525
escolhida texto cifrado seguro sob um pouco
suposição estranha. Neste segmento, estamos

3
00:00:07,525 --> 00:00:11,146
vai olhar para as variantes de ElGamal que
tem um texto cifrado muito melhor escolhido

4
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

5
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

6
00:00:18,766 --> 00:00:22,387
seguro. Eu realmente debatido por algum tempo
sobre a melhor forma de apresentar este aqui. E

7
00:00:22,387 --> 00:00:26,197
finalmente, decidi tipo de mostrar um
levantamento dos principais resultados do último

8
00:00:26,197 --> 00:00:29,960
décadas, especificamente como eles se aplicam ao
Sistema ElGamal. E, em seguida, no final da

9
00:00:29,960 --> 00:00:33,770
o módulo, sugiro uma série de documentos
que você pode olhar para outras leituras.

10
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

11
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

12
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

13
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,

14
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.

15
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

16
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

17
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

18
00:01:10,233 --> 00:01:15,156
sistema de criptografia simétrica com a chave K
que é derivada da função hash. E

19
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

20
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

21
00:01:24,654 --> 00:01:28,940
Diffie Hellman segredos, descriptografar o
sistema simétrico, e produzir o

22
00:01:28,940 --> 00:01:33,645
mensagem M. Agora, no último segmento dissemos
ElGamal que é escolhido cifrado seguro sob

23
00:01:33,645 --> 00:01:37,881
este interativo engraçado Diffie-Hellman
suposição. Eu não vou lembrá-lo que

24
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

25
00:01:42,447 --> 00:01:46,683
questões naturais. A primeira pergunta é
podemos provar CCA segurança de

26
00:01:46,683 --> 00:01:50,864
ElGamal apenas com base no padrão
Pressuposto de Diffie-Hellman computacional,

27
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

28
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

29
00:01:59,259 --> 00:02:03,454
maneiras de fazer isso. A primeira opção é usar
um grupo onde o Diffie computacional

30
00:02:03,454 --> 00:02:07,306
Pressuposto de Hellman é difícil. Mas é
comprovadamente equivalente ao interativo

31
00:02:07,306 --> 00:02:11,227
Diffie Hellman suposição. E acontece
fora não é realmente difícil de

32
00:02:11,227 --> 00:02:15,147
construção de tais grupos. Estes grupos são
chamados grupos bilineares. E de tal

33
00:02:15,147 --> 00:02:19,544
grupos, sabemos que o sistema é ElGamal
texto cifrado escolhido seguro, estritamente baseadas

34
00:02:19,544 --> 00:02:23,782
sob a Computational Diffie Hellman
suposição, pelo menos no oráculo aleatório

35
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

36
00:02:28,983 --> 00:02:33,715
especiais curvas elípticas. Portanto, há um pouco
mais estrutura algébrica que permite-nos

37
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

38
00:02:38,404 --> 00:02:42,928
quer usar grupos curvas elípticas, talvez
você quer usar estrela ZP por algum motivo.

39
00:02:42,928 --> 00:02:47,817
Então é uma pergunta muito natural perguntar.
Podemos mudar o sistema de tal forma que ElGamal

40
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

41
00:02:52,828 --> 00:02:57,840
CDH onde é difícil? [Agora com isso??] Assumindo
qualquer estrutura adicional sobre o grupo,

42
00:02:57,840 --> 00:03:02,132
E acontece que a resposta é sim. E
há um tipo de uma construção elegante

43
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

44
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

45
00:03:10,607 --> 00:03:14,954
escolher um gerador aleatório. Mas, desta vez,
vamos escolher dois expoentes, A1 e

46
00:03:14,954 --> 00:03:19,409
A2 como a chave secreta. Portanto, a chave é segredo
vai consistir desses dois expoentes, A1

47
00:03:19,409 --> 00:03:23,783
e A2. Conhece a chave pública do curso
se vai consistir em nosso gerador. E

48
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

49
00:03:28,340 --> 00:03:32,840
ElGamal que a chave pública é simplesmente g
para o A e é isso. Aqui temos dois

50
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.

51
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

52
00:03:42,297 --> 00:03:47,137
ElGamal regular. A forma como criptografar usando
esta chave pública é realmente muito semelhante

53
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

54
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

55
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

56
00:04:01,691 --> 00:04:06,642
então nós basicamente criptografar a mensagem
usando a chave de criptografia simétrica derivada

57
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?

58
00:04:11,410 --> 00:04:16,027
Bem, agora a chave secreta consiste em
esses dois expoentes, A1 e A2. E a

59
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

60
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

61
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

62
00:04:31,934 --> 00:04:37,250
espero que todos trabalhados, a solução
que é basicamente o que podemos fazer é que

63
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

64
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

65
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

66
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

67
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

68
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

69
00:05:07,802 --> 00:05:11,888
nós fazemos o hash, que um hash mais
elemento, em vez de apenas dois elementos.

70
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

71
00:05:16,246 --> 00:05:20,491
mudanças. O texto cifrado é o mesmo
comprimento como antes, e é isso, agora o

72
00:05:20,491 --> 00:05:24,647
coisa surpreendente é que esta simples
modificação permite-nos agora provar escolhido

73
00:05:24,647 --> 00:05:28,640
segurança texto cifrado diretamente com base em
padrão computacional Diffie-Hellman

74
00:05:28,640 --> 00:05:32,795
suposição, ok? Ainda vamos
precisa assumir que temos uma simétrica

75
00:05:32,795 --> 00:05:36,897
sistema de criptografia que nos fornece
autenticada criptografia e que o hash

76
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

77
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

78
00:05:45,747 --> 00:05:49,803
baseado numa Computational Diffie-Hellman
suposição. Então agora o que é o custo disso?

79
00:05:49,803 --> 00:05:53,966
Claro, se você pensar sobre isso, durante
criptografia e descriptografia, criptografia tem

80
00:05:53,966 --> 00:05:57,418
fazer mais uma exponenciação, eo
decodificação tem que fazer mais uma

81
00:05:57,418 --> 00:06:01,581
exponenciação. Assim, o codificador faz agora
exponenciações três em vez de dois, e

82
00:06:01,581 --> 00:06:05,490
o decoder faz duas exponenciações
em vez de um. Então a questão é agora,

83
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

84
00:06:09,965 --> 00:06:14,228
durante a criptografia e descriptografia. E sua
chave pública é um pouco maior, mas

85
00:06:14,228 --> 00:06:18,331
que realmente não importa. O trabalho
durante a criptografia e descriptografia é mais

86
00:06:18,331 --> 00:06:22,434
significativo. E, como resultado você começa
cifrado escolhido segurança baseado em espécie

87
00:06:22,434 --> 00:06:26,644
de uma hipótese mais natural, ou seja,
Computational Diffie-Hellman em oposição a

88
00:06:26,644 --> 00:06:30,480
estes interativo de aparência estranha
Diffie-Hellman suposição. Mas vale a pena

89
00:06:30,480 --> 00:06:34,743
isso? Tipo de questão é que existem
grupos onde CDH detém IDH, mas não

90
00:06:34,743 --> 00:06:38,815
segurar? Se houvesse tais grupos, então
seria definitivamente vale a pena, porque

91
00:06:38,815 --> 00:06:43,050
esses grupos, o ElGamal duplo seria
seguro, mas o ElGamal regular não

92
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

93
00:06:47,508 --> 00:06:51,383
fato de, tanto quanto sabemos, é certamente
possível que qualquer grupo que detém CDH,

94
00:06:51,383 --> 00:06:55,307
IDH também tem. Portanto, a resposta é, realmente,
não sabemos se o custo extra é

95
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

96
00:06:59,530 --> 00:07:03,256
para atingir cifrado escolhido
segurança diretamente da CDH, você pode fazer

97
00:07:03,256 --> 00:07:08,051
TI sem muitas mudanças para o ElGamal
sistema. A próxima pergunta é se nós

98
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

99
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

100
00:07:16,617 --> 00:07:20,482
trabalhar nesta área, sobre como construir
eficientes sistemas de criptografia de chave pública

101
00:07:20,482 --> 00:07:24,922
que são escolhidos cifrado seguro sem
oráculos aleatórios. Esta é uma área muito ativa

102
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

103
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

104
00:07:33,379 --> 00:07:37,515
primeira construção é uma construção que
usa esses grupos especiais chamados estes

105
00:07:37,515 --> 00:07:41,599
grupos bilineares que acabei de mencionar
antes. Acontece que a estrutura extra

106
00:07:41,599 --> 00:07:45,682
desses grupos bilineares permite
construir muito eficiente escolhido cifrado

107
00:07:45,682 --> 00:07:50,128
sistemas seguros sem referindo-se ao acaso
oráculos e como eu disse no final do

108
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

109
00:07:54,367 --> 00:07:58,876
construção interessante. Mas vai demorar
me várias horas para o tipo de explicar como

110
00:07:58,876 --> 00:08:03,434
obras. A outra alternativa é efectivamente
usar grupos, onde uma forte hipótese

111
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

112
00:08:07,830 --> 00:08:11,798
suposição aqui. Vou apenas dizer-lhe que
esta hipótese, na verdade, tem em

113
00:08:11,798 --> 00:08:16,141
subgrupos de ZP estrela, em particular se
olhar para a forma principal de um subgrupo de

114
00:08:16,141 --> 00:08:19,812
ZP estrela. A decisão Diffie-Hellman
suposição parece ter nesses grupos

115
00:08:19,812 --> 00:08:23,852
e, em seguida, os grupos que podemos realmente
construir uma variante de ElGamal, chamado

116
00:08:23,852 --> 00:08:27,141
sistema Cramer Shoup que é escolhido
cifrado seguro ea decisão

117
00:08:27,141 --> 00:08:30,665
Diffie-Hellman suposição sem aleatório
oráculos. Mais uma vez, este é um belo

118
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

119
00:08:34,659 --> 00:08:38,324
vou fazer isso aqui. Este é provavelmente um
essas coisas que eu vou deixar para

120
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

121
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ê

122
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

123
00:08:50,626 --> 00:08:54,208
material. Então se você quer ler sobre
Suposições Diffie Hellman, eu acho que

124
00:08:54,208 --> 00:08:58,036
escreveu um artigo sobre isso há muito tempo,
que fala sobre várias suposições

125
00:08:58,036 --> 00:09:01,716
relacionado, a Diffie Hellman. E em
particular, estudos Diffie decisão

126
00:09:01,716 --> 00:09:05,685
Suposição Hellman. E se você quer aprender
sobre como construir escolhida texto cifrado

127
00:09:05,685 --> 00:09:10,098
sistema seguro de decisão Diffie-Hellman
e premissas gostar. Há um muito

128
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 é

129
00:09:14,563 --> 00:09:18,618
mais uma vez um papel muito bem recomendado. Se
você quer aprender a construir escolhido

130
00:09:18,618 --> 00:09:22,672
cifrado segurança destas
grupos bilineares, em seguida, o papel é para ler

131
00:09:22,672 --> 00:09:26,983
a um, aqui citados, que, na verdade, usa um
mecanismo geral chamada Identidade Baseado

132
00:09:26,983 --> 00:09:30,884
Criptografia que muito surpreendentemente,
Acontece que realmente nos dá escolhido

133
00:09:30,884 --> 00:09:34,638
cifrado segurança quase de graça.
Assim, uma vez que construímos baseado em identidade

134
00:09:34,638 --> 00:09:38,486
criptografia escolhido cifrado segurança cai
imediatamente. E isso é abordado neste

135
00:09:38,486 --> 00:09:42,283
papel que eu, que eu descrevê-la. O
Dupla construção Diffie-Hellman e sua

136
00:09:42,283 --> 00:09:46,381
prova é descrito neste trabalho que eu
referência aqui E, finalmente, se você meio que

137
00:09:46,381 --> 00:09:50,135
quero ver um papel muito recente. Que
dá um quadro muito geral para

138
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

139
00:09:54,345 --> 00:09:58,506
é mais uma vez um papel bonito por Hoeteck Wee, que
foi recentemente publicado. Eu definitivamente

140
00:09:58,506 --> 00:10:02,416
recomendo a leitura de tudo, tudo tem
idéias muito, muito elegantes eles. Eu gostaria de

141
00:10:02,416 --> 00:10:06,426
poderia cobrir todos eles no básico
claro, mas eu vou ter que deixar algumas de

142
00:10:06,426 --> 00:10:10,436
estes para o curso mais avançado ou
talvez os tópicos mais avançados no

143
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

144
00:10:14,446 --> 00:10:18,506
Criptografia RSA e ElGamal
em conjunto para que você veja como o tipo dois

145
00:10:18,506 --> 00:10:20,512
de acompanhamento de um princípio mais geral.