open-gyckel-crypto

by goulov and L0rdComm4nder and mandlebro

Points: 226 (Dynamic, 56 solves)

Description:

Primes are fun, don’t google translate me bro. https://s3.eu-north-1.amazonaws.com/dl.2019.midnightsunctf.se/529C928A6B855DC07AEEE66037E5452E255684E06230BB7C06690DA3D6279E4C/gyckel.tar.gz

Given: gyckel.txt

Solution:

TLDR

  1. Understand the given 7 lines of code, A prime p with 500 digits is generated. From it a second prime q is constructed by taking the first 250 digits of the first and swaping them with the other 250. Encrypt the text with RSA.

  2. 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 factor n.

  3. 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
  • block-1: left-digits of a*b
  • block-2: left-digits of a^2 + b^2 plus right-digits of a*b
  • block-3: right-digits of a^2 + b^2 plus left-digits of a*b
  • block-4: right-digits of a*b

We concatenate block-1 to block-4 to get a*b, and subtract block-4 from block-2 and block-1 from block-3, to recover a^2 + b^2. The only catch to this is that there are carries that can go from block to block (except block-4), 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.