Constructions (11 min)

No último segmento, o que é explicado que um sistema de criptografia de chave pública. E nós

definido o que isso significa para um sistema de criptografia de chave pública para ser seguro. Se você

lembre-se, necessária segurança contra ataques ativos. E, em particular, nós

segurança texto definido da cifra escolhida como nossa meta. Esta semana, nós vamos construir dois

famílias de sistemas públicos de criptografia de chave que são escolhidos texto cifrado seguro. E em

este segmento, nós vamos começar pela construção de públicos-chave de criptografia,

um conceito chamado de um alçapão permutação. Então vamos começar pela definição de um

conceito geral chamada uma função alçapão. Então, o que é uma função alçapão?

Bem, uma função de alçapão, basicamente, é uma função que vai de algum conjunto X para alguns

conjunto Y. E é realmente definido por um triplo de algoritmos. Há uma geração

algoritmo, a função f, eo inverso da função f. Assim, a geração

algoritmo, basicamente o que ele faz quando você executá-lo, ele irá gerar um par de chaves, uma

chave pública e uma chave secreta. A chave pública vai definir uma função específica

a partir do conjunto X para o Y. conjunto E, então, a chave secreta que vai definir o inverso

função agora da Y definido para o conjunto X. Então a idéia é que você pode avaliar

função em qualquer ponto usando um PK de chave pública e, em seguida, você pode inverter essa função

usando a chave secreta, SK. Então, o que quero dizer com inversão? Mais precisamente, se

olhada em qualquer par de chaves e segredo de chave pública gerada pelo algoritmo de geração de chaves

G, em seguida, acontece que se eu avaliar a função no ponto X, e então eu

avaliar o inverso no ponto resultante, eu deveria receber o X ponto original

para trás. Assim, a imagem que você deve ter em sua mente, há é este conjunto X grande e

este grande conjunto Y E então, esta função irá mapear qualquer ponto X a um ponto em Y,

e isto pode ser feito usando a chave pública. Assim, novamente, em qualquer ponto X pode ser mapeado para

um ponto no Y. E, então, se alguém tem a chave secreta, então basicamente eles podem ir em

direção inversa, aplicando, este sk chave secreta. Assim agora que nós

entender o que é uma função de alçapão, vamos definir o que significa para um alçapão

função para ser seguro. E por isso vamos dizer que este triplo, (G, F, F inversa), é seguro

se de fato essa função F (PK.) é o que se chama uma função de uma maneira. E deixe-me

explicar o que uma, o que é uma função de uma maneira. A ideia é que, basicamente, o

função pode ser avaliada em qualquer ponto, mas invertendo é difícil sem a

SK chave secreta. Portanto, vamos definir que com mais precisão. Como de costume, definir que o uso de uma

jogo. Então aqui temos o nosso jogo entre o desafiante eo adversário. E o jogo

procede como se segue. Basicamente, o desafiante irá gerar uma chave pública e

uma chave secreta. E então eles vão gerar um aleatório X. Ele vai enviar a chave pública

sobre o adversário e, em seguida, ele irá avaliar a função no ponto X e

enviar o Y resultando também para o adversário. Portanto, tudo o adversário começa a

vemos é apenas uma chave pública, que define qual é a função, e então ele começa a

ver a imagem dessa função em um ponto X aleatório, e é objetivo é, basicamente, para inverter

função neste ponto Y. Okay, então ele gera alguns principal X. E nós dissemos que o

função alçapão é seguro se a probabilidade de que o anúncio, o adversário inverte

o indicado no ponto y é negligenciável. Em outras palavras, dada a probabilidade de que y

o adversário é capaz de alterar a imagem de pré y é na verdade um insignificante

probabilidade e se isso é verdade para todos os algoritmos eficientes, então dizemos que esta

função trapdor é segura. Então, novamente de forma abstrata, é um muito interessante

conceito em que você pode avaliar a função para a frente muito

facilmente. Mas então ninguém pode avaliar a função na direção inversa, a menos

eles têm esse alçapão, o SK chave secreta, que então, de repente, lhes permite

. Então, usando o conceito de uma função de alçapão,

