1
00:00:00,000 --> 00:00:04,388
Neste segmento perguntamos se podemos construir a partir de cifras de bloco simples

2
00:00:04,388 --> 00:00:09,456
primitivos como pseudo geradores aleatórios. A resposta é sim. Então, para começar, vamos

3
00:00:09,456 --> 00:00:14,215
perguntar se podemos construir pseudo funções aleatórias em vez de pseudo-aleatório

4
00:00:14,215 --> 00:00:18,789
permutações de um gerador pseudo-aleatório. Podemos construir um PRF de um PRG?

5
00:00:18,789 --> 00:00:23,873
Nosso objetivo final que é construir uma cifra de bloco que é um PRP. E nós vamos chegar

6
00:00:23,873 --> 00:00:29,130
a que, no final. Ok, agora vamos construir um PRF. Então vamos começar com um PRG que

7
00:00:29,130 --> 00:00:34,590
dobra suas entradas de modo as sementes para o PRG é um elemento em K ea saída é

8
00:00:34,590 --> 00:00:39,420
, na verdade, dois elementos em K. Portanto, aqui temos um esquema do gerador, que

9
00:00:39,420 --> 00:00:44,296
basicamente tem sua entrada de C e K, e saídas de dois elementos, em K, como sua saída.

10
00:00:44,296 --> 00:00:48,992
E agora o que significa para essa pureza para ser seguro, lembre-se isto significa que

11
00:00:48,992 --> 00:00:52,965
essencialmente a saída é indistinguível de um elemento aleatório

12
00:00:52,965 --> 00:00:58,355
dentro de K quadrado Agora verifica-se que é muito fácil definir basicamente o que é

13
00:00:58,355 --> 00:01:03,455
chamado uma PRF bit um a partir deste PRG. Então, o que é um pouco um PRF é basicamente um PRF

14
00:01:03,455 --> 00:01:08,360
domínio que é apenas um bit. Ok, então é um PRF que só leva um pouco como

15
00:01:08,360 --> 00:01:13,461
de entrada. Ok, ea forma como vamos fazê-lo é que vai dizer é se o X bit de entrada é zero

16
00:01:13,461 --> 00:01:18,627
eu vou colocar a saída esquerda e se o bit de entrada X é um, então eu vou colocar o direito

17
00:01:18,627 --> 00:01:23,678
saída do PRF. Ok, em símbolos, temos basicamente o que escrevi aqui. Agora

18
00:01:23,678 --> 00:01:28,523
é simples para mostrar que, de facto, G é um PRG segura, então este bit PRF um é

19
00:01:28,523 --> 00:01:32,901
, de facto, uma PRF seguro. Se você pensar nisso por um segundo, isso realmente não é

20
00:01:32,901 --> 00:01:37,571
[inaudível]. É realmente apenas afirmando a mesma coisa duas vezes. Então eu vou deixá-lo por

21
00:01:37,571 --> 00:01:42,241
você pensar sobre isso de forma breve e ver e se convencer de que de fato esta

22
00:01:42,241 --> 00:01:46,853
teorema é verdadeiro. As verdadeiras questões é se podemos construir um PRF, que na verdade

23
00:01:46,853 --> 00:01:51,756
tem um domínio que é maior do que um bit. Idealmente gostaríamos que o domínio para ser 128

24
00:01:51,756 --> 00:01:56,425
bits, basta dizer que a [inaudível] tem. Então a questão é que podemos construir 128 bits PRS

25
00:01:56,425 --> 00:02:01,197
a partir de um gerador pseudo-aleatório. Bem, então vamos ver se podemos fazer progressos. Assim, o

26
00:02:01,197 --> 00:02:05,970
primeira coisa que vamos fazer é que nós vamos dizer, bem de novo, vamos começar com um PRG

27
00:02:05,970 --> 00:02:10,863
, que duplica o seu contributo vamos ver se podemos construir um PRG que quadruplica suas entradas.

28
00:02:10,863 --> 00:02:15,797
Ok? Assim, ele vai de K para K para o quarto em vez de K para K quadrado. Ok, então vamos

29
00:02:15,797 --> 00:02:20,809
ver como fazer isso. Então, vamos começar com a nossa PRG original que apenas duplica a sua

30
00:02:20,809 --> 00:02:25,884
entradas, agora lembrar que o facto de a sua é um PRG significa que a saída do

