朱雀

crypto002

各位朱雀组参赛选手请注意，平台新增“CRYPTO02”赛题提示：
提示信息如下：请根据提示信息进一步完成解题。

（1）RSA模数 n：

0x00b8cb1cca99b6ac41876c18845732a5cbfc875df346ee9002ce608508b5fcf6b60a5ac7722a2d64ef74e1443a338e70a73e63a303f3ac9adf198595699f6e9f30c009d219c7d98c4ec84203610834029c79567efc08f66b4bc3f564bfb571546a06b7e48fb35bb9ccea9a2cd44349f829242078dfa64d525927bfd55d099c024f

（2）素数 p 的高位：

0xe700568ff506bd5892af92592125e06cbe9bd45dfeafe931a333c13463023d4f0000000000000000000000000000000000000000000000000000000000000000

（3）加密指数 e：

0x10001

（4）加密消息文件：flag.enc，你需要读取并解密此文件。

你的任务是通过给定的信息恢复素数 p，计算私钥 d，并解密加密消息以获得 flag。

这题就没啥弯弯绕绕的了，就是一个已知 p 高位攻击，已知的比特是 256 位的，只有一半，直接 copper 是 copper 不出的，需要爆破一下。

爆破之前，可以先在本地测一下，什么样的参数，多少位能出，这样能够节省一些时间。

from Crypto.Util.number import *
import time
p = getPrime(512)
q = getPrime(512)
n = p * q

s = time.time()
R.<x> = Zmod(n)[]

f = (p>>248)<<248
f += x
f.small_roots(X=2^248,beta = 0.49,epsilon = 0.014)
print(time.time()-s)

我这里测的用 epsilon = 0.014 能出 248 比特，用 win 下的 sagemath 虚拟机一个要跑 9 秒左右，总共爆破 8 比特，需要大概 38 分钟。可以考虑一下多进程。

crypto003

#!/usr/bin/env python3

import random
from sympy import nextprime
from gmpy2 import is_prime
from Crypto.Util.number import getPrime, bytes_to_long
from Secret import flag

m = bytes_to_long(flag)

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 2999

f = open("out.txt", 'w')

p1 = getPrime(1024)
q1 = nextprime(2024 * p1)
n1 = p1 * q1
f.write("n1 = {0}n".format(n1))

p2 = getPrime(1024)
q2 = 1
while q2 < p2:
    q2 = getPrime(1024)
n2 = p2 * q2
n22 = p2 * p2 + q2 * q2
f.write("n2 = {0}n".format(n2))
f.write("n22 = {0}n".format(n22))

r = random.getrandbits(1024)
p3 = r
while not is_prime(p3):
    p3 += random.getrandbits(400)
q3 = r
while q3 < p3:
    q3 += random.getrandbits(500)
while not is_prime(p3):
    q3 += random.getrandbits(500)
n3 = p3 * q3
f.write("n3 = {0}n".format(n3))

m1 = p1 * m * m + p2 * m + p3
m2 = q1 * m * m + q2 * m + q3
c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

f.write("n = {0}n".format(n))
f.write("c1 = {0}n".format(c1))
f.write("c2 = {0}n".format(c2))

一共套了三层，

p1 = getPrime(1024)
q1 = nextprime(2024 * p1)
n1 = p1 * q1

第一层直接给 n1//2024 开根就好了。

p2 = getPrime(1024)
q2 = 1
while q2 < p2:
    q2 = getPrime(1024)
n2 = p2 * q2
n22 = p2 * p2 + q2 * q2
f.write("n2 = {0}n".format(n2))
f.write("n22 = {0}n".format(n22))

第二层就是解一个二元二次方程，也没啥。

r = random.getrandbits(1024)
p3 = r
while not is_prime(p3):
    p3 += random.getrandbits(400)
q3 = r
while q3 < p3:
    q3 += random.getrandbits(500)
while not is_prime(p3):
    q3 += random.getrandbits(500)
n3 = p3 * q3
f.write("n3 = {0}n".format(n3))

