Criptografia em RSA - O Algoritmo mais usado atualmente

Nessa postagem falaremos do RSA, o mais usado algoritmo de criptografia assimétrica atualmente, mostrando um pouco como ele funciona e dando exemplos bem simples.

O RSA foi inventado em 1977 pelos professores do MIT: Ronald L. Rivest, Adi Shamir, e Leonard Adleman que controlavam a empresa RSA Security. Essa empresa é a detentora da patente do algoritmo RSA nos EUA. Mas se restringe a esse país, não se aplicando a outros que desenvolvam programas que usem o RSA, o que permite que o usemos livremente.

O RSA é usado para envio de informação de forma segura usando uma chave pública e uma privada (criptografia assimétrica). Um exemplo seria eu mandar uma mensagem criptografada por mim para um amigo. Se eu usasse uma criptografia de uma chave única privada para isso, teria de enviar para meu amigo a chave que usei na criptografia de forma segura, o que é um grande problema nesse tipo de comunicação. A criptografia simétrica não resolveria esse caso e o RSA é um dos algoritmos de chave assimétrica que resolveriam esse problema como mostra a imagem abaixo.

Desta forma eu não precisaria enviar minha chave para meu amigo, o que é uma vantagem, porém seriam necessárias 3 viagens e eu não estaria criptografando a mensagem diretamente, mas sim o "recipiente que a envolveu", nesse caso do exemplo a "caixa com os cadeados".

RSA e seu funcionamento

RSA é um algoritmo de criptografia assimétrica, então usa duas chaves: uma pública e uma privada, onde a pública pode ser distribuida livremente para que qualquer remetente possa usa-la para me enviar uma mensagem criptografada, mas só sendo possivel descriptografá-las com minha chave privada que é guardada comigo em segredo.

Seguindo com essa idéia, para eu enviar uma mensagem para meu amigo, como no exemplo anterior, eu só precisaria enviá-la usando a chave pública dele e somente ele poderia abrí-la usando sua chave privada guardada com ele em segredo.

Esse algoritmo se baseia na teoria dos números, uma clássica área matemática, e se fundamenta na dificuldade em fatorar um número em seus componentes primos (números divisíveis por eles mesmos e pelo número 1 numa divisão exata e sem restos).

"Apesar dessa função ser inversível, se multiplicarmos números primos muito grandes, a quantidade de números que precisaremos testar para descobrir a entrada vai ser tão grande, que torna esse trabalho impraticável. Por isso, para que essa função seja segura, devemos estar certos de que os dois números escolhidos são realmente primos e que sejam números muito grandes. Por exemplo, quando dizemos que estamos trabalhando com uma chave de 1024 bits no RSA, isso quer dizer, que a chave pública tem 1024 bits, ou seja, precisamos de 1024 bits para representar o número que foi gerado pela multiplicação dos dois primos, portanto cada número primo deveria ter 512 bits.
Para se ter uma ideia, um número de 1024 bits é da ordem de 1 x 10^308 na representação decimal, imagine quantos números antes desse devemos testar para encontrar os dois números primos que o geraram!!! Com o computador que está na sua frente agora, você levaria mais tempo do que a idade do universo para conseguir fatorar esse número, heheheh que exagero..."

Para isso temos de nos lembrar como descobrir fatores primos de um número e para facilitar abaixo segue um vídeo, do Youtube postado por Vinicius Silva, que nos ajudará a entender como funciona a matemática por trás do RSA, e que não há magia nenhuma nisso. 

O vídeo é bem prático e explicativo mostrando o passo-a-passo da matemática que fundamenta o RSA e me ajudou bastante a compreender esse algoritmo criptográfico, espero que ajude a todos da mesma forma e como diz no fim do vídeo por enquanto "that's all folks" (isso é tudo pessoal).

Referências

Postagens de:

blog.lambda3.com.br

Blog 0fx66

Imagem editada de http://blog.lambda3.com.br/2012/12/entendendo-de-verdade-a-criptografia-rsa/

Conteúdo sobre a patente do RSA em http://www.cyberlaw.com/rsa.html

Citação retirada de http://0fx66.com/blog/criptografia-rsa-algoritmos-e-implementacoes/

Vídeo postado por Vinicius Silva retirado de Aprendendo o RSA - Criptografia 

De onde e para quê surgiu a Criptografia Assimétrica?

Numa postagem anterior já definimos criptografia e o porquê de encripitar, então vamos complementar a definição de Criptografia Assimétrica mostrando de onde surgiu essa necessidade e qual problema veio solucionar.

Já sabemos que a Criptografia oculta o significado de uma mensagem, usa recursos matemáticos para isso e é utilizada por motivos de privacidade ou ocultação de informação. Mas vamos ver brevemente como foram os primórdios de sua aparição na antiguidade apenas por caráter ilustrativo antes de diferenciar Simétrica de Assimétrica. 

Ela foi usada na antiguidade, principalmente em guerras para que inimigos não descobrissem informações estratégicas mesmo em casos de interceptação. 

