Add known MSB CRT exponents - RSA

[D-Cryp7]

Hello! I just implement the MSB case that is described in this paper: https://eprint.iacr.org/2022/271.pdf (Section 3.1 and 3.3), and i would like to contribute to the project, hope this helps!

[jvdsn]

@D-Cryp7 do you have any test cases that you used this attack for? To verify it works?

[D-Cryp7]

@jvdsn Sure! I just prepared more general test cases right now, so sorry for the delay in my response, here you go:

from sage.all import PolynomialRing, GF, Zmod, gcd, ceil, is_prime
from Crypto.Util.number import getPrime, GCD, bytes_to_long
from random import uniform

def attack(e, N, dp_msb, dq_msb, dp_msb_bit_length, dq_msb_bit_length, delta_upper_bound):
    """
    Generates prime factors for a modulus, if the MSB of dp and dq are known.
    More information: Alexander M., Julian N., Santanu S., "Approximate Divisor Multiples - Factoring with Only a Third of the Secret CRT-Exponents"
    :param e: public exponent
    :param N: public modulus
    :param dp_msb: most significant bits (MSB) of d mod p - 1 
    :param dq_msb: most significant bits (MSB) of q mod p - 1 
    :param dp_msb_bit_length: the bit length of dp_msb
    :param dq_msb_bit_length: the bit length of dq_msb
    :param delta_upper_bound: upper bound of delta, defined below
    :return: the prime factors of N = p * q

    Constraints:
    - We will set the public exponent bit length (e) as log2(N) * alpha, where 0 < alpha < 1
    - Then, the unknown LSBs of dp and dq are upper bound in bit length by log2(N) * delta
    - delta < (1/2) - 2 * alpha
    """

    # https://stackoverflow.com/questions/14822184/is-there-a-ceiling-equivalent-of-operator-in-python
    A_hat = -(2**(dp_msb_bit_length + dq_msb_bit_length) * e**2 * dp_msb * dq_msb // -N) # A_hat = kl

    x, = GF(e)["x"].gens()
    poly = x**2 - (1 - A_hat*(N - 1)) * x + A_hat

    k_roots = poly.roots()

    for root in k_roots:
        k = int(root[0])
        a = (e * dp_msb * 2**dp_msb_bit_length + k - 1) * pow(e, -1, k * N) % (k * N)

        dp_lsb, = Zmod(k * N)["dp_lsb"].gens()
        poly = dp_lsb + a

        dp_roots = poly.small_roots(X = 2**dp_msb_bit_length, beta = delta_upper_bound)
        print(dp_roots)
        if dp_roots:
            dp = int(dp_roots[0]) + a
            p = int(gcd(dp, N))
            q = N // p

            assert N == p * q
            return p, q

    return "Attack failed, make sure that your params satisfies the constraints."

def keygen(bits):
    # alpha must be between 0 and 1/4 (non inclusive)
    alpha = uniform(0, 0.25)

    # e is bounded (in bits) by N^alpha
    while True:
        e = getPrime(int(bits * alpha))

        p, q = [ getPrime(bits // 2) for i in range(2) ]

        try:
            dp = pow(e, -1, p - 1)
            dq = pow(e, -1, q - 1)
            break

        except:
            continue

    # dp and dq LSBs are upper bound by N^delta
    delta_upper_bound = min(1/4 + alpha, 1/2 - 2*alpha)
    delta = uniform(0, delta_upper_bound)

    dp = dp >> int(bits * delta)
    dq = dq >> int(bits * delta)

    return e, p * q, dp, dq, int(bits * delta), delta_upper_bound

e, N, dp, dq, bits, delta_upper_bound = keygen(2048)

print(attack(e, N, dp, dq, bits, bits, delta_upper_bound))

The experimental results described in the paper shows some relation between the public exponent $e$ bits and the unknown MSB bits of $d_p$ and $d_q$, some frontier cases may not work such as small $e$ and a bigger amount of unknown MSB bits that the paper shows that are difficult to solve. We can also assume that $d_p$ and $d_q$ unknown MSB bits are different in quantity, but i didn't test that much at the moment.

[jvdsn]

Thanks for the PR, I merged it in but made some updates to your code to make it more consistent with existing code.