[Dicas-L] Introducao a Criptografia RSA
Introdução à Criptografia RSA
Data de Publicação: 11 de Junho de 2007
Encaminhar uma mensagem de forma segura é uma preocupação que remonta aos primeiros estrategistas que se têm notícia, na Grécia Antiga.
Houve época em que soldados tinham mensagens escritas em seu couro cabeludo como estratégia para transpassar uma informação pelas linhas inimigas, bastando chegar ao seu destino e ter sua cabeça raspada.
Na Segunda Guerra Mundial, a Alemanha dispunha de um intrincado sistema de informações criptografadas. A base de todo esse sistema era uma máquina eletro-mecânica conhecida como enigma, semelhante à apresentada na figura, capaz de gerar mensagens criptografadas com enorme facilidade.
A preocupação com a guarda das informações é a base da Criptografia, essencial para o tráfego de informações, especialmente nos dias atuais.
Um dos algoritmos mais seguros de encriptação de informações atuais originou-se dos estudos de Ronald Rivest, Adi Shamir e Leonard Adleman, um trio de Matemáticos brilhantes que mudaram a história da Criptografia.
O princípio do algoritmo é construir chaves públicas e privadas utilizando números primos.
Uma chave é uma informação restrita que controla toda a operação dos algoritmos de criptografia. No processo de codificação uma chave é quem dita a transformação do texto puro (original) em um texto criptografado.
É uma informação pessoal que permanece em posse da pessoa - não publicável.
Informação associada a uma pessoa que é distribuída a todos.
Uma analogia amplamente conhecida no meio acadêmico é a transmissão de mensagens entre Alice e Bob.
Alice e Bob são personagens fictícios que precisam trocar mensagens seguras sem interceptação. O algoritmo RSA permite essa troca segura de mensagens pela utilização de chaves públicas e privadas:
Alice cria seu par de chaves (uma pública e outra privada) e envia sua chave pública para todos, inclusive Bob;
Bob escreve sua mensagem para Alice. Após escrita, Bob faz a cifragem do texto final com a chave pública de Alice, gerando um texto criptografado;
Alice recebe o texto criptografado de Bob e faz a decifragem utilizando a sua chave privada.
O procedimento é realizado com sucesso porque somente a chave privada de Alice é capaz de decifrar um texto criptografado com a sua chave pública.
É importante destacar que se aplicarmos a chave pública de Alice sobre o texto critografado não teremos a mensagem original de Bob. Dessa forma, mesmo que a mensagem seja interceptada é impossível decifrá-la sem a chave privada de Alice.
Conforme mencionado, o algoritmo RSA é baseado na construção de chaves públicas e privadas utilizando números primos. Inicialmente devem ser escolhidos dois números primos quaisquer P e Q. Quanto maior o número escolhido mais seguro será o algoritmo.
A título de exemplificação, serão escolhidos números primos pequenos, para permitir um acompanhamento de todo o processo de cifragem e decifragem.
A seguir são calculados dois novos números N e Z de acordo com os números P e Q escolhidos:
No caso obtêm-se como resultado:
N = 17 * 11 = 187
Z = 16 * 10 = 160
Agora define-se um número D que tenha a propriedade de ser primo em relação à Z. No caso, opta-se pela escolha:
De posse desses números começa o processo de criação das chaves públicas e privadas. É necessário encontrar um número E que satisfaça a seguinte propriedade:
Se forem feitos os testes com 1, 2, 3... teremos:
E = 1 => (1 * 7) mod 160 = 7
E = 2 => (2 * 7) mod 160 = 14
E = 3 => (3 * 7) mod 160 = 21
E = 23 => (23 * 7) mod 160 = 1
E = 183 => (183 * 7) mod 160 = 1
E = 343 => (343 * 7) mod 160 = 1
E = 503 => (503 * 7) mod 160 = 1
Logo até o momento os números 23, 183, 343, 503 satisfazem a propriedade indicada.
Para efeito de simplificação de cálculos, será tomado como referência:
E = 23.
Com esse processo definem-se as chaves de encriptação e desencriptação.
para encriptar: utilizar E e N - esse par de números será utilizado como chave pública.
para desencriptar: utilizar D e N - esse par de números utilizado como chave privada.
TEXTO CRIPTOGRAFADO = (TEXTO ORIGINAL ^ E) mod N
TEXTO ORIGINAL = (TEXTO CRIPTOGRAFADO ^ D) mod N
Caso prático para o exemplo
Seja a necessidade de se encaminhar uma mensagem bem curta de forma criptografada, como o número 4 por exemplo, tendo por base as chaves aqui estabelecidas.
Para criptografar:
TEXTO ORIGINAL = 4
TEXTO CRIPTOGRAFADO = (4 ^ 23) mod 39
TEXTO CRIPTOGRAFADO = 70.368.744.177.664 mod 39
TEXTO CRIPTOGRAFADO = 64
TEXTO RECEBIDO = 64
TEXTO ORIGINAL = (64 ^ 7) mod 39
TEXTO ORIGINAL = 4.398.046.511.104 mod 39
A questão das escolhas dos números primos envolvidos é fundamental para o algoritmo. Por essa razão escolhem-se números primos gigantescos para garantir que a chave seja inquebrável.
Assim como o exemplo apresentado, existem outras combinações que podem ser feitas rapidamente para confirmação, sem que se exija uma aplicação especial para os cálculos envolvidos.