Corrupted Key - Blue Hat Cup 2022

Challenge:

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

Where \(u = q^{-1}\ mod\ p,\ and\ dq = d\ mod\ (q-1)\)

Solve:

\[dq \cdot e \equiv d \cdot e\ mod\ (q-1)\] \[dq \cdot e \equiv 1\ mod\ (q-1)\] \[dq \cdot e - 1 = k\ (q-1)\]

Check how many bits of dq we have:

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

So, \(dqlow = dq\ mod\ 2^{120}\)

\[dq \cdot e + k - 1 = k \cdot q\] \[dqlow \cdot e + k - 1 \equiv k \cdot q\ (mod\ 2^{120})\] \[k^{-1} \cdot (dqlow \cdot e + k - 1) \equiv q\ (mod\ 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}\ mod\ p\] \[u \cdot q \equiv 1\ mod\ 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\ (mod\ 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 + qlow\]

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