Criptografia assimétrica com o RSA

Devido a dificuldade de troca de chaves, os algoritmos assimétricos são o principal motor de comunicações cifradas sobre SSL, como o HTTPS. De fácil compreensão, o RSA é um interessante método matemático que permite a cifra assimétrica baseado em números primos. E você pode brincar de RSA com a sua calculadora bc de linha de comando.

[ Hits: 179.419 ]

Por: Elgio Schlemer em 05/08/2009 | Blog: http://gravatai.ulbra.tche.br/~elgio


RSA passo a passo



E quase que o algoritmo recebeu o nome de ARS!

Ronald Rivest teve um momento de brilhantismo após uma grande quantidade de vinho e passou a noite de páscoa escrevendo um artigo científico sobre sua descoberta. Após terminar, como só chegara a este algoritmo após anos de trabalho junto com seus colegas, enumerou os autores em ordem alfabética: Adleman, Rivest, Shamir.

Adleman não concordou em ser citado como autor do artigo pois julgara que o trabalho maior fora de Rivest e, conforme confidenciou mais tarde, não considerava aquilo realmente algo brilhante. Após longa discussão e negociação, Adleman aceitou seu nome no trabalho, desde que fosse o último autor citado, nascendo assim o algoritmo mais conhecido da criptografia, batizado pelas iniciais de seus criadores Rivest, Shamir e Adleman, o RSA (O livros dos códigos, páginas 297 a 299).

O coração do RSA consiste na mesma função de mão única descoberta por Whitfield Diffie e Martin Hellman, a função modular. Novamente, assim como no algoritmo Diffie-Hellman, a segurança está no emprego de números realmente gigantes, hoje da ordem de 512 bits. Zelando pela compreensão, serão usados valores numéricos pequenos nesta demonstração, assim todos os leitores podem reproduzir facilmente em suas calculadoras de linha de comando, bc ou dc.

A primeira etapa do algoritmo RSA é a criação do par de chaves, a pública e a privada. Deixando Alice e Bob de lado, pois ninguém mais os aguenta, Luiza quer criar seu par de chaves.

Luiza cria seu par de chaves

Luiza começa escolhendo dois números primos, chamados de p e q, que mantém em segredo. Um número primo é aquele que não possui nenhum divisor, exceto 1 e ele mesmo. Luiza escolheu os números p=17, q=23.

Após Luiza calcula o produto destes dois números, chamado de n. No caso, n = p*q, sendo que n=17*23.

Agora Luiza computa o quociente de Euler, que nada mais é do que (p-1)*(q-1). Neste exemplo este valor será representado por qq.

Neste momento Luiza tem os seguintes números:

p = 17
q = 23
n = 391 (17 *23)
qq = 352 (16 * 22)

Luiza agora precisa encontrar um número e que seja primo relativo a qq. Um primo relativo é apenas aquele que não possui divisor em comum, ou seja, sendo qq=352 e possuindo vários divisores (352 possui 10 divisores: 2, 4, 8, 11, 16, 22, 32, 44, 88 e 176 ) qualquer número que não tenha nenhum destes divisores serve. Na prática se e for também um número primo, ou seja, não possuir divisor algum, ele será com certeza um primo relativo a qq. Assim qualquer número primo serve como e (de fato, o RSA atual fixa este número para todas as chaves, normalmente 65537).

Luiza decidiu ficar com o número 7 para e.

Agora vem a parte mais interessante do algoritmo. Luiza precisa encontrar um número d, que satisfaça a expressão (d*e) mod qq = 1, ou seja, um número d que ao se multiplicar por e, realizando o módulo com o quociente de Euler (qq), resulte em 1. Pode-se, para números pequenos, simplesmente escolher um d que sirva, mas isto não é uma boa ideia para números grandes. Contudo o número d pode ser calculado através de uma variação do teorema de Euclides, chamada de euclides estendido, para cálculo do máximo divisor comum. Uma implementação em C deste algoritmo pode ser encontrada em Algoritmo de euclides estendido (calcula o D RSA)

