Quebrando a Cifra de Vigenère

A disciplina de Criptografia é outra que tem se revelado bastante interessante. Na última aula ficou como tarefa quebrar um texto criptografado com a cifra de Vigenère, método de criptografia descrito por Giovan Battista Bellaso em um livro de sua autoria datado de 1553.

Para quem possui pouco ou nenhum conhecimento sobre criptoanálise, este método pode parecer inquebrável, ou seja, indecifrável. Mas através de algumas técnicas básicas é possível quebrá-lo facilmente, como vou demonstrar com um programa que escrevi em Ruby para a tarefa da disciplina.

Entendendo a Cifra de César

Para entender a Cifra de Vigenère, é interessante entender primeiro a Cifra de César, que consiste em incrementar ou decrementar cada letra em N (chave) posições. O nome é uma homenagem a Júlio César, imperador romano que utilizou o método para comunicação confidencial entre o seu exército. Apesar de simples e facilmente quebrável, a Cifra de César parece ter tido grande sucesso em sua época, visto ser analfabeta a maioria dos inimigos do Império Romano, e os poucos que sabiam ler imaginavam que o texto estivesse escrito em outra língua.

Exemplificando a lógica deste método, em um texto criptografado com chave 3, cada letra aumentaria em três posições no alfabeto: 'A' se tornaria 'D', 'B' se tornaria 'E' e assim por diante. Chegando ao final do alfabeto, o incremento retornaria ao início, por exemplo, 'Z' se tornaria 'C'. A figura ao lado ilustra melhor esta troca.

Entendendo a Cifra de Vigenère

O grande diferencial da Cifra de Vigenère em relação à Cifra de César é que para cada posição é atribuído um incremento diferente. Por exemplo, em vez de incrementar todas as letras em 3 posições, a primeira letra é incrementada em 4, mas a segunda já é incrementada em 1, a terceira em 14, a quarta em 9, a quinta em 5, a sexta em 12 e, a partir da sétima posição, o incremento volta a ser 4. Assim temos uma variação de incrementos igual a 4, 1, 14, 9, 5, 12, que, transposta para letras conforme a posição no alfabeto, forma 'D', 'A', 'N', 'I', 'E' e 'L', meu nome: DANIEL. :o)

Mas a grande questão que interessa aqui é como quebrar a Cifra de Vigenère.
E é bem simples!

Primeiro passo da criptoanálise: Encontrar o tamanho da chave

O primeiro passo é descobrir o tamanho da chave, ainda que não se saiba que chave é essa. Para tanto, basta localizar blocos de caracteres que se repitam várias vezes no corpo do texto, ou seja, estão sendo codificados sempre na mesma posição da chave.

Vamos supor que o bloco ernamw é encontrado várias (dezenas de) vezes no texto, isso nos indica um padrão de repetição. Aí pegamos a diferença de posição entre todas estas ocorrências e vemos qual é o maior número que divide perfeitamente todas estas diferenças, ou seja, não deixa resto de divisão ( x mod y = 0). Exemplificando fica mais claro.

Encontramos esta sequência de caracteres nas seguintes posições do texto:

426
   ----> Distância entre ocorrências: 108
534
   ----> Distância entre ocorrências: 120
654
   ----> Distância entre ocorrências: 108
762
   ----> Distância entre ocorrências: 66
828

Iniciando com a possibilidade de tamanho 20 para nossa chave, por exemplo, e decrementando, vemos que 20 não é um divisor perfeito para nenhum dos casos, 19 também não, 18 só é divisor perfeito para 108 mas não para as outras distâncias, e assim por diante, até descobrirmos que 6 divide perfeitamente todas as diferenças, logo, temos um número fortemente suspeito para o tamanho da chave.

No caso da tarefa que eu tinha para fazer, essa lógica foi perfeita e o tamanho da chave encontrada foi 5. Nesse caso é 6.

Segundo passo da criptoanálise: Fatiar o cipher text

Sabendo o tamanho da chave podemos "fatiar" o nosso cipher text (texto criptografado) em 6 partes. Para a primeira fatia, pegamos o primeiro caractér do texto, seis posições à frente pegamos o próximo, mais seis posições à frente pegamos o seguinte, e assim por diante para construir a primeira fatia. Para construir a segunda, começamos pelo segundo caractér e seguimos também de seis em seis, e assim por diante até a sexta fatia.

