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
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.