Cifra de transposição - Transposition cipher

Na criptografia , uma cifra de transposição é um método de criptografia pelo qual as posições mantidas por unidades de texto simples (que normalmente são caracteres ou grupos de caracteres) são deslocadas de acordo com um sistema regular, de modo que o texto cifrado constitui uma permutação do texto simples. Ou seja, a ordem das unidades é alterada (o texto simples é reordenado). Matematicamente, uma função bijetiva é usada nas posições dos personagens para criptografar e uma função inversa para descriptografar.

A seguir estão algumas implementações.

Cifra Rail Fence

A cifra Rail Fence é uma forma de cifra de transposição que recebe o nome da forma como é codificada. Na cifra da cerca ferroviária, o texto simples é escrito para baixo e diagonalmente em "trilhos" sucessivos de uma cerca imaginária, subindo quando chegarmos ao fundo. A mensagem é então lida em linhas. Por exemplo, usando três "trilhos" e uma mensagem de 'SOMOS DESCOBRIDOS FLEE AT ONCE', o codificador escreve:

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .

Em seguida, lê:

WECRL TEERD SOEEF EAOCA IVDEN

(A cifra dividiu este texto cifrado em blocos de cinco para ajudar a evitar erros. Esta é uma técnica comum usada para tornar a cifra mais legível. O espaçamento não está relacionado a espaços no texto simples e, portanto, não contém nenhuma informação sobre o texto simples.)

Scytale

A cifra da cerca ferroviária segue um padrão semelhante ao da scytale , um sistema mecânico de produção de uma cifra de transposição usado pelos antigos gregos . O sistema consistia em um cilindro e uma fita que envolvia o cilindro. A mensagem a ser criptografada foi gravada na fita em espiral. As letras da mensagem original seriam reorganizadas quando a fita fosse desenrolada do cilindro. No entanto, a mensagem foi facilmente decifrada quando a fita foi enrolada em um cilindro do mesmo diâmetro do cilindro de criptografia. Usando o mesmo exemplo de antes, se o cilindro tiver um raio tal que apenas três letras possam caber em sua circunferência, o codificador escreve:

W . . E . . A . . R . . E . . D . . I . . S . . C
. O . . V . . E . . R . . E . . D . . F . . L . .
. . E . . E . . A . . T . . O . . N . . C . . E .

Neste exemplo, o cilindro está rodando horizontalmente e a fita está enrolada verticalmente. Portanto, o criptografador então lê:

WOEEV EAEAR RTEEO DDNIF CSLEC

Cifra de rota

Em uma cifra de rota, o texto simples é primeiro escrito em uma grade de dimensões fornecidas e, em seguida, lido em um padrão fornecido na chave. Por exemplo, usando o mesmo texto simples que usamos para cerca ferroviária :

W R I O R F E O E 
E E S V E L A N J 
A D C E D E T C X 

A chave pode especificar "espiral para dentro, no sentido horário, começando do canto superior direito". Isso daria um texto cifrado de:

EJXCTEDEC DAEWRIORF EONALEVSE

As cifras de rota têm muito mais chaves do que uma cerca ferroviária. Na verdade, para mensagens de comprimento razoável, o número de chaves possíveis é potencialmente grande demais para ser enumerado mesmo por máquinas modernas. No entanto, nem todas as chaves são igualmente boas. Rotas mal escolhidas deixarão pedaços excessivos de texto simples, ou texto simplesmente invertido, e isso dará aos criptanalistas uma pista sobre as rotas.

Uma variação da cifra de rota foi a Union Route Cipher, usada pelas forças da União durante a Guerra Civil Americana . Isso funcionou muito como uma cifra de rota comum, mas transpôs palavras inteiras em vez de letras individuais. Como isso deixaria certas palavras altamente sensíveis expostas, tais palavras seriam primeiro ocultadas pelo código . O funcionário da cifra também pode adicionar palavras nulas inteiras, que costumam ser escolhidas para tornar o texto cifrado engraçado.

Transposição colunar

Em uma transposição colunar, a mensagem é escrita em linhas de comprimento fixo, e então lida novamente coluna por coluna, e as colunas são escolhidas em alguma ordem embaralhada. Tanto a largura das linhas quanto a permutação das colunas são geralmente definidas por uma palavra-chave. Por exemplo, a palavra-chave ZEBRAS tem comprimento 6 (portanto, as linhas têm comprimento 6) e a permutação é definida pela ordem alfabética das letras na palavra-chave. Nesse caso, o pedido seria "6 3 2 4 1 5".

Em uma cifra de transposição colunar regular, todos os espaços sobressalentes são preenchidos com nulos; em uma cifra de transposição colunar irregular, os espaços são deixados em branco. Por fim, a mensagem é lida em colunas, na ordem especificada pela palavra-chave. Por exemplo, suponha que usamos a palavra-chave ZEBRAS e a mensagem SOMOS DESCOBERTOS. FUGIR DE UMA VEZ . Em uma transposição colunar regular, escrevemos isso na grade da seguinte forma:

