Como funciona a criptografia RSA

Introdução:

A transmissão de informações codificadas sempre foi uma necessidade da humanidade, desde os tempos da Grécia antiga. Imagine então nos tempos atuais, com a internet, onde informações confidenciais sempre viajam de todos os cantos para todos os cantos e sempre podem ser interceptadas por pessoas mal-intencionadas. Por isso crio-se a criptografia, um modo de transmitir informações de maneira que só o destinatário possa ter acesso a elas. Existem muitos tipos de criptografia, mas a mais utilizada é a criptografia RSA, por ser uma das mais seguras atualmente. RSA são as iniciais dos nomes dos matemáticos que a criaram em 1978, Ronald Rivest, Adi Shamir e Leonard Adleman, que na época  trabalhavam  no  Massachussets  Institute  of Technology  (M.I.T).

Essa criptografia baseia-se no uso de chaves públicas e privadas. Você pode criar uma chave pública e distribuí-la pra todo mundo, para que as pessoas possam criptografar informações e envia-las pra ti com segurança, sem o perigo de interceptação ilícita. Somente você, que possui a sua chave particular, consegui descriptografar as informações codificadas com a sua chave pública. As pessoas que codificaram as informações com a chave pública também não conseguem decodificá-las. Isso é útil por exemplo em sites de comércio eletrônico: o usuário do site utiliza a chave pública para codificar os dados, mas só a empresa que possui a chave particular consegui decodifica-los.

Funcionamento:

Conforme mencionado, o algoritmo RSA é baseado na construção de chaves públicas e privadas, utilizando números primos. Inicialmente devem ser escolhidos dois números primos quaisquer A e B. Quanto maior o número escolhido mais seguro será o algoritmo.

A título de exemplificação, serão escolhidos números primos pequenos, para permitir um acompanhamento de todo o processo de codificação e decodificação.

• A = 17
• B = 11

A seguir são calculados dois novos números N e Z de acordo com os números P e Q escolhidos:

• N = A * B
• O(N) = (A - 1) * (B - 1)

No caso obtêm-se como resultado:

• N = 17 * 11 = 187
• O(N) = 16 * 10 = 160

Agora se define um número P que tenha a propriedade de ser primo em relação a (O)N. No caso, opta-se pela escolha:

• P = 7

De posse desses números começa o processo de criação das chaves públicas e privadas. É necessário encontrar um número S que satisfaça a seguinte propriedade:

• (P *S) mod O(N) = 1

Se forem feitos os testes com 1, 2, 3... teremos:

• S = 1 => (1 * 7) mod 160 = 7
• S = 2 => (2 * 7) mod 160 = 14
• S = 3 => (3 * 7) mod 160 = 21
• ...
• S = 23 => (23 * 7) mod 160 = 1
• ...
• S = 183 => (183 * 7) mod 160 = 1
• ...
• S = 343 => (343 * 7) mod 160 = 1
• ...
• S = 503 => (503 * 7) mod 160 = 1
• ...

Logo até o momento os números 23, 183, 343, 503 satisfazem a propriedade indicada.

Para efeito de simplificação de cálculos, será tomado como referência:

• S = 23.

Com esse processo definem-se as chaves de encriptação e desencriptação.

• para codificar: utilizar P e N - esse par de números será utilizado como chave pública.

• para decodificar: utilizar S e N - esse par de números será utilizado como chave privada.

As equações são:

• TEXTO CRIPTOGRAFADO = (TEXTO ORIGINAL ^ P) mod N

• TEXTO ORIGINAL = (TEXTO CRIPTOGRAFADO ^ S) mod N

Caso prático para o exemplo

Seja a necessidade de se encaminhar uma mensagem bem curta de forma criptografada, como o número 4 por exemplo, tendo por base as chaves aqui estabelecidas.

Para criptografar:

• TEXTO ORIGINAL = 4
• TEXTO CRIPTOGRAFADO = (4 ^ 7) mod 187
• TEXTO CRIPTOGRAFADO =  16384 mod 187
• TEXTO CRIPTOGRAFADO = 115

Para descriptografar:

• TEXTO RECEBIDO = 115
• TEXTO ORIGINAL = (115 ^ 23) mod 187
• TEXTO ORIGINAL = 2,4891457557496919672912398470124e+47 mod 187
• TEXTO ORIGINAL = 4

A questão das escolhas dos números primos envolvidos é fundamental para o algoritmo. Por essa razão escolhem-se números primos gigantescos para garantir que a chave seja inquebrável.

Antes da codificação os caracteres são transformados em cadeias de números que correspondem aos seus códigos ASCII.