Cifra de substituição - Substitution cipher

Na criptografia , uma cifra de substituição é um método de criptografia em que unidades de texto simples são substituídas pelo texto cifrado , de forma definida, com o auxílio de uma chave; as "unidades" podem ser letras simples (as mais comuns), pares de letras, tercinas de letras, misturas das anteriores e assim por diante. O receptor decifra o texto executando o processo de substituição inversa para extrair a mensagem original.

As cifras de substituição podem ser comparadas com as cifras de transposição . Em uma cifra de transposição, as unidades do texto simples são reorganizadas em uma ordem diferente e geralmente bastante complexa, mas as unidades em si permanecem inalteradas. Em contraste, em uma cifra de substituição, as unidades do texto simples são mantidas na mesma sequência no texto cifrado, mas as próprias unidades são alteradas.

Existem vários tipos diferentes de cifras de substituição. Se a cifra opera em letras únicas, é denominada cifra de substituição simples ; uma cifra que opera em grupos maiores de letras é denominada poligráfica . Uma cifra monoalfabética usa substituição fixa em toda a mensagem, enquanto uma cifra polialfabética usa uma série de substituições em diferentes posições na mensagem, onde uma unidade do texto simples é mapeada para uma das várias possibilidades no texto cifrado e vice-versa.

Substituição simples

ROT13 é uma cifra de César , um tipo de cifra de substituição. No ROT13, o alfabeto é girado em 13 etapas.

A substituição de letras únicas separadamente - substituição simples - pode ser demonstrada escrevendo o alfabeto em alguma ordem para representar a substituição. Isso é denominado alfabeto de substituição . O alfabeto cifrado pode ser alterado ou invertido (criando as cifras de César e Atbash , respectivamente) ou embaralhado de uma forma mais complexa, caso em que é chamado de alfabeto misto ou alfabeto desordenado . Tradicionalmente, os alfabetos mistos podem ser criados escrevendo primeiro uma palavra-chave, removendo as letras repetidas dela e, em seguida, escrevendo todas as letras restantes do alfabeto na ordem usual.

Usando este sistema, a palavra-chave " zebras " nos dá os seguintes alfabetos:

Alfabeto em texto simples A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Alfabeto de texto cifrado ZEBRASCDFGHIJKLMNOPQTUVWXY

Uma mensagem 

flee at once. we are discovered!

codificações para 

SIAA ZQ LKBA. VA ZOA RFPBLUAOAR!

Normalmente, o texto cifrado é escrito em blocos de comprimento fixo, omitindo pontuação e espaços; isso é feito para disfarçar os limites das palavras do texto simples e para ajudar a evitar erros de transmissão. Esses blocos são chamados de "grupos" e, às vezes, uma "contagem de grupo" (ou seja, o número de grupos) é fornecida como uma verificação adicional. Grupos de cinco letras são freqüentemente usados, datando de quando as mensagens costumavam ser transmitidas por telégrafo : 

SIAAZ QLKBA VAZOA RFPBL UAOAR

Se o comprimento da mensagem não for divisível por cinco, ela pode ser preenchida no final com " nulos ". Podem ser quaisquer caracteres que se descriptografem para um absurdo óbvio, de modo que o receptor possa identificá-los e descartá-los com facilidade.

O alfabeto do texto cifrado às vezes é diferente do alfabeto do texto simples; por exemplo, na cifra do chiqueiro , o texto cifrado consiste em um conjunto de símbolos derivados de uma grade. Por exemplo:

Um exemplo de mensagem de chiqueiro

No entanto, tais características fazem pouca diferença para a segurança de um esquema - no mínimo, qualquer conjunto de símbolos estranhos pode ser transcrito de volta para um alfabeto AZ e tratado normalmente.

Em listas e catálogos para vendedores, às vezes é usada uma criptografia muito simples para substituir dígitos numéricos por letras.

Dígitos em texto simples 1234567890
Alfabetos de texto cifrado MAKEPROFIT 

Exemplo: MAT seria usado para representar 120.

Segurança para cifras de substituição simples

