A criptografia é um assunto indispensável na atualidade. Transações financeiras e troca de mensagens na internet utilizam criptografia para garantir a segurança dos dados pessoais e impedir que pessoas mal intencionadas tenham acesso a contas bancárias e cartões de crédito de outras.

Um dos algoritmos mais famosos é o RSA, criado em 1978 e usado até hoje pela sua eficácia. Ele é chamado de algoritmo de chave assimétrica, pois nele cada usuário possui 2 chaves, uma pública, de conhecimento de todos, usado para que enviem mensagens para o usuario, e uma privada, que só o usuário conhece, deve ser mantida em segredo e serve para decodificar as mensagens recebidas por ele.

Método RSA

Matematicamente, funciona assim:

Geração de chaves:

  1. Escolha de forma aleatória 2 números primos grandes $p$ e $q$, com um mínimo de 100 dígitos cada;
  2. Calcule $n = p \cdot q$;
  3. Calcule a função totiente em $φ(n) = (p-1) \cdot (q-1)$;
  4. Escolha um inteiro $e$, tal que $1 < e < φ(n)$, de forma que $e$ e $φ(n)$ sejam primos entre si;
  5. Calcule $d$, de forma que $d \cdot e \equiv 1 \pmod{φ(n)}$, ou seja, $d$, seja o inverso multiplicativo de $e$ em $\pmod{φ(n)}$.

Dos 5 passos, definimos, então:

A chave pública: o par $\mathbf{(n,e)}$.

A chave privada: a tripla $\mathbf{(p,q,d)}$. (De fato, para desencriptar, basta guardar $d$ como chave privada, mas os primos $p$ e $q$ são usados para acelerar os cálculos).

Cifragem:

Para transformar uma mensagem $m$, onde $1 < m < n-1$, numa mensagem $c$ cifrada usando a chave pública do destinatário $n$ e $e$, basta fazer uma potência modular: $$m^e \equiv c \pmod{n}$$ A mensagem, então, pode ser transmitida em canal inseguro para o receptor. Há um algoritmo para realizar esta potência rapidamente.

Decifragem:

Para recuperar a mensagem $m$ da mensagem cifrada $c$ usando a respectiva chave privada do receptor $n$ e $d$, basta fazer outra potenciação modular: $$c^d \equiv m \pmod{n}$$ O RSA baseia-se no fato de que, embora seja fácil encontrar 2 números primos de grandes dimensões (p.e. 100 dígitos), conseguir fatorar o produto de tais números é considerado computacionalmente complexo (em outras palavras, o tempo estimado para o conseguir ronda os milhares de anos). [fonte: Wikipedia - Método RSA]

Mas e o desafio do aplicativo?

Imagine que você trabalha no comitê organizador da copa mundial de basquete paraolímpico e precisa montar a tabela de jogos. Para evitar fraudes e vazamentos, o comitê lhe envia um e-mail utilizando criptografia RSA com as diversas partidas a ocorrerem na primeira fase. Você ficou curioso para saber o rival do Brasil.
De posse da chave pública, sua chave privada e da mensagem recebida, decodifique-a e descubra, em primeira mão, com quem o Brasil vai jogar.

Observação: Os valores do problema são valores extremamente pequenos, para ilustrar um método de decifrar a mensagem original, mas, na prática, como já dissemos, os valores tem centenas de dígitos.

Mensagem Recebida (cifrada):

A chave pública: o par

A chave privada: a tripla

Com base nessas informações, siga os passos abaixo para descobrir o país oponente:

Passos:

  1. Pelo método RSA, precisamos calcular: .

  2. Como temos a chave privada $\mathbf{(p,q,d)}$, sabemos que . Com primos de mais de 100 dígitos e $\mathbf{n}$ de mais de 200 dígitos, isso seria inviável computacionalmente sem a chave.

  3. É muito mais fácil trabalharmos com números pequenos, e, para isso, quebraremos o problema em 2 menores. Ao invés de tentarmos calcular de uma vez: , calcularemos: e . Assim, achados $r$ e $s$ utilizaremos os valores para determinar $m$.

  4. Mas veja que, mesmo se obtivermos os valores de $\mathbf{r}$ e $\mathbf{s}$, achar $\mathbf{m}$ ainda não é simples. Para isso, utilizaremos o Teorema Chinês dos Restos, que veremos posteriormente.

  5. E para acharmos $\mathbf{r}$ e $\mathbf{s}$, como faremos? ( e )

    O expoente complica por ser um valor alto em relação as contas que estamos acostumados.
    Utilizaremos, então, o Pequeno Teorema de Fermat, que diz:
    "Se $\mathbf{p}$ é primo e $\mathbf{a}$ inteiro, onde $\mathbf{mdc(a,p)=1}$, $\mathbf{a^{p-1} \equiv 1 \pmod p}$"
    Utilize o resultado acima para reduzir o expoente nas equações modulares dos primos e .

    Qual valor de $\mathbf{t}$ satisfaz , para ? $\to$ $\mathbf{t = }$

    Qual valor de $\mathbf{u}$ satisfaz . para ?$\to$ $\mathbf{u = }$

  6. Já diminuímos grande parte do trabalho. Uma forma interessante de resolver potências modulares com um expoente grande é substituí-lo pelo produto de potências com expoentes menores. Por exemplo, para resolvermos $\mathbf{8^5}$ (mod $\mathbf{13}$), decompomos o expoente $\mathbf{5 = 4 + 1}$ usando as maiores potências de $\mathbf{2}$ possíveis no lado direito. Assim: $8^5 = (8^4) \cdot (8^1)$. Potências de 2 são mais fáceis de calcular potências menores: $8^4 = (8^2)^2$. Para calcularmos $8^2$: $\mathbf{8^2 = 64 \equiv 12 \pmod {13}}$. E para chegarmos a $8^4$, basta elevarmos ao quadrado: $\mathbf{8^4 = (8^2)^2 \equiv (12)^2 = 144 \equiv 1 \pmod {13}}$, e assim: $\mathbf{ 8^5 \equiv (8^4) \cdot (8^1) \equiv 1 \cdot 8 \equiv 8 \pmod {13}}$. Preencha os valores da tabela abaixo a fim de auxiliar a encontrar o resto das potências com expoentes $\mathbf{t}$ e $\mathbf{u}$:

    Com ajuda dos valores da tabela, preencha corretamente os valores de r e s das equações modulares abaixo:

    , para $\to$ $\mathbf{r \equiv }$

    , para $\to$ $\mathbf{s \equiv }$

  7. De posse dos valores numéricos de $\mathbf{r}$ e $\mathbf{s}$, qual o valor de $\mathbf{m}$, que satisfaz o sistema? A maneira geral de resolver esse sistema modular é aplicando o Teorema Chinês dos Restos, tema abordado em outro módulo do portal (aqui). Como o método requer vários passos, vamos simplificar a questão a ser resolvida. O $\mathbf{m}$ que satisfaz o sistema, na verdade é um dos valores abaixo:


    Você saberia responder qual o valor correto de $\mathbf{m}$ e o correspondente país rival? (Dica: Teste as 3 possibilidades de restos nas equações modulares do item 7 e veja qual deles satisfaz o sistema de equações modulares dado)
    $\mathbf{m \equiv }$