não é muito difícil construir um sistema de criptografia de chave pública, e deixe-me mostrar-lhe como

para fazê-lo. Então aqui nós temos a nossa função de alçapão, (G, F e F inversa). O outro

ferramenta que vamos precisar é um esquema de criptografia simétrica, e eu vou

supor que este esquema de criptografia é realmente seguro contra ataques ativos, portanto, em

especial que eu precisava para fornecer criptografia autenticado. Observe que a

sistema de criptografia simétrica tem chaves em K ea função alçapão leva insumos

em X. Esses são dois grupos diferentes e por isso estamos também vai precisar da função hash.

que vai de X a K. Em outras palavras, ele mapeia elementos do conjunto X em chaves para

os sistemas de criptografia simétrica. E agora, uma vez que temos esses três componentes,

pode realmente construir o sistema de criptografia de chave pública da seguinte forma: assim que a chave

geração para o sistema de criptografia de chave pública é, basicamente, exatamente o mesmo que

geração a chave para a função de alçapão. Então corremos G para a porta da armadilha

função, temos uma chave pública e uma chave secreta. E esses são vai ser o público e

chaves secretas para o sistema de criptografia de chave pública. E como criptografar e descriptografar? Vamos

início com criptografia. Assim, o algoritmo de encriptação leva uma chave pública e uma mensagem

como entrada. Então, o que ele vai fazer é que vai gerar um aleatória X da capital conjunto

X. Será então aplicar a função alçapão para esta aleatória X, para se obter Y. Assim

Y é a imagem de X sob a função alçapão. Em seguida, ele vai em frente e

gerar uma chave simétrica hash X. Portanto, esta é uma chave simétrica para a simétrica

sistema de chave. E então, finalmente, ele criptografa 'm' a mensagem de texto simples usando essa chave que foi

acabou de gerar. E então ele produz o valor de Y que apenas computado, o que é

a imagem de X, ao longo da encriptação sob o sistema de forma simétrica, a mensagem de M. Então

que é como criptografia funciona. E eu quero enfatizar novamente que a função alçapão

só é aplicada a este valor aleatório X, enquanto que a própria mensagem é criptografada

utilizando um sistema de chave simétrica usando uma chave que foi derivado a partir do valor que X

escolheu aleatoriamente. Portanto, agora que entendemos criptografia, vamos ver como descriptografar.

Enquanto o algoritmo de decodificação leva uma chave secreta como entrada, eo texto cifrado.

O texto cifrado em si contém dois componentes, o valor de Y eo valor C.

Então o primeiro passo que vamos fazer, é que vamos aplicar a transformação inversa,

a função inversa porta armadilha para o valor de Y, e que nos dará de volta o

X originais que foi escolhido durante a criptografia. Então, agora deixe-me perguntar, como fazer

derivamos a chave simétrica K descriptografia deste X que apenas obteve? Bem,

de modo que é uma pergunta fácil. Nós basicamente X de hash novamente. Isso dá-nos apenas como K

durante a criptografia. E agora que temos essa chave de criptografia simétrica, podemos aplicar

o, o algoritmo de descriptografia simétrica para descriptografar o texto cifrado C. Ficamos com a

M mensagem original e é isso que nós de saída. Então, é assim que a chave pública

funciona o sistema de criptografia foram esta função alçapão só é usado para criptografar

algum tipo de um valor aleatório X ea mensagem real é criptografada usando a

sistema simétrica. Assim, em fotos aqui, temos a mensagem M, obviamente, a simples

texto poderia ser muito grande. Então, aqui nós temos o corpo do texto decifrado que

pode ser bastante longo, na verdade é criptografada usando o sistema simétrico. E então, novamente

eu enfatizo que a chave para o sistema simétrico é simplesmente o hash de X.

E então o cabeçalho da mensagem cifrada é simplesmente esta aplicação do alçapão

para esta função aleatória X que nós escolhemos. E assim, durante a descriptografia o que acontece é

que primeiro descriptografar o cabeçalho para obter X e então nós decifrar o corpo usando o

sistema simétrica para realmente obter o texto original planície M. Assim como de costume quando eu

