Entendendo a criptografia RSA – Parte 1


Muito se ouve falar sobre criptografia e, mais especificamente, da eficiência da RSA para proteção de dados. Mas é menos comum ver explicações acerca dos motivos que a tornam tão boa no que se propõe. Mais que isso, como são relativamente simples as teorias nas quais se embasaram Rivest, Shamir e Adleman para sua criação. Claro que não dá para falar tudo num só post! Por isso, dedicarei a próxima série a este fascinante assunto: A teoria matemática por trás da criptografia RSA.

Desde que li O livro dos códigos, sou fascinado pelo assunto “criptografia”. Em especial, o livro me despertou um enorme interesse pela Enigma e pela criptografia RSA. Apesar de não ter informações muito técnicas, conta a história por trás das coisas e foi justamente isso que me interessou. Especificamente sobre a RSA, fiquei curioso por entender como algo tão “simples” pudesse ser tão eficiente. Até porque, sempre achei que as soluções simples são as mais elegantes.

Antes de qualquer coisa, é preciso entender que tudo se baseia na matemática modular. Apesar do nome soar estranho aos ouvidos de alguns e, ainda, as coisas parecerem ainda mais esquisitas quando se ouve dizer que pode acontecer 9  + 7 = 4 em matemática modular; posso afirmar que tratam-se de conceitos que usamos quase naturalmente no cotidiano. O exemplo mais ilustrativo é o cálculo de horas num relógio de ponteiro: suponha que o ponteiro das horas esteja no nove, onde ele estará depois de sete horas? Viu como não é mais tão inconsebível 9 + 7 = 4?

Outros exemplos simples de contas que custumeiramente fazemos usando matemática modular podem ser o cálculo de que dia da semana será daqui a cinco dias ou em quantos anos acontecerá o próximo ano bissexto. Iniciando uma “tradução” para matemática, dizer que 9 + 7 = 4 num relógio de ponteiro é o mesmo que dizer “9 + 7 deixa resto 4 quando dividido por 12”. Aliás, esta é a principal ideia na matemática modular: buscamos sempre o resto da divisão de um número por outro. Voltando ao relógio, para calcularmos onde o ponteiro estará depois de 49 horas ao invés de 7, teríamos que somar 49 + 9 = 58 e achar o resto da divisão por 12 que é 10. Neste caso, 49 + 9 = 10.

Tendo já um conceito acerca da matemática modular, é importante que saibamos como tudo isso é formalmente escrito. Abstraindo o conceito de congruência, para dizer que 9 + 7 deixa resto 4 ao ser dividido por 12 ou que 49 + 9 deixa resto 10 na mesma divisão, precisamos escrever 9 + 7 = 4 (mod 12) e 9 + 49 = 10 (mod 12). Melhor explicando, dizer que a + b = c (mod x)(lê-se a mais b é igual a c módulo x), é o mesmo que dizer que a + b deixa resto c ao ser dividido por x.

Explicado tudo isso, vamos a resultados práticos! Dois deles podem ser ditos assim: a + b (mod x) = a (mod x) + b (mod x). Apesar de parecer um resultados sem muita utilidade, imagine-se calculando onde estaria o ponteiro do relógio já citado se passassem 13 horas e, depois, mais 25 horas! Normalmente, somaríamos 9 + 13 + 25, dividiríamos por 12 e acharíamos o resto. Seria como calcular 9 + 13 + 25 (mod 12), o que pode não ser um cálculo tão trivial. Mas pode ser simplificado se fizermos 9 (mod 12) + 13 (mod 12) + 25 (mod 12), ou seja, calcular os restos antes de somar. Teríamos então: 9 + 1 + 1 = 11 (mod 12). Viu como as contas ficam mais simples?! O mais impressionante é que o mesmo se aplica à multiplicação, mas isso fica para o próximo post.

Fonte: http://dascoisasqueaprendi.com.br/

Lomadee, uma nova espécie na web. A maior plataforma de afiliados da América Latina.

, , , , ,