Analysis

In this challenge, we get the values of $c$ and $N$as well as the script that was used for generating $p$ and $q$:

import binascii
import random
from Crypto.Util.number import isPrime

flag = open("flag.txt", "rb").read().strip()
m = int(binascii.hexlify(flag), 16)

def genPrimes(size):
    base = random.getrandbits(size // 2) << size // 2
    base = base | (1 << 1023) | (1 << 1022) | 1
    while True:
        temp = base | random.getrandbits(size // 2)
        if isPrime(temp):
            p = temp
            break
    while True:
        temp = base | random.getrandbits(size // 2)
        if isPrime(temp):
            q = temp
            break
    return (p, q)

p, q = genPrimes(1024)
n = p * q
e = 0x10001

print("c:", pow(m, e, n))

The function genPrimes() looks quite complicated, but in essence:

• Get size//2 random bits, bit shift it size//2 bits to the left
• OR it with some stuff
• For both $p$ and $q$, generate size//2 more random bits and OR it with the original base until it's a prime number
• Return $p$ and $q$

Weaknesses

Clearly, there must be an implementation error in the genPrimes() function. One thing that you may noticed is that the first size//2 bits (in this case 512) are the same for both $p$ and $q$! This is because the first 512 bits are the random bits that make up base:

base = random.getrandbits(size // 2) << size // 2

Then in the two while loops, there are only ever size//2 bits randomised, and they aren't bit shifted but rather ORed with the base, meaning that only the last size//2 bits are randomised.

This has a side-effect of making $p$ and $q$ quite close numerically, i.e. $|p-q|$ is quite small. This opens $N$ up to Fermat Factorisation.

Fermat Factorisation

During Fermat Factorisation, we hope to find $a$ and $b$ such that

$$ a^2 - b^2 = N $$

Because that then means we can factorise the left-hand expression into

$$ (a+b)(a-b)=N $$

As thus we get the two factors of $N$ as $(a+b)$ and $(a-b)$.

The reason we use this when $p$ and $q$ are numerically close is because the closer they are to each other the closer they are to $\sqrt{N}$. If we say $a=\sqrt{N}$ rounded up to the nearest integer, we can calculate $b^2 = a^2-N$ (as rearranged from before) until $b$ is a whole number, after which we've solved the equation.