DASCTF 2026

three_friends

题目

from Crypto.Util.number import *

flag = b"***********"

L = len(flag)
m1 = bytes_to_long(flag[:L//3])
m2 = bytes_to_long(flag[L//3:2*L//3])
m3 = bytes_to_long(flag[2*L//3:])

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)

e = 65537

n1 = p * q
n2 = q * r
n3 = p * r

c1 = pow(m1, e, n1)
c2 = pow(m2, e, n2)
c3 = pow(m3, e, n3)

print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"n3 = {n3}")
print(f"e = {e}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"c3 = {c3}")

"""
n1 = 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829
n2 = 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989
n3 = 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401
e = 65537
c1 = 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413
c2 = 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792
c3 = 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002
"""

思路

对n1，n2，n3两两求公因数可以得到p、q、r，分别计算出φ后再解出d即可

解答

from Crypto.Util.number import *

n1 = 110479112338979326841231465480900311437095583241804968504367003268478785311645575853029227541889465070127417880290972698509502098875302777600751062235679028180932171554996023850242418398546147652141811910224228666917788640895453721648601609529326886128507435254380985821439510394329605362511800619781782498829
n2 = 95225891725804035729098697183853172993650305271540351260130976375990969994680256179992972429701670943885218431291657615581872984046365977866046911929212400122026478512046580419614160900113488336302811792780327677539930592604198331529856760869923384410189400614767668529075682332352478496830621674767765967989
n3 = 111603865467493745511917065096450766019551858630764507502030413922630178420561431122201021143404521026218410173550594126191240832822627851633700772093095150654117699219949636045712687320990198957564564857885138504872560550777788915442814980338401072475446362026076893466520135409327492048388030114969050367401
e = 65537
c1 = 83456548767677952158133165776385438048214812740470347872014544040241661979735585698444752238351578159480247608435786172021153411975720140472715451216442036398970558532828923787921375318802867775369825882219621531795085442575971814645729572790836415339290407608988460626504016819536559945368010686567075802413
c2 = 55598291653542627898994967211126815679185160762475277667203320398466974811147081936849639204784572327753766773503264941715352990434513737784771805183050575481575095545922660276426069697449001567347723946016416649932633528235458091960122921036028416845355866656581114844470311590282808396786169332755296721792
c3 = 99617304265145206462280689337024202287720390645940568836285315412577937662785727570612881726190729195621460858194592258472873348744392240254689998279616123901037173010035977506212880680604466077172284894508163086916852071659627506881093976971048133795462670278664801263633610021626528113016267024450025017002

n=[n1,n2,n3]
c=[c1,c2,c3]

p=GCD(n1,n3)
q=GCD(n1,n2)
r=GCD(n2,n3)

fac=[(p,q),(q,r),(r,p)]
flag=b''
for ci,(a,b) in zip([c1,c2,c3],fac):
    d=inverse(e,(a-1)*(b-1))
    flag+=long_to_bytes(pow(ci,d,a*b))
print(flag.decode())

lattice_oracle

题目

from Crypto.Cipher import AES
import hashlib, os, json, random

flag = b"?"

n = 6
q = 97
m = 30

s = [random.randint(0, 3) for _ in range(n)]

A = []
b = []
for _ in range(m):
    a_i = [random.randint(0, q - 1) for _ in range(n)]
    e_i = random.randint(-1, 1)
    b_i = (sum(x * y for x, y in zip(a_i, s)) + e_i) % q
    A.append(a_i)
    b.append(b_i)

key = hashlib.sha256(str(s).encode()).digest()[:16]
iv = os.urandom(16)
pad_len = 16 - len(flag) % 16
enc = AES.new(key, AES.MODE_CBC, iv).encrypt(flag + bytes([pad_len]) * pad_len)

print(f"n = {n}")
print(f"q = {q}")
print(f"m = {m}")
print(f"A = {A}")
print(f"b = {b}")
print(f"iv = '{iv.hex()}'")
print(f"enc = '{enc.hex()}'")

"""
n = 6
q = 97
m = 30
A = [[94, 13, 86, 94, 69, 11], [54, 4, 3, 11, 27, 29], [77, 3, 71, 25, 91, 83], [69, 53, 28, 57, 75, 35], [20, 89, 54, 43, 35, 19], [43, 13, 11, 48, 12, 45], [77, 33, 5, 93, 58, 68], [48, 10, 70, 37, 80, 79], [73, 24, 90, 8, 5, 84], [37, 10, 29, 12, 48, 35], [81, 46, 20, 47, 45, 26], [34, 89, 87, 82, 9, 77], [21, 68, 93, 31, 20, 59], [34, 81, 88, 71, 28, 87], [77, 29, 4, 40, 51, 34], [27, 72, 91, 40, 27, 83], [50, 82, 58, 18, 33, 17], [95, 71, 68, 33, 95, 74], [74, 51, 46, 28, 17, 65], [11, 96, 6, 14, 19, 80], [87, 54, 76, 8, 49, 48], [59, 67, 32, 70, 1, 87], [14, 87, 68, 96, 34, 82], [14, 37, 55, 20, 58, 0], [92, 33, 64, 22, 64, 13], [38, 81, 64, 77, 25, 19], [20, 69, 67, 0, 76, 41], [2, 14, 46, 39, 30, 7], [72, 10, 10, 93, 62, 8], [16, 16, 84, 60, 70, 21]]
b = [56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28]
iv = 'bcdad772f7a0ec967887f7b8f36234c8'
enc = '00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc'
"""

思路

观察题目：

$$b_i=a_i*s_i+e_i \qquad 其中a_i \in [0,q-1],e_i \in [-1,1] $$

那么：

$$s_i=(b_i-e_i)*a_i^{-1}$$

对于e_i枚举一下即可

但是呢，这个s_i只有4个取值，所以直接爆破s要快些方便些

解答

from Crypto.Cipher import AES
import hashlib, os, json, random
from itertools import product
n = 6
q = 97
m = 30
A = [[94, 13, 86, 94, 69, 11], [54, 4, 3, 11, 27, 29], [77, 3, 71, 25, 91, 83], [69, 53, 28, 57, 75, 35], [20, 89, 54, 43, 35, 19], [43, 13, 11, 48, 12, 45], [77, 33, 5, 93, 58, 68], [48, 10, 70, 37, 80, 79], [73, 24, 90, 8, 5, 84], [37, 10, 29, 12, 48, 35], [81, 46, 20, 47, 45, 26], [34, 89, 87, 82, 9, 77], [21, 68, 93, 31, 20, 59], [34, 81, 88, 71, 28, 87], [77, 29, 4, 40, 51, 34], [27, 72, 91, 40, 27, 83], [50, 82, 58, 18, 33, 17], [95, 71, 68, 33, 95, 74], [74, 51, 46, 28, 17, 65], [11, 96, 6, 14, 19, 80], [87, 54, 76, 8, 49, 48], [59, 67, 32, 70, 1, 87], [14, 87, 68, 96, 34, 82], [14, 37, 55, 20, 58, 0], [92, 33, 64, 22, 64, 13], [38, 81, 64, 77, 25, 19], [20, 69, 67, 0, 76, 41], [2, 14, 46, 39, 30, 7], [72, 10, 10, 93, 62, 8], [16, 16, 84, 60, 70, 21]]
b = [56, 74, 51, 28, 10, 30, 34, 45, 82, 56, 62, 52, 5, 71, 35, 41, 86, 47, 8, 27, 64, 29, 57, 92, 34, 55, 57, 70, 87, 28]
iv = 'bcdad772f7a0ec967887f7b8f36234c8'
enc = '00ac1bac207e84d91c6243c4aead3576a20f996a5420eea7bfa0df3b61d68c83f283bd31f1fedf7465b6445d7a58dcdc'

iv=bytes.fromhex(iv)
enc=bytes.fromhex(enc)

def check_s(s):
    for a_i,b_i in zip(A,b):
        val=sum(x*y for x,y in zip(a_i,s))%q

        if (b_i-val)%q not in (0,1,q-1):
            return False

    return True

for s in product(range(4),repeat=n):
    s=list(s)

    if check_s(s):
        key=hashlib.sha256(str(s).encode()).digest()[:16]
        flag=AES.new(key,AES.MODE_CBC,iv).decrypt(enc)
        print(flag.decode())

phantom_sign

题目

import os, hashlib, json
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes, bytes_to_long

p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a  = 0
b  = 7
n  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

def inv_mod(val, mod):
    return pow(val, -1, mod)

def point_add(P, Q):
    if P is None: return Q
    if Q is None: return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and y1 != y2:
        return None
    if P == Q:
        lam = (3 * x1 * x1 + a) * inv_mod(2 * y1, p) % p
    else:
        lam = (y2 - y1) * inv_mod(x2 - x1, p) % p
    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p
    return (x3, y3)

def point_mul(k, P):
    R = None
    Q = P
    while k > 0:
        if k & 1:
            R = point_add(R, Q)
        Q = point_add(Q, Q)
        k >>= 1
    return R

G = (Gx, Gy)

flag = b"DASCTF{************************************}"
d = bytes_to_long(os.urandom(32)) % n

Q = point_mul(d, G)

NUM_SIGS = 40

messages = []
sigs = []

for i in range(NUM_SIGS):
    msg = f"transaction_{i:04d}".encode()
    h_i = int(hashlib.sha256(msg).hexdigest(), 16) % n
    k_i = bytes_to_long(os.urandom(31))
    R_i = point_mul(k_i, G)
    r_i = R_i[0] % n
    s_i = inv_mod(k_i, n) * (h_i + d * r_i) % n
    messages.append(msg.decode())
    sigs.append((h_i, r_i, s_i))

key = hashlib.sha256(long_to_bytes(d)).digest()[:16]
iv = os.urandom(16)
enc = AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16))

output = {
    "curve": {"p": p, "a": a, "b": b, "n": n, "Gx": Gx, "Gy": Gy},
    "Q": [Q[0], Q[1]],
    "messages": messages,
    "signatures": [(h, r, s) for h, r, s in sigs],
    "iv": iv.hex(),
    "enc": enc.hex(),
}

with open("data.json", "w") as f:
    json.dump(output, f, indent=2)

思路

已知40组：$$s_i \equiv \frac{h_i+d*r_i}{k_i} \pmod n \qquad 其中k_i是较小的，目标求d$$

$$\Rightarrow k_i\equiv \frac{h_i}{s_i}+\frac{r_i}{s_i}d \pmod n \Rightarrow k_i=\frac{h_i}{s_i}+\frac{r_i}{s_i}d-\lambda_i n$$

$$k_i

$$\begin {pmatrix} -\lambda_1,-\lambda_2,…,-\lambda_{40},d,1 \end {pmatrix} * \begin {pmatrix} An & 0 & \cdots & 0 & 0 & 0 \ 0 & An & \cdots & 0 & 0 & 0 \ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \ 0 & 0 & \cdots & An & 0 & 0 \ AR_1 & AR_2 & \cdots & AR_{40} & 1 & 0 \ AH_1 & AH_2 & \cdots & AH_{40} & 0 & AK \end {pmatrix} = \begin {pmatrix} Ak_1,Ak_2,…,Ak_{40},d,AK \end {pmatrix}$$

$$其中A=2^8$$

$$但是这样似乎算不出来，这里k_i\in [0,K)，为了使向量更短可以考虑构造偏移：$$

$$\begin {pmatrix} -\lambda_1,-\lambda_2,…,-\lambda_{40},d,1 \end {pmatrix} * \begin {pmatrix} An & 0 & \cdots & 0 & 0 & 0 \ 0 & An & \cdots & 0 & 0 & 0 \ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \ 0 & 0 & \cdots & An & 0 & 0 \ AR_1 & AR_2 & \cdots & AR_{40} & 1 & 0 \ A(H_1-\frac{K}{2}) & A(H_2-\frac{K}{2}) & \cdots & A(H_{40}-\frac{K}{2}) & 0 & AK \end {pmatrix} = \begin {pmatrix} A(k_1-\frac{K}{2}),A(k_2-\frac{K}{2}),…,A(k_{40}-\frac{K}{2}),d,AK \end {pmatrix}$$

$$这样A(k_i-\frac{K}{2})\in [-\frac{K}{2},\frac{K}{2}]$$

解答

import os, hashlib, json
from Crypto.Util.number import *
import gmpy2
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
data=json.load(open("data.json","r"))
p  = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n=ZZ(data["curve"]["n"])
a=ZZ(data["curve"]["a"])
b=ZZ(data["curve"]["b"])
Gx=ZZ(data["curve"]["Gx"])
Gy=ZZ(data["curve"]["Gy"])

Qx=ZZ(data["Q"][0])
Qy=ZZ(data["Q"][1])
signs=data["signatures"]

A=2**8
K=2**248
B=2**256

R=[]
H=[]

for h,r,s in signs:
    si=gmpy2.invert(s,n)

    R.append((r*si)%n)
    H.append((h*si)%n)

rows=[]
for i in range(40):
    row=[0]*42
    row[i]=n*A
    rows.append(row)

rows.append([x*A for x in R]+[1,0])
rows.append([(x-K//2)*A for x in H]+[0,B])

M=Matrix(ZZ,rows)
L=M.LLL()
d=None

F=GF(p)
E=EllipticCurve(F,[a,b])
G=E(Gx,Gy)
Q=E(Qx,Qy)

for row in L.rows():
    if abs(row[-1])!=B:
        continue
    if row[-1]==B:
        d=int(row[-2])%n
    else:
        d=ZZ(-row[-2])%n

    if d*G==Q:
        print(d)
        break
key = hashlib.sha256(long_to_bytes(d)).digest()[:16]
iv=bytes.fromhex(data["iv"])
enc=bytes.fromhex(data["enc"])
pt = unpad(AES.new(key,AES.MODE_CBC,iv).decrypt(enc),16)
print(pt.decode())        

#69733894115169365517439430123407937761015055472912247236884018827222720875663
#DASCTF{3cd5a_b1as3d_n0nc3_HNP_l4tt1c3_4ttack!}