O que é o RSA? - Sua história e origem

jjcajota

Viva pessoal;

Este artigo foi encontrado no _http://www.funfiles.ws/upload.php (_http://www.funfiles.ws/upload.php?do=download&id=35882), e foi publicado pelo "fclone" que agradece ao "oilen (3º Sargento)". Créditos devidamente atribuídos e como o artigo não referia restrições de publicação cá vai. Motivo de orgulho, pois está em Português de Portugal e portanto escrito por um português.


----------------- Material pertencente aos referidos autores --------------
A História do RSA

Ron Rivest
Como era o trio de pesquisadores do Laboratório de Ciência da Comp*tação do MIT em 1976? Ron Rivest é um jovem cientista da comp*tação, dono de uma curiosidade científica insaciável e de uma imensa capacidade de absorver e aplicar novas ideias. 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 comp*taçã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 a ganhar-lhes por 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 a esgotar-se quando Rivest, no meio de uma noite de insônia, se lembrou de uma particularidade da matemática. Era muito simples e provavelmente tinha tomado conhecimento do assunto quando ainda estava na escola primária: a factoração. Multiplicar dois números primos é uma questão de segundos mas, se temos apenas o resultado e quisermos encontrar os números primos (factores) deste resultado, o processo é bem mais demorado. À medida que multiplicamos números primos cada vez maiores, o tempo gasto para factorar 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 o seu "advogado do diabo". Adleman, acostumado às 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 tinha baptizado 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 o 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 o seu nome fosse citado em último lugar, motivo pelo qual a cifra foi rebatizada e passou a ser chamada de RSA.

Noções de Aritmética

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 exactamente por 1 ou por si mesmo. Assim, 3 é um número primo porque só tem uma divisão exacta quando dividido por 1 ou por 3. Já o número 4 não é primo porque pode ser dividido exactamente por 1, 2 e 4. Se o número 4 não é um número primo, então pode ser factorado, 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 para 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 3x (mod 7) acompanha 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!


A mecânica do algoritmo RSA

Rivest, Shamir e Adleman criaram um função especial que praticamente pode ser considerada de via única. As funções de via única 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 via única. O algoritmo pode ser dividido em 6 fases, a saber:


1. Escolha de dois números primos gigantes

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.



2. Cálculo da chave pública

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 factores 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

Factorando o resultado 396, obtemos o seguinte:


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.


2. Cálculo da 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.

Considera 5 (mod 14). O resultado é 5 porque 5 ÷ 14 = 0 com resto 5. O inverso de 5 (mod 14) precisa de 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 a 5 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 todos 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 nenhuma solução.

Para calcular a chave privada será preciso fazer uma redução modular. No exemplo que estamoa a usar, é 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 exacta) é 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



4. Publicação da chave

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 da chave. É importante esclarecer que se pode publicar e e manter d em segredo ou fazer o contrário, publicar d e manter e em segredo.



5. Cifrar uma mensagem

Digamos que um dos amigos do dono da chave queira enviar uma mensagem confidencial e que o conteúdo desta mensagem seja "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:



n = 110
u = 117
m = 109
a = 97
b = 98
o = 111
a = 97

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:


m1 = 110
m2 = 117
m3 = 109
m4 = 979
m5 = 811
m6 = 197

É preciso esclarecer que o último bloco não precisa necessariamente de 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 = me (mod N)

c1 = 110 ^ 13 (mod 437)
c2 = 117 ^ 13 (mod 437)
c3 = 109 ^ 13 (mod 437)
c4 = 979 ^ 13 (mod 437)
c5 = 811 ^ 13 (mod 437)
c6 = 197 ^ 13 (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



c1 = 110 ^ 13 (mod 437)
= [110 ^ 5 (mod 437) x 110 ^ 5 (mod 437) x 110 ^ 3 (mod 437)] (mod 437)

Como 110 ^ 5 (mod 437) = 16.105.100.000 (mod 437) = 325
e 110 ^ 3 (mod 437) = 1.331.000 (mod 437) = 335

c1 = [325 x 325 x 335] (mod 437)
= 35.384.375 (mod 437)
= 48

c2 = 119 ^ 13 (mod 437)
= [119 ^ 5 (mod 437) x 119 ^ 5 (mod 437) x 119 ^ 3 (mod 437)] (mod 437)

Como 119 ^ 5 (mod 437) = 23.863.536.599 (mod 437) = 104
e 119 ^ 3 (mod 437) = 1.685.159 (mod 437) = 87

c2 = [104 x 104 x 87] (mod 437)
= 940.992 (mod 437)
= 131

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



6. Decifrar a mensagem

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



m = cd (mod N)

m1 = 48 ^ 61 (mod 437)
m2 = 131 ^ 61 (mod 437)
m3 = 401 ^ 61 (mod 437)
m4 = 146 ^ 61 (mod 437)
m5 = 243 ^ 61 (mod 437)
m6 = 330 ^ 61 (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 comp*tador 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 ^ 5 + 2 ^ 4 + 2 ^ 3 + 2 ^ 2 + 2 ^ 0 = 32 + 16 + 8 + 4 + 1 = 61. Tomando o bloco m1 como exemplo, podemos calcular:



48 ^ 61 (mod 437) = 48 ^ 32 x 48 ^ 16 x 48 ^ 8 x 48 ^ 4 x 48 (mod 437)

Como
48 ^ 4 (mod 437) = (48 ^ 2 (mod 437)) ^ 2 (mod 437)
= (2.304 (mod 437)) ^ 2 (mod 437)
= 119 ^ 2 (mod 437)
= 14.161 (mod 437)
= 177

Como
48 ^ 8 (mod 437) = ((48 ^ 2 (mod 437)) ^ 2 (mod(437)) ^ 2 (mod 437)
e (48 ^ 2 (mod 437)) ^ 2 (mod 437) = 177
então = 177 ^ 2 (mod 437)
= 31.329 (mod 437)
= 302

Pelo mesmo raciocínio
48 ^ 16 (mod 437) = (48 ^ 8 (mod 437)) ^ 2 mod (437)
= 302 ^ 2 mod (437)
= 91.204 (mod 437)
= 308

E novamente pelo mesmo raciocínio
48 ^ 32 (mod 437) = (48 ^ 16 (mod 437)) ^ 2 mod (437)
= 308 ^ 2 mod (437)
= 94.864 (mod 437)
= 35

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



4861 (mod 437) = 48 ^ 32 x 48 ^ 16 x 48 ^ 8 x 48 ^ 4 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 numa qualquer linguagem de programação para calcular tanto a cifragem quanto a decifração porque é iteractiva.

Segurança e Velocidade

Afirma-se com frequência que a segurança do RSA depende exclusivamente da dificuldade de factorar números grandes. Mas não é bem assim. Até agora não foi provado matematicamente que seja necessário fazer a factoraçã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" 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 continuando a ser, descobrir um método de factoração rápido que consiga abrir N nos seus factores 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 por tornar 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 optimizado 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!".



Muitos perguntam por onde começar para estudar os sistemas de encriptação usados no Sat. Ora aqui têm um caminho, simples para já e com documentos pequenos e acessíveis.
Abraços

islander

Ufff.. epá o meu curso é ciência política

Mas ainda assim parece-me simples... e lógico! (Que é um conceito que não consigo aplicar á matemática em geral... enfim questões filosóficas)

Valeu!

tvbarao

Acho este tópico deveras interessante! Vou segui-lo atentamente!
Espero não me "perder" pelo caminho...
O Excel pode ser uma ferramenta útil, para este estudo.
Numa divisão inteira, apenas o valor inteiro é assumido como resultado, descartando-se os valores decimais.
Exemplo:
Divisão normal: 5 : 2 = 2,5
Divisão Inteira(LN): 5 : 2 = 2 ; resto 1
Então o resto da divisão inteira é o que sobra se multiplicarmos o restultado (2) pelo divisor (2) e os subtrairmos ao dividendo (5). Assim temos que:
5 - (2*2) = 5 - 4 = 1
MOD = Resto da divisão inteira