朱雀
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
原文始发于微信公众号(Van1sh):2024 网鼎杯 朱雀&玄武
- 左青龙
- 微信扫一扫
- 右白虎
- 微信扫一扫
评论