Luiza calculou o valor d=151, pois (151*7) mod 352 é realmente igual a 1, conforme você mesmo pode verificar com o seu bc:

echo "(151 * 7) % 352" | bc
1

Desta forma, Luiza possui os seguintes números:

p  =  17    escolhido aleatoriamente, desde que primo
q  =  23    escolhido aleatoriamente, desde que primo
n  = 391    pela operação p*q
qq = 352    pela operação (p-1) * (q-1)
e  =   7    que seja primo relativo a qq.
d  = 151    calculado pelo teorema de Euclides

Luiza agora precisa apagar e remover quaisquer vestígios de p, q e qq, mantendo apenas o e, d e o n (e aconselha-se escrever na memória várias vezes lixo nas variáveis que tem p, q e qq, a fim de que não fiquem vestígios dela nem mesmo na área de troca do sistema, o swap).

Luiza agora já tem o seu par de chaves, a saber:
  • Ke = (n, e), ou seja, Ke é a chave usada para cifrar (e de "encriptar") e deve ser tornada pública. Assim o "cadeado aberto" de Luiza será Ke = (391, 7).
  • Kd = (n, d), ou seja, Kd é a chave usada para decifrar (d de "decifrar") e deve manter-se em sigilo. Assim, a "chave" que abre o cadeado é Kd = (391, 151).

Chaves públicas de Luiza:

        Kd = (391, 151)             Ke = (391, 7)


Usando o RSA

Usar o RSA significa cifrar algo com a chave Ke e que somente quem tiver a chave Kd possa abrir. Quando me deparei com isto pela primeira vez, minha reação foi de ceticismo. Não é por menos, pois Clifford Cocks, matemático do serviço secreto GCHQ ficou igualmente cético e dedicou boa parte do seu precioso tempo para tentar provar que não funciona. Ele fracassou (GCHQ era o Quartel General de comunicações do Governo Britânico. Hoje se sabe que lá nasceu o RSA quatro anos antes de Diffie-Hellman terem descoberto a função de mão única).

Para cifrar uma mensagem para Luiza basta realizar a seguinte operação matemática:

C = Me mod N

O único cuidado que é necessário ter é que M, mensagem a ser cifrada, não pode ser maior do que o valor de N. Neste exemplo, considerando que N é 391, pegando-se apenas 8 bits da mensagem o valor numérico máximo que se pode ter é 255, ficando sempre menor do que N. Desta forma o algoritmo RSA pode ser considerado como um algoritmo de cifra de bloco e, neste caso, com um tamanho de bloco igual a oito bits (veja Criptografia chave simétrica de bloco e de fluxo).

Ainda está com a sua calculadora bc a postos?

Cifrando com o RSA

Fulano deseja enviar de forma cifrada a string "Amanha" para Luiza (sem acento no ã, para não entrar em detalhes sobre UTF-8 ou ISO8859-1). Fulano obteve a chave pública de Luiza, pois ela não é segredo:

Ke(Luiza) = (391, 7)

Então ele simplesmente divide a mensagem em blocos, cada bloco não maior do que 391, e cifra usando a expressão C = Me mod n, ou no caso, C = M7 mod 391:

  'A'      'm'      'a'      'n'      'h'      'a'
01000001 01101101 01100001 01101110 01101000 01100001
  65       109       97      110      104       97

Assim Fulano pode cifrar a mensagem para Luiza aplicando a expressão matemática em cada byte. Convido-o a reproduzir este cálculo em sua calculadora bc:

 657 mod 391 = 176 (execute: echo "( 65 ^ 7) % 391" | bc)
1097 mod 391 = 250 (execute: echo "(109 ^ 7) % 391" | bc)
 977 mod 391 = 109 (execute: echo "( 97 ^ 7) % 391" | bc)
1107 mod 391 = 236 (execute: echo "(110 ^ 7) % 391" | bc)
1047 mod 391 = 315 (execute: echo "(104 ^ 7) % 391" | bc)
 977 mod 391 = 109 (execute: echo "( 97 ^ 7) % 391" | bc)

Desta forma Fulano cifrou a palavra "Amanha" e chegou ao resultado 176, 250, 109, 236, 315 e 109. Estes valores cifrados serão transmitidos para Luiza que deverá ter condições de recuperar a mensagem.

Decifrando com o RSA

Luiza, ao receber a mensagem, usa a sua chave privada Kd, nunca divulgada, para recuperar a mensagem original.

Kd(Luiza) = (391, 151)

Para recuperar a mensagem, Luiza precisa executar a expressão M = Cd mod n, ou seja, M = C151 mod 391

Sinta-se novamente a vontade para reproduzir em seu Linux:

176151 mod 391 =  65 (execute: echo "(176 ^ 151) % 391"|bc)
250151 mod 391 = 109 (execute: echo "(250 ^ 151) % 391"|bc)
109151 mod 391 =  97 (execute: echo "(109 ^ 151) % 391"|bc)
236151 mod 391 = 110 (execute: echo "(236 ^ 151) % 391"|bc)
315151 mod 391 = 104 (execute: echo "(315 ^ 151) % 391"|bc)
109151 mod 391 =  97 (execute: echo "(109 ^ 151) % 391"|bc)

Luiza recuperou com sucesso os valores 65, 109, 97, 110, 104 e 97 que quando lidos como letras resultam na frase "Amanha".

Página anterior     Próxima página

Páginas do artigo
   1. Introdução
   2. A teoria dos algoritmos assimétricos
   4. RSA passo a passo
   5. Não frite seu processador
   6. Quebrando o RSA: um desafio para você valendo um livro
   7. Conclusão
Outros artigos deste autor

Estrutura do IPTables 2: a tabela nat

Guerra Infinita, uma análise da Ciência da Computação

Armazenamento de senhas no Linux

Estrutura do Iptables

A mágica do dc

Leitura recomendada

Sudo 1.8.12 - Parte II - Como sudo funciona

Importar Chave GPG

Gaim + Gaim Encryption - Bate-papo com segurança

Desligamento automático seletivo com apcupsd

Utilizando SSH com método de autenticação publickey + ssh-agend + ssh-add

  
Comentários
[1] Comentário enviado por cesar em 05/08/2009 - 14:34h

Nota 10!

parabéns elgio!

[]'s

[2] Comentário enviado por elgio em 05/08/2009 - 14:53h


VALENDO!

Valores de N publicados!
http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Desafio-1-RSA

[3] Comentário enviado por cesar em 05/08/2009 - 15:17h

@elgio

Fiquei interessado neste "teorema de Euclides e atalhos matemáticos para cálculo de módulo" tem como você me enviar este material por e-mail? não sei se pode mandar por causa do desafio, mas quando concluir o desafio tú me manda?
meu e-mail é [email protected]

[]'s

[4] Comentário enviado por elgio em 05/08/2009 - 15:33h

O teorema de euclides é uma pequena variação da fórmula para cálculo do máximo divisor comum. Está publicado no meu site e o link é fornecido no artigo.

Quanto ao atalho matemático, claro. Mas depois. com o tempo. Também teria as explicações dos 3 testes de primaridade. não sou matemático, mas sou curioso. Corri muito atras de alguns conceitos para poder entender e até mesmo ACREDITAR no RSA :-D

Estou escrevendo um NOVO artigo sobre linguagens que irá ajudar MUITO a quebrar o N. Mas este eu vou segurar para publicar depois.

[5] Comentário enviado por fernandoborges em 06/08/2009 - 13:13h

Prof. Elgio, parabéns pelo rigor com que tratou o assunto. Mesmo sendo formado em Matemática, ainda me faltavam alguns conceitos que relacionassem Teoria dos Numeros e Criptografia Assimétrica. Comecei uma Pós nesse ramo em 2007, mas infelizmente tive que trancar. Seu artigo me remeteu ao OpenVPN, que aliás, é uma das minha ferramentas em meu trabalho atual. O Sr poderia fazer uma análise da segurança implementada no OpenVPN com certificados X509 à luz de seu conhecimento sobre criptografia?

