Criptografia Numaboa

Algoritmo RSA *

Os bastidores

Noções de Aritmética

A mecânica do algoritmo RSA

Segurança e Velocidade

Confira a cifra

Algumas dicas

1. Escolha de dois números primos gigantes

2. Cálculo da chave pública

3. Cálculo da chave privada

4. Publicação da chave

5. Cifrar uma mensagem

6. Decifrar a mensagem

Fontes

Sab

Out

2005

20:29

(133 votos, média 4.82 de 5)

Detalhes: Categoria: Chave Pública; Atualização: Domingo, 14 Junho 2009 12:10; Autor: vovó Vicki; Acessos: 56080

O RSA é um algoritmo de chave pública idealizado por Ron Rivest, Adi Shamir e Leonard Adleman. O nome do algoritmo deriva das iniciais dos sobrenomes dos autores. Desde 1977, Diffie, Hellman e Merkle são considerados os inventores do conceito do algoritmo assimétrico e, desde 1978, Rivest, Shamir e Adleman são admirados por terem criado a implementação mais perfeita da criptografia de chave pública.

Ron Rivest

Como era o trio de pesquisadores do Laboratório de Ciência da Computação do MIT em 1976? Ron Rivest é um jovem cientista da computação, dono de uma curiosidade científica insaciável e de uma imensa capacidade de absorver e aplicar novas idéias. Assim que leu o trabalho publicado por Diffie, Hellman e Merkle, ficou obcecado pelo assunto e passou a procurar sem descanso uma função matemática que pudesse transformar a idéia dos três criptólogos num sistema real e viável. Além disso, Rivest acabou "contaminando" um colega, Adi Shamir, também cientista da computação. Shamir, conhecido pelo seu intelecto brilhante, mordeu a isca. Os dois conjecturavam insistentemente à procura de uma cifra assimétrica produzindo teorias mirabolantes que, uma após a outra, eram contestadas pelo terceiro colega, Leonard Adleman. Depois de quase um ano de brainstorming, Adleman, um matemático calmo e detalhista, estava ganhando de mil a zero, pois, até então, todas as sugestões de Rivest e Shamir tinham falhas imperdoáveis.

Adi Shamir

A esperança estava quase se esgotando quando Rivest, no meio de uma noite de insônia, lembrou-se de uma particularidade da matemática. Era muito simples e provavelmente havia tomado conhecimento do assunto quando ainda estava na escola primária: a fatoração. Multiplicar dois números primos é uma questão de segundos mas, se temos apenas o resultado e quisermos encontrar os números primos (fatores) deste resultado, o processo é bem mais demorado. À medida que multiplicamos números primos cada vez maiores, o tempo gasto para fatorar o resultado aumenta exponencialmente. Talvez esta função fosse a resposta tão procurada!

A noite foi definitivamente de insônia. Rivest escreveu até o romper do dia e, logo de manhã, foi procurar seu "advogado do diabo". Adleman, acostumado com as explosões intelectuais do amigo, começou a ler o texto preparando-se para encontrar defeitos. Leu, releu e, para o espanto dos dois, não havia nada para ser contestado. Nascia o primeiro algoritmo de chave pública, a primeira cifra assimétrica perfeitamente acabada.

Leonard Adleman

Mais uma curiosidade: Rivest havia batizado o algoritmo de ARS, colocando as iniciais do sobrenome do trio pesquisador em ordem alfabética. Adleman protestou porque achava que tinha contribuído pouco e porque não via futuro algum na publicação do trabalho. Pediu inclusive que seu nome fosse retirado. Rivest, ciente da importância do papel desempenhado por cada um, pediu que Adleman pensasse melhor no assunto e desse a sua resposta no dia seguinte. Não querendo magoar os amigos, Adleman concordou que seu nome fosse citado em último lugar, motivo pelo qual a cifra foi rebatizada e passou a ser chamada de RSA.

