[pbsd]

Look at how RSA CRT decryption works:

    m_1 = c^d_p mod p
    m_2 = c^d_q mod q
    h = (m_1 - m_2)*q^-1 mod p
    m = m_2 + h * m_1

If m < q, m_2 = m and there is nothing left to add. But if m >= q, there needs to be something to add, and this something will very likely be wrong and kind of random, because q^-1 mod p is wrong. The distinguisher between the two cases hinges on the upper bits of the decryption result being (non-)0. So for this attack to work all you have to do is change any part of q^-1; it doesn't really matter much what the change is.

Now you have a binary search oracle for q, from which you can iteratively obtain the most significant bits of q, one guess at a time (e.g., try m = 2^1024 first, then (2^1024 or 0) + 2^1023, etc). Once you have half of the most significant bits of q, you can use the Coppersmith method [1] to find a small root of f(x) = msb(q) + x modulo a divisor of n and thus recover the rest of q.

In reality doing exactly 512 iterations of guessing plus Coppersmith is pretty costly; if possible, guessing a few more bits will make the Coppersmith step much faster.

[1] https://en.wikipedia.org/wiki/Coppersmith_method

[Moodles]

Pretty elucidating, thanks.

Could you just elaborate on the part:

> If m < q, m_2 = m and there is nothing left to add.

Why is this? What is d_p? d mod p?

[pbsd]

There is nothing left to add because m_2 is already the correct value:

- If m is also < p, then (m_1 - m_2) is obviously 0, and so will be h.

- If m >= p, then m must be of the form m_1 + k * p for some k. But we've already established that m = m_2, so m_1 - m_2 = (m - k * p) - m_2 = -k * p = 0 mod p. Thus h = 0.

So regardless of the value of qinv, we get m verbatim if it's less than q. d_p and d_q are d mod (p-1) and d mod (q-1) respectively.

Here, this Sage script is short enough that it all fits in a comment. I guess 624 bits and recover the remaining 400 with Coppersmith; this is fast enough to run in a few seconds.

    def oracle(c, d, p, q, qinv):
        m_1 = power_mod(c, d % (p-1), p)
        m_2 = power_mod(c, d % (q-1), q)
        h = (m_1 - m_2)*qinv % p
        m = m_2 + h * m_1
        return (m >> (211*8)) != 0 # check if sid != 0

    # Setup
    p = random_prime(2^1024, lbound=2^1023+2^1022)
    q = random_prime(2^1024, lbound=2^1023+2^1022)
    n = p*q
    e = 65537
    d = inverse_mod(e, (p-1)*(q-1))
    qinv = inverse_mod(q, p) + randint(0, 2^128) # random error block inserted in the least significant 128 bits

    msb_q = 0
    for bit in reversed(range(400, 1024)):
        # if m < q, we are within range
        if not oracle(power_mod(msb_q + 2^bit, e, n), d, p, q, qinv):
            msb_q += 2^bit

    # Find a small root of msb_q  + x modulo a divisor of n of size ~n^(1/2)
    P.<x> = Zmod(n)[]
    f = msb_q + x
    [lsb_q] = f.small_roots(beta=0.49, epsilon=1/32)
    # Check we've reached the correct solution
    assert(q == msb_q + lsb_q)

[Moodles]

Right, but my question is, why is it the correct value? There's some math theorem which makes it true?

m_2 = c^d_q mod q

    = m^(e * d_q) mod q

    = m because?

[pbsd]

That's just how RSA works, via Fermat's little theorem: e * d_q mod (q-1) = 1, so m^(e * d_q) mod q = m^1 mod q = m.

[Moodles]

Got it, thank you!