CODEGATE 2022 - PrimeGenerator

TL;DR

$p=U+l$ という形の素数が生成され、 $l$ だけがわかる。この入手は何度でも行える
$l$ を小さな素数で法をとることを繰り返せば、 $p$ が素数という条件が上手く効いて $U$ がある素数を法として幾つであるかを特定することが出来る
中国剰余定理を使って $U$ を求め、その結果から $N$ の片方の素因数をCoppersmith's Attackを使って解く

Prerequisite

中国剰余定理
Coppersmith's Attack

Writeup

次のスクリプトが動いている

#!/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}")

296bitの未知数 $u$ に対してUPPERが $u\times 2^{296}$ で定義されている。以下、UPPERを $U$ とおく。

接続すると次の2つのコマンドを実行出来る

素数生成: $p=U+l$ となるような素数 $p$ を生成し、下位ビットである $l$ だけを得る。これは最大10回まで同時に出来る
フラグの暗号化: $N=pq, e=65537$ でフラグを暗号化する。ここで $p,q$ はどちらも512bitであるが、 $p$ は1の素数生成で生成されたものを用いる

1を実行した時に得られた素数を $p_i \coloneqq U+l_i$ とおく。この時 $p_i - l_i = U$ となる。

ここで、両辺をある小さい素数 $p$ で法をとることを考える。例えば3で法をとると次のようになる。

$U = p_i - l_i \equiv \begin{cases} 0 \cr 1 \cr 2 \end{cases} \mod 3$

$l_i$ を移項すると次のようになる。

$p_i \equiv \begin{cases} l_i \cr l_1 + 1 \cr l_i + 2 \end{cases} \mod 3$

$p_i$ は素数であったから、右辺が $p$ (ここでは $3$ )の倍数、つまり $p$ を法として0と合同となることはありえない。よって、次のような関係がある。

$\begin{aligned} p_i \equiv l_i \mod 3 \Rightarrow l_i \not \equiv 0 \mod 3 \cr p_i \equiv l_i+1 \mod 3 \Rightarrow l_i \not \equiv 2 \mod 3 \cr p_i \equiv l_i+2 \mod 3 \Rightarrow l_i \not \equiv 1 \mod 3 \cr \end{aligned}$

$\begin{aligned} l_i \equiv 0 \mod 3 \Rightarrow p_i \not \equiv l_1 \mod 3 \Leftrightarrow U \not \equiv 0 \mod 3 \cr l_i \equiv 1 \mod 3 \Rightarrow p_i \not \equiv l_1+2 \mod 3 \Leftrightarrow U \not \equiv 2 \mod 3 \cr l_i \equiv 2 \mod 3 \Rightarrow p_i \not \equiv l_1+1 \mod 3 \Leftrightarrow U \not \equiv 1 \mod 3 \cr \end{aligned}$

一般化すると、 $l_i \equiv k \mod p \Rightarrow U \not \equiv -k \mod p$ となる。

当然だが、 $U$ に対して何かしらの $k_p$ が存在して $U \equiv k_p \mod p$ となる。よって、 $l_i$ を $p$ で法を取った結果を複数集めることで $U \not \equiv k_p \mod p$ となる $0\leq k_p \lt p$ を集めることになり、これが $p-1$ 個集まれば、残ったものが $U \equiv k_p \mod p$ となる。

これを異なる複数の $p$ で行ってから、中国剰余定理を用いると、 $p$ の総積が $U$ の上界である $2^{512}$ を超えていれば $U$ を求めることが出来る。

$U$ が求まって後はフラグを復号するだけなので2つ目のコマンドを用いて $N$ を得て素因数分解することを考える。これは、 $p =U+l \equiv 0 \mod p$ であるから、 $x+U \equiv 0 \mod p$ となる合同方程式を解くことになる。 $p$ は $N$ の約数なので約数を法とした合同方程式の解を求めるCoppersmith's Attackを用いれば $x=l$ が解の1つとなるので $U+l$ を計算して $p$ を求めて素因数分解出来る。

後はいつものRSAの復号を行って終わり。

Code

SageMathのシンタックスハイライトが効かないのが嫌だったので $U$ の導出はPythonだけで行っています(xcryptoは自作ライブラリ)。

$U$ の導出

from pwn import remote
from Crypto.Util.number import isPrime
from xcrypto.mod import crt


def choice(c):
    sc.recvuntil(b"> ")
    sc.sendline(str(c).encode())


def genprimes(num=10):
    choice(1)
    sc.recvuntil(b"> ")
    sc.sendline(str(num).encode())
    ls = []
    for _ in range(num):
        p = int(sc.recvline())
        ls.append(p)

    return ls


def encrypt_flag():
    choice(2)
    sc.recvuntil(b"n : ")
    n = int(sc.recvline())
    sc.recvuntil(b"c : ")
    c = int(sc.recvline())

    return (n,c)


def get_prime_list(cnt=100):
    ps = {}
    p = 2
    while cnt > len(ps):
        if isPrime(p):
            ps[p] = [False, [0 for _ in range(p)]]

        p += 1

    return ps

ps = get_prime_list()
done_ps = []
sc = remote("localhost", 13337)
sc.recvuntil(b"UPPER=")

cnt = 0

while True:
    cnt += 1

    ls = genprimes()
    for l in ls:
        for p in ps:
            if ps[p][0]:
                continue
            r = l % p
            r = -r % p
            ps[p][1][r] = 1

    for p in ps:
        if not ps[p][0] and sum(ps[p][1]) == p-1:
            ps[p][0] = True
            done_ps.append(p)

    prod = 1
    for p in done_ps:
        prod *= p

    if prod > 2**512:
        break

    print(f"[{cnt}]: {prod}")

n, c = encrypt_flag()
print(f"{n=}")
print(f"{c=}")

problem = []
a_list = []
m_list = []
for p in done_ps:
    for r, res in enumerate(ps[p][1]):
        if res == 0:
            problem.append((r, p))

U = crt(problem)
print(f"{U=}")

$p$ の導出 -> 復号

from Crypto.Util.number import long_to_bytes


n=4419682141838668174056472337796246322771088341617508330729828139372258630861586126006691712272624875341579641119907546374896459679600559451079885919176341160335040217367773399401084804372787213069180855942085113678673332316193505184679041301849547514904320689718488453643165483149308310951450306380658581023
c=2576197797103209297147112316980849323478673629853854533134082646554855831341338745041543067742963169783238878027507491132466399884354908201171176569122749401138191452067092638488933989713622478084659847677883769027939992970005691079323320422315021313059909497113372161557504568097587479680931808851606642301
U=384121792851371754101247263043200748807006798497173985986186817238142866305033619582167379814849963392130067437614010776041887693928962243932002011054080

beta = 0.49
print(U > n**beta)
PR.<x> = PolynomialRing(Zmod(n))
f = U+x
rs = f.small_roots(beta=beta, epsilon=1/50)

if len(rs) > 0:
    lower = rs[0]

p = U+int(lower)
assert n % p == 0
q = n // p
phi = (p-1)*(q-1)
d = inverse_mod(0x10001, phi)
pt = pow(c, int(d), n)

print(long_to_bytes(pt))

Flag

(ローカルで解いただけなので無し)