Uma Caminhada por Encriptação e Coisas Quânticas

Publicado em 21 de abril de 2025

Recentemente, assisti a um vídeo explicando como um computador quântico poderia, em teoria, acelerar significativamente o processo de quebra da criptografia RSA. Isso me deixou algumas perguntas: afinal, por que criptografamos as coisas? Como o RSA funciona? O que isso tem a ver com números primos? Como um computador quântico realmente funciona? E por aí vai. Infelizmente, não responderemos a todas essas perguntas agora, mas farei o meu melhor para explorar a maioria delas.

No espírito de “começar pelo começo”, imagine que você queira enviar uma mensagem a um amigo, mas não quer que ninguém mais a leia. Você não pode garantir que a mensagem não será interceptada, então vocês dois criam uma cifra — basicamente, uma maneira de embaralhar a mensagem para que, se for interceptada, pareça um amontoado de caracteres sem sentido e o conteúdo original permaneça protegido.

A forma “mais simples” de cifra que você poderia tentar é chamada cifra de César (e sim, ele a utilizava). Ela desloca as letras por um número fixo — César usava 3, então A virava D, B virava E e assim por diante. O destinatário só precisa saber esse “número” e realizar a operação inversa para recuperar a mensagem original. É fácil perceber que esse método não é nada seguro.

Tangente - Melhorias Simples para Criptografar Mensagens

Uma melhora direta sobre algoritmos baseados em deslocamento é usar um mapeamento de caracteres — atribuindo a cada letra uma substituição única. Por exemplo, A → M, B → D e assim por diante. Isso torna a cifra mais robusta, pois é mais difícil adivinhar mapeamentos individuais do que um único deslocamento global.

Contudo, esse método ainda é facilmente quebrável com análise de frequência. Em qualquer idioma, as letras aparecem com frequências bem definidas. Em inglês, por exemplo, a letra mais comum é “e”, seguida de “t” e “a”. Em português brasileiro, a ordem é “e”, “a” e “o”. Ao analisar quantas vezes cada caractere aparece na mensagem criptografada, muitas vezes é possível deduzir o mapeamento subjacente.

Um método desenvolvido em meados de 1500 pelo criptólogo italiano Giovan Battista Bellaso — depois (injustamente) atribuído a um francês e conhecido como cifra de Vigenère — foi o primeiro a introduzir a ideia de usar uma chave para criptografar uma mensagem. A ideia é simples: o remetente e o destinatário combinam uma palavra‑chave, por exemplo ABACAXIKRYPTONITA, e cada letra da mensagem é deslocada pelo índice da letra correspondente na chave. Isso significa que o primeiro caractere da mensagem seria deslocado por 15 (o índice de “A” vale 0, “B” vale 1…), o segundo por 1 (“B”), e assim por diante.

Esse método é consideravelmente mais resistente a ataques de análise de frequência. Mas, como a chave deve ser repetida para criptografar mensagens longas, padrões repetidos podem revelar o comprimento da chave. Uma vez conhecido esse comprimento, a análise de frequência pode ser aplicada a cada segmento de tamanho fixo, tornando a mensagem novamente vulnerável.

Uma variante engenhosa, que começa a introduzir o conceito de números primos, é a versão running key da cifra de Vigenère. Nessa abordagem, duas (ou mais) chaves de comprimentos diferentes são usadas para criptografar a mensagem — efetivamente criptografando‑a várias vezes. Se as chaves forem coprimas (ou seja, não tiverem fatores em comum), o comprimento efetivo da chave é o mínimo múltiplo comum (MMC) dos comprimentos individuais. Por exemplo, usar chaves de comprimento 10, 12 e 15 resulta em um comprimento combinado de 60. Mas se você usar 8, 11 e 15, o comprimento salta para 1 320. Fica claro que chaves com fatores compartilhados produzem padrões mais previsíveis, facilitando a quebra da cifra.

