## Twin

We are given the encryption of a message *m* with two RSA keys that share the same modulus *n* and two distinct exponents *e1* and *e2.* Our first thought is to try using a common modulus attack, which can help us find *m^(gcd(e1, e2)* which is *m^17* in our case and hope that *m^17* is small enough *(< n)* so that we can recover m from it. After some googling, we find some code [1] for the common modulus attack that we can modify to our needs.

[1] https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Common-Modulus/exploit.py

Here is the solve script.

```python
from Crypto.PublicKey import RSA
from binascii import hexlify
import math
from Crypto.Util.number import (
long_to_bytes,
bytes_to_long,
GCD
)
import gmpy2
from base64 import b64decode

import argparse
import sys

# Source: https://crypto.stackexchange.com/a/60404
def bytes_to_integer(data):
output = 0
size = len(data)
for index in range(size):
output |= data[index] << (8 * (size - 1 - index))
return output

def integer_to_bytes(integer, _bytes):
output = bytearray()
for byte in range(_bytes):
output.append((integer >> (8 * (_bytes - 1 - byte))) & 255)
return output

# Source: https://github.com/ashutosh1206/Crypton/blob/master/RSA-encryption/Attack-Common-Modulus/exploit.py
def egcd(a, b):
if (a == 0):
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

# Calculates a^{b} mod n when b is negative
def neg_pow(a, b, n):
assert b < 0
assert GCD(a, n) == 1
res = int(gmpy2.invert(a, n))
res = pow(res, b*(-1), n)
return res

# e1 --> Public Key exponent used to encrypt message m and get ciphertext c1
# e2 --> Public Key exponent used to encrypt message m and get ciphertext c2
# n --> Modulus
# The following attack works only when m^{GCD(e1, e2)} < n
def common_modulus(e1, e2, n, c1, c2):
g, a, b = egcd(e1, e2)
if a < 0:
c1 = neg_pow(c1, a, n)
else:
c1 = pow(c1, a, n)
if b < 0:
c2 = neg_pow(c2, b, n)
else:
c2 = pow(c2, b, n)
ct = c1*c2 % n
m = int(gmpy2.iroot(ct, g)[0])
return m

import sys
sys.setrecursionlimit(10000)
key1 = RSA.import_key(open('key1.pem','rb').read())
key2 = RSA.import_key(open('key2.pem','rb').read())
c1 = 198851474377165718028112972842265639215206348877016608622627311171042209963702835769614338398847455363946863082762173236373502223802847244557769309152020719377009343678096323767255545133734392981272835212545353488715110156427711111525743585480758640009319505322315888005188276904901023280620051538053743929669167795850860335549768969166461593906239357372330505433946129717041834475732372670961026001478227254999273718196250867204510681064391880099449164629711720021122445665846890550815079811041241824128791656795460007230003283109669795738520458565694688073372232365469969279979269172335621053156518588065204669164636568515585968088715299221616098448196835007486026306834585857385394379932580809203103023106229424720660096661585932612179471986633721231396764156601845262479014417201866703796806022479395694033815788446795158605478744234679438921219482709321859861288988156224563399413134218092016216147313958327131507901433719054874275160651556856183380492151746510052730242685874618761355215984376265719715473363476986957901445315504092719499838417381325617015369293491930133307630128865051357500960150518954750856507501366553062420719464692404538472137892443679198526541754483324903275970820090884602410278644781399298682978387326
c2 = 541940109836125333895781430104885967485013462238357425709353944075428304212181613346342168833632915771850317706081582413750750719712828061669251836467513116815496399077435572514863813419820177695716122433176805528532535188403726732767914692088563121640407878586264559446821905465347721083017105647280563402969518765808190495949892463753148040234604183497869168213134441134251591933907135463336654029223065998877557269475470179804195639035481928376550039377473960558788269310431313825888988908660191302311385846641723702093086996138971258640836061285893970041520552244977929645483977290602241276584136088984907441193129409236710662584843118801800457934169438121910252362434716190064236551302755562358860534549136237814085075287652312464795604230258140807652348468032431267225399615168922885291236301151723996369977845223020976025668767146139688511344868583917521559162297134719274102553947904603784500638033579530233721139319885875767560434666844423652986065991855466499543496592686627509183766091917402747468665062914322631033890742828511915046161646985793301031872822709060588586773552581644418553383314263000798086024158809854568189418235663070035600457464233007552461215491869285368208456103672933515573777187729174614608959934215

m_17 = common_modulus(key1.e, key2.e, key1.n, c1, c2)

print(long_to_bytes(m_17))
```

Flag: `ENO{5har1ng_is_n0t_c4r1ng}`