Loading
Nota de Estudos
Study Reminders
Support
Text Version

Limitações da Segurança Perseguida

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 of Cryptography Prof. Dr. Ashish Choudhury (Ex-) Infosys Foundation Career Development Chair Professor International Institute of Information Technology-Bengaluru Lecture-05 Limitações de Perfect Security Olá todos, bem-vindos a palestra 5. (Consulte Slide Time: 00:30) Então, o plano para esta palestra é o seguinte Nós veremos um candidato para encriptação perfeitamente segura, o que chamamos como one time pad e veremos as limitações que são impostas por qualquer esquema de criptografia perfeitamente seguro. (Consulte O Tempo De Deslizamento: 00 :44) Então, o processo de criptografia do pad one time, que também é chamado como Vernam cipher é muito simples. Aqui o espaço de texto simples, o espaço chave e um espaço de texto cifrado são todas as cordas l bit, onde l é algum parâmetro de sistema que é publicamente conhecido do remetente, para o receptor e para qualquer um que esteja usando este sistema. O algoritmo de geração de chaves está indo para a saída de uma chave uniformemente aleatória. Assim, uma vez que o espaço chave é configurado como l bit strings, o algoritmo de geração de chaves está indo para a saída de uma chave l bit uniformemente aleatória. O algoritmo de criptografia é o seguinte. Por isso, é preciso um texto simples que vai ser uma cadeia de l bits e a chave k gerada pelo algoritmo de geração de chaves, que também é um string de l bit. E o texto cifrado é um barbante l bit, onde o texto cifrado não passa de XOR dos caracteres de texto simples e os caracteres chave pouco a pouco. E como você pode ver que este é um algoritmo determinístico não há aleatoriedade interna como parte deste algoritmo de criptografia. Isso significa que se você criptografar a mesma mensagem m usando a mesma chave k você vai obter o mesmo texto cifrado. O algoritmo de decriptografia é apenas uma operação reversa do algoritmo de criptografia no sentido ele leva um texto cifrado que vai ser uma string de l bit e a chave k que também vai ser uma string l bit. E para recuperar a mensagem o algoritmo de decriptografia apenas executa o XOR do texto cifrado com a chave k bit por bit. Então só para relembrar, o que exatamente é uma operação XOR, assim a operação XOR opera com 2 bits por vez e a saída é definida da seguinte forma se ambos os bits forem iguais, então a saída vai ser 0. Considerando que se os bits são diferentes, e a saída vai ser 1, é o que é a operação XOR, certo. (Consulte O Slide Time: 02:30) Então, em algum sentido, você pode imaginar que esse algoritmo de criptografia faz o mascaramento da mensagem com a chave, certo. Por isso, a operação XOR tem o efeito de mascarar a mensagem pouco a pouco com os bits da chave. Considerando que a operação de descriptografia como você pode imaginar, ela tem a operação reversa de mascaramento a saber desmascarar o efeito de chave do texto cifrado pouco a pouco. Então, o importante aqui é que já que a operação XOR é meio reversível aqui, você pode mascarar a mensagem usando a chave realizando a operação XOR. E para obter o efeito de desmascarar, é só ter que XOR a chave do texto cifrado para voltar sua mensagem. Por isso, agora vamos provar que esta cifra de Vernam ou one time pad é de fato perfeitamente segura. E podemos provar a sua segurança perfeita como por qualquer uma das 3 definições que vimos na última palestra. Por isso, vou provar que a cifra Vernam é de fato perfeitamente segura sobre o espaço de mensagens de cordas de l bits. E para isso vou usar a primeira definição alternativa de sigilo perfeito que discutimos na última palestra. A saber, vou provar que a distribuição do texto cifrado é independente do autor subjacente em qualquer instância da cifra Vernam. Para isso consideramos uma distribuição de probabilidade arbitrária sobre o espaço à plaina, e um par arbitrário de mensagens m0, m1 pertencente ao espaço de texto simples conforme aquela distribuição de probabilidade que tem uma probabilidade não zero de ocorrência. E também escolhemos um texto cifrado arbitrário, que tem uma probabilidade não zero de ocorrência. O que eu vou provar é que para qualquer m0 e m1 que nós colhemos aqui arbitrariamente e para qualquer texto cifrado c que colhemos arbitrariamente aqui, a probabilidade de que m0 seja criptografada em c, e a probabilidade de que m1 em criptografados seja c, sejam iguais, o que provará que a cifra de Vernam é perfeitamente segura. Por isso, agora vamos primeiro tentar computar a probabilidade condicional de que se o seu autor for m0, qual a probabilidade de que a cifra Vernam vá produzir o texto cifrado para ser c, certo. Assim, a probabilidade de que o autor do m0 vá produzir o texto cifrado, c, é o mesmo que a probabilidade de que a chave que é utilizada para a criptografia seja esta string, a saber, a chave é XOR de m0 e c. E qual é a probabilidade de que a chave que é obtida executando o algoritmo de geração de chaves seja de fato o XOR de m0 e c. Bem, é 1/2l. Pois, conforme a sintaxe de nosso algoritmo de geração de chaves, o algoritmo de geração de chaves está fora indo para a saída uma chave uniformemente aleatória. Assim, a probabilidade de que a chave aleatória uniformemente obtida por algoritmo de geração chave de fato satisfaça o valor XOR de m0 e c é 1/2l. Da mesma forma, a probabilidade de que a mensagem m1 seja criptografada no texto cifrado, c, é a mesma que o valor de chave que é utilizado para a criptografia é o XOR de m1 e c. E de novo, já que meu algoritmo de geração de chaves está indo para a saída de chaves aleatórias uniformes, a probabilidade de que minha chave seja XOR de m1 e c é 1/2l. Assim, uma vez que ambas as 2 probabilidades são iguais depois de ver um texto cifrado, que vai ser uma sequência de l bit, adversário não pode identificar se é uma criptografia de m0, ou se é uma criptografia de m1. E daí o adversário será completamente despreocupado. E é por isso que essa criptografia satisfaz a definição de sigilo perfeito. Por isso, agora temos um esquema de criptografia de candidato, que é perfeitamente seguro. (Consulte O Slide Time: 06 :17) Então agora você pode estar se perguntando que se temos um esquema de criptografia de candidato, o que é perfeitamente seguro, por que não podemos nos dar ao luxo de usá-lo na prática. Por isso, agora, vejamos algumas das limitações que são impostas pelo esquema de pad one time. A primeira limitação que se impõe aqui é que a chave deve ser tão grande quanto o texto à plaina porque o tamanho da chave é l assim como o tamanho do plaintexto também é l, certo. Isso significa que se você quiser dizer criptografar 1 GB arquivo, isso significa que se o remetente quiser criptografar um arquivo de 1 GB, então ele tem que concordar sobre uma chave que também é do tamanho 1 GB, o que parece muito imprático porque na prática visamos ir para processo de criptografia, onde podemos usar uma chave de tamanho pouco tamanho para criptografar mensagens longas. Portanto, essa é a primeira restrição que é imposta pela Vernam cipher. A segunda limitação que se impõe aqui é que não é possível reutilizar a mesma chave para criptografar mais de uma mensagem. Isso significa que cada instância da criptografia precisa de uma chave fresca. Eu ressalto aqui que quando digo aqui que não se pode reutilizar a chave, não quero dizer que não se pode reutilizar a chave na próxima instância, o que eu quero dizer aqui é que em cada instância, é preciso voltar a ser executado em uma instância independente ou em uma instância recente de algoritmo de geração de chaves. Está bem se a chave que você vai obter na próxima chamada de algoritmo de geração de chaves é a mesma que você obteve na chamada anterior. O que é importante aqui é que ambas as invocações da geração de chaves vão para a saída de saídas independentes. Assim, a partir do ponto de vista do adversário ou de um atacante que está interceptando texto cifrado, ele não estaria sabendo que as chaves que foram usadas se são iguais ou se são diferentes. A partir do ponto de vista do atacante, são chaves independentes. Por isso, a segunda restrição, que é imposta aqui é não é possível reter a mesma chave e manter-se em criptografar várias mensagens usando a mesma chave. Por exemplo, imagine um cenário em que o remetente vai usar ou reter a mesma chave k para criptografar 2 mensagens diferentes m0 e m1 em sequência. Isso significa que usou um k chave para criptografar primeiro uma mensagem m0 comunicou o texto cifrado. E suponhamos que seja novamente reter o mesmo valor de chave em vez de executar novamente o algoritmo de geração de chaves. E ele reutiliza a mesma chave k para criptografar uma próxima mensagem m1, e novamente, o texto cifrado é comunicado sobre o canal. E suponha que adversário esteja ciente desse fato de que a mesma chave foi retida e usada pelo remetente para criptografar duas mensagens m0 e m1. Então agora o que um atacante pode fazer é o seguinte. Desde que interceptou o texto cifrado c0, assim como ele interceptou o texto cifrado c1 e sabe a relação entre as mensagens m0 e k, m1 e k, e c0, c1. Nomeadamente, sabe-se que c0 é o XOR de m0 e k e sabe que c1 é o XOR de m1 e k. Se ele executar o XOR de c0 e c1, o efeito de k vai sumir, certo porque é isso que é a propriedade da operação XOR. Porque k será XORed com o próprio k, que lhe dará 0. E como resultado realizando o XOR de c0 e c1, o adversário vai obter o XOR de m0 e m1. Então agora você pode estar se perguntando o quanto de informação é realmente revelada pelo aprendizado do XOR de m0 e m1. E acontece que se trata de uma quantidade significativa de informações. E isso significa que não podemos reivindicar o perfeito sigilo para esse tipo de processo de criptografia em que o mesmo k agora é retido para criptografar várias mensagens. (Consulte O Slide Time: 09 :48) Então aqui está o que o vencedor do prêmio Turing, o lendário cientista da computação Michael Rabin tem a dizer sobre uma hora pad, ele diz que você nunca deve reutilizar um pad one time, ele é como um papel higiênico, porque se você reaproveita, as coisas podem ficar baguncedas, certo, então você nunca deve reutilizar a chave. Para cada instância do one time pad Vernam cifrão você precisa executar um algoritmo de geração de chaves e obter uma chave fresca para criptografar suas próximas mensagens. (Consulte O Tempo De Deslizamento: 10:14) Então estas são as 2 restrições impostas pela Vernam cipher. Agora, uma questão natural é se essas 2 restrições são apenas com respeito a uma plataforma de tempo ou de Vernam, ou são essas 2 restrições inerentes a qualquer cifra perfeitamente segura. O que agora vamos provar é que essas duas restrições são inerentes a qualquer cifra perfeitamente segura, para qualquer chave de cifração perfeitamente segura deve ser tão grande quanto o texto simples. E também provaremos que qualquer cifra perfeitamente segura, cada instância da criptografia precisa de uma chave fresca. (Consulte O Tempo De Deslizamento: 10:49) Então, vamos primeiro provar a primeira limitação aqui. Por isso, o teorema aqui, é imagine que você recebe uma cifra perfeitamente segura. Pode não ser uma plataforma de tempo, pode ser qualquer cifra perfeitamente segura. O teorema diz que se o esquema é perfeitamente seguro, então o espaço chave tem que ser tão grande quanto o espaço de mensagens, certo. Então, aqui está a prova, a prova vai ser por contradição. Por isso, ao contrário, imagine que apesar de meu esquema estar perfeitamente seguro meu espaço chave é menor do que o meu espaço de mensagens. Isso significa que o número de chaves candidatas é menor do que o número de candidatos à plaina. E para demonstração aqui é um exemplo, estou assumindo que o meu espaço de texto de fábrica candidato consiste em 3 texto simples e o meu espaço chave candidato é composto por 2 chaves possíveis. Então agora você considera a distribuição de probabilidade uniforme sobre o espaço da mensagem, isso significa que você considera um cenário em que o remetente poderia ter criptografado qualquer uma dessas 3 mensagens possíveis com igual probabilidade. E você considera um texto cifrado com cuja probabilidade de ocorrência é diferente de zero. Então, agora, deixe-me definir o conjunto M (c) que é o conjunto de todas as decrpções válidas do texto cifrado c, a saber, M (c) consiste em todo texto simples m do espaço de texto simples, que eu posso obter ao decriptografar o texto cifrado c sob diferentes chaves candidatas do espaço chave, certo. Por isso, novamente neste exemplo particular, se eu tentar descriptografar o texto cifrado c, eu tenho 2 chaves possíveis. Sobre decriptografia cifrada por k1, eu vou obter uma mensagem e sobre decriptografar cifração c pela segunda chave k2 eu obterá segunda mensagem que significa o que eu posso dizer é que a cardinalidade do conjunto M (c) é superior delimitado pela cardinalidade do espaço chave porque esse é o número máximo de decodificações distintas que você pode obter decriptografando o texto cifrado c aqui, e já que como parte da minha suposição, a cardinalidade do espaço chave é menor que a cardinalidade do espaço de mensagens, o que eu obtive aqui é que a cardinalidade de M (c) é estritamente menor que a cardinalidade do espaço chave que é menor que a cardinalidade da cardinalidade da mensagem espaço. O que significa aqui é que existe pelo menos uma mensagem do espaço da mensagem, espaço de texto simples, que nunca pode levar ao texto cifrado c que significa em decriptografar o texto cifrado, jamais obirei obter de volta aquele texto simples. Novamente neste exemplo específico, você pode ver que a decriptografia de c nunca pode te dar volta m3. E isso é uma violação da condição de sigilo perfeita porque a perfeita condição de sigilo diz que se você tem uma distribuição de probabilidade uniforme sobre o espaço de texto simples, então para cada texto cifrado c que ocorre com probabilidade não zero, deve ser uma criptografia potencial de todas as mensagens do candidato com probabilidades iguais ou em outro sentido se eu ver as definições originais de perfeito sigilo, o que chegamos aqui é o fato de que temos pelo menos uma mensagem é m, em que a probabilidade de ocorrência do m é diferente de zero, mas a probabilidade condicional de que m é criptografado no texto cifrado c é 0. Isso significa que essas 2 probabilidades não são iguais. E daí isso é uma violação do perfeito sigilo certo. Então, isso significa que provamos que em qualquer esquema de criptografia perfeitamente seguro, o espaço chave tem que ser tão grande quanto o espaço de mensagens. (Consulte O Tempo De Deslizamento: 14 :20) Agora, qual é a implicação desse teorema. Imagine o seu espaço chave é o conjunto de todas as cordas possíveis de comprimento x. Isso significa que o meu processo de criptografia suporta criptografia de strings de bits x. Isso significa que a cardinalidade do espaço chave não passa de 2x. E, da mesma forma, imagine que meu processo de criptografia suporta espaço de texto simples de cordas de y bit que significa que o texto à plaina tem que ser y bit strings e como resultado, a cardinalidade do meu espaço de mensagens é 2y. Agora conforme este teorema é meu esquema é perfeitamente seguro Eu preciso da cardinalidade do espaço chave para estar tão grande quanto a cardinalidade do espaço de mensagens, isso significa que 2x deve ser maior que igual a 2y. E como implicação disso, eu fico com o fato de que x deve ser maior do que igual a y, isso significa que o comprimento da chave deve ser tão grande quanto o texto à parte. Essa é a primeira limitação de qualquer cifra perfeitamente segura, a saber, a chave deve ser tão grande o texto à plaina. (Consulte O Tempo De Deslizamento: 15 :24) Agora, provemos a segunda limitação de qualquer cifra perfeitamente segura. E eu não estaria provando isso de forma rigorosa e formal, vou apenas dar um detalhe de altíssimo nível da prova aqui. Por isso, os estados teorema que imaginam que você recebe uma cifra perfeitamente segura sobre o espaço de texto simples m e espaço chave k, então cada instância do processo de criptografia dessa cifra deve exigir que uma chave independente seja gerada pelo algoritmo de geração de chaves. Isso significa que não é possível reter a mesma chave para criptografar mais de uma mensagem. Então agora deixe-nos novamente tentar provar isso você usando uma contradição. Então imagine um cenário em que o remetente retém a mesma chave k para criptografar 2 mensagens m1 e m2 em sequência, certo. Por isso, tem mensagem criptografada m1 produzindo texto cifrado c1 comunicado sobre o canal, e então ele tem que usar a mesma chave k para criptografar uma segunda mensagem na sequência. E novamente o texto cifrado é comunicado sobre o canal. E o adversário interceptou tanto o texto cifrado quanto o adversário está ciente do fato de que a mesma chave desconhecida k foi retida e usada para criptografar tanto as mensagens m1 quanto m2. O que nós vamos provar é que se algo desse tipo aconteceu, então você nunca poderá alcançar um sigilo perfeito, certo. Então imagine 2 seqüências diferentes de texto simples. A primeira sequência é quando a primeira mensagem é m1 e a segunda mensagem também é m1 e na segunda sequência m ’, as seqüências de mensagens são m1 e m2, em que m1 e m2 são diferentes. E imagine que adversário tenha interceptado um texto cifrado que consiste em 2 seqüências de texto cifrado onde o texto da primeira cifra é c1 e o segundo texto cifrado c2, certo. Assim, conforme a exigência do sigilo perfeito, se o adversário tiver obtido uma sequência de texto cifrado sendo c1 e c2, e se adversário tiver uma informação prévia que estas 2 sequências de mensagens, que poderiam ter sido criptografadas em c1 c2 poderiam ser m1, m1 ou m1, m2, então a exigência de perfeito sigilo é que com igual probabilidade a sequência de texto cifrado c1, c2 deve ser qualquer criptografia de m1, m1 assim como deve ser uma criptografia potencial de m1, m2 direito. Isso significa, se eu considerar a probabilidade lateral esquerda aqui então eu introduzi aqui 2 variáveis aleatórias c1 e c2 em boldface, o que denota o valor da primeira sequência de texto cifrado e a segunda sequência de texto cifrado. E, da mesma forma, introduzi 2 variáveis aleatórias, boldface m1 e boldface m2, para notar o candidato primeiro plaintexto e o candidato segundo plaintexto. Por isso, minha afirmação aqui é que a probabilidade de que a sua probabilidade lateral esquerda e a sua probabilidade laterais da mão direita nunca possam ser iguais, o que é uma violação do sigilo perfeito. Pictorialmente a exigência de um sigilo perfeito deve ser que não importa se a primeira sequência de mensagens m1, m1 é criptografada ou se a segunda sequência de mensagem m1, m2 é criptografada usando a chave conforme seu processo de criptografia com igual probabilidade ele deve levá-lo à sequência de texto cifrado c1, c2, se em todos os seus processos de criptografia perfeitamente seguros. Mas se for esse o caso, isso significa imaginar um cenário em que realmente a sequência de mensagens m1, m1 e uma sequência de mensagens m1, m2, ambas levam a uma sequência de texto de criptografia c1, c2 com probabilidade igual sob a mesma e chave k, então significa um erro de decriptografia. Pois isso significa que se você descriptografar o texto cifrado c2 para usar a chave k, então ele deverá estar levando você de volta para o texto simples m1 assim como deve levá-lo de volta para o texto simples m2, o que significa que há um erro de correção em seu processo de criptografia. Isso significa que há um erro de decriptografia em seu processo de criptografia, o que é uma violação do fato de que seu processo de criptografia é seguro, pois um dos requisitos de qualquer cifra segura é o requisito de correção, o que demanda que sua descrição deve ser inequívoca, mas se estamos em um cenário como este, em que tanto a sequência de mensagens m1 m1 e a sequência de mensagens m1 m2 leva à mesma sequência de texto cifrada c1, c2. Então isso significa que se eu apenas descriptografar a sequência de texto cifrado c2 ele poderia me levar de volta a m1 assim como poderia me levar de volta a m2. Isso significa que há uma ambiguidade na decriptografia do meu próprio processo de encriptação original, o que é uma contradição, isso prova informalmente o teorema de que cada instância do processo de criptografia deve correr de nova instância do algoritmo de geração de chaves direito. Então isso me leva ao fim dessa palestra. Só para resumir. Nesta palestra discutimos um candidato, processo de criptografia perfeitamente seguro, a saber, uma plataforma de tempo ou cifra Vernam e provamos o seu perfeito sigilo. Também vimos as 2 restrições impostas por uma hora pad. E argumentamos que essas 2 restrições, a saber, o tamanho da chave sendo tão grande quanto a mensagem e a chave fresca para cada instância da criptografia são inerentes a qualquer processo de criptografia perfeitamente seguro. Espero que tenha gostado desta palestra. Obrigado.