mostrar-lhe um sistema como este, obviamente você vai querer verificar que a descriptografia de fato é

inversa de criptografia. Mas mais importante que você quer perguntar porque é que esta

sistema seguro. E de fato há um teorema a segurança agradável aqui que diz. Isso se

a função de porta armadilha que nós começamos com é segura. Em outras palavras, essa é uma

função de sentido único se o adversário não tenha uma chave secreta. A simétrica

sistema de criptografia fornece criptografia autenticado. E a função hash é uma

oráculo aleatório, o que significa simplesmente que é uma função aleatória do conjunto X para

, o conjunto de teclas de K. Assim, um oráculo aleatório é uma espécie de uma idealização do, o que é um

função hash é suposto ser. Na prática, é claro, quando você vem para

implementar um sistema como este, você só iria usar, SHA-256, ou qualquer um dos

outras funções hash que discutimos em sala de aula. Assim, sob essas três condições em

fato de o sistema que acabamos de descrever é escolhido texto cifrado seguro por isso é CCA

seguro, o ro pouco aqui apenas denotar o fato de que a segurança é definida em que é chamado

um modelo oráculo aleatório. Mas, isso é um detalhe que na verdade não é tão importante para

discussão aqui, o que eu quero que você lembre-se é que se a função alçapão

é, de facto, uma função de porta segura armadilha. O sistema de criptografia simétrica é seguro

contra adulteração de modo que fornece criptografia autenticado. E H

é em certo sentido, uma boa função hash. É uma função aleatória, o que na prática

você só usar SHA-256, então na verdade o sistema que acabamos mostrou é CCA

seguro, é escolhido cifrado seguro. Devo dizer-lhe que há realmente uma ISO

padrão, define esse modo de criptografia, de criptografia de chave pública. ISO

estandes para International Standards Organization. Então, na verdade, esta especial

sistema foi realmente padronizada, e isso é uma coisa boa de usar. Vou me referir a

este como o criptografia ISO nos segmentos mais próximos. Para concluir este segmento, eu quero

para avisá-lo sobre uma forma incorreta de usar uma função alçapão para construir um

sistema de criptografia de chave pública. E de fato este método pode ser a primeira coisa que

vem à mente, e ainda é completamente insegura. Então deixe-me mostrar-lhe, como não

encrypt usando uma função de alçapão. Bem a primeira coisa que pode vir à mente

é, bem, vamos aplicar a função alçapão diretamente à mensagem M. Assim,

Criptografar simplesmente por aplicação de uma função para a mensagem M, e nós descriptografar simplesmente por

aplicação F inversa à C texto cifrado para recuperar a mensagem original M. Então

funcionalmente, isto é, de facto, decriptação é o inverso de encriptação, e ainda este

é completamente inseguro para muitas, muitas razões diferentes. A maneira mais fácil de ver

que este é inseguro, é que é simplesmente, esta é a criptografia determinista.

Você percebe não há aleatoriedade ser usados aqui. Quando criptografar uma mensagem

Você percebe não há aleatoriedade ser usados aqui. Quando criptografar uma mensagem

semanticamente seguro. Mas, na verdade, como eu disse, quando instanciar este alçapão

função com implementações particular, por exemplo com a porta de armadilha RSA

função, então há muitos, muitos ataques que são possíveis nesta

construção particular, e por isso você não deve nunca, nunca, nunca usá-lo, e eu vou

repetir isso ao longo deste módulo, e de fato no segmento seguinte, eu vou lhe mostrar uma

número de ataques contra esta implementação particular. Ok então, o que eu gostaria

você a lembrar é que você deve estar usando um sistema de criptografia como o ISO

padrão, e você nunca deve aplicar a função alçapão diretamente ao M. mensagem

Embora no próximo segmento veremos outras maneiras de criptografar usando uma armadilha

função porta que também são corretas, mas este método particular, é claramente, claramente

incorreta. Ok, então agora que entendemos como construir criptografia de chave pública

dada uma função alçapão, a próxima questão é como construir alçapão

funções, e vamos fazer isso no próximo segmento.