Rating:

## 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.

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)

Flag: ENO{5har1ng_is_n0t_c4r1ng}