25 de março de 2016

A Matemática é Bonita - Parte 2 - Um Pouco Sobre Criptografia de Chave Pública (RSA)

Você entra na sua rede social favorita, ou mesmo no seu banco, o que garante que ninguém é capaz de ter acesso a sua senha? O site ou aplicativo é seguro, correto? Mas como? Para isso é utilizados uma criptografia de chave pública, onde existem duas chaves, uma pública, que todos têm acesso, e uma privada, que apenas um dos lados tem acesso. Os dados a serem enviados são criptografados com a chave pública e apenas quem detém a chave privada pode descriptografá-los.

Existem várias técnicas de criptografia que podem ser utilizadas para tal aplicação, como as baseadas em curvas elípticas, porém aqui falaremos sobre as assentadas em números primos, técnica chamada de RSA devido a seus criadores Rivest, Shamir e Adleman. É interessante que essa técnica foi publicada pelos 3 em 1977, porém em 1973 Clifford Cocks, um pesquisador trabalhando para a GCHQ (NSA britânica), já havia descoberto a técnica, fato que veio a público apenas em 1997.


Essa técnica se baseia no principio que fatorar o produto de dois números primos é uma tarefa computacionalmente muito demorada. Um número primo é um número que apenas é divisível por 1 e por ele mesmo, assim os números: 2, 3, 5, 7, 11, 13, 17... são primos. Enquanto 4 e todos os outros pares não são, pois são divisíveis por 2, o número 9 não é, pois é divisível por 3, o 15 é por 3 e pelo 5.

Agora imagine dois números primos muito grandes, fazer sua multiplicação é fácil, por outro lado depois de realizar a multiplicação é difícil saber quais eram os fatores. Novamente tomemos um exemplo: A multiplicação de 3.167 por 5.483 resulta em 17.364.661, para achar novamente os dois fatores eu necessito dividir este grande número por todos os primos entre 2 até o primeiro fator, ou seja, eu teria de realizar algumas centenas de divisões (na realidade existem algoritmos melhores, que não cabem aqui). O problema começa com números maiores, no nosso caso o número tem apenas de 8 dígitos, em 2009 pesquisadores levaram 2 anos para fatorar um número de 232 dígitos utilizando centenas de computadores.

Agora sabemos que fatorar números grandes é uma tarefa computacionalmente demorada, mas como a criptografia utiliza isso para funcionar? Eu irei explicar o algoritmo praticamente copiando o exemplo da Wikipédia, porém escrevi um programinha em Python que você pode brincar, trocando um número a ser criptografado ou os números primos utilizados.
1. Primeiramente, escolha dois números primos arbitrariamente: p = 61 e q = 53;
2. Multiplique-os agora, tal que n = p * q = 61 * 53 = 3233;
3. Calcule agora o Totiente de 3233, tal que φ(3233) = (p-1) * (q-1) = 60 * 53 =3120;
Agora cabe um parênteses para explicar o que é a Função totiente de Euler (esse paragrafo pode ser desconsiderado se você simplesmente aceitar o cálculo feito no passo 3). Esta função calcula o número de coprimos entre 1 e este número. Dois números são coprimos quando apenas o número 1 é divisor de ambos, por exemplo, 5 e 7, 4 e 9, etc. Por outro lado, os números 9 e 15 não são coprimos, pois além do 1, o 3 também é divisor de ambos, 7 e 14 não, pois 7 é divisor. Um fato interessante é que para números primos, a função totiente é sempre φ (n) = (n-1), pois um primo só é divisível por 1 e ele mesmo, além disso, ela tem uma propriedade de que φ (pq) = φ(p) * φ(q), que apenas é válida quando p e q são coprimos, funções com essa propriedade são chamadas de "Funções multiplicativas". Isso torna possível calcular φ(pq) = (p-1) * (q-1), quando p e q são primos, pois primos sempre são coprimos.
4. Escolha qualquer "e" entre 1 e 3120 que seja coprimo a 3120, escolhemos e = 17 (basta escolher um primo que não divida 3120, automaticamente serão coprimos);
5. Calcule o inverso multiplicativo modular "d" tal que:
d * e mod φ(n) = 1
d * 17 mod 3120 = 1
d = 2753
Repare que apenas existe d, se "n" e "e" são coprimos.
Temos agora nossa chave pública:
"n" = 3233 e "e" = 17
Nossa chave privada:
d = 2753
A equação para criptografar sendo:
dado_criptografado = (dado^e)mod(n)
dado_criptografado = (dado^17)mod(3233)
E a descriptografar:
dado = (dado_criptografado^d)mod(3233)
Coloque um número no lugar de "dado" e tente fazer as contas. O problema é que o numero fica extremamente grande e nossas calculadoras o arredondam ou o resultado é infinito, portanto precisamos utilizar bibliotecas especificas para isso. No meu caso, decidi utilizar Python, que suporta inteiros de tamanho arbitrário. Abaixo mostro um pequeno algoritmo (com muitos comentários) implementando o RSA. É evidente que é algo super simples e aplicações de verdade implementam de maneiras bem mais eficientes.


Este artigo ficou bem denso, mas é interessante para podermos ver que com conceitos relativamente simples podemos fazer coisas complicadas. A criptografia utilizada na maioria das transações seguras na internet é baseada neste algoritmo.

Nenhum comentário: