Entendendo a criptografia RSA – parte II


Dando sequência ao primeiro post (Entendendo a criptografia RSA – Parte 1), vou explicar como são feitos os cálculos envolvendo multiplicação em matemática modular e mostrar algumas propriedades interessantes. A intenção é completar a base de conhecimento para compreensão da matemática envolvida na criptografia RSA. Mas é bom frisar que, para tornar a explicação compreensível a todos, algumas particularidades serão ignoradas.

A multiplicação na matemática modular pode ser feita de uma maneira muito simples se os módulos forem calculados antes. Por exemplo, calcular 351 x 437 (mod 10) poderia ser complicado se formos calcular 351x 437 e só depois achar o resto módulo 10. Para isso, teríamos que calcular 351x 437 = 153.387 e só depois achar 153.387 (mod 10) = 7. Calculando os módulos antes, teríamos 351 (mod 10) = 1 e 437 (mod 10) = 7., ou seja, nossa conta se resume a 1 . 7 = 7 (mod 10). Apesar de eu ter escolhido o módulo 10 para tornar mais fácil a visualização, fica também nítida a redução na complexidade dos cálculos se quisermos achar 12.243 x 626 (mod 12) porque podemos calcular 12.243 (mod 12) x 626 (mod 12) e nossa conta se resume a achar 3 x 2 = 6 (mod 12).

Por consequência direta, as contas com potências também podem ficar bastante simplificadas. Para isso, precisamos usar algumas estratégias de cálculos a fim de reduzir o expoente ou transformar as contas em sucessivas multiplicações como a anterior. Por exemplo, calcular 24123.495.876mod 23seria praticamente impossível sem o uso de programa específico de computador, mas podemos fazer as contas de cabeça se usarmos o fato de que 24 = 1 (mod 23). Isso simplifica o cálculo e nos permite ver rapidamente que o resultado é 1. Outro exemplo seria calcular de cabeça 35(mod 7). Transformando em sucessivas multiplicações, teríamos:

  • 3×3=2(mod 7), ou seja, 32= 2(mod 7);
  • Como 33=32x3, podemos fazer 33=2×3=6(mod 7) e seguir até 35;
  • Mas podemos usar que 35=32x32x3 e teríamos 35=2x2x3(mod 7), resultando em 35 =4×3=5(mod 7)

São simplificações como essas que permitem aos computadores calcularem potências cujos expoentes são números com mais de 300 algarismos, o que seria impraticável em tempo hábil se as contas fossem feitas da maneira que estamos acostumados.

Como lidamos com números inteiros e as divisões nem sempre têm resultados inteiros, essa operação não existe em matemática modular. Isso é contornado com o uso do inverso multiplicativo que nada mais é do que encontrar um número a que, multiplicado por seu inverso b, seja igual a 1 (mod c). Em breve falarei de meios eficientes de se encontrar o inverso de um número mas, para entender o funcionamento da RSA, basta saber que a . b = 1 (mod c) implica que a é o inverso multiplicativo de b módulo c e vice-versa.

Se você entendeu o que foi dito nestes dois post da série, já está apto a entender porque a RSA funciona e, ainda, ter um noção dos motivos de sua eficiência. Portanto, no próximo post falarei exatamente sobre isso. Espero que, como eu, você fique maravilhado com a simplicidade da ideia frente à sua eficiência.

Fonte: http://dascoisasqueaprendi.com.br/

Entendendo a criptografia RSA – Parte 1

 

Lomadee, uma nova espécie na web. A maior plataforma de afiliados da América Latina.

, , , , , , , , ,