Os conhecimentos necessários para entender o RSA são básicos. Antes de mais nada, é preciso lembrar que um número primo é um número diferente de 1 que só é divisível exatamente por 1 ou por ele mesmo. Assim, 3 é um número primo porque só tem uma divisão exata quando dividido por 1 ou por 3. Já o número 4 não é primo porque pode ser dividido exatamente por 1, 2 e 4. Se o número 4 não é um número primo, então pode ser fatorado, ou seja, pode-se encontrar os números primos que, multiplicados, resultam em 4 (no caso, 2 x 2).

Existem alguns números conhecidos como primos entre si. Dois números inteiros são ditos primos entre si quando não existir um divisor maior do que 1 que divida ambos. Isto significa que o máximo divisor comum dos primos entre si é igual a 1.

Outro conceito necessário á a aritmética modular. Na aritmética modular não dispomos de uma quantidade infinita de números, mas de um grupo finito deles. O melhor exemplo é o mostrador do relógio que, por sinal, trabalha no módulo 12. Quando o mostrador passa do 12, não tem como mostrar 13 horas porque o conjunto dos números disponíveis vai de 1 a 12. Desta forma, 12 horas + 1 hora = 1 e 9 horas + 8 horas = 5. Costuma-se escrever estas operações da seguinte forma: 12 + 1 = 1 (mod 12) e 9 + 8 = 5 (mod 12).

O modo de se encontrar um resultado modular é dividindo o resultado não modular pelo módulo e considerar o resto. Por exemplo, 9 + 8 = 17 e 17 ÷ 12 = 1 com resto 5. Da mesma forma, 11 x 9 (mod 13) é 11 x 9 = 99 e 99 ÷ 13 = 7 com resto 8, ou seja, 11 x 9 = 8 (mod 13). Podemos complicar um pouco as coisas e considerar uma potenciação. Digamos que a base seja 3 e que este número seja elevado a um número qualquer que chamaremos de x. Para analisar o comportamento da função 3^x (mod 7) acompanhe os resultados obtidos na tabela 1. Na operação normal, os valores encontrados são crescentes. Já na operação modular, os resultados são erráticos e difíceis de predizer.

Pois bem, por mais incrível que possa parecer, para entender a mecânica do algoritmo RSA não é preciso mais do que isto!

Rivest, Shamir e Adleman criaram um função especial que praticamente pode ser considerada unidirecional (ou de mão única). As funções unidirecionais autênticas não têm volta, ou seja, o resultado não pode ser revertido para os valores iniciais. A função do RSA é tão complicada ou tão demorada de ser revertida que, para efeitos práticos, pode ser considerada como uma função de mão única. O algoritmo pode ser dividido em 6 fases, a saber:

O destinatário ou dono da chave privada deve escolher dois números primos. Quanto maiores forem estes números, maior será a segurança obtida. Estes números são identificados por p e q e devem ser mantidos em segredo. Para facilitar o acompanhamento do processo, usaremos um exemplo com números primos pequenos: p = 19 e q = 23.

Escolhidos os números primos secretos, o destinatário multiplica-os para obter um novo número N, ou seja:

     N = p x q
     N = 19 x 23
     N = 437

A seguir, escolhe um número e que não tenha fatores comuns com (p-1) x (q-1). Isto é o mesmo que dizer que e e (p-1) x ( q-1) precisam ser primos entre si:

     (p-1) x (q-1) = 18 x 22
     (p-1) x (q-1) = 396

Fatorando o resultado 396, obtemos o seguinte (lembra das aulas de aritmética do primeiro grau?):

     396 | 2
     198 | 2
      99 | 3
      33 | 3
      11 | 11
       1 |

     ou seja, 396 = 2 x 2 x 3 x 3 x 11

Para que e e 396 sejam primos entre si, o valor de e não pode ser divisível nem por 2, nem por 3 e nem por 11. Digamos que o número escolhido tenha sido 13.

Estes dois números, N = 437 e e = 13 são a chave pública.

Aqui cabe mais uma explicação aritmética. O inverso de um número inteiro é 1 dividido por este número. Por exemplo, o inverso de 3 é 1/3 porque 3 x 1/3 = 1 e o inverso de 18 é 1/18 porque 18 x 1/18 = 1. Este conceito também pode ser aplicado à aritmética modular.

Considere 5 (mod 14). O resultado é 5 porque 5 ÷ 14 = 0 com resto 5. O inverso de 5 (mod 14) precisa ser um número que, multiplicando 5, resulte 1 no módulo 14 (assim como 3 x 1/3 = 1). Neste caso, o cálculo do inverso não é uma tarefa trivial. Como os números do exemplo são pequenos, podemos achar o inverso de 5 (mod 14) por tentativa:

     5 x 1 (mod 14) =  5 (mod 14) =  5
     5 x 2 (mod 14) = 10 (mod 14) = 10
     5 x 3 (mod 14) = 15 (mod 14) =  1 <----

Se chamarmos 5 de a, o módulo de n e a variável que multiplica 5 de y, podemos generalizar o problema do inverso de um módulo como a x y (mod n) = 1 onde precisamos encontrar o valor de y. O inverso de um módulo também é conhecido como redução modular. É importante saber que nem todas as reduções modulares têm soluções. Por exemplo, 2 não tem um inverso no módulo 14. De modo geral, quando a e n são primos entre si, existe uma solução única e, quando a e n não são primos entre si, não existe uma solução.

Para calcular a chave privada será preciso fazer uma redução modular. No exemplo que está sendo usado, é a redução modular 13 (mod 396). O cálculo de um inverso modular por tentativa pode ser um processo muito demorado e existem formas mais elegantes de resolver o problema. Uma delas é o algoritmo de Euclides estendido que será aplicado no nosso exemplo.

     (1)    13 ÷ 396 =  0 com resto 13   ...   divide-se o valor pelo módulo
     (2)   396 ÷  13 = 30 com resto  6   ...   divide-se o divisor anterior pelo resto
     (3)    13 ÷   6 =  2 com resto  1   ...   divide-se o divisor anterior pelo resto
             6 ÷   1 =  6 com resto  0   ...   divide-se o divisor anterior pelo resto

Na verdade, o cálculo acima nada mais é do que o cálculo do máximo divisor comum entre 13 e 396, comumente expresso como MDC(13,396). Como o último divisor com resto zero (divisão exata) é 1, sabemos que o MDC(13,396) = 1. Este é o algoritmo de Euclides que também serve para determinar se os números são primos entre si.

O algoritmo de Euclides estendido usa apenas os restos diferentes de zero das divisões mostradas acima. Estes podem ser expressos da seguinte maneira:

     (1)   13 = (1 x 13) - (0 x 396)
           13 = (1 x 13)

     (2)    6 = (1 x 396) - (30 x 13)       ...   e como (1) nos diz que 13 = (1 x 13)
            6 = (1 x 396) - (30 x (1 x 13))
            6 = (1 x 396) - (30 x 13)

     (3)    1 = (1 x 13) - (2 x 6)          ...   e como (2) nos diz que 6 = (1 x 396) - (30 x 13)
            1 = (1 x 13) - 2 x ((1 x 396) - (30 x 13))
            1 = (1 x 13) - (2 x 396) + (60 x 13)
            1 = (61 x 13) - (2 x 396)

O multiplicador de 13 é o inverso de 13 (mod 396). Neste caso, se chamarmos o inverso de d, então d = 61. Esta é a chave privada e que precisa ser mantida em sigilo.

Como os números primos que serviram de base para obter estes valores já cumpriram a sua função e precisam ser mantidos em segredo, eles podem ser simplesmente descartados. Resumindo os passos até este ponto temos:

     Chave pública: 437 e 13
     Chave privada: 437 e 61

Uma vez definida a chave pública N = 437 e e = 13, ela pode ser distribuída livremente para servir de chave para todos os remetentes que quiserem enviar mensagens cifradas para o dono do par de chaves. É importante esclarecer que se pode publicar e e manter d em segredo ou fazer o contrário, publicar d e manter e em segredo.

Digamos que um dos amigos do dono da chave queira lhe enviar uma mensagem confidencial e que o conteúdo desta mensagem seja (para variar) "numaboa". Esta mensagem precisa ser transformada num número (ou números) para que o algoritmo possa ser aplicado. Para isto, os valores ASCII dos caracteres da mensagem são perfeitos:

Neste caso, a mensagem será representada por m = 110117109979811197. Inicialmente m deve ser dividida em blocos. No presente exemplo, um bom tamanho serão blocos de três dígitos. Assim:

     m₁ = 110
     m₂ = 117
     m₃ = 109
     m₄ = 979
     m₅ = 811
     m₆ = 197

É preciso esclarecer que o último bloco não precisa necessariamente ter três dígitos. Cada um dos blocos será submetido à seguinte cifragem usando a chave pública, onde N é o módulo e e é o expoente:

     c = m^e (mod N)

     c₁ = 110¹³ (mod 437)
     c₂ = 117¹³ (mod 437)
     c₃ = 109¹³ (mod 437)
     c₄ = 979¹³ (mod 437)
     c₅ = 811¹³ (mod 437)
     c₆ = 197¹³ (mod 437)

Como as máquinas de calcular normalmente não mostram mais do que 10 a 12 dígitos, podemos facilitar os cálculos usando a propriedade distributiva da multiplicação modular. Como 13 = 5 + 5 + 3, então

     c₁ = 110¹³ (mod 437)
        = [110⁵ (mod 437) x 110⁵ (mod 437) x 110³ (mod 437)] (mod 437)

     Como 110⁵ (mod 437) = 16.105.100.000 (mod 437) = 325
     e    110³ (mod 437) =      1.331.000 (mod 437) = 335
     
     c₁ = [325 x 325 x 335] (mod 437)
        = 35.384.375 (mod 437)
        = 48

     c₂ = 117¹³ (mod 437)
        = [117⁵ (mod 437) x 117⁵ (mod 437) x 117³ (mod 437)] (mod 437)

     Como 117⁵ (mod 437) = 21.924.480.357 (mod 437) = 262
     e    117³ (mod 437) =      1.601.613 (mod 437) =   8
     
     c₂ = [262 x 262 x 8] (mod 437)
        = 549.152 (mod 437)
        = 280

Completando os cálculos, a mensagem cifrada será 048 280 401 146 243 330

Decifrar a mensagem significa realizar a mesma exponenciação, porém usando a chave de decifração ou chave privada:

     m = c^d (mod N)

     m₁ =  48⁶¹ (mod 437)
     m₂ = 280⁶¹ (mod 437)
     m₃ = 401⁶¹ (mod 437)
     m₄ = 146⁶¹ (mod 437)
     m₅ = 243⁶¹ (mod 437)
     m₆ = 330⁶¹ (mod 437)

Se com o expoente 13 já é aconselhável usar a propriedade distributiva da multiplicação modular, com o expoente 61 esta necessidade fica ainda mais evidente. Como normalmente usamos o computador para fazer os cálculos e a máquina usa o sistema binário, segue um exemplo de como usar a base 2. O valor decimal 61 é expresso em binário como 0011 1101, ou seja, é o mesmo que 2⁵ + 2⁴ + 2³ + 2² + 2⁰ = 32 + 16 + 8 + 4 + 1 = 61. Tomando o bloco m₁ como exemplo, podemos calcular:

     48⁶¹ (mod 437) = 48³² x 48¹⁶ x 48⁸ x 48⁴ x 48 (mod 437)
     
     Como
     48⁴ (mod 437) = (48² (mod 437))² (mod 437)
                   = (2.304 (mod 437))² (mod 437)
                   = 119² (mod 437)
                   = 14.161 (mod 437)
                   = 177

     Como
     48⁸ (mod 437) = ((48² (mod 437))² (mod(437))² (mod 437)
     e                (48² (mod 437))² (mod 437) = 177
     então         = 177² (mod 437)
                   = 31.329 (mod 437)
                   = 302

     Pelo mesmo raciocínio
     48¹⁶ (mod 437) = (48⁸ (mod 437))² mod (437)
                    = 302² mod (437)
                    = 91.204 (mod 437)
                    = 308
     
     E novamente pelo mesmo raciocínio
     48³² (mod 437) = (48¹⁶ (mod 437))² mod (437)
                    = 308² mod (437)
                    = 94.864 (mod 437)
                    = 35

De posse destes valores intermediários, fica fácil calcular

     48⁶¹ (mod 437) = 48³² x 48¹⁶ x 48⁸ x 48⁴ x 48 (mod 437)
                    = 35 x 308 x 302 x 177 x 48 (mod 437)
                    = 27.659.237.760 (mod 437)
                    = 110 <-- o valor original

Esta forma "binária" de calcular a exponenciação é um bom exemplo de como montar uma sub-rotina em qualquer linguagem de programação para calcular tanto a cifragem quanto a decifração, por que é iterativa.

Com frequência se afirma que a segurança do RSA depende exclusivamente da dificuldade de fatorar números grandes. Mas não é bem assim. Até agora não foi provado matematicamente que seja necessário fazer a fatoração de N para calcular a mensagem clara a partir do texto cifrado e da chave pública. Portanto, não é possível descartar a possibilidade de algum "maluco beleza" descobrir uma forma de encontrar a chave privada usando a chave pública. Enquanto isto não acontecer, a forma mais óbvia de atacar o RSA vai continuar sendo descobrir um método de fatoração rápido que consiga abrir N nos seus fatores primos. Também, enquanto isto, a segurança do RSA vai depender essencialmente dos números primos que escolhermos para criar as chaves. Primos pequenos, como os usados no exemplo, são um desastre e primos grandes demais (usados pelos paranóicos por segurança) acabam tornando os cálculos extremamente lentos.

Já que falamos de cálculos lentos, não custa frisar que um software que implementa o algoritmo RSA é cerca de 100 vezes mais lento do que um que implementa o DES. Por mais otimizado que seja, nada supera uma cifra de bloco em termos de velocidade. Se o algoritmo for implementado através de hardware, o cenário não melhora. Muito pelo contrário. Pelo que se sabe, chips especiais para RSA são cerca de 1000 vezes mais lentos do que chips para o DES, ou seja, em termos de velocidade, a coisa fica 10 vezes pior! Mas, apesar de tudo isto, o que eu tenho a dizer é "vida longa para os algoritmos assimétricos!".

Brinque um pouco on line para sentir o gosto. Acho que vale a pena por que me diverti um bocado escrevendo o JavaScript smile

Escrevi a ferramenta de cifragem e decifração abaixo em JavaScript. Utilizo apenas números primos pequenos por dois motivos: para não penalizar a velocidade do script e por pura preguiça, para não ter que usar uma biblioteca especial que lide com números muito grandes. Os valores considerados para a cifragem são os valores ASCII dos caracteres da mensagem clara.

Esta ferramenta é um modelo simplificado do algoritmo RSA e serve apenas para fins didáticos. Espero que ajude a entender o mecanismo do RSA.

Existe uma ferramenta para calcular o inverso modular através do algoritmo de Euclides estendido na Escolinha da Aldeia. Procure na Caixa de Ferramentas/Matemáticas/Algoritmo de Euclides Estendido. Na mesma Caixa de Ferramentas você encontra várias outras que podem ajudar: Aritmética Modular, Este número é primo?, MDC - Máximo Divisor Comum e Logaritmos e Potenciação.

Além disso, nos Garranchos NumaBoa/Sistemas Informatizados há um aplicativo para determinar os valores ASCII do teclado (os mesmos que foram usados acima). Tá na mão smile

3^x (mod 7)

Tabela 1
Comportamento errático
da função 3^x (mod 7)

Bruce Schneier, "Applied Cryptography".
Steve Burnett e Stephen Paine, "RSA Security's Official Guide to Cryptography".
Simon Singh, "O Livro dos Códigos".
Paul Johnson, RSA Algorithm.
David Shapiro, RSA In JavaScript.