Embora o método tradicional de palavras-chave para criar um alfabeto de substituição misto seja simples, uma séria desvantagem é que as últimas letras do alfabeto (que são em sua maioria de baixa frequência) tendem a ficar no final. Uma maneira mais eficaz de construir um alfabeto misto é gerar o alfabeto de substituição de forma totalmente aleatória.

Embora o número de alfabetos de substituição possíveis seja muito grande (26! ≈ 2 88,4 , ou cerca de 88 bits ), essa cifra não é muito forte e pode ser facilmente quebrada. Desde que a mensagem tenha um comprimento razoável (veja abaixo), o criptanalista pode deduzir o significado provável dos símbolos mais comuns, analisando a distribuição de frequência do texto cifrado. Isso permite a formação de palavras parciais, que podem ser preenchidas provisoriamente, expandindo progressivamente a solução (parcial) (consulte a análise de frequência para uma demonstração disso). Em alguns casos, as palavras subjacentes também podem ser determinadas a partir do padrão de suas letras; por exemplo, atrair , ósseo e palavras com esses dois como raiz são as únicas palavras comuns em inglês com o padrão ABBCADB . Muitas pessoas resolvem essas cifras por recreação, como os quebra-cabeças de criptogramas do jornal.

De acordo com a distância unicidade do inglês , 27,6 letras de texto cifrado são necessárias para quebrar uma substituição simples de alfabeto misto. Na prática, normalmente são necessárias cerca de 50 letras, embora algumas mensagens possam ser interrompidas com menos se padrões incomuns forem encontrados. Em outros casos, o texto simples pode ser planejado para ter uma distribuição de frequência quase plana, e textos simples muito mais longos serão então exigidos pelo criptanalista.

Nomenclator

A mensagem do nomenclador forjada usada no gráfico de Babington
Uma tabela de códigos do nomenclador francês

Uma variante comum da cifra de substituição é o nomenclator . Nomeado após o funcionário público que anunciou os títulos dos dignitários visitantes, esta cifra usa uma pequena folha de código contendo letras, sílabas e tabelas de substituição de palavras, às vezes homofônicas, que normalmente convertiam símbolos em números. Originalmente, a parte do código era restrita aos nomes de pessoas importantes, daí o nome da cifra; nos últimos anos, abrangia também muitas palavras comuns e nomes de lugares. Os símbolos para palavras inteiras (palavras- código na linguagem moderna) e letras ( cifra na linguagem moderna) não foram distinguidos no texto cifrado. Os Rossignols ' Grande Cifra usados por Louis XIV da França era um deles.

Os nomencladores eram a tarifa padrão da correspondência diplomática , espionagem e conspiração política avançada do início do século XV ao final do século XVIII; a maioria dos conspiradores era e continua sendo menos sofisticada criptograficamente. Embora os criptoanalistas de inteligência do governo estivessem sistematicamente quebrando os nomencladores em meados do século XVI, e sistemas superiores estivessem disponíveis desde 1467, a resposta usual à criptoanálise era simplesmente tornar as tabelas maiores. No final do século XVIII, quando o sistema estava começando a desaparecer, alguns nomencladores tinham 50.000 símbolos.

No entanto, nem todos os nomencladores foram quebrados; hoje, a criptoanálise de textos cifrados arquivados continua sendo uma área frutífera de pesquisa histórica .

Substituição homofônica

Uma das primeiras tentativas de aumentar a dificuldade dos ataques de análise de frequência em cifras de substituição foi disfarçar as frequências das letras em texto simples pela homofonia . Nessas cifras, as letras do texto simples são mapeadas para mais de um símbolo de texto cifrado. Normalmente, os símbolos de texto simples de frequência mais alta recebem mais equivalentes do que letras de frequência mais baixa. Desta forma, a distribuição de frequência é achatada, tornando a análise mais difícil.

Uma vez que mais de 26 caracteres serão necessários no alfabeto do texto cifrado, várias soluções são empregadas para inventar alfabetos maiores. Talvez o mais simples seja usar um 'alfabeto' de substituição numérica. Outro método consiste em variações simples do alfabeto existente; maiúsculas, minúsculas, de cabeça para baixo, etc. De forma mais artística, embora não necessariamente mais segura, algumas cifras homofônicas empregavam alfabetos totalmente inventados de símbolos fantasiosos.

