Neste segmento perguntamos se podemos construir a partir de cifras de bloco simples
primitivos como pseudo geradores aleatórios. A resposta é sim. Então, para começar, vamos
perguntar se podemos construir pseudo funções aleatórias em vez de pseudo-aleatório
permutações de um gerador pseudo-aleatório. Podemos construir um PRF de um PRG?
Nosso objetivo final que é construir uma cifra de bloco que é um PRP. E nós vamos chegar
a que, no final. Ok, agora vamos construir um PRF. Então vamos começar com um PRG que
dobra suas entradas de modo as sementes para o PRG é um elemento em K ea saída é
, na verdade, dois elementos em K. Portanto, aqui temos um esquema do gerador, que
basicamente tem sua entrada de C e K, e saídas de dois elementos, em K, como sua saída.
E agora o que significa para essa pureza para ser seguro, lembre-se isto significa que
essencialmente a saída é indistinguível de um elemento aleatório
dentro de K quadrado Agora verifica-se que é muito fácil definir basicamente o que é
chamado uma PRF bit um a partir deste PRG. Então, o que é um pouco um PRF é basicamente um PRF
domínio que é apenas um bit. Ok, então é um PRF que só leva um pouco como
de entrada. Ok, ea forma como vamos fazê-lo é que vai dizer é se o X bit de entrada é zero
eu vou colocar a saída esquerda e se o bit de entrada X é um, então eu vou colocar o direito
saída do PRF. Ok, em símbolos, temos basicamente o que escrevi aqui. Agora
é simples para mostrar que, de facto, G é um PRG segura, então este bit PRF um é
, de facto, uma PRF seguro. Se você pensar nisso por um segundo, isso realmente não é
[inaudível]. É realmente apenas afirmando a mesma coisa duas vezes. Então eu vou deixá-lo por
você pensar sobre isso de forma breve e ver e se convencer de que de fato esta
teorema é verdadeiro. As verdadeiras questões é se podemos construir um PRF, que na verdade
tem um domínio que é maior do que um bit. Idealmente gostaríamos que o domínio para ser 128
bits, basta dizer que a [inaudível] tem. Então a questão é que podemos construir 128 bits PRS
a partir de um gerador pseudo-aleatório. Bem, então vamos ver se podemos fazer progressos. Assim, o
primeira coisa que vamos fazer é que nós vamos dizer, bem de novo, vamos começar com um PRG
, que duplica o seu contributo vamos ver se podemos construir um PRG que quadruplica suas entradas.
Ok? Assim, ele vai de K para K para o quarto em vez de K para K quadrado. Ok, então vamos
ver como fazer isso. Então, vamos começar com a nossa PRG original que apenas duplica a sua
entradas, agora lembrar que o facto de a sua é um PRG significa que a saída do
PRG é indistinguível de dois valores aleatórios em K. Bem, se a saída se parece
como dois valores aleatórios em K, podemos simplesmente aplicar o gerador de novo para os dois
saídas. Então, digamos que nós aplicamos o gerador de uma vez para a saída da esquerda, e
uma vez para as saídas de direitos. E nós vamos chamar a saída de que, este
quádruplo de elementos, que são, vão chamar isso de G1K. E eu escrevi em
símbolos que esse gerador faz, mas você pode ver, basicamente, a partir desta figura,
exatamente como funciona o gerador. Portanto, agora que temos um gerador de K a K para
quarta, Nós realmente obter um pouco PRF dois. Ou seja, o que vamos fazer é, vamos dizer,
dado dois bits, 000110 ou 11, vontades implica a saída do bloco apropriado que
saída de G1K. Ok, então agora podemos basicamente ter um PRF que leva quatro
entradas possíveis ao invés de apenas duas entradas possíveis como antes. Portanto, a questão
você deve estar me perguntando é porque é que este caso G1 seguro? Por que é um PRG seguro? Que
é por que isso é quadruplicar de saídas indistinguíveis de forma aleatória. E assim
vamos fazer uma prova rápida de isso, apenas vou fazer uma prova simples por imagens. Então aqui está
gerador nossa que queremos provar é seguro. E o que isso significa é que nós
quero argumentar que essa distribuição é indistinguível de um fordable aleatória
em K para a quarta. Ok então nosso objetivo é provar que esses dois são
indistinguíveis. Bem vamos fazer um passo de cada vez. Sabemos que o gerador
é um gerador de segura, portanto, de facto, a saída do primeiro nível é
indistinguível da aleatória. Em outras palavras, se se substituir o primeiro nível por
seqüências verdadeiramente aleatórias estes dois são verdadeiramente aleatórios colhidos na tecla de espaço, então não
adversário eficiente deve ser capaz de distinguir essas duas distribuições. Em
fato, se você pudesse distinguir estas duas distribuições, é fácil mostrar que você
iria quebrar o PRG original. Ok, mas essencialmente você ver que a razão pela qual podemos
fazer esta substituição, pode-se substituir a saída de G, com valores verdadeiramente aleatório, é
exatamente por causa da definição do PRG, que diz que o posto para fora do PRG é
indistinguível de forma aleatória, por isso pode muito bem colocar aleatório lá, e não
adversário eficiente pode distinguir os resultantes duas distribuições. Ok, até agora
tão bom, mas agora podemos fazer a mesma coisa de novo para o lado esquerdo. Em outro
palavras, podemos substituir estes dois pseudo saídas aleatórias, pelas saídas verdadeiramente aleatórios.
E novamente, pois o gerador G é seguro, eficiente nenhum adversário pode dizer
a diferença entre estas duas distribuições. Mas de maneira diferente, se um
adversário pode distinguir estas duas distribuições, então nós também daria uma
ataque ao gerador de G. E agora finalmente nós vamos fazer isso uma última vez. Estamos
vai substituir este par pseudo-aleatório por um par verdadeiramente aleatório, e baixo e eis que
obter a distribuição real de que nós estávamos gravando para, gostaríamos de obter uma distribuição
que é realmente feito de quatro blocos independentes. E agora temos provado isso
transição, basicamente, que estes dois indistinguíveis, estes dois
indistinguíveis, e estes dois indistinguíveis, e, portanto, estes dois
são indistinguíveis, que é o que queríamos provar. Ok então este é o tipo de
a idéia de alto nível para a prova, não é muito difícil fazer este rigoroso,
, mas eu só queria mostrar-lhe a intuição meio de como a prova funciona. Bem,
se fôssemos capazes de estender as saídas de geradores de uma vez, não há nada que impeça
nos de fazê-lo novamente por isso aqui é um gerador G1 que produz quatro elementos em
espaço a chave. E lembre-se a saída aqui é indistinguível do nosso aleatória
par quatro, que é o que acabamos de provar. E então não há nada que nos impede de
aplicando o gerador de novo. Então vamos dar o gerador de aplicá-la a este aleatório
procurando coisa e devemos ser capazes de obter essa coisa aleatória procurando. Este par mais
aqui que é aleatória procurando. E nós podemos fazer a mesma coisa novamente, e novamente, e
novamente. E agora, basicamente, nós construímos um novo gerador que produz elementos em K para
oitavo a, em oposição a K para a quarta. E mais uma vez a prova de segurança é muito
da mesma forma como o que acabei de mostrar, essencialmente, você alterar gradualmente a
saídas em saídas verdadeiramente aleatórios. Então nós mudar isso para um verdadeiramente aleatório
de saída, então este, em seguida, que, em seguida, este, em seguida, que e assim por diante e assim por diante. Até
finalmente temos algo que é verdadeiramente aleatório e, portanto, os dois originais
distribuições nós começamos com G2K e verdadeiramente aleatório são indistinguíveis. Ok,
tão longe tão bom. Portanto, agora temos um gerador que produz elementos em K para o oitavo.
Agora, se fizermos isso, basicamente, temos um bit PRF três. Em outras palavras, a zero, zero,
de zero esta PRF geraria este bloco, e assim por diante e assim por diante, até que um, um, um que
geraria este bloco. Agora, o interessante é que na verdade isso PRF
é fácil de calcular. Por exemplo, vamos supor que queremos para calcular a PRF no ponto
um zero um. Ok, é um pouco PRF três. Ok então um zero um. Como faríamos
que? Bem, basicamente, que iria começar a partir do original chave K. E agora gostaríamos de aplicar
G o gerador, mas nós só prestar atenção ao direito de saída G,
porque o primeiro bit é um. E então vamos aplicar o gerador de novo, mas nós
só prestar atenção para a esquerda da saída do gerador porque o
segundo bit é zero. E, então, se aplicaria o gerador de novo e só paga
atenção para as saídas da direita, porque o terceiro bit é um e que seria o
saída final. Certo, então você pode ver que, que nos levam a 101, e, de fato, porque
gerador [inaudível] é pseudo-aleatório, sabemos que, em particular, que,
esta saída aqui é pseudo-aleatório. Ok, então isso nos dá um pouco PRF três. Bem, se
ele trabalhou três vezes, não há nenhuma razão pela qual não podem trabalhar N vezes. E assim se
aplicar esta transformação mais uma vez, chegamos ao que é chamado de GGMPRF. GGM
estandes para Goldreich, Goldwasser e Micali estes são os inventores do
PRF isso e assim que funciona é o seguinte. Então, começamos com um gerador
apenas dobra suas saídas, e agora nós somos capazes de construir um PRF que atua em um grande
domínio principalmente um domínio de tamanho zero um para o N. ou N poderia ser tão grande como 128 ou mesmo
mais. Então vamos ver, vamos supor que nós estamos dando uma entrada em 01 para o N, deixe-me mostrar-lhe como
para avaliar a PRF. Bem, agora você deve realmente ter uma boa idéia de como
para fazê-lo. Essencialmente, nós começamos a partir da chave original e, em seguida, aplicamos o
gerador e tomamos a esquerda ou a direita dependendo do bit X0 e
, em seguida, chegamos à próxima chave, K1. E, então, aplicar o gerador de novo e nós
tomar à esquerda ou à direita dependendo X1 e chegamos à próxima chave. E
então fazer isso de novo e de novo, até que finalmente estamos a chegar à saída. Então, nós
ter processado todos os bits finais, e chegamos à saída desta função. E
, basicamente, podemos provar a segurança de novo muito bonito ao longo das mesmas linhas como fizemos
antes, e nós podemos mostrar que se G é um PRG seguro, então, de facto, temos um seguro
PRF, a 01 para o N, em um domínio muito grande. Então, isso é fantástico. Agora, temos
temos essencial, temos uma PRF que é comprovadamente seguro, assumindo que o
gerador subjacente é seguro, eo gerador é supostamente muito mais fácil
construir do que um PRF real. E, na verdade ele funciona em blocos que podem ser muito grandes, em
particular, 01 ao 128, que é o que precisávamos. Então você pode perguntar por que não é bem
coisa esta sendo usado na prática? E a razão é, que na verdade é bastante lento.
Então, imagine que ligar como um gerador que conecta o gerador de salsa. Então agora para
avaliar este PRF em um 128 entradas de bits, teríamos basicamente tem que executar o salsa
gerador 128 vezes. Uma vez por bit da entrada. Mas, então, teria um PRF
que é 128 vezes mais lenta do que a salsa original. E isso é muito, muito, muito mais lento
que o AES. AES é um PRF heurística. Mas, no entanto, é muito mais rápido, então o que nós
acabou de chegar aqui. E por isso mesmo que esta é uma construção muito elegante, ela não é usada
, na prática, para construir pseudo funções aleatórias, embora em uma semana estaremos
usando este tipo de construção para construir um mecanismo de integridade da mensagem. Assim, a última
passo, é basicamente agora que temos construído um PRF, as perguntas é se podemos
realmente construir a cifra de bloco. Em outras palavras, podemos realmente construir uma PRP seguro
a partir de um PRG seguro. Tudo o que fizemos até agora, não é reversível. Novamente, se você
olhar para essa construção aqui, não podemos decifrar, basicamente devido aos resultados finais.
Não é possível voltar atrás ou, pelo menos, não sabemos como voltar a, o
entradas originais. Então agora a questão de interesse é tão podemos realmente resolver o
problema que queria resolver inicialmente? Principalmente, podemos realmente construir uma cifra de bloco de
um PRG seguro? Tão mal deixá-lo pensar sobre isso por um segundo, e marcar a resposta. Assim
é claro que eu espero que todos disse que a resposta é sim e você já tem todos os
ingredientes para fazê-lo. Em particular, você já sabe como construir um PRF de um
gerador pseudo-aleatório. E nós dissemos que uma vez que temos um PRF que podemos ligá-lo na
construção Luby-Rackoff, que se você se lembra, é apenas Feistel um três-redonda.
Então nós dissemos que se você ligar um PRF seguro em um Feistel de três rounds, você recebe um
PRP seguro. Então, combinando estes dois, basicamente nos dá uma PRP seguro
a partir de um gerador pseudo-aleatório. E isto é provably assegurar enquanto o
gerador subjacente é segura. Portanto, é um belo resultado, mas infelizmente mais uma vez
ela não é usada na prática porque é consideravelmente mais lento que a heurística
construções como AES. Ok assim que este completa o nosso módulo sobre construção
pseudo permutações aleatórias e pseudo funções aleatórias. E, em seguida, no próximo
módulo nós vamos falar sobre como usar essas coisas para fazer a criptografia apropriada.