0:00:00.000,0:00:04.388
Neste segmento perguntamos se podemos construir a partir de cifras de bloco simples

0:00:04.388,0:00:09.456
primitivos como pseudo geradores aleatórios. A resposta é sim. Então, para começar, vamos

0:00:09.456,0:00:14.215
perguntar se podemos construir pseudo funções aleatórias em vez de pseudo-aleatório

0:00:14.215,0:00:18.789
permutações de um gerador pseudo-aleatório. Podemos construir um PRF de um PRG?

0:00:18.789,0:00:23.873
Nosso objetivo final que é construir uma cifra de bloco que é um PRP. E nós vamos chegar

0:00:23.873,0:00:29.130
a que, no final. Ok, agora vamos construir um PRF. Então vamos começar com um PRG que

0:00:29.130,0:00:34.590
dobra suas entradas de modo as sementes para o PRG é um elemento em K ea saída é

0:00:34.590,0:00:39.420
, na verdade, dois elementos em K. Portanto, aqui temos um esquema do gerador, que

0:00:39.420,0:00:44.296
basicamente tem sua entrada de C e K, e saídas de dois elementos, em K, como sua saída.

0:00:44.296,0:00:48.992
E agora o que significa para essa pureza para ser seguro, lembre-se isto significa que

0:00:48.992,0:00:52.965
essencialmente a saída é indistinguível de um elemento aleatório

0:00:52.965,0:00:58.355
dentro de K quadrado Agora verifica-se que é muito fácil definir basicamente o que é

0:00:58.355,0:01:03.455
chamado uma PRF bit um a partir deste PRG. Então, o que é um pouco um PRF é basicamente um PRF

0:01:03.455,0:01:08.360
domínio que é apenas um bit. Ok, então é um PRF que só leva um pouco como

0:01:08.360,0:01:13.461
de entrada. Ok, ea forma como vamos fazê-lo é que vai dizer é se o X bit de entrada é zero

0:01:13.461,0: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

0:01:18.627,0:01:23.678
saída do PRF. Ok, em símbolos, temos basicamente o que escrevi aqui. Agora

0:01:23.678,0:01:28.523
é simples para mostrar que, de facto, G é um PRG segura, então este bit PRF um é

0:01:28.523,0:01:32.901
, de facto, uma PRF seguro. Se você pensar nisso por um segundo, isso realmente não é

0:01:32.901,0:01:37.571
[inaudível]. É realmente apenas afirmando a mesma coisa duas vezes. Então eu vou deixá-lo por

0:01:37.571,0:01:42.241
você pensar sobre isso de forma breve e ver e se convencer de que de fato esta

0:01:42.241,0:01:46.853
teorema é verdadeiro. As verdadeiras questões é se podemos construir um PRF, que na verdade

0:01:46.853,0:01:51.756
tem um domínio que é maior do que um bit. Idealmente gostaríamos que o domínio para ser 128

0:01:51.756,0:01:56.425
bits, basta dizer que a [inaudível] tem. Então a questão é que podemos construir 128 bits PRS

0:01:56.425,0:02:01.197
a partir de um gerador pseudo-aleatório. Bem, então vamos ver se podemos fazer progressos. Assim, o

0:02:01.197,0:02:05.970
primeira coisa que vamos fazer é que nós vamos dizer, bem de novo, vamos começar com um PRG

0:02:05.970,0:02:10.863
, que duplica o seu contributo vamos ver se podemos construir um PRG que quadruplica suas entradas.

0:02:10.863,0: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

0:02:15.797,0:02:20.809
ver como fazer isso. Então, vamos começar com a nossa PRG original que apenas duplica a sua

0:02:20.809,0:02:25.884
entradas, agora lembrar que o facto de a sua é um PRG significa que a saída do

0:02:25.884,0:02:30.771
PRG é indistinguível de dois valores aleatórios em K. Bem, se a saída se parece

0:02:30.771,0:02:35.847
como dois valores aleatórios em K, podemos simplesmente aplicar o gerador de novo para os dois

0:02:35.847,0:02:40.358
saídas. Então, digamos que nós aplicamos o gerador de uma vez para a saída da esquerda, e

0:02:40.358,0:02:45.342
uma vez para as saídas de direitos. E nós vamos chamar a saída de que, este

0:02:45.342,0:02:50.448
quádruplo de elementos, que são, vão chamar isso de G1K. E eu escrevi em

0:02:50.448,0:02:55.554
símbolos que esse gerador faz, mas você pode ver, basicamente, a partir desta figura,

0:02:55.554,0:03:00.862
exatamente como funciona o gerador. Portanto, agora que temos um gerador de K a K para

