4k-rsa

Only n00bz use 2048-bit RSA. True gamers use keys that are at least 4k bits long, no matter how many primes it takes…

Files

• 4k-rsa-public-key.txt

Solution

• Checking FactorDB, we get multiple prime factors for the given modulus n
• This is multi-prime RSA
• Following the usual algorithm, the given ciphertext c can be decrypted to find the flag

Solution Code

n = 5028492424316659784848610571868499830635784588253436599431884204425304126574506051458282629520844349077718907065343861952658055912723193332988900049704385076586516440137002407618568563003151764276775720948938528351773075093802636408325577864234115127871390168096496816499360494036227508350983216047669122408034583867561383118909895952974973292619495653073541886055538702432092425858482003930575665792421982301721054750712657799039327522613062264704797422340254020326514065801221180376851065029216809710795296030568379075073865984532498070572310229403940699763425130520414160563102491810814915288755251220179858773367510455580835421154668619370583787024315600566549750956030977653030065606416521363336014610142446739352985652335981500656145027999377047563266566792989553932335258615049158885853966867137798471757467768769820421797075336546511982769835420524203920252434351263053140580327108189404503020910499228438500946012560331269890809392427093030932508389051070445428793625564099729529982492671019322403728879286539821165627370580739998221464217677185178817064155665872550466352067822943073454133105879256544996546945106521271564937390984619840428052621074566596529317714264401833493628083147272364024196348602285804117877
c = 3832859959626457027225709485375429656323178255126603075378663780948519393653566439532625900633433079271626752658882846798954519528892785678004898021308530304423348642816494504358742617536632005629162742485616912893249757928177819654147103963601401967984760746606313579479677305115496544265504651189209247851288266375913337224758155404252271964193376588771249685826128994580590505359435624950249807274946356672459398383788496965366601700031989073183091240557732312196619073008044278694422846488276936308964833729880247375177623028647353720525241938501891398515151145843765402243620785039625653437188509517271172952425644502621053148500664229099057389473617140142440892790010206026311228529465208203622927292280981837484316872937109663262395217006401614037278579063175500228717845448302693565927904414274956989419660185597039288048513697701561336476305496225188756278588808894723873597304279725821713301598203214138796642705887647813388102769640891356064278925539661743499697835930523006188666242622981619269625586780392541257657243483709067962183896469871277059132186393541650668579736405549322908665664807483683884964791989381083279779609467287234180135259393984011170607244611693425554675508988981095977187966503676074747171
e = 65537
z = 1

# factors of n
k = "9353689450544968301 9431486459129385713 9563871376496945939 9734621099746950389 9736426554597289187 10035211751896066517 10040518276351167659 10181432127731860643 10207091564737615283 10435329529687076341 10498390163702844413 10795203922067072869 11172074163972443279 11177660664692929397 11485099149552071347 11616532426455948319 11964233629849590781 11992188644420662609 12084363952563914161 12264277362666379411 12284357139600907033 12726850839407946047 13115347801685269351 13330028326583914849 13447718068162387333 13554661643603143669 13558122110214876367 13579057804448354623 13716062103239551021 13789440402687036193 13856162412093479449 13857614679626144761 14296909550165083981 14302754311314161101 14636284106789671351 14764546515788021591 14893589315557698913 15067220807972526163 15241351646164982941 15407706505172751449 15524931816063806341 15525253577632484267 15549005882626828981 15687871802768704433 15720375559558820789 15734713257994215871 15742065469952258753 15861836139507191959 16136191597900016651 16154675571631982029 16175693991682950929 16418126406213832189 16568399117655835211 16618761350345493811 16663643217910267123 16750888032920189263 16796967566363355967 16842398522466619901 17472599467110501143 17616950931512191043 17825248785173311981 18268960885156297373 18311624754015021467 18415126952549973977"

k = k.split(" ")
ans = []

for i in range(len(k)) :
	z *= int(k[i])
	ans.append(int(k[i]))

p = ans
d = 1

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]

def modInv(a, m):
	g, x, y = egcd(a, m)
	if (g != 1):
		raise Exception("[-]No modular multiplicative inverse of %d under modulus %d" % (a, m))
	else:
		return x % m

phi = 1

for a in p :
	phi *= (a-1)
	
d = modInv(e, phi)
m = pow(c, d, n)
flag = (hex(m)[2:-1]).decode('hex')
print(flag)

flag{t0000_m4nyyyy_pr1m355555}

Note : Crypto.Util.number, gmpy module in python can be used.