As cifras de Beale são outro exemplo de cifra homofônica. Esta é uma história de um tesouro enterrado que foi descrita em 1819-21 por meio de um texto cifrado que foi codificado para a Declaração de Independência. Aqui, cada caractere de texto cifrado foi representado por um número. O número foi determinado tomando o caractere de texto simples e encontrando uma palavra na Declaração de Independência que começava com esse caractere e usando a posição numérica dessa palavra na Declaração de Independência como a forma criptografada dessa carta. Como muitas palavras na Declaração de Independência começam com a mesma letra, a criptografia desse caractere pode ser qualquer um dos números associados às palavras na Declaração de Independência que começam com essa letra. Decifrar o caractere de texto criptografado X (que é um número) é tão simples quanto procurar a palavra X da Declaração de Independência e usar a primeira letra dessa palavra como o caractere descriptografado.

Outra cifra homofônica foi descrita por Stahl e foi uma das primeiras tentativas de fornecer segurança para sistemas de dados em computadores por meio de criptografia. Stahl construiu a cifra de forma que o número de homófonos de um determinado caractere fosse proporcional à freqüência do caractere, tornando a análise da freqüência muito mais difícil.

A cifra do livro e o tabuleiro de damas são tipos de cifra homofônica.

Francesco I Gonzaga , duque de Mântua , usou o primeiro exemplo conhecido de uma cifra de substituição homofônica em 1401 para correspondência com Simone de Crema.

Substituição polialfabética

Artigo principal: Cifra polialfabética

O trabalho de Al-Qalqashandi (1355-1418), baseado no trabalho anterior de Ibn al-Durayhim (1312-1359), continha a primeira discussão publicada sobre a substituição e transposição de cifras, bem como a primeira descrição de um polialfabético cifra, na qual cada letra do texto simples é atribuída a mais de um substituto. As cifras de substituição polialfabéticas foram posteriormente descritas em 1467 por Leone Battista Alberti na forma de discos. Johannes Trithemius , em seu livro Steganographia ( grego antigo para "escrita oculta") introduziu a forma agora mais padrão de um quadro (ver abaixo; cerca de 1500, mas não publicado até muito mais tarde). Uma versão mais sofisticada usando alfabetos mistos foi descrita em 1563 por Giovanni Battista della Porta em seu livro, De Furtivis Literarum Notis ( latim para "Sobre caracteres ocultos na escrita").

Em uma cifra polialfabética, vários alfabetos de cifra são usados. Para facilitar a criptografia, todos os alfabetos são geralmente escritos em uma grande tabela , tradicionalmente chamada de tableau . O quadro é geralmente 26 × 26, de modo que 26 alfabetos de texto cifrado completos estão disponíveis. O método de preencher o quadro e de escolher o alfabeto a ser usado a seguir define a cifra polialfabética específica. Todas essas cifras são mais fáceis de quebrar do que se acreditava, pois os alfabetos de substituição são repetidos para textos simples suficientemente grandes.

Um dos mais populares foi o de Blaise de Vigenère . Publicado pela primeira vez em 1585, era considerado inquebrável até 1863 e, de fato, era comumente chamado de le chiffre indéchiffrable (em francês para "cifra indecifrável").

Na cifra de Vigenère , a primeira linha do quadro é preenchida com uma cópia do alfabeto em texto simples e as linhas sucessivas são simplesmente deslocadas um lugar para a esquerda. (Esse quadro simples é chamado de tabula recta e corresponde matematicamente à adição do texto simples e das letras-chave, módulo 26.) Uma palavra-chave é então usada para escolher o alfabeto do texto cifrado a ser usado. Cada letra da palavra-chave é usada sucessivamente e, em seguida, são repetidas novamente desde o início. Portanto, se a palavra-chave for 'CAT', a primeira letra do texto simples é codificada no alfabeto 'C', a segunda em 'A', a terceira em 'T', a quarta em 'C' novamente e assim por diante. Na prática, as chaves de Vigenère eram frequentemente frases com várias palavras.

