# INS’HACK: Yet Another RSA Challenge

This was a two part RSA challenge. We were supplied with $m,e,c$ and a corrupted “prime” $p$. The first stage introduced the problem in a form where you could try possible $p$ values by hand, stage two put the problem into a form that required some programming.

# Part One

## Challenge

Buy an encrypted flag, get a (almost intact) prime factor for free ! You can find a harder version of this challenge in the Programming category.

The source code shows how the $p$ was corrupted and allows us to determine exactly what was given to us in the output.txt.

import subprocess
p = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
q = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
flag = int('INSA{REDACTED}'.encode('hex'), 16)

N = int(p,16) * int(q,16)
print N
print '0x'+p.replace('9F','FC')
print pow(flag,65537,N)


## Method

Looking at the corrupted $p$ value in the output:

0xDCC5A0BD3A1FC0BEB0DA1C2E8CF6B474481B7C12849B76E03C4C946724DB577D2825D6AA193DB559BC9DBABE1DDE8B5E7805E48749EF002F622F7CDBD7853B200E2A027E87E331AFCFD066ED9900F1E5F5E5196A451A6F9E329EB889D773F08E5FBF45AACB818FD186DD74626180294DCC31805A88D1B71DE5BFEF3ED01F12678D906A833A78EDCE9BDAF22BBE45C0BFB7A82AFE42C1C3B8581C83BF43DFE31BFD81527E507686956458905CC9A660604552A060109DC81D01F229A264AB67C6D7168721AB36DE769CEAFB97F238050193EC942078DDF5329A387F46253A4411A9C8BB71F9AEB11AC9623E41C14FCD2739D76E69283E57DDB11FC531B4611EE3


There are 4 instances of FC, which means there was at most 4 9F replaced. This gives $2^4$ possible values of $p$. You can check each of these values by hand, or get your computer to try all 16 values of $p$ for you.

We checked for the correct $p$ value looking for $n \mod p = 0$. The flag after decrypting is INSA{I_w1ll_us3_OTp_n3xT_T1M3}.

# Part Two

This is exactly the same problem as before, but there have been 8 instances of the replace mixing and so we’re not going to be able to try all of the different possibilities by hand, even if we wanted to.

## Challenge

The source code sets the scene

import subprocess
p = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
q = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
flag = int('INSA{REDACTED}'.encode('hex'), 16)

N = int(p,16) * int(q,16)
print N
print '0x'+p.replace('12','8D').replace('33','D4').replace('5E','FF').replace('09','95').replace('E4','38').replace('6B','89').replace('9E','E0').replace('59','3E')
print pow(flag,65537,N)


## Method

The goal now is to find an efficient way to make all possible string replacements for all 8 instances. The method we used was to create a set of all possible values of $p$, working backwards through the eight replacements. We end up with over 1,000,000 possible prime values and we simply iterate through them all and decrypting using the value when $n \mod p = 0$.

The correct value of $p$ is given by

p = 27207852581327866405087823667605448590879010013227826358847092780035210321793504880325940216718337487396072164496007982969062153457249825841387303789340168307345198340289780841780775519616179644375029427001893073329165063349924021531316671597438108960745173365258247048176055774932736580556497631388766619325642748953764064431900902509832526296549507917189176177626973840443734025141158673750408928322616401221180059867496281187731967858877968251610849486692645888138411828273843287901045651440388515710393698604711633177126248348930473971258291695989452776816815123460972817838228697384263540612910611262936800312657


The decrypted message gives the flag INSA{Uh_never_give_4w4y_your_Pr1mes_I_m34n_duhhh}

### Python Implementation

from Crypto.Util.number import inverse
from collections import Counter
import itertools

# generates all possible integers from the swap from x to y

def gen_p(l_num,x,y):
all_p = set(l_num)
l_num, l = list(l_num), len(l_num)
l_num  = [p.replace(x, '_') for p in l_num]
for pn in range(l):
count = Counter(l_num[pn])['_']
if count == 0:
all_p.add(l_num[pn])
else:
joiners = list(itertools.product([x,y], repeat=count))
for j in joiners:
new_p = l_num[pn]
for c in range(count):
new_p = new_p.replace('_',j[c],1)
all_p.add(new_p)
return all_p

# Puzzle Data

n = 737611163443959284842367849241210504758770468900963447745605275812981372405732262639464389012528980016931096127343933425531508977427016967370838523007185109804122827435442876112926896405911684006913203175001902528962659926046227042479405858100518975905360430463250839310857983177028295643515725251012428553651998860175968606629769294473365526541620801873942073999635165942812779333418405669820767884314938500537161124341967101209379749620814652441184505316661790048734950052497097493871158994129217835162546653468074537465326514182322892918918625260996455179683746164361293138705790829022424332601363202790350347639455664656064705450037947152881312491133191289211419037325704774394630500271194735028396494665835379325963853042514832498826985928063545989015763434053963155703531024791434836954197474393368464043648904368880777954234469571406476568488608818611878807321749318425353873416639028342088117081977903731238631252547599612554002863288409286756260496090170930084625283076970661877432107608911551414435036116940780849204521422482251640736907024303127956310763272428319732230450480696798568635499915064255846815425268220147645177869463315347549456623125597500648525429960478399391403082954189840918045663557930850169068717203841
e = 65537
c = 238625175560117519818219655160700093672765696917859228632607011580941239729981338983916209022919475382357227963405365905148115318257038277146986081479123834942285774969894504633426906629030480787741565635778433780362722138925014818166488253621790448543359319453495165651188539177460365420486442547806453231416816633460519873660432319115179116336907802631692806970121302821171652412917375895244055318035607411137420274957028058695317500603598525629698305540801857314426359129633709966978334387372229490871242813925900864337395540528999023305226494361061535292380487362207573111785857146840743150168595521892054972163853976096692431697845761601194595494668734667899627964699784309805348028825617943571577132154874260866191233001610717099049253716197026401372924319018736900888351182876610669592251724095719123094054432644034621312701246109838942945597240248959486831491623970160080568107285964593924238967189856179059372322390416530545895764941716546818701469100406503650604889258155970317233013903059065959366407802296924017896297385415541256814333380793132923243754142847186952683218437937882137950119347398825971468218656558007008879510066175287320907270138115038609371999806062759974181729622851705386276830651522840256814183961092
p_broken = '0xD78717E5C560636F461952384C67475479931C73E8573DE1658AD9828BA322DF497E2FC6042AE093EC7F194B47AF7E507CFF542F9085A0C526DC4B3B44D6FBEC4CA672FB2F75B56F151E5A103A1CBF6DB17611A6E6D1C054CE7A9D0A2170370E8AD349B98DFD984A6955B97AB7087AF81019C0F31456A6179DB47D2A240E307422D3F968193F8F239035640A357EBC4C3726DBF9935FF243AF8F0A4D458534381B38C3435AC0E61564BF79C7F808C38AB61F5DD2080EC2A2211AAFC17F8E89F99690278D494F1C8D1170C31442D1A8624EAE9938FB874962BBAE8915DA1943FC41B8D8CA675FE35FFD30B1CA5DF21E1BB0F9BC3C1F7CDC7E3E3E3AB834503D51'

# Produce all possible values for p

all_p = [p_broken]
all_p = gen_p(all_p, '3E', '59')
all_p = gen_p(all_p, 'E0', '9E')
all_p = gen_p(all_p, '89', '6B')
all_p = gen_p(all_p, '38', 'E4')
all_p = gen_p(all_p, '95', '09')
all_p = gen_p(all_p, 'FF', '5E')
all_p = gen_p(all_p, 'D4', '33')
all_p = gen_p(all_p, '8D', '12')

# Run through the list of p values, if p divides n then p,q are used to decrypt c

for p_guess in all_p:
p_guess = int(p_guess,16)
if n%p_guess == 0:
p = p_guess
print("prime found, ", p)
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(bytes.fromhex(format(m,'x')).decode('utf-8'))
exit()