Publicações Artigos, teses, monografias, reportagens, etc... %!preproc: "SITEPATH" ".." %!includeconf: ../config.t2t %!postproc: "SITEPATH" ".." %!include: SITEPATH/menu.t2t = Introdução à Criptografia RSA = == Histórico == Encaminhar uma mensagem de forma segura é uma preocupação que remonta aos primeiros estrategistas que se têm notícia, na Grécia Antiga. [SITEPATH/imagens/maquina_enigma.jpg] 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. Com o passar dos anos, a evolução da Matemática e a critatividade humana em desenvolver novos mecanismos fez com que a arte cifrar mensagens grande destaque nas decisões políticas, com influência direta nos acontecimentos históricos. 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 http://pt.wikipedia.org/wiki/M%C3%A1quina_Enigma], capaz de gerar mensagens criptografadas com enorme facilidade. A preocupação com a guarda das informações é a base da [Criptografia http://pt.wikipedia.org/wiki/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 **R**ivest, Adi **S**hamir e Leonard **A**dleman, 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: + 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. As figuras a seguir, extraídas do site da [Wikipédia http://pt.wikipedia.org], ilustram bem a dinâmica de uso de chaves públicas e privadas. | [SITEPATH/imagens/250px-Asymetric_cryptography_-_step_1.svg.png] | | Alice envia sua chave pública para todos, inclusive Bob. | | [SITEPATH/imagens/250px-Asymetric_cryptography_-_step_2.svg.png] | | Bob cifra a mensagem com a chave pública de Alice e a envia. | | Alice, por sua vez, recebe o texto criptografado e o decifra {{br}} utilizando sua chave privada. | == 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 {{br}} 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 {{br}} Z = (P - 1) * (Q - 1) No caso obtêm-se como resultado: N = 17 * 11 = 187 {{br}} Z = 16 * 10 = 160 Agora define-se um número **D** que tenha a propriedade de ser **//primo em relação à Z//**. Pode-se escolher qualquer número que satisfaça essa propriedade. Nesse exemplo, visando simplificação dos cálculos, 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 {{br}} E = 2 => (2 * 7) mod 160 = 14 {{br}} E = 3 => (3 * 7) mod 160 = 21 {{br}} .{{br}} .{{br}} .{{br}} E = 23 => (23 * 7) mod 160 = 1{{br}} .{{br}} .{{br}} .{{br}} E = 183 => (183 * 7) mod 160 = 1{{br}} .{{br}} .{{br}} .{{br}} E = 343 => (343 * 7) mod 160 = 1{{br}} .{{br}} .{{br}} .{{br}} E = 503 => (503 * 7) mod 160 = 1{{br}} .{{br}} .{{br}} .{{br}} 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 187 {{br}} TEXTO CRIPTOGRAFADO = 70.368.744.177.664 mod 187 {{br}} TEXTO CRIPTOGRAFADO = 64 Para desencriptar: TEXTO RECEBIDO = 64 TEXTO ORIGINAL = (64 ^ 7) mod 187 {{BR}} TEXTO ORIGINAL = 4.398.046.511.104 mod 187 {{br}} 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 | %!postproc(html): '("maquina_enigma.jpg.*?alt=")' '\1 Uma foto da máquina enigma. Fonte Wikipédia.' %!postproc(html): '("maquina_enigma.jpg BORDER="0" ALT=")' '\1 Uma foto da máquina enigma. Fonte Wikipédia.">' %!postproc(html): '("250px-Asymetric_cryptography_-_step_1.svg.png.*?alt=")' '\1 Alice envia sua chave para Bob.' %!postproc(html): '("250px-Asymetric_cryptography_-_step_2.svg.png.*?alt=")' '\1 Bob escreve uma mensagem para Alice, criptografa com a chave pública de A.lice e esta acessa o conteúdo original pela sua chave privada.' %!include: SITEPATH/rodape.t2t