Em 1863, Friedrich Kasiski publicou um método (provavelmente descoberto secretamente e independentemente antes da Guerra da Crimeia por Charles Babbage ) que permitia o cálculo do comprimento da palavra-chave em uma mensagem cifrada de Vigenère. Uma vez feito isso, as letras do texto cifrado que foram criptografadas sob o mesmo alfabeto poderiam ser selecionadas e atacadas separadamente como uma série de substituições simples semi-independentes - complicadas pelo fato de que dentro de um alfabeto as letras eram separadas e não formavam palavras completas, mas simplificado pelo fato de que geralmente uma tabula recta tinha sido empregada.

Como tal, ainda hoje uma cifra do tipo Vigenère deveria teoricamente ser difícil de quebrar se alfabetos mistos forem usados ​​no quadro, se a palavra-chave for aleatória e se o comprimento total do texto cifrado for menor que 27,67 vezes o comprimento da palavra-chave. Esses requisitos raramente são compreendidos na prática e, portanto, a segurança da mensagem criptografada Vigenère é geralmente menor do que deveria.

Outros polialfabéticos notáveis ​​incluem:

  • A cifra de Gronsfeld. Ele é idêntico ao Vigenère, exceto que apenas 10 alfabetos são usados ​​e, portanto, a "palavra-chave" é numérica.
  • A cifra Beaufort . É praticamente igual ao Vigenère, exceto que a tabula recta é substituída por uma invertida, matematicamente equivalente a ciphertext = key - plaintext. Esta operação é auto-inversa , em que a mesma tabela é usada para criptografar e descriptografar.
  • A cifra autokey , que mistura texto simples com uma chave para evitar a periodicidade .
  • A cifra de chave em execução , em que a chave é feita muito longa usando uma passagem de um livro ou texto semelhante.

As cifras de fluxo modernas também podem ser vistas, de uma perspectiva suficientemente abstrata, como uma forma de cifra polialfabética na qual todo o esforço foi feito para tornar o fluxo - chave o mais longo e imprevisível possível.

Substituição poligráfica

Em uma cifra de substituição poligráfica, as letras do texto simples são substituídas em grupos maiores, em vez de substituir as letras individualmente. A primeira vantagem é que a distribuição de frequência é muito mais plana do que a de letras individuais (embora não seja realmente plana em idiomas reais; por exemplo, 'TH' é muito mais comum do que 'XQ' em inglês). Em segundo lugar, o maior número de símbolos requer correspondentemente mais texto cifrado para analisar produtivamente as frequências das letras.

Para substituir pares de letras, seria necessário um alfabeto de substituição de 676 símbolos ( ). No mesmo De Furtivis Literarum Notis mencionado acima, della Porta realmente propôs tal sistema, com um quadro 20 x 20 (para as 20 letras do alfabeto italiano / latino que ele estava usando) preenchido com 400 glifos únicos . No entanto, o sistema era impraticável e provavelmente nunca foi realmente usado.

A mais antiga cifra digital prática (substituição de pares) foi a chamada cifra Playfair , inventada por Sir Charles Wheatstone em 1854. Nesta cifra, uma grade 5 x 5 é preenchida com as letras de um alfabeto misto (duas letras, geralmente I e J, são combinados). Uma substituição digital é então simulada tomando pares de letras como dois cantos de um retângulo e usando os outros dois cantos como o texto cifrado (veja o artigo principal da cifra Playfair para um diagrama). Regras especiais lidam com letras duplas e pares na mesma linha ou coluna. A Playfair estava em uso militar desde a Guerra dos Bôeres até a Segunda Guerra Mundial .

Vários outros polígrafos práticos foram introduzidos em 1901 por Felix Delastelle , incluindo as cifras bífidas e quatro-quadradas (ambas digitalizadas) e a cifra tríplice (provavelmente a primeira tríade prática).

A cifra de Hill , inventada em 1929 por Lester S. Hill , é uma substituição poligráfica que pode combinar grupos muito maiores de letras simultaneamente usando álgebra linear . Cada letra é tratada como um dígito na base 26 : A = 0, B = 1 e assim por diante. (Em uma variação, 3 símbolos extras são adicionados para tornar a base primo .) Um bloco de n letras é então considerado como um vetor de n dimensões e multiplicado pela matriz ansn , módulo 26. Os componentes da matriz são a chave, e deve ser aleatório, desde que a matriz seja invertível em (para garantir que a descriptografia seja possível). Uma versão mecânica da cifra de Hill de dimensão 6 foi patenteada em 1929.

