Você está em Comunidade > Colunas

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 10200, 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) = q1۰E + r2 , 0 ≤ r2 < 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 r2 e, assim por diante,  até obtermos o resto igual a 1:

E = q2۰ r2 + r3,  0 ≤ r3 < r2

r2  = q3۰ r3 + r4, 0 ≤ r4 < r3

...

rn-4 = qn-3۰ rn-3 + rn-2, 0 ≤ rn-2 < rn-3

rn-3 = qn-2۰ rn-2 + rn-1, 0 ≤ rn-1 < rn-2

rn-2 = qn-1۰ rn-1 + 1, 0 ≤ 1 < rn-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 = rn-2    qn-1۰ rn-1      (1)

     rn-1 = rn-3    qn-2۰ rn-2      (2)

    rn-2  = rn-4qn-3۰ rn-3  (3)

      r4  =  r2   q3۰ r3               (n – 3)

        r3 = Eq2۰ r2,     (n – 2)

      r2  = (p  – 1)۰(q  – 1) – q1E         (n – 1)

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

 

1 = (1 + qn-1۰qn-2rn-2 qn-1۰rn-3  

 

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

 

rn = – (qn-3 + qn-1۰qn-2۰qn-3 + qn-1rn-3 + (1 + qn-1۰qn-2rn-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.

Voltar para colunas

Divirta-se com o LOBIS HOMEM

Produtos de quando CORONA era motivo de alegria

O sonho de ser cantor