O objetivo de fatiar o texto é que temos certeza de que todas as letras de uma determinada fatia foram codificadas com uma única letra da chave e, sendo assim, sabemos que todos os 'A' são uma versão criptografada de um mesmo caractér, todos os 'B' também, todos os 'C', e assim por diante. Captou a ideia? Se não captou, tente voltar uns parágrafos e tentar acompanhar novamente o raciocínio. Se não adiantar, é porque minha didática está muito ruim mesmo...

Tendo essa informação, podemos empregar uma técnica trivial e fatal: A Análise de Frequência.

Terceiro passo da criptoanálise: Análise de Frequência

A Análise de Frequência é uma técnica bastante antiga, cuja primeira menção foi encontrada em um manuscrito de um filósofo árabe do século IX, que visa inferir a letra original a partir da frequência de repetição da letra criptografada.

Como assim? A grande questão é que, se sabemos o idioma em que a mensagem original foi escrita, sabemos qual é a letra que costuma se repetir com maior frequência em textos escritos naquele idioma. Por exemplo, no Inglês, a letra que mais se repete é o 'E', no Português é o 'A', e da mesma forma esta é uma informação de fácil acesso, especialmente hoje em dia.

Sabemos que nosso texto original é em Português e acabamos descobrindo que na primeira fatia do cipher text a letra que mais se repete é o 'E'. Assim sabemos que há uma probabilidade imensa de que o 'E' na verdade seja 'A'. Assumindo isso como verdadeiro, temos que o 'A' incrementou 4 posições para se tornar o caractér criptografado 'E'. E qual é a quarta letra do alfabeto? Resposta: 'D'. Assim, após termos descoberto o tamanho da chave, acabamos de descobrir qual é a primeira letra da chave, usando esta informação e a Análise de Frequência.

Seguindo o mesmo raciocínio em cada uma das outras fatias do cipher text, conseguimos descobrir todos os caracteres da chave.

Um ponto importantíssimo aqui é que a Análise de Frequência só é eficaz em textos amplos, pois um texto pequeno, mesmo escrito em Português, pode por exemplo ter uma quantidade de ocorrências da letra 'O' muito maior do que a da letra 'A', sendo assim, a criptoanálise não fica tão "automática", e necessitaria de algumas tentativas e erros para se descobrir a chave correta.

Quarto passo da criptoanálise: Aplicando a chave ao cipher text

Sabemos que, pela Cifra de Vigenère, os caractéres da chave foram somados aos caracteres do texto original nas posições correspondentes, formando então o cipher text. Sendo assim, de posse da chave e do cipher text, é possível chegar no texto original fazendo o cálculo inverso, de subtração em vez de soma.

A primeira letra da chave é 'D' e a primeira letra do cipher text é 'E'. Então, considerando índices iniciando em zero (e não 1), sabemos que o índice da primeira letra da chave é 3 e se diminuirmos 3 de 'E' temos 'B', logo, 'B' é a primeira letra do nosso texto original. Seguindo a mesma lógica você conseguirá obter o resto do texto original correspondente ao trecho 'ernamw' do cipher text.

O código em Ruby

Como um bom desenvolvedor de software, você deve estar ansioso pelo código, ou possivelmente pulou direto para essa parte. O código é meio auto-explicativo (ou pelo menos eu o considero assim). Coloco abaixo o artefato principal, code_breaker.rb, que tem a lógica inteira. O código completo pode ser encontrado no meu GitHub.

Bom, divirta-se!! E qualquer dúvida (ou proposta de refactoring, correção, etc.), comente aí!

require "./constants.rb"

#
# Author: Daniel Adornes
# Date: 03/30/2013
# 

