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.
