This is what we're given
```from Crypto.Util.number import *p=getPrime(512)q=getPrime(512)n=p*qe1=71e2=101msg=bytes_to_long(b'UDCTF{REDACTED}')c1 = pow(msg, e1, n)c2 = pow(msg, e2, n)print(n)print(e1)print(e2)print(c1)print(c2)```
Check out [https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-1/](http://) for a hint if you still want to try and figure it out yourself.  
We're given two ciphertexts. According to the given RSA textbook, it seems like we can just solve this by solving Bezout's identity!  This comes from the following proof:  
	If gcd(e1, e2) = 1, then according to Bezout's identity, there exist integers a and b such that a * e1 + b * e2 = 1.	Therefore, we have the following:	c1 = m ^ e1 (mod n) ==> c1 ^ a = m ^ (e1 * a) (mod n)	c2 = m ^ e2 (mod n) ==> c2 ^ b = m ^ (e2 * b) (mod n)	c1 * c2 = m ^ (e1 * a + e2 * b) (mod n) = m ^ 1 (mod n) Therefore, we just need to solve Bezout's identity to get m. In order to solve Bezout's identity, you can use the extended Euclid algorithm.  [https://www.rookieslab.com/posts/extended-euclid-algorithm-to-find-gcd-bezouts-coefficients-python-cpp-code](http://) provides the code for the extended Euclid algorithm.  
	UDCTF{3uc1id_th4_60at}
```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=87587426608653108851564813489752475287019321764561555461700901651463446024854423042554629096780987943450742890279417241231211446818009232077230407281610183609540264821974669679932743621434901779832901512681108061652309435608446510337833028029876549629818957952682516026313018526405972829923620377438164377109e1=71e2=101c1=1421275848974615267320815554113040672023972283807752574007971561416386636110464890632994733734995114229161525885389065244354678964389211537085513310823751266472044865745324866096898051759507738772227296453397678055024824805366251635154522059070310922367078281343183508274450904681187384450253350434931649011c2=26097095086985946477598349002260598942399303275420948828501512467473619292573670218058274201990116295246084096584962695127706609264424951086000719935218496250047555039460733768633688410770610612614744411304261153778159881980276162174277085197608466835857196307432992312260307797540746411319330318058866868362
#ax + by = 1gcd, x, y = extended_euclid_gcd(e1, e2)m = (pow(c1, x, n) * pow(c2, y, n)) % nm = format(m, 'x')for i in range(0, len(m), 2):    print(chr(int(m[i:i+2], 16)), end='')```