A cifra de Hill é vulnerável a um ataque de texto simples conhecido porque é completamente linear , portanto, deve ser combinada com alguma etapa não linear para derrotar esse ataque. A combinação de etapas difusivas lineares mais amplas e fracas, como uma cifra de Hill, com etapas de substituição não linear, em última análise, leva a uma rede de substituição-permutação (por exemplo, uma cifra de Feistel ), portanto, é possível - a partir desta perspectiva extrema - considerar as cifras de bloco modernas como um tipo de substituição poligráfica.

Cifras de substituição mecânica

Máquina de cifragem Enigma usada pelos militares alemães na Segunda Guerra Mundial

Entre por volta da Primeira Guerra Mundial e a disponibilidade generalizada de computadores (para alguns governos isso foi aproximadamente nos anos 1950 ou 1960; para outras organizações foi uma década ou mais depois; para indivíduos, não foi antes de 1975), implementações mecânicas de cifras de substituição polialfabéticas foram amplamente utilizados. Vários inventores tiveram ideias semelhantes na mesma época, e as máquinas de criptografia de rotor foram patenteadas quatro vezes em 1919. A mais importante das máquinas resultantes foi a Enigma , especialmente nas versões usadas pelos militares alemães a partir de aproximadamente 1930. Os Aliados também desenvolveram e máquinas de rotor usadas (por exemplo, SIGABA e Typex ).

Todas elas eram semelhantes no sentido de que a letra substituída era escolhida eletricamente entre o grande número de combinações possíveis resultantes da rotação de vários discos de letras. Como um ou mais discos giravam mecanicamente com cada letra do texto simples codificada, o número de alfabetos usados ​​era astronômico. No entanto, as primeiras versões dessas máquinas eram quebráveis. William F. Friedman , do SIS do Exército dos Estados Unidos, logo encontrou vulnerabilidades na máquina de rotor de Hebern , e Dillwyn Knox , do GC&CS , resolveu versões da máquina Enigma (aquelas sem o "plugboard") muito antes do início da Segunda Guerra Mundial . O tráfego protegido por essencialmente todos os Enigmas militares alemães foi interrompido por criptoanalistas Aliados, mais notavelmente aqueles em Bletchley Park , começando com a variante do Exército Alemão usada no início dos anos 1930. Esta versão foi quebrada por um insight matemático inspirado por Marian Rejewski na Polônia .

Tanto quanto é do conhecimento público, nenhuma mensagem protegida pelas máquinas SIGABA e Typex foi interrompida durante ou perto do tempo em que esses sistemas estavam em serviço.

O pad de uso único

Artigo principal: Bloco de uso único

Um tipo de cifra de substituição, o teclado único , é bastante especial. Foi inventado perto do final da Primeira Guerra Mundial por Gilbert Vernam e Joseph Mauborgne nos Estados Unidos. Foi matematicamente comprovado como inquebrável por Claude Shannon , provavelmente durante a Segunda Guerra Mundial ; seu trabalho foi publicado pela primeira vez no final dos anos 1940. Em sua implementação mais comum, o bloco único pode ser chamado de cifra de substituição apenas de uma perspectiva incomum; normalmente, a letra do texto simples é combinada (não substituída) de alguma maneira (por exemplo, XOR ) com o caractere de material chave nessa posição.

O bloco de uso único é, na maioria dos casos, impraticável, pois requer que o material da chave seja tão longo quanto o texto simples, na verdade aleatório , usado uma vez e apenas uma vez e mantido inteiramente em segredo de todos, exceto do remetente e do destinatário pretendido. Quando essas condições são violadas, mesmo que marginalmente, o bloco de uso único não é mais inquebrável. As mensagens soviéticas únicas enviadas dos Estados Unidos por um breve período durante a Segunda Guerra Mundial usaram material de chave não aleatório . Os criptanalistas americanos, começando no final dos anos 40, foram capazes de, total ou parcialmente, quebrar alguns milhares de mensagens de várias centenas de milhares. (Veja o projeto Venona )

