4 ms·
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 t
by pbsd 4y ago
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 https://en.wikipedia.org/wiki/Coppersmith_method
- Moodles 4y agoPretty 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 4y agoThere 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 4y agoRight, 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?