6 3 2 4 1 5
W E A R E D
I S C O V E 
R E D F L E 
E A T O N C 
E Q K J E U 

fornecendo cinco nulos ( QKJEU ), essas letras podem ser selecionadas aleatoriamente, pois apenas preenchem as colunas incompletas e não fazem parte da mensagem. O texto cifrado é então lido como:

EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE

No caso irregular, as colunas não são preenchidas por nulos:

6 3 2 4 1 5
W E A R E D 
I S C O V E 
R E D F L E 
E A T O N C 
E 

Isso resulta no seguinte texto cifrado:

EVLNA CDTES EAROF ODEEC WIREE

Para decifrá-lo, o destinatário precisa calcular o comprimento da coluna, dividindo o comprimento da mensagem pelo comprimento da chave. Em seguida, eles podem escrever a mensagem em colunas novamente e, em seguida, reordenar as colunas reformando a palavra-chave.

Em uma variação, a mensagem é bloqueada em segmentos que têm o comprimento da chave e a cada segmento é aplicada a mesma permutação (dada pela chave). Isso é equivalente a uma transposição colunar onde a leitura é por linhas em vez de colunas.

A transposição colunar continuou a ser usada para propósitos sérios como um componente de cifras mais complexas, pelo menos até os anos 1950.

Transposição dupla

Uma única transposição colunar poderia ser atacada adivinhando os comprimentos de coluna possíveis, escrevendo a mensagem em suas colunas (mas na ordem errada, pois a chave ainda não é conhecida) e, em seguida, procurando por anagramas possíveis . Assim, para torná-lo mais forte, costumava-se usar uma dupla transposição. Esta é simplesmente uma transposição colunar aplicada duas vezes. A mesma chave pode ser usada para ambas as transposições, ou duas chaves diferentes podem ser usadas.

Como exemplo, podemos pegar o resultado da transposição colunar irregular da seção anterior e realizar uma segunda criptografia com uma palavra-chave diferente, STRIPE , que dá a permutação "564231":

5 6 4 2 3 1 
E V L N A C
D T E S E A
R O F O D E
E C W I R E
E

Como antes, isso é lido em colunas para fornecer o texto cifrado:

CAEEN SOIAE DRLEF WEDRE EVTOC

Se várias mensagens com exatamente o mesmo comprimento forem criptografadas usando as mesmas chaves, elas podem ser anagramas simultaneamente. Isso pode levar à recuperação das mensagens e às chaves (de modo que todas as outras mensagens enviadas com essas chaves possam ser lidas).

Durante a Primeira Guerra Mundial , os militares alemães usaram uma cifra de transposição colunar dupla, alterando as chaves com pouca frequência. O sistema era regularmente resolvido pelos franceses, com o nome de Übchi, que normalmente era capaz de encontrar rapidamente as chaves depois de interceptar uma série de mensagens do mesmo tamanho, o que geralmente levava apenas alguns dias. No entanto, o sucesso francês tornou-se amplamente conhecido e, após uma publicação no Le Matin , os alemães mudaram para um novo sistema em 18 de novembro de 1914.

Durante a Segunda Guerra Mundial, a dupla cifra de transposição foi usada pelos grupos da Resistência Holandesa , os Maquis franceses e o Executivo de Operações Especiais Britânico (SOE), que se encarregou de gerenciar as atividades clandestinas na Europa. Também foi usado por agentes do Escritório Americano de Serviços Estratégicos e como uma cifra de emergência para o Exército e a Marinha Alemã.

Até a invenção da cifra VIC , a transposição dupla era geralmente considerada a cifra mais complicada que um agente poderia operar de forma confiável em condições de campo difíceis.

Criptanálise

A cifra de transposição dupla pode ser tratada como uma única transposição com uma chave, desde que seja o produto dos comprimentos das duas chaves.

No final de 2013, um duplo desafio de transposição, considerado por seu autor como indecifrável, foi resolvido por George Lasry usando uma abordagem de dividir para conquistar, em que cada transposição era atacada individualmente.

Transposição de Myszkowski

Uma forma variante de transposição colunar, proposta por Émile Victor Théodore Myszkowski em 1902, requer uma palavra-chave com letras recorrentes. Na prática usual, as ocorrências subsequentes de uma letra de palavra-chave são tratadas como se a próxima letra em ordem alfabética, por exemplo, a palavra-chave TOMATO produza uma sequência numérica de "532164".

Na transposição de Myszkowski, letras de palavras-chave recorrentes são numeradas de forma idêntica, TOMATO produzindo uma sequência de teclas de "432143".

4 3 2 1 4 3
W E A R E D
I S C O V E
R E D F L E
E A T O N C
E

As colunas de texto simples com números exclusivos são transcritas para baixo; aqueles com números recorrentes são transcritos da esquerda para a direita:

ROFOA CDTED SEEEA CWEIV RLENE

Transposição interrompida

