As Redes RSA

RSA

Grupo:

Professor:

RSA

RSA é um algoritmo de criptografia de dados, que deve o seu nome a três professores do Instituto de Tecnologia de Massachusetts (MIT), Ronald Rivest, Adi Shamir e Leonard Adleman, fundadores da atual empresa RSA Data Security, Inc.

que inventaram este algoritmo — até a data (2008) a mais bem sucedida implementação de sistemas de chaves assimétricas, e fundamenta-se em teorias clássicas dos números. É considerado dos mais seguros, já que mandou por terra todas as tentativas de quebrá-lo. Foi também o primeiro algoritmo a possibilitar criptografia e assinatura digital, e uma das grandes inovações em criptografia de chave pública.

Funcionamento

O RSA envolve um par de chaves, uma chave pública que pode ser conhecida por todos e uma chave privada que deve ser mantida em sigilo. Toda mensagem cifrada usando uma chave pública só pode ser decifrada usando a respectiva chave privada.

Exemplos:

Mensagens de emails

Compras on-line

.

Geração das chaves

No RSA as chaves são geradas desta maneira:

Pegar dois números primos muito grandes, p e q (tamanho aproximadamente igual).

Calcular n = p*q.

Compute a função totient em ϕ = (p-1)*(q-1).

Escolher um número aleatório e tal que 1<e<ϕ e não tenha nenhum fator em comum com ϕ.

Em seguida calcular d de modo que e*d mod ϕ = 1.

O par (e,n) é a chave pública. (d,n) é a chave privada.

1

Exemplo:

Em primeiro lugar, vamos criar nosso par de chaves:

1- Pegar dois números primos aleatórios: p = 29, q = 37

2- Calcular n = p*q = 29 * 37 = 1073

3-Calcular função totient (p-1)(q-1) = (29-1)(37-1) = 1008

4-”e” deve ser escolhido de forma aleatória de modo que e não tenha nenhum fator em comum com (p-1) (q-1):

Pegar e = 71

5- Escolher d como 71*d mod 1008 = 1

Vamos encontrar d = 1079

Agora temos as nossas chaves:

A chave pública é (e,n) = (71,1073) (=chave de criptografia)

A chave privada é (d,n) = (1079,1073) (=chave de decodificação)

Criptografia

Para criptografar uma mensagem C basta fazer uma potenciação modular, usando a chave pública formada por “e” e “n”:

P = Ce (mod n)

2

Exemplo:

Vamos criptografar a mensagem “HELLO”. Vamos pegar o código ASCII de cada caractere e colocá-los lado a lado:

m = 7269767679

Dividindo a mensagem em blocos de 3 dígitos temos:

726 976 767 900 (completado com 0)

Depois, vamos criptografar cada bloco:

726^71 mod 1073 = 436

976^71 mod 1073 = 822

767^71 mod 1073 = 825

900^71