A hipótese de Riemann e a Internet - IV
Não é fácil elaborar um sistema de criptografia seguro na era dos supercomputadores. Contudo, os cientistas R. Rivest, A. Shamir e L. Adleman, desenvolveram um criptosistema de chave pública, denominado “RSA”, que tem se mostrado inviolável. Esse criptosistema depende do conhecimento matemático dos números primos e suas propriedades.
Como vimos nas colunas anteriores, o trabalho da comunidade matemática foi importantíssimo na elaboração desse sistema. O matemático alemão C. F. Gauss, formulou a noção de congruências, que é fundamental na codificação e decodificação das chaves no sistema RSA. Por outro lado, o método proposto se justifica por causa de um teorema do matemático suíço L. Euler, que é uma generalização de um resultado sobre congruências do matemático francês P. de Fermat, conhecido como “Pequeno Teorema de Fermat”. Tal qual aconteceu em relação ao “Último Teorema de Fermat”, o matemático francês apenas enunciou esse resultado e coube a Euler a demonstração e generalização do “Pequeno Teorema de Fermat”. Esse resultado afirma que:
“Se p é um número primo, e m é um inteiro que não é divisível por p,
então m p – 1 ≡ 1 (mod p), isto é, o resto da divisão de m p – 1 pelo primo p é 1.”
Por exemplo, o resto da divisão de 1.024 = 210 = 211 – 1 por 11 é 1.
A generalização desse teorema, por Euler, aplica-se a qualquer módulo. Sendo assim, utilizaremos a versão requerida para justificar o sistema RSA, onde o módulo é constituído pelo produto de dois números primos.
Teorema de Euler-Fermat:
“Se p e q são um números primos, e m é um inteiro que não é divisível nem por p e nem por q,
então m (p–1)×(q–1) ≡ 1 (mod p•q), isto é, o resto da divisão de m (p–1)×(q–1) por p•q é 1.”
Por exemplo, o resto da divisão de 256 = 28 = 22.4 por 15 = 3.5 é 1.
Como vimos anteriormente, 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)).
A relação entre E e D é simétrica, isto é, se D é chave de decodificação para E, então E é chave de decodificação para D.
Nas colunas anteriores codificamos a mensagem PUBLIC KEY usando o sistema RSA, onde escolhemos
N = 2.537 = 43•59, p = 43, q = 59 e chave de codificação E = 13.
Primeiramente, observamos que o número 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 às letras do alfabeto números naturais, os blocos da mensagem convertidos são:
1520 0111 0802 1004 2402.
Dessa maneira, o receptor receberá a mensagem cifrada:
0095 1648 1410 1299 0811.
Para decodificar essa mensagem necessitamos da chave pública de decodificação, D. Na coluna anterior obtivemos D = 937 como a chave de decodificação.
Codificamos cada bloco, P, da mensagem em um bloco cifrado Q, usando a relação
Q ≡ P13 (mod 2.537).
Para decodificarmos o bloco Q dessa mensagem cifrada, devemos usar a relação
P ≡ Q 937 (mod 2.537), 0 ≤ P < 2.537.
Observamos que essa relação é válida, pois
Q ≡ P13 (mod 2.537) implica em
Q 937≡ (P13)937 (mod 2.537) ≡ P12.181 (mod 2.537).
Como 13۰937 = 12.181 = 5۰2.436 + 1, obtemos
Q 937≡ (P13)937 (mod 2.537) ≡ P12.181 (mod 2.537) ≡ (P2.436)5 P (mod 2.537).
Pelo Teorema de Euler-Fermat, pois 13 e 59 são números primos, obtemos
P (13 – 1) (59 –1) = P 2.436 ≡ 1 (mod 2.537)
e, então,
(P2.436)5 P ≡ P (mod 2.537).
Logo, por transitividade, obtemos
Q937≡ P (mod 2.537), 0 ≤ P < 2.537
quando MDC(P, 2.537) = 1.
Observe que a relação
Q937≡ P (mod 2537), 0 ≤ P < 2.537, MDC(P, 2.537) = 1
é verdadeira para todos os blocos desse exemplo.
Agora, tomemos Q como o bloco 0095. Sendo assim, temos que resolver a congruência
95 937 ≡ P (mod 2.537),
isto é, determinar o resto da divisão de 95937 por 2.537.
Em primeiro lugar, observamos que é mais fácil resolver essa congruência se tomarmos 937 como a somatória de potências de base 2:
937 = 512 + 256 + 128 + 32 + 8 + 1 = 29 + 28 + 27 + 25 + 23 + 1.
Sendo assim, temos:
952 = 9.025 = 3۰2.537 + 1.414 ≡ 1.414 (mod 2.537);
logo,
954 ≡ (1.414)2 (mod 2.537).
Como (1.414)2 = 1.999.396 = 788۰2.537 + 240, segue-se que
954 ≡ 240 (mod 2.537).
Da mesma maneira, obtemos:
958 ≡ 1.786 (mod 2.537);
9516 ≡ 787 (mod 2.537);
9532 ≡ 341 (mod 2.537);
9564 ≡ 2.116 (mod 2.537);
95128 ≡ 2.188 (mod 2.537);
95256 ≡ 25 (mod 2.537);
95512 ≡ 625 (mod 2.537);
Portanto:
(95)937 =
(95)512 ۰ (95)256۰ (95)128۰ (95)32۰ (95)8۰ (95) ≡
625۰25۰2188۰341۰1786۰95 (mod 2.537).
Tomando-se os produtos dois a dois, obtemos:
625۰25 = 15.625 = 6۰2.537 + 403 ≡ 403(mod 2.537)
2.188۰341 = 746.108 = 294۰2.537 + 230 ≡ 230(mod 2.537)
1.786۰95 = 169.670 = 66۰2.537 + 2.228 ≡ 2.228(mod 2.537).
Logo,
625۰25۰2.188۰341۰1.786۰95 (mod 2.537) ≡
403۰ 230۰ 2.228 (mod 2.537).
Como
403۰230 =
92.690 =
36۰2.537 + 1.358 ≡
1.358(mod 2.537)
segue que
1.358۰ 2.228 = 3.025.624 = 1.192۰2.537 + 1.520 ≡ 1.520 (mod 2537).
Concluímos que
625۰25۰2.188۰341۰1.786۰95 =
1.358۰ 2.228 =
3.025.624 =
1.192۰2.537 + 1.520 ≡
1.520 (mod 2.537).
Portanto, Q corresponde ao bloco 1.520.
A pesquisa sobre a Hipótese de Riemann fornece informações tão preciosas, sobre o padrão dos números primos, que avanços nessa investigação poderiam nos levar a um progresso substancial nas técnicas de fatoração e, conseqüentemente, levar à quebra da segurança na transmissão de dados via Internet.
Enfatizamos que o desenvolvimento do criptosistema RSA representa mais um exemplo notável da necessidade da pesquisa em Matemática, pois representa o trabalho de inúmeras gerações de matemáticos. Na verdade, vale lembrar que foi Euclides, há mais de dois mil e trezentos anos, quem demonstrou, de modo genial, que existem infinitos números primos.
Apesar de toda a força e todo o poder que a Matemática evidencia, ainda persiste uma idéia bastante pobre e inconsistente que a identifica apenas a uma linguagem a serviço da ciência... .
A Matemática é uma das maiores criações do espírito humano e encerramos com as palavras de um dos criadores do Cálculo Diferencial e Integral, o matemático alemão Leibniz:
“A Matemática é a honra do espírito humano”.
