Confusão e difusão - Confusion and diffusion

Na criptografia , confusão e difusão são duas propriedades da operação de uma cifra segura identificada por Claude Shannon em seu relatório classificado de 1945, A Mathematical Theory of Cryptography . Essas propriedades, quando presentes, funcionam para impedir a aplicação de estatísticas e outros métodos de criptanálise .

Esses conceitos também são importantes no projeto de funções hash robustas e geradores de números pseudo - aleatórios, onde a decorrelação dos valores gerados é de suma importância.

Definição

Confusão

Confusão significa que cada dígito binário (bit) do texto cifrado deve depender de várias partes da chave, obscurecendo as conexões entre os dois.

A propriedade de confusão oculta a relação entre o texto cifrado e a chave.

Esta propriedade torna difícil encontrar a chave no texto cifrado e se um único bit em uma chave for alterado, o cálculo da maioria ou todos os bits no texto cifrado será afetado.

A confusão aumenta a ambigüidade do texto cifrado e é usada tanto por cifras de bloco quanto de fluxo.

Em redes de substituição-permutação , a confusão é fornecida por caixas de substituição .

Difusão

Difusão significa que, se alterarmos um único bit do texto simples, cerca de metade dos bits do texto cifrado deverá mudar e, da mesma forma, se mudarmos um bit do texto cifrado, cerca de metade dos bits do texto simples deverá mudar. Isso é equivalente à expectativa de que os esquemas de criptografia exibam um efeito de avalanche .

O objetivo da difusão é ocultar a relação estatística entre o texto cifrado e o texto simples. Por exemplo, a difusão garante que quaisquer padrões no texto simples, como bits redundantes, não sejam aparentes no texto cifrado. As cifras de bloco conseguem isso "difundindo" as informações sobre a estrutura do texto simples nas linhas e colunas da cifra.

Em redes de substituição-permutação, a difusão é fornecida por caixas de permutação .

Teoria

Nas definições originais de Shannon, confusão se refere a tornar a relação entre o texto cifrado e a chave simétrica o mais complexa e envolvente possível; difusão refere-se a dissipar a estrutura estatística do texto simples sobre a maior parte do texto cifrado . Essa complexidade é geralmente implementada por meio de uma série bem definida e repetível de substituições e permutações . Substituição refere-se à substituição de certos componentes (geralmente bits) por outros componentes, seguindo certas regras. A permutação refere-se à manipulação da ordem dos bits de acordo com algum algoritmo. Para ser eficaz, qualquer não uniformidade de bits de texto simples precisa ser redistribuída por estruturas muito maiores no texto cifrado, tornando essa não uniformidade muito mais difícil de detectar.

Em particular, para uma entrada escolhida aleatoriamente, se alguém inverter o i -ésimo bit, então a probabilidade de que o j- ésimo bit de saída mude deve ser metade, para qualquer i e j - isso é denominado critério estrito de avalanche . Mais geralmente, pode-se exigir que a inversão de um conjunto fixo de bits altere cada bit de saída com probabilidade pela metade.

Um dos objetivos da confusão é dificultar muito a localização da chave, mesmo que haja um grande número de pares de texto simples-texto cifrado produzidos com a mesma chave. Portanto, cada bit do texto cifrado deve depender da chave inteira e, de maneiras diferentes, de diferentes bits da chave. Em particular, alterar um bit da chave deve alterar o texto cifrado completamente. A maneira mais simples de obter difusão e confusão é usar uma rede de substituição-permutação . Nesses sistemas, o texto simples e a chave geralmente têm um papel muito semelhante na produção da saída, portanto, o mesmo mecanismo garante tanto a difusão quanto a confusão.

Aplicado à criptografia

Projetar um método de criptografia usa os princípios de confusão e difusão. Confusão significa que o processo altera drasticamente os dados da entrada para a saída, por exemplo, traduzindo os dados por meio de uma tabela não linear criada a partir da chave. Existem muitas maneiras de reverter cálculos lineares, portanto, quanto mais não linear, mais ferramentas de análise são quebradas.

Difusão significa que alterar um único caractere da entrada mudará muitos caracteres da saída. Bem feito, cada parte da entrada afeta todas as partes da saída, tornando a análise muito mais difícil. Nenhum processo de difusão é perfeito: sempre deixa passar alguns padrões. Uma boa difusão espalha esses padrões amplamente pela saída e, se houver vários padrões passando, eles se misturam. Isso torna os padrões muito mais difíceis de detectar e aumenta muito a quantidade de dados a serem analisados ​​para quebrar a cifra.

Análise de AES

O Advanced Encryption Standard (AES) apresenta excelente confusão e difusão. Suas tabelas de consulta de confusão são muito não lineares e boas para destruir padrões. Seu estágio de difusão espalha todas as partes da entrada para todas as partes da saída: mudar um bit de entrada muda a metade dos bits de saída, em média. Tanto a confusão quanto a difusão são repetidas várias vezes para cada entrada para aumentar a quantidade de embaralhamento. A chave secreta é misturada em cada estágio para que um invasor não possa calcular previamente o que a cifra faz.

Nada disso acontece quando um simples embaralhamento de um estágio é baseado em uma chave. Os padrões de entrada fluiriam direto para a saída. Pode parecer aleatório à vista, mas a análise encontraria padrões óbvios e a cifra poderia ser quebrada.

Veja também

• Rede de substituição-permutação
• Efeito avalanche

Referências

Trabalhos citados

• Claude E. Shannon, "A Mathematical Theory of Cryptography" , Bell System Technical Memo MM 45-110-02, 1 de setembro de 1945.
• Claude E. Shannon, " Communication Theory of Secrecy Systems ", Bell System Technical Journal , vol. 28-4, páginas 656–715, 1949. [1]
• Wade Trappe e Lawrence C. Washington, Introdução à Criptografia com Teoria de Codificação. Segunda edição. Pearson Prentice Hall, 2006.