初赛
Unsafe Parameters
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha3_512
from secret import *
def genParams():
ns = []
es = []
ps = []
d = getPrime(425)
for _ in 'flag{':
p, q, r = [getPrime(512) for _ in range(3)]
ps.append((p, q, r))
n = p * q * r
totient = (p - 1) * (q - 1) * (r - 1)
es.append(inverse(d, totient))
ns.append(n)
return (ns, es), (d, ps)
pub, priv = genParams()
key = sha3_512(str(sum(sum(psum) for psum in priv[1])).encode()).digest()[:16]
ct = AES.new(key, AES.MODE_ECB).encrypt(pad(flag, 16))
print(f'ns = {pub[0]}')
print(f'es = {pub[1]}')
print(f'ct = {ct}')
"""
ns = [...]
es = [...]
ct = b'...'
"""这道题是基于Common Private Exponent Attack on Multi Prime RSA这篇paper的，设\(N_{\max}\)是模数中最大的一个，\(n\)为模数的个数，\(r\)为所有模数质因数的个数（在这里\(n=5,r=3\)），很显然，这里的\(d\)是一个\(425\)位的质数，满足文章中描述的：
$$
d<N_{\max}^{\delta_n},\delta_n<\frac{n}{r(n-1)}-\log_{N_{\max}}{(4r-2)}
$$
所以我们可以利用paper中提及的方式来进行攻击得到\(d\)，首先构造格：
$$
B=\left(\begin{matrix} M&e_1&e_2&e_3&e_4&e_5\\ &-N_1&&&&\\ &&-N_2&&&\\ &&&-N_3&&\\ &&&&-N_4&\\ &&&&&-N_5 \end{matrix}\right)
$$
其中\(M=\lfloor N_{\max}^{1-1/r}\rfloor\)，预期有：
$$
(d,k_1,k_2,k_3,k_4,k_5)B=(dM,1-k_1s_1,1-k_2s_2,1-k_3s_3,1-k_4s_4,1-k_5s_5)
$$
那么我们对格进行规约即可（满足条件的向量不一定在第一个，建议扫一遍所有向量），之后参考RSA: how to factorize N given d中的算法通过求出的\(d\)以及给出的所有\(e\)和\(N\)就可以分解所有\(N\)从而得到加密flag的key了：
from Crypto.Util.number import *
from random import *
from Crypto.Cipher import AES
from hashlib import sha3_512
ns = [...]
es = [...]
ct = b'J\x08\x0c\xfe\x0eC\n\x96!\xb3\x05\xa9\x9b\xf9\n\xe3-\xf2m\xdb&.\xb5h\xe1\x0e\xd6\x89\x14\x87Z\x0b0p\xbb\xd9\x93\xd7\x1cT\xa2\xf36\x02\x8e:\\\x92'
nn = max(ns)
L = matrix(ZZ, len(ns)+1, len(ns)+1)
for i in range(1, len(ns)+1):
L[0, i] = es[i-1]
L[i, i] = -ns[i-1]
M = floor(nn^(2/3))
L[0, 0] = M
res = L.LLL()[2]
d = abs(res[0] // M)
print(d)
def factor_with_ed(n, e, d):
k = e*d - 1
while True:
t = k
g = randint(2, n-1)
while t % 2 == 0:
t //= 2
x = pow(g, t, n)
y = gcd(x-1, n)
if x > 1 and y > 1:
return y, n // y
key = 0
for i in range(len(ns)):
pq, r = factor_with_ed(ns[i], es[i], d)
if pq < r:
pq, r = r, pq
p, q = factor_with_ed(pq, es[i], d)
key += p + q + r
key = sha3_512(str(key).encode()).digest()[:16]
pt = AES.new(key, AES.MODE_ECB).decrypt(ct)
print(pt)FMS
import os
import pty
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha256
from random import randrange
from string import ascii_letters, digits
flag = os.getenv('FLAG')
class PRNG:
def __init__(self, a=None, b=None, p=None, seed=None):
self.p = p if p else getPrime(128)
self.a = a if a else randrange(1, self.p)
self.b = b if b else randrange(0, self.p)
self.state = seed if seed else randrange(0, self.p)
def next(self):
self.state = (self.a * self.state + self.b) % self.p
return self.state
def randbytes(self, n):
out = b''
for _ in range(n):
out += bytes([self.next() % 256])
return out
def choices(self, seq, k):
return [seq[self.next() % len(seq)] for _ in range(k)]
def getPrime(self, n):
while True:
num = self.randbytes(n // 8)
p = bytes_to_long(num) | (1 << (n - 1)) | 1
if isPrime(p):
return p
def getrandbits(self, n):
num = self.randbytes((n + 7) // 8)
return bytes_to_long(num) & ((1 << n) - 1)
def __repr__(self):
return f'a = {self.a}\nb = {self.b}\np = {self.p}'
prng = PRNG()
Account = {"admin": sha256(("".join(prng.choices(ascii_letters + digits, 32))).encode()).hexdigest(),
"guest": "84983c60f7daadc1cb8698621f802c0d9f9a3c3c295c810748fb048115c186ec"}
user = None
menu = """Flag Management System
[L]ogin
[G]et Public Key
[R]ead Flag
[E]xit"""
if __name__ == "__main__":
while True:
print(menu)
op = input(">>> ").strip().upper()
if op == "L" or op == "LOGIN":
vcode = prng.randbytes(4).hex().rjust(8, '0')
print(f"Verification code: {vcode}")
username = input("Username: ").strip()
password = input("Password: ").strip()
verify = input("Verification code: ").strip()
if verify != vcode:
print("Verification code error!")
continue
if username in Account and Account[username] == sha256(password.encode()).hexdigest():
print(f"Welcome, {username}!")
user = username
else:
print("Login failed!")
elif op == "G" or op == "GET PUBLIC KEY":
print(prng)
elif op == "R" or op == "READ FLAG":
if user == "admin":
key = prng.randbytes(16)
iv = prng.randbytes(16)
aes = AES.new(key, AES.MODE_CBC, iv)
print(aes.encrypt(pad(flag.encode(), 16)).hex())
else:
print("Permission denied!")
elif op == "E" or op == "EXIT":
print("Goodbye!")
exit(0)
else:
print("Invalid option!")通过PRNG类的代码我们不难看出这里生成随机字节的函数实际上是实现了一个截断LCG，而admin账户的密码是PRNG类的choice生成的，要获得密码，我们首先需要获得seed，而在LOGIN这一步，我们每一次登录都会从PRNG中获得四个字节，那么进行s次登录我们就可以获得4s个字节，记为\(\{c_1,c_2,\cdots,c_{4s}\}\)，事实上每一个\(c_i\)都对应原先LCG的一个状态\(x_i\)，根据randbytes截断方法我们不难看出\(c_i=x_i\mod{256}\)，那么必有：
$$
c_i+256k_i=x_i
$$
这样的话我们就可以得到\(4k-1\)条关系：
$$
\begin{cases} a(c_1+256k_1)+b&\equiv c_2+256k_2\pmod{p}\\ a(c_2+256k_2)+b&\equiv c_3+256k_3\pmod{p}\\ &\vdots\\ a(c_{4s-1}+256k_{4s-1})+b&\equiv c_{4s}+256k_{4s}\pmod{p}\\ \end{cases}
$$
那么我们可以进行若干次登录来通过验证码获得足够多的\(c_i\)，之后就可以构造出上述关系，应用cuso（keeganryan/cuso）求解就可以恢复出\(k_1,k_2,\cdots,k_{4s}\)，从而恢复出\(x_1=256k_1+c_1\)，结合给出的\(a,b,p\)进行状态倒推就可以获得seed，从而利用题目给出的PRNG类来生成admin账户的密码、加密flag用的key和iv，这样就可以获得flag了：
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from hashlib import sha256
from random import randrange
from string import ascii_letters, digits
from pwn import *
import cuso
class PRNG:
def __init__(self, a=None, b=None, p=None, seed=None):
self.p = p if p else getPrime(128)
self.a = a if a else randrange(1, self.p)
self.b = b if b else randrange(0, self.p)
self.state = seed if seed else randrange(0, self.p)
def next(self):
self.state = (self.a * self.state + self.b) % self.p
return self.state
def randbytes(self, n):
out = b''
for _ in range(n):
out += bytes([self.next() % 256])
return out
def choices(self, seq, k):
return [seq[self.next() % len(seq)] for _ in range(k)]
def getPrime(self, n):
while True:
num = self.randbytes(n // 8)
p = bytes_to_long(num) | (1 << (n - 1)) | 1
if isPrime(p):
return p
def getrandbits(self, n):
num = self.randbytes((n + 7) // 8)
return bytes_to_long(num) & ((1 << n) - 1)
def __repr__(self):
return f'a = {self.a}\nb = {self.b}\np = {self.p}'
io = remote('127.0.0.1', 1145)
io.sendlineafter(b'>>> ', b'G')
exec(io.recvline().decode().strip())
exec(io.recvline().decode().strip())
exec(io.recvline().decode().strip())
sample = []
for _ in range(8):
io.sendlineafter(b'>>> ', b'L')
io.recvuntil(b'Verification code: ')
verify = io.recvline().strip()
print(verify)
for i in range(0, 8, 2):
sample.append(int(verify[i:i+2], 16))
io.sendlineafter(b'Username: ', b'guest')
io.sendlineafter(b'Password: ', b'guest')
io.sendlineafter(b'Verification code: ', verify)
print(sample)
k = [var(f'k{i}') for i in range(len(sample))]
relations = []
for i in range(len(sample) - 1):
f = a * (sample[i] + 256 * k[i]) + b - (sample[i + 1] + 256 * k[i + 1])
relations.append(f)
modulus = [p for _ in range(len(relations))]
bounds = {k[i]: (0, 2**120) for i in range(len(sample))}
roots = cuso.find_small_roots(relations, bounds, modulus)
print(roots)
state = sample[0] + 256 * roots[0][k[0]]
seed = state
for _ in range(33):
seed = (seed - b) * pow(a, -1, p) % p
prng = PRNG(a, b, p, seed)
password = "".join(prng.choices(ascii_letters + digits, 32)).encode()
io.sendlineafter(b'>>> ', b'L')
io.recvuntil(b'Verification code: ')
verify = io.recvline().strip()
io.sendlineafter(b'Username: ', b'admin')
io.sendlineafter(b'Password: ', password)
io.sendlineafter(b'Verification code: ', verify)
for _ in range(9):
trash = prng.randbytes(4)
io.sendlineafter(b'>>> ', b'R')
ct = bytes.fromhex(io.recvline().decode().strip())
key = prng.randbytes(16)
iv = prng.randbytes(16)
pt = AES.new(key, AES.MODE_CBC, iv).decrypt(ct)
print(pt)当然如果直接造格来打应该也是可以的.
决赛
Day1 | babyprng
import random
from dataclasses import dataclass
from typing import List, Tuple
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes
from secret import flag
MODULE_BITS = 512
BETA = 0.6
@dataclass(frozen=True)
class MaskSpec:
low_bits: int
high_shift: int
def keep_low(self, value: int) -> int:
return value & ((1 << self.low_bits) - 1)
def keep_high(self, value: int) -> int:
return (value >> self.high_shift) << self.high_shift
@dataclass
class LinearRecurrence:
modulus: int
coeffs: List[int]
history: List[int]
def tick(self) -> int:
nxt = (self.coeffs[0] * self.history[-1] + self.coeffs[1] * self.history[-2]) % self.modulus
self.history.append(nxt)
return nxt
@dataclass
class ClockworkPRNG:
n1: int
n2: int
x_rec: LinearRecurrence
y_rec: LinearRecurrence
z_trace: List[int]
@classmethod
def bootstrap(cls) -> "ClockworkPRNG":
n1 = getPrime(MODULE_BITS)
n2 = getPrime(MODULE_BITS)
a_coeffs = [random.randrange(1, n1) for _ in range(2)]
b_coeffs = [random.randrange(1, n2) for _ in range(2)]
x_seed = [random.randrange(1, n2) for _ in range(2)]
y_seed = [random.randrange(1, n2) for _ in range(2)]
z_seed = [((x_seed[i] - y_seed[i]) % n1) for i in range(2)]
return cls(
n1=n1,
n2=n2,
x_rec=LinearRecurrence(n1, a_coeffs, x_seed),
y_rec=LinearRecurrence(n2, b_coeffs, y_seed),
z_trace=z_seed,
)
def step(self) -> Tuple[int, int, int]:
x_val = self.x_rec.tick()
y_val = self.y_rec.tick()
z_val = (x_val - y_val) % self.n1
self.z_trace.append(z_val)
return x_val, y_val, z_val
@property
def a_coeffs(self) -> List[int]:
return self.x_rec.coeffs
@property
def b_coeffs(self) -> List[int]:
return self.y_rec.coeffs
MASK = MaskSpec(low_bits=int(MODULE_BITS * BETA), high_shift=int(MODULE_BITS * (1 - BETA)))
def gather_leakage(prng: ClockworkPRNG, count: int = 5) -> Tuple[List[int], List[int]]:
low_x, high_z = [], []
for _ in range(count):
x_val, _, z_val = prng.step()
low_x.append(MASK.keep_low(x_val))
high_z.append(MASK.keep_high(z_val))
return low_x, high_z
def encrypt_flag(prng: ClockworkPRNG) -> bytes:
pad = prng.step()[1]
plaintext = bytes_to_long(flag)
return long_to_bytes(pad ^ plaintext)
def emit_challenge():
engine = ClockworkPRNG.bootstrap()
xs, zs = gather_leakage(engine)
blob = encrypt_flag(engine)
print(engine.a_coeffs, engine.b_coeffs, engine.n1, engine.n2, xs, zs, blob)
if __name__ == "__main__":
emit_challenge() 代码有点复杂，但是整理一下就可以知道对于\(\{x_n\},\{y_n\},\{z_n\}\)三个随机数序列，有：
$$
\begin{aligned}
&x_{n}\equiv a_{0}x_{n-1} + a_{1}x_{n-2}\pmod{n_1}\\
&y_{n}\equiv b_{0}y_{n-1} + b_{1}y_{n-2}\pmod{n_2}\\
&z_{n}\equiv x_{n}-y_{n}\pmod{n_1}
\end{aligned}
$$
（其中\(n\ge2\)）
本题给出了\(a_0,a_1,b_0,b_1,n_1,n_2\)以及\(x_0,x_1,\cdots x_{4}\)的低307位以及\(z_0,z_1,\cdots,z_{4}\)的高308位，并且使用\(y_{5}\)与flag异或来加密flag，对于\(x_0,x_1,\cdots,x_{4}\)，设其低307位分别为\(X_0,X_1,\cdots,X_4\)，那么存在\(k_0,k_1,\cdots,k_{4}\in(0,2^{512-307}]\)使得：\(x_i=2^{307}k_{i}+X_i\)，所以可以知道：
$$
\begin{aligned}
&X_{2}+2^{307}k_{2}\equiv a_{0}(X_{1}+2^{307}k_{1})+a_{1}(X_{0}+2^{307}k_{0})\pmod{n_1}\\
&X_{3}+2^{307}k_{3}\equiv a_{0}(X_{2}+2^{307}k_{2})+a_{1}(X_{1}+2^{307}k_{1})\pmod{n_1}\\
&X_{4}+2^{307}k_{4}\equiv a_{0}(X_{3}+2^{307}k_{3})+a_{1}(X_{2}+2^{307}k_{2})\pmod{n_1}
\end{aligned}
$$
因为\(a_0,a_1,X_0,X_1,\cdots,X_4\)均已知，故上述三式均为线性方程使用cuso对上述三个方程进行求解即可得到\(k_{0},k_{1}\cdots,k_{4}\)，从而恢复\(x_0,x_1,\cdots,x_{4}\).
我们设\(z_0,z_1,\cdots,z_4\)的高308位分别为\(Z_0,Z_1,\cdots,Z_4\)，则存在\(s_0,s_1,\cdots,s_4\)使得\(z_i=Z_i+s_i\)，那么必然有：
$$
Z_i+s_i\equiv x_i-y_i\pmod{n_1}
$$
可以得到\(y_i\equiv x_i-(Z_i+s_i)\pmod{n_1}\)，但是因为\(\{y_n\}\)的递推是在\(\mathbb{Z}/n_2\mathbb{Z}\)上进行的，所以我们只能再引入未知量\(t_0,t_1,\cdots,t_4\)来将上式变为：
$$
y_i= x_i-(Z_i+s_i)+t_in_1
$$
那么根据\(\{y_n\}\)的递推关系可以得到三条方程：
$$
\begin{aligned}
&x_2-(Z_2+s_2)+t_2n_1\equiv b_{0}[x_1-(Z_1+s_1)+t_1n_1]+b_1[x_0-(Z_0+s_0)+t_0n_1]\pmod{n_2}\\
&x_3-(Z_3+s_3)+t_3n_1\equiv b_{0}[x_2-(Z_2+s_2)+t_2n_1]+b_1[x_1-(Z_1+s_1)+t_1n_1]\pmod{n_2}\\
&x_4-(Z_4+s_4)+t_4n_1\equiv b_{0}[x_3-(Z_3+s_3)+t_3n_1]+b_1[x_2-(Z_2+s_2)+t_2n_1]\pmod{n_2}
\end{aligned}
$$
其中\(0\le s_{i}\le2^{512-308},t_{i}\in{0,1}\)，利用cuso进行求解就可以得到\(s_{0},s_{1}\cdots,s_{4},t_{0},t_{1}\cdots,t_{4}\)，从而恢复出\(y_0,y_1,\cdots,y_{4}\)，最后只需要计算\(y_5= b_0y_{4}+b_{1}y_{3}\mod{n_2}\)，再用得到的结果与密文异或就可以得到flag了.
from sage.all import *
from cuso import find_small_roots
from Crypto.Util.number import *
a_coeff = [10622255399663562069145222517631074636757726505025087959277441735616749694319550854863797670443534651186783567693433208322290346562348465617862644514847389, 5150224460963481866238166841282851820818799947914254748673565625815793126729527793491938920282232686079347210569442266283305865531049268112169511496927746]
b_coeff = [5204753952338586880092348641669994129156178590855745261366232039885223974622545298276563525577443972124651339577891468011258412431471629386828307912459683, 5079734225447067974754947945327873911346636735905981526770074407711905651696829190513809796947471049379019689297209799730493816027786423191781843875675531]
n1 = 10958629774530192764747159728121861053823929124378086630226413004437630713430771741823493173237142084991026926121932444744870148381851604042781380970444669
n2 = 9200429328134412336748885997782239392391071834610532031258802195740647984625163693533960417075416851627572621668211171924294159251959827253934478090380211
xs = [172725921333705219686828397089776629172393055263012306396644606402731506210035516013543058124, 202745603270735608816524609283552093051331406448017971177380147701504875041184048198495558462, 68257763774743195610382299802371568139328884220019261062295558680693871404298028655323585656, 43570456098916056176492492662033934339435783469233318932894634807752715508937618248659738676, 81841093335490318218610136444202014180397509231955246448074176971442543798922263928961552133]
zs = [271002669418479642642553068844767379421050469420412042037755345994650216281759046698397156930164080245025575271381613567101064496930163675096593859608576, 211135275275860792942153398813833694516264877765852833336196411843651599326161620416771042200698342659972594458559247361195195948983619285219890713067520, 991565319401384342708138044676400067103250615156973756673688176776512913820178642376466735143963291078610359922261986209305378761794438074244766231429120, 7241056566248466988336854177955892118871557610915394850944392384375122314753075306409754732545646373509067809914409174184285627474963632984172466026840064, 5077484677424452789903502336300408141020037022065419442932638660556301184491285669822304104044377634411443772881151522717100856738472316902437457252843520]
ct = b'\xa9\xeb\x90\xab\t\x8a\xf1\xfe6y\xdf\xa8\xe7\x17\xa6\x9c\xc4|;q\x87_\xd3E\x1f)\x0bT\x08\x8a\xb6\x91c\xfcS\xab7\xc1\x13\x83\xcdgqp=RV\xd9\x82\xcf\xe8\xf9\xf7\xc3\xe2\x12_\xa4\xc7\x9fp\x07\x8a\x07'
k = [var(f"k{i}") for i in range(5)]
relations = []
for i in range(3):
x0 = xs[i] + k[i]*2**307
x1 = xs[i+1] + k[i+1]*2**307
x2 = xs[i+2] + k[i+2]*2**307
relations.append(x0 * a_coeff[1] + x1 * a_coeff[0] - x2)
bounds = {k[i]: (0, 2**(512-307)) for i in range(5)}
modulo = n1
solutions = find_small_roots(relations, bounds, modulo)
xs = [int(solutions[0][k[i]]) * 2**307 + xs[i] for i in range(5)]
s = [var(f"s{i}") for i in range(5)]
t = [var(f"t{i}") for i in range(5)]
relations = []
for i in range(3):
y0 = xs[i] - (zs[i] + s[i]) + t[i]*n1
y1 = xs[i+1] - (zs[i+1] + s[i+1]) + t[i+1]*n1
y2 = xs[i+2] - (zs[i+2] + s[i+2]) + t[i+2]*n1
relations.append(y0 * b_coeff[1] + y1 * b_coeff[0] - y2)
bounds = {s[i]: (0, 2**(512-308)) for i in range(5)}
for i in range(5):
bounds[t[i]] = (-100, 100)
modulo = n2
solutions = find_small_roots(relations, bounds, modulo)
zs = [int(solutions[0][s[i]]) + zs[i] for i in range(5)]
ys = [(xs[i] - zs[i]) % n1 for i in range(5)]
y = (ys[-1] * b_coeff[0] + ys[-2] * b_coeff[1]) % n2
print(long_to_bytes(bytes_to_long(ct) ^ y))Day2 | SSS?
from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import randint
from hashlib import md5
from secret import flag
def keygen(n, d):
assert n >= d
PR.<x> = PolynomialRing(QQ)
f = PR.random_element(degree=d)
share = [(i, f(i)) for i in range(1, n+1)]
return share, f.list()
def encrypt(msg, n, d):
share, sk = keygen(n, d)
enc = AES.new(key=md5(str(sk).encode()).digest(), nonce=b"SSS", mode=AES.MODE_CTR).encrypt(msg)
_ = [share[i] if randint(1, 1377) > 1337 else (0, 0) for i in range(n)]
return enc, _
enc, broken_share = encrypt(flag, 317, 137)
print("enc =", enc)
print("broken_share =", broken_share)通过代码很容易可以看出这是有理数域上的Shamir’s Secret Sharing，但是只会给出很少的点，因为\(f(x)\)是一个137次多项式，所以如果我们要用拉格朗日插值法来恢复\(f(x)\)，那么我们至少需要138个点，但是在输出文件中我们能拿到6个点，那么我们不太可能直接恢复，尝试用f = PR.random_element(degree=d)随机生成多项式可以发现这样生成的多项式的系数都是很小的，而对于获得的6个点\((x_0,y_0),(x_1,y_1),\cdots,(x_5,y_5)\)，有如下关系：
$$
\begin{aligned}
\sum_{k=0}^{137}a_kx_0^k-y_0&=0\\
\sum_{k=0}^{137}a_kx_1^k-y_1&=0\\
&\vdots\\
\sum_{k=0}^{137}a_kx_5^k-y_5&=0\\
\end{aligned}
$$
也就是：
$$
\left(\begin{matrix}
1&x_0&x_0^2&\cdots&x_0^{137}&-y_0\\
1&x_1&x_1^2&\cdots&x_1^{137}&-y_1\\
1&x_2&x_2^2&\cdots&x_2^{137}&-y_2\\
1&x_3&x_3^2&\cdots&x_3^{137}&-y_3\\
1&x_4&x_4^2&\cdots&x_4^{137}&-y_4\\
1&x_5&x_5^2&\cdots&x_5^{137}&-y_5\\
\end{matrix}\right)
\left(\begin{matrix}
a_0\\
a_1\\
\vdots\\
a_{137}\\
1
\end{matrix}\right)=\left(\begin{matrix}
0\\
0\\
0\\
0\\
0\\
0\\
\end{matrix}\right)
$$
也就是说，系数向量\((a_0,a_1,\cdots,a_{137},1)^{T}\)必然在矩阵：
$$
\left(\begin{matrix}
1&x_0&x_0^2&\cdots&x_0^{137}&-y_0\\
1&x_1&x_1^2&\cdots&x_1^{137}&-y_1\\
1&x_2&x_2^2&\cdots&x_2^{137}&-y_2\\
1&x_3&x_3^2&\cdots&x_3^{137}&-y_3\\
1&x_4&x_4^2&\cdots&x_4^{137}&-y_4\\
1&x_5&x_5^2&\cdots&x_5^{137}&-y_5\\
\end{matrix}\right)
$$
所张成的线性空间的核空间中，为了避免分数带来的误差，我们可以将上述矩阵的每一行都进行通分之后乘上共同分母，那么就会得到：
$$
\left(\begin{matrix}
D_0&D_0x_0&D_0x_0^2&\cdots&D_0x_0^{137}&-D_0y_0\\
D_1&D_1x_1&D_1x_1^2&\cdots&D_1x_1^{137}&-D_1y_1\\
D_2&D_2x_2&D_2x_2^2&\cdots&D_2x_2^{137}&-D_2y_2\\
D_3&D_3x_3&D_3x_3^2&\cdots&D_3x_3^{137}&-D_3y_3\\
D_4&D_4x_4&D_4x_4^2&\cdots&D_4x_4^{137}&-D_4y_4\\
D_5&D_5x_5&D_5x_5^2&\cdots&D_5x_5^{137}&-D_5y_5\\
\end{matrix}\right)
$$
求其右核可以得到其核空间的基，再规约找短向量就行：
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
enc = b'\xa3\xf7\xe1\xf9\x1bw\x15\xce\xc1\xaa\xa4\x1ch\tn\xbf\x8d\xc2\xf7\x1b\x8aXl\xa8Ra\x91>\xa9\xe4\xda`Z\x82t\x81\x83\xdfr\xa2'
broken_share = [...]
PR.<x> = PolynomialRing(QQ)
share = []
for xy in broken_share:
if xy == (0, 0):
continue
share.append(xy)
# print(share)
M = matrix(ZZ, len(share), 139)
for i in range(len(share)):
x, y = share[i]
D = lcm(x.denominator()^137, y.denominator())
for exp in range(138):
M[i, exp] = D * x^exp
M[i, -1] = -D * y
Ker = M.right_kernel_matrix()
res = Ker.LLL()
for v in res:
if v[-1] == 0:
continue
if v[-1] < 0:
v = -v
g = gcd(v)
coeff = [(QQ(c) // g) // QQ(v[-1]) for c in v[:-1]]
key = str(coeff).encode()
flag = AES.new(key=md5(key).digest(), nonce=b"SSS", mode=AES.MODE_CTR).decrypt(enc)
if b'flag' in flag:
print(flag)
breakDay2 | 777
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import randint, choices
from hashlib import md5
from secret import flag
import string
import os
m = 16
n = 64
p = getPrime(256)
a = randint(0, p^2 - 1)
Px = bytes_to_long("".join(choices(string.hexdigits.lower(), k = 45)).encode())
Py = bytes_to_long("".join(choices(string.hexdigits.lower(), k = 64)).encode())
b = (Py^2 - Px^3 - a * Px) % p^2
E = EllipticCurve(Zmod(p ^ 2), [a, b])
P = E(Px, Py)
Q = [randint(0, p - 1) * P for _ in range(m)]
c = [os.urandom(m) for _ in range(n)]
R = [sum([x * y for x, y in zip(ci, Q)]) for ci in c]
key = md5(str(sum(Q)).encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
ct = aes.encrypt(pad(flag, 16))
with open("output.txt", "w") as f:
f.write(str(Px % p) + "\n")
f.write(str([Ri.xy() for Ri in R]) + "\n")
f.write(ct.hex() + "\n")很显然，本题主要在\(\mathbb{Z}/p^2\mathbb{Z}\)的椭圆曲线\(E:y^2\equiv x^3+ax+b\pmod{p^2}\)上进行操作的，首先对于点\(P\)，生成16个随机数\(x_0,x_1,\cdots,x_{15}\)，计算\(Q_{i}=x_iP\)（\(i=0,1,\cdots,15\)），之后生成64组小随机数\(0\le c_{i,j}\le 255\)（\(0\le i\le 15,0\le j\le 63\)），有：
$$
R_j=\sum_{i=0}^{15}c_{j,i}Q_i
$$
即：
$$
\left(\begin{matrix}
c_{0,0}&c_{0,1}&\cdots&c_{0,15}\\
c_{1,0}&c_{1,1}&\cdots&c_{1,15}\\
\vdots&\vdots&\ddots&\vdots\\
c_{63,0}&c_{63,1}&\cdots&c_{63,15}\\
\end{matrix}\right)
\left(\begin{matrix}
Q_0\\
Q_1\\
\vdots\\
Q_{15}
\end{matrix}\right)=
\left(\begin{matrix}
R_0\\
R_1\\
\vdots\\
R_{63}
\end{matrix}\right)
$$
最后用\(Q_{sum}=Q_0+Q_1\cdots+Q_{15}\)来加密flag，并给出\(P_x\mod{p}\)，点\(R_0,R_1,\cdots,R_{63}\)以及密文，很显然我们需要先恢复曲线\(E\)才能进行后续操作，因为我们知道椭圆曲线\(E\)的64个点\(R_0,R_1,\cdots,R_{63}\)，所以我们可以借助这些点来恢复曲线\(E\)的参数\(a,b,p^2\)，我们取四个点（分别记为\((x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)\)），有：
$$
\begin{aligned}
y_1^2\equiv x_1^3+ax_1+b\pmod{p^2}\\
y_2^2\equiv x_2^3+ax_2+b\pmod{p^2}\\
y_3^2\equiv x_3^3+ax_3+b\pmod{p^2}\\
y_4^2\equiv x_4^3+ax_4+b\pmod{p^2}
\end{aligned}
$$
将第一第二式相减，可得：
$$
y_1^2-y_2^2\equiv x_1^3-x_2^3+a(x_1-x_2)\pmod{p^2}
$$
即可得：
$$
(y_1^2-y_2^2-x_1^3+x_2^3)(x_1-x_2)^{-1}\equiv a\pmod{p^2}
$$
同理：
$$
\begin{aligned}
(y_2^2-y_3^2-x_2^3+x_3^3)(x_2-x_3)^{-1}\equiv a\pmod{p^2}\\
(y_3^2-y_4^2-x_3^3+x_4^3)(x_3-x_4)^{-1}\equiv a\pmod{p^2}\\
(y_1^2-y_4^2-x_1^3+x_4^3)(x_1-x_4)^{-1}\equiv a\pmod{p^2}
\end{aligned}
$$
故有：
$$
\begin{aligned}
(y_1^2-y_2^2-x_1^3+x_2^3)(x_1-x_2)^{-1}-(y_2^2-y_3^2-x_2^3+x_3^3)(x_2-x_3)^{-1}\equiv 0\pmod{p^2}\\
(y_3^2-y_4^2-x_3^3+x_4^3)(x_3-x_4)^{-1}-(y_1^2-y_4^2-x_1^3+x_4^3)(x_1-x_4)^{-1}\equiv 0\pmod{p^2}
\end{aligned}
$$
也就是说：
$$
\begin{aligned}
(y_1^2-y_2^2-x_1^3+x_2^3)(x_2-x_3)-(y_2^2-y_3^2-x_2^3+x_3^3)(x_1-x_2)\equiv 0\pmod{p^2}\\
(y_3^2-y_4^2-x_3^3+x_4^3)(x_1-x_4)-(y_1^2-y_4^2-x_1^3+x_4^3)(x_3-x_4)\equiv 0\pmod{p^2}
\end{aligned}
$$
也就是说：
$$
\begin{aligned}
(y_1^2-y_2^2-x_1^3+x_2^3)(x_2-x_3)-(y_2^2-y_3^2-x_2^3+x_3^3)(x_1-x_2)=k_1p^2\\
(y_3^2-y_4^2-x_3^3+x_4^3)(x_1-x_4)-(y_1^2-y_4^2-x_1^3+x_4^3)(x_3-x_4)=k_2p^2
\end{aligned}
$$
求最大公约数就可以得到\(gcd(k_1,k_2)\cdot p^2\)了（因为\(\gcd(k_1,k_2)\)大概率不大，所以直接分解去掉小因子就能得到\(p^2\)），之后解如下方程就可以得到\(a,b\)：
$$
\begin{cases}
y_1^2\equiv x_1^3+ax_1+b\pmod{p^2}\\
y_2^2\equiv x_2^3+ax_2+b\pmod{p^2}
\end{cases}
$$
之后我们就可以关注前面提到的椭圆曲线HSSP问题：
$$
\left(\begin{matrix}
c_{0,0}&c_{0,1}&\cdots&c_{0,15}\\
c_{1,0}&c_{1,1}&\cdots&c_{1,15}\\
\vdots&\vdots&\ddots&\vdots\\
c_{63,0}&c_{63,1}&\cdots&c_{63,15}\\
\end{matrix}\right)
\left(\begin{matrix}
Q_0\\
Q_1\\
\vdots\\
Q_{15}
\end{matrix}\right)=
\left(\begin{matrix}
R_0\\
R_1\\
\vdots\\
R_{63}
\end{matrix}\right)
$$
很显然直接打正交格攻击是行不通的，所以要考虑是否可以将椭圆曲线的HSSP问题转换为数域上的HSSP问题，观察到这里的椭圆曲线是在\(\mathbb{Z}/p^2\mathbb{Z}\)上的，可能可以考虑从这里入手，询问AI可以知道我们可以利用p-adic对数这个同态映射来将曲线上的加法运算转化为整数环上的加法运算，对于一点\(R_i\)，映射的具体步骤如下：
- 将\(R_i\)的坐标提升到\(p\)进有理数域\(\mathbb{Q}_p\)上，记提升后的点为\(R_i’\)
- 之后计算\(R_i”=|E(\mathbb{Z}/p\mathbb{Z})|R_i’\)，将点\(R_i’\)映射到其形式群的内核
- 最后对于得到的\(R_i'(x_i,y_i)\)计算\(h_i\equiv\frac{-x_i}{y_ip}\pmod{p}\)
这样的话我们就可以将椭圆曲线的HSSP问题转换成数域上的HSSP问题了：
$$
\left(\begin{matrix}
c_{0,0}&c_{0,1}&\cdots&c_{0,15}\\
c_{1,0}&c_{1,1}&\cdots&c_{1,15}\\
\vdots&\vdots&\ddots&\vdots\\
c_{63,0}&c_{63,1}&\cdots&c_{63,15}\\
\end{matrix}\right)
\left(\begin{matrix}
Q_0\\
Q_1\\
\vdots\\
Q_{15}
\end{matrix}\right)=
\left(\begin{matrix}
R_0\\
R_1\\
\vdots\\
R_{63}
\end{matrix}\right)\Rightarrow
\left(\begin{matrix}
c_{0,0}&c_{0,1}&\cdots&c_{0,15}\\
c_{1,0}&c_{1,1}&\cdots&c_{1,15}\\
\vdots&\vdots&\ddots&\vdots\\
c_{63,0}&c_{63,1}&\cdots&c_{63,15}\\
\end{matrix}\right)
\left(\begin{matrix}
x_0\\
x_1\\
\vdots\\
x_{15}
\end{matrix}\right)=
\left(\begin{matrix}
h_0\\
h_1\\
\vdots\\
h_{63}
\end{matrix}\right)
$$
接下来就可以通过正交格攻击来恢复\(c_{i,j}\)了（但是直接攻击得到的向量中分量范围不在\([0,255]\)，所以我们还需要进行BFS来找到解空间中符合条件的向量），经测试发现，这样的向量一共有17条，而我们只需要16条，所以需要爆破所有\(C_{17}^{16}\)个向量组合来尝试求解下面这个方程了：
$$
\left(\begin{matrix}
c_{0,0}&c_{0,1}&\cdots&c_{0,15}\\
c_{1,0}&c_{1,1}&\cdots&c_{1,15}\\
\vdots&\vdots&\ddots&\vdots\\
c_{63,0}&c_{63,1}&\cdots&c_{63,15}\\
\end{matrix}\right)
\left(\begin{matrix}
Q_0\\
Q_1\\
\vdots\\
Q_{15}
\end{matrix}\right)=
\left(\begin{matrix}
R_0\\
R_1\\
\vdots\\
R_{63}
\end{matrix}\right)
$$
当然，直接用solve_left大概率是行不通的，那么我们可以尝试先求解：
$$
(x_0,x_1,\cdots,x_{63})
\left(\begin{matrix}
c_{0,0}&c_{0,1}&\cdots&c_{0,15}\\
c_{1,0}&c_{1,1}&\cdots&c_{1,15}\\
\vdots&\vdots&\ddots&\vdots\\
c_{63,0}&c_{63,1}&\cdots&c_{63,15}\\
\end{matrix}\right)=(1,1,\cdots,1)
$$
来找到满足下式的\(x_0,x_1,\cdots,x_{63}\)：
$$
\sum_{i=0}^{63}x_iR_i=\sum_{i=0}^{15}Q_i=Q_{sum}
$$
之后就可以直接计算我们需要的\(Q_{sum}\)，从而解出flag：
from Crypto.Cipher import AES
from Crypto.Util.number import *
from hashlib import md5
import itertools
m = 16
n = 64
Px = 92020820868814394988968261411073571398478104763002140061700066014545477552236
R = [...]
ct = bytes.fromhex("11bc7ed97bbe78d20b47be587b5cf5fe3f79c4823d8f56c3057fb0a3b57738bbd2940600bf2520e0fcd7b8d6be5abe98")
kpp1 = (R[0][1]^2-R[1][1]^2-R[0][0]^3+R[1][0]^3)*(R[1][0]-R[2][0])-(R[1][1]^2-R[2][1]^2-R[1][0]^3+R[2][0]^3)*(R[0][0]-R[1][0])
kpp2 = (R[2][1]^2-R[3][1]^2-R[2][0]^3+R[3][0]^3)*(R[0][0]-R[3][0])-(R[0][1]^2-R[3][1]^2-R[0][0]^3+R[3][0]^3)*(R[2][0]-R[3][0])
kM = gcd(kpp1, kpp2)
ps = list(factor(kM))
for p, e in ps:
if p.bit_length() == 256 and e == 2:
M = p^2
p = isqrt(M)
A = matrix(Zmod(M), [[R[0][0], 1], [R[1][0], 1]])
v = vector(Zmod(M), [R[0][1]^2 - R[0][0]^3, R[1][1]^2 - R[1][0]^3])
a, b = A.solve_right(v)
o = EllipticCurve(Zmod(p), [a, b]).order()
Qp2 = Qp(p, 5)
E_Qp2 = EllipticCurve(Qp2, [a, b])
h = []
for x, y in R:
xp2 = Qp2(x)
yp2 = (xp2^3 + Qp2(a)*xp2 + Qp2(b)).sqrt()
if yp2.lift() % p != y % p:
yp2 = -yp2
R_ = o * E_Qp2(xp2, yp2)
x1, y1 = R_.xy()
res = Integer(((-x1 / y1) / p).lift() % p)
h.append(res)
L = matrix(ZZ, n+1, n+1)
for i in range(n):
L[i, i] = 1
L[i, -1] = h[i]
L[-1, -1] = p
res = L.LLL()
candidate = []
for v in res:
if v[-1] == 0:
candidate.append(v[:-1])
M = matrix(ZZ, candidate[:n-m])
KerM = M.right_kernel().basis_matrix()
res = KerM.BKZ(block_size=20)
basis_vecs = [list(row) for row in res]
vs = basis_vecs + [[-x for x in v] for v in basis_vecs]
found, pool, queue = [], set(), []
for v in vs:
if all(0 <= x <= 255 for x in v):
t = tuple(v);
if t not in pool:
pool.add(t)
found.append(v)
queue = list(found)
while len(found) < m + 10 and queue:
now = queue.pop(0)
for v in vs:
candidate = [c + b for c, b in zip(now, v)]
if all(0 <= x <= 255 for x in candidate):
t = tuple(candidate)
if t not in pool:
pool.add(t)
found.append(candidate)
queue.append(candidate)
if len(found) >= m + 10:
break
if len(found) >= m + 10:
break
E = EllipticCurve(Zmod(p^2), [a, b])
R = [E(r) for r in R]
o2 = p * o
for vs in itertools.combinations(found, m):
l = list(vs)
A = matrix(QQ, l)
if A.rank() < m:
continue
v = vector(QQ, [1 for _ in range(m)])
res = A.solve_right(v)
Qsum = E(0)
for i in range(len(res)):
wn = int(res[i].numerator())
wd = int(res[i].denominator())
if gcd(wd, o2) != 1:
break
w = wn * inverse(wd, o2) % o2
Qsum += w * R[i]
key = md5(str(Qsum).encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
flag = aes.decrypt(ct)
if b'flag' in flag:
print(flag)
breakDay3 | SomethingHidden
from Crypto.Util.number import getPrime, inverse
from math import gcd
from hashlib import sha256
from Crypto.Cipher import AES
flag = b"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
class Alice:
def __init__(self) -> None:
p, q = getPrime(1024), getPrime(1024)
N = p * q
d = getPrime(int(2048 * 0.35))
phi = (p - 1) * (q - 1)
if gcd(d, phi) == 1:
e = inverse(d, phi)
self.sk = (p, q, d)
self.pk = (N, e)
self.partialkey = []
def RSAdecrypt(self, c):
_, _, d = self.sk
N, _ = self.pk
m = pow(c, d, N)
return m
class Bob:
def __init__(self) -> None:
self.secret = getPrime(1024)
self.partialkey = []
def RSAencrypt(self, pk, m):
N, e = pk
c = pow(m, e, N)
return c
A = Alice()
B = Bob()
print("A -> B:", A.pk)
pk = A.pk
N, e = pk
for _ in range(3):
Bm = B.secret * getPrime(512)
Bc = B.RSAencrypt(pk, Bm)
print("B -> A:", Bc)
Am = A.RSAdecrypt(Bc)
A.partialkey.append(getPrime(511))
Ac = A.RSAdecrypt(Am + A.partialkey[-1])
print("A -> B:", Ac)
B.partialkey.append((B.RSAencrypt(pk, Ac) - Bm) % N)
hfunc = sha256()
hfunc.update(str(B.partialkey).encode())
cipher = AES.new(hfunc.digest(), AES.MODE_ECB)
print("B -> A:", cipher.encrypt(flag))首先Alice和Bob协商出公钥\(N=pq\)以及\(e\)，其中\(e\)对应的私钥\(d<N^{2048\cdot0.35}\)（显然不能通过维纳攻击或者Boneh-Durfee攻击来求出\(d\)），之后Bob与Alice之间进行了三次通讯，对于第\(i\)（\(1\le i\le 3\)）次通讯，Bob生成了一个随机质数\(k_i\)，并于其私钥\(b\)相乘得到\(B_{mi}=k_ib\)，之后对其加密得到\(B_{ci}\equiv B_{mi}^{e}\pmod{N}\)，而Alice接收到\(B_{ci}\)之后则进行解密得到\(B_{mi}\)，并且生成了一个随机质数\(s_i\)，计算\(A_{mi}=B_{mi}+s_i\)之后进行一次RSA解密得到\(A_{ci}\equiv A_{mi}^d\pmod{N}\)，最后将\(A_{ci}\)发送给Bob，在三次通讯后，程序使用B.partialkey来对flag进行加密，通过分析可以知道B.partialkey实际上就是\([s_1,s_2,s_3]\). 很显然，我们需要通过Alice和Bob的通讯内容来恢复出\(s_1,s_2,s_3\)，也就是说我们需要先将\(A_{mi}\)以及\(B_{mi}\)恢复出来，\(A_{mi}\)显然是好恢复的，因为\(e\)我们是知道的，所以直接求\(A_{mi}\equiv A_{ci}^e\pmod{N}\)即可，这样我们就得到了：
$$
\begin{cases}
A_{m1}=B_{m1}+s_1=k_1b+s_1\\
A_{m2}=B_{m2}+s_2=k_2b+s_2\\
A_{m3}=B_{m3}+s_3=k_3b+s_3
\end{cases}
$$
因为\(k_i\)是512位的，\(s_{i}\)是511位的，而\(b\)是1024位的，很显然这是ACD（近似公约数）问题，通过构造如下格：
$$
\left(\begin{matrix}
2^{512}&A_{m2}&A_{m3}\\
0&-A_{m1}&0\\
0&0&-A_{m1}
\end{matrix}\right)
$$
规约就可以得到\(2^{512}k_1\)了，那么可以计算\(b=\lfloor A_{m1}/k_1\rfloor\)，从而就可以恢复出\(s_i=A_{mi}\mod{b}\)了：
from Crypto.Util.number import *
from hashlib import sha256
from Crypto.Cipher import AES
N = ...
e = ...
Ac = [..., ..., ...]
Bc = [..., ..., ...]
ct = b'|\x9aN\x16puZq\xb8R\xce\x84G\x06\xb0H\x91\xb4,\xd2\xba|\xac\x91\xbf"\xa7C\n\x82\xad\xa26s- 2\xc9[\xd5>\xa3\x81"t\xd2\x00"'
Am = [pow(c, e, N) for c in Ac]
L = matrix(ZZ, [[2^512, Am[1], Am[2]], [0, -Am[0], 0], [0, 0, -Am[0]]])
res = L.LLL()
k0 = int(abs(res[0][0])) // (2^512)
b = Am[0] // k0
s = [m % b for m in Am]
cipher = AES.new(sha256(str(s).encode()).digest(), AES.MODE_ECB)
print(cipher.decrypt(ct))