WEBVTT 00:00:00.000 --> 00:00:03.827 No último segmento, o que é explicado que um sistema de criptografia de chave pública. E nós 00:00:03.827 --> 00:00:07.557 definido o que isso significa para um sistema de criptografia de chave pública para ser seguro. Se você 00:00:07.557 --> 00:00:11.142 lembre-se, necessária segurança contra ataques ativos. E, em particular, nós 00:00:11.142 --> 00:00:15.211 segurança texto definido da cifra escolhida como nossa meta. Esta semana, nós vamos construir dois 00:00:15.211 --> 00:00:19.281 famílias de sistemas públicos de criptografia de chave que são escolhidos texto cifrado seguro. E em 00:00:19.281 --> 00:00:22.914 este segmento, nós vamos começar pela construção de públicos-chave de criptografia, 00:00:23.059 --> 00:00:27.124 um conceito chamado de um alçapão permutação. Então vamos começar pela definição de um 00:00:27.124 --> 00:00:31.064 conceito geral chamada uma função alçapão. Então, o que é uma função alçapão? 00:00:31.064 --> 00:00:35.484 Bem, uma função de alçapão, basicamente, é uma função que vai de algum conjunto X para alguns 00:00:35.484 --> 00:00:39.585 conjunto Y. E é realmente definido por um triplo de algoritmos. Há uma geração 00:00:39.585 --> 00:00:43.685 algoritmo, a função f, eo inverso da função f. Assim, a geração 00:00:43.685 --> 00:00:47.892 algoritmo, basicamente o que ele faz quando você executá-lo, ele irá gerar um par de chaves, uma 00:00:47.892 --> 00:00:52.098 chave pública e uma chave secreta. A chave pública vai definir uma função específica 00:00:52.098 --> 00:00:56.869 a partir do conjunto X para o Y. conjunto E, então, a chave secreta que vai definir o inverso 00:00:56.869 --> 00:01:01.639 função agora da Y definido para o conjunto X. Então a idéia é que você pode avaliar 00:01:01.639 --> 00:01:06.588 função em qualquer ponto usando um PK de chave pública e, em seguida, você pode inverter essa função 00:01:06.588 --> 00:01:12.443 usando a chave secreta, SK. Então, o que quero dizer com inversão? Mais precisamente, se 00:01:12.443 --> 00:01:17.255 olhada em qualquer par de chaves e segredo de chave pública gerada pelo algoritmo de geração de chaves 00:01:17.255 --> 00:01:21.727 G, em seguida, acontece que se eu avaliar a função no ponto X, e então eu 00:01:21.727 --> 00:01:26.142 avaliar o inverso no ponto resultante, eu deveria receber o X ponto original 00:01:26.142 --> 00:01:30.670 para trás. Assim, a imagem que você deve ter em sua mente, há é este conjunto X grande e 00:01:30.670 --> 00:01:35.857 este grande conjunto Y E então, esta função irá mapear qualquer ponto X a um ponto em Y, 00:01:35.857 --> 00:01:41.508 e isto pode ser feito usando a chave pública. Assim, novamente, em qualquer ponto X pode ser mapeado para 00:01:41.508 --> 00:01:46.897 um ponto no Y. E, então, se alguém tem a chave secreta, então basicamente eles podem ir em 00:01:46.897 --> 00:01:53.758 direção inversa, aplicando, este sk chave secreta. Assim agora que nós 00:01:53.758 --> 00:01:58.289 entender o que é uma função de alçapão, vamos definir o que significa para um alçapão 00:01:58.289 --> 00:02:02.652 função para ser seguro. E por isso vamos dizer que este triplo, (G, F, F inversa), é seguro 00:02:02.652 --> 00:02:06.903 se de fato essa função F (PK.) é o que se chama uma função de uma maneira. E deixe-me 00:02:06.903 --> 00:02:10.986 explicar o que uma, o que é uma função de uma maneira. A ideia é que, basicamente, o 00:02:10.986 --> 00:02:15.516 função pode ser avaliada em qualquer ponto, mas invertendo é difícil sem a 00:02:15.516 --> 00:02:19.639 SK chave secreta. Portanto, vamos definir que com mais precisão. Como de costume, definir que o uso de uma 00:02:19.639 --> 00:02:23.764 jogo. Então aqui temos o nosso jogo entre o desafiante eo adversário. E o jogo 00:02:23.764 --> 00:02:27.496 procede como se segue. Basicamente, o desafiante irá gerar uma chave pública e 00:02:27.496 --> 00:02:31.622 uma chave secreta. E então eles vão gerar um aleatório X. Ele vai enviar a chave pública 00:02:31.622 --> 00:02:36.116 sobre o adversário e, em seguida, ele irá avaliar a função no ponto X e 00:02:36.116 --> 00:02:40.160 enviar o Y resultando também para o adversário. Portanto, tudo o adversário começa a 00:02:40.160 --> 00:02:44.653 vemos é apenas uma chave pública, que define qual é a função, e então ele começa a 00:02:44.653 --> 00:02:49.483 ver a imagem dessa função em um ponto X aleatório, e é objetivo é, basicamente, para inverter 00:02:49.483 --> 00:02:54.097 função neste ponto Y. Okay, então ele gera alguns principal X. E nós dissemos que o 00:02:54.097 --> 00:02:58.507 função alçapão é seguro se a probabilidade de que o anúncio, o adversário inverte 00:02:58.507 --> 00:03:03.143 o indicado no ponto y é negligenciável. Em outras palavras, dada a probabilidade de que y 00:03:03.143 --> 00:03:07.271 o adversário é capaz de alterar a imagem de pré y é na verdade um insignificante 00:03:07.271 --> 00:03:11.907 probabilidade e se isso é verdade para todos os algoritmos eficientes, então dizemos que esta 00:03:11.907 --> 00:03:17.882 função trapdor é segura. Então, novamente de forma abstrata, é um muito interessante 00:03:17.882 --> 00:03:21.885 conceito em que você pode avaliar a função para a frente muito 00:03:21.885 --> 00:03:26.150 facilmente. Mas então ninguém pode avaliar a função na direção inversa, a menos 00:03:26.150 --> 00:03:30.311 eles têm esse alçapão, o SK chave secreta, que então, de repente, lhes permite 00:03:30.311 --> 00:03:35.424 . Então, usando o conceito de uma função de alçapão, 00:03:35.424 --> 00:03:39.552 não é muito difícil construir um sistema de criptografia de chave pública, e deixe-me mostrar-lhe como 00:03:39.552 --> 00:03:43.528 para fazê-lo. Então aqui nós temos a nossa função de alçapão, (G, F e F inversa). O outro 00:03:43.528 --> 00:03:47.605 ferramenta que vamos precisar é um esquema de criptografia simétrica, e eu vou 00:03:47.605 --> 00:03:51.531 supor que este esquema de criptografia é realmente seguro contra ataques ativos, portanto, em 00:03:51.531 --> 00:03:55.350 especial que eu precisava para fornecer criptografia autenticado. Observe que a 00:03:55.350 --> 00:04:00.726 sistema de criptografia simétrica tem chaves em K ea função alçapão leva insumos 00:04:00.726 --> 00:04:05.790 em X. Esses são dois grupos diferentes e por isso estamos também vai precisar da função hash. 00:04:05.790 --> 00:04:09.937 que vai de X a K. Em outras palavras, ele mapeia elementos do conjunto X em chaves para 00:04:09.937 --> 00:04:14.033 os sistemas de criptografia simétrica. E agora, uma vez que temos esses três componentes, 00:04:14.033 --> 00:04:17.821 pode realmente construir o sistema de criptografia de chave pública da seguinte forma: assim que a chave 00:04:17.821 --> 00:04:21.764 geração para o sistema de criptografia de chave pública é, basicamente, exatamente o mesmo que 00:04:21.764 --> 00:04:25.655 geração a chave para a função de alçapão. Então corremos G para a porta da armadilha 00:04:25.655 --> 00:04:29.956 função, temos uma chave pública e uma chave secreta. E esses são vai ser o público e 00:04:29.956 --> 00:04:34.171 chaves secretas para o sistema de criptografia de chave pública. E como criptografar e descriptografar? Vamos 00:04:34.171 --> 00:04:38.978 início com criptografia. Assim, o algoritmo de encriptação leva uma chave pública e uma mensagem 00:04:38.978 --> 00:04:43.898 como entrada. Então, o que ele vai fazer é que vai gerar um aleatória X da capital conjunto 00:04:43.898 --> 00:04:48.545 X. Será então aplicar a função alçapão para esta aleatória X, para se obter Y. Assim 00:04:48.545 --> 00:04:53.130 Y é a imagem de X sob a função alçapão. Em seguida, ele vai em frente e 00:04:53.130 --> 00:04:58.272 gerar uma chave simétrica hash X. Portanto, esta é uma chave simétrica para a simétrica 00:04:58.272 --> 00:05:03.290 sistema de chave. E então, finalmente, ele criptografa 'm' a mensagem de texto simples usando essa chave que foi 00:05:03.290 --> 00:05:08.123 acabou de gerar. E então ele produz o valor de Y que apenas computado, o que é 00:05:08.123 --> 00:05:13.260 a imagem de X, ao longo da encriptação sob o sistema de forma simétrica, a mensagem de M. Então 00:05:13.260 --> 00:05:18.366 que é como criptografia funciona. E eu quero enfatizar novamente que a função alçapão 00:05:18.366 --> 00:05:23.112 só é aplicada a este valor aleatório X, enquanto que a própria mensagem é criptografada 00:05:23.112 --> 00:05:28.098 utilizando um sistema de chave simétrica usando uma chave que foi derivado a partir do valor que X 00:05:28.098 --> 00:05:32.959 escolheu aleatoriamente. Portanto, agora que entendemos criptografia, vamos ver como descriptografar. 00:05:32.959 --> 00:05:37.366 Enquanto o algoritmo de decodificação leva uma chave secreta como entrada, eo texto cifrado. 00:05:37.366 --> 00:05:41.551 O texto cifrado em si contém dois componentes, o valor de Y eo valor C. 00:05:41.551 --> 00:05:46.070 Então o primeiro passo que vamos fazer, é que vamos aplicar a transformação inversa, 00:05:46.070 --> 00:05:50.366 a função inversa porta armadilha para o valor de Y, e que nos dará de volta o 00:05:50.366 --> 00:05:54.495 X originais que foi escolhido durante a criptografia. Então, agora deixe-me perguntar, como fazer 00:05:54.495 --> 00:06:00.042 derivamos a chave simétrica K descriptografia deste X que apenas obteve? Bem, 00:06:00.042 --> 00:06:04.736 de modo que é uma pergunta fácil. Nós basicamente X de hash novamente. Isso dá-nos apenas como K 00:06:04.736 --> 00:06:09.372 durante a criptografia. E agora que temos essa chave de criptografia simétrica, podemos aplicar 00:06:09.372 --> 00:06:13.783 o, o algoritmo de descriptografia simétrica para descriptografar o texto cifrado C. Ficamos com a 00:06:13.783 --> 00:06:17.741 M mensagem original e é isso que nós de saída. Então, é assim que a chave pública 00:06:17.741 --> 00:06:22.321 funciona o sistema de criptografia foram esta função alçapão só é usado para criptografar 00:06:22.321 --> 00:06:26.788 algum tipo de um valor aleatório X ea mensagem real é criptografada usando a 00:06:26.788 --> 00:06:31.244 sistema simétrica. Assim, em fotos aqui, temos a mensagem M, obviamente, a simples 00:06:31.244 --> 00:06:35.545 texto poderia ser muito grande. Então, aqui nós temos o corpo do texto decifrado que 00:06:35.545 --> 00:06:39.953 pode ser bastante longo, na verdade é criptografada usando o sistema simétrico. E então, novamente 00:06:39.953 --> 00:06:44.039 eu enfatizo que a chave para o sistema simétrico é simplesmente o hash de X. 00:06:44.039 --> 00:06:48.232 E então o cabeçalho da mensagem cifrada é simplesmente esta aplicação do alçapão 00:06:48.232 --> 00:06:52.641 para esta função aleatória X que nós escolhemos. E assim, durante a descriptografia o que acontece é 00:06:52.641 --> 00:06:56.888 que primeiro descriptografar o cabeçalho para obter X e então nós decifrar o corpo usando o 00:06:56.888 --> 00:07:01.829 sistema simétrica para realmente obter o texto original planície M. Assim como de costume quando eu 00:07:01.829 --> 00:07:06.542 mostrar-lhe um sistema como este, obviamente você vai querer verificar que a descriptografia de fato é 00:07:06.542 --> 00:07:10.605 inversa de criptografia. Mas mais importante que você quer perguntar porque é que esta 00:07:10.605 --> 00:07:14.963 sistema seguro. E de fato há um teorema a segurança agradável aqui que diz. Isso se 00:07:14.963 --> 00:07:18.900 a função de porta armadilha que nós começamos com é segura. Em outras palavras, essa é uma 00:07:18.900 --> 00:07:22.634 função de sentido único se o adversário não tenha uma chave secreta. A simétrica 00:07:22.634 --> 00:07:26.621 sistema de criptografia fornece criptografia autenticado. E a função hash é uma 00:07:26.621 --> 00:07:30.558 oráculo aleatório, o que significa simplesmente que é uma função aleatória do conjunto X para 00:07:30.558 --> 00:07:34.696 , o conjunto de teclas de K. Assim, um oráculo aleatório é uma espécie de uma idealização do, o que é um 00:07:34.696 --> 00:07:38.280 função hash é suposto ser. Na prática, é claro, quando você vem para 00:07:38.280 --> 00:07:42.317 implementar um sistema como este, você só iria usar, SHA-256, ou qualquer um dos 00:07:42.317 --> 00:07:47.252 outras funções hash que discutimos em sala de aula. Assim, sob essas três condições em 00:07:47.252 --> 00:07:51.863 fato de o sistema que acabamos de descrever é escolhido texto cifrado seguro por isso é CCA 00:07:51.863 --> 00:07:56.416 seguro, o ro pouco aqui apenas denotar o fato de que a segurança é definida em que é chamado 00:07:56.416 --> 00:08:00.572 um modelo oráculo aleatório. Mas, isso é um detalhe que na verdade não é tão importante para 00:08:00.572 --> 00:08:05.012 discussão aqui, o que eu quero que você lembre-se é que se a função alçapão 00:08:05.012 --> 00:08:09.000 é, de facto, uma função de porta segura armadilha. O sistema de criptografia simétrica é seguro 00:08:09.000 --> 00:08:13.017 contra adulteração de modo que fornece criptografia autenticado. E H 00:08:13.017 --> 00:08:17.468 é em certo sentido, uma boa função hash. É uma função aleatória, o que na prática 00:08:17.468 --> 00:08:22.245 você só usar SHA-256, então na verdade o sistema que acabamos mostrou é CCA 00:08:22.245 --> 00:08:27.615 seguro, é escolhido cifrado seguro. Devo dizer-lhe que há realmente uma ISO 00:08:27.615 --> 00:08:31.752 padrão, define esse modo de criptografia, de criptografia de chave pública. ISO 00:08:31.752 --> 00:08:35.781 estandes para International Standards Organization. Então, na verdade, esta especial 00:08:35.781 --> 00:08:40.456 sistema foi realmente padronizada, e isso é uma coisa boa de usar. Vou me referir a 00:08:40.456 --> 00:08:44.947 este como o criptografia ISO nos segmentos mais próximos. Para concluir este segmento, eu quero 00:08:44.947 --> 00:08:48.925 para avisá-lo sobre uma forma incorreta de usar uma função alçapão para construir um 00:08:48.925 --> 00:08:53.328 sistema de criptografia de chave pública. E de fato este método pode ser a primeira coisa que 00:08:53.328 --> 00:08:57.572 vem à mente, e ainda é completamente insegura. Então deixe-me mostrar-lhe, como não 00:08:57.572 --> 00:09:01.762 encrypt usando uma função de alçapão. Bem a primeira coisa que pode vir à mente 00:09:01.762 --> 00:09:05.696 é, bem, vamos aplicar a função alçapão diretamente à mensagem M. Assim, 00:09:05.696 --> 00:09:10.047 Criptografar simplesmente por aplicação de uma função para a mensagem M, e nós descriptografar simplesmente por 00:09:10.047 --> 00:09:14.180 aplicação F inversa à C texto cifrado para recuperar a mensagem original M. Então 00:09:14.180 --> 00:09:18.639 funcionalmente, isto é, de facto, decriptação é o inverso de encriptação, e ainda este 00:09:18.639 --> 00:09:22.881 é completamente inseguro para muitas, muitas razões diferentes. A maneira mais fácil de ver 00:09:22.881 --> 00:09:26.960 que este é inseguro, é que é simplesmente, esta é a criptografia determinista. 00:09:26.960 --> 00:09:30.944 Você percebe não há aleatoriedade ser usados aqui. Quando criptografar uma mensagem 00:09:30.944 --> 00:09:34.154 Você percebe não há aleatoriedade ser usados aqui. Quando criptografar uma mensagem 00:09:34.154 --> 00:09:37.948 semanticamente seguro. Mas, na verdade, como eu disse, quando instanciar este alçapão 00:09:37.948 --> 00:09:41.644 função com implementações particular, por exemplo com a porta de armadilha RSA 00:09:41.644 --> 00:09:44.951 função, então há muitos, muitos ataques que são possíveis nesta 00:09:44.951 --> 00:09:48.794 construção particular, e por isso você não deve nunca, nunca, nunca usá-lo, e eu vou 00:09:48.794 --> 00:09:52.830 repetir isso ao longo deste módulo, e de fato no segmento seguinte, eu vou lhe mostrar uma 00:09:52.830 --> 00:09:56.699 número de ataques contra esta implementação particular. Ok então, o que eu gostaria 00:09:56.699 --> 00:10:00.717 você a lembrar é que você deve estar usando um sistema de criptografia como o ISO 00:10:00.717 --> 00:10:04.992 padrão, e você nunca deve aplicar a função alçapão diretamente ao M. mensagem 00:10:04.992 --> 00:10:09.010 Embora no próximo segmento veremos outras maneiras de criptografar usando uma armadilha 00:10:09.010 --> 00:10:13.233 função porta que também são corretas, mas este método particular, é claramente, claramente 00:10:13.233 --> 00:10:17.560 incorreta. Ok, então agora que entendemos como construir criptografia de chave pública 00:10:17.560 --> 00:10:21.423 dada uma função alçapão, a próxima questão é como construir alçapão 00:10:21.423 --> 00:10:24.360 funções, e vamos fazer isso no próximo segmento.