Sigilo perfeito

RKA11C Considere o seguinte jogo: Eve instrui Bob para entrar em uma sala. Bob encontra a sala vazia com exceção de alguns cadeados, uma caixa vazia e um baralho de cartas. Eve diz para Bob selecionar uma carta a partir do baralho, e escondê-la da melhor forma possível. As regras são simples. Bob não pode sair da sala dos objetos, as cartas e as chaves devem ficar dentro do quarto. Ele pode colocar, no máximo, uma carta na caixa. Eve concorda que ela nunca viu os cadeados. Ele ganha o jogo se Eve não for capaz de descobrir a sua carta, então, qual é a melhor estratégia? Bob selecionou uma carta 6 de ouro e jogou na caixa. Primeiro, ele considerou os diferentes tipos de cadeados, talvez ele deva trancar a caixa com o cadeado de chave. No entanto, ele considera outros modelos, então ele pega o cadeado de combinação. A senha está na parte de trás, por isso ele deve trancar e riscar a senha. Parece ser a melhor escolha. Mas, de repente, ele percebe o problema. As cartas restantes na mesa vazam informações sobre a sua escolha, já que está faltando uma carta no baralho. Os cadeados são uma isca. Ele não deveria separar sua carta do baralho. Ele retorna a sua carta para o baralho, mas não consegue lembrar da posição inicial. Assim, ele pega as cartas e as embaralha. Embaralhar é o melhor bloqueio porque não deixa nenhuma informação sobre sua escolha. A carta agora tem a mesma probabilidade de qualquer carta do baralho, ele agora pode deixar as cartas abertamente em confiança. Bob ganha o jogo, porque o melhor que Eve pode fazer é simplesmente palpitar, pois não há informações sobre sua escolha. E o mais importante, mesmo se déssemos à Eve um poder computacional ilimitado, ela não pode fazer nada melhor do que um palpite. Isso define o que chamamos de sigilo perfeito. Em 1.º de setembro de 1945, com 29 anos, Claude Shannon publicou um documento confidencial sobre essa ideia. Shannon deu a primeira prova matemática para saber como e porque uma cifra de uso único é perfeitamente secreta. Shannon pensa sobre esses esquemas de criptografia da seguinte maneira: Imagine que ali se escreva uma mensagem de 20 letras para Bob, isso é equivalente a selecionar uma página específica do espaço da mensagem. O espaço da mensagem pode ser pensado com uma completa coleção de todas as possíveis mensagens com 20 letras. Qualquer coisa que você pensar que tem 20 letras é uma página dessa pilha. Em seguida, Alice aplica uma chave partilhada, que é uma lista de 20 letras geradas aleatoriamente, em turnos entre 1 e 26. O espaço da chave é a coleção completa de todos os resultados possíveis. Assim, gerando uma chave que é equivalente a selecionar uma página, a partir desta pilha de forma aleatória. Quando ela aplica a troca para criptografar a mensagem, ela acaba com o texto encriptado. O espaço de texto encriptado representa todos os resultados possíveis de uma encriptação. Quando se aplica a chave, ela dá indicação de uma única página nessa pilha. Note que o tamanho do espaço da mensagem é igual ao tamanho do espaço da chave, que é igual ao tamanho do espaço do texto encriptado. Isso define o que chamamos de sigilo perfeito, pois se alguém tem acesso a uma página de apenas texto encriptado, a única coisa que ele sabe é que cada mensagem tem a mesma probabilidade. Assim, nenhum poder computacional jamais poderia ajudar a melhorar um palpite cego. Agora o grande problema é... como nós enviamos essas grandes chaves com antecedência? Para resolver esse problema, precisamos flexibilizar nossa definição de sigilo, através do desenvolvimento de uma definição de pseudoaleatoriedade.