Eu adoraria fazer um desvio para falar sobre a máquina Enigma e como os Aliados a quebraram (é uma história fascinante de matemática, criptografia e computação primitiva), mas vamos tentar manter o foco… por enquanto.

Criptografia RSA

Vamos revisitar alguns conceitos e dar-lhes nomes adequados. Quando usamos métodos de deslocamento e chaves, assumimos que, ao ultrapassar a última letra (Z, por exemplo), simplesmente voltamos ao início — começando novamente do A. Isso implica que, se você tem 26 letras, a letra A pode ser representada não apenas por 1, mas também por 27, 53 e assim por diante. Se dividirmos esses números pelo tamanho do alfabeto, o resto (ou módulo) da divisão nos dá o índice real da letra.

Esse conceito é chamado aritmética modular e desempenha um papel central na criptografia moderna. Expressamos essa equivalência assim:

$$ a \equiv b \pmod{n} $$

Lê‑se: “$a$ é congruente a $b$ módulo $n$”, significando que $a$ e $b$ deixam o mesmo resto quando divididos por $n$.

Vamos percorrer o algoritmo de geração de uma chave RSA, tentar criptografar/descriptografar algumas mensagens e depois entender por que tudo isso funciona. O princípio é encontrar três inteiros positivos $e$, $d$ e $n$ (sim, $e$ será usado para encriptar e $d$ para descriptar) tais que:

$$ (m^{e})^{d} \equiv m \pmod{n} $$

Essa relação mostra que a operação é reversível: se você fizer exponenciação modular em uma mensagem $m$ usando $e$ e depois novamente usando $d$, obtém a mensagem original. Esses números são escolhidos de modo que, dado apenas $e$ e $n$ (a chave pública), seja muito difícil determinar $d$ (a chave privada).

Vamos testar com um exemplo:

Os números $e$ e $n$ são divulgados como parte da chave pública. A única relação conhecida é que:

$$ ed \equiv 1 \pmod{\Phi(n)} $$

Isso implica que, para calcular $d$, é preciso conhecer $\Phi(n)$, mas $\Phi(n)$ depende dos primos originais $p$ e $q$ usados para gerar $n$. Em outras palavras, um atacante teria de fatorar $n$ nos seus componentes primos. E aqui está o ponto: não há um método rápido conhecido para isso. Mesmo com algoritmos engenhosos bem mais rápidos que testar todos os números até $\sqrt{n}$, o tempo ainda está longe de ser polinomial.

Quanto Tempo Realmente Levaria para Fatorar uma Chave RSA de 2048 bits?

Fatorar chaves RSA grandes, como um módulo de 2048 bits (aprox. 617 dígitos decimais), geralmente envolve o uso do General Number Field Sieve (GNFS), atualmente o algoritmo clássico de fatoração mais rápido conhecido. A complexidade do GNFS é dada por:

$$ \exp\left[1.923 \cdot (\ln n)^{1/3} \cdot (\ln\ln n)^{2/3}\right] $$

onde $n$ é o número a ser fatorado.

Para ilustrar, a fatoração do RSA‑768, um número de 768 bits (232 dígitos), exigiu cerca de dois mil anos‑CPU quando concluída em 2009. Escalonar esse cálculo para um módulo de 2048 bits aumenta drasticamente a complexidade, tornando‑o impraticável com os recursos de computação clássica atuais.

Fazendo uma estimativa concreta, assumindo uma capacidade de $10^{18}$ operações por segundo, fatorar um número RSA de 2048 bits exigiria cerca de $10^{17}$ segundos, ou aproximadamente 3,17 bilhões de anos — muito além de qualquer horizonte factível.

Consequentemente, chaves RSA de 2048 bits ainda são consideradas seguras contra métodos clássicos de fatoração disponíveis hoje, o que explica seu uso contínuo em comunicações digitais seguras.

O Algoritmo de Shor

Em 1994, Peter Shor, cientista da computação, mostrou que um algoritmo quântico — agora chamado algoritmo de Shor — pode fatorar um inteiro de $N$ bits em tempo polinomial em $N$, ameaçando a criptografia RSA.