31
00:02:25,884 --> 00:02:30,771
PRG é indistinguível de dois valores aleatórios em K. Bem, se a saída se parece

32
00:02:30,771 --> 00:02:35,847
como dois valores aleatórios em K, podemos simplesmente aplicar o gerador de novo para os dois

33
00:02:35,847 --> 00:02:40,358
saídas. Então, digamos que nós aplicamos o gerador de uma vez para a saída da esquerda, e

34
00:02:40,358 --> 00:02:45,342
uma vez para as saídas de direitos. E nós vamos chamar a saída de que, este

35
00:02:45,342 --> 00:02:50,448
quádruplo de elementos, que são, vão chamar isso de G1K. E eu escrevi em

36
00:02:50,448 --> 00:02:55,554
símbolos que esse gerador faz, mas você pode ver, basicamente, a partir desta figura,

37
00:02:55,554 --> 00:03:00,862
exatamente como funciona o gerador. Portanto, agora que temos um gerador de K a K para

38
00:03:00,862 --> 00:03:06,170
quarta, Nós realmente obter um pouco PRF dois. Ou seja, o que vamos fazer é, vamos dizer,

39
00:03:06,170 --> 00:03:11,410
dado dois bits, 000110 ou 11, vontades implica a saída do bloco apropriado que

40
00:03:11,410 --> 00:03:16,070
saída de G1K. Ok, então agora podemos basicamente ter um PRF que leva quatro

41
00:03:16,070 --> 00:03:21,061
entradas possíveis ao invés de apenas duas entradas possíveis como antes. Portanto, a questão

42
00:03:21,061 --> 00:03:26,113
você deve estar me perguntando é porque é que este caso G1 seguro? Por que é um PRG seguro? Que

43
00:03:26,113 --> 00:03:30,611
é por que isso é quadruplicar de saídas indistinguíveis de forma aleatória. E assim

44
00:03:30,611 --> 00:03:35,664
vamos fazer uma prova rápida de isso, apenas vou fazer uma prova simples por imagens. Então aqui está

45
00:03:35,664 --> 00:03:40,408
gerador nossa que queremos provar é seguro. E o que isso significa é que nós

46
00:03:40,408 --> 00:03:45,399
quero argumentar que essa distribuição é indistinguível de um fordable aleatória

47
00:03:45,399 --> 00:03:49,292
em K para a quarta. Ok então nosso objetivo é provar que esses dois são

48
00:03:49,292 --> 00:03:53,887
indistinguíveis. Bem vamos fazer um passo de cada vez. Sabemos que o gerador

49
00:03:53,887 --> 00:03:58,028
é um gerador de segura, portanto, de facto, a saída do primeiro nível é

50
00:03:58,028 --> 00:04:02,453
indistinguível da aleatória. Em outras palavras, se se substituir o primeiro nível por

51
00:04:02,453 --> 00:04:06,991
seqüências verdadeiramente aleatórias estes dois são verdadeiramente aleatórios colhidos na tecla de espaço, então não

52
00:04:10,267 --> 00:04:11,359
adversário eficiente deve ser capaz de distinguir essas duas distribuições. Em

53
00:04:11,359 --> 00:04:15,954
fato, se você pudesse distinguir estas duas distribuições, é fácil mostrar que você

54
00:04:15,954 --> 00:04:20,768
iria quebrar o PRG original. Ok, mas essencialmente você ver que a razão pela qual podemos

55
00:04:20,768 --> 00:04:25,581
fazer esta substituição, pode-se substituir a saída de G, com valores verdadeiramente aleatório, é

56
00:04:25,581 --> 00:04:30,578
exatamente por causa da definição do PRG, que diz que o posto para fora do PRG é

57
00:04:30,578 --> 00:04:35,391
indistinguível de forma aleatória, por isso pode muito bem colocar aleatório lá, e não

58
00:04:35,391 --> 00:04:40,265
adversário eficiente pode distinguir os resultantes duas distribuições. Ok, até agora

59
00:04:40,265 --> 00:04:45,018
tão bom, mas agora podemos fazer a mesma coisa de novo para o lado esquerdo. Em outro

60
00:04:45,018 --> 00:04:49,710
palavras, podemos substituir estes dois pseudo saídas aleatórias, pelas saídas verdadeiramente aleatórios.