Em uma implementação mecânica, um pouco como o equipamento Rockex , o bloco de uso único foi usado para mensagens enviadas na linha direta Moscou - Washington estabelecida após a Crise dos Mísseis de Cuba .

Substituição na criptografia moderna

As cifras de substituição conforme discutido acima, especialmente as cifras manuais mais antigas de lápis e papel, não são mais usadas de forma séria. No entanto, o conceito criptográfico de substituição continua até hoje. De uma perspectiva suficientemente abstrata, as cifras de bloco orientadas a bits modernas (por exemplo, DES ou AES ) podem ser vistas como cifras de substituição em um alfabeto binário enormemente grande . Além disso, as cifras de bloco geralmente incluem tabelas de substituição menores chamadas S-boxes . Veja também rede de substituição-permutação .

Cifras de substituição na cultura popular

  • Sherlock Holmes quebra uma cifra de substituição em " A Aventura dos Homens Dançantes ". Lá, a cifra permaneceu indecifrada por anos, senão décadas; não por sua dificuldade, mas porque ninguém suspeitou que fosse um código , ao invés disso, considerou-o rabiscos infantis.
  • O idioma Al Bhed em Final Fantasy X é na verdade uma cifra de substituição, embora seja pronunciado foneticamente (ou seja, "você" em inglês é traduzido como "oui" em Al Bhed, mas é pronunciado da mesma forma que "oui" em francês )
  • O alfabeto Minbari da série Babylon 5 é uma cifra de substituição do inglês.
  • O idioma em Starfox Adventures : Dinosaur Planet, falado pelos nativos Saurians e Krystal, também é uma cifra de substituição do alfabeto inglês .
  • O programa de televisão Futurama continha uma cifra de substituição na qual todas as 26 letras foram substituídas por símbolos e denominadas "Linguagem Alienígena" . Isso foi decifrado rapidamente pelos espectadores obstinados, exibindo um anúncio "Slurm" com a palavra "Drink" tanto em inglês quanto na língua alienígena, dando assim a chave. Mais tarde, os produtores criaram uma segunda linguagem alienígena que usava uma combinação de substituição e cifras matemáticas. Uma vez que a letra inglesa da língua estrangeira é decifrada, o valor numérico dessa letra (0 para "A" a 25 para "Z" respectivamente) é adicionado (módulo 26) ao valor da letra anterior, mostrando o real pretendido carta. Essas mensagens podem ser vistas em todos os episódios da série e nos filmes subsequentes.
  • No final de cada episódio da 1ª temporada da série de desenhos animados Gravity Falls , durante a rolagem de crédito, há uma das três cifras de substituição simples: A cifra de César -3 (sugerida por "3 letras de volta" no final da sequência de abertura) , uma cifra Atbash ou uma cifra de substituição simples de letra para número. O final da 1ª temporada codifica uma mensagem com todos os três. Na segunda temporada, as cifras de Vigenère são usadas no lugar das várias cifras monoalfabéticas, cada uma usando uma chave escondida dentro de seu episódio.
  • Na série Artemis Fowl de Eoin Colfer, existem três cifras de substituição; Gnomês, Centauro e Eterno, que correm ao longo da parte inferior das páginas ou estão em algum outro lugar dentro dos livros.
  • Em Bitterblue , o terceiro romance de Kristin Cashore , as cifras de substituição servem como uma forma importante de comunicação codificada.
  • No videogame BioShock Infinite de 2013 , há cifras de substituição ocultas por todo o jogo, nas quais o jogador deve encontrar livros de código para ajudar a decifrá-los e obter acesso a um excedente de suprimentos.
  • Na adaptação para anime de The Devil Is a Part-Timer! , a linguagem de Ente Isla, chamada entean, usa uma cifra de substituição com o alfabeto do texto cifrado AZYXEWVTISRLPNOMQKJHUGFDCB , deixando apenas A, E, I, O, U, L, N e Q em suas posições originais.

Veja também

Referências

links externos