0:03:00.862,0:03:06.170
quarta, Nós realmente obter um pouco PRF dois. Ou seja, o que vamos fazer é, vamos dizer,

0:03:06.170,0:03:11.410
dado dois bits, 000110 ou 11, vontades implica a saída do bloco apropriado que

0:03:11.410,0:03:16.070
saída de G1K. Ok, então agora podemos basicamente ter um PRF que leva quatro

0:03:16.070,0:03:21.061
entradas possíveis ao invés de apenas duas entradas possíveis como antes. Portanto, a questão

0:03:21.061,0:03:26.113
você deve estar me perguntando é porque é que este caso G1 seguro? Por que é um PRG seguro? Que

0:03:26.113,0:03:30.611
é por que isso é quadruplicar de saídas indistinguíveis de forma aleatória. E assim

0:03:30.611,0:03:35.664
vamos fazer uma prova rápida de isso, apenas vou fazer uma prova simples por imagens. Então aqui está

0:03:35.664,0:03:40.408
gerador nossa que queremos provar é seguro. E o que isso significa é que nós

0:03:40.408,0:03:45.399
quero argumentar que essa distribuição é indistinguível de um fordable aleatória

0:03:45.399,0:03:49.292
em K para a quarta. Ok então nosso objetivo é provar que esses dois são

0:03:49.292,0:03:53.887
indistinguíveis. Bem vamos fazer um passo de cada vez. Sabemos que o gerador

0:03:53.887,0:03:58.028
é um gerador de segura, portanto, de facto, a saída do primeiro nível é

0:03:58.028,0:04:02.453
indistinguível da aleatória. Em outras palavras, se se substituir o primeiro nível por

0:04:02.453,0: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

0:04:10.267,0:04:11.359
adversário eficiente deve ser capaz de distinguir essas duas distribuições. Em

0:04:11.359,0:04:15.954
fato, se você pudesse distinguir estas duas distribuições, é fácil mostrar que você

0:04:15.954,0:04:20.768
iria quebrar o PRG original. Ok, mas essencialmente você ver que a razão pela qual podemos

0:04:20.768,0:04:25.581
fazer esta substituição, pode-se substituir a saída de G, com valores verdadeiramente aleatório, é

0:04:25.581,0:04:30.578
exatamente por causa da definição do PRG, que diz que o posto para fora do PRG é

0:04:30.578,0:04:35.391
indistinguível de forma aleatória, por isso pode muito bem colocar aleatório lá, e não

0:04:35.391,0:04:40.265
adversário eficiente pode distinguir os resultantes duas distribuições. Ok, até agora

0:04:40.265,0:04:45.018
tão bom, mas agora podemos fazer a mesma coisa de novo para o lado esquerdo. Em outro

0:04:45.018,0:04:49.710
palavras, podemos substituir estes dois pseudo saídas aleatórias, pelas saídas verdadeiramente aleatórios.

0:04:49.710,0:04:53.925
E novamente, pois o gerador G é seguro, eficiente nenhum adversário pode dizer

0:04:54.091,0:04:57.807
a diferença entre estas duas distribuições. Mas de maneira diferente, se um

0:04:57.807,0:05:02.077
adversário pode distinguir estas duas distribuições, então nós também daria uma

0:05:02.077,0:05:06.707
ataque ao gerador de G. E agora finalmente nós vamos fazer isso uma última vez. Estamos

0:05:06.707,0:05:11.280
vai substituir este par pseudo-aleatório por um par verdadeiramente aleatório, e baixo e eis que

0:05:11.280,0:05:15.672
obter a distribuição real de que nós estávamos gravando para, gostaríamos de obter uma distribuição

0:05:15.672,0:05:19.851
que é realmente feito de quatro blocos independentes. E agora temos provado isso

0:05:19.851,0:05:23.279
transição, basicamente, que estes dois indistinguíveis, estes dois

0:05:23.279,0:05:27.243
indistinguíveis, e estes dois indistinguíveis, e, portanto, estes dois

0:05:27.243,0:05:31.475
são indistinguíveis, que é o que queríamos provar. Ok então este é o tipo de

0:05:31.475,0:05:35.760
a idéia de alto nível para a prova, não é muito difícil fazer este rigoroso,

0:05:35.760,0:05:39.792
, mas eu só queria mostrar-lhe a intuição meio de como a prova funciona. Bem,

0:05:39.792,0:05:44.363
se fôssemos capazes de estender as saídas de geradores de uma vez, não há nada que impeça

0:05:44.363,0:05:48.822
nos de fazê-lo novamente por isso aqui é um gerador G1 que produz quatro elementos em

0:05:48.822,0:05:53.337
espaço a chave. E lembre-se a saída aqui é indistinguível do nosso aleatória

