Exercício de Criptografia RSA

Prévia do material em texto

UNIVERSIDADE FEDERAL DO MARANHÃO 
DEPARTAMENTO DE MATEMÁTICA 
ALUNO: Samuel Cantoária Ferreira 
 
CRIPTOGRAFIA 
 
Utilize os primos 7 e 11 e criptografe usando RSA a informação: " EU ESTUDO MATEMATICA" 
e depois decodifique explicando cada passo. 
 
 Primeiro convertemos o texto “EU ESTUDO MATEMATICA" para número: 
 
143014282930132422102914221029181210 
 
Agora separamos em blocos os números, e usamos a chave 𝑛 = 7 ∗ 11 = 77 para codificar 
cada bloco da seguindo forma, o número codificado será indicado por 𝐶(𝑏) e ele é o resto da 
divisão de 𝑏7 por 𝑛. 
 
14 − 30 − 14 − 28 − 29 − 30 − 13 − 24 − 22 − 10 − 29 − 14 − 22 − 10 − 29 − 18 − 12 
 −10 
 
𝐶(14) = 42 𝐶(13) = 62 𝐶(18) = 39 
𝐶(30) = 2 𝐶(24) = 73 𝐶(12) = 12 
𝐶(28) = 63 𝐶(22) = 22 
 
𝐶(29) = 50 𝐶(10) = 10 
 
 
OBS: Podemos encontrar esses valores com ajuda de uma calculadora, usando a função 
 𝑀𝑂𝐷(𝑚, 𝑛) que retorna o resto da divisão de 𝑚 por 𝑛. 
Logo a mensagem codificada ficará: 
4224263502627322105042221050391210 
 Para decodificar vamos separar os números em blocos: 
42 − 2 − 42 − 63 − 50 − 2 − 62 − 73 − 22 − 10 − 50 − 42 − 22 − 10 − 50 − 39 − 12 
 −10 
 A decodificação 𝐷(𝑎) será o resto da divisão de 𝑎𝑑 por 𝑛, onde 𝑑 é tal que 
