by L0rdComm4nder and majo and mandlebro
Points: 226 (Dynamic, 56 solves)
Primes are fun, don’t google translate me bro. https://s3.eu-north-1.amazonaws.com/dl.2019.midnightsunctf.se/529C928A6B855DC07AEEE66037E5452E255684E06230BB7C06690DA3D6279E4C/gyckel.tar.gz
Understand the given 7 lines of code, A prime
pwith 500 digits is generated. From it a second prime
qis 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 factor
nsolves RSA and we can decrypt the flag.
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.
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
- block-2: left-digits of
a^2 + b^2plus right-digits of
- block-3: right-digits of
a^2 + b^2plus left-digits of
- block-4: right-digits of
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^2 + b^2. Solving the system, get
b, we compute
q, successfully factoring
n. And we can solve RSA!
Solution in gyckel.py.