Loading
Nota de Estudos
Study Reminders
Support
Text Version

Segurança perfeita

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fundamentos de CryptographyProf. Dr. Ashish Choudhury (Ex-) Infosys Foundation Career Development Cátedra Instituto Professor de Technology-BengaluruLecture-04Perfect SecurityHello todos, bem-vindos à palestra 4. (Consulte o Tempo do Slide: 00:28) Plano para esta palestra é o seguinte: discutiremos o sigilo perfeito, que é a primeira noção formal de segurança, que é também a noção mais forte de sigilo. Também discutiremos várias definições equivalentes de perfeito sigilo. (Consulte o Slide Time: 00 :45) Assim, a definição de segurança perfeita foi dada por Claude Shannon em sua obra clássica em 1948 e Shannon é muitas vezes considerada como o pai da teoria da informação e essa noção de segurança também é chamada de segurança incondicional e segurança da informação. O modelo de ataque que é considerado na definição de segurança perfeita é o modelo de ataque cifrado somente modelo de ataque, onde assumimos que temos um emissor e um receptor que concordaram com um valor aleatório de chave de valor k. supomos que o remetente tenha criptografado uma única mensagem m usando um processo de encriptação publicamente conhecido sob essa chave k, e o texto cifrado foi interceptado pelo adversário. A parte interessante deste modelo de ataque é que assumimos aqui que o adversário é computacionalmente descalço. Isso significa que não assumimos nenhuma hipótese sobre seu poder de computação. Supomos que ele possa fazer qualquer tipo de cálculo com força bruta ou qualquer outro computamento. Sendo assim, esse é o aspecto interessante deste modelo de segurança. Informalmente, a segurança perfeita diz que independentemente de qualquer informação prévia que o atacante tenha sobre o texto simples subjacente, ver o texto cifrado não fornece nenhuma informação adicional a ele sobre o texto simples subjacente. Isso significa ver o texto cifrado é absolutamente inútil para o atacante. O que quer que pudesse inferir sobre a mensagem do texto cifrado, o mesmo poderia já ter inferido antes de qualquer texto cifrado ter sido comunicado. Então, aqui temos 2 entidades, temos as informações prévios e temos o termo sem informações adicionais. Temos que agora aprender um pouco de matemática para entender como formalizar esses 2notions a saber: o de informações prévios e que não têm informações adicionais. (Consulte o Tempo do slide: 02 :36) Então, imagine que somos dados uma cifra publicamente conhecida a saber, um triplet de algoritmo de geração de chaves de algoritmos, algoritmo de criptografia e um algoritmo de decriptografia. Em seguida, qualquer invasor tem as seguintes informações sobre o processo de criptografia. A saber, ele conhece 3 espaços, a saber, o espaço da mensagem, o espaço fundamental e o espaço de texto cifrado, onde o espaço da mensagem é o conjunto de todas as mensagens legítimas que poderiam ser criptografadas pelo processo de criptografia. O espaço de chaves denota todas as chaves possíveis que poderiam ser de saída pelo algoritmo de geração de chaves. E o texto cifrado denota todo o possível texto cifrado, que poderia ser gerado pelo algoritmo de criptografia. A partir do ponto de vista do atacante, qualquer esquema de criptografia induz 3 de distribuição de probabilidade, uma distribuição de probabilidade sobre o espaço da mensagem, uma distribuição de probabilidade sobre o espaço chave e uma distribuição de probabilidade sobre o espaço cifrado. Por isso, agora vamos passar por cima dessa probabilidade distribuições uma por uma. A primeira distribuição de probabilidade é sobre o espaço chave e isso é induzido pelo algoritmo de geração de chaves. Então lembre-se, conforme o princípio Kerckhoffs ’, assumimos que etapas do algoritmo de geração de chaves, algoritmo de criptografia e algoritmo de decriptografia são publicamente conhecidos do invasor. Discutimos também que o algoritmo geracional chave tem que ser um algoritmo randomizado. Isso significa que, toda vez que executamos o algoritmo de geração de chaves ele vai a saída de uma possível chave candidata do espaço chave com certa probabilidade. Portanto, é isso que queremos dizer com a distribuição de probabilidade sobre o espaço chave induzido pelo algoritmo de geração de chaves. Também, discutimos em uma das palestras anteriores que na maioria dos casos, o algoritmo de geração de chaves vai a saída de uma chave uniformemente aleatória do espaço chave. A saber, se o tamanho do espaço chave é a cardinalidade do espaço chave, então qualquer chave candidata poderia ser gerada com probabilidade um sobre o espaço chave. Sendo assim, essa é a distribuição uniforme sobre o espaço chave, que adversário já terá se souber as etapas do algoritmo de geração de chaves. Mas não é necessário que o seu algoritmo de geração de chaves sempre supere as chaves uniformemente aleatórias do espaço chave. Sendo assim, isso seria induzir outro tipo de distribuição de probabilidade. Qualquer que seja o caso desde que as etapas dos algoritmos de geração de chave sejam conhecidas publicamente. Sabemos que, a partir do ponto de vista do atacante, há uma distribuição de probabilidade sobre diferentes valores de chaves, o que poderia ocorrer com diferentes probabilidades. É justamente essa a distribuição de probabilidade sobre o espaço de texto simples que o atacante tem. Podemos também capturar matematicamente o que exatamente queremos dizer por nenhuma informação adicional. Formalmente, um processo de criptografia a saber, uma coleção de algoritmos de geração de algoritmos, Enc e Dec sobre um espaço de texto simples M é chamado perfeitamente seguro se para cada distribuição de probabilidade sobre o espaço de texto simples e espaço de chave, e para cada texto simples m pertencente ao espaço de texto simples, de acordo com essa distribuição de probabilidade, e para cada texto cifrado c pertencente ao espaço cifrado, Pr [M =? | C =?] = Pr [M =?] segura. Por isso, deixe de entender o que exatamente o LHS e RHS desta igualdade representa. Se você considerar a parte RHS desta igualdade, a saber: Pr [M =?], m poderia ser comunicado pelo remetente. Essa é uma informação prévia sobre o texto simples subjacente antes de qualquer comunicação ter acontecido do remetente ao receptor, antes de qualquer algoritmo de geração de chaves ter sido usado, e a mensagem foi criptografada. Essa é a informação de apriori sobre o plaintexto subjacente. Considerando que a parte LHS dessa igualdade Pr [M =? | C =?] que suposta posteriori probabilidade de que a mensagem m seja criptografada em c. Isso significa, dado que o adversário viu ou interceptou um texto cifrado c, qual é a probabilidade de que o texto simples m seja criptografado neste texto cifrado c. Então, intuitivamente, quando dizemos que essas 2 probabilidades são iguais, significa que qualquer que seja o adversário sabia sobre o texto simples subjacente antes de qualquer texto cifrado ser comunicado com mesma probabilidade adversário sabe que um texto simples poderia ser m e no texto cifrado cifrado c. Isso significa observar o texto cifrado c não alterar invasor ’ s conhecimento sobre a distribuição do texto à plaina. Qualquer que seja o conhecimento do atacante ’ era antes de ver o texto cifrado, o mesmo conhecimento que tem, mesmo depois de ver o texto cifrado. Além disso, mantém-se mesmo que o adversário seja computacionalmente ilimitado. Essa é a importância desta definição. Essa definição não coloca qualquer tipo de restrição ao poder computacional do adversário. Mesmo que adversário conheça as etapas do algoritmo, mesmo que saiba o que poderia ser as chaves candidatas mesmo que seja permitido fazer força bruta, sua visão ou seu conhecimento sobre o texto simples subjacente ou sobre a distribuição do texto simples não deve mudar antes e depois de ver o texto cifrado. Se isso se mantém, então dizemos que nosso processo de criptografia subjacente é perfeitamente seguro. Observe que nesta definição, tenho destacado poucas coisas a saber, tenho dito que a condição deve guardar para cada distribuição de probabilidade sobre o espaço de texto simples. Isso significa que não importa se a distribuição sobre um espaço de texto simples é uma distribuição uniforme ou uma distribuição de viés, a condição deve se manter para qualquer possível distribuição de probabilidade sobre o espaço de mensagens. Da mesma forma, a condição ou igualdade deve guardar para qualquer tipo de distribuição de probabilidade sobre o espaço chave se é uma chave uniformemente gerada, se a saída do algoritmo de geração de chaves uniformemente gera chaves aleatórias ou chaves de viés ainda a condição deve hold.Além disso, uma vez que fixamos a distribuição de probabilidade do espaço de texto simples e o espaço chave, a condição deve guardar para cada plaintexto pertencente ao espaço da mensagem e todo candidato cifrado pertencente ao espaço de texto cifrado. (Consulte o Tempo do slide: 20 :45) Então agora, o que faremos será vermos algum equivalente alternativo definições para uma segurança perfeita. Esta é a definição original de segurança perfeita como dada por Shannon e a interpretação da igualdade dessas 2 probabilidades é que a probabilidade de se conhecer um texto à plaina permanece a mesma antes e depois de ver o texto cifrado. Essa é a interpretação da definição original de segurança perfeita como dada por Shannon.Agora vejamos a primeira definição alternativa. A primeira definição alternativa diz que vamos dizer um processo de criptografia ou um esquema de criptografia para estar perfeitamente seguro se para cada distribuição de probabilidade sobre o espaço à plaintexto e espaço chave e para cada par de mensagem m0, m1 que ocorre com probabilidade não zero com relação a essa distribuição de probabilidade e a cada texto cifrado c a seguinte igualdade deve segurar: Pr [C =? | M =? 0] = Pr [C =? | M =? 1]. A igualdade diz que Pr [C =? | M =? 0] é o mesmo que Pr [C =? | M =? 1]. A interpretação dessa igualdade é que a distribuição de probabilidade do texto cifrado é independente do que exatamente é o seu texto simples subjacente. Isso significa que se o adversário ver o texto cifrado c sobre o canal, então não importa se M =? 0 ou M =? 1 com probabilidade igual do ponto de vista do atacante, o texto cifrado c deverá ser uma criptografia candidata de m0, bem como uma criptografia candidata de m1.Não deve haver qualquer viés na probabilidade. Mas se é uma criptografia de m0 ou se é uma criptografia de m1, isso significa que a distribuição de texto cifrado deve ser independente do texto demandado subjacente. (Consulte o Tempo do slide: 22 :32) Então agora o que nós vamos fazer a seguir é que vamos provar que ambas as 2 definições são equivalentes. A saber, mostraremos que se houver um processo de criptografia que satisfaça a condição original da segurança perfeita de Shannon, então o mesmo processo de criptografia tem que satisfazer a definição alternativa e vice-versa. Comprove primeiramente a equivalência da definição assumindo que temos um processo de criptografia que satisfaz a condição de definition.Namely, supomos que temos um processo de criptografia onde para cada distribuição de probabilidade, Pr [C =? | M =? 0] = Pr [C =? | M =? 1] =?, dizem delta, para todos os pares de mensagens m0, m1 no espaço de texto simples, e para todo o texto cifrado c pertencentes ao espaço de texto cifrado. Dado isso, provaremos que a condição original da segurança perfeita de Shannon ’ também é verdadeira para o processo de criptografia. Pr [M =? | C =?] = Pr [M =?]. Então o que nós vamos fazer é supor que temos um texto simples arbitrário e caráter de texto cifrado arbitrário. Agora vamos tentar computar Pr [M =? | C =?]. Então, o que eu vou fazer aqui é eu vou aplicar o teorema de Bayes aqui. Ao aplicar o teorema de Bayes, agora vamos tentar computar Pr [C =?]? A probabilidade de que seu texto cifrado seja c vai ser essa somatória. Este estado de somatória que você leva todas as mensagens possíveis do espaço de texto simples e descubra qual é a probabilidade de que a mensagem seja aquele texto simples do candidato a saber, m ’ e dado que a mensagem é m ’, qual é a probabilidade que m ’ é criptografada em c. Isso lhe dará a distribuição de probabilidade sobre o texto cifrado c. Porque o que tem que basicamente fazer é imaginar que você tem o espaço de texto simples você leva cada um do candidato à plaina que é justamente o primeiro termo nessa somatória. E uma vez que você fixou aquele candidato à plaina você apenas computa qual é a probabilidade de que aquele candidato à plaina te leve ao texto cifrado c, esse é esse segundo termo. E se você multiplicar tudo isso, se estas 2 probabilidades e levar a somatória sobre todo o texto simples candidato, isso lhe dará a distribuição de probabilidade de cifração cifrada sendo c. Ora, conforme a nossa hipótese da condição, sabemos que a probabilidade condicional de que o texto cifrado é c dado o texto simples é m ’ é igual para todos m ’ a saber, Pr [C =? | M =? ’] =?, porque é isso que é a suposição que estamos fazendo. Estamos fazendo a suposição de que nosso processo de criptografia satisfaz a condição alternativa. Então, para cada m ’, eu posso substituir o segundo termo no somatório por?. Como resultado, obtenho essa forma simplificada da somatória que computamos o valor da probabilidade de C = c, ou seja?. Agora, vamos tentar computar Pr [C =? | M =?], essa é a parte numeradora desta expressão RHS. E, novamente, conforme a nossa hipótese deste teorema, ou este lemma, já sabemos que Pr [C =?] =?. E isso é independentemente do que é o meu m, poderia ser m0, poderia ser m1 poderia ser m2 para qualquer candidato m da base de plaintexto, Pr [C =?] =?. Então, isso significa que a parte numeradora dessa expressão RHS também é?. Daí, posso dizer que o meu LHS original a saber, Pr [M =? | C =?] nada além desta igualdade.E no numerador assim como no denominador, eu tenho o? para que eu possa cancelá-lo. E daí, eu obtenho que essa probabilidade condicional não passa de Pr [M =?], que é justamente o que exatamente nós queríamos provar. Isso significa que provamos que se o processo de criptografia satisfaz a condição da definição alternativa, então ele também tem que satisfazer a condição da definição original de Shannon. Então, agora deixe-nos fazer a prova na direção inversa. (Consulte o tempo de deslizamento: 27 :54) a saber, assumimos que temos um processo de criptografia que satisfaz a condição da definição original de Shannon. Esse é o Pr [M =? | C =?] = Pr [M =?] ∀? M,? ?. Tendo em conta esta vontade, provará que a distribuição do texto cifrado é independente do texto à base subjacente. A saber, não importa se o texto simples é m0 ou se o texto simples é m1with igual probabilidade, ele poderia levar ao texto cifrado c, e isso comporta para cada par de mensagens m0, m1 em do espaço de texto simples e a cada texto cifrado c do espaço de texto cifrado. Vamos primeiro tentar computar Pr [C =? | M =? 0]. Para isso vamos utilizar o fato de que conforme a condição dada, uma vez que o esquema de criptografia satisfaz a condição original de Shannon ’, sabemos que Pr [C =? | M =? 0] = Pr [M =? 0]. Então agora o que eu vou fazer é eu vou expandir minha parte do LHS aqui usando o teorema de Bayes, onde estou apenas trocando o numerador e o denominador da probabilidade condicional. E aplicando o teorema de Bayes, obtenho essa igualdade. = Pr [M =? 0] Agora, o que eu posso fazer é que eu posso cancelar esse termo comum tanto do LHS quanto do RHS. Daí eu obtenho que Pr [C =? | M =? 0] = Pr [C =?]. Ao aplicar a mesma lógica, posso concluir que Pr [C =? | M =? 1] = Pr [C =?]. Como resultado, ambos Pr [C =? | M =? 0] e Pr [C =? | M =? 1] são mesmos a saber, é Pr [C =?]. Isso significa, nós provamos que se a condição original de Shannon está satisfeita, então o processo de criptografia também tem que satisfazer a condição para a definição alternativa. Isso significa, ambas as definições são equivalentes a cada other.Então, se você for dado um processo de criptografia e se for solicitado a provar se ele é perfeitamente seguro ou não, então você pode prová-lo conforme a condição original de Shannon ou você pode prová-lo conforme a primeira definição alternativa. (Consulte o Slide Time: 30 :30) Agora, vejamos outra definição equivalente de segurança perfeita. Antes de ir para esta definição, vamos primeiro tentar entender a intuição subjacente que queremos capturar através desta definição. Então, o objetivo da segurança perfeita é o seguinte: imagine um cenário em que uma chave para o processo de criptografia tenha sido acordada entre o emissor e o receptor. Suponhamos que o adversário saiba disso? {?0,? 1} e isso também com probabilidade igual.Suponhamos que realmente o remetente vai criptografar a mensagem m0 ou m1 com igual probabilidade. E ele criptografa uma dessas mensagens aleatoriamente usando a chave k conforme o processo de criptografia, computa o texto cifrado c e o enviou por cima do canal. Digamos, o atacante intercepta o texto cifrado c, e o atacante desatou o poder de computação. O sigilo intuitivamente perfeito exige que o conhecimento do adversário ’ sobre o texto simples subjacente deve permanecer o mesmo mesmo depois de ver o texto cifrado c. Então, o que foi essa informação sobre o texto simples antes de qualquer texto cifrado foi comunicado neste caso específico: com probabilidade a metade do ponto de vista do atacante, o texto simples poderia ser m0, e com probabilidade metade do texto simples seria m1. Agora o sigilo perfeito exige que mesmo depois de ver o texto cifrado c e mesmo depois de conhecer os passos do processo de criptografia, e mesmo que o adversário tenha poder computacional ilimitado, a vantagem que a adversidade fica após ver o texto cifrado e aprender o texto simples subjacente deve ser 0.That significa, mesmo depois de ver o texto cifrado c, a probabilidade de que o texto simples subjacente seria m0 ou m1 deve ser a metade. Adversário não pode fazer nada melhor do que adivinhar o texto simples subjacente. Essa é a intuição subjacente que agora vamos formalizar. (Consulte o Slide Time: 32 :21) E essa intuição é formalizada por um jogo de resposta de desafio, que chamamos de experimento. E vamos ver que no restante deste curso, toda definição de segurança vai ser formalizada por esse tipo de experimento de resposta de desafio ou um jogo que modelam algo que queremos, o que pode acontecer na realidade. O experimento é o seguinte: supomos que nos é dada uma cifra de cifras publicamente conhecida = (Gen, Enc, Dec), M, e o jogo é jogado entre 2entities.The primeira entidade aqui é um adversário ou um algoritmo para o atacante que denotamos por este algoritmo A e o algoritmo ou o adversário é computacionalmente ilimitado. Isso modela o fato de que estamos tentando captar a noção de sigilo perfeito onde o adversário é computacionalmente desvinculado. A segunda entidade aqui é o verificador hipotético que vai modelar o sender.Agora, a nomenclatura que vamos seguir enquanto denominamos esse tipo de experimentos é a seguinte: este experimento em particular é denotado por ????? (?, Π) ???. Agora, vamos tentar decodificar cada uma das partes individuais deste nome complicado. Por isso, o nome PrivK denota aqui que estamos tentando modelar um experimento para um processo de criptografia simétrica ou um processo de criptografia de chave privada. É por isso que o nome PrivK, mais tarde quando tentaremos modelar o requisito de segurança para primitivas de chave pública. Este privK será substituído por PubK. O nome do string eav denota aqui estamos considerando um adversário onde o adversário só tem permissão para eavesbaixar ou apenas ouvir o texto cifrado porque estamos no texto cifrado apenas de ataque modelo. O nome A aqui denota o nome do algoritmo aqui e acontece denota o nome do processo de criptografia com relação ao qual este jogo vai ser jogado. Essa é a nomenclatura que vamos seguir para denotar esta experiência específica. Agora, quais são as regras deste jogo? Esse experimento vai ser um experimento randomizado. O primeiro passo aqui é que o adversário seleciona um par de mensagens do espaço de texto simples, digamos m0and m1 com a restrição de que seu tamanho tem que ser igual. Um adversário pode escolher qualquer par de mensagens. Não há absolutamente nenhuma restrição que colocamos em qual par de mensagens que ele pode enviar para o verificador. A única restrição é que seu comprimento tem que ser igual, assim, o adversário pode, deterministicamente, pegar um par de mensagem, ele poderia escolher aleatoriamente um par de mensagem, pode usar qualquer estratégia para escolher o par de mensagem que deseja enviar para o verificador. Agora, uma vez que o par de mensagens é comunicado ao verificador, o que o verificador vai fazer é o seguinte: ele vai rodar o algoritmo de geração de chaves que irá a saída de uma chave aleatória uniformemente ou uma chave conforme as etapas do algoritmo de geração de chaves para o verificador. E o verificador vai escolher aleatoriamente uma dessas duas mensagens para criptografia. O índice da mensagem que se vai escolher para a criptografia é denotado por b, que é colhida uniformemente. Isso significa, com a metade da probabilidade, pode estar escolhem a mensagem m0 para criptografia, ou com probabilidade metade pode estar escolhem a mensagem m1 para criptografia. Uma vez que tenha decidido o índice da mensagem, ele criptografa essa mensagem mb usando a chave k que é conhecida apenas para o verificador e o texto cifrado é dado ao adversário.E agora o objetivo do adversário é descobrir o índice da mensagem que foi criptografada em c, isso significa que o adversário tem que descobrir se o c é uma criptografia de m0 ou se ela é uma criptografia de m1. Depois de analisar o texto cifrado c conforme qualquer que seja o adversário de estratégia quer seguir, ele dá a eles previsão. A saber, ela supera um pouco, que é 0 ou 1 correspondente ao índice, que sente que aquela mensagem específica foi criptografada no texto cifrado c. Isso significa b ’ denota o índice, que segundo o adversário é o índice da mensagem que é criptografada no texto cifrado c. Esse é o experimento. Como você pode ver, este é um experimento randomizado, porque adversário poderia escolher qualquer par de mensagens conforme sua aleatoriedade. Da mesma forma o verificador vai escolher qualquer mensagem aleatória para fora desse par para criptografia, e a chave poderia ser qualquer chave aleatória conforme o algoritmo de geração de chave. Agora a saída do experimento é decidida da seguinte forma. Dizemos que a saída do experimento é 1 ou o que é interpretado como adversário ganhou o jogo, se ele previu corretamente o que exatamente é a mensagem que é criptografada no texto cifrado c. Isso significa se ela corretamente saída b ’ igual a b então dizemos que o adversário ganhou esse experimento ou o adversário ’ saída ’ s output é 1.On a outra mão, se o adversário incorretamente identifica o que é criptografado naquele texto cifrado c que significa que ele supera b ’ que é diferente de b, então dizemos que saída do experimento é 0, o que é interpretado como adversário perdeu o jogo. Também vimos o jogo-baseddefinição, que modela perfeita indistinguibilidade. Espero que tenha gostado desta palestra. Obrigado!