Você está em Comunidade > Colunas

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 pq), isto é, o resto da divisão de m (p–1)×(q–1) por pq é 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 = pq.

 (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:

 ED ≡ 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

QP13  (mod 2.537).

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

PQ 937 (mod 2.537), 0 ≤ P < 2.537.

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

QP13  (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

Q937P  (mod 2.537), 0 ≤ P < 2.537

quando MDC(P, 2.537) = 1.

Observe que a relação 

Q937P  (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 937P (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”.

 

Voltar para colunas

Divirta-se com o LOBIS HOMEM

Produtos de quando CORONA era motivo de alegria

O sonho de ser cantor