... ainda dentro de Criptografia Assimétrica ...
Na
criptografia assimétrica, o acrônimo RSA está para as iniciais dos sobre nomes
de Ron Rivest, Adi Shamir e Leonard Adleman que foram os primeiros a publicar
uma implementação de um algoritmo para a criptografia de chaves públicas, sendo
que tal publicação ocorrera em 1978. É o primeiro algoritmo conhecido utilizado
para assinaturas e criptografia de mensagens, e um dos primeiros a mostrar as
grandes vantagens desta criptografia de chaves públicas. o RSA é amplamente
utilizado nos protocolos de comércio eletrônico, e a este pode ser dado a
confiança, se utilizado chaves suficientemente grandes e ainda com atualizações
periódicas na implementação do algoritmo, que ocorre quando encontrado
possíveis falhas.
Há relatos de que outra pessoa já
havia descrito o trabalho do algoritmo de chaves públicas de maneira bastante
parecida com o que foi apresentado com o RSA. Esta pessoa é Clifford Cocks, um
matemático britânico que trabalha para a inteligência inglesa, e descreveu um
sistema "equivalente" em um ofício interno em 1973, porém como o
poder computacional necessário seria muito caro, o projeto até que era curioso,
mas nas atuais circunstâncias, acabou sua descoberta não sendo desenvolvida, no
entanto não havia sido revelada até meados de 1998.
O MIT concedeu uma patente aos
inventores do RSA pelo algoritmo desenvolvido cujo foi denominado como
"Sistema e método de comunicações criptográficas", a patente
espiraria em 21 de setembro de 2000, mas a expiração e o algoritmo foi liberado
para domínio público duas semanas antes, em 6 de setembro de 2000. Um resumo da
patente discursa o seguinte:
"O sistema cria um
canal de comunicação, onde um terminal de ponta tem a tarefa de codificar a mensagem
e outro terminal tem a tarefa de decifrar a mensagem. A mensagem a ser
transferida é cifrada/codificada por um terminal para um texto não legível pela
codificação com um número M em um conjunto predeterminado. O número é então
elevado para o poder predeterminado (associado com o número do recebedor) e
finalmente computado. O resto ou os resíduos, C, é computado o número potenciado
é dividido pelo produto de dois número primos predeterminados (associados com
recebedor pretensioso)."
Sendo tal resumo não muito fácil de ser
compreendido, segue uma descrição do algoritmo, desde a geração das chaves, até
a utilização do algoritmo: O RSA envolve
uma chave pública e uma chaves privada. A chave pública pode ser de
conhecimento público, e é frequentemente utilizada para criptografar mensagens.
Uma mensagem cifrada com determinada chave pública só pode ser decifrada com a
chave privada correspondente. As chaves geradas para os algoritmos RSA são
geradas da seguinte maneira;
1 - É escolhido dois números primos distintos,
denominados p e q, por exemplo, p=61 e q=53;
2 - Computa n = p * q, no caso
n=(61*53), ou seja, n=3233; (o valor de n é utilizado como um módulo para ambas
as chaves, públicas e privadas)
3 - Calcula-se (f é a função phi de
Euler) que corresponde a f(pq) = (p - 1)(q - 1), que vem a ser (61-1)*(53-1)
resultando 3120.
4 - Escolhe um número inteiro
denominado “e” de maneira que e seja maior que 1 e menor que f(pq), ou seja,
menor que 3120 no nosso exemplo, e ainda o valor o valor de “e” necessita ser
um número primo que seja fácil de ser encontrado, e o valor de “e” não pode ser
um divisor de f(pq), ou seja, o nosso valor de “e”, não pode ser divisor de
3120. Dentre os primeiros números primos que poderiam ser utilizados pode-se
citar o 7 e o 17 que atendem ao critério para o valor de “e”, para tanto, será
escolhido o número 17, logo, “e”= 17.
5 – Determinar o valor de “d” de
maneira que obedeça a fórmula d*e=1 (mod f(pq)), cujo valor de “d” deve ser
encontrado com a extensão do algoritmo de Euclides, com a Multiplicação Modular
Inversa que é assim definido;
“A multiplicação modular
inversa de um número inteiro "a" e módulo "m" é um inteiro
"x" que obedece à: a-1=x(mod m). Isto é, a multiplicação
inversa é uma aliança do módulo dos inteiros. Isto equivale a ax=aa-1
= 1 (mod m). A multiplicação inversa de um módulo existe 'se e somente se' o
valor de "a" e o valor de "m" são primos entre si, por
exemplo, se gcd(a, m) = 1. Se a multiplicação modular de um módulo
"m" existe, a operação de divisão por um módulo "m" pode
ser definida como multiplicação pelo seu inverso, o que é a essência do mesmo
conceito do campo da divisão dos número reais.” Do original; “The modular multiplicative inverse of an
integer "a" modulo m is an integer x such that a-1=x(mod
m). That is, it is the multiplicative inverse in the ring of integers modulo m.
This is equivalent to ax=aa-1 = 1 (mod m). The multiplicative
inverse of a modulo m exists iff (if and only if) "a" and
"m" are coprime (i.e., if gcd(a, m) = 1). If the modular
multiplicative inverse of a modulo "m" exists, the operation of
division by a modulo m can be defined as multiplying by the inverse, which is
in essence the same concept as division in the field of reals.”
Para poder então efetuar o cálculo de “d”
dado a regra supracitada, onde os valores até o momento obtidos como parâmetro
são os valores de “e” e f(pq) que são 17 e 3120 respectivamente, se faz
necessário efetuar iterações sobre o valor de f(pq), de maneira a obter a
condição d*17=x e x+1 mod f(pq)=1.A maneira relativamente barata de se
encontrar é por tentativas, enquanto deve-se iterar sobre o valor de f(pq) e
somado a 1 dividir este valor por “e”, e este valor obtido que podemos
denominar de “auxiliar” deve ser multiplicado então a “e”, e se a condição
“valor obtido”
O valor de “d” encontrado é então 2753, visto
que se dá por 17 * 2753 = 46801, que por sua vez o valor de 46801 mod 3120 = 1.
A resposta então é: o valor de f(pq) iterado 15 vezes mais 1 dividido por 17
resulta 2753, considerando ainda que outro valor, como por exemplo não iria
produzir um resto inteiro.
A chave pública é o valor (n=3233,
e=17), de maneira que para criptografar uma mensagem m, a função de
criptografia é m elevado a 17 mod 3233, e a chave privada é (n=3233, e=17), a
função de decifrar a mensagem criptografada c,
é c elevado 2753 mod 3233.
Na prática, para fazer o cálculo da
mensagem cifrada c, por exemplo, da
mensagem m 65 com a chave pública,
deve-se calcular c = 2790, visto que
é o resultado de 6517 mod 3233.
No recebimento da mensagem cifrada
2790, a chave privada é utilizada para decifrar a mensagem m, cujo cálculo deve ser m
= 65, visto que 27902753 mod 3233.
A segurança do sistema RSA e de
vários outros sistemas de criptografia simétrica em especial os de chaves públicas
se baseiam na dificuldade da fatoração de números inteiros grandes o que é uma
tarefa dificílima mesmo para poderosos computadores, sendo considerado em
algumas vezes tarefas impossíveis, o que é válido afirmar que ao selecionar
dois primos de 512 bytes aleatoriamente, e multiplicando estes valores, é
possível criar uma chave pública que não vai ser quebrada em um período viável
com tecnologia que conhecemos atualmente. De acordo com a fonte de informação,
para evitar que se novos métodos de fatoração sejam desenvolvidos e as
aplicações que utilizam o RSA sejam enfraquecidos, faz-se necessário que cada
vez mais os inteiros trabalhados sejam grandes, o quanto maior possível, a
fonte que escrita em 2001 afirma que trabalhava com faixas de 768 a 2048 bits.
Com certeza de acordo com que o
tamanho das chaves se torna maior, mais pesado será o processamento de
criptografia e maior ainda o de decifragem das mensagens. Para mensagens
grandes, a tarefa pode ser inviável de ser executada, então uma solução é cifrar
a mensagem com uma criptografia simétrica, com uma chave secreta escolhida pelo
remetente, e então cifrar a chave secreta com a chave pública do destinatário,
assim será necessário enviar a mensagem criptografada, qual foi o algoritmo
simétrico utilizado na cifragem e enviar a chave de decifragem também cifrada.
No segmento, o destinatário irá utilizar a sua chave privada para decifrar a
chave secreta que se encontra cifrada, e então sabendo o algoritmo simétrico
certo, utilizá-lo na decifragem da mensagem com a chave secreta obtida. Vale
mencionar que foi dito várias vezes no texto supracitado o algoritmo simétrico
porque este tem um desempenho melhor na execução, por utilizar uma única chave
secreta na cifra e decifragem de uma mensagem. Esta abordagem é conhecida como
abordagem híbrida, pois utiliza a criptografia simétrica e a assimétrica.
