Algoritmo de geração de chaves na criptografia RSA

---

Geração da chave pública

1. Escolha de dois números primos: Escolha dois números primos distintos, geralmente denotados como $p$ e $q$. Por exemplo, $p=61$ e $q=53$. Esses números devem ser mantidos em segredo.

2. Cálculo do módulo $n$: Calcule o produto dos dois números primos: $n=p\cdot q$. No nosso exemplo, $n=61\cdot 53=3233$. O valor de $n$ é público e faz parte da chave pública.

3. Cálculo da função totiente de Euller ($\phi (n)$): Calcule a função totiente de $n$, denotada como $\phi (n)$. A função totiente de um número é o número de inteiros positivos menores do que $n$ e coprimos com $n$ (ou seja, números que não têm fatores em comum com $n$, exceto 1). Para números primos, $\phi (n)=(p-1)\cdot (q-1)$.

   No exemplo, $\phi (n)=(61-1)\cdot (53-1)=60\cdot 52=3120$.

4. Escolha do expoente público ($E$): Escolha um número inteiro $E$ que satisfaça $1<E<\phi (n)$. É comum escolher um número pequeno e primo para $E$, como 1091, pois isso acelera os cálculos e é seguro. Verifique se $E$ e $\phi (n)$ são coprimos (ou seja, seu maior divisor comum é 1).

   No exemplo, escolhemos $E=1091$, que é primo, e $E$ e $\phi (n)$ são coprimos.

5. Chave pública: A chave pública é composta pelo par $(E,n)$. Essa chave é publicamente conhecida e usada para criptografar mensagens.

6. Codificação: Utilize a chave pública $(E;n)$ para fazer a codificação de um bloco numérico $T$. $$ W = T^E \text{ mod } n

   Por exemplo, escolhemos T = 23 e temos a chave pública $(1091; 3233)$, então temos:

W = T^E \text{ mod } n = 23^{1091} \text{ mod } 3233 = 3210

### Geração da Chave Privada: 1. **Cálculo do expoente privado ($D$):** Calcule o [[Inversa modular|inverso multiplicativo modular]] de $E$ em relação a $\varphi(n)$. Em outras palavras, encontre um número $D$ tal que $(E \cdot D) \mod \varphi(n) = 1$. Isso pode ser calculado usando o algoritmo de Euclides estendido. No exemplo, calculamos $D$ de forma que $(1091 \cdot D) \mod 3120 = 1$, e encontramos $D = 2651$. 3. **Chave Privada:** A chave privada consiste apenas no valor $D$. Essa chave é mantida em segredo e é usada para descriptografar mensagens. 5. **Decodificação:** Utilize a chave privada $D$ para fazer a codificação de um bloco numérico $T$. $$ T = W^D \text{ mod } n $$ Por exemplo, temos W = 2037 e temos a chave privada 2017, então temos: $$ T = W^D \text{ mod } n = 3210^{2651} \text{ mod } 3233 = 23

Agora, para criptografar uma mensagem, alguém usa a chave pública $(E,n)$ para elevar a mensagem a uma potência $E$ e, em seguida, aplica o operador de módulo $n$. Para descriptografar, a chave privada $D$ é usada para elevar o texto cifrado a uma potência $D$ e, em seguida, aplica o operador de módulo $n$. A segurança do RSA é baseada na dificuldade de fatorar o módulo $n$ em seus números primos constituintes, o que é um problema computacionalmente complexo. Portanto, a segurança do sistema depende da robustez dos números primos escolhidos e dos cálculos envolvidos.

Referências

---