Here's what we're given:```from Crypto.Util.number import *p=getPrime(1024)q=getPrime(1024)n=p*qe1=32e2=94msg=bytes_to_long("REDACTED")assert(pow(msg,2) < n)c1 = pow(msg, e1, n)c2 = pow(msg, e2, n)print(n)print(e1)print(e2)print(c1)print(c2)```
This is suspiciously similar to grade 3 RSA ([https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/](http://) elaborates on the method behind it), only that e1 and e2 do not have a GCD of 1. But wait, check this code out:assert(pow(msg,2) < n)
This seems to tell us that the square of the message is less than 2. So, what if we just find m^2 and then take the square root of that?
Note that we can slightly modify Bezout's identity to the following:
	2ax + 2by = 2
If we divide e1 and e2 by 2, it gives a = 16 and b = 47, which are coprime to each other.Hence, we can do a bit of math to prove that we can get m^2
	c1 = (m ^ e1) % n, c2 = (m ^ e2) % n	[(c1 ^ x) % n] * [(c2 ^ y) % n] = (m ^ (e1 * x + e2 * y)) % n = (m ^ (2a * x + 2b * y)) % n = (m ^ 2) % n
Therefore, we can get m^2! To find m from that, we can use gmpy2's iroot function to get an integer square root.
	UDCTF{l4rg3_int3ger_sqrt_w1th0ut_fl04ts}
The implemenation follows below:
```import gmpy2
def extended_euclid_gcd(a, b):    """    Returns a list `result` of size 3 where:    Referring to the equation ax + by = gcd(a, b)        result[0] is gcd(a, b)        result[1] is x        result[2] is y     """    s = 0; old_s = 1    t = 1; old_t = 0    r = b; old_r = a
    while r != 0:        quotient = old_r//r # In Python, // operator performs integer or floored division        old_r, r = r, old_r - quotient*r        old_s, s = s, old_s - quotient*s        old_t, t = t, old_t - quotient*t    return [old_r, old_s, old_t]
n = 15144989296069059933372368453196092175005161975349151110345314566785160131088640293080496647831336241835434081246752372095089223274410617149601529995353586979709767320781773241635911841825135157128620635284850556358212336804356913383250552153118005157608892746468253056994929497147176358510660250974046147584489593314250043332900225627695013699452589204281775937461626931870469970564649337891804670484615877731064389199146553155645996166903057997780769847954473558252319887360004797752922471164238094762917170732419058459198871816368754874928563582062094607146743861963241102686280889624636580265012154494857871226911e1=32e2=94c1=517413713703886999866857886363089094585257050613499021392236739949207714015445698823055234855661713319078211477553629447153099784179447532323740595057178898139959674381355432131055787089201673781698752057672521217038516832753572594045829378268006522196608125682968252235804171902500675561571516482830716057356093346644739755000641419389456649384154636696468100735075639775740773984117668523785494430624107703773927953688140653884319491595701619752757483259322185639861570200460175036940484201361523531829151771132059047908439112074722779866239565825707838090161372153338024174748440497243107864663782108641727771659c2=7627448403143228380990811828784190441589966806784538493012623116575366382931836531487460665746937844089811800210162413422176546183916362252942569359187329261606901744873414894672206518833504277712248120517227097337821671357183002903689123275299969496743046843235865472598002895668376113637844709030956945481612135136663699655327584977008477587437014970931004029432308882904616641276931607404737262279319635052041442201857436898171408177118684300765925831306704477989772422231625570934627171304088385754161129883791893955034648200851254688716049371226939666530556140959866437156338956068301001303202802889970914365861
# ax + by = 1gcd, x, y = extended_euclid_gcd(e1//2, e2//2)m = (pow(c1, x, n) * pow(c2, y, n)) % nm = gmpy2.iroot(m, 2)[0]m = format(m, 'x')for i in range(0, len(m), 2):    print(chr(int(m[i:i+2], 16)), end='')```