Congruência modular aplicada à criptografia

Abstract

Nos meios eletrônicos e internet existem várias informações que devem ser mantidas em sigilo, as quais somente o emissor e o destinatário podem saber. Um meio de garantir o sigilo da informação é a criptografia, palavra que vem do grego kryptós  “secreto” e gráphein  “escrita”, que é o estudo das técnicas de codificação/decodificação de informações. A criptografia busca a melhor forma de transformar dados em material dificilmente decifrável através de processos puramente matemáticos. Uma das ferramentas mais comuns é o uso da Matemática Discreta para, através da Congruência Modular, trabalhar sobre um código numérico onde apenas quem tem a chave de descriptografar consegue ler a mensagem (Cf. [1]). Este trabalho objetiva mostrar a importância da criptografia, e como a Criptografia RSA funciona a partir da aplicação da Congruência Modular, exibindo sua construção e funcionamento. Definição 1: Definimos a Função de Euler como sendo a função ϕ : N  N , onde ϕ(n)  ]{k Nk  n mdc(k, n)  1}. Definição 2: Sejam a, b  Z e n um inteiro positivo. Dizemos que a é congruente a b módulo n, e escrevemos a  b (mod n), se, e somente se, a b é múltiplo de n. Estas definições nos serão úteis para a construção da Criptografia RSA. Esta envolve um par de chaves: uma pública (que pode ser conhecida por todos) e uma privada (que deve ser mantida em sigilo). Toda mensagem cifrada usando uma chave pública só pode ser decifrada usando a respectiva privada. Escolhe-se dois números primos gigantescos, p e q, preferencialmente com mais de cem dígitos, e define-se N  p.q. Cada pessoa que utiliza o sistema escolhe um k  N, tal que mdc(k, ϕ(N)) 1, e então obtém-se a chave pública, que será (N, k), usada da seguinte forma:  [...]