Noise (ictf Round 49)

RSA Coppersmith small roots

Challenge overview

In this CTF challenge we are given the following encryption script

from Crypto.Util.number import *
import random

p, q = getPrime(2048), getPrime(1024)
n = p * q
e = 0x10001

noisy, noisier = random.randint(1, 2**12), random.randint(1, 2**512)

with open("flag.txt", "rb") as f:
    flag = f.read().strip()

m = bytes_to_long(flag)
c = pow(m, e, n)

gift = noisy * p + noisier

print(f"{n=}")
print(f"{c=}")
print(f"{e=}")
print(f"{gift=}")

As well as the output:

n=2210207631834878306977610331587079414688726953852127891743978241115467417514094490885566596532764649734820781875162772076016465849910335495372655172642859051060956584290873279160663067803174918451720322838557173843633878071295344210911196115990053284420290269638208349629325617519702019624501487443701298384672014340985699408886396495620058467232100228731856574068359498427202897094625763145751714585179102627870557248970789486442471319505178102443916262883081617756026976865185419952047507555024806306004206204042146093305086341414121101850799333552467591600959030784159616150021083233109658306508752117033405807640546353541158685254561969331091010971880374397106345601382073403759349417748413427393638774935665402411809081311678970683509810197459847560263116215959674274648782638547882565264544675777393850180083460661862299374321637799493291320411669948548144915613244602771858777564064822457745520136074892686631201535629
c=79439884742083711071755708487414199227960981699158038243609142136149459074237967818193044573408796991464893562991427356744294371475148385737143807007504892071879989044266659035575563987497090782335686903156254372768431356367418614020286355521959397788294292899973119817539182954396015903303725571977137543596186210469780857742751071840507978622305859250707777868161458398620843538940309027698509455591823032948634850046109079854184348132280034164050803222199373753935223739099032044266536568184980008630458622800613158348155826201215465471666029712694113256326735123264023294318770217642927129637551823218005993221538797660621438082190763601605266305238235566305280859661354507510659899045052637616359654240690250951805447842902044413272339036945387447645766924762392584002031869390162781669350528181577055491871204217667526325081714043586669414455262130528301349828288629641304620478812606124138969628375055191143814322641
e=65537
gift=76161898251767442700733157555848818813603954596961294098824533307067668835961954000479299659153714638772058129913954467688624803595944141139373250325395786662059257969706539819120584005106522589094454995565373852400017032856812097418510354121690769294765707631393606366289280283451782627364805828863775680443955954083274513766771291143807920615369032763512859350304599713181948381282632555462948635135094538099931625876301604238310194450086512286119571690086064406403874078915448155800917929395528944094970903688886559478191636291079886098726158646354963419686358844253161736807644626698053019138548522750953514577562660

We are given a hint $noisy \cdot p + noisier$ where the noise terms are 12 bits and 512 bits respectively.

Recovering p

We also notice that the prime factor $p$ is 2048 bits, while $q$ is just 1024 bits. This means the noise terms are quite small compared to $p$ itself. Lets denote the noise terms as $a$ and $b$:

\[\large gift = a\cdot p+b\]

If we can recover the noise $b$, we can recover $a\cdot p$ and then use $gcd$ to recover the prime factors.

To do this, we can set up a univariate polynomial and solve for the unknown x:

P.<x> = PolynomialRing(Zmod(N))
roots = (gift - x).monic().small_roots(2^512, 0.66)
y = gift - roots[0]
p = int(gcd(y, N))

From here, decryption is simple:

q = N // p
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
print(bytes.fromhex(f"{pow(c,d,N):x}").decode())

Which gives us our flag:

ictf{recover_it_using_continued_fraction_b7b85f8e}

Solve.py

