# Description
Franklin gave birth to the amazing show blacklist but before he leaves the stage he left us some few words as well as a certain machine that generates encrypted messages


## Files
- `main.py`
- `message.py`

# Solution
- Looking at the challenge files, we see that `main.py` is very similar to the one supplied with the challenge **the_messager** but with a slight twist, Here's how the code in `main.py` looks like :
```python
from Crypto.Util.number import bytes_to_long, getStrongPrime
from math import gcd
from flag import FLAG
from Crypto.Random import get_random_bytes

def encrypt_message(m):
return pow(m,e,N)

def advanced_encrypt(a,m):
return encrypt_message(pow(a,3,N)+(m << 24))

e = 3
p = getStrongPrime(512)
q = getStrongPrime(512)

# generate secure keys
result = 0
while (result !=1):
p = getStrongPrime(512)
q = getStrongPrime(512)
result = gcd(e,(p-1)*(q-1))

N = p * q

print("N = " + str(N))
print("e = " + str(e))

rand = bytes_to_long(get_random_bytes(64))

ct = []
ct.append(encrypt_message(rand << 24))

for car in FLAG:
ct.append(advanced_encrypt(car,rand))

print("ct = "+str(ct))
```
- After examining the code, we notice that strange `advanced_encryption` function that does some operations to the ciphertext after encrypting, it basically mixes a 512 bit random number into the process. Or, to be precise, if $r$ is that random number then $r = r<<24 = r*2^{24}$ is used for encryption.
- Looking at the output file, we can see that we have an array of ciphertexts, and by examining `main.py` we surely know it's encrypting the flag character by character
- To better understand how the `advanced_encryption` works, we can understand it like this :

1 - if we want to encrypt the letter `a`, we'll normally do it in RSA like this : $c = a^{3}$ mod $N$ (with $e = 3$)

2 - some additional operations are done to produce an output that we can call $l$ : $l = (c + r')^{3} = c^{3} + 3c^{2}r' + 3cr'^{2} + r'^{3}$

3 - Since we know the flag format which is `CyberErudites{}`, we know $l$ and $c$ for the first 14 ciphertexts and we also know $r'^{3}$ mod $N$ which is the first element in our list. If we can calculate $r'$ we can simply encrypt all letters and recover the flag.

- This is known as the Franklin-Reiter attack on RSA, it basically states that if two messages differ only by a known fixed difference between the two messages and are encrypted under the same modulus $N$, then it is possible to recover both of them.

- If we wanna get $r$, we can solve two equations with our knowledge of the first two ciphertexts and $r'^{3}$, treating the exponents of $r'$ as independent variables we have a system of two linear modular equations in two variables which is solvable. I wrote a sage script that solves for $r'$ :
```sage
N = 128704452311502431858930198880251272310127835853066867118127724648453996065794849896361864026440048456920428841973494939542251652347755395656512696329757941393301819624888067640984628166587498928291226622894829126692225620665358415985778838076183290137030890396001916620456369124216429276076622486278042629001
e = 3
R = 21340757543584301785921441484183053451553315439245254915339588451884106542258661009436759738472587801036386643847752005362980150928908869053740830266273664899424683013780904331345502086236995074501779725358484854206059302399319323859279240268722523450455802058257892548941510959997370995292748578655762731064
l1 = 53066819955389743890197631647873076075338086201977617516688228878534943391813622173359672220491899999289257725082621279332126787067021987817619363964027754585057494857755310178293620211144789491527192983726079040683600073569676641124270473179040250808117008272524876858340200385005503388452491343904776677382
l2 = 7842029648140254898731712025732394370883533642138819492816448948307815782380138847628158108013809453236401089035015649397623608296202122635822677717636589547775619483739816443584071749358123933593122063285229582290924379314987624399741427190797914523635723048501174115183499642950146958355891757875557441498

F = Zmod(N)

p1 = ord('C')
p2 = ord('y')
c1 = F(power_mod(p1, e, N))
c2 = F(power_mod(p2, e, N))

d1 = F(l1 - c1^3 - R)
k11 = F(3*c1^2)
k21 = F(3*c1)

d2 = F(l2 - c2^3 - R)
k12 = F(3*c2^2)
k22 = F(3*c2)

a = k11*k22-k12*k21
b = d1*k22 - d2*k21

r = b*a^(-1)

#Sanity check
assert(k21*r^2+k11*r == d1)
assert(k22*r^2+k12*r == d2)

print(r)

# r' = 166948911880587234600972597325398559800623586442106754544249387904660171481281804594820145380464642946591165741209919048255667796045110331101490851949349850578944
```
- Now that we have $r'$, we only have to reconstruct the flag, this python script does exactly that :
```python
ciphertexts = [21340757543584301785921441484183053451553315439245254915339588451884106542258661009436759738472587801036386643847752005362980150928908869053740830266273664899424683013780904331345502086236995074501779725358484854206059302399319323859279240268722523450455802058257892548941510959997370995292748578655762731064, 53066819955389743890197631647873076075338086201977617516688228878534943391813622173359672220491899999289257725082621279332126787067021987817619363964027754585057494857755310178293620211144789491527192983726079040683600073569676641124270473179040250808117008272524876858340200385005503388452491343904776677382, 7842029648140254898731712025732394370883533642138819492816448948307815782380138847628158108013809453236401089035015649397623608296202122635822677717636589547775619483739816443584071749358123933593122063285229582290924379314987624399741427190797914523635723048501174115183499642950146958355891757875557441498, 81695021584105358045051566003505716258539304380158236410692031154675976958477102448120001354028763788338277726836564439223825775055987134804476545219389719030154358688010609211929573454049639296115583549679374560630884139585632673018270295206596781845043810461183562700653267241738473715845857687319113614456, 86586501887041201286527802721761642260725877818992995519871353147763446402104956574783967901914351377837180089585862713765704485010827129195281513365094091181910563864296721772761074690566705659717173959009277068631076288853911923094528971015851696547954102181618472963745794032190874682537561541341010731317, 4407010096401177719382587860973089547269774584169025945612873836837456069669989617488086581303974564705691737258603082424491662678151761823140849931562969625660637062703801758223280715291175509480824528541363322136476980382432430887691493142016500898713242165899187042640529277802536975777824806009438943965, 20524927494678402175950259591111162749212820045240667997136299019445709195168242983746096181865554404588029237712065575377811975608978219126831818907269960069985776657364619267644968568292446797472239793194732664070169465897817709246314196916593546896176278896250403566147976472899677805168690321734513565299, 4407010096401177719382587860973089547269774584169025945612873836837456069669989617488086581303974564705691737258603082424491662678151761823140849931562969625660637062703801758223280715291175509480824528541363322136476980382432430887691493142016500898713242165899187042640529277802536975777824806009438943965, 51139318697490622650693660298147944378988372035109840705368428672127413619272423551816883049235344493649752002429044518033993427344083454465185748371604373504028204966800166389631164678888210143920677529018088140621435737669118638794028597406100569365879488348484226040476359974085585581378223149467179501946, 61799162491846407044403618488152290977719649337271367195813541845489917481067315542645819191562014741305490739984114955413967671171269164971415239796230389202065094904892080733323413509954520339080338852975324810347271929340532300585500631891040710031375781370408675545957886220089645926354912765277207193798, 107206043735279333846992454448839140370827883940390260597595481248800707737249317944514632453873180357326528319466071505831942392623928121738100851252667510107695812737386157242288048018487583295361010891262525476641689707830363622742934590525129489305921929428048618530386530992073266265026078031189655320106, 85307591403552508243723419381075892490553211323303653139542717671522446932474210804647996573033586101417717988233360452582706073794403902188813545550074952753888569571363969851352079224368979656333248386459649432144248164681972775841136644513642798070299209002137286717588527668402619441954609514753661947313, 86586501887041201286527802721761642260725877818992995519871353147763446402104956574783967901914351377837180089585862713765704485010827129195281513365094091181910563864296721772761074690566705659717173959009277068631076288853911923094528971015851696547954102181618472963745794032190874682537561541341010731317, 41397924411890772454375265845933795072222843402754920501088753051420044021616883093528477351669664383575552141733184262754285200808444804620877416618853152278116553671610496732425895917227824642073742631842238665475944337858457051856626631418115315171059531227054863964810769428751856584563528521378904763004, 10605243757384588410949346291843691695059260029262285885688340336498786144062875360655352621500803735554571187372176718434140069866861892334998832161282034966596765115799113734407139063630983608233399160254561926930070785190320545453208884166339176430224475632173509946846905362279714116952844713431984171423, 65849650090975782672006215530044304732838792899298125801656552932222950757929203789661590769174992774295751413212216292841524763630804121853440450854889497695508837735482849044800782262622201081754096333157119856307403189214765778617730569259936442310922376487593547587612071369577598550538470953180060327484, 4407010096401177719382587860973089547269774584169025945612873836837456069669989617488086581303974564705691737258603082424491662678151761823140849931562969625660637062703801758223280715291175509480824528541363322136476980382432430887691493142016500898713242165899187042640529277802536975777824806009438943965, 25192663003159777174615451629938213843222366842683940183362551204469496974891644208321342646667233572676576472164648007266602388592839440014310951184481049521012297732473729920930726303235436945383858287317594336428793167109440236357984389807244311551143246546400865347076405661274883099848046482994822149839, 81111299336050275750472008224957667125146586306759086248084295752602324720839543288370663615750857287552903922536031859099788116379487391773903754451992919367596305768339444201446994649849712459520992343839084870637197983082887171667909318521242800685401171176726353172069040622627821647795603423551447271897, 172967095404256540830825090627890385022225889601723954575733125793475006259282286018366839965172738142366017838292656817573153121633640374942242813153661050037135885057976712584829626048750871049237074200959050511068507540075123164896445819553176441313661889437609142291778433892651893386678048468180013621, 54209820127153720986474084238052778697132905502967498816654290121880250372787906574546961463213093657385992644387672873438452821695140015330496830316777538022586647303682910176500454712473480999658744024410467615800495847992591570851886050019970720291086916154447046480846281731972943090264324948456440665661, 28885040548649433818312707049098386302426564056859377602258643789733090344285966189272164940417109799449123029221353559595585853944793603746038212728785628090812468725975339605126975370377243473883045109400760722557049145239156309228858278704148782700632988895826738069560545828526225627800055745581440022577, 81111299336050275750472008224957667125146586306759086248084295752602324720839543288370663615750857287552903922536031859099788116379487391773903754451992919367596305768339444201446994649849712459520992343839084870637197983082887171667909318521242800685401171176726353172069040622627821647795603423551447271897, 15712112799522387502102713193722467424402631384092196807057434496598674428309494459811523180782790044819285433524468899851335245998768088831658170418466392438399410802792501309056236805241160176754059850691703432150262405441430237695612809894131939658419704673281367391393311992247965290741727023994779433141, 90557913992970124339018122417017168647892092654619957439310943241692998853469781201535236911728649858936776518532983596071103348064396527739989572674507974009483171965078556587909741335279567452647179397815757421899178406412750565529499623891538068993828045760955318494257424529204657968028613157183995612711, 85675609516128041505642974246105781207878835838608550975500845934782884530583531039538004477522284615403428772115964969520508967026139845649101029319923434926707385504059806901530960679704218584706660751338176542291587725130564020356976235189119834080273889731614886626208044719903723301580316649222174716532, 15712112799522387502102713193722467424402631384092196807057434496598674428309494459811523180782790044819285433524468899851335245998768088831658170418466392438399410802792501309056236805241160176754059850691703432150262405441430237695612809894131939658419704673281367391393311992247965290741727023994779433141, 81111299336050275750472008224957667125146586306759086248084295752602324720839543288370663615750857287552903922536031859099788116379487391773903754451992919367596305768339444201446994649849712459520992343839084870637197983082887171667909318521242800685401171176726353172069040622627821647795603423551447271897, 85675609516128041505642974246105781207878835838608550975500845934782884530583531039538004477522284615403428772115964969520508967026139845649101029319923434926707385504059806901530960679704218584706660751338176542291587725130564020356976235189119834080273889731614886626208044719903723301580316649222174716532, 85675609516128041505642974246105781207878835838608550975500845934782884530583531039538004477522284615403428772115964969520508967026139845649101029319923434926707385504059806901530960679704218584706660751338176542291587725130564020356976235189119834080273889731614886626208044719903723301580316649222174716532, 61799162491846407044403618488152290977719649337271367195813541845489917481067315542645819191562014741305490739984114955413967671171269164971415239796230389202065094904892080733323413509954520339080338852975324810347271929340532300585500631891040710031375781370408675545957886220089645926354912765277207193798, 15712112799522387502102713193722467424402631384092196807057434496598674428309494459811523180782790044819285433524468899851335245998768088831658170418466392438399410802792501309056236805241160176754059850691703432150262405441430237695612809894131939658419704673281367391393311992247965290741727023994779433141, 38962700196345764443430076328468823048654528820043766024585560519262075591273928991068126566288543007226770928003946070052439096668643477740474190703788526219925328431721859530740114691295801384955561916420881286450144549992327909272769286620245430583032691331672843446292771750462163437595822776667096333763, 81111299336050275750472008224957667125146586306759086248084295752602324720839543288370663615750857287552903922536031859099788116379487391773903754451992919367596305768339444201446994649849712459520992343839084870637197983082887171667909318521242800685401171176726353172069040622627821647795603423551447271897, 81604909815994086673421693572426298878862835900596359748090824964404410968235612905849185964777674389932839535035599455168277871014038156501897270840412741045214049490644167087296649367556864887777074100267203854799140784786464099851736527907291367077573005882823454864594785834874833652994406695607530576301, 85307591403552508243723419381075892490553211323303653139542717671522446932474210804647996573033586101417717988233360452582706073794403902188813545550074952753888569571363969851352079224368979656333248386459649432144248164681972775841136644513642798070299209002137286717588527668402619441954609514753661947313, 52156001220188104895473522650224336584905726666754737059523290472567230003322526600513423004029753974157905270382920020591958052240353991252839261876495000572160369521817108757646640716294419293319582726159643898164423211489747574918997667612756540268118158962997647124621728161184263876514787554342131369200, 85675609516128041505642974246105781207878835838608550975500845934782884530583531039538004477522284615403428772115964969520508967026139845649101029319923434926707385504059806901530960679704218584706660751338176542291587725130564020356976235189119834080273889731614886626208044719903723301580316649222174716532, 8626201435710132500083028176804629797027088958282385045951979777069641530512143047104352887040944488529150298079174517417971856366246040580278209977476709229172088355435726582119603207919684569044830141050650718261952439402562787510913838563646318999328281769878916484145022935183249932414990371457340982530, 15712112799522387502102713193722467424402631384092196807057434496598674428309494459811523180782790044819285433524468899851335245998768088831658170418466392438399410802792501309056236805241160176754059850691703432150262405441430237695612809894131939658419704673281367391393311992247965290741727023994779433141, 121226218034082229384971342687398416100893638888085513248813472413262145283395477535912994933231543339828879244145432486720289587030092361101582541189271478597197509543997536280636089567590609161877061652162188271757425292313858133390807992771802944817639363538653163784369687974560442354969526917376491860952, 85675609516128041505642974246105781207878835838608550975500845934782884530583531039538004477522284615403428772115964969520508967026139845649101029319923434926707385504059806901530960679704218584706660751338176542291587725130564020356976235189119834080273889731614886626208044719903723301580316649222174716532, 25192663003159777174615451629938213843222366842683940183362551204469496974891644208321342646667233572676576472164648007266602388592839440014310951184481049521012297732473729920930726303235436945383858287317594336428793167109440236357984389807244311551143246546400865347076405661274883099848046482994822149839, 49537543950196981196008705073490431322869824547419754434164989869148910207602945400222339540873326843877995376121122967451939219149806674439960220589193189585760172923124276530124072984487005587747672999647203434177959209139239195212611226079544263186906487384149209242751551401702465174463378551587903464013, 81604909815994086673421693572426298878862835900596359748090824964404410968235612905849185964777674389932839535035599455168277871014038156501897270840412741045214049490644167087296649367556864887777074100267203854799140784786464099851736527907291367077573005882823454864594785834874833652994406695607530576301, 82605108086464943169862550306200946889734302370750892864214984485030047777068048016807926063544535451667188130157336614116049572675082898787939202381661956285707961358162934993215182977800779844581722076853699116970869839871673603035667037900906095736260590599998045628715894324887335765024740238758306886601, 15712112799522387502102713193722467424402631384092196807057434496598674428309494459811523180782790044819285433524468899851335245998768088831658170418466392438399410802792501309056236805241160176754059850691703432150262405441430237695612809894131939658419704673281367391393311992247965290741727023994779433141, 87183215347967191590542176417724958857058607082507361242348562809358164198308247679047180368020902280813201721298429403561075113836349947551334588733174809438143792381327054583566337165561000865476978009557708693850414825902676261268716823948760442922777052374371288490023049947720611595532141510532644435250, 49537543950196981196008705073490431322869824547419754434164989869148910207602945400222339540873326843877995376121122967451939219149806674439960220589193189585760172923124276530124072984487005587747672999647203434177959209139239195212611226079544263186906487384149209242751551401702465174463378551587903464013, 25192663003159777174615451629938213843222366842683940183362551204469496974891644208321342646667233572676576472164648007266602388592839440014310951184481049521012297732473729920930726303235436945383858287317594336428793167109440236357984389807244311551143246546400865347076405661274883099848046482994822149839, 66766715720902966595178914295223547348495022878823462889622775721913448987561303310541276071530863698182890278728480864181198078543766251390078585132912767108062691265660663002406799106089377580272724589978697222635560956414236639690889939243054319449595599517712915493280854882719256210734111619403134480752, 23942811148204157202654637859911277560708533796069053111751942163750895868053622268645847217089096022452975956692323271828103232820789988209286647453449929108598776835367103056318289898885824280500932307262080931914632255743345269865080087850167325191747197921286245735954464811042826275305804860020107464497]

r = 166948911880587234600972597325398559800623586442106754544249387904660171481281804594820145380464642946591165741209919048255667796045110331101490851949349850578944

chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ{}-_#0123456789"

N = 128704452311502431858930198880251272310127835853066867118127724648453996065794849896361864026440048456920428841973494939542251652347755395656512696329757941393301819624888067640984628166587498928291226622894829126692225620665358415985778838076183290137030890396001916620456369124216429276076622486278042629001
e = 3

def encrypt_message(m):
return pow(m,e,N)

def advanced_encrypt(a):
return encrypt_message(pow(a,3,N)+r)

# Sanity check
# assert(advanced_encrypt(ord('C')) == ciphertexts[0])
# assert(advanced_encrypt(ord('y')) == ciphertexts[1])

# Build a dictionary of all ciphertexts
ctpt = {}
for char in chars:
ct = advanced_encrypt(ord(char))
ctpt[ct] = char

# Reconstruct the flag from the knows plaintext/ciphertext pairs
flag = ''
for ct in ciphertexts:
if(ct in ctpt):
flag += ctpt[ct]
else:
flag += "#"

print(flag)
```
- I ended up commenting out the assertion part cause it kept failing for some reason, then after executing the code we get our flag !

# Flag

CyberErudites{Fr4nkl1n_W3_n33d_an0th3R_S3450N_A54P}

Original writeup (https://github.com/not1cyyy/CTF-Writeups/blob/master/GDG-Algiers-CTF/franklin-last-words.md).