Substituição de Cifra
Origem: Wikipédia, a enciclopédia livre.
Em Criptografia, uma cifra de substituição é um método do encriptação o qual as unidades do plaintext são substituídas com mensagem cifrada de acordo com um sistema regular; as “unidades” podem ser as únicas letras (os mais comuns), pares de letras, triplo de letras, e assim por diante. O receptor decifra o texto executando uma substituição inversa. As cifras de substituição podem ser comparadas com as cifras de transportação. Em uma cifra de transportação, as unidades do plaintext são rearranjadas em uma ordem diferente e geralmente completamente complexa, mas as unidades são deixadas inalteradas. Já em uma cifra da substituição, as unidades do plaintext são retidas na mesma seqüência na mensagem cifrada, mas as unidades são alteradas. Há um número de tipos diferentes de cifras de substituição. Se a cifra operar sobre letras únicas, será denominada uma cifra simples da substituição; uma cifra que opere sobre grupos maiores das letras é denominada poligráfica. Uma cifra “monoalfabética” usa substituição fixa sobre a mensagem inteira, visto que uma cifra “polialfabética” usa um número de substituições em tempos diferentes na mensagem – o mesmo ocorre com o “homófones”, onde uma unidade do plaintext é traçada em uma das diversas possibilidades na mensagem cifrada.
Índice |
[editar] Substituição Simples
Substituição Simples pode ser demonstrada escrevendo o alfabeto em outra ordem para representar a substituição. Isto é chamado de substituição do alfabeto. A cifra do alfabeto pode ser deslocada ou invertida, criando as cifras de “Caesar” e de “Atbash”, ou “scrambled” em uma forma mais complexa, que no caso é chamado de um alfabeto misturado.
[editar] Exemplos
Usando o sistema, o keyword “zebras” dá-nos os seguintes alfabetos:
- Alfabeto do Plaintext: abcdefghijklmnopqrstuvwxyz;
- Alfabeto da mensagem Cifrada: ZEBRASCDFGHIJKLMNOPQTUVWXY.
Exemplo à mensagem: Fomos descobertos! Transforma-se em: SLJLP RAPBLEAOQLF!
Tradicionalmente, a mensagem cifrada é escrita nos blocos de comprimento fixo, omitindo a pontuação e os espaços; isto é feito para ajudar a evitar erros da transmissão e disfarçar limites de palavra do plaintext. Estes blocos são chamados “grupos”, e algumas vezes são chamados de “contagem de grupo” (isto é, o número dos grupos) é como uma verificação adicional. Cinco grupos de letras são tradicionais, datando de quando as mensagens se usaram ser transmitidas pelo telegrama: SLJLP RAPBLEAOQLF
Se o comprimento da mensagem não for divisível por cinco, pode ser adicionada nas extremidades a palavra “anula”. Estes podem ser todos os caracteres que decifrarem ao absurdo óbvio, assim o receptor pode facilmente descobri-los e rejeitá-los. O alfabeto da mensagem cifrada é às vezes é diferente do alfabeto do plaintext; por exemplo, na cifra “pigpen”, a mensagem cifrada consiste em um jogo dos símbolos derivados de uma grade.
Por exemplo:
Tais características fazem pouca diferença à segurança de um esquema, porém - qualquer símbolo estranho pode ser transcrito para trás em um alfabeto de A-Z e ser tratado de como o normal. Nas listas e nos catálogos é muito comum substituir dígitos numéricos por letras.
Dígitos: 1234567890
Alfabeto da mensagem cifrada: MAKEPROFIT
Exemplo: 120 poderia ser substituído por MAT.
[editar] Segurança para Cifras de Substituição Simples
Uma desvantagem deste método é que as últimas letras do alfabeto tendem a permanecer no fim. Uma maneira mais forte de construir um alfabeto misturado é executar uma cifra de transposição no alfabeto ordinário usando o keyword, mas isto não é feito freqüentemente.
Embora o número de chaves possíveis seja muito grande, estas cifras não são muito fortes, são facilmente quebráveis. Desde que a mensagem seja de um comprimento razoável, através da Criptoanálise pode-se deduzir o provável significado dos símbolos mais comuns, analisando a distribuição de freqüência da análise da mensagem. Isto permite a formação das palavras parciais, que podem ser preenchidas por tentativas, progressivamente expandindo a solução. Em alguns casos, as palavras subjacentes podem também ser determinadas pelo teste padrão de suas letras; por exemplo, “attract” e “osseous”,são as únicas duas palavras inglesas comuns, com o teste padrão ABBCADB.
ATTRACT = ABBCADB
OSSEOUS = ABBCADB
Muitas pessoas resolvem tais cifras por diversão, como os enigmas de criptogramas no jornal.
[editar] Substituição Homofônica
Antigamente na tentativa de aumentar a dificuldade nos ataques das cifras de substituição era disfarçar a letra do plaintext através da homófona. Geralmente, as mais elevadas-freqüências dos símbolos do plaintext são dadas mais equivalentes do que letras de uma freqüência mais baixa. Nesta maneira, a distribuição de freqüência é aplainada, fazendo a análise mais difícil. Já que mais de 26 caracteres são requeridos no alfabeto de mensagem cifrada, várias soluções são empregadas para inventar alfabetos maiores. Talvez a mais simples seja usar um “alfabeto” de substituição numérica.
Uma variante interessante é a “nomenclatura”. Esta cifra combinou um codebook pequeno com as tabelas homofônicas grandes da substituição. O código foi restringido originalmente aos nomes de povos importantes, por isso o nome da cifra “nomenclatura”; alguns anos atrás cobriram muitos palavras e nomes de lugares comuns também.
Os símbolos para as palavras inteiras e as letras não eram distinguidos na mensagem cifrada. A grande cifra de Rossignols foi usada por Louis XIV na França; depois que saíram de uso, as mensagens dos arquivos franceses foram inquebráveis por centenas de anos. Nomenclatura era o meio padrão de correspondência diplomática, espionagem, e conspiração política desde o início do séc. XV até o fim do séc. XVIII; a maioria dos conspiradores eram poucos sofisticados na criptografia. Por volta do séc. XVIII, quando o sistema estava chegando ao fim, alguns nomencladores tinham até 50.000 símbolos.
[editar] Substituição Polialfabética
As cifras da substituição polialfábetica foram feitas em 1467 por Leone Battista Alberti na forma de discos. Johannes Trithemius, em seu livro Esteganografia (do grego “a escrita escondida”) as introduziu de uma forma mais padrão. Uma versão mais sofisticada, que usa alfabetos misturados, foi descrita em 1563 pelo Giovanni Battista della Porta em seu livro, “De Furtivis Literarum Notis” (Em Latim “Caracteres escondidos na escrita”).
Em uma cifra polialfabética, os alfabetos múltiplos da cifra são usados. Para facilitar a encriptação, todos os alfabetos são escritos geralmente em uma tabela grande, chamada tradicionalmente de quadro. O quadro é geralmente 26×26, de modo que 26 alfabetos cheios de mensagens cifradas estejam disponíveis. O método de encher o quadro, e de escolher qual alfabeto usar, define a cifra polialfabética particular. Essas cifras são mais fáceis de quebrar do que se acreditava, porque os alfabetos da substituição são repetidos para plaintexts suficientemente grandes.
Uma das mais populares era a de Blaise de Vigenère. Publicada primeiramente em 1585, considerada inquebrável até 1863, e foi chamada de “Le chiffre indéchiffrable” ou seja “A cifra indecifrável”. Na cifra de Vigenère, a primeira fileira do quadro é preenchida com uma cópia do alfabeto do plaintext, e as fileiras sucessivas são deslocadas simplesmente um lugar à esquerda.
Um “keyword” é usado então para escolher que alfabeto da mensagem cifrada será usado. Cada letra do “keyword” é usada por sua vez, e são repetidos então outra vez do começo. Assim se o “keyword” for “CAT”, a primeira letra do plaintext será “C”, o segundo “A”, a terceira “T”, a quarta “C” outra vez, e assim por diante. Na prática, as chaves de Vigenère eram sempre frases com diversas palavras grandes.
Em 1863, Friedrich Kasiski publicou um método que permitisse o cálculo do comprimento do “keyword” em uma mensagem calculada por Vigenère. Uma vez que isto tenha sido feito, as letras da mensagem cifrada que foram cifradas sob o mesmo alfabeto poderiam ser escolhidas e atacadas separadas como um número de substituições simples semi-independentes - complicadas pelo fato de que as letras de um alfabeto foram separadas e não deram forma a palavras completas, mas simplificadas pelo fato de que geralmente uma tábua reta tenha sido empregada. Até hoje a cifra de Vigenère é teoricamente difícil de quebrar, se os alfabetos misturados estiverem usados no quadro, se o keyword for aleatório, e se o comprimento total da mensagem cifrada for menos de 27.6 vezes o comprimento do keyword. Estas exigências são compreendidas raramente na prática.
[editar] Substituição de Cifras Mecânicas
Entre a 1° Guerra Mundial e a disponibilidade difundida dos computadores, as execuções mecânicas de substituição de cifras polialfabética foram usadas extensamente. Diversos inventores tiveram idéias similares quase que no mesmo tempo, e as máquinas de cifra do rotor foram patenteadas quatro vezes em 1919. O resultado mais importante da máquinas foi a Enigma, especialmente nas versões usadas pelas forças armadas alemãs, aproximadamente em 1930. Os aliados também desenvolveram e usaram máquinas de rotor (por exemplo, SIGABA e Typex).
Todos estes eram similares no que diz respeito, como a letra é substituída, eram escolhidas eletricamente por um grande número de combinações possíveis resultante da rotação de diversos discos de letra.Desde que um ou mais dos discos giraram mecanicamente com cada letra cifrada do plaintext, o número dos alfabetos usado era substancialmente mais do que astronômico.
William F. Friedman do exército dos E.U. encontrou vulnerabilidades na máquina do rotor de Hebern, e Dillwyn Knox de GC&CS resolveu versões da máquina Enigma (aquelas sem o “plugboard”) bem antes que WWII começou. O tráfego protegido essencialmente por todos os Enigmas militares alemães foram quebrados por criptanalistas aliados, o mais notável foi o do Park Bletchley, começando com o exército alemão usado no inicio de 1930. Esta versão era quebrada pela introspecção matemática inspirada por Marian Rejewski em Poland. Não se conhece nenhuma mensagem, protegida pelas máquinas de SIGABA e de Typex que tenha sido quebrada.
[editar] One-time pad
Ver o artigo: One-time pad
Um tipo de substituição de cifra é o one-time pad (OTP), um algoritmo de encriptação onde o plaintext é combinado com uma chave aleatória ou uma “pad” que seja tão grande quanto o plaintext e é usado somente uma vez. Uma adição modular (por exemplo, XOR) é usada para combinar o plaintext com a pad. Foi inventada em 1917. Se a chave for verdadeiramente aleatória, nunca reutilizada, e mantida em segredo, a one-time pad pode ser inquebrável. Também provou-se que toda a cifra teórica inquebrável deve usar chaves com as mesmas exigências que chaves de OTP. A chave consiste normalmente em um fluxo aleatório de números, cada qual indica o número dos lugares no alfabeto (ou número de fluxos, se a mensagem do plaintext estiver no formulário numérico) que a letra ou o número correspondente na mensagem do plaintext devem ser deslocados. Para mensagens no alfabeto Latin, por exemplo, a chave consistirá em uma corda aleatória dos números de 0 a 25; para mensagens binárias a chave consistirá em uma corda aleatória de 0s e de 1s; e assim por diante.
[editar] Substituição com Criptografia Moderna
A substituição de cifra, especialmente as cifras mais velhas como lápis-e-papel, na são mais usadas. Entretanto, o conceito criptográfico da substituição continua o mesmo hoje. De uma perspectiva suficientemente abstrata, as cifras modernas de bit-orientado de cifra de bloco (por exemplo, DES, ou [Padrão Avançado de Encriptação (AES]) podem ser vistas como cifras de substituição em um alfabeto binário muito grande. Além disso, as cifras de bloco incluem freqüentemente as tabelas menores de substituição chamadas S-box.
