A hipótese de Riemann e a Internet II
Em 1977, os cientistas R. Rivest, A. Shamir e L. Adleman propuseram um cripto-sistema de chave pública, denominado RSA. Esse sistema utiliza algumas idéias elementares de Teoria dos Números.
Apesar das idéias utilizadas serem elementares, isso não significa que sejam triviais. Na verdade um dos maiores matemáticos de todos os tempos, o matemático alemão Gauss (1777-1855), criou e desenvolveu a noção de congruências que é fundamental na codificação e decodificação das chaves no sistema RSA. As congruências, e o conseqüente desenvolvimento denominado de Aritmética Modular, representam uma grande contribuição à Teoria dos Números. Em particular, às questões de divisibilidade, pois, quando existe a necessidade de se trabalhar com os restos da divisão euclidiana, as congruências são os instrumentos adequados.
Gauss introduziu o conceito de congruência no primeiro capítulo de sua obra “Disquisitiones Arithmeticae” publicada em 1801. Gauss introduziu, simultaneamente ao conceito de congruência, a notação “≡”, que tornou o conceito uma técnica poderosa em Álgebra e Teoria doa Números. Vamos às definições.
Consideramos dois inteiros a, b e n um inteiro positivo. Se n divide a – b, então dizemos que a é congruente a b modulo n, e escrevemos a ≡ b (mod n).
Por exemplo:
37 ≡ 2 (mod 5) , pois, 5 divide 37 – 2 = 35,
27 ≡ 3 (mod 4) , pois, 4 divide 27 – 3 = 24,
7 ≡ 7 (mod 4) , pois, 4 divide 7 – 7 = 0.
Portanto, a ≡ b (mod n) significa que n divide a – b; logo, existe um inteiro k tal que a – b = kn pela definição de divisibilidade. Por exemplo, 37 ≡ 2 (mod 5) implica que existe k (= 7) tal que 37 – 2 = 35 = 7 • 5.
Dados os inteiros a e n, sabemos pelo Algoritmo da Divisão que existem inteiros q e r denominados, respectivamente, de quociente e resto, tais que: a = qn + r, onde 0 ≤ r < n; logo, a – r = qn, ou seja, n divide a – r. Portanto, pela definição de congruência a ≡ r (mod n).
O resto r pode assumir qualquer valor entre 0 e n - 1. Dessa maneira, concluímos que todo inteiro a é congruente modulo n a exatamente um dos valores entre 0, 1, 2, ..., n - 1. O conjunto {0, 1, 2, ..., n – 1} dos inteiros m que são os restos das divisões modulo n, é chamado de classe de resíduos módulo n. Se fixarmos n = 7, então a classe de resíduos módulo 7 possui exatamente 7 elementos, a saber: 0, 1, 2,..., 6. Portanto, qualquer que seja o inteiro, ele é congruente a um único elemento da classe de resíduos modulo 7.
Por exemplo, 20 é representado por 6 na classe de resíduos mod 7, pois 20 ≡ 6 (mod 7).
A idéia de congruência está presente em nossa vida diária se pensarmos que relógios marcam as horas módulo 12, dias da semana são medidos módulo 4, meses do ano seguem um padrão módulo 12. Devido às muitas propriedades semelhantes entre congruências e igualdades, Gauss escolheu o símbolo “≡” para o sinal de congruência.
Observe que a ≡ a (mod n) e, se a ≡ b (mod n), então b ≡ a(mod n). As operações de adição, multiplicação e potenciação se comportam da maneira seguinte.
Se a ≡ b (mod n) e c ≡ d (mod n) então:
a + c ≡ b + d (mod n),
a • c ≡ b • d (mod n),
ar ≡ br (mod n).
O método apresentado no exemplo seguinte é fundamental em nosso tratamento de codificação e decodificação de chaves no sistema RSA. Além disso, constitui-se em um exemplo bastante interessante de aplicação da noção de congruências.
Para determinar o resto da divisão de a por n é suficiente encontrar um inteiro r tal que a ≡ r (mod n), onde 0
r < n. Por exemplo, para determinar o resto da divisão de 310 por 13, efetuamos 310 e depois dividimos por 13, o que não é fácil. Entretanto, a noção de congruência facilita bastante esse procedimento. Em primeiro lugar observamos que:
33 ≡ 1 (mod 13), isso é fácil!
Agora, elevando tudo ao cubo, obtemos
(33)3 ≡ (1)3 mod 13, ou seja, 39 ≡ 1 (mod 13).
Se multiplicarmos ambos os lados da congruência por 3, então obtemos 310 ≡ 3 (mod 13).
Os computadores atuais atingiram níveis tão sofisticados que qualquer cripto-sistema precisa ser suficientemente robusto para resistir aos ataques de indivíduos que desejam quebrar a segurança de suas transações.
Em 1975, os matemáticos W. Diffie e M. Hellman propuseram um sistema totalmente novo de codificação: a criptografia de chave pública. Nesse método codificador duas chaves são utilizadas: uma para codificar e outra para decodificar. Alguns métodos específicos foram desenvolvidos para implementar as idéias de Diffie e Hellmann. Entretanto, o método que recebeu mais apoio e que permanece como padrão é o sistema RSA.
Para codificar um texto, segundo o sistema RSA, são necessários:
(1) um número grande N, que é o produto de dois primos distintos p e q, ou seja, N = p • q.
(2) um 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 inteiro D, conhecido como chave de decodificação, que satisfaz a condição:
E • D ≡ 1(mod (p –1) (q –1)).
Observamos que 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.
Vamos codificar a mensagem PUBLIC KEY usando o sistema RSA com N = 2537 e chave de codificação E = 13. Primeiramente, observamos que N = 43.59 onde 43 e 59 são números primos.
Logo, MDC (13, (43 – 1) • (59 – 1)) = MDC (13, 42 • 58) = 1, pois o inteiro 13 não divide 42 e nem 58; MDC (13, 2537) = 1, pois 13, 43 e 59 (2537 = 43 • 59) são números primos. Agora convertemos o texto usando a tabela de correspondência entre letras e números:
A = 00, B = 01, C = 02, D = 03, ... , X = 23, Y = 24, Z = 25.
Como N = 2537 contém 4 dígitos, nós 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 acima, os 5 blocos da mensagem convertidos são:
1520 0111 0802 1004 2402.
Chamaremos de B o bloco de quatro dígitos. O próximo passo é calcular o valor de cada um dos blocos de quatro dígitos elevados ao expoente 13 (mod 3127), isto é, dado um bloco B, queremos determinar C tal que C = P13 (mod 2537).
Por exemplo, quando codificamos o primeiro bloco, temos que resolver C ≡ 152013 ≡ r (mod 2537). Então, procedemos da seguinte maneira:
15202 = 2.310.400 = 910•2537 + 1730 ≡ 1730 (mod 2537);
15204 = 17302 = 2.992.900 = 1179 • 2537 + 1777 ≡ 1777 (mod 2537);
15208 = 17772 = 3.157.729 = 1244 • 2537 + 1701 ≡ 1701 (mod 2537);
152012 = 15208.• 15204 = 1701 • 1777 = 3.022.677 = 1191 • 2537 + 1110 =
= 1110 (mod 2537);
152013 = 152012 • 1520 = 1110 • 1520 = 1.687.200 = 665 • 2537 + 95 = 95 (mod 2537).
Assim, a codificação de 1520 é 0095.
Os outros blocos da mensagem são codificados da mesma maneira, isto é, elevando-se cada bloco constituído de quatro dígitos à potência 13 (mod 2537). Portanto, o receptor receberá a mensagem cifrada:
0095 1648 1410 1299 0811.
Observe que não podemos converter essa mensagem em letras, pois alguns pares de dígitos constituintes dos blocos são maiores que 25. Na próxima coluna daremos os passos para decodificar mensagens segundo o sistema RSA e decodificaremos a mensagem desse exemplo.