61
00:04:49,710 --> 00:04:53,925
E novamente, pois o gerador G é seguro, eficiente nenhum adversário pode dizer

62
00:04:54,091 --> 00:04:57,807
a diferença entre estas duas distribuições. Mas de maneira diferente, se um

63
00:04:57,807 --> 00:05:02,077
adversário pode distinguir estas duas distribuições, então nós também daria uma

64
00:05:02,077 --> 00:05:06,707
ataque ao gerador de G. E agora finalmente nós vamos fazer isso uma última vez. Estamos

65
00:05:06,707 --> 00:05:11,280
vai substituir este par pseudo-aleatório por um par verdadeiramente aleatório, e baixo e eis que

66
00:05:11,280 --> 00:05:15,672
obter a distribuição real de que nós estávamos gravando para, gostaríamos de obter uma distribuição

67
00:05:15,672 --> 00:05:19,851
que é realmente feito de quatro blocos independentes. E agora temos provado isso

68
00:05:19,851 --> 00:05:23,279
transição, basicamente, que estes dois indistinguíveis, estes dois

69
00:05:23,279 --> 00:05:27,243
indistinguíveis, e estes dois indistinguíveis, e, portanto, estes dois

70
00:05:27,243 --> 00:05:31,475
são indistinguíveis, que é o que queríamos provar. Ok então este é o tipo de

71
00:05:31,475 --> 00:05:35,760
a idéia de alto nível para a prova, não é muito difícil fazer este rigoroso,

72
00:05:35,760 --> 00:05:39,792
, mas eu só queria mostrar-lhe a intuição meio de como a prova funciona. Bem,

73
00:05:39,792 --> 00:05:44,363
se fôssemos capazes de estender as saídas de geradores de uma vez, não há nada que impeça

74
00:05:44,363 --> 00:05:48,822
nos de fazê-lo novamente por isso aqui é um gerador G1 que produz quatro elementos em

75
00:05:48,822 --> 00:05:53,337
espaço a chave. E lembre-se a saída aqui é indistinguível do nosso aleatória

76
00:05:53,337 --> 00:05:57,909
par quatro, que é o que acabamos de provar. E então não há nada que nos impede de

77
00:05:57,909 --> 00:06:02,480
aplicando o gerador de novo. Então vamos dar o gerador de aplicá-la a este aleatório

78
00:06:02,480 --> 00:06:07,221
procurando coisa e devemos ser capazes de obter essa coisa aleatória procurando. Este par mais

79
00:06:07,221 --> 00:06:11,511
aqui que é aleatória procurando. E nós podemos fazer a mesma coisa novamente, e novamente, e

80
00:06:11,511 --> 00:06:16,405
novamente. E agora, basicamente, nós construímos um novo gerador que produz elementos em K para

81
00:06:16,405 --> 00:06:21,261
oitavo a, em oposição a K para a quarta. E mais uma vez a prova de segurança é muito

82
00:06:21,261 --> 00:06:26,056
da mesma forma como o que acabei de mostrar, essencialmente, você alterar gradualmente a

83
00:06:26,056 --> 00:06:30,612
saídas em saídas verdadeiramente aleatórios. Então nós mudar isso para um verdadeiramente aleatório

84
00:06:30,612 --> 00:06:35,168
de saída, então este, em seguida, que, em seguida, este, em seguida, que e assim por diante e assim por diante. Até

85
00:06:35,168 --> 00:06:39,724
finalmente temos algo que é verdadeiramente aleatório e, portanto, os dois originais

86
00:06:39,724 --> 00:06:44,396
distribuições nós começamos com G2K e verdadeiramente aleatório são indistinguíveis. Ok,

87
00:06:44,396 --> 00:06:49,325
tão longe tão bom. Portanto, agora temos um gerador que produz elementos em K para o oitavo.

88
00:06:49,325 --> 00:06:54,016
Agora, se fizermos isso, basicamente, temos um bit PRF três. Em outras palavras, a zero, zero,

89
00:06:54,016 --> 00:06:58,884
de zero esta PRF geraria este bloco, e assim por diante e assim por diante, até que um, um, um que

90
00:06:58,884 --> 00:07:03,163
geraria este bloco. Agora, o interessante é que na verdade isso PRF

91
00:07:03,163 --> 00:07:07,695
é fácil de calcular. Por exemplo, vamos supor que queremos para calcular a PRF no ponto

