ASIS Quals 2017 – F-4 Phantom – 176 points

Description:

With F-4 Phantom II, we want to break the encryption! Please help us!!

 

‍‍‍nc 66.172.27.77 54979

Here is the [K]ey generating fuction

As we can see, a prime p is chosen random, another number is created by change 2 bit of p, then find the prime next to that number as q. The modulus n=p*q.

Let len is the length of p in bits minus, k is a natural number smaller than len and l=len-k, we have:

with x is a small number.

n can be represented as:

Let and , now we have:

We have p and q is odd primes so their difference is an even number, it means x is even and a, b is integers. Morever the integer a is closely with . So, if we know the random number k, we can factor n efficiently by travial method (similar to the Fermat’s factorization). Luckily, len is appropriate 540 so we have about 270 available value of k. Then we can brute force the value of k.

Now, extract the key by openssl:

By brute-forcing, we get k=117 and n be factored. Here is my script.

I got the elements, but i couldn’t find the modular inverse of e because e is a divisor of (p-1). So i used dq to compute m:

but that result still isn’t the flag, after add some times of q, finally i got the flag:

ASIS{Still____We_Can_Solve_Bad_F4!}