A primeira parte do algoritmo de Shor consiste em transformar o problema de “encontrar fatores” no problema de “encontrar o período” de uma função. Primeiro, vamos entender o que é esse período. Considere a sequência:

$$ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, \dots $$

Agora, vamos ver o que acontece quando usamos $\bmod{n}$; por exemplo, suponha $n = 15$:

$$ 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, \dots $$

A sequência se repete com período 4. De fato, todo inteiro menor que $n$ e coprimo de $n$ forma um grupo finito sob multiplicação $\bmod{n}$. Por exemplo, para $n = 15$, os elementos do grupo são ${1, 2, 4, 7, 8, 11, 13, 14}$. O produto de quaisquer dois números $\bmod{n}$ é um elemento do próprio grupo:

Observe que, por causa disso, qualquer $x$ no grupo pode ser multiplicado por si mesmo qualquer número de vezes (ou seja, pode ser exponenciado), e o resultado continuará no grupo. Além disso, o Teorema de Euler nos diz que, para qualquer elemento $x$ desse grupo $ mod n$ em que $n = pq$, vale:

$$ x^{(p-1)(q-1)} \equiv 1 \pmod{n} $$

Lembre que, ao definir as chaves RSA, calculamos $\Phi(n) = (p-1)(q-1)$. Esse número é um limite superior para o período $s$ da função de exponenciação modular — o período real sempre divide $\Phi(n)$, mas pode (e costuma) ser menor:

$$ f(r) = x^{r} \pmod{n} $$

Assim, se escolhemos um $x$ aleatório coprimo de $n$ e encontramos o período $s$, temos que $x^{s} \equiv 1 \pmod{n}$. Agora, supondo que demos sorte e $s$ seja par, podemos reescrever:

$$ x^{s} - 1 \equiv 0 \pmod{n} \ \Rightarrow (x^{\frac{s}{2}} - 1)(x^{\frac{s}{2}} + 1) \equiv 0 \pmod{n} $$

Se nem $x^{\frac{s}{2}} - 1$ nem $x^{\frac{s}{2}} + 1$ forem múltiplos de $n$, isso significa que encontramos um fator de $n$. Quando algo $\equiv 0 \pmod{n}$, o resto da divisão por $n$ é zero — o que implica que esse algo é múltiplo ou contém um fator de $n$. Se $n = pq$, acabamos de encontrar $p$ ou $q$, quebrando a criptografia.

No nosso exemplo de $n = 15$, escolha $x = 7$. Para encontrar o período $s$, precisamos do menor $r$ que satisfaça:

$$ 7^{r} \equiv 1 \pmod{15} $$

Testando $r = 2$:

$$ 7^{2} \pmod{15} = 4 $$

não é 1. Com $r = 3$:

$$ 7^{3} \pmod{15} = 13 $$

Também não é 1. Já $r = 4$:

$$ 7^{4} \pmod{15} = 1 $$

Logo, o período é $s = 4$. Como $4$ é par, podemos calcular:

$$ 7^{\frac{4}{2}} - 1 = 48 \pmod{15} = 3 $$

e

$$ 7^{\frac{4}{2}} + 1 = 50 \pmod{15} = 5 $$

obtendo os fatores de $n$, $p$ e $q$.

Então, Onde Diabos Está a Parte Quântica?

Você deve ter reparado: para encontrar o período $s$, tivemos que testar vários $r$ até achar um que satisfizesse a congruência. No fim, ainda é um processo de tentativa e erro com muitos palpites.

Mas e se pudéssemos “chutar” um monte de números ao mesmo tempo e depois extrair informação útil desse chute? Vamos apresentar alguns conceitos que permitem isso:

Transformada de Fourier

Vimos que lidamos com funções periódicas que se repetem com período $s$. Em física, há o conceito da Transformada de Fourier, que, dado um sinal periódico (ou qualquer sinal), o decompõe em seus componentes de frequência e, inversamente, reconstrói o sinal a partir deles.

