A HIPÓTESE DE RIEMANN E A INTERNET – III

O matemático alemão C. F. Gauss introduziu o conceito de congruência no primeiro capítulo de sua obra “Disquisitiones Arithmeticae”, publicada em 1801. Esse conceito é fundamental na codificação e na decodificação das chaves no sistema RSA.  O criptosistema de chave pública, denominado RSA, foi desenvolvido pelos cientistas R. Rivest, A. Shamir e L. Adleman.

            Para codificar um texto, segundo o sistema RSA, são necessários:

(1)   um número grande N, que é o produto de dois números primos distintos p e q, ou seja, N = p۰q.

(2)   um número inteiro E, conhecido como chave de codificação, que satisfaz as seguintes propriedades:

      o máximo divisor comum (MDC) entre E e o produto (p – 1)۰(q –1) é 1, e o MDC 

       entre E e N também é 1.

           Para decodificar um texto, segundo o sistema RSA, são necessários:

(3)   um número inteiro D, conhecido como chave de decodificação, que satisfaz a condição:

E۰D ≡ 1 (mod (p –1)۰(q – 1)).

            A relação entre E e D é simétrica, isto é, se D é a chave de decodificação para E, então E é a chave de decodificação para D.

           Na coluna anterior codificamos a mensagem PUBLIC KEY usando o sistema RSA com 

N = 2.537 = 43•59, p = 43, q = 59 e com a chave de codificação E = 13.            

           Primeiramente, observamos que N = 2.537 possui 4 dígitos e assim quebramos o texto em pares de letras: PU   BL   IC   KE   Y e completamos o último bloco com a letra C obtendo: PU   BL   IC   KE   YC.

            Utilizando a tabela de conversão que associa números naturais às letras do alfabeto, os blocos convertidos da mensagem são: 1520  0111  0802  1004  2402. Dessa maneira, o receptor receberá a mensagem cifrada: 0095 1648 1410 1299 0811.

            O nosso objetivo é dar os passos necessários para decodificarmos essa mensagem segundo o criptosistema RSA. Para decodificar essa mensagem necessitamos da chave pública D de decodificação.

           Existe um método para se determinar D, se E, p e q são conhecidos. Contudo, se p e q não são conhecidos, D não pode ser determinado. A segurança do criptosistema RSA reside nesse fato. 

            Se p e q são extremamente grandes, por exemplo, maiores que 10²⁰⁰, então determinar esses números primos em um tempo razoável, o que equivale a fatorar N = p۰q, pode estar além da capacidade dos supercomputadores mais rápidos.

            Nosso objetivo é determinar D tal que E۰D ≡ 1 (mod (p – 1)۰(q – 1)), em outras palavras D é o inverso de E módulo (p  – 1)۰(q  – 1).

            O método consiste na utilização do Algoritmo de Euclides aplicado à chave E de codificação e ao número (p – 1)۰(q – 1). Como E e (p – 1)۰(q – 1) são primos entre si, o MDC entre eles é 1. Primeiramente, percorremos todas as etapas do Algoritmo de Euclides para a determinação do MDC que nesse caso é 1.

            Pelo Algoritmo Euclidiano temos que 

(p  – 1)۰(q  – 1) = q₁۰E + r₂ , 0 ≤ r₂ < E.

            Como sabemos que MDC ((p – 1)۰(q – 1), E) = 1, continuamos aplicando o Algoritmo Euclidiano até obtermos o resto da divisão igual a 1. Portanto, efetuamos a divisão de E por r₂ e, assim por diante,  até obtermos o resto igual a 1:

E = q₂۰ r₂ + r_3,  0 ≤ r₃ < r₂

r₂  = q₃۰ r₃ + r₄, 0 ≤ r₄ < r₃

...

r_n-4 = q_n-3۰ r_n-3 + r_n-2, 0 ≤ r_n-2 < r_n-3

r_n-3 = q_n-2۰ r_n-2 + r_n-1, 0 ≤ r_n-1 < r_n-2

r_n-2 = q_n-1۰ r_n-1 + 1, 0 ≤ 1 < r_n-1.

           Agora, utilizando o Algoritmo de Euclides em sentido inverso podemos calcular D tal que

E۰D ≡ 1 (mod (p –1)۰(q – 1)). 

             Portanto, D é a chave de decodificação.

            Observemos que:

         1 = r_n-2  –  q_n-1۰ r_n-1            (1)

     r_n-1 = r_n-3  –  q_n-2۰ r_n-2            (2)

    r_n-2  = r_n-4 – q_n-3۰ r_n-3              (3)

…

             r₄  =  r₂ –  q₃۰ r₃                           (n – 3)

              r₃ = E – q₂۰ r_2,                                    (n – 2)

             r₂  = (p  – 1)۰(q  – 1) – q₁E         (n – 1)

            Substituindo o valor de r_n-1 de (2) em (1), obtemos 

1 = (1 + q_n-1۰q_n-2)۰r_n-2 – q_n-1۰r_n-3  

e, substituindo nessa igualdade o valor de r_n-2 de (3), obtemos

r_n = – (q_n-3 + q_n-1۰q_n-2۰q_n-3 + q_n-1)۰r_n-3 + (1 + q_n-1۰q_n-2)۰r_n-4.

Assim, procedemos sucessivamente até obtermos, no final, o número inteiro D tal que  

E۰D ≡ 1 (mod (p –1)۰(q – 1)).

            Em nosso exemplo, temos:

 N = 2.537 = 43۰59, p = 43,  q = 59 e (p – 1)۰(q – 1) = 42۰58 = 2.436 e E = 13.

           Utilizando o Algoritmo de Euclides para determinar o MDC entre (p – 1)۰(q – 1) = 2.436 e E = 13 obtemos:

2.436 = 187۰13 + 5, 13 = 2۰5 + 3, 5 = 1۰3 + 2, 3 = 1۰2 + 1.

            Agora, utilizando o Algoritmo de Euclides em sentido inverso, obtemos:

1 = 3 – 1۰2, 2 = 5 – 1۰3, 3 = 13 – 2۰5, 5 = 2436 – 187۰13

            Portanto, substituindo conforme explicamos acima, temos:

1 = 3 – 1۰2 = 3 – 1۰( 5 – 1۰3) = 3 – 1۰5 + 1۰3 = – 5 + 2۰3;

1 = – 5 + 2۰3 = – 5 + 2۰( 13 – 2۰5) = – 5 + 2۰13 – 4۰5 = 2۰13 – 5۰5;

1 = 2۰13 – 5۰5 = 2۰13 – 5۰( 2.436 – 187۰13) = 2۰13 – 5۰2.436 + 935.۰13 =

= 937۰13 – 5۰2.436.

            Assim, obtemos 1 = 937۰13 – 5۰2.436 o que  implica em 937۰13 = 5۰2.436 +1.            

            Logo, 13۰937 ≡ 1 (mod 2.436), ou seja, E۰937 ≡ 1 (mod(p –1)۰(q – 1)).

            Concluímos que D = 937.

            Na próxima coluna decodificaremos a mensagem.