[6] Comentário enviado por elgio em 06/08/2009 - 13:57h

Fernando:

Não importa qual programa, nenhum deles usa algoritmos Assimétricos para cifrar!

Os assimétricos, como o RSA ou o DSA são computacionalmente inviáveis, devido ao esforço matemático exigido. Um processador não daria conta de cifrar um download de um CD Iso, por exemplo.

TODOS ELES usam algoritmos SIMÉTRICOS, por serem bons e rápidos.

Olhando o man do openvpn vi que ele prefere usar o algoritmo simétrico blowfish em modo CBC (Cipher-Block Chaining, ou seja, como um algoritmo de bloco encadeando-os para evitar repetição).

Mas como toda boa ferramenta profissional, o OpenVPN suporta diversos algoritmos (execute openvpn --show-ciphers para ter uma listagem do seu).

Assim, a segurança dos dados em tráfego dependem do algoritmo e do tamanho da chave. O menor deles, ma minha versão de openvpn, é o DES com 64 bits que já está fraquinho. Usar ele pode significar estar fragilizado.

O Blowfish padrão usa 128 bits que está MUITO, mas MUITO BOM (o pessoal acha que é pouco já que o RSA deve ser de, pelo menos, 1024. Mas são princípios matemáticos distintos: http://www.vivaolinux.com.br/artigo/Introducao-a-criptografia cap 6)

Bom, mas onde entra o certificado e a criptografia assimétrica?

Quando cliente e servidor negociam, há uma troca de certificados. Um certificado tem muitas informações, incluindo a chave pública, podento estar assinado por uma certificadora.

Um certificado usa diversos algoritmos:
- RSA ou algum outro assimétrico: esta chave deve ser de pelo menos 1024 bits. Menos que isto é perigoso

- HASH: Pra as assinaturas digitais. Não convém mais usar o MD5 por conta das colisões descobertas. O bam bam bam de agora é o SHA1

Ocorre que no início cliente e servidor CRIAM uma chave de sessão de 128 bits para ser usado pelo simétrico (no caso o blowfish). Podem fazer isto usando o protocolo Diffie-Hellman. Esta negociação irá precisar de algumas mensagens, TODAS CIFRADAS PELO RSA (e gastando CPU!).

Mas são só estas poucas, pois assim que uma chave de sessão é trocada, abandonam o lentérrimo RSA e usam o "rapidésimo" simétrico (blowfish no exemplo).

Então, caro amigo, o openssl é sim EXTREMAMENTE SEGURO se observadas algumas coisas:

a) que se use algoritmos bons. O padrão que vem nele está "da hora"
b) que se usem certificados bons, sem MD5 de preferência
c) que se use uma chave forte RSA, se for o caso, de, pelo menos, 1024 bits


[7] Comentário enviado por elgio em 07/08/2009 - 10:01h

VALENDO!

Valores de N publicados!
http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Desafio-1-RSA

[8] Comentário enviado por fernandoborges em 08/08/2009 - 16:34h

Prof. Elgio,
Quero agradecê-lo pela rápida abordagem sobre o OpenVPN. Muito esclarecedor pra mim. Será de grande valia para que eu possa avaliar melhor a segurança dos dados que trafegam na minha VPN.
Cordiais saudações,
Fernando.

[9] Comentário enviado por marcelogpl em 09/08/2009 - 01:32h

Parabéns Professor!

Realmente um artigo muito interessante e claro nos conceitos utilizados, vai ajudar muito em projetos onde um dos focos é a segurança.

Obrigado

[10] Comentário enviado por elgio em 12/08/2009 - 16:52h

Novo desafio postado.

ESTE VALE UM LIVRO!
http://www.vivaolinux.com.br/topico/Seguranca-Da-Informacao/Desafio-2-RSA

