CODEGATE 2022 Preliminary : Prime-Generator

10 Solves in General Division. Author : Barkingdog

 

#!/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}'
 
def menu1():
    while True:
        lower = bytes_to_long(os.urandom(LOWER_BITS // 8))
        p = UPPER | lower
        if isPrime(p): return lower
 
def menu2():
    p = UPPER + menu1()
    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)):
            print(menu1())
    elif idx == 2:
        n, c = menu2()
        print(f"n : {n}")
        print(f"c : {c}")

 

Solution

 

This is a RSA challenge. We see that menu1 generates primes that have equal upper 296 bits, i.e. $UPPER$. It then returns the value $lower$, which is the value of the lower 216 bits. If we can somehow find the value of $UPPER$, this leads us to knowing much more than half of the upper bits of $p$, so we will be able to factor $n$ via standard RSA attacks using coppersmith algorithm.

 

Now we focus on finding $UPPER$. Each time we are given $lower$, we know that $UPPER + lower$ is a prime. 

Therefore, for each small primes $p<700$, we actually have a relatively strong information $$UPPER + lower \not\equiv 0 \pmod{p}$$ or $$UPPER \not\equiv -lower \pmod{p}$$ which is good enough to remove one possible candidate of $UPPER \pmod{p}$. 

 

Given sufficient number of $lower$ such that $UPPER + lower$ is a prime, we will be able to remove all but one possible candidate for $UPPER \pmod{p}$ for each prime $p <700$. This essentially means that we can recover $UPPER \pmod{p}$ for each prime $p<700$.

 

Combining these information with Chinese Remainder Theorem along with the bound $UPPER < 2^{512}$ is strong enough to deduce the value of $UPPER$. This solves the problem. The code below is due to the challenge author barkingdog.

 

 

#!/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[0] - 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 = [0]
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)