Creipoti

A próxima etapa é servir-se desta chave para codificarmos a mensagem sugerida. Neste momento trabalharemos com sistema de congruências.
Dividiremos o enorme número, que obtivemos com a transformação das letras da frase em números, em pequenos blocos sempre menores que n, pois trabalharemos com a congruência módulo n, logo se o número escolhido for maior que o meu n, ele se transformará em outro módulo n.
Em cada parte que foi dividida usaremos a seguinte congruência: A c E (mod n)
E é o resto da divisão de A c por n, A é o bloco que faria parte da mensagem clara e c o menor primo que não divide
(n), isto é c é invertível módulo
(n).
Após a codificação destes pequenos blocos não poderemos mais juntá-los, pois não conseguiríamos dividi-los novamente da mesma maneira, e não poderíamos decifrar os dados cifrados. Para seguirmos o caminho “inverso”, deveremos aproveitar mais uma vez de
(n), pois a partir dele e de c é que vamos encontrar a outra metade da chave que denominaremos d, já que n é a outra. Assim o par (n, d) seria a chave de decodificação. Nós encontraremos d, o inverso de c módulo
(n), aplicando o algoritmo euclidiano estendido em
(n) e c. Usando o algoritmo de Euclides estendido em
(n) e c, e sabendo que o mdc (
(n), c) =1, teremos a seguinte equação:

(n)a + cb = 1
Como
(n) E (mod
(n)), teremos que cb = 1 em
(n). Logo b é o inverso de c em
(n).
Fazendo b=d teremos que d é o inverso de c.
Agora usando a congruência
A E d (mod n) decodificaremos os dados, saindo limpa e legível a parte A, ou seja, a mensagem clara.
Mas para o método funcionar de acordo com o esperado teremos que verificar se, ao decodificarmos a parte codificada teremos a mensagem clara. Então temos que saber se:
A (E) d (mod n)
Como vimos d é o inverso de c módulo
(n), então cd=1+k
(n), para k sendo um inteiro qualquer. Como
E A c (mod n)
Daí temos