Por exemplo, se temos um sinal assim:

Podemos aplicar uma Transformada de Fourier para descobrir as frequências que o compõem:

Isso significa que podemos usar uma Transformada de Fourier para encontrar o período de uma função repetitiva. O equivalente quântico é a Transformada de Fourier Quântica — o conceito é o mesmo.

Superposição e Medidas

Uma das propriedades mais faladas de sistemas quânticos é que eles podem estar em vários estados simultaneamente; isso é uma superposição. Suponha que temos 4 qubits; poderíamos preparar um estado quântico como:

$$ |\psi\rangle = \frac{1}{4}\big(|0000\rangle + |0001\rangle + |0010\rangle + \dots + |1111\rangle\big) $$

Essa é a superposição, com mesma amplitude, dos números binários 0 a 15. O fator $1/4$ garante normalização, pois $(1/4)^{2} \times 16 = 1$.

A física quântica não permite acessar diretamente todas essas informações. Para extrair algo, precisamos fazer uma medida, que colapsa o estado e devolve apenas um resultado (por exemplo, $|0110\rangle$), destruindo os demais. Ademais, sistemas quânticos podem ficar emaranhados; medir um qubit pode determinar instantaneamente o estado de outro — fato que exploraremos.

Tentando Concluir

Em resumo, a parte quântica do algoritmo funciona assim. Temos dois “registradores” (o registrador de período e o registrador computacional), que são apenas conjuntos diferentes de qubits. Primeiro, preparamos, no registrador de entrada, uma superposição de todos os expoentes possíveis $r$:

$$ \frac{1}{\sqrt{Q}}\sum_{r=0}^{Q-1}|r\rangle $$

Vamos analisar o significado dessa equação. A parte $1/\sqrt{Q}$ é um "fator de normalização" — na física quântica, os estados precisam somar uma probabilidade total de 1. As probabilidades são obtidas ao "elevar ao quadrado" um estado (tecnicamente, multiplicando o estado pelo seu complexo conjugado, já que a mecânica quântica envolve números complexos). O grande símbolo $\sum$ indica que o estado quântico completo é representado como uma soma de diferentes estados básicos. Por fim, a notação $|r\rangle$ representa um vetor de estado quântico, onde r funciona apenas como um rótulo amigável para o vetor. Na computação quântica, esses estados correspondem aos "qubits", que são o equivalente quântico dos bits clássicos usados para representar números em binário.

Na física quântica, como os estados são vetores, podemos aplicar "transformações" a esses vetores, como a exponenciação modular – matematicamente, estamos multiplicando uma matriz que representa a transformação pelo vetor de estado – depois disso, levamos o vetor a outro estado – uma forma simples de pensar nisso é aplicar uma matriz de rotação $H_{\theta}$ a um vetor $|x\rangle$ – o resultado é o vetor rotacionado – se $\theta = 90^\circ \Rightarrow H_{\theta}|x\rangle = |y\rangle$.

Em seguida, aplicamos a função de exponenciação modular a esse sistema e a escrevemos no registrador de saída (na prática, o Algoritmo de Shor implementa isso como “quadrados repetidos” — pense nisso como elevar um número ao quadrado várias vezes — elevar ao quadrado é apenas multiplicar, algo que pode ser implementado com facilidade tanto em um computador clássico quanto em um quântico). Após isso, os dois registradores estarão no estado:

$$ \dfrac{1}{\sqrt{Q}}\sum_{r=0}^{Q-1}|r\rangle_{i}|a^{r}\pmod{n}\rangle_{o} $$

Vamos tentar observar isso novamente com um conjunto de 4 qubits — o registrador de entrada $|r\rangle_{i}$ seria inicializado com (vamos trocar a notação binária pela inteira e, por ora, não nos preocupar com a normalização):

$$ |1\rangle_{i} + |2\rangle_{i} + |3\rangle_{i} + |4\rangle_{i} + |5\rangle_{i} + |6\rangle_{i} + |7\rangle_{i} + \cdots $$

