Corrupted Key - Blue Hat Cup 2022

Challenge:

n = 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961
e = 65537
c = 96458723724899437870554342796876171017896652413964521193266438981853945238446913579867464909353925601873532290626111170073532116639383463734148270579305067733147411306325252107181823453497914478588342362177625026365513002442585949837516090367171824895036711246039928723021679235071368954348296729327873680822
u = 11889246144866782519155392157369478059715977597114885585873502852127888907191116911762955888968046505980125449346852147369649024143226438553109462231463320
dq_low = 1043891160170747082120115133012365745

Where $u = q^{- 1} m o d p, a n d d q = d m o d (q - 1)$

Solve:

d q \cdot e \equiv d \cdot e m o d (q - 1)

d q \cdot e \equiv 1 m o d (q - 1)

d q \cdot e - 1 = k (q - 1)

Check how many bits of dq we have:

print(len(bin(dq_low)[2:]))
# 120

So, $d q l o w = d q m o d 2^{120}$

d q \cdot e + k - 1 = k \cdot q

d q l o w \cdot e + k - 1 \equiv k \cdot q (m o d 2^{120})

k^{- 1} \cdot (d q l o w \cdot e + k - 1) \equiv q (m o d 2^{120})

Now we can solve the lower 120 bits of q.

Since dq·e = k(q-1)+1, and q-1 > dq, k < e.

So we only have to iterate from k=1 to k=e.

for k in range(1, e):
	try:
		q_low = (pow(k, -1, 2**120) * (dq_low * e + k - 1)) % (2**120)
	except:
		continue

	...

Next to recover q:

u = q^{- 1} m o d p

u \cdot q \equiv 1 m o d p

u \cdot q - 1 = k \cdot p

u \cdot q^{2} - q = k \cdot p \cdot q

u \cdot q^{2} - q = k \cdot n

u \cdot q^{2} - q (m o d n) = 0

So we can apply small_roots to u·q^2-q

Now check size of n:

print(len(bin(n)[2:]))
# 1024

So q should be 512 bits. q_low is 120 bits, so

q = 2^{120} \cdot x + q l o w

and we should search up to

X = 2^{512 - 120}

from Crypto.Util.number import long_to_bytes 
from Crypto.PublicKey import RSA  
from Crypto.Cipher import PKCS1_OAEP  
from tqdm import tqdm  
  
n = 151036135413139226687867011199700639084856588533884431118047808395603993635242690166659649156476428533386350427603713487259266502837260466348398817558768025404903682189934563578605367223796247470920497617904900418615352839562681665973088711089128789315193951623751145385357347144960284983398745189236464272961  
e = 65537  
c = 96458723724899437870554342796876171017896652413964521193266438981853945238446913579867464909353925601873532290626111170073532116639383463734148270579305067733147411306325252107181823453497914478588342362177625026365513002442585949837516090367171824895036711246039928723021679235071368954348296729327873680822  
u = 11889246144866782519155392157369478059715977597114885585873502852127888907191116911762955888968046505980125449346852147369649024143226438553109462231463320  
dq_low = 1043891160170747082120115133012365745  
  
for k in tqdm(range(1, e)):  
    #k = 59199  
    try:  
        q_low = (pow(k, -1, 2**120) * (dq_low * e + k - 1)) % (2**120)  
        q_low = int(q_low)  
    except:  
        continue  
  
    PR.<x> = PolynomialRing(Zmod(n))  
    qq = 2**120 * x + q_low  
    f = u*qq**2 - qq  
    xx = f.monic().small_roots(X=2**(512-120))  
    if xx:  
        xx = xx[0]  
        q = 2**120 * xx + int(q_low)  
        q = int(q)  
        p = n // q  
        d = pow(e, -1, (p-1)*(q-1))  
        rsa = RSA.construct((int(n),int(e),int(d),int(p),int(q)))  
        print(PKCS1_OAEP.new(rsa).decrypt(long_to_bytes(c)))  
        break