Ataques a RSA

Definição

Ao longo dos anos, diversos tipos de ataques foram desenvolvidos para tentar quebrar sua segurança. Esses ataques variam em complexidade e abordagem, utilizando desde força bruta até cálculos matemáticos avançados, explorando vulnerabilidades em implementações inadequadas ou escolhas incorretas de parâmetros.

Aqui são exploradas algumas falhas e exercícios envolvendo-as, mas existem outras tais como ataques de chave compartilhada, utilização do teorema do resto chinês, que não serão abordadas.

Fatoração e números primos

Por que RSA usa números primos para p e q? De acordo com o teorema fundamental da aritmética, todo inteiro pode ser fatorado em potências de números primos de forma única para aquele número.

Quando escolhemos p e q primos, temos um número n já fatorado e que, se for grande o suficiente, se torna inviável para outros fatorarem, dependendo do tamanho do número. Se não forem primos, há mais de uma possibilidade de combinação para n, facilitando a quebra e dificultando a determinação exata dos parâmetros.

Outro fator importante é o tamanho desses números, eles devem ser grandes o suficiente para que sua fatoração seja inviável, devido ao tempo necessário para o cálculo.

Uma base de dados contendo diversas fatorações em números primos já calculadas pode ser encontrada em factordb.

Exercícios

• rsa-pop-quiz

Expoente pequeno

O valor do expoente e em RSA é arbitrário, desde que seja co-primo de φ(n).

Normalmente, é utilizado o número 65537, que é o maior Número Primo de Fermat, ou seja, que segue a fórmula 2^2^n + 1 com n = 4.

Ele é usado por ser grande o suficiente para não ser inseguro, mas pequeno o suficiente para manter os valores calculáveis, além da padronização de implementações ao longo do tempo.

Entretanto, se o expoente for pequeno o suficiente, é possível descobrir a mensagem facilmente:

• Se me < N, basta calcular a raiz: m = √(c).

• Se me > N, mas o expoente ainda for pequeno o suficiente, é possível realizar um ataque de força bruta para descobrir a mensagem, variando o valor de k na seguinte expressão:

  from gmpy2 import iroot
  m = iroot(ct, e)

Exercício: Desafio PicoCTF

Chave privada d pequena - Ataque de Wiener

Vamos supor que temos a chave pública (n, e). O Ataque de Wiener tenta determinar d a partir dessa chave.

Primeiro, converte-se a fração n/e em uma fração contínua [a0, a1, a2, ..., ak]. Em seguida, cada convergente da fração contínua é calculado e testado.

Para cada convergente:

1. Defina o numerador como k e o denominador como d.

2. Verifique se d é ímpar; se não, passe ao próximo convergente.

3. Verifique se ed ≡ 1 mod k; se não, prossiga.

4. Calcule φ(n) e use-o para encontrar as raízes do polinômio (x^2 - (n - φ(n) + 1)x + n). Se as raízes forem inteiras, d foi encontrado.

Uma implementação pode ser encontrada em CryptoHack

Código com a técnica já implementada:

import owiener

e = # complete com e
n = # complete com n

d = owiener.attack(e, n)

if d is None:
    print("Failed")
else:
    print("Hacked d={}".format(d))

Exercício: Desafio PicoCTF

Ataque de cifra escolhida (Chosen Ciphertext Attack)

Com uma mensagem criptografada C = m^e % n, escolhe-se uma outra mensagem r para criptografar com os mesmos parâmetros:

• C_escolhida = r^e % n

• Multiplica-se as duas: C_produto = C * C_escolhida

• Isso resulta em: C_produto = (m * r)^e % n

• Decriptando: (C_produto)^d = (m * r) % n

• Como r^ed % n = r % n, obtemos m * r % n

• Dividindo por r, encontramos m.

Ou seja, escolhemos uma mensagem a ser criptografada, multiplicamos ela pela mensagem criptografada original e decriptamos o produto das duas. Dividimos o resultado pela mensagem escolhida e encontramos a mensagem original.

Referências

• RSA Cipher - DCode

• FactorDB

• Wikipedia: 65537

• CryptoHack - Ataque de Wiener