opengyckelcrypto  Midnightsun 2019 Quals CTF
opengyckelcrypto
by goulov and L0rdComm4nder and mandlebro
Points: 226 (Dynamic, 56 solves)
Description:
Primes are fun, don’t google translate me bro. https://s3.eunorth1.amazonaws.com/dl.2019.midnightsunctf.se/529C928A6B855DC07AEEE66037E5452E255684E06230BB7C06690DA3D6279E4C/gyckel.tar.gz
Given: gyckel.txt
Solution:
TLDR

Understand the given 7 lines of code, A prime
p
with 500 digits is generated. From it a second primeq
is constructed by taking the first 250 digits of the first and swaping them with the other 250. Encrypt the text with RSA. 
Since the second prime is constructed from the first, we can exploit this dependency, as this structure will be reflected in
n=p*q
. We can factorn
. 
Factoring
n
solves RSA and we can decrypt the flag.
Attack
This is a very nice little problem. First, one can see that the primes have the following structure:
p = a*10^250 + b
q = b*10^250 + a
.
As such, n = a*b*10^500 + (a^2 + b^2)*10^250 + a*b
.
Schematically, this is:

n =  1  2  3  4 

1000 750 500 250 0 Digits
 block1: leftdigits of
a*b
 block2: leftdigits of
a^2 + b^2
plus rightdigits ofa*b
 block3: rightdigits of
a^2 + b^2
plus leftdigits ofa*b
 block4: rightdigits of
a*b
We concatenate block1 to block4 to get a*b
, and subtract block4 from block2 and block1 from block3, to recover a^2 + b^2
. The only catch to this is that there are carries that can go from block to block (except block4), but these are not many cases and we can try them all. Only one case will be a solution to the system of equations.
So, by exploiting this structure, we can recover a*b
and a^2 + b^2
. Solving the system, get a
and b
, we compute p
and q
, successfully factoring n
. And we can solve RSA!
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}
Resources:
Solution in gyckel.py.