92
00:07:07,695 --> 00:07:11,948
um zero um. Ok, é um pouco PRF três. Ok então um zero um. Como faríamos

93
00:07:11,948 --> 00:07:16,536
que? Bem, basicamente, que iria começar a partir do original chave K. E agora gostaríamos de aplicar

94
00:07:16,536 --> 00:07:20,620
G o gerador, mas nós só prestar atenção ao direito de saída G,

95
00:07:20,620 --> 00:07:25,040
porque o primeiro bit é um. E então vamos aplicar o gerador de novo, mas nós

96
00:07:25,040 --> 00:07:29,516
só prestar atenção para a esquerda da saída do gerador porque o

97
00:07:29,516 --> 00:07:33,864
segundo bit é zero. E, então, se aplicaria o gerador de novo e só paga

98
00:07:33,864 --> 00:07:38,588
atenção para as saídas da direita, porque o terceiro bit é um e que seria o

99
00:07:38,588 --> 00:07:43,140
saída final. Certo, então você pode ver que, que nos levam a 101, e, de fato, porque

100
00:07:43,140 --> 00:07:47,461
gerador [inaudível] é pseudo-aleatório, sabemos que, em particular, que,

101
00:07:47,461 --> 00:07:52,796
esta saída aqui é pseudo-aleatório. Ok, então isso nos dá um pouco PRF três. Bem, se

102
00:07:52,796 --> 00:07:58,632
ele trabalhou três vezes, não há nenhuma razão pela qual não podem trabalhar N vezes. E assim se

103
00:07:58,632 --> 00:08:03,501
aplicar esta transformação mais uma vez, chegamos ao que é chamado de GGMPRF. GGM

104
00:08:03,501 --> 00:08:07,956
estandes para Goldreich, Goldwasser e Micali estes são os inventores do

105
00:08:07,956 --> 00:08:12,528
PRF isso e assim que funciona é o seguinte. Então, começamos com um gerador

106
00:08:12,528 --> 00:08:17,279
apenas dobra suas saídas, e agora nós somos capazes de construir um PRF que atua em um grande

107
00:08:17,279 --> 00:08:22,236
domínio principalmente um domínio de tamanho zero um para o N. ou N poderia ser tão grande como 128 ou mesmo

108
00:08:22,236 --> 00:08:26,897
mais. Então vamos ver, vamos supor que nós estamos dando uma entrada em 01 para o N, deixe-me mostrar-lhe como

109
00:08:26,897 --> 00:08:31,274
para avaliar a PRF. Bem, agora você deve realmente ter uma boa idéia de como

110
00:08:31,274 --> 00:08:35,480
para fazê-lo. Essencialmente, nós começamos a partir da chave original e, em seguida, aplicamos o

111
00:08:35,480 --> 00:08:40,255
gerador e tomamos a esquerda ou a direita dependendo do bit X0 e

112
00:08:40,255 --> 00:08:44,746
, em seguida, chegamos à próxima chave, K1. E, então, aplicar o gerador de novo e nós

113
00:08:44,746 --> 00:08:49,444
tomar à esquerda ou à direita dependendo X1 e chegamos à próxima chave. E

114
00:08:49,444 --> 00:08:54,730
então fazer isso de novo e de novo, até que finalmente estamos a chegar à saída. Então, nós

115
00:08:54,730 --> 00:08:59,818
ter processado todos os bits finais, e chegamos à saída desta função. E

116
00:08:59,818 --> 00:09:05,170
, basicamente, podemos provar a segurança de novo muito bonito ao longo das mesmas linhas como fizemos

117
00:09:05,170 --> 00:09:10,324
antes, e nós podemos mostrar que se G é um PRG seguro, então, de facto, temos um seguro

118
00:09:10,324 --> 00:09:14,917
PRF, a 01 para o N, em um domínio muito grande. Então, isso é fantástico. Agora, temos

119
00:09:14,917 --> 00:09:19,064
temos essencial, temos uma PRF que é comprovadamente seguro, assumindo que o

120
00:09:19,064 --> 00:09:23,495
gerador subjacente é seguro, eo gerador é supostamente muito mais fácil

121
00:09:23,495 --> 00:09:28,153
construir do que um PRF real. E, na verdade ele funciona em blocos que podem ser muito grandes, em

