# Source:
```
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, inverse
import random

FLAG = b'HTB{--REDACTED--}'
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 257

def encrypt_flag():
a = random.getrandbits(1024)
b = random.getrandbits(1024)

flag = bytes_to_long(FLAG)

msg = a*flag + b

ct = pow(msg, e, n)
return {'ct': format(ct, 'x'), 'n': format(n, 'x'), 'e': format(e, 'x'), 'a': format(a, 'x'), 'b': format(b, 'x')}
```

# Solve:

We get given an encryption endpoint that returns encrypted flags of the form $a\times flag +b$ . This looks very vunerable to the Franklin-Reiter related message attack, an attack on rsa where we have two messages of the form: $$m_2 = f(m_1)$$ $$f(x)=ax+b$$ Given we know the values of the two coefficients $a$ and $b$, we now just have to write an implementation of the related message attack. We chose to write ours in sage as it had most of the functionality that we needed out of the box, lacking only a composite modulus GCD function, so we added that in, and solved.

### Solve Script:
```
from sage.all import *
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, inverse
n = 27455407323096989038707767967686788128008040912285545191387752268045317651747009835336335934721647728929368413771708021590017001701685605010158159340248147881838091203465902621173423102828450192332868018317626964451022022797426915076514125033325893379676566905882622894645763669679437179606451958893184575351580869947763575019642582589131333599965675465728981486404917292660472287659943714967905478878972693846981984913573405737593977612095060716048945868600660962884058371915932122224080461928865642901912874293789696054876984849520438875571755985635947551171628800328937534487687113359830492533808905556525003285723
e = 257
c1 = 13039835730636339059279958629414823958600374640153694710603769941841518717581360908757773582298464997543074450567895944502732083868197684496322773743479443155491660211824842330124728330817239124246559627986248222933867912873621199849101953018562009389886860550048918723791430586350508953135377334349772919786563924615561623187867575173451970331797021441502419837435021782053678509297405767346740736858302277939287915674474740685224802423994133044840443776449605979021778641728531855113113529139203952004517841123829567331278176593468732780726572662067124530362015808758018569001370555297733983204615105861791351356731
a1 = 73323678190387475566655162681387285442675714073813354329706337231179508215603433977744256603023254369717277375737324792403467068433618758479771850252465621296064960246850519217638256731790467702937921688376261486958909520559768188700040467463128950645760425706624061234056439016504795859156284251967734529951
b1 = 142949604479152405191048291376099557919804066455335447005610027694379178456845348463740002155265925494645432447046929781523190202401807171869608565742847957149162207794858599211086795519482954081833968987901619262611254182810036394725846352635957893826237592257956289562496629026088501148243608852262643046056
c2 = 16284330675633348199222170379465883288561319494598330947983412207685634623843464942181310571306831518612390141673621578732060935977299457401229101993678518863415779223778262194300919071904675770789729384044332448259035292396190449696083322628041972412377614598831305840347941366744787999018143821487587053333368002207209042628857937907164388531570176431651158053692913697858298257329016481126695284381207733656727759391420312284966834283188928609911930656568734666487016403546747841821964014888760826282374198549421390690267777329510243586936408302681732989153021997287157804477355788317532636996505965169243880478983
a2 = 111893252295533622460529880561016753553721891960638416129928977326805030144732594122713679236926670288372779486403117262482249990036203251128598076637159136329972492793910646059117856465947889764220882138906278997387299821180021965404639491156097504602716790789227147098147104444258018294862237772781568546079
b2 = 164425395105389083814080728419218571462360295781439032477268517576679703055124348503558821511959033494657567259358335198199919194958639894580766293840656642675917406273972816175684673389980747286587581804206851486678589023687537904525870220430204594586471316653906517700363472653187050885828329745846816757381

def compositeModulusGCD(a, b):
if(b == 0):
return a.monic()
else:
return compositeModulusGCD(b, a % b)

def FranklinReiter(n, e, c1, c2, a1, a2, b1, b2):
P.<x> = PolynomialRing(Zmod(n))
f = (a1*x+b1)^e - c1
g = (a2*x+b2)^e - c2
m = Integer(n-(compositeModulusGCD(f,g)).coefficients()[0])
return m

print(long_to_bytes(FranklinReiter(n, e, c1, c2, a1, a2, b1, b2)))
```

#### Flag: `HTB{f1n1t3_d1ff3r3nc35_134d_70_r31473d_m355493_4774ck5}`