0:05:53.337,0:05:57.909
par quatro, que é o que acabamos de provar. E então não há nada que nos impede de

0:05:57.909,0:06:02.480
aplicando o gerador de novo. Então vamos dar o gerador de aplicá-la a este aleatório

0:06:02.480,0:06:07.221
procurando coisa e devemos ser capazes de obter essa coisa aleatória procurando. Este par mais

0:06:07.221,0:06:11.511
aqui que é aleatória procurando. E nós podemos fazer a mesma coisa novamente, e novamente, e

0:06:11.511,0:06:16.405
novamente. E agora, basicamente, nós construímos um novo gerador que produz elementos em K para

0:06:16.405,0:06:21.261
oitavo a, em oposição a K para a quarta. E mais uma vez a prova de segurança é muito

0:06:21.261,0:06:26.056
da mesma forma como o que acabei de mostrar, essencialmente, você alterar gradualmente a

0:06:26.056,0:06:30.612
saídas em saídas verdadeiramente aleatórios. Então nós mudar isso para um verdadeiramente aleatório

0:06:30.612,0: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é

0:06:35.168,0:06:39.724
finalmente temos algo que é verdadeiramente aleatório e, portanto, os dois originais

0:06:39.724,0:06:44.396
distribuições nós começamos com G2K e verdadeiramente aleatório são indistinguíveis. Ok,

0:06:44.396,0:06:49.325
tão longe tão bom. Portanto, agora temos um gerador que produz elementos em K para o oitavo.

0:06:49.325,0:06:54.016
Agora, se fizermos isso, basicamente, temos um bit PRF três. Em outras palavras, a zero, zero,

0:06:54.016,0:06:58.884
de zero esta PRF geraria este bloco, e assim por diante e assim por diante, até que um, um, um que

0:06:58.884,0:07:03.163
geraria este bloco. Agora, o interessante é que na verdade isso PRF

0:07:03.163,0:07:07.695
é fácil de calcular. Por exemplo, vamos supor que queremos para calcular a PRF no ponto

0:07:07.695,0:07:11.948
um zero um. Ok, é um pouco PRF três. Ok então um zero um. Como faríamos

0:07:11.948,0:07:16.536
que? Bem, basicamente, que iria começar a partir do original chave K. E agora gostaríamos de aplicar

0:07:16.536,0:07:20.620
G o gerador, mas nós só prestar atenção ao direito de saída G,

0:07:20.620,0:07:25.040
porque o primeiro bit é um. E então vamos aplicar o gerador de novo, mas nós

0:07:25.040,0:07:29.516
só prestar atenção para a esquerda da saída do gerador porque o

0:07:29.516,0:07:33.864
segundo bit é zero. E, então, se aplicaria o gerador de novo e só paga

0:07:33.864,0:07:38.588
atenção para as saídas da direita, porque o terceiro bit é um e que seria o

0:07:38.588,0:07:43.140
saída final. Certo, então você pode ver que, que nos levam a 101, e, de fato, porque

0:07:43.140,0:07:47.461
gerador [inaudível] é pseudo-aleatório, sabemos que, em particular, que,

0:07:47.461,0:07:52.796
esta saída aqui é pseudo-aleatório. Ok, então isso nos dá um pouco PRF três. Bem, se

0:07:52.796,0: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

0:07:58.632,0:08:03.501
aplicar esta transformação mais uma vez, chegamos ao que é chamado de GGMPRF. GGM

0:08:03.501,0:08:07.956
estandes para Goldreich, Goldwasser e Micali estes são os inventores do

0:08:07.956,0:08:12.528
PRF isso e assim que funciona é o seguinte. Então, começamos com um gerador

0:08:12.528,0:08:17.279
apenas dobra suas saídas, e agora nós somos capazes de construir um PRF que atua em um grande

0:08:17.279,0: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

0:08:22.236,0: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

0:08:26.897,0:08:31.274
para avaliar a PRF. Bem, agora você deve realmente ter uma boa idéia de como

0:08:31.274,0:08:35.480
para fazê-lo. Essencialmente, nós começamos a partir da chave original e, em seguida, aplicamos o

0:08:35.480,0:08:40.255
gerador e tomamos a esquerda ou a direita dependendo do bit X0 e

0:08:40.255,0:08:44.746
, em seguida, chegamos à próxima chave, K1. E, então, aplicar o gerador de novo e nós

0:08:44.746,0:08:49.444
tomar à esquerda ou à direita dependendo X1 e chegamos à próxima chave. E

0:08:49.444,0:08:54.730
então fazer isso de novo e de novo, até que finalmente estamos a chegar à saída. Então, nós

