This is what we're given

```
from Crypto.Util.number import *
p=getPrime(512)
q=getPrime(512)
n=p*q
e1=71
e2=101
msg=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=87587426608653108851564813489752475287019321764561555461700901651463446024854423042554629096780987943450742890279417241231211446818009232077230407281610183609540264821974669679932743621434901779832901512681108061652309435608446510337833028029876549629818957952682516026313018526405972829923620377438164377109
e1=71
e2=101
c1=1421275848974615267320815554113040672023972283807752574007971561416386636110464890632994733734995114229161525885389065244354678964389211537085513310823751266472044865745324866096898051759507738772227296453397678055024824805366251635154522059070310922367078281343183508274450904681187384450253350434931649011
c2=26097095086985946477598349002260598942399303275420948828501512467473619292573670218058274201990116295246084096584962695127706609264424951086000719935218496250047555039460733768633688410770610612614744411304261153778159881980276162174277085197608466835857196307432992312260307797540746411319330318058866868362

#ax + by = 1
gcd, x, y = extended_euclid_gcd(e1, e2)
m = (pow(c1, x, n) * pow(c2, y, n)) % n
m = format(m, 'x')
for i in range(0, len(m), 2):
print(chr(int(m[i:i+2], 16)), end='')
```