Uma cifra de transposição interrompida complica ainda mais o padrão de transposição com preenchimento irregular das linhas da matriz, ou seja, com alguns espaços intencionalmente deixados em branco (ou escurecidos como no Rasterschlüssel 44 ), ou preenchidos posteriormente com outra parte do texto simples ou letras aleatórias . Um algoritmo possível é iniciar uma nova linha sempre que o texto simples atingir um caractere de senha. Outra opção simples seria usar uma senha que coloque espaços em branco de acordo com sua seqüência numérica. Por exemplo, "SECRET" seria decodificado para uma sequência de "5,2,1,4,3,6" e riscaria o 5º campo da matriz, então contaria novamente e riscaria o segundo campo, etc. O exemplo a seguir seria ser uma matriz configurada para transposição colunar com a chave colunar "CRIPTO" e preenchida com campos riscados de acordo com a chave de interrupção "SEGREDO" (marcada com um asterisco), após o que é colocada a mensagem "somos descobertos, foge imediatamente" nos espaços restantes. O texto cifrado resultante (as colunas lidas de acordo com a chave de transposição) é "WCEEO ERET RIVFC EODN SELE ADA".

C R Y P T O
1 4 6 3 5 2
W E A R * E
* * D I S *
C O * V E R
E D * F L E
E * A * * T
O N * C E *

Grelha

Outra forma de cifra de transposição usa grades ou máscaras físicas com recortes. Isso pode produzir uma transposição altamente irregular ao longo do período especificado pelo tamanho da grade, mas exige que os correspondentes mantenham uma chave física em segredo. As grades foram propostas pela primeira vez em 1550 e ainda estavam em uso militar durante os primeiros meses da Primeira Guerra Mundial.

Detecção e criptanálise

Uma vez que a transposição não afeta a frequência dos símbolos individuais, a transposição simples pode ser facilmente detectada pelo criptanalista fazendo uma contagem de frequência. Se o texto cifrado exibir uma distribuição de frequência muito semelhante ao texto simples, é mais provável que seja uma transposição. Muitas vezes, isso pode ser atacado por anagramas - deslizando pedaços de texto cifrado e, em seguida, procurando por seções que se parecem com anagramas de palavras em inglês e resolvendo os anagramas. Uma vez que tais anagramas tenham sido encontrados, eles revelam informações sobre o padrão de transposição e, conseqüentemente, podem ser estendidos.

Transposições mais simples também costumam sofrer da propriedade de que as chaves muito próximas da chave correta revelarão longas seções de texto simples legível intercaladas por rabiscos. Consequentemente, essas cifras podem ser vulneráveis ​​a algoritmos de busca ideais, como algoritmos genéticos .

Uma descrição detalhada da criptoanálise de uma cifra de transposição alemã pode ser encontrada no capítulo 7 de "The American Black Chamber", de Herbert Yardley.

Uma cifra usada pelo Zodiac Killer , chamada "Z-340", organizada em seções triangulares com substituição de 63 símbolos diferentes para as letras e transposição diagonal de "movimento do cavaleiro", permaneceu sem solução por mais de 51 anos, até que uma equipe internacional de cidadãos particulares quebrou-o em 5 de dezembro de 2020 usando um software especializado.

Combinações

A transposição costuma ser combinada com outras técnicas, como métodos de avaliação. Por exemplo, uma cifra de substituição simples combinada com uma transposição colunar evita a fraqueza de ambos. Substituir símbolos de texto cifrado de alta frequência por letras de texto simples de alta frequência não revela pedaços de texto simples por causa da transposição. Anagramar a transposição não funciona por causa da substituição. A técnica é particularmente poderosa se combinada com fracionamento (veja abaixo). Uma desvantagem é que essas cifras são consideravelmente mais trabalhosas e sujeitas a erros do que cifras mais simples.

Fracionamento

A transposição é particularmente eficaz quando empregada com fracionamento - ou seja, um estágio preliminar que divide cada símbolo de texto simples em vários símbolos de texto cifrado. Por exemplo, o alfabeto em texto simples pode ser escrito em uma grade e cada letra da mensagem substituída por suas coordenadas (veja o quadrado de Políbio e o tabuleiro de xadrez ). Outro método de fracionamento é simplesmente converter a mensagem em código Morse , com um símbolo para espaços, bem como pontos e travessões.

Quando uma mensagem tal fraccionado é transposta, os componentes de letras individuais tornam-se amplamente separados na mensagem, conseguindo-se assim Claude E. Shannon de difusão . Exemplos de cifras que combinam fracionamento e transposição incluem a cifra bífida , a cifra trifídica , a cifra ADFGVX e a cifra VIC .

Outra opção seria substituir cada letra por sua representação binária, transpor isso e, em seguida, converter a nova string binária nos caracteres ASCII correspondentes. O loop do processo de embaralhamento na string binária várias vezes antes de transformá-lo em caracteres ASCII provavelmente tornaria mais difícil quebrá-lo. Muitas cifras de bloco modernas usam formas mais complexas de transposição relacionadas a essa ideia simples.

Veja também

Notas

Referências

  • Kahn, David. The Codebreakers: The Story of Secret Writing. Rev Sub. Scribner, 1996.
  • Yardley, Herbert. A Câmara Negra Americana. Bobbs-Merrill, 1931.