Block ciphers from PRGs(12 min)

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.