Distância unicidade - Unicity distance

Na criptografia , a distância de unicidade é o comprimento de um texto cifrado original necessário para quebrar a cifra, reduzindo o número de chaves espúrias possíveis a zero em um ataque de força bruta . Ou seja, depois de tentar todas as chaves possíveis , deve haver apenas uma decifração que faça sentido, ou seja, a quantidade esperada de texto cifrado necessária para determinar a chave completamente, supondo que a mensagem subjacente tenha redundância.

Claude Shannon definiu a distância unicidade em seu artigo de 1949 " Communication Theory of Secrecy Systems ".

Considere um ataque à string de texto cifrado "WNAIW" criptografada usando uma cifra de Vigenère com uma chave de cinco letras. É concebível que essa string possa ser decifrada em qualquer outra string - RIVER e WATER são possibilidades para certas chaves. Esta é uma regra geral da criptoanálise : sem informações adicionais, é impossível decodificar esta mensagem.

Claro, mesmo neste caso, apenas um certo número de teclas de cinco letras resultará em palavras em inglês. Tentando todas as chaves possíveis, não obteremos apenas RIVER e WATER, mas também SXOOS e KHDOP. O número de chaves "funcionais" provavelmente será muito menor do que o conjunto de todas as chaves possíveis. O problema é saber qual dessas chaves "funcionais" é a certa; o resto é espúrio.

Relação com o tamanho da chave e possíveis textos simples

Em geral, dadas as suposições específicas sobre o tamanho da chave e o número de mensagens possíveis, existe um comprimento médio de texto cifrado em que há apenas uma chave (em média) que irá gerar uma mensagem legível. No exemplo acima, vemos apenas caracteres ingleses maiúsculos , portanto, se assumirmos que o texto simples tem esta forma, então existem 26 letras possíveis para cada posição na string. Da mesma forma, se assumirmos chaves em maiúsculas de cinco caracteres, existem K = 26 5 chaves possíveis, das quais a maioria não "funcionará".

Um número enorme de mensagens possíveis, N, pode ser gerado usando até mesmo este conjunto limitado de caracteres: N = 26 L , onde L é o comprimento da mensagem. No entanto, apenas um conjunto menor deles é texto simples legível devido às regras da linguagem, talvez M deles, onde M é provavelmente muito menor do que N. Além disso, M tem uma relação um-para-um com o número de chaves que funcionam, portanto, dadas K chaves possíveis, apenas K × (M / N) delas "funcionará". Uma delas é a chave correta, as demais são falsas.

Uma vez que M / N fica arbitrariamente pequeno à medida que o comprimento L da mensagem aumenta, há eventualmente algum L que é grande o suficiente para tornar o número de chaves espúrias igual a zero. Grosso modo, este é o L que faz KM / N = 1. Este L é a distância unicidade.

Relação com entropia chave e redundância de texto simples

A distância de unicidade pode ser definida de forma equivalente como a quantidade mínima de texto cifrado necessária para permitir que um adversário ilimitado computacionalmente recupere a chave de criptografia exclusiva.

A distância de unicidade esperada pode então ser mostrada como:

onde U é a distância de unicidade, H ( k ) é a entropia do espaço da chave (por exemplo, 128 para 2 128 chaves equiprováveis, um pouco menos se a chave for uma frase-senha memorizada). D é definido como a redundância de texto simples em bits por caractere.

Agora, um alfabeto de 32 caracteres pode transportar 5 bits de informação por caractere (como 32 = 2 5 ). Em geral, o número de bits de informação por caractere é log 2 (N) , onde N é o número de caracteres do alfabeto e log 2 é o logaritmo binário . Portanto, para o inglês, cada caractere pode transmitir log 2 (26) = 4,7 bits de informação.

No entanto, a quantidade média de informações reais transportadas por caractere em um texto significativo em inglês é de apenas cerca de 1,5 bits por caractere. Portanto, a redundância de texto simples é D = 4,7 - 1,5 = 3,2.

Basicamente, quanto maior a distância unicidade, melhor. Para um bloco de tempo único de tamanho ilimitado, dada a entropia ilimitada do espaço-chave, temos , o que é consistente com o bloco único ser inquebrável.

Distância unicidade da cifra de substituição

Para uma cifra de substituição simples , o número de chaves possíveis é 26! = 4,0329 × 10 26 = 2 88,4 , o número de maneiras pelas quais o alfabeto pode ser permutado. Assumindo que todas as chaves são igualmente prováveis, H ( k ) = log 2 (26!) = 88,4 bits. Para o texto em inglês D = 3,2 , portanto U = 88,4 / 3,2 = 28 .

Assim, com 28 caracteres de texto cifrado, deveria ser teoricamente possível calcular um texto simples em inglês e, portanto, a chave.

Aplicação prática

A distância de unicidade é uma medida teórica útil, mas não diz muito sobre a segurança de uma cifra de bloco quando atacada por um adversário com recursos do mundo real (limitados). Considere uma cifra de bloco com uma distância unicidade de três blocos de texto cifrado. Embora haja informações claramente suficientes para um adversário sem limites computacionalmente encontrar a chave certa (pesquisa exaustiva simples), isso pode ser computacionalmente inviável na prática.

A distância de unicidade pode ser aumentada reduzindo a redundância de texto simples. Uma maneira de fazer isso é implantar técnicas de compactação de dados antes da criptografia, por exemplo, removendo vogais redundantes, mantendo a legibilidade. De qualquer forma, essa é uma boa ideia, pois reduz a quantidade de dados a serem criptografados.

Pode-se presumir que os textos cifrados maiores que a distância unicidade têm apenas uma descriptografia significativa. Os textos cifrados mais curtos do que a distância unicidade podem ter várias descriptografias plausíveis. A distância de unicidade não é uma medida de quanto texto cifrado é necessário para a criptoanálise, mas quanto texto cifrado é necessário para que haja apenas uma solução razoável para a criptoanálise.

Referências

links externos