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 = 2¹⁰ = 2^{11 – 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 = 2⁸ = 2^2.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 ≡ P¹³  (mod 2.537).

        Para decodificarmos o bloco Q dessa mensagem cifrada, devemos usar a relação

P ≡ Q ⁹³⁷ (mod 2.537), 0 ≤ P < 2.537.

   Observamos que essa relação é válida, pois

Q ≡ P¹³  (mod 2.537)   implica em

Q ⁹³⁷≡ (P¹³)⁹³⁷  (mod 2.537) ≡ P^12.181  (mod 2.537).

Como  13۰937 = 12.181 = 5۰2.436 + 1, obtemos

Q ⁹³⁷≡ (P¹³)⁹³⁷  (mod 2.537) ≡ P^12.181  (mod 2.537) ≡ (P^2.436)⁵ 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,

(P^2.436)⁵ P ≡  P (mod 2.537). 

Logo, por transitividade, obtemos

Q⁹³⁷≡ P  (mod 2.537), 0 ≤ P < 2.537

quando MDC(P, 2.537) = 1.

Observe que a relação 

Q⁹³⁷≡ 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 ⁹³⁷ ≡ P (mod 2.537),

isto é, determinar o resto da divisão de 95⁹³⁷ 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 = 2⁹ + 2⁸ + 2⁷ + 2⁵  + 2³ + 1. 

Sendo assim, temos:

95² = 9.025 = 3۰2.537 + 1.414 ≡ 1.414 (mod 2.537);

logo,

95⁴ ≡ (1.414)² (mod 2.537).

Como (1.414)² = 1.999.396 = 788۰2.537 + 240, segue-se que

95⁴ ≡ 240 (mod 2.537).

Da mesma maneira, obtemos:

95⁸ ≡ 1.786 (mod 2.537);

95¹⁶ ≡ 787 (mod 2.537);

95³² ≡ 341 (mod 2.537);

95⁶⁴ ≡ 2.116 (mod 2.537);

95¹²⁸ ≡ 2.188 (mod 2.537);

95²⁵⁶ ≡ 25 (mod 2.537);

95⁵¹² ≡ 625 (mod 2.537);

Portanto:

(95)⁹³⁷ =

(95)⁵¹² ۰  (95)²⁵⁶۰ (95)¹²⁸۰ (95)³²۰ (95)⁸۰ (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”.