0:08:54.730,0:08:59.818
ter processado todos os bits finais, e chegamos à saída desta função. E

0:08:59.818,0:09:05.170
, basicamente, podemos provar a segurança de novo muito bonito ao longo das mesmas linhas como fizemos

0:09:05.170,0:09:10.324
antes, e nós podemos mostrar que se G é um PRG seguro, então, de facto, temos um seguro

0:09:10.324,0:09:14.917
PRF, a 01 para o N, em um domínio muito grande. Então, isso é fantástico. Agora, temos

0:09:14.917,0:09:19.064
temos essencial, temos uma PRF que é comprovadamente seguro, assumindo que o

0:09:19.064,0:09:23.495
gerador subjacente é seguro, eo gerador é supostamente muito mais fácil

0:09:23.495,0:09:28.153
construir do que um PRF real. E, na verdade ele funciona em blocos que podem ser muito grandes, em

0:09:28.153,0:09:33.296
particular, 01 ao 128, que é o que precisávamos. Então você pode perguntar por que não é bem

0:09:33.296,0:09:39.122
coisa esta sendo usado na prática? E a razão é, que na verdade é bastante lento.

0:09:39.122,0:09:44.597
Então, imagine que ligar como um gerador que conecta o gerador de salsa. Então agora para

0:09:44.597,0:09:50.142
avaliar este PRF em um 128 entradas de bits, teríamos basicamente tem que executar o salsa

0:09:50.142,0:09:55.617
gerador 128 vezes. Uma vez por bit da entrada. Mas, então, teria um PRF

0:09:55.617,0:10:01.513
que é 128 vezes mais lenta do que a salsa original. E isso é muito, muito, muito mais lento

0:10:01.513,0:10:06.227
que o AES. AES é um PRF heurística. Mas, no entanto, é muito mais rápido, então o que nós

0:10:06.227,0:10:10.585
acabou de chegar aqui. E por isso mesmo que esta é uma construção muito elegante, ela não é usada

0:10:10.585,0:10:14.522
, na prática, para construir pseudo funções aleatórias, embora em uma semana estaremos

0:10:14.522,0:10:18.915
usando este tipo de construção para construir um mecanismo de integridade da mensagem. Assim, a última

0:10:18.915,0:10:23.183
passo, é basicamente agora que temos construído um PRF, as perguntas é se podemos

0:10:23.183,0:10:27.729
realmente construir a cifra de bloco. Em outras palavras, podemos realmente construir uma PRP seguro

0:10:27.729,0:10:32.054
a partir de um PRG seguro. Tudo o que fizemos até agora, não é reversível. Novamente, se você

0:10:32.054,0:10:36.600
olhar para essa construção aqui, não podemos decifrar, basicamente devido aos resultados finais.

0:10:36.600,0:10:40.535
Não é possível voltar atrás ou, pelo menos, não sabemos como voltar a, o

0:10:40.535,0:10:44.520
entradas originais. Então agora a questão de interesse é tão podemos realmente resolver o

0:10:44.520,0:10:48.654
problema que queria resolver inicialmente? Principalmente, podemos realmente construir uma cifra de bloco de

0:10:48.654,0:10:53.540
um PRG seguro? Tão mal deixá-lo pensar sobre isso por um segundo, e marcar a resposta. Assim

0:10:53.540,0:10:57.718
é claro que eu espero que todos disse que a resposta é sim e você já tem todos os

0:10:57.718,0:11:01.896
ingredientes para fazê-lo. Em particular, você já sabe como construir um PRF de um

0:11:01.896,0:11:06.395
gerador pseudo-aleatório. E nós dissemos que uma vez que temos um PRF que podemos ligá-lo na

0:11:06.395,0:11:10.573
construção Luby-Rackoff, que se você se lembra, é apenas Feistel um três-redonda.

0:11:10.573,0: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

0:11:14.750,0:11:19.044
PRP seguro. Então, combinando estes dois, basicamente nos dá uma PRP seguro

0:11:19.044,0:11:23.328
a partir de um gerador pseudo-aleatório. E isto é provably assegurar enquanto o

0:11:23.328,0:11:28.075
gerador subjacente é segura. Portanto, é um belo resultado, mas infelizmente mais uma vez

0:11:28.075,0:11:32.475
ela não é usada na prática porque é consideravelmente mais lento que a heurística

0:11:32.475,0:11:36.725
construções como AES. Ok assim que este completa o nosso módulo sobre construção

0:11:36.725,0:11:40.456
pseudo permutações aleatórias e pseudo funções aleatórias. E, em seguida, no próximo

0:11:40.456,0:11:44.287
módulo nós vamos falar sobre como usar essas coisas para fazer a criptografia apropriada.