você está aqui: Home  → Arquivo de Mensagens

Introdução à Criptografia RSA

Colaboração: Daniel Darlen

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.

O algoritmo RSA

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.

Chave Privada
É uma informação pessoal que permanece em posse da pessoa - não publicável.

Chave Pública
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:

  1. Alice cria seu par de chaves (uma pública e outra privada) e envia sua chave pública para todos, inclusive Bob;
  2. 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;
  3. 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.

Funcionamento

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.

  • P = 17
  • Q = 11

    A seguir são calculados dois novos números N e Z de acordo com os números P e Q escolhidos:
  • N = P * Q
  • Z = (P - 1) * (Q - 1)

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:

  • D = 7

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:

  • (E * D) mod Z = 1

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.

As equações são:

  • 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

Para desencriptar:

  • TEXTO RECEBIDO = 64

  • TEXTO ORIGINAL = (64 ^ 7) mod 39
  • TEXTO ORIGINAL = 4.398.046.511.104 mod 39
  • TEXTO ORIGINAL = 4

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.

P Q D E
11 17 7 23
5 7 11 35
3 13 7 31
3 13 7 7
3 5 17 9

Fonte: www.darlen.eti.br



 

 

Veja a relação completa dos artigos de Daniel Darlen

Opinião dos Leitores

DavidsonDFGL
09 Out 2013, 22:18
Olá agente,o D foi escolhido aleatoriamente, e "ser primo em relação a Z" é o D não ser um dos divisores comuns de Z, no caso 160, obviamente, qualquer D que você venha a escolher que seja primo, concerteza não é primo em relação a Z, XD
agente
09 Out 2013, 17:45
Ainda não entendi como vc chegou ao numero 7 de D. O que é um número "primo em relação a Z" ???
Narciso
10 Set 2012, 11:01
Quer dizer, 187
Narciso
02 Set 2012, 15:06
Só corrigindo... no final não é mod 39, é mod 189
Davidson
21 Jul 2012, 14:03
Poxa, adorei o texto, esse site foi um dos poucos que além de explicar muito bem a parte conceitual, ainda explica a aplicação do mesmo, perfeito. Só gostaria de perguntar como ficaria essa criptografia sendo aplicada a letras ao invés de numeros?
fabio
15 Out 2011, 08:38
Ola Daniel, muito bom esse seu artigo,queria que vc me ajuda-se, tenho que entregar um algoritmosimples de criptografia em 128bits e não sei por onde começo vc tem uma idea pra me ajudar.Se tiver muito obrigado.
Vailton Renato
31 Jan 2011, 11:27
Olá Daniel, gostei muito este artigo e achei-o bacana a sua explicação. Gostaria de deixar aqui 2 comentários que espero que ajude: o primeiro é sobre um erro no calculo envolvendo a criptografia e descriptografia do texto onde é aplicado um "mod 39" quando o correto seria um "mod 187" (valor correto da variavel N citada no exemplo acima) e outra informação que achei interessante, mas não foi citada, é no trecho onde se menciona que D deve ser um "primo em relação à Z"... ou seja, o que seriam "números primos entre si"?

Pesquisando na web achei outros artigos sobre este assunto e também a explicação de que "números primos entre si, são os números que tem apenas o número 1 igual na decomposição de sua divisão".

Com estas dicas e seu artigo, consegui implementar com êxito tal algoritmo para efeito de estudos.
gui
11 Out 2010, 06:44
gostei de explicacao , mas agradecia que exemplificasse com um algoritimo
*Nome:
Email:
Me notifique sobre novos comentários nessa página
Oculte meu email
*Texto:
 
  Para publicar seu comentário, digite o código contido na imagem acima
 


Powered by Scriptsmill Comments Script