N=2210207631834878306977610331587079414688726953852127891743978241115467417514094490885566596532764649734820781875162772076016465849910335495372655172642859051060956584290873279160663067803174918451720322838557173843633878071295344210911196115990053284420290269638208349629325617519702019624501487443701298384672014340985699408886396495620058467232100228731856574068359498427202897094625763145751714585179102627870557248970789486442471319505178102443916262883081617756026976865185419952047507555024806306004206204042146093305086341414121101850799333552467591600959030784159616150021083233109658306508752117033405807640546353541158685254561969331091010971880374397106345601382073403759349417748413427393638774935665402411809081311678970683509810197459847560263116215959674274648782638547882565264544675777393850180083460661862299374321637799493291320411669948548144915613244602771858777564064822457745520136074892686631201535629
c=79439884742083711071755708487414199227960981699158038243609142136149459074237967818193044573408796991464893562991427356744294371475148385737143807007504892071879989044266659035575563987497090782335686903156254372768431356367418614020286355521959397788294292899973119817539182954396015903303725571977137543596186210469780857742751071840507978622305859250707777868161458398620843538940309027698509455591823032948634850046109079854184348132280034164050803222199373753935223739099032044266536568184980008630458622800613158348155826201215465471666029712694113256326735123264023294318770217642927129637551823218005993221538797660621438082190763601605266305238235566305280859661354507510659899045052637616359654240690250951805447842902044413272339036945387447645766924762392584002031869390162781669350528181577055491871204217667526325081714043586669414455262130528301349828288629641304620478812606124138969628375055191143814322641
e=65537
gift=76161898251767442700733157555848818813603954596961294098824533307067668835961954000479299659153714638772058129913954467688624803595944141139373250325395786662059257969706539819120584005106522589094454995565373852400017032856812097418510354121690769294765707631393606366289280283451782627364805828863775680443955954083274513766771291143807920615369032763512859350304599713181948381282632555462948635135094538099931625876301604238310194450086512286119571690086064406403874078915448155800917929395528944094970903688886559478191636291079886098726158646354963419686358844253161736807644626698053019138548522750953514577562660

P.<x> = PolynomialRing(Zmod(N))
roots = (gift - x).monic().small_roots(2^512, 0.33)
y = gift - roots[0]
p = int(gcd(y, N))
q = N // p
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
print(bytes.fromhex(f"{pow(c,d,N):x}").decode())

Alternate solution using continued fractions

While I solved this challenge using univariate coppersmith, the intended solution seems to be continued fractions:

from fractions import Fraction
from math import gcd

n=2210207631834878306977610331587079414688726953852127891743978241115467417514094490885566596532764649734820781875162772076016465849910335495372655172642859051060956584290873279160663067803174918451720322838557173843633878071295344210911196115990053284420290269638208349629325617519702019624501487443701298384672014340985699408886396495620058467232100228731856574068359498427202897094625763145751714585179102627870557248970789486442471319505178102443916262883081617756026976865185419952047507555024806306004206204042146093305086341414121101850799333552467591600959030784159616150021083233109658306508752117033405807640546353541158685254561969331091010971880374397106345601382073403759349417748413427393638774935665402411809081311678970683509810197459847560263116215959674274648782638547882565264544675777393850180083460661862299374321637799493291320411669948548144915613244602771858777564064822457745520136074892686631201535629
c=79439884742083711071755708487414199227960981699158038243609142136149459074237967818193044573408796991464893562991427356744294371475148385737143807007504892071879989044266659035575563987497090782335686903156254372768431356367418614020286355521959397788294292899973119817539182954396015903303725571977137543596186210469780857742751071840507978622305859250707777868161458398620843538940309027698509455591823032948634850046109079854184348132280034164050803222199373753935223739099032044266536568184980008630458622800613158348155826201215465471666029712694113256326735123264023294318770217642927129637551823218005993221538797660621438082190763601605266305238235566305280859661354507510659899045052637616359654240690250951805447842902044413272339036945387447645766924762392584002031869390162781669350528181577055491871204217667526325081714043586669414455262130528301349828288629641304620478812606124138969628375055191143814322641
e=65537
gift=76161898251767442700733157555848818813603954596961294098824533307067668835961954000479299659153714638772058129913954467688624803595944141139373250325395786662059257969706539819120584005106522589094454995565373852400017032856812097418510354121690769294765707631393606366289280283451782627364805828863775680443955954083274513766771291143807920615369032763512859350304599713181948381282632555462948635135094538099931625876301604238310194450086512286119571690086064406403874078915448155800917929395528944094970903688886559478191636291079886098726158646354963419686358844253161736807644626698053019138548522750953514577562660

frac = Fraction(n, gift).limit_denominator(4096)
p = gcd(n, frac.numerator)                  
q = n // p
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
print(bytes.fromhex(f"{pow(c,d,n):x}").decode())