[11] Comentário enviado por elgio em 13/08/2009 - 10:08h

Ontem pela manhã removi o link do artigo que remetia para o cálculo do D em C. Ele não funcionava para todos os casos. Agora eu REFIZ o código e voltei a citar o código em C no artigo. Esta versão, em C, FUNCIONA e corretamente calcula qualquer valor de D, mas só se ele estiver dentro da capacidade da ULA. Necessário para GANHAR O LIVRO do desafio.

Ah, mas com este código não dá para quebrar todos os D?

Ora, modifique ele: http://www.vivaolinux.com.br/artigo/Programacao-com-numeros-inteiros-gigantes/

[12] Comentário enviado por Lisandro em 10/06/2010 - 07:04h

Ótimo Artigo. Parabéns!

[13] Comentário enviado por rafatmb em 23/11/2010 - 17:23h

Excelente documentação sobre o assunto. Informações fundamentais para todos os administradores de rede linux.

um bom material de apoio em: http://cseweb.ucsd.edu/~mihir/papers/oae.pdf

Acho importante sabermos a história das coisas, e de onde vieram as soluções que hoje fazem parte do dia a dia. Muitas vezes, usamos tanto, que nem atribuimos a devida importante para as ferramentas, e deixamos também de reconhecer aqueles que passaram tanto tempo estudando e desenvolvendo a tecnologia.

Abraço a todos!

Rafael Marangoni
LPIC/1/2/3 - Expertise em Servidor Linux
http://www.brlink.com.br



[14] Comentário enviado por uberalles em 01/12/2010 - 01:28h

Grande e excelentíssimo Professor. Que pena que só encontrei este artigo agora.. há dois meses atrás, por volta de outubro, tive que fazer um programa em C, com API MySQL para tratar senhas e tals e acabei usando a função ENCODE() e DECODE() do próprio MySQL, sendo que queria ter feito em C. talvez eu reveja e refaça uma nova versão, mas a que tenho hoje está muito boa.

Um abraço e muito obrigado.
.

[15] Comentário enviado por DavidsonDFGL em 26/07/2012 - 22:13h

Poxa, de longe o melhor artigo de RSA que já li na internet, tanto que até tive vontade de implementar algo simples em C, mas me veio uns problemas:

o programa gerou aleatoriamente
p = 5
q = 11
e = 7
o n 55
o qq 40
e o d deu 23
acontece que quando cifro o número 10 por ex, o resultado é 10 também, e decifrado vira 18.
Isso seria uma infeliz coincidência, ou tem algo de muito errado com estes valores? confesso que já vi e revi estes valores e aparentemente estão certos, :(

[16] Comentário enviado por sk4d1nh4 em 26/11/2012 - 17:02h


[17] Comentário enviado por DavidsonDFGL em 26/07/2012 - 22:13h:

Poxa, de longe o melhor artigo de RSA que já li na internet, tanto que até tive vontade de implementar algo simples em C, mas me veio uns problemas:

o programa gerou aleatoriamente
p = 5
q = 11
e = 7
o n 55
o qq 40
e o d deu 23
acontece que quando cifro o número 10 por ex, o resultado é 10 também, e decifrado vira 18.
Isso seria uma infeliz coincidência, ou tem algo de muito errado com estes valores? confesso que já vi e revi estes valores e aparentemente estão certos, :(


Caro DavidsonDFGL,

acredito que tenha alguma coisa errada no seu "C". Decifrando o 10 com esses números da 10 mesmo. Faça o teste. echo (10^23)%55 | bc

[17] Comentário enviado por fabinhotfj em 21/02/2013 - 20:55h

Parabéns pelo seu artigo


[18] Comentário enviado por dougaslinux em 01/10/2013 - 00:19h

Olá, Ótimo poste!

Se alguem poder me confimar alguns sistemas que utilizam a criptografia RSA , ficarei muito grato!

[19] Comentário enviado por reinaldobatista em 15/07/2014 - 13:16h

Excelente! Parabéns! Bravo!


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts