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()