Fatoração de primos e criptografia de chave pública (em inglês: RSA encryption)
Criptografia e Números Primos
Por que multiplicar dois números primos é fácil, mas descobrir quais primos formam um produto é quase impossível — e como essa assimetria protege sua senha de banco.
🔐 Multiplicar é fácil. Desfazer, nem tanto.
Uma operação fácil de fazer, difícil de desfazer
Multiplicar dois números primos grandes é instantâneo para qualquer computador — ou até para uma pessoa com papel e caneta, com um pouco de paciência. Mas fazer o processo inverso — pegar o produto e descobrir quais dois primos o geraram — é surpreendentemente difícil, mesmo para os computadores mais rápidos do mundo, quando os primos são grandes o suficiente.
Essa assimetria — fácil de calcular numa direção, difícil de desfazer na outra — é chamada de função de mão única (em inglês: one-way function), e é a base matemática de um dos sistemas de criptografia mais usados do mundo: o RSA, nomeado com as iniciais de seus criadores (Rivest, Shamir e Adleman, 1977).
Como isso vira uma "fechadura" digital
Em termos simplificados, o RSA funciona assim: um site (como o do seu banco) escolhe dois números primos gigantes e os multiplica, gerando uma chave pública — que qualquer pessoa pode usar para criptografar uma mensagem para esse site, incluindo sua senha ou dados do cartão. Só quem conhece os dois primos originais (a chave privada, guardada em segredo pelo próprio site) consegue desfazer essa criptografia e ler a mensagem.
Um atacante que interceptar a mensagem criptografada só conseguiria descobri-la se conseguisse fatorar o produto público de volta aos dois primos originais — e é exatamente essa tarefa que se torna impraticável quando os primos são grandes o bastante.
Por que "grande o bastante" muda tudo
No simulador acima, com primos de 2 dígitos, o produto tem no máximo 4 dígitos — pequeno o suficiente para testar todos os divisores possíveis em milissegundos. Só que a dificuldade de fatorar não cresce de forma linear com o tamanho dos primos: ela cresce exponencialmente. Primos reais usados em RSA têm centenas de dígitos cada, gerando produtos com 600 dígitos ou mais.
🧮 Uma tarefa impraticável, não impossível
Fatorar um número desses não é matematicamente impossível — é só impraticável com a tecnologia atual. Usando os melhores algoritmos conhecidos e os supercomputadores mais rápidos do mundo, estima-se que fatorar uma chave RSA de 2048 bits levaria mais tempo do que a idade do universo. É essa margem de segurança — não uma garantia teórica absoluta — que protege o tráfego criptografado da internet hoje.
Onde você usa isso todos os dias
Cadeado no navegador (HTTPS): sempre que você vê o ícone de cadeado ao lado do endereço de um site, uma variante desse processo de criptografia de chave pública está protegendo a conexão entre seu navegador e o servidor.
Chave PIX e apps bancários: a comunicação entre seu celular e o banco usa criptografia baseada nesses mesmos princípios matemáticos para impedir que alguém interceptando a rede consiga ler os dados da transação.
Assinaturas digitais: o mesmo mecanismo, usado de forma invertida, permite provar que um documento ou uma transação realmente veio de quem diz ter enviado — a base de contratos digitais e de criptomoedas.
Computadores quânticos: uma ameaça futura
Vale mencionar: computadores quânticos suficientemente avançados, rodando um algoritmo chamado algoritmo de Shor, conseguiriam fatorar números grandes muito mais rápido que computadores tradicionais — o que quebraria a segurança do RSA como o conhecemos hoje. É por isso que pesquisadores já desenvolvem ativamente algoritmos de "criptografia pós-quântica", baseados em outros problemas matemáticos difíceis, para o dia em que essa tecnologia se tornar prática.
Resumindo em 4 pontos
- Multiplicar dois primos é fácil; fatorar o produto de volta aos primos originais é difícil — uma função de mão única.
- O RSA usa essa assimetria: uma chave pública (o produto) para criptografar, e uma chave privada (os primos) para decriptografar.
- A dificuldade de fatorar cresce exponencialmente com o tamanho dos primos — por isso primos de centenas de dígitos tornam o ataque impraticável.
- Você usa esse princípio todo dia: no cadeado HTTPS do navegador, no PIX, e em qualquer assinatura digital.