RSA e Testes de Primalidade

1. O Algoritmo RSA

Em 1977, três pesquisadores (Rivest, Shamir e Adleman) desenvolveram um algoritmo de criptografia de chave pública baseado na dificuldade de fatorar números compostos com elevada magnitude, que foi chamado RSA.

O RSA veio a ser o primeiro modelo real, uma vez que o modelo original desenvolvido por Diffie-Helman não tinha viabilidade prática na época.

Segundo o RSA, um usuário inicial (Bob) escolhe dois primos aleatórios de grande magnitude (p e q). Ele multiplica esses valores e gera um novo número n=p*q.

De posse de n, Bob seleciona um expoente criptográfico e, tal que ele tenha a seguinte propriedade gcd (e, (p-1)(q-1)=1.

Após calcular o expoente criptográfico, Bob envia ele (e) juntamente com n para os usuários que deseja estabelecer um canal seguro.

O usuário remoto que deseja enviar uma mensagem (m) através de um canal seguro deve realizar a seguinte operação: c deve ser congruente a me (mod n), onde c é a mensagem cifrada a ser trafegada.

Ao receber a mensagem, Bob deverá calcular um valor d (secreto), tal que d*e seja congruente a 1 (mod(p-1)(q-1)), onde a mensagem em claro (m ) será congruente a cd(mod n).

2. Testes de Primalidade

Conforme pode-se ver nos parágrafos anteriores, a eficácia de uma algoritmo RSA se deve a correta seleção dos valores primos que comporão o valor de n, usado para calcular a chave pública e privada usada pelo algoritmo.

Uma das tarefas assessórias, porém tão importante como o armazenamento de forma segura dos valores p e q, são os testes que definem se um valor é primo ou não, pois caso não o seja, toda a proteção do RSA fica comprometida, pois é possível fatorar o valor de forma bastante eficiente e rápida.

2.1. Teste Fundamental de Primalidade

O teste de primalidade mais rudimentar é baseado em um teorema de primalidade. Esse teorema diz que se um valor n inteiro e positivo é composto, então ele possui um divisor primo menor ou igual a raiz quadrada de n.

Por esse teorema, se eu quero descobrir os números primos que compõe um valor n, então eu texto (força bruta) todos os valores ímpar menores que a raiz quadrada de n para verificar se dividem n.

O problema dessa abordagem é que seriam necessárias pelo menos raiz quadrada de logaritmo da raiz quadrada de n divisões para provar que um valor é primo, ou seja, é extremamente ineficiente.

2.1. Teste Fermat

O teste de fermat diz que se n é primo, para todo a pertencente ao conjunto dos inteiros existe an-1 congruente a 1 (mod n).

Caso o valor n passe em seu teste, ou seja, ele é congruente a 1, não se pode afirmar que o valor é primo, apenas diz-se que ele é provavelmente primo, uma vez que existem alguns números compostos que passam por esse teste (números de Carmichael).

Porém quando o valor de n não passa no teste, pode-se afirmar que o valor n não é primo, ou seja, é composto.

Ex.: n=341=11 * 31 => 2340 congruente a 1 (mod 341), porém 3340 é congruente a 56 (mod 341).

Um bom uso para o teste de fermat é em um teste inicial de um valor, caso ele não passe, automaticamente se define que o número é composto. Caso ele passe, deve-se executar um novo teste que será visto a seguir (o teste de Miller-Rabin).

2.2. Número de Carmichael

Um número de Carmichael é um valor que não se consegue provar pelo teste de fermat se ele é composto ou não para qualquer que seja a base utilizada.

Um exemplo de um número de Carmichael é 561, que é igual 3*11*17 e qualquer que seja a base testada, sempre retornará que o valor é primo.

2.3. Testes de Miller-Rabin

O teste de Miller-Rabin garante que um valor é primo, onde ele é totalmente imune aos números de carmichael.

Para realizar teste de miller-rabin, deve-se escolher um valor ímpar n>1, tal que n-1=m*2k e m também é um valor ímpar.

O teste consiste em selecionar um novo valor randômico a, tal que 1.

Deve-se calcular b0 congruente am (mod n). Se b0 for congruente a +/- 1 (mod n), então n é certamente composto, caso contrário, ele provavelmente seja primo e deve-se calcular um novo valor b1 congruente b02 (mod n).

Caso o valor de b0 for congruente a +/- 1 (mod n), n é composto.

Esse teste deve ser repetido várias vezes de forma a se garantir que o valor n tenha uma grande probabilidade de ser primo, uma vez que o teste miller-rabin é baseado na distribuição estatística de Monte Carlo.

Uma vez que a teoria informa que a densidade de números primos é de aproximadamente 1/ln(x). Se eu quero um x com uma grandeza aproximadamente de 100 casas decimais (x=10100), então a densidade de primos (k) é de aproximadamente 1/230. Como os primos são sempre ímpar (exceto 2), k será aproximadamente 1/100, fazendo com que seja necessário, para essa magnitude, cerca de 100 testes de miller-rabin.