Ir para conteúdo

c4v0k

Membros
  • Postagens

    1
  • Registro em

  • Última visita

  • Dias Ganhos

    2

c4v0k venceu a última vez em Dezembro 10 2021

c4v0k tinha o conteúdo mais apreciado!

Últimos Visitantes

O bloco dos últimos visitantes está desativado e não está sendo visualizado por outros usuários.

Conquistas de c4v0k

3

Reputação

  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))
×
×
  • Criar Novo...