08 - Algoritmo RSA

Algoritmo RSA (Rivest-Shamir-Adleman)

O RSA é um dos principais algoritmos de criptografia assimétrica (chave pública) utilizados atualmente. Sua segurança reside na dificuldade computacional de fatorar números inteiros extremamente grandes que são produtos de dois números primos.

Fundamentação Matemática

O RSA é baseado no conceito de Trapdoor Permutation (permutação de alçapão). Isso significa que a função é fácil de calcular em uma direção (encriptação), mas extremamente difícil de inverter (decriptação) sem o conhecimento de uma informação específica (a chave privada).

1. Geração de Chaves

Para implementar o RSA, seguimos os seguintes passos matemáticos:

1. Escolha de Primos: Selecione dois números primos grandes e distintos, $p$ e $q$.
2. Cálculo do Módulo ($n$): Multiplique os dois primos: $n=p\times q$ O valor de $n$ é utilizado como módulo para ambas as chaves e é tornado público.
3. Função Totiente ($\Phi$): Calcule o valor da função totiente de Euler para $n$: $\Phi (n)=(p-1)(q-1)$
4. Escolha do Expoente Público ($e$): Escolha um número inteiro $e$ que atenda aos critérios:

• $1<e<\Phi (n)$
• $e$ deve ser coprimo de $\Phi (n)$, ou seja, $\text{mdc}(e,\Phi (n))=1$. (Comumente utiliza-se o valor 65537 por questões de eficiência).

5. Cálculo do Expoente Privado ($d$): Determine $d$ como o inverso multiplicativo modular de $e(\mathrm{mod}\Phi (n))$. Matematicamente: $d\cdot e\equiv 1(\mathrm{mod}\Phi (n))$

Definição das Chaves:

• Chave Pública: O par $(n,e)$.
• Chave Privada: O valor $d$.

---

2. Operações Criptográficas

Encriptação

Para encriptar uma mensagem $m$, o remetente aplica o expoente público $e$ e o módulo $n$ à mensagem (que deve ser tratada como um número inteiro menor que $n$): $c=m^e(\mathrm{mod}n)$

Decriptação

Para recuperar a mensagem original, o destinatário aplica seu expoente privado $d$ ao texto cifrado $c$: $m=c^d(\mathrm{mod}n)$

---

Exemplo em Python

Abaixo, um script simples para ilustrar o processo de geração e uso das chaves. Em implementações reais, utilize bibliotecas consolidadas como cryptography ou PyCryptodome.

# Exemplo simplificado de RSA
def rsa_demonstration():
# 1. Primos pequenos para exemplo (Em produção seriam > 2048 bits)
p = 61
q = 53
 
# 2. n = p * q
n = p * q
 
# 3. Phi = (p-1)*(q-1)
phi = (p - 1) * (q - 1)
 
# 4. Expoente público e (coprimo de phi)
e = 17
 
# 5. Expoente privado d (Inverso modular de e mod phi)
# d * 17 % 3120 == 1
d = pow(e, -1, phi)
 
print(f"--- Configuração RSA ---")
print(f"Chave Pública (n, e): ({n}, {e})")
print(f"Chave Privada d: {d}\n")
 
# Mensagem original (deve ser < n)
m = 42
print(f"Mensagem Original: {m}")
 
# Encriptação: c = m^e mod n
c = pow(m, e, n)
print(f"Texto Cifrado (c): {c}")
 
# Decriptação: m = c^d mod n
m_decrypted = pow(c, d, n)
print(f"Mensagem Decifrada: {m_decrypted}")
 
if __name__ == "__main__":
rsa_demonstration()