[Codegate 2022] PrimeGenerator

It was a great opportunity to author a problem & participate in the organizing process..!!

server.py

#!/usr/bin/python3
from Crypto.Util.number import *
import os

BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS

UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS
FLAG = b'codegate2022{this_is_a_sample_flag}'

while True:
lower = bytes_to_long(os.urandom(LOWER_BITS // 8))
p = UPPER | lower
if isPrime(p): return lower

q = getPrime(512)
e = 0x10001
n = p * q
return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)

while True:
print("1. Generate 10 random primes (only lower bits)")
print("2. Encrypt a flag")
idx = int(input("> "))
if idx == 1:
print("How many? (Up to 10)")
num = int(input("> "))
for _ in range(min(10, num)):
elif idx == 2:
print(f"n : {n}")
print(f"c : {c}")
UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS

It is known that n is efficiently factorized when partial bits of p is exposed. So our goal is to recover a UPPER.

menu1 is quite artificial and it gives a important "hint" of UPPER. For example, when we receive a number 16 through menu1, it refers that UPPER % 3 != 2, UPPER % 5 != 4, UPPER % 7 != 5, ... We can eliminate candidate remainder for specific primes.

By gathering enough informations(about 1200-1600 primes), UPPER can be recovered by Chinise remainder theorem. After that, flag is recovered by Coppersmith attack(RSA Factoring with high bits known attack).

TMI) I was planning to fix a FLAG padding but rbtree pointed out that if FLAG is fixed, FLAG^e is revealed after gather e = 0x10001 (n, c) pairs(It is well known attack when e = 3). Thanks rbtree!

solver.py

#!/usr/bin/sage
from Crypto.Util.number import *
from pwn import *
from sage.all import *
import math

r = remote("localhost", 9001)

BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS

primes = [ 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659]

remainders = [set([x for x in range(p)]) for p in primes]

def prod(L):
val = 1
for x in L:
val *= x
return val

def get_lower():
r.recvuntil(b"> ")
r.sendline(b"1")
r.recvuntil(b"> ")
r.sendline(b"10")
return [int(r.recvline()) for _ in range(10)]

def get_nc():
r.recvuntil(b"> ")
r.sendline(b"2")
r.recvuntil(b"n : ")
n = int(r.recvline())
r.recvuntil(b"c : ")
c = int(r.recvline())
return n, c

def rsa_high_bits_known(n, c, upper):
F.<x> = PolynomialRing(Zmod(n), implementation='NTL');
pol = x - upper
beta = 0.48  # we should have q >= N^beta
XX = 2 ** LOWER_BITS
epsilon = beta / 7
rt = pol.small_roots(XX, beta, epsilon)
q = int(gcd(rt - upper, n))
p = int(n) // int(q)
assert(p*q == n and p > 1 and q > 1)
phi = (p-1)*(q-1)
e = 0x10001
d = int(pow(e, -1, phi))
plain = int(pow(c, d, n))
print(long_to_bytes(plain))

#### STEP 1. Recover UPPER using crt ####
print("[+] STEP 1. Recover UPPER using crt")
crt_a = 
crt_m = [2**LOWER_BITS]

cnt = 0
while prod(crt_m) < 2**BITS:
cnt += 1
if cnt % 10 == 0:
print(f"Gather {cnt*10} primes.. progress : {int(100 * (math.log2(prod(crt_m))-LOWER_BITS) / UPPER_BITS)}%")
lowers = get_lower()
for lower in lowers:
for i in range(len(primes)):
rem = lower % primes[i]
if rem in remainders[i]:
remainders[i].remove(rem)
if len(remainders[i]) == 1:
crt_a.append(primes[i] - remainders[i].pop())
crt_m.append(primes[i])

upper = crt(crt_a, crt_m)
print(f"[+]UPPER = {upper.hex()}")

#### STEP 2. Recover FLAG using RSA Factoring with high bits known attack ###
print("[+] STEP 2. Recover FLAG using RSA Factoring with high bits known attack")
n, c = get_nc()
rsa_high_bits_known(n, c, upper)

#### 'CTF > Crypto' 카테고리의 다른 글

 [zer0pts CTF 2022] EDDH  (0) 2022.03.22 2022.03.22 2022.03.22 2022.02.28 2021.10.11 2021.10.11 2019.12.14
댓글 쓰기