Criptografia - Cifra de Hill¶

Vamos aprender um método para codificar mensagens utilizando Cifras de Hill, cujo princípio reside em transformações matriciais. Para isso, vamos usar uma matriz chave e sua inversa mod 26.¶

Referência: Álgebra Linear com aplicações / Anton Howard e Chris Rorres; trad. Claus Ivo Doering. - 8. ed. - Porto Alegre: Bookman, 2001.¶

O estudo de codificação e decodificação de mensagens secretas é denomidado criptografia. Embora os códigos secretos remotem aos primórdios da comunicação escrita, tem havido um aumento recente de interesse no assunto devido à necessidade de manter a privacidade da informação transmitida ao longo de linhas públicas de comunicação (um exemplo atual é o sistema de criptografia utilizado pela marca WhatsApp, do Facebook). Na linguagem da criptografia, os códigos são denomidados cifras, as mensagens não codificadas são textos comuns e as mensagens codificadas são textos cifrados ou criptogramas. O processo de converter um texto comum em cifrado é chamado cifrar ou criptografar e o processo inverso de converter um texto cifrado em comum é chamado decifrar.

As cifras mais simples, denominadas de cifras de substituição, são as que substituem cada letra do alfabeto por uma outra letra. Para o exemplo que vamos mostrar não vamos usar esse sistema trivial. Vamos substituir cada letra por um número, que pode ser tabelada a demanda do cliente. Entretanto, para esse exemplo, vamos usar a numeração sequencial para fins didáticos:

$$\begin{bmatrix} 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 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 0 \\ \end{bmatrix}$$

In [1]:

# importando a biblioteca de funções numpy do Python
import numpy as numpy 

In [2]:

# Função responsável por retornar o equivalente numérico para as letras do alfabeto
def equivalenteDecimal(letra):
    
    # definindo uma cadeia de caracteres com todas as letras do alfabeto
    alfabeto = "zabcdefghijklmnopqrstuvwxy"
    
    # encontra a posição da letra na string e a retorna
    return(alfabeto.find(letra))

In [3]:

# função responsável por retornar o equivalente alfabético para um valor numérico
def equivalenteAlfabetico(numero):
    
    # definindo uma cadeia de caracteres com todas as letras do alfabeto
    alfabeto = "zabcdefghijklmnopqrstuvwxy"
    
    # encontra o pedaço da string a qual o número correspondente indica
    return(alfabeto[numero])

Cifras de Hill (Criptografar)¶

Uma desvantagem das cifras de substituição é que elas preservam as frequências de letras individuais, tornando relativamente fácil quebrar o código por métodos estatísticos. Uma maneira de superar este problema é dividir o texto em grupos de letras e criptografar o texto comum por grupo, em vez de uma letra de cada vez. Um sistema polígrafo é um sistema de criptografia no qual o texto comum é dividido em n letras, cada um dos quais é substituido por um conjunto de n letras cifradas. Vamos estudar as Cifras de Hill que são baseadas em transformações matriciais. Daqui para frente nos vamos supor que cada letra de texto comum e de texto cifrado, excetuando o z, tem um valor númerico que especifica sua posição no alfabeto padrão. O z receberá 0 por estarmos trabalhando com operações que envolvem o módulo 26, e como z seria a 26º letra do alfabeto, o seu módulo por 26 é 0.

Nos casos mais simples de Cifras de Hill, transformaremos pares sucessivos de texto comum em texto cifrado pelo seguinte procedimento:

1 - ) Escolha uma matriz 2 x 2 (poderia ser matrizes de ordens maiores, trabalhando assim com 3 letras consecutivas):

$$A = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix}$$

com entradas inteiras para efetuar a codificação.

2 - ) Agrupe letras sucessivas de texto em pares, adicionando uma letra fictícia para completar o último par. Se o texto comum tem um número ímpar de letras, substitua cada letra de texto comum por seu valor numérico.

3 - ) Converta cada par sucessivo $p_{1}p_{2}$ de letras de texto em um vetor-coluna:

$$p = \begin{bmatrix} p_{1} \\ p_{2} \\ \end{bmatrix}$$