Vamos novamente usar o número $7$ como nosso chute, então a exponenciação modular aplicada será $|7^{r}\pmod{15}\rangle$ — o estado resultante terá os restos da exponenciação modular para cada $r$:

$$ |1\rangle_{i}|7\rangle_{o} + |2\rangle_{i}|4\rangle_{o} + |3\rangle_{i}|13\rangle_{o} + |4\rangle_{i}|1\rangle_{o} + |5\rangle_{i}|7\rangle_{o} + \cdots $$

Se medirmos, por exemplo, $|7\rangle_{o}$ no registrador de saída, essa medição destruirá todos os outros estados no registrador de entrada que não produzem $|7\rangle_{o}$ como resto. Lembre-se do "emaranhamento" — o registrador de entrada tem uma superposição de todos os números, enquanto o registrador de saída tem uma superposição de todos os restos da exponenciação modular, e eles estão emaranhados. Então, se medirmos o resto $|7\rangle_{o}$, não pode haver nenhuma chance de que exista um número no registrador de entrada que gere um resto diferente de $|7\rangle_{o}$. O que sobra é o estado:

$$ |1\rangle_{i}|7\rangle_{o} + |5\rangle_{i}|7\rangle_{o} + |9\rangle_{i}|7\rangle_{o} + |13\rangle_{i}|7\rangle_{o} + \cdots $$

Veja que agora o registrador de entrada tem um período de $4$ (1, 5, 9, 13, ...). Voltando ao caso geral, o que sobra no registrador de entrada pode ser escrito como:

$$ |r\rangle + |r + s\rangle + |r + 2s\rangle + |r + 3s\rangle + \cdots $$

Se pudéssemos medir esse estado várias vezes (lembre-se de que uma medição sempre retorna apenas um único estado), poderíamos inferir rapidamente o período $s$ — mas não podemos, porque a medição anterior que fizemos em $|a^{r}\pmod{n}\rangle$ retornaria um resto diferente a cada vez que repetíssemos o experimento (é aleatório), então não conseguiríamos tirar nenhuma conclusão.

Então aplicamos a Transformada de Fourier Quântica. Ela não devolve $1/s$ diretamente, mas produz uma superposição que interfere construtivamente em múltiplos inteiros de $1/s$:

$$ |1/s\rangle + |2/s\rangle + |3/s\rangle + \cdots $$

Medindo esse sistema, encontramos um múltiplo de $1/s$ (uma fração). Usamos então um algoritmo clássico, como frações contínuas, para recuperar $s$, ou repetimos o experimento para estimar a distribuição.

Conhecido $s$, basta fazer os mesmos testes descritos na parte clássica (verificar se $s$ é par, se não é múltiplo de $n$) e, se tudo der certo, o algoritmo fatora $n$ com sucesso.

Conclusão — O que Devemos Levar Disso?

Começamos com o deslocamento de três letras de César e terminamos mergulhados em transformadas de Fourier quânticas. No caminho, vimos:

Então, devemos entrar em pânico? Não exatamente — mas devemos ficar atentos. Órgãos de padronização já estão lançando algoritmos de criptografia pós‑quântica (PQ‑C) preparados para resistir a ataques clássicos e quânticos. Na próxima década, navegadores, VPNs e sistemas operacionais migrarão para PQ‑C do mesmo jeito que, um dia, passaram de RSA‑1024 para RSA‑2048.

Até lá, o RSA e seus amigos baseados em fatoração continuam firmes — prova elegante de que ideias antigas da teoria dos números podem proteger terabytes de dados modernos. E, se você se perder no alfabeto (MMC, QFT, GNFS…), lembre‑se: toda mensagem segura que você envia é, basicamente, uma cifra de César muito sofisticada, esticada por vinte e um séculos de engenhosidade matemática.

Boa criptografia e, quem sabe, um dia, uma boa descriptografia quântica também.