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.