e forme o produto A.p. Nós chamamos p de vetor comum e A.p o correspondente vetor cifrado.

Com o novo vetor coluna cifrado, é possível que ocorra resultados acima de 25. Em casos como esses, vamos fazer o módulo por 26 de cada elemento do vetor-coluna cifrado, justificando o motivo de z receber 0.

4 - ) Converta cada vetor cifrado em seu equivalente alfabético.

In [4]:

# criando uma matriz A, responsável pela segurança da criptografia
# definindo a matriz A
A = numpy.array([[5,6],[2,3]]) 

In [5]:

# função responsável por codificar nossa matriz, dependendo da matriz inserida
# veremos mais abaixo que uma entrada específica de outra matriz é suficiente para decodificar nossa matriz
def cifraHill(texto,chave):
    
    # inicializa a variável que vai receber a mensagem codificada
    codigo = ""
    # criando uma matriz responsável por receber o valor númerico equivalente ao alfabético
    valorNumerico = numpy.empty([2,1], dtype = int)
    # as inicializações indicam que ela será um vetor-coluna do tipo inteiro

    # criando uma matriz responsável por receber o valor codificado equivalente ao alfabético
    valorCodificado = numpy.empty([2,1], dtype = int)
    # as inicializações indicam que ela será um vetor-coluna do tipo inteiro
    
    # estrutura de repetição for responsável para codificar cada par do texto formado
    for indice in range(0, len(texto)):
    
        # estrutura de seleção if responsável por adicionar o valor numérico para a primeira letra do par
        if(indice == 0 or indice % 2 == 0):
            
            # pega exatamente a letra localizada no elemento numerico de 'indice'
            valor = equivalenteDecimal(texto[indice]) 
            # adiciona na primeira linha da primeira coluna
            valorNumerico[0][0] = valor 
    
        # estrutura de seleção responsável por adicionar o valor numérico para a segunda letra do par
        if(indice != 0 and indice % 2 != 0):
            
            # pega exatamente a letra localizada no elemento numerico de 'indice'
            valor = equivalenteDecimal(texto[indice])  
            # adiciona na segunda linha da primeira coluna
            valorNumerico[1][0] = valor 
        
        # estrutura de seleção responsável por calcular a multiplicação da matriz A pelo vetor-coluna 
        # dos pares numéricos
        if(indice != 0 and indice % 2 != 0):
            # realiza a multiplicação da matriz A com os pares de números equivalentes a letras
            valorCodificado = numpy.dot(chave, valorNumerico)
        
            # caso o valor do resultado codificado no primeiro par da letra seja maior que 25, 
            # substitui pelo valor 
            # do seu módulo por 26
            if(valorCodificado[0][0] > 25):
                valorCodificado[0][0] = (valorCodificado[0][0] % 26)
        
            # caso o valor do resultado codificado no segundo par da letra seja maior que 25, 
            # substitui pelo valor 
            # do seu módulo por 26
            if(valorCodificado[1][0] > 25):
                valorCodificado[1][0] = (valorCodificado[1][0] % 26)
        
            # pega o equivalente alfabético para os novos números codificados, visando 
            # construir a frase codificada
            a = str(equivalenteAlfabetico(valorCodificado[0][0])) # primeira linha do vetor-coluna
            b = str(equivalenteAlfabetico(valorCodificado[1][0])) # segunda linha do vetor-coluna
        
            # adiciona letra por letra codificada a uma variável string para montar a frase
            codigo += a
            codigo += b
        
    # remove os caracteres desnecessários e mostra somente a parte codificada
    codigo = codigo[len(codigo) - len(texto): len(codigo)]
    
    # função retorna código
    return codigo

In [6]:

# função responsável por pegar o texto a ser encriptado
def inserirFrase():
    
    texto = "" # inicializando uma variável vazia
    texto = str(input("Informe um texto sem acentos: ")) # padrão de entrada para receber uma string
    texto = texto.replace(" ", "") # eliminando os espaços em branco do texto
    texto = texto.lower() # deixando toda a string com letras minúsculas
    
    # caso o texto tenha uma quantidade ímpar de letras, adiciona mais uma letra arbitrária ao final
    if(len(texto) % 2 != 0):
        texto += "g" # adiciona-se g, por exemplo
    
    print("o texto é: {}".format(texto)) # imprime o texto informado na tela
    
    return texto # retorna a frase pronta para o sistema de criptografia