第三层有 bug，两行都是 while not is_prime(p3):，这就导致 q3 根本不是素数（除非一发入魂了，那是真的没话讲），不过似乎也不太影响解题。

本地生成了一组数据测一下，大概高 528 比特是一样的。直接对 n 开根得到 p 的高位，然后直接已知 p 高位攻击（故技重施）。

于是根据大小关系，我们能获得 p1,p2,p3,q1,q2,q3

我们还有两条式子

由于 m 是这两个式子的共同的根，所以对这两个式子做一个 gcd 就可以了。但是 次数比较大，直接 gcd 会炸掉，这里要用一下 fast_polynomial_gcd，在 2023 SEECTF 里有用到过。

github上有一个 crypto-attacks 项目，里面有一个 fast_polynomial_gcd

Van1sh，公众号：Van1sh2023 SEECTF（see you again~）

玄武

crypto001

# SageMath version 10.0, Release Date: 2023-05-20

from sage.all import *
from Crypto.Util.number import *

from secret import flag
flag = flag.lstrip(b"wdflag{").rstrip(b"}")

class ShamirSS:
    def __init__(self, coefs, value):
        self.coefs = coefs
        self.value = value

class ShamirProtocol:
    def __init__(self, n_players, threshold, modulus):
        self.n_players = n_players
        self.threshold = threshold
        
        assert isPrime(modulus), "Modulus must be a prime number"
        self.modulus = modulus
        
        
    def input_share(self, values):
        coefs = [
            [getRandomRange(1, self.modulus) for _ in range(self.threshold)]
            for _ in range(self.n_players)
        ]

        randoms = values + [getRandomRange(1, self.modulus) for _ in range(self.threshold - len(values))]

        values = [
            sum([r * c for r, c in zip(randoms, coef)]) % self.modulus
            for coef in coefs
        ]
        shares = [ShamirSS(coef, value) for coef, value in zip(coefs, values)]
        return shares
    
protocol = ShamirProtocol(len(flag), len(flag) * 2, 257)
values = list(flag)

import os
os.mkdir("shares")

for i in range(10000):
    shares = protocol.input_share(values)
    save(shares, f"shares/share_{i}.sobj")

题目一共10000份数据，设 flag 的字节长度为 n，那么每份数据包含 n 个 2*n 项一次多项式。设除flag外的数据为噪声 g， 那么我们有

我们可以把它画成矩阵的样子，对于一组数据，我们有

其中，所有的 coef 我们都是知道的。这里需要头脑风暴一下，假设如果 coef2 所表示的 矩阵不满秩，那么我们就能在其左零空间找到一条向量 ，然后式子两边都左乘一个 ，这样我们就能消掉 g 那部分向量的影响了。（因为 ）

然后经过测试，发现10000条数据里有 32 份数据满足我们上面的设想。而刚好我们 flag 字节长度 ，于是我们解一个线性方程组就能把 flag 求出来了。

class ShamirSS:
    def __init__(self, coefs, value):
        self.coefs = coefs
        self.value = value
from tqdm import *
p=257
NEWV = []
FLAG = True
index=0
for i in trange(10000):
    s = load('share_%d.sobj'%i)
    C1 = matrix(GF(p),[ss.coefs[:32] for ss in s])
    C2 = matrix(GF(p),[ss.coefs[32:] for ss in s])
    V = vector(GF(p),[ss.value for ss in s])
    if C2.rank()<32:
        Ck = C2.left_kernel().basis()
        CK = Matrix(GF(p),Ck)
        newC1 = CK * C1 
        newV = CK * V
        if FLAG:
            NEWC1 = newC1
            NEWV.append(newV)
            FLAG = False
            continue
        NEWC1 = NEWC1.stack(newC1)
        NEWV.append(newV)
        index += 1
NEWV = [i[0] for i in NEWV]
NEWV = vector(GF(p),NEWV)
FLAG =  (NEWC1.solve_right(NEWV))
print(''.join(chr(i) for i in FLAG))

# sage: print(''.join(chr(i) for i in FLAG))
# 197de281fd12e95eba04e7b84539fc8c