122
00:09:28,153 --> 00:09:33,296
particular, 01 ao 128, que é o que precisávamos. Então você pode perguntar por que não é bem

123
00:09:33,296 --> 00:09:39,122
coisa esta sendo usado na prática? E a razão é, que na verdade é bastante lento.

124
00:09:39,122 --> 00:09:44,597
Então, imagine que ligar como um gerador que conecta o gerador de salsa. Então agora para

125
00:09:44,597 --> 00:09:50,142
avaliar este PRF em um 128 entradas de bits, teríamos basicamente tem que executar o salsa

126
00:09:50,142 --> 00:09:55,617
gerador 128 vezes. Uma vez por bit da entrada. Mas, então, teria um PRF

127
00:09:55,617 --> 00:10:01,513
que é 128 vezes mais lenta do que a salsa original. E isso é muito, muito, muito mais lento

128
00:10:01,513 --> 00:10:06,227
que o AES. AES é um PRF heurística. Mas, no entanto, é muito mais rápido, então o que nós

129
00:10:06,227 --> 00:10:10,585
acabou de chegar aqui. E por isso mesmo que esta é uma construção muito elegante, ela não é usada

130
00:10:10,585 --> 00:10:14,522
, na prática, para construir pseudo funções aleatórias, embora em uma semana estaremos

131
00:10:14,522 --> 00:10:18,915
usando este tipo de construção para construir um mecanismo de integridade da mensagem. Assim, a última

132
00:10:18,915 --> 00:10:23,183
passo, é basicamente agora que temos construído um PRF, as perguntas é se podemos

133
00:10:23,183 --> 00:10:27,729
realmente construir a cifra de bloco. Em outras palavras, podemos realmente construir uma PRP seguro

134
00:10:27,729 --> 00:10:32,054
a partir de um PRG seguro. Tudo o que fizemos até agora, não é reversível. Novamente, se você

135
00:10:32,054 --> 00:10:36,600
olhar para essa construção aqui, não podemos decifrar, basicamente devido aos resultados finais.

136
00:10:36,600 --> 00:10:40,535
Não é possível voltar atrás ou, pelo menos, não sabemos como voltar a, o

137
00:10:40,535 --> 00:10:44,520
entradas originais. Então agora a questão de interesse é tão podemos realmente resolver o

138
00:10:44,520 --> 00:10:48,654
problema que queria resolver inicialmente? Principalmente, podemos realmente construir uma cifra de bloco de

139
00:10:48,654 --> 00:10:53,540
um PRG seguro? Tão mal deixá-lo pensar sobre isso por um segundo, e marcar a resposta. Assim

140
00:10:53,540 --> 00:10:57,718
é claro que eu espero que todos disse que a resposta é sim e você já tem todos os

141
00:10:57,718 --> 00:11:01,896
ingredientes para fazê-lo. Em particular, você já sabe como construir um PRF de um

142
00:11:01,896 --> 00:11:06,395
gerador pseudo-aleatório. E nós dissemos que uma vez que temos um PRF que podemos ligá-lo na

143
00:11:06,395 --> 00:11:10,573
construção Luby-Rackoff, que se você se lembra, é apenas Feistel um três-redonda.

144
00:11:10,573 --> 00:11:14,750
Então nós dissemos que se você ligar um PRF seguro em um Feistel de três rounds, você recebe um

145
00:11:14,750 --> 00:11:19,044
PRP seguro. Então, combinando estes dois, basicamente nos dá uma PRP seguro

146
00:11:19,044 --> 00:11:23,328
a partir de um gerador pseudo-aleatório. E isto é provably assegurar enquanto o

147
00:11:23,328 --> 00:11:28,075
gerador subjacente é segura. Portanto, é um belo resultado, mas infelizmente mais uma vez

148
00:11:28,075 --> 00:11:32,475
ela não é usada na prática porque é consideravelmente mais lento que a heurística

149
00:11:32,475 --> 00:11:36,725
construções como AES. Ok assim que este completa o nosso módulo sobre construção

150
00:11:36,725 --> 00:11:40,456
pseudo permutações aleatórias e pseudo funções aleatórias. E, em seguida, no próximo

151
00:11:40,456 --> 00:11:44,287
módulo nós vamos falar sobre como usar essas coisas para fazer a criptografia apropriada.