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
(ローカルで解いただけなので無し)