Jump to content

c4v0k

Members
  • Posts

    1
  • Joined

  • Last visited

  • Days Won

    2

c4v0k last won the day on December 10 2021

c4v0k had the most liked content!

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

c4v0k's Achievements

3

Reputation

  1. c4v0k

    Introdução ao RSA

    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))
×
×
  • Create New...