"O primeiro uso documentado da criptografia foi em torno de 1900 a.c., no Egito, quando um escriba usou hieróglifos fora do padrão numa inscrição.Entre 600 a.c. e 500 a.c., os hebreus utilizavam a cifra de substituição simples (de fácil reversão e fazendo uso de cifragem dupla para obter o texto original), sendo monoalfabético e monogrâmica (os caracteres são trocados um a um por outros), e com ela escreveram o Livro de Jeremias."[1]

Uma das técnicas mais clássicas de criptografia é a substituição e um exemplo que enganou muitos inimigos do Império Romano foi o "Codificador de Júlio César", que simplesmente substituía as letras do alfabeto avançando três casas e obviamente perdeu sua funcionalidade após ter a chave descoberta, como toda técnica de criptografia.

"A criptografia existe desde a antiguidade, e estava altamente associada a atividades militares e diplomáticas. Considerada por muitos como uma ciência ou até mesmo arte, tem como objetivo principal disfarçar a informação através de processos de codificação, e de repor essa mesma informação no seu estado original através de processos de descodificação."[2]

Enquanto a criptografia estuda os métodos usados na proteção da informação existe por outro lado um estudo das técnicas que permitem quebrar um algoritmo criptográfico denominado criptoanálise e a soma desses estudos é o estudo da criptologia.

"Atualmente, os dois protocolos mais usados para proteção de dados na Internet, o SSL (Secure Sockets Layer) e o TLS (Transport Layer Security) utilizam a criptografia simétrica para proteger os dados transmitidos e armazenados. No entanto, a criptografia simétrica possui um desafio importante e impossível de ser resolvido. Como combinar uma chave secreta entre duas pessoas que querem se comunicar através da Internet? Essa pergunta não teve solução até a década de 1970 e não foi na criptografia simétrica que a solução foi encontrada". [1]

Diferenças Básicas entre criptografias Simétrica e Assimétrica.

 Algoritimos que usam a criptografia simétrica, ou de chave secreta, tendem a ser mais rápidos, uma vez que a chave usada é compartilhada entre as várias máquinas, no entanto não são tão seguros quanto os que usam criptografia assimétrica. Uma única chave para criptografar e descriptografar é compartilhada entre o emissor da informação e o receptor. DES , 3DES , AES e RC4 são alguns dos algoritmos que usam criptografia simétrica. Para garantir a confidencialidade de informações quando armazenada, tanto na origem como no destino e a atividade de fazer compras on-line são exemplos que utilizam desses tipos de algoritimos.

Já os algoritimos que usam a criptografia assimétrica, ou de chave pública, usam um par de chaves distintas onde uma chave pública é usada para criptografar e uma chave privada é usada para descriptografar. Eles tendem a ser mais lentos exigindo mais recursos do computador, mas compõe um método muito bom para garantir segurança em um canal público e inseguro como a Internet. Apenas a chave pública é compartilhada entre o emissor e receptor, e a chave privada é usada para decifrar a toda a informação. Gnupg ,PGP e RSA são exemplos de algoritmos assimétricos e o uso de e-mails é um exemplo de atividade que usa esse tipo de criptografia.

[1] Retirado de Matéria completa: http://corporate.canaltech.com.br/o-que-e/seguranca/Criptografia-voce-deveria-conhecer/#ixzz39YwGOIjp

[2] Retirado de http://escreveassim.com.br/2010/12/08/criptografia-simetrica-e-assimetrica/

O que é Criptografia Assimétrica?

Para começar a responder essa pergunta, é necessário primeiro explicar o porquê é preciso criptografar os dados.

A criptografia tem o objetivo de esconder informação de acesso não autorizado. Ela é usada Quando se pretende preservar os valores de uma senha, do conteúdo de uma mensagem, dos dados de um HD etc. As técnicas mais utilizadas usam o conceito de chave, convertendo toda mensagem a partir de um conjunto especifico de bits.

A criptografia assimétrica faz referencia a uma dessas técnicas de chave, ela trabalha com duas chaves distintas que se complementam. Uma das chaves é publica e outra privada. Numa troca de informações a chave publica é disponibilizada ao emissor, dessa forma ele poderá ocultar a mensagem, com os dados codificados a mensagem só poderá ser decodificada com a chave privada do remetente.

Figura-1: Exemplo de criptografia assimétrica

Um dos algoritmos mais utilizados é o RSA (Rivest, Shamir and Adleman), foi criado no MIT( Massachusetts Institute of Technology). O RSA utiliza números primos para criar suas chaves, basicamente é usado dois números primos grandes, a multiplicação dos números se torna a chave publica, a chave privada fica sendo os números originais. Os números primos tem como característica serem divididos apenas por eles mesmos e por 1. Dessa forma, encontrar números primos é demasiadamente custoso computacionalmente. Vale lembrar ainda que essa é uma solução de segurança independente do poder de processamento das maquinas, para processadores mais rápidos basta alcançarmos números primos significativamente maiores.

Referências:
http://www.techtudo.com.br/artigos/noticia/2012/06/o-que-e-criptografia.html
http://www.infowester.com/criptografia.php
Figura1:http://packetlife.net/blog/2010/nov/23/symmetric-asymmetric-encryption-hashing/