Jump to content
  • Introdução ao RSA

       (0 reviews)

    c4v0k
     Share

    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.

    Caixacorreio.thumb.jpeg.a5c8b1a6643bae152db71d4c2ffabb7a.jpeg

    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))

    • l33t 2
     Share


    User Feedback

    Join the conversation

    You can post now and register later. If you have an account, sign in now to post with your account.
    Note: Your post will require moderator approval before it will be visible.

    Guest

    • This will not be shown to other users.
    • Add a review...

      ×   Pasted as rich text.   Paste as plain text instead

        Only 75 emoji are allowed.

      ×   Your link has been automatically embedded.   Display as a link instead

      ×   Your previous content has been restored.   Clear editor

      ×   You cannot paste images directly. Upload or insert images from URL.


  • Similar Content

×
×
  • Create New...