Because how the  `n` (modulus of the RSA key) generation works the `n` - 1 must be divisible by `s` where `s` is the prime found based on the user input.For the input `000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000` the algorithm will generate a `1000000000000000000000000000` + `x` prime where `x` is a 16 bit number.That's really easy to bruteforce.
Based on this prime the program generates two other numbers `q` and `p`.
`p` =`((s * a * 2) + 1) ` where `a` is in `[1,s]` 
`q` =`((s * b * 2) + 1) ` where `b` is in `[1,s]`  and `b` != `a`
Because of the RSA `n` = `p` * `q` and we know `s` (from the bruteforce) if the `a+b` < `s`  (good chance) its really easy to find `a * b` and `a + b`.If we find the value of `a` and `b` we have the private key and they can be found by solving the quadratic equation.
```n = ((s * a * 2) + 1) * ((s * b * 2) + 1)n = (4 * s * s * a * b) + (2 * s * a + 2 * s * b) + 1  			/ - 1n - 1 = (4 * s * s * a * b) + (2 * s * a) + (2 * s * b)			/ / (2 * s)
(n - 1) / (2 * s) = (2 * s * a * b) + a + b			/ % s THIS ONLY WORKS IF a + b < s((n - 1) / (2 * s)) % s = a + b
(n - 1) / (2 * s) = (2 * s * a * b) + a + b							/ - a+b((n - 1) / (2 * s)) - (((n - 1) / (2 * s)) % s) = 2 * s * a * b		/ / (2 * s)(((n - 1) / (2 * s)) - (((n - 1) / (2 * s)) % s)) / (2 * s) = a * b```
POC:```#include <stdint.h>#include <string.h>#include <openssl/bn.h>#include <openssl/rsa.h>#include <openssl/pem.h>#include <openssl/err.h>
BIGNUM *g_BN_0;BIGNUM *g_BN_1;BIGNUM *g_BN_3;BIGNUM *g_BN_5;BIGNUM *g_BN_7;BN_CTX *g_BN_ctx;
void create_and_set(BIGNUM **bn, uint64_t val){	*bn = BN_new();	BN_set_word(*bn, val);}
void init_BN(){	create_and_set(&g_BN_0, 0LL);	create_and_set(&g_BN_1, 1LL);	create_and_set(&g_BN_3, 3LL);	create_and_set(&g_BN_5, 5LL);	create_and_set(&g_BN_7, 7LL);	g_BN_ctx = BN_CTX_new();}
RSA * createRsaStruct(BIGNUM * p, BIGNUM * q){    RSA *rsa; // [rsp+10h] [rbp-60h]    BIGNUM *n; // [rsp+18h] [rbp-58h]    BIGNUM *e; // [rsp+20h] [rbp-50h]    BIGNUM *d; // [rsp+28h] [rbp-48h]    BIGNUM * v7; // [rsp+30h] [rbp-40h]    BIGNUM * v8; // [rsp+38h] [rbp-38h]    BIGNUM * v9; // [rsp+40h] [rbp-30h]    BIGNUM *v10; // [rsp+48h] [rbp-28h]    BIGNUM *v11; // [rsp+50h] [rbp-20h]    BIGNUM *v12; // [rsp+58h] [rbp-18h]    BIGNUM * v13; // [rsp+60h] [rbp-10h]    BIGNUM * v14; // [rsp+68h] [rbp-8h]
    rsa = RSA_new();    n = BN_new();    e = BN_new();    d = BN_new();    v7 = BN_new();    v8 = BN_new();    v9 = BN_new();    v10 = BN_new();    v11 = BN_new();    v12 = BN_new();    v13 = BN_new();    v14 = BN_new();    BN_mul(n, p, q, g_BN_ctx);    BN_set_word(e, 0x10001LL);    BN_sub(v13, p, g_BN_1);    BN_div(0LL, v10, d, v13, g_BN_ctx);    BN_sub(v14, q, g_BN_1);    BN_div(0LL, v11, d, v14, g_BN_ctx);    BN_mod_inverse(v12, q, p, g_BN_ctx);    BN_gcd(v7, v13, v14, g_BN_ctx);    BN_mul(v8, v13, v14, g_BN_ctx);    BN_div(v9, 0LL, v8, v7, g_BN_ctx);    BN_mod_inverse(d, e, v9, g_BN_ctx);    rsa->p = p;    rsa->q = q;	printf("n: %s\n", BN_bn2hex(n));    rsa->n = n;    rsa->e = e;    rsa->d = d;    rsa->dmp1 = v10;    rsa->dmq1 = v11;    rsa->iqmp = v12;    return rsa;}
// cames from boooring sslint BN_sqrt(BIGNUM *out_sqrt, const BIGNUM *in, BN_CTX *ctx) {  BIGNUM *estimate, *tmp, *delta, *last_delta, *tmp2;  int ok = 0, last_delta_valid = 0;
  if (in->neg) {    return 0;  }  if (BN_is_zero(in)) {    BN_zero(out_sqrt);    return 1;  }
  BN_CTX_start(ctx);  if (out_sqrt == in) {    estimate = BN_CTX_get(ctx);  } else {    estimate = out_sqrt;  }  tmp = BN_CTX_get(ctx);  last_delta = BN_CTX_get(ctx);  delta = BN_CTX_get(ctx);  if (estimate == NULL || tmp == NULL || last_delta == NULL || delta == NULL) {    goto err;  }
  // We estimate that the square root of an n-bit number is 2^{n/2}.  if (!BN_lshift(estimate, BN_value_one(), BN_num_bits(in)/2)) {    goto err;  }
  // This is Newton's method for finding a root of the equation |estimate|^2 -  // |in| = 0.  for (;;) {    // |estimate| = 1/2 * (|estimate| + |in|/|estimate|)    if (!BN_div(tmp, NULL, in, estimate, ctx) ||        !BN_add(tmp, tmp, estimate) ||        !BN_rshift1(estimate, tmp) ||        // |tmp| = |estimate|^2        !BN_sqr(tmp, estimate, ctx) ||        // |delta| = |in| - |tmp|        !BN_sub(delta, in, tmp)) {      goto err;    }
    delta->neg = 0;    // The difference between |in| and |estimate| squared is required to always    // decrease. This ensures that the loop always terminates, but I don't have    // a proof that it always finds the square root for a given square.    if (last_delta_valid && BN_cmp(delta, last_delta) >= 0) {      break;    }
    last_delta_valid = 1;
    tmp2 = last_delta;    last_delta = delta;    delta = tmp2;  }
  if (BN_cmp(tmp, in) != 0) {    goto err;  }
  ok = 1;
err:  if (ok && out_sqrt == in && !BN_copy(out_sqrt, estimate)) {    ok = 0;  }  BN_CTX_end(ctx);  return ok;}
RSA *haxme(BIGNUM * n){	// Find the prime based on our input	BIGNUM * prime = BN_new();	BN_hex2bn(&prime, "1000000000000000000000000000");	BIGNUM * mod = BN_new();	for (int i = 0; i < 0x10000; i++)	{		BN_add_word(prime, 1);
		BN_mod(mod, n, prime, g_BN_ctx);		if (BN_cmp(mod, g_BN_1) != 0)			continue; 		printf("prime: %s\n", BN_bn2hex(prime));		break;	} 	BIGNUM *nm1 = BN_new();	BN_sub(nm1, n, g_BN_1);	BIGNUM *abp2aADDb = BN_new();	BIGNUM *rem = BN_new();	BN_div(abp2aADDb, rem, nm1, prime, g_BN_ctx);	BN_rshift1(abp2aADDb, abp2aADDb); 	BIGNUM *aADDb = BN_new();	BN_mod(aADDb, abp2aADDb, prime, g_BN_ctx); // a + b 	BIGNUM *aMULb = BN_new();	BN_sub(aMULb, abp2aADDb, aADDb);	BN_rshift1(aMULb, aMULb);	BN_div(aMULb, rem, aMULb, prime, g_BN_ctx); // a * b 	if (BN_cmp(rem, g_BN_0) != 0)	{		printf("FAIL\n");  // a + b > p #fixme		exit(0);	}  	BIGNUM *aADDbDIV2 = BN_new();	BN_rshift1(aADDbDIV2, aADDb); 	BIGNUM *tmp = BN_new();	BN_mul(tmp, aADDbDIV2, aADDbDIV2, g_BN_ctx);	BN_sub(tmp, tmp, aMULb); 	BN_sqrt(tmp, tmp, g_BN_ctx); 	BIGNUM *a = BN_new();	BN_add(a, aADDbDIV2, tmp);	printf("a: %s\n", BN_bn2hex(a)); 	BIGNUM *b = BN_new();	BN_sub(b, aADDbDIV2, tmp);	printf("b: %s\n", BN_bn2hex(b)); 	BIGNUM * p = BN_new();	BN_mul(p, prime, a, g_BN_ctx);	BN_lshift1(p, p);	BN_add(p, p, g_BN_1);     BIGNUM * q = BN_new();	BN_mul(q, prime, b, g_BN_ctx);	BN_lshift1(q, q);	BN_add(q, q, g_BN_1);     return createRsaStruct(p, q);}
void do_BN(){	FILE *f = fopen("pub.pem", "rb");    RSA *rsa = NULL;	PEM_read_RSAPublicKey(f, &rsa, 0, 0); 	rsa = haxme(rsa->n); 	FILE *fd = fopen("q.hex", "rb");	char data[1000];	int len = fread(data, 1, 1000, fd); 	char dec[1000];	memset(dec, 0, 1000);	RSA_private_decrypt(len, data, dec, rsa, 1); 	printf("%s\n", dec); 	int a, b;	sscanf (dec,"What's the sum of %d and %d?", &a, &b); 	int64_t x = a;	x += b; 	printf("%ld\n", x);}
void free_BN(){    BN_free(g_BN_0);    BN_free(g_BN_1);    BN_free(g_BN_3);    BN_free(g_BN_5);    BN_free(g_BN_7);}
int main(){	init_BN();	do_BN();    free_BN();    return 0LL;}```A little wrapper written in python:```#!/usr/bin/env python
import socket, binascii, os
HOST = 'coooppersmith.challenges.ooo'PORT = 5000
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)s.connect((HOST, PORT))
def readln(s):    data = ''    c = s.recv(1)    while c == None:        c = s.recv(1)    while c != '\n':        data = data + c        c = s.recv(1)        while c == None:            c = s.recv(1)    return data
s.sendall(b'000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000\n')
while readln(s) != '-----BEGIN RSA PUBLIC KEY-----':    pass
rsa = '-----BEGIN RSA PUBLIC KEY-----\n'
line = readln(s)while line != '-----END RSA PUBLIC KEY-----':    rsa += line + '\n'    line = readln(s)rsa += line + '\n'
open('pub.pem', 'wb').write(rsa)
while readln(s) != 'Question: ':    pass
question = readln(s)
open('q.hex', 'wb').write(binascii.unhexlify(question))
stream = os.popen('./keygen')output = stream.read()response = output.splitlines()[-1]print responseif response == 'FAIL':    exit()
s.sendall(response + '\n')
while readln(s) != 'Your flag message:':    pass
question = readln(s)
open('q.hex', 'wb').write(binascii.unhexlify(question))
stream = os.popen('./keygen')output = stream.read()
response = output.splitlines()[-2]print response```