Vamos agora escolher uma frase a ser encriptada:

"Professor Edmar Ensina Muito Bem Algebra Linear" (sem acentos)

In [7]:

# chama a função para adicionar um texto a variável
texto = inserirFrase() 
# a opção por criar tal função advém da necessidade da frase ter que atender aos requisitos 
# informados acima para ser codificada

o texto é: professoredmarensinamuitobemalgebralinearg

Vamos agora codificar a mensagem inserida acima:

In [8]:

cifraHill(texto, A) # função responsável por criptografar o texto
# entrada do parâmetro da string de texto e da matriz chave

Out[8]:

'fhgviocepytuidezsmxeikizijywylmcnfylyhembe'

Cifras de Hill (Descriptografia)¶

Antes de entrar na parte de descriptografia, vamos falar um pouco de aritmética modular, requisito necessário para conseguir descriptografar as frases criptografadas através das Cifras de Hill. Contudo, vamos nos fixar apenas em definições, teoremas e colorários para entender o básico de tal requesito, pois o assunto em sua integridade não é algo que se possa entender de forma superficial.

Definição:¶

Dados um número inteiro positivo m e dois inteiros a e b quaisquer, dizemos que a é equivalente a b módulo m, e escrevemos a = b (mod m), se a - b é um múltiplo inteiro de m.

Exemplos¶

7 = 2 (mod 5)

19 = 3 (mod 2)

-1 = 25 (mod 26)

12 = 0 (mod 4)

Definição:¶

Dado um número a em $Z_{m}$, dizemos que um número $a^{-1}$ em $Z_{m}$ é um recíproco, ou inverso multiplicativo de a módulo m se $aa^{-1} = a^{-1}a = 1 (mod m)$.

Embora existam métodos gerais para resolver equações modulares, ensiná-los seria algo que foge do objetivo de tudo em que estamos trabalhando no momento. Então, vamos ver uma tabela que poderá ajudar a definir nossa matriz de descriptografia:

Recíprocos Módulo 26:¶

$\begin{bmatrix} a & 1 & 3 & 5 & 7 & 9 & 11 & 15 & 17 & 19 & 21 & 23 & 25 \\ a^{-1} & 1 & 9 & 21 & 15 & 3 & 19 & 7 & 23 & 11 & 5 & 17 & 25 \\ \end{bmatrix}$

Cada cifra útil deve possuir um procedimento para decifrar. Para fazer isso com as cifras de Hill, usamos a inversa (mod 26) da matriz codificadora. Para ser preciso, se m é um inteiro positivo, dizemos que uma matriz A com entradas em $Z_{m}$ é invertível módulo m se existir uma matriz B com entradas em $Z_{m}$ tal que:

$$AB = BA = I(mod m)$$

é invertível módulo 26 e que está matriz é usada para uma 2-cifra de Hill (o 2 indica quantas letras são usadas por grupo de criptografia). Se

$$p = \begin{bmatrix} p_{1} \\ p_{2} \\ \end{bmatrix}$$

é um vetor comum, então

$$c = Ap$$

$$p = A^{-1}c$$

Assim, cada vetor comum pode ser recuperado do correspondente vetor cifrado pela multiplicação à esquerda por $A^{-1}$ (mod 26).

Colorário:¶

Uma matriz quadrada A com entradas em $Z_{m}$ é invertível módulo m se, e somente se, m e o resíduo de det(A) módulo m não têm fatores primos comuns.

Colorário:¶

Uma matriz quadrada A com entradas em $Z_{26}$ é invertível módulo 26 se, e somente se, o resíduo de det(A) módulo 26 não é divisível por 2 ou 13.

Em suma, temos que a partir dessas definições, teremos os seguintes procedimentos:

$$A^{-1} = (ad - bc)^{-1}\begin{bmatrix} d & -b \\ -c & a \\ \end{bmatrix}(mod 26)$$

Onde $(ad - bc)^{-1}$ é o recíproco do resíduo de $ad - bc(mod 26)$

Vamos encontrar a inversa da matriz A módulo 26:

In [9]:

# imprime a matriz A
print("{}".format(A)) 

[[5 6]
 [2 3]]

In [10]:

# definindo a matriz A
A = numpy.array([[5,6],[2,3]]) 
# calculando o resíduo (ad - bc)
residuo = (A[0][0] * A[1][1] - A[0][1] * A[1][0]) % 26 
# temos a.a^{-1} = 1 (mod 26)
# residuo.reciproco = x  = 1 (mod 26)

In [11]:

# imprime o residuo 
print("{}".format(residuo)) 

Por erro e tentativa temos: $3.9 = 27 = 1(mod 26)$

Logo o recíproco é 9.

In [12]:

# definindo o reciproco
reciproco = 9 
# definindo o posicionamento da matriz invertível (mod 26)
descriptografia = numpy.array([[A[1][1], -A[0][1]], [-A[1][0], A[0][0]]]) 
# realizando a multiplicação com o recíproco
descriptografia *= reciproco 
# definindo o módulo 26 de cada elemento
descriptografia %= 26 

In [13]:

# imprimindo a matriz descriptograda
print("{}".format(descriptografia)) 

[[ 1 24]
 [ 8 19]]

Vamos descriptografar a mensagem criptografada anteriormente, usando a $matriz A^{-1} (mod 26)$

In [14]:

# definindo a cifra criptografada, dada anteriormente pela criptografia com A
cifra = "fhgviocepytuidezsmxeikizijywylmcnfylyhembe" 

In [15]:

# chamando a função responsável por criptografar/descriptografar
cifraHill(cifra,descriptografia) 

Out[15]:

'professoredmarensinamuitobemalgebralinearg'

Cifras de Hill (N Camadas de Criptografia)¶

Podemos utilizar o processor de criptografia n vezes consecutivas em uma mesma frase utilizando m matrizes, de modo que ao fazer as m inversíveis módulo 26 das matrizes e realizar n vezes o mesmo processo de criptografia com essas novas matrizes, teremos o texto original em nossas mãos.

Vamos aplicar a criptografia duas vezes consecutivas em uma mesma frase, mas para fins didáticos vamos manter a mesma matriz de transformação definida.

In [16]:

# chama a função para receber uma frase e configurá-la para a criptografia
frase = inserirFrase() 
# A Frase é: "Quem Estuda Passa"

o texto é: quemestudapassag

In [17]:

cifraHill(frase,A) # imprime a frase criptografada

Out[17]:

'csywioryzkhiaquw'

In [18]:

# vamos inserir a frase criptografada
frase = inserirFrase() 

o texto é: csywioryzkhiaquw

In [19]:

# vamos encriptar uma segunda camada
cifraHill(frase,A) 

Out[19]:

'ykcoekfgngpqcaig'

In [20]:

# vamos inserir a frase encriptada por duas vezes consecutivas
frase = inserirFrase() 

o texto é: ykcoekfgngpqcaig

In [21]:

# vamos descriptografar a primeira camada
cifraHill(frase,descriptografia) 

Out[21]:

'csywioryzkhiaquw'

In [22]:

# vamos inserir a frase novamente para quebrar a segunda e última camada
frase = inserirFrase() 

o texto é: csywioryzkhiaquw

In [23]:

# por fim, vamos descriptografar por completo
cifraHill(frase,descriptografia) 

Out[23]:

'quemestudapassag'

Aprenda Mais Sobre Criptografia¶

1 - ) ABRAHAM SINKOV, Elementary Criptanalysis, a Mathematical Approach(Mathematical Association of America, Mathematical Library, 1966).

2 - ) ALAN G. KONHEIM, Cryptography, a Primer(Wiley-Interscience, 1981).

Alguma Dúvida? Entre em Contato Comigo:¶

Me envie um e-mail;