Continuando a série de artigos com foco em criptografia, hoje veremos um dos primeiros algoritmos de chave assimétrica, o RSA, que permite estabelecer uma conexão segura entre duas entidades sem contato prévio entre elas.
Antes de prosseguir, vale relembrar boas práticas apresentadas no artigo do Chinchila: nunca implemente um esquema criptográfico, utilize bibliotecas reconhecidas pela comunidade, preferencialmente de código aberto.
Outro ponto importante é que o RSA parece simples em termos matemáticos, mas é fácil de ser utilizado de maneira incorreta na construção de protocolos e/ou implementado de forma a inserir várias vulnerabilidades. O algoritmo básico apresentado aqui não garante proteção contra a maioria de tais vulnerabilidades. Por fim, serão apresentadas simplificações no algoritmo e código em Python para auxiliar a compreensão.
Criptografia de chave assimétrica
Como apresentado no primeiro artigo de criptografia, algoritmos de chave assimétrica possuem 2 chaves: uma chave pública e uma chave privada (secreta). O uso correto de ambas as chaves permite que duas pessoas estabeleçam um canal de comunicação seguro sem a necessidade de terem combinado chaves anteriormente.
O funcionamento do algoritmo é análogo a uma caixa de correio como a da foto abaixo. Vamos considerar que a comunicação segura é estabelecida entre a pessoa que envia uma carta e o correio. Quando a pessoa vai enviar a carta, basta deixá-la na caixa. Para manter a analogia mais precisa, vamos considerar que existe uma chave disponível junto à caixa de correio e que ela deve ser utilizada para depositar a carta na caixa. Qualquer usuário pode ter acesso a chave para depositar cartas na caixa, por isso tal chave é denominada chave pública.
Caixa de correio - Fonte: Wikipedia
Apenas o Correio possui a chave necessária para abrir a caixa, portanto sabemos que somente ele pode receber as cartas depositadas na caixa. Esta chave é denominada chave privada.
Dessa forma, o usuário pode enviar mensagens que somente o correio pode ler. Isso ocorre porque todas as mensagens deixadas na caixa só podem ser recebidas pelo detentor da chave privada, ou seja, o próprio correio.
Um dos primeiros algoritmos capazes de proporcionar a funcionalidade descrita é o RSA.
Aritmética modular
A aritmética modular é feita apenas com números inteiros. Utilizando mais uma analogia, a aritmética modular é próxima ao funcionamento de um relógio. O ponteiro das horas de um relógio tem funcionamento cíclico, nunca é maior que 11 e menor que 0 (considerando que 12h = 0h). Sempre que o relógio ultrapassa 11h, o relógio volta a contar a partir de 0h. O mesmo vale para somar horas: somando 10h com 4h, o resultado será 2h. Nesse caso, diz-se que as operações são feitas "módulo 12", também representadas por "8 + 6 = 2 mod 12".
Computar o valor de a módulo b pode ser interpretada também como calcular o resto da divisão de a por b, por exemplo 23 = 2 mod 7, porque 23 = 7\*3 + 2, 16 mod 4 = 0, porque 16 = 4\*4 + 0
Em Python, o operador "%" é utilizado para computar a operação modular:
print(23%7)
Além da soma, também existem as operações de multiplicação e potenciação modular. Essas operações são computadas assim como na aritmética regular. Em seguida, é calculado o resto da divisão pelo valor do módulo, por exemplo:
3\*7 mod 5 -> 3\*7 = 21 = 4\*5+1 = 1 mod 5
3^5 mod 7 -> 3^5 = 243 = 34\*7 + 5 = 5 mod 7
print(3*7%5, pow(3,5,7)) # no Python, pow(a,b,c) = (a**b)%c
O RSA
O algoritmo RSA utiliza a potenciação modular, onde os expoentes são as chaves. Conforme a analogia da caixa de correio, existe uma chave pública, representada por e, e uma chave privada (secreta), representada por d. O valor do módulo é representado por N e é calculado como o produto de dois inteiros primos, representados por p e q. A segurança do algoritmo depende, entre outros fatores que não serão apresentados aqui, do tamanho de p e q, sendo recomendado usar primos de no mínimo 1024 bits.
from random import randint from sympy import isprime def random_prime(lower_bound, upper_bound): while True: r = randint(lower_bound, upper_bound) if isprime(r): return r p = random_prime(2**512, 2**513) q = random_prime(2**512, 2**513) N = p*q print(p, q, N)
As chaves pública e privada devem ser calculadas de forma que uma mensagem encriptada pela chave pública pode ser desencriptada somente com o conhecimento da chave privada. Em outro artigo será apresentado o porque de calcular as chaves conforme o código abaixo.
phi = (p-1)*(q-1) e = 17 d = pow(e, -1, phi) print(e, d)
Consideramos que a mensagem a ser enviada seja "artigo_RSA_mente_binaria". Ela deve ser convertida para uma representação em números inteiros com a função bytes_to_long da biblioteca Pycryptodome:
from Crypto.Util.number import long_to_bytes, bytes_to_long msg = b"artigo_RSA_mente_binaria" m = bytes_to_long(msg) print(m)
A encriptação da mensagem consiste em elevar o valor inteiro da mensagem à chave pública e:
ciphertext = pow(m, e, N) print(ciphertext) print(long_to_bytes(ciphertext))
É possível ver que, após a encriptação, é difícil ver qualquer relação entre a mensagem original e a mensagem encriptada.
Para que o destinatário recupere a mensagem, basta que ele faça o mesmo procedimento da encriptação, mas utilizando o expoente secreto d:
plaintext = pow(ciphertext, d, N) print(plaintext) print(long_to_bytes(plaintext))
Importante
Esse artigo apresenta apenas uma introdução ao RSA, diversas partes importantes foram omitidas para facilitar a compreensão. Existem várias vulnerabilidades inerentes a uma implementação básica como essa. Uma boa forma de estudar e compreender melhor esse algoritmo e suas vulnerabilidades é analisar e implementar estes ataques. No ASIS CTF Quals 2021 havia um chall que envolvia uma versão modificada do RSA, mas suscetível às mesmas vulnerabilidades. O write-up do ELT pode ser encontrado aqui. Para saber mais, recomendo os challs do Cryptohack e as próximas postagens aqui no site.
Bom estudo, se tiver dúvidas e/ou sugestões deixe nos comentário abaixo, até a próxima!
Código
from random import randint from sympy import isprime from Crypto.Util.number import long_to_bytes, bytes_to_long def random_prime(lower_bound, upper_bound): while True: r = randint(lower_bound, upper_bound) if isprime(r): return r p = random_prime(2**512, 2**513) q = random_prime(2**512, 2**513) N = p*q print(p, q, N) phi = (p-1)*(q-1) e = 17 d = pow(e, -1, phi) print(e, d) msg = b"artigo_RSA_mente_binaria" m = bytes_to_long(msg) print(m) ciphertext = pow(m, e, N) print(ciphertext) print(long_to_bytes(ciphertext)) plaintext = pow(ciphertext, d, N) print(plaintext) print(long_to_bytes(plaintext))
-
1
-
2
