O RSA (Rivest-Shamir-Adleman) é um sistema de criptografia de chave pública amplamente usada. É baseado na dificuldade prática de fatorar o produto de dois grandes números primários. Aqui está um colapso:  
 como o RSA funciona:   1. 
 Geração de chave:  *Escolha dois números primos distintos, *p *e *q *. Quanto maiores estes são, mais segura a criptografia. 
 * Calcule * n =p * q *. * n* é o módulo. 
 * Calcule φ (n) =(P-1) (Q-1). Esta é a função totient de Euler, representando o número de números inteiros menos que *n *que são relativamente primos para *n *. 
 * Escolha um número inteiro * e * (expoente público) de modo que 1 <* e * <φ (n) e GCD (e, φ (n)) =1 (o maior divisor comum é 1; * e * e φ (n) são coprime). Uma escolha comum é 65537 (2 
 16 
 + 1). 
 * Calcule * d * (expoente privado) de modo que * d * * e ≡ 1 (mod φ (n)). Isso significa * d * * * e * deixa um restante de 1 quando dividido por φ (n). Isso geralmente é feito usando o algoritmo euclidiano estendido.  
 2. 
 chave pública: A chave pública é o par (*n*,*e*). Isso é compartilhado publicamente.  
 3. 
 Chave privada: A chave privada é o par (*n*,*d*). Isso deve ser mantido em segredo.  
 4. 
 Criptografia: Para criptografar uma mensagem *m *(representada como um número menor que *n *):
 * CipherText * c * =* m 
 e 
 *(mod *n *)  
 5. 
 Decripção: Para descriptografar o texto cifrado *C *:
 * PlainText * m * =* c 
 d 
 *(mod *n *)   
 Por que funciona: O teorema de Euler afirma que se *a *e *n *são coprime, então *a 
 φ (n) 
 1 (mod n)*. A escolha de * d * e a aritmética modular garantem que a descriptografia recupere corretamente a mensagem original. A quebra da RSA depende da fatoração *n *em *p *e *q *, que é computacionalmente inviável para primos suficientemente grandes.    
 Resolvendo os numéricos RSA:   A dificuldade de resolver problemas numéricos da RSA depende de quais informações são fornecidas. Aqui estão exemplos de problemas típicos e como resolvê -los:  
 Exemplo 1:Criptografia    * 
 Problema: Dado * p * =11, * q * =13, * e * =7, e mensagem * m * =5, criptografar a mensagem.  
 * 
 Solução:  1. Calcule * n * =* p * * * q * =11 * 13 =143 
 2. Calcule φ (n) =(11-1) (13-1) =120 
 3. Verifique se GCD (7, 120) =1 (eles são coprime) 
 4. Encrypt:*c *=*m 
 e 
 *(mod *n *) =5 
 7 
 (Mod 143) 
 * 5 
 7 
 =78125 
 * 78125 ÷ 143 ≈ 546 com um restante de 67 
 * Portanto, * C * =67   
 Exemplo 2:Decripção    * 
 Problema: Dado * p * =11, * q * =3, * e * =7 e CipherText * c * =10, descriptografar o texto cifrado.  
 * 
 Solução:  1. Calcule * n * =* p * * * q * =11 * 3 =33 
 2. Calcule φ (n) =(11-1) (3-1) =20 
 3. Encontre * d * tal que * d * * * e * ≡ 1 (mod φ (n)) isso significa 7 * * d * ≡ 1 (mod 20). Você pode resolver isso usando o algoritmo euclidiano estendido ou por tentativa e erro. * d * =3 funciona porque (7 * 3) =21 ≡ 1 (mod 20). 
 4. Descriptografar:*m *=*c 
 d 
 *(mod *n *) =10 
 3 
 (Mod 33) 
 * 10 
 3 
 =1000 
 * 1000 ÷ 33 ≈ 30 com um restante de 10 
 * Portanto, * m * =10   
 Exemplo 3:Encontrar D (Expoente Privado)    Encontrar 'd' geralmente requer o algoritmo euclidiano estendido, que está além do escopo de uma explicação simples aqui. No entanto, para números menores, tentativa e erro podem funcionar. Você está procurando um número 'd' que satisfaz a congruência * d * * e ≡ 1 (mod φ (n)).    
 Considerações importantes:   * 
 grandes números: O RSA do mundo real usa números primários extremamente grandes (centenas ou milhares de bits). Cálculos manuais são impossíveis; Software especializado é necessário. 
 * 
 aritmética modular: A compreensão da aritmética modular é crucial para trabalhar com RSA. Muitas calculadoras e linguagens de programação têm funções internas para exponenciação modular. 
 * 
 Segurança: A segurança do RSA depende inteiramente da dificuldade de fatorar grandes números. À medida que o poder da computação aumenta, o tamanho dos primos utilizados também deve aumentar para manter a segurança.   
 Esses exemplos ilustram os princípios básicos. Para problemas mais avançados, você provavelmente precisará usar ferramentas computacionais e uma compreensão mais profunda da teoria dos números.