7𝑑 ≡ 1 (𝑚𝑜𝑑 (𝑝 − 1)(𝑞 − 1)) 
7𝑑 ≡ 1 (𝑚𝑜𝑑 6 ∗ 10) 
7𝑑 ≡ 1 (𝑚𝑜𝑑 60) ⟹ 𝑑 = 43 
Aplicando o processo acima temos: 
• 𝐷(42) 
Basta resolver o sistema 
{
𝑥 ≡ 4243(𝑚𝑜𝑑 7)
𝑥 ≡ 4243(𝑚𝑜𝑑 11)
(1) 
 
Como 42 ≡ 0 (𝑚𝑜𝑑 7) então 
7343 ≡ 0 (𝑚𝑜𝑑 7) 
E por 42 ≡ −2 (𝑚𝑜𝑑 11) então 
7343 ≡ −(210)4. 23 ≡ −23 ≡ −8 (𝑚𝑜𝑑 11) 
 Ou seja, o sistema (1) equivale ao sistema: 
{
𝑥 ≡ 0 (𝑚𝑜𝑑 7)
𝑥 ≡ −8 (𝑚𝑜𝑑 11)
 
Por 7 ∗ 8 ≡ 1 (𝑚𝑜𝑑 11) e 11 ∗ 2 ≡ 1 (𝑚𝑜𝑑 7) a solução do sistema se dá por 
𝑋 = 0 ∗ 11 ∗ 2 − 8 ∗ 7 ∗ 8 = −448 
Ou melhor 
𝑥 ≡ −448 ≡ 14 (𝑚𝑜𝑑 77) 
Logo 𝐷(42) = 14 
 
• 𝐷(2) 
Basta resolver o sistema 
{
𝑥 ≡ 243(𝑚𝑜𝑑 7)
𝑥 ≡ 243(𝑚𝑜𝑑 11)
(2) 
243 ≡ (26)7. 2 ≡ 2 (𝑚𝑜𝑑 7) 
243 ≡ (210)4. 23 ≡ 23 ≡ 8 (𝑚𝑜𝑑 11) 
 Ou seja, o sistema (2) equivale ao sistema: 
{
𝑥 ≡ 2 (𝑚𝑜𝑑 7)
𝑥 ≡ 8 (𝑚𝑜𝑑 11)
 
Que tem como solução 
𝑋 = 2 ∗ 11 ∗ 2 + 8 ∗ 7 ∗ 8 = 492 
Ou melhor 
𝑥 ≡ 492 ≡ 30 (𝑚𝑜𝑑 77) 
Logo 𝐷(2) = 30 
 
• 𝐷(63) 
Basta resolver o sistema 
{
𝑥 ≡ 6343(𝑚𝑜𝑑 7)
𝑥 ≡ 6343(𝑚𝑜𝑑 11)
(3) 
 
Como 63 ≡ 0 (𝑚𝑜𝑑 7) então 
63 ≡ 0 (𝑚𝑜𝑑 7) 
E por 63 ≡ −3 (𝑚𝑜𝑑 11) então 
7343 ≡ −(310)4. 33 ≡ −43 ≡ −27 ≡ −5 (𝑚𝑜𝑑 11) 
 Ou seja, o sistema (3) equivale ao sistema: 
{
𝑥 ≡ 0 (𝑚𝑜𝑑 7)
𝑥 ≡ −5 (𝑚𝑜𝑑 11)
 
Que tem como solução 
𝑋 = 0 ∗ 11 ∗ 2 − 5 ∗ 7 ∗ 8 = −280 
Ou melhor 
𝑥 ≡ −280 ≡ 28 (𝑚𝑜𝑑 77) 
Logo 𝐷(63) = 28 
 
• 𝐷(50) 
Basta resolver o sistema 
{
𝑥 ≡ 5043(𝑚𝑜𝑑 7)
𝑥 ≡ 5043(𝑚𝑜𝑑 11)
(4) 
 
Como 50 ≡ 1 (𝑚𝑜𝑑 7) então 
5043 ≡ 1 (𝑚𝑜𝑑 7) 
E por 50 ≡ −5 (𝑚𝑜𝑑 11) então 
7343 ≡ −(510)4. 53 ≡ −53 ≡ −125 ≡ −4 (𝑚𝑜𝑑 11) 
 Ou seja, o sistema (4) equivale ao sistema: 
{
𝑥 ≡ 1 (𝑚𝑜𝑑 7)
𝑥 ≡ −4 (𝑚𝑜𝑑 11)
 
Que tem como solução 
𝑋 = 1 ∗ 11 ∗ 2 − 4 ∗ 7 ∗ 8 = −202 
Ou melhor 
𝑥 ≡ −202 ≡ 29 (𝑚𝑜𝑑 77) 
Logo 𝐷(50) = 29 
 
• 𝐷(62) 
Basta resolver o sistema 
{
𝑥 ≡ 6243(𝑚𝑜𝑑 7)
𝑥 ≡ 6243(𝑚𝑜𝑑 11)
(5) 
 
Como 62 ≡ −1 (𝑚𝑜𝑑 7) então 
6243 ≡ −1 (𝑚𝑜𝑑 7) 
E por 62 ≡ −4 (𝑚𝑜𝑑 11) então 
6243 ≡ −(410)4. 43 ≡ −43 ≡ −64 ≡ −9 (𝑚𝑜𝑑 11) 
 Ou seja, o sistema (5) equivale ao sistema: 
{
𝑥 ≡ −1(𝑚𝑜𝑑 7)
𝑥 ≡ −9(𝑚𝑜𝑑 11)
 
Que tem como solução 
𝑋 = −1 ∗ 11 ∗ 2 − 9 ∗ 7 ∗ 8 = −526 
Ou melhor 
𝑥 ≡ −526 ≡ 13 (𝑚𝑜𝑑 77) 
Logo 𝐷(62) = 13 
 
• 𝐷(73) 
Basta resolver o sistema 
{
𝑥 ≡ 7343(𝑚𝑜𝑑 7)
𝑥 ≡ 7343(𝑚𝑜𝑑 11)
(6) 
 
Como 73 ≡ 3 (𝑚𝑜𝑑 7) então 
7343 ≡ (36)7. 3 ≡ 3 (𝑚𝑜𝑑 7) 
E por 73 ≡ −4 (𝑚𝑜𝑑 11) então 
7343 ≡ −(410)4. 43 ≡ −43 ≡ −64 ≡ −9 (𝑚𝑜𝑑 11) 
 Ou seja, o sistema (6) equivale ao sistema: 
{
𝑥 ≡ 3 (𝑚𝑜𝑑 7)
𝑥 ≡ −9 (𝑚𝑜𝑑 11)
 
Que tem como solução 
𝑋 = 3 ∗ 11 ∗ 2 − 9 ∗ 7 ∗ 8 = −438 
Ou melhor 
𝑥 ≡ −526 ≡ 24 (𝑚𝑜𝑑 77) 
Logo 𝐷(73) = 24 
 
• 𝐷(22) 
Basta resolver o sistema 
{
𝑥 ≡ 2243(𝑚𝑜𝑑 7)
𝑥 ≡ 2243(𝑚𝑜𝑑 11)
(7) 
 
Como 22 ≡ 1 (𝑚𝑜𝑑 7) então 
2243 ≡ 1 (𝑚𝑜𝑑 7) 
E 22 ≡ 0 (𝑚𝑜𝑑 11), ou seja, o sistema (7) equivale ao sistema: 
{
𝑥 ≡ 1 (𝑚𝑜𝑑 7)
𝑥 ≡ 0 (𝑚𝑜𝑑 11)
 
Que tem como solução 
𝑋 = 1 ∗ 11 ∗ 2 + 0 ∗ 7 ∗ 8 = 22 
Ou melhor 
𝑥 ≡ 22 (𝑚𝑜𝑑 77) 
Logo 𝐷(22) = 22 
 
• 𝐷(10) 
Basta resolver o sistema 
{
𝑥 ≡ 1043(𝑚𝑜𝑑 7)
𝑥 ≡ 1043(𝑚𝑜𝑑 11)
(8) 
 
Como 10 ≡ 3 (𝑚𝑜𝑑 7) então 
1043 ≡ (36)7. 3 ≡ 3 (𝑚𝑜𝑑 7) 
E por 10 ≡ −1 (𝑚𝑜𝑑 11) então 
7343 ≡ −1 (𝑚𝑜𝑑 11) 
 Ou seja, o sistema (8) equivale ao sistema: 
{
𝑥 ≡ 3 (𝑚𝑜𝑑 7)
𝑥 ≡ −1 (𝑚𝑜𝑑 11)
 
Que tem como solução 
𝑋 = 3 ∗ 11 ∗ 2 − 1 ∗ 7 ∗ 8 = 10 
Ou melhor 
𝑥 ≡ 10 (𝑚𝑜𝑑 77) 
Logo 𝐷(10) = 10 
 
• 𝐷(39) 
Basta resolver o sistema 
{
𝑥 ≡ 3943(𝑚𝑜𝑑 7)
𝑥 ≡ 3943(𝑚𝑜𝑑 11)
(9) 
 
Como 39 ≡ 4 (𝑚𝑜𝑑 7) então 
3943 ≡ (46)7. 4 ≡ 4 (𝑚𝑜𝑑 7) 
E por 39 ≡ 6 (𝑚𝑜𝑑 11) então 
3943 ≡ (610)4. 63 ≡ 216 ≡ 7 (𝑚𝑜𝑑 11) 
 Ou seja, o sistema (9) equivale ao sistema: 
{
𝑥 ≡ 4 (𝑚𝑜𝑑 7)
𝑥 ≡ 7 (𝑚𝑜𝑑 11)
 
Que tem como solução 
𝑋 = 4 ∗ 11 ∗ 2 + 7 ∗ 7 ∗ 8 = 480 
Ou melhor 
𝑥 ≡ 480 ≡ 18 (𝑚𝑜𝑑 77) 
Logo 𝐷(39) = 18 
 
• 𝐷(12) 
Basta resolver o sistema 
{
𝑥 ≡ 1243(𝑚𝑜𝑑 7)
𝑥 ≡ 1243(𝑚𝑜𝑑 11)
(10) 
 
Como 12 ≡ −2 (𝑚𝑜𝑑 7) então 
7343 ≡ −(26)7. 2 ≡ −2 (𝑚𝑜𝑑 7) 
E por 12 ≡ 1 (𝑚𝑜𝑑 11) então 
7343 ≡ 1 (𝑚𝑜𝑑 11) 
 Ou seja, o sistema (10) equivale ao sistema: 
{
𝑥 ≡ −2 (𝑚𝑜𝑑 7)
𝑥 ≡ 1 (𝑚𝑜𝑑 11)
 
Que tem como solução 
𝑋 = −2 ∗ 11 ∗ 2 + 1 ∗ 7 ∗ 8 = 12 
Ou melhor 
𝑥 ≡ 12 (𝑚𝑜𝑑 77) 
Logo 𝐷(12) = 12 
Resumindo os descodificados são: 
𝐷(42) = 14 𝐷(62) = 13 𝐷(39) = 18 
𝐷(2) = 30 𝐷(73) = 24 𝐷(12) = 12 
𝐷(63) = 28 𝐷(22) = 22 
 
𝐷(50) = 29 𝐷(10) = 10 
 
 
Logo a mensagem decodificada ficará: 
143014282930132422102914221029181210