Midnight Sun CTF 2019 Quals Write-Up: open-gyckel-crypto - LostMyPlaintext

Midnight Sun CTF 2019 Quals Write-up

Card image cap

For this challenge we're given the following code: 

while True:
    p = next_prime(random.randint(0, 10**500))
    if len(str(p)) != 500:
        continue
    q = Integer(int(str(p)[250:] + str(p)[:250]))
    if q.is_prime():
        break

>> p * q
6146024643941503757217715363256725297474582575057128830681803952150464985329239705861504172069973746764596350359462277397739134788481500502387716062571912861345331755396960400668616401300689786263797654804338789112750913548642482662809784602704174564885963722422299918304645125966515910080631257020529794610856299507980828520629245187681653190311198219403188372517508164871722474627810848320169613689716990022730088459821267951447201867517626158744944551445617408339432658443496118067189012595726036261168251749186085493288311314941584653172141498507582033165337666796171940245572657593635107816849481870784366174740265906662098222589242955869775789843661127411493630943226776741646463845546396213149027737171200372484413863565567390083316799725434855960709541328144058411807356607316377373917707720258565704707770352508576366053160404360862976120784192082599228536166245480722359263166146184992593735550019325337524138545418186493193366973466749752806880403086988489013389009843734224502284325825989
>> pow(m, 65537, p * q)
3572030904528013180691184031825875018560018830056027446538585108046374607199842488138228426133620939067295245642162497675548656988031367698701161407333098336631469820625758165691216722102954230039803062571915807926805842311530808555825502457067483266045370081698397234434007948071948000301674260889742505705689105049976374758307610890478956315615270346544731420764623411884522772647227485422185741972880247913540403503772495257290866993158120540920089734332219140638231258380844037266185237491107152677366121632644100162619601924591268704611229987050199163281293994502948372872259033482851597923104208041748275169138684724529347356731689014177146308752441720676090362823472528200449780703866597108548404590800249980122989260948630061847682889941399385098680402067366390334436739269305750501804725143228482932118740926602413362231953728010397307348540059759689560081517028515279382023371274623802620886821099991568528927696544505357451279263250695311793770159474896431625763008081110926072287874375257

First let's make sure we understand what's going on. This was a pretty interesting RSA math challenge were p is a random prime of size 500 digits. Here's were things get interesting though, let's say L represents the 250 leftmost digits of p(ordered from left to right) and R the 250 rightmost digits of p (ordered from left to right), q is equal to L concatenated with R. So the code splits p's digits in half swaps the left half with the right half and q becomes the result of this operation(note the code makes sure both are primes).

Knowing this we can write p using L and P as:

  • p = L * 10(len(p)/2) + R = L * 10250 + R

Likewise, since we have an established relation between p and q we can write q as:

  • q = R * 10(len(p)/2) + L = R * 10250 + L

And now we can use some math to write n as:

  • n = p*q = (L * 10250 + R) * (R * 10250 + L)
  • n = L * 10250 * R + L2 * 10250 + R2 * 10250 + L*R
  • n = LR * 10500 + (L2 + R2)*10250 + L*R

From here we can conclude that the 250 leftmost digits of L*R must corresponde to the 250 leftmost digits of n (minus a possible carry, wich can be easily bruteforced if present) and the 250 rightmost digits of L*R must correspond to the 250 rightmost digits of n. The following python line might ilustrate better how we can calculate L*R (also keep in mind that n is 1000 digits long):

LR = (int(str(n)[:250])-carry)*10**250+int(str(n)[750:])

Now that we have a way to calculate L*R we can write an equation to calculate (L2+R2) based on our previous result:

  • n = L*R * 10500 + (L2 + R2)*10250 + L*R
  • (=) n - L*R * 10500 = (L2 + R2)*10250 + L*R
  • (=) n - L*R * 10500 - L*R = (L2 + R2)*10250
  • (=) (n - L*R * 10500 - L*R)/10250 = L2 + R2
  • (=) L2 + R2 = (n - L*R * 10500 - L*R)/10250

Here I admittedly got stuck for quite a while. I was having trouble figuring out how to get the correct values for p and q from here. Playing around with some math, I wrote, among other things, phi(n) as:

  • phi(n) = (p-1)*(q-1)
  • phi(n) = p*q - p - q + 1
  • phi(n) = p*q - (p + q) + 1

But I didn't immediately see how we can use this to solve the challenge. Then it hit me. We can write p + q as:

  • p + q = (L * 10250 + R) + (R * 10250 + L)
  • p + q = (L + R) * 10250 + L + R

We can then write (L + R)2 as:

  • (L + R)2 = L2+R2+2*L*R

And since we can calculate both L*R and L2+R2 we can calculate (L+R)2 and thus calculate (L+R) since (L+R) = sqrt((L+R)2). Knowing L + R we can calculate p + q and thus calculatephi(n) without even knowing the exact values of p and q

Solver:

import codecs
import gmpy

decode_hex = codecs.getdecoder("hex_codec")

n = 6146024643941503757217715363256725297474582575057128830681803952150464985329239705861504172069973746764596350359462277397739134788481500502387716062571912861345331755396960400668616401300689786263797654804338789112750913548642482662809784602704174564885963722422299918304645125966515910080631257020529794610856299507980828520629245187681653190311198219403188372517508164871722474627810848320169613689716990022730088459821267951447201867517626158744944551445617408339432658443496118067189012595726036261168251749186085493288311314941584653172141498507582033165337666796171940245572657593635107816849481870784366174740265906662098222589242955869775789843661127411493630943226776741646463845546396213149027737171200372484413863565567390083316799725434855960709541328144058411807356607316377373917707720258565704707770352508576366053160404360862976120784192082599228536166245480722359263166146184992593735550019325337524138545418186493193366973466749752806880403086988489013389009843734224502284325825989
c = 3572030904528013180691184031825875018560018830056027446538585108046374607199842488138228426133620939067295245642162497675548656988031367698701161407333098336631469820625758165691216722102954230039803062571915807926805842311530808555825502457067483266045370081698397234434007948071948000301674260889742505705689105049976374758307610890478956315615270346544731420764623411884522772647227485422185741972880247913540403503772495257290866993158120540920089734332219140638231258380844037266185237491107152677366121632644100162619601924591268704611229987050199163281293994502948372872259033482851597923104208041748275169138684724529347356731689014177146308752441720676090362823472528200449780703866597108548404590800249980122989260948630061847682889941399385098680402067366390334436739269305750501804725143228482932118740926602413362231953728010397307348540059759689560081517028515279382023371274623802620886821099991568528927696544505357451279263250695311793770159474896431625763008081110926072287874375257 
e = 65537


for carry in range(1,10):
  LR = (int(str(n)[:250])-carry)*10**250+int(str(n)[750:])

  L2_plus_R2 = (n - LR * 10**500  - LR) // 10**250

  if((LR*10**500+L2_plus_R2*10**250+LR) == n):
    break

L_plus_R = gmpy.root(L2_plus_R2 + 2*LR,2)[0]

phin = n - (L_plus_R*10**250+L_plus_R) + 1

d = gmpy.invert(e,phin)

m = pow(c,d,n)

flag = decode_hex(hex(m)[2:])[0]

print(flag)

Flag: midnight{w3ll_wh47_d0_y0u_kn0w_7h15_15_4c7u4lly_7h3_w0rld5_l0n6357_fl46_4nd_y0u_f0und_17_

50_y0u_5h0uld_b3_pr0ud_0f_y0ur53lf_50_uhmm_60_pr1n7_7h15_0n_4_75h1r7_0r_50m37h1n6_4nd

_4m4z3_7h3_p30pl3_4r0und_y0u}