class CodeBreaker

  attr_accessor(:cipher_text, :key_length, :key)


  def decrypt
    
    # Find out the key length, unless it is already set
    @key_length = find_key_length unless @key_length
    
    # Find out the key based on frequency analysis, unless it is already set
    @key = find_key unless @key
    
    # Find out and return plain text
    find_plain_text
  end
  

  private


  def find_key_length

    # Search for blocks repetitions, starting with blocks of length 20, down to 3
    20.downto(3) do |block_length|
      
      blocks = find_block_repetitions( block_length )
      
      # Find repetitions whose distances have common divisor
      blocks.each_pair do |block, occurrencies|
        
        # Consider only blocks that repeat more than 10 times
        if occurrencies > 10

          # Find positions index for each block
          idx_occurrencies = find_occurrencies_position(block, occurrencies)
          
          # Test possible key lengths from 30 to 4
          # by looking for perfect division (mod zero for all cases)
          30.downto(4) do |possible_key_length|
            divisable = true
            
            (idx_occurrencies.length-1).downto(1) do |i|
              if (idx_occurrencies[i] - idx_occurrencies[i-1]) % possible_key_length != 0
                divisable = false
                break
              end
            end
            
            # Assumes the key length was found when all distances between occurrences of a given block
            # are perfectly divisable by the same number
            if divisable
              puts "Key length found: #{possible_key_length}"
              return possible_key_length
            end
          end
        end
      end
    end

    raise "Key length not found!"
  end

  
  def find_key

    @key = Array.new

    # Chooses 'e' char as the base char for frequency analysis
    base_char_for_frequency_analysis = 'e'
    idx_base_char = Constants.ALPHABET.index(base_char_for_frequency_analysis)
    
    # Iterates up to the key length
    (0...@key_length).each do |key_position|
      
      # Builds the cipher text slice
      cipher_text_slice = build_cipher_text_slice( key_position )
      
      # Frequency analysis
      encrypted_e = find_more_frequent_char( cipher_text_slice )
      
      # Stores the key char index
      @key[key_position] = (Constants.ALPHABET.index(encrypted_e) - idx_base_char + Constants.ALPHABET.length) % Constants.ALPHABET.length
              
    end
    
    # Output the Key

    str_key = String.new
    (0...@key_length).each do |key_idx|
      str_key << Constants.ALPHABET[@key[key_idx]]
    end
    
    puts "Key found: #{str_key}"
    
    @key
  end

  
  def find_plain_text
    plain_text = String.new
    
    # Iterates through each position of the cipher text
    (0...@cipher_text.length).each do |i|
      # Finds the key index to use for decryption
      idx_key = @key[i % @key.length]

      # Finds the cipher char index
      idx_cipher_char = Constants.ALPHABET.index(@cipher_text[i])

      # Finds the plain text char index
      idx_plain = (idx_cipher_char - idx_key + Constants.ALPHABET.length) % Constants.ALPHABET.length
      
      # Append the plain text char to plain text variable
      plain_text << Constants.ALPHABET[idx_plain]
    end
    
    plain_text
  end


  def find_block_repetitions ( block_length )
    blocks = Hash.new
      
    (0..(@cipher_text.length-block_length)).each do |i|
      block = @cipher_text[i,block_length]
      
      c = blocks.include?(block) ? blocks[block] + 1 : 1
      blocks[block] = c
    end

    blocks
  end


  def find_occurrencies_position( block, occurrencies )
    idx_occurrencies = Array.new

    position = 0
    idx = 0
    while idx < occurrencies do
      position = @cipher_text.index(block, position)
      if position then
        idx_occurrencies[idx] = position
        idx += 1
        position += 1
      else
        break
      end                    
    end

    idx_occurrencies
  end


  def build_cipher_text_slice( position )
    cipher_text_slice = String.new
      
    (position...(@cipher_text.length)).step(@key_length) do |i|
      cipher_text_slice << @cipher_text[i]
    end

    cipher_text_slice
  end


  def find_more_frequent_char( cipher_text_slice )
    char_occurrences = Hash.new
      
    (0...cipher_text_slice.length).each do |i|
      character = cipher_text_slice[i]
      
      c = char_occurrences.include?(character) ? char_occurrences[character] + 1 : 1
      char_occurrences[character] = c
    end
    
    more_frequent = 0
    encrypted_e = 0
    
    # Finds the more frequent char in the current cipher text slice
    # in order to infer the 'e' correspondent encrypted char
    char_occurrences.each_pair do |character, frequency|
      if frequency > more_frequent
        more_frequent = char_occurrences[character]
        encrypted_e = character
      end
    end

    encrypted_e
  end
end

Referências

• Cifra de Vigenère - Artigo Wikipedia
• Cifra de César - Artigo Wikipedia
• Análise de Frequência - Artigo Wikipedia