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-4 – qn-3۰ rn-3 (3)
…
r4 = r2 – q3۰ r3 (n – 3)
r3 = E – q2۰ 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-2)۰rn-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-1)۰rn-3 + (1 + qn-1۰qn-2)۰rn-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.
