Here's what we're given:
```
from Crypto.Util.number import *
p=getPrime(1024)
q=getPrime(1024)
n=p*q
e1=32
e2=94
msg=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 = 15144989296069059933372368453196092175005161975349151110345314566785160131088640293080496647831336241835434081246752372095089223274410617149601529995353586979709767320781773241635911841825135157128620635284850556358212336804356913383250552153118005157608892746468253056994929497147176358510660250974046147584489593314250043332900225627695013699452589204281775937461626931870469970564649337891804670484615877731064389199146553155645996166903057997780769847954473558252319887360004797752922471164238094762917170732419058459198871816368754874928563582062094607146743861963241102686280889624636580265012154494857871226911
e1=32
e2=94
c1=517413713703886999866857886363089094585257050613499021392236739949207714015445698823055234855661713319078211477553629447153099784179447532323740595057178898139959674381355432131055787089201673781698752057672521217038516832753572594045829378268006522196608125682968252235804171902500675561571516482830716057356093346644739755000641419389456649384154636696468100735075639775740773984117668523785494430624107703773927953688140653884319491595701619752757483259322185639861570200460175036940484201361523531829151771132059047908439112074722779866239565825707838090161372153338024174748440497243107864663782108641727771659
c2=7627448403143228380990811828784190441589966806784538493012623116575366382931836531487460665746937844089811800210162413422176546183916362252942569359187329261606901744873414894672206518833504277712248120517227097337821671357183002903689123275299969496743046843235865472598002895668376113637844709030956945481612135136663699655327584977008477587437014970931004029432308882904616641276931607404737262279319635052041442201857436898171408177118684300765925831306704477989772422231625570934627171304088385754161129883791893955034648200851254688716049371226939666530556140959866437156338956068301001303202802889970914365861

# ax + by = 1
gcd, x, y = extended_euclid_gcd(e1//2, e2//2)
m = (pow(c1, x, n) * pow(c2, y, n)) % n
m = 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='')
```