W'Blog

Wbuildings的自勉小屋

0%

DASCTF 2024暑期挑战赛

发表于 分类于 Valine：
本文字数： 31k 阅读时长 ≈ 28 分钟

能从中学习到很多

complex_enc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Util.number import *
import random
from secret import flag


def GET_KEY(n):
    sum=2
    key=[1]
    for i in range(n):
        r=random.randint(0,1)
        x=sum+random.randint(0,n)*r
        key.append(x)
        sum+=x
    return key

def enc(m,k):
    cipher_list = []
    for i in range(len(m)):
        if m[i] == 1:
            cipher_list.append(m[i] * k[i])
    cipher = sum(cipher_list)
    return cipher

m=bytes_to_long(flag)
m = [int(bit) for byte in flag for bit in format(byte, '08b')]
key=GET_KEY(len(m))
c=enc(m,key)

with open('output.txt', 'w') as f:
    f.write(str(c))
    f.write(str(key))

背包密码

1
2
3
4
5
6
7
n = len(key)
d = n / log(max(key), 2)
print(CDF(d))
assert CDF(d) < 0.9408

# 0.9899087608789052
# AssertionError

似乎 格打不了

那就利用背包密码的超递增序列性质 来解题

注意到最开始有 key = [1] ，这里已经垫了一个 1，所以key 的长度比 m 大一，最后一个key并没有用上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *

c =
key =

m = ''
for i in key[::-1]:
    if c >= i:
        m = '1' + m
        c -= i
    else:
        m = '0' + m
        
flag = long_to_bytes(int(m[:-1],2))
# flag = long_to_bytes(int(m+'0'*7,2))
print(flag)

m= [m[i:i + 8] for i in range(0, len(m), 8)]
decoded_string = ''.join(chr(int(''.join(map(str, byte)), 2)) for byte in m)
print(decoded_string)

# DASCTF{you_kn0w_b@ckpack_Crypt0?}

用厨子有奇效，就不用注意多出来的0或者1了，也可以手动处理，如上

（int 似乎默认是从后面（低位）开始数八位来转换，所以填充或者去掉就很有必要）

1z_RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *
from sympy import *
import os
from secrets import flag

nbit =130
e = 3
l = getPrime(505)
m = bytes_to_long(flag + os.urandom(64))

assert len(flag) == 29

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    PQ = int(str(p<<120)+str(q))
    QP = int(str(q<<120)+str(p))
    if isPrime(PQ) and isPrime(QP):
        break

n = PQ * QP
PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ
M = pow(m,1,l)
c = pow(m,e,N)

print('n =', n)
print('M =', M)
print('l =', l)
print('c =', c)

'''
n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691
M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
'''

求 p，q

1，通过取模的方式 + 解方程 得到 p，q

x = len(str(q))， 39 , 40

y = len(str(p))

令x = 39，y = 40，则有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import getPrime

p = getPrime(130)
q = getPrime(130)

print(len(str(q)))
print(len(str(p)))

print(((p**2+10*q**2)*2**120*10**39).bit_length())
print(((2**240*10**79+1)).bit_length())
print(2**10)

# 39
# 40
# 512
# 503
# 1024

可以看到 $2^{240}*10^{79}+1$ 略小于

数值并不大，当我们 两边 $// (2^{240}*10^{79}+1) $ 的 时候

i 可以采取爆破的方法得到

第一个方程有了，第二个方程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sympy
from tqdm import *

n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691

for i in trange(2**10):
    pq = n // (2**240 * 10**79 + 1) - i
    pq2 = (n - pq*(2**240 * 10**79 + 1)) // (2**120 * 10**39)
    if (n - pq*(2**240 * 10**79 + 1)) % (2**120 * 10**39) == 0:     # 倍数
        p, q = sympy.symbols('p q')
        flag = sympy.solve([pq - p*q,pq2-(p**2+10*q**2)],[p,q])
        break

p = abs(flag[0][0])
q = abs(flag[0][1])
print(p,q)

# 1213149261930568621267125437333569321667 855604426214387476576649090490109822073

2，二元copper

1
2
R.<x,y> = PolynomialRing(Zmod(n^2))
roots = small_roots(f,(2^130,2^130),m=1,d=4)

构造出正确的多项式 f 之后，bounds 是 小根的上界，一般都已知

m为移位（shifts），d 为多项式中的最高幂。（这两个具体咋写值也不是很清楚，直接爆破，1-4试呗🥲）

m越大，跑的越慢，但精度更高

需要注意的是模数 n ，Zmod(n)，如果我们求出的根是 0,0，两个零，那可能是模数小了，乘个 k 倍，或者 如上，n^2，

1
2
PR.<p,q> = PolynomialRing(Zmod(n))
f = ((2*p+1)*2^120*10^39+(2*q+1))*((2*q+1)*2^120*10^40+(2*p+1))

也可以用上p，q是素数的性质（糖醋小鸡块师傅😍）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from Crypto.Util.number import long_to_bytes
import itertools
import sys


def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691

lenght = [39,40]
for i in lenght:
    for j in lenght:
        print((i, j))
        R.<x,y> = PolynomialRing(Zmod(n^2))
        PQ = x*2^120*10^i + y
        QP = y*2^120*10^j + x
        f = n - PQ*QP
        roots = small_roots(f,(2^130,2^130),m=1,d=4)
        if roots !=[]:
            # print(roots)
            p,q = roots[0]
            print(p,q)
            break
 
# 1213149261930568621267125437333569321667 855604426214387476576649090490109822073

扩展

不知名的一道题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *
from secret import flag

nbit =128
while True:
    p, q= getPrime(nbit), getPrime(nbit)
    PQ = int(str(p<<256)+str(q))
    QP = int(str(q<<256)+str(p))
    if isPrime(PQ) and isPrime(QP):
        break

e=0x10001
N = PQ * QP
n = p * q
m=bytes_to_long(flag)
c=pow(m,e,n)


print('N =', N)
print('c=',c)

'''
N = 1085674311530255489464290129824772067886812106070317576328547361171348401864749700142226317981052597718932148985813969001766383466131904811646438034866606166860409715940892963991884944642366896061549360382036310506993659981270186354624380079666262454880589702937061510841107889532190435909694042809685218422473
c= 56930360094664103380901535309475311481122482721421214918816986675606014573458
'''

当时解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import libnum
from xenny.ctf.crypto.modern.asymmetric.rsa import factor

N = 1085674311530255489464290129824772067886812106070317576328547361171348401864749700142226317981052597718932148985813969001766383466131904811646438034866606166860409715940892963991884944642366896061549360382036310506993659981270186354624380079666262454880589702937061510841107889532190435909694042809685218422473
c = 56930360094664103380901535309475311481122482721421214918816986675606014573458
e = 65537

bit = str(bin(N)[2:])
n = int('0b'+bit[1027//4*3:],2)

p,q = factor.attack(n)
d=libnum.invmod(e,(p-1)*(q-1))
m = pow(c,d,n)
print(libnum.n2s(pow(c,d,n)))

# flag{Do_9ou_1ike_5andwich}

也可以从flag看出这不是预期解

二元copper解同上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []


N = 1085674311530255489464290129824772067886812106070317576328547361171348401864749700142226317981052597718932148985813969001766383466131904811646438034866606166860409715940892963991884944642366896061549360382036310506993659981270186354624380079666262454880589702937061510841107889532190435909694042809685218422473
c= 56930360094664103380901535309475311481122482721421214918816986675606014573458

R.<x,y> = PolynomialRing(Zmod(n^2))
PQ = x*2^256*10^39 + y
QP = y*2^256*10^39 + x
f = N - PQ*QP
roots = small_roots(f,(2^130,2^130))
if roots !=[]:
    # print(roots)
    p,q = roots[0]
    print(p,q)

有限域开根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *

c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
e = 3

p = 1213149261930568621267125437333569321667 
q = 855604426214387476576649090490109822073
PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))

PP = next_prime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = next_prime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ
e = 3      

for mp in GF(PP)(c).nth_root(e, all=True):
    for mq in GF(QQ)(c).nth_root(e, all=True):
        m = long_to_bytes(crt([ZZ(mp), ZZ(mq)], [PP, QQ]))
        if b'DASCTF' in m:
            print(m)
            break

# DASCTF{Ar3_Y0u_Su93_Abt139??}

上面没有用到 M = pow(m,1,l)

由于 m 被填充了，不能被直接开3次方得到，但我们可以 得到 m = M + k*l

k（93*8-505=239）远小于 N （758 bit），用 coppersmith 求 k 就很容易得到了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#sage
from Crypto.Util.number import *

M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
p = 1213149261930568621267125437333569321667 
q = 855604426214387476576649090490109822073

PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))
PP = next_prime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = next_prime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ

PR.<x> = PolynomialRing(Zmod(N))
f = c - (M+x*l)^3
# f = c - (x)^3
f = f.monic()
roots = f.small_roots(X=2^239,epsilon = 0.02)
k = roots[0]

m = M+k*l
print(long_to_bytes(int(m)))

# DASCTF{Ar3_Y0u_Su93_Abt139??}

found

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from Crypto.Util.number import *
from random import *
from secret import flag
from sympy import *

bits = 1024
l = 138833858362699289505402947409766595473722379891580589518174731439613184249727659678966809301611194545239974736175752769503863392697421092435438747741790652435801956708356186578269272819715592752821497122516109657809748674185639254430403157877064556216401002688452227124543508128414591884297632663910714681207

assert isPrime(l)

def generate_prime(bits):
    return randprime(2**(bits-1), 2**bits)

def fun(data,y,n):
    return sum([data[i] * pow(y,i,n) for i in range(len(data))]) % n

def gen(x, y, z, w, n):
    data = [randint(n // 4, n) for _ in range(10)]
    leak1 = pow(x + pow(y, z, n), w, n)
    leak2 = fun(data, y, n)
    return data, leak1, leak2

def encrypt(l,m,n):
    mm = bin(m)[2:].zfill((m.bit_length() // 8 + 1) * 8)
    length = len(mm)
    c = []
    s = []
    for i in range(length):
        a = randint(1, n)
        s.append(pow(a, length, n))
    for j in range(length):
        c.append(pow(l,int(mm[j]),n) * s[j] % n)
    return c

p, q = [generate_prime(bits) for _ in range(2)]
r = generate_prime(bits // 4)
n = p ** 2 * q * r
e1 = generate_prime(128)
e2 = generate_prime(128)
phi1 = p * (p - 1) * (q - 1) * (r - 1)
phi2 = (p - 1) * (p - 2) * (q - 2) * (r - 2)
d1 = inverse(e1, phi1)
d2 = inverse(e2, phi2)

t = getRandomRange(n // 4, n)
data, leak1, leak2 = gen(r, t, e1, d1, n)
m = bytes_to_long(flag)
c = encrypt(l, m, n)

with open('output.txt','w') as f:
    f.write(f'n = {n}\n')
    f.write(f'e1 = {e1}\n')
    f.write(f'ed = {e2 * d2}\n')
    f.write(f'data = {data}\n')
    f.write(f'leak1 = {leak1}\n')
    f.write(f'leak2 = {leak2}\n')
    f.write(f'c = {c}')

当 mm = 0 时，$ c = a_i^{length} \bmod n$

当 mm = 1 时，$c = l* a_i^{length} \bmod n $

注意到 length = len(mm) 是个偶数，根据二次剩余定理

$x^2 = a \pmod p，其中\gcd(a,p)=1，则称 a 为模p的二次剩余$

所以 length = 2*k ，$ c = (a_i^k)^{2} \bmod n$ ，符合二次剩余定理（经测试，所有c和n互素）

1
2
3
4
5
6
7
8
import libnum

n = 214189098485907407681203562477141616514627803973812423866137712061520397412283304756125615530911730190509122275581663270324067756428063773995710185422014937638013530995658678484408224195008950739065869752467503449898424403807629035201754909341605483646512086652631108980705938767234014655512244203488129210213088484751842078315616338034946509581920246058635374657554442252420460618886159118637553788160140879059706396460523335509806462257352635091258764319929220939182156189941663585022210802535804264016891744621140144859992731921592420695928759275864955373537480452694672023754214092487216273962896544919015905264313446548396379618341043583032673900608611135254563997519445284222602183035105369017270389887769617942348731416370092842162632579589494341854993600540689280924183073089475208340685636482246115054414077320832052204722015428500812923185709772796221129375539131726373252482799298746655947376656143301849009181701495003174228813534439192414768762803822975277797520157025175837722175072241107
l = 138833858362699289505402947409766595473722379891580589518174731439613184249727659678966809301611194545239974736175752769503863392697421092435438747741790652435801956708356186578269272819715592752821497122516109657809748674185639254430403157877064556216401002688452227124543508128414591884297632663910714681207

print(libnum.jacobi(l,n))

# -1

同样，测试发现 l 不符合二次剩余定理

于是，这题就需要用到 n 和 c，利用二次剩余定理解题

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import libnum
from Crypto.Util.number import *

n = 214189098485907407681203562477141616514627803973812423866137712061520397412283304756125615530911730190509122275581663270324067756428063773995710185422014937638013530995658678484408224195008950739065869752467503449898424403807629035201754909341605483646512086652631108980705938767234014655512244203488129210213088484751842078315616338034946509581920246058635374657554442252420460618886159118637553788160140879059706396460523335509806462257352635091258764319929220939182156189941663585022210802535804264016891744621140144859992731921592420695928759275864955373537480452694672023754214092487216273962896544919015905264313446548396379618341043583032673900608611135254563997519445284222602183035105369017270389887769617942348731416370092842162632579589494341854993600540689280924183073089475208340685636482246115054414077320832052204722015428500812923185709772796221129375539131726373252482799298746655947376656143301849009181701495003174228813534439192414768762803822975277797520157025175837722175072241107

with open('output.txt','r') as f:
    c = (f.read().strip().split('c = ')[-1])

c = eval(c)

m = ''
for i in c:
    if (libnum.jacobi(i,n)) == 1:
        m += '0'			# 根据题意 + 0
    else:
        m += '1'
print(long_to_bytes(int(m,2)))

# DASCTF{c764ba09-b2aa-12ed-ab17-9408ad39ce84}

再看

学习一下其他解法：

gcd

有：

所以 $p = \gcd(2^{ed}-2 \bmod n,n)$

与上面同理，只是把 n 换成 p 了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import libnum
from Crypto.Util.number import *

with open('output.txt','r') as f:
    c = (f.read().strip().split('c = ')[-1])
c = eval(c)

ed = 8238783462304466047370608758999664260116370123313022088538091162770601739116628806460542503654403361322931229200817491683096695046254053538710523477982774850621979868926682997393573131262930645387042545807254462907502249936746101134745335780459335767976492133149192198880107516742633966664923533160167069625322094242414191994000927842976472080411237834215691897822371792754587587715760051582955795834883174474583440371035173351136370107484245425758954400434828144460697864191261513214008084848001467959369934964428291290009392620134215667173457413630882523557102057539902909381706460767916715499306316003286608457624713509816056636249181986636842368337873445101552453774405927824096616431732124001038586048766823358751593885500314021939046991953062562270782883182855487098328026196086288533138907969729187779739950764344200364360079479047132746676799216491472345637845220255139152063453462176656553357596450484408472263570570448409671724853674399060252094955913831086556844240273178815236110565265190938731402297513542863173575371193878977
n = 214189098485907407681203562477141616514627803973812423866137712061520397412283304756125615530911730190509122275581663270324067756428063773995710185422014937638013530995658678484408224195008950739065869752467503449898424403807629035201754909341605483646512086652631108980705938767234014655512244203488129210213088484751842078315616338034946509581920246058635374657554442252420460618886159118637553788160140879059706396460523335509806462257352635091258764319929220939182156189941663585022210802535804264016891744621140144859992731921592420695928759275864955373537480452694672023754214092487216273962896544919015905264313446548396379618341043583032673900608611135254563997519445284222602183035105369017270389887769617942348731416370092842162632579589494341854993600540689280924183073089475208340685636482246115054414077320832052204722015428500812923185709772796221129375539131726373252482799298746655947376656143301849009181701495003174228813534439192414768762803822975277797520157025175837722175072241107

p = GCD(pow(2,ed,n)-2,n)
m = ''
for i in c:
    if (libnum.jacobi(i,p)) == 1:
        m += '0'
    else:
        m += '1'
print(long_to_bytes(int(m,2)))

# DASCTF{c764ba09-b2aa-12ed-ab17-9408ad39ce84}

已知 ed 分解 n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import random
import libnum

def factor_with_ed(ed,n):
    p=1
    q=1
    while p==1 and q==1:
        k = ed -1
        g = random.randint(1,n)
        while k%2==0:
            k //= 2
            x = pow(g,k,n)
            if x>1 and libnum.gcd(x-1,n)>1:
                p = libnum.gcd(x-1,n)
                q = n//p
    return p,q

n = 214189098485907407681203562477141616514627803973812423866137712061520397412283304756125615530911730190509122275581663270324067756428063773995710185422014937638013530995658678484408224195008950739065869752467503449898424403807629035201754909341605483646512086652631108980705938767234014655512244203488129210213088484751842078315616338034946509581920246058635374657554442252420460618886159118637553788160140879059706396460523335509806462257352635091258764319929220939182156189941663585022210802535804264016891744621140144859992731921592420695928759275864955373537480452694672023754214092487216273962896544919015905264313446548396379618341043583032673900608611135254563997519445284222602183035105369017270389887769617942348731416370092842162632579589494341854993600540689280924183073089475208340685636482246115054414077320832052204722015428500812923185709772796221129375539131726373252482799298746655947376656143301849009181701495003174228813534439192414768762803822975277797520157025175837722175072241107
ed = 8238783462304466047370608758999664260116370123313022088538091162770601739116628806460542503654403361322931229200817491683096695046254053538710523477982774850621979868926682997393573131262930645387042545807254462907502249936746101134745335780459335767976492133149192198880107516742633966664923533160167069625322094242414191994000927842976472080411237834215691897822371792754587587715760051582955795834883174474583440371035173351136370107484245425758954400434828144460697864191261513214008084848001467959369934964428291290009392620134215667173457413630882523557102057539902909381706460767916715499306316003286608457624713509816056636249181986636842368337873445101552453774405927824096616431732124001038586048766823358751593885500314021939046991953062562270782883182855487098328026196086288533138907969729187779739950764344200364360079479047132746676799216491472345637845220255139152063453462176656553357596450484408472263570570448409671724853674399060252094955913831086556844240273178815236110565265190938731402297513542863173575371193878977

# ed = e * d
p,q = factor_with_ed(ed,n)
print(p)

# 168207689659417173628607066039457820275276732311636007089001107530860513351122555769649031031435042743185528528881857626080873859026128498997148721030271703030768717788591275936600239642357340350598106488044312274746860587888105379606096757814370419770414183228756583472285941821276338279728115488001890742673

求出了 p，与上同理

求 r (Sylvester结式法)

Sylvester结式法求解多项式方程

结式：

指由两个多项式的系数所构成的一种行列式，或称Sylvester行列式，结式可判断两个多项式是否有公根、是否互素，以及判断多项式是否有重根。

我并不准备原理转述：

Sylvester结式法求解多项式方程_用经典的 sylvester 消元法适用于三个未知数吗-CSDN博客

两个式子：

这两个式子出现过几次了，所以还是多看一下

两个未知数，我们可以利用 结式 消去 t，来求 r，由于 $t^{e_1}$ 较大，无法直接表示，故我们需要优化一下，求它的时候 模一个多项式 g

1
2
3
4
5
6
7
ff = t
te = 1

for i in bin(e1)[2:][::-1]:		# 原来求一个数的幂是这么求的，前提 e1>0
    if i == '1':
        te = (te * ff) % g
    ff = (ff * ff) % g

结式：

1
2
h = f.sylvester_matrix(g, t).det().univariate_polynomial().monic()
he = (companion_matrix(h)).charpoly()    # 非必选，两个的结果是一样的，如果需要对多项式求幂的话启用第二行

代码的意思，不过多赘述，想必你看完就明白了：

https://tover.xyz/p/resultant-companion-hardrsa/#Resultant

r 相对 n 较小，copper 即可解

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from Crypto.Util.number import * 
from random import *

n = 
e1 = 
data = 
leak1 = 
leak2 = 

R.<t,r>=PolynomialRing(Zmod(n))   

g = sum([int(data[i]) * t ** i for i in range(len(data))]) - leak2

ff = t
te = 1

for i in bin(e1)[2:][::-1]:
    if i == '1':
        te = (te * ff) % g
    ff = (ff * ff) % g

f = r + te - pow(leak1,e1,n)

h = f.sylvester_matrix(g, t).det().univariate_polynomial().monic()
# he = (companion_matrix(h)).charpoly()   

res = h.small_roots(X = 2 ** 256,epsilon = 0.03)
if res:
    print(res[0])

# 77477547161688496725906506626131775883966333151442864639104100690032824193233

出题人题目灵感应该是来自 Van1sh 佬：

好题分享系列 - 2023 江苏省数据安全竞赛 - hardrsa (qq.com)

DAS_DSA

DDAASSSAA.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

from Crypto.Util.number import *
import hashlib

b2l=lambda x:bytes_to_long(x)
l2b=lambda x:long_to_bytes(x)
def xor(A,B):
  return bytes([a ^ b for a, b in zip(A, B)])
class SimpleDSASigner:
    def __init__(self, p, q, g, x,KEY):
        self.p = p
        self.q = q
        self.g = g
        self.x = x
        self.y = pow(self.g, self.x, self.p)
        self.KEY=KEY
    def sign(self, message):
        h = int(hashlib.sha256(message).hexdigest(), 16)
        k = b2l(xor(message,self.KEY))
        r = pow(self.g, k, self.p) % self.q
        s = (inverse(k, self.q) * (h + self.x * r)) % self.q
        if r != 0 and s != 0:
            return (r, s)
    def verify(self, message, r, s):
        h = int(hashlib.sha256(message).hexdigest(), 16)
        w = inverse(s, self.q)
        u1 = (h * w) % self.q
        u2 = (r * w) % self.q
        v = ((pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p) % self.q
        return v == r
    def give_gift(self):
        return (self.p,self.q,self.g,self.y)

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import random
from DDAASSSAA import *
from Crypto.Util.Padding import pad
from flag import FLAG
ALPHABET = "DAS"
KEY_LENGTH = 32

def generate_random_string(length, chars):
    return ''.join(random.choice(chars) for _ in range(length))

def get_message(num_messages):
    return [generate_random_string(random.randint(20, 32), ALPHABET) for _ in range(num_messages)]

def get_key():
    return generate_random_string(KEY_LENGTH, ALPHABET).encode()

def get_strong_prime(kbits):
    while True:
        q = getPrime(kbits)
        p = q * 2 + 1
        if isPrime(p):
            return p, q

def write_to_file(filename, data, rwx="w"):
    with open(filename, rwx) as file:
        for item in data:
            file.write(f"{item}\n")

if __name__ == "__main__":
    num_messages = 2024 // 65
    messages = get_message(num_messages)
    p, q = get_strong_prime(256)
    x = random.randrange(q)
    key = get_key()

    signer = SimpleDSASigner(p, q, 2, x, key)
    write_to_file("GIFT.txt", messages)
    signatures = [signer.sign(pad(msg.encode(), 32)) for msg in messages]
    write_to_file("enc.txt", map(str, signatures))
    write_to_file("enc.txt", [str(signer.give_gift())],"a")

    assert FLAG==b"DASCTF{"+key+b"}"

GIFT.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
SDSSDASSAAASSDADSASADASSSSADDS
SADADDAASSAASDSAAAAADS
SSASDDDSSSSDDSDAAAAAASAASDSA
SASSDSDSSSDSSDSDASADDA
SDDAAASASADDAADDSSSSDASAASADSA
AASADASADDSDDASADSAS
DASDDDDAASADDASADAAAAAADS
DSAAAASASDDDDDDSSASDADSASDDA
ADSSSSAADDSDDDADAADD
ASDDSADAASSASSDSDDSSD
SASSDDAASDDSADSDSSDAASSAD
DADSDAASAADDAAASASSSA
DADDADSSDADAADSSADDADDDSSDAS
AAASDSSDSAASDADDSADSDA
ASDASSDSDDADADSDSDDDDADSSAADAS
SDSASDADDASDASSDSAAASSASSDADA
AADDSSDSDADSASDDSASSDDD
SAADASAADAASDDDSASSDAASAAAS
SSDDADSAADSDSSADSADSAASASDSAS
DSDDAAASDDDSAASSDDDAASADSS
SASSAAAAAAADSDASSDASSDAS
DDDASAASDAADSSSASAAAADSDD
SASADSSSAADDASADDDADD
ASDDDDSDDSSSAASASDSSDDASA
DSAASDSDAADAAAAASADSDDDDAAA
ADSDADDDASASDSDADSADADDSASSSD
ADADDASSDSDASADDSADSD
SASAASDSDDASADASSSDSAAA
SASDDADSSDASDDSSDSDA
ADAASDSSDSDASSASADDSDDASAS
AADADDSAADDDSASADASSDAADADAA

enc.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
(59254487398967388114905667045028363843329923626238494813205814542210325221866, 38134152657262330507433713437784426184950965354807113354631630191330303144120)
(7272091585909282735283006759301331954064261183899338079418296410637263888770, 25499964678151126566605578540840513489434638253159604087981425065951344757164)
(6899645492048427857621143178962093646174799398991863666101058693217698732368, 9791582686238213337967141368906212036310014918808878260483336268832064128819)
(25004120896291255053237639070744331951278481119827357255754648579794346195560, 141512006531073436448016797005260994098008785866923890662245540709534244927)
(2970680424634969125510981613739745658897845410407912521400879068659540408508, 21793011307831199247000930716490000926029175766326909085969585420590222327264)
(54566000630497640561512172245143554745650114820675965968691149808463168361994, 14349862994826483344159692458388566295460798903541941504424537018216650283613)
(75159685495692974866291952764676724718763580667689472941977359299782008334398, 70458140884809949567915541063312538538372757595177423386408938073672211639375)
(20041025052466338500977838626769109456575569706600589389016534358968746705758, 65530083011107720400920780939345704754954869671333734672594688826098321351660)
(70127192435034402135747706941502224672808592757766109942714487474501491910214, 57063474646503909216126596725677068514339517777473453937098665282959018241139)
(9691674719110233709152049443866537766465800386755314400120771762265195237696, 62093763551744197212031574855244002702924782008725363963219173846480120194830)
(71705536377844454384479609516094364197930343317149881589774662842233960882414, 77374603032347186343803094100249733360600621594214414598796066240713702791608)
(52879693221782582945807231749976747516107564896599455986464226581743117039645, 1344584960351311598238142429846629993914377848692708811135221930719773821079)
(77382790022991362370508965243223326049308313776687214599186184000848696471646, 43641233828500431963081402892838426285406919342406723474664571883294369141394)
(56346141869522955969887972614456267251604757060687228073793419107933969328162, 76285674574149814839616688665569434237657824816977670694242559140508233840268)
(13673786393914569132256858604647869957632869873889606981549833789272316263013, 55327829510120473782794486945583818434703312785066895788282945944551470490709)
(64767740468987944636292946852714160626094908713011502873333251460983428727987, 13259490361346409766866273875042192439139048727072955549892484859673179719539)
(3957421961183318932163297455146838208380750250268324980567615749312524020603, 26882140137481455957383933013829466811327529673163422516945649296787438630196)
(26427922029900012253901950242265848521558605010629901777129266992870754082725, 69951840114040217998552588969628162605092507207522992695398095063314527794456)
(41377529326816743042387061355650636824586430044255853849728865473372840135697, 11219359019456290145545276763003725218855047474525360923001515509608652449000)
(25716607607446503241765016815241812755718791371526314953930748513731536667770, 28453782213087434330094261632474010077787574243224303728751260500450723227337)
(19800391798756020076641438144957219387739406397111495660920822320302304854123, 45451686690348328576376896082606976500453603983712180502700202971927238065259)
(38726290839677684687529233274549282905118675478275260942535144771737271586397, 40829316203033016996956478373044348905634931325393076578307296318880401948880)
(39209612764454560795450300186392582769693156243512973558204034254768849812055, 1354495451811853700039180690705948597695565424847801455594169929311025313998)
(65513712517147774905818288938959930101260466094015953149923879872714745367445, 15372704507991354781967074099137226451034611060413049367266363154832614415805)
(15729001560566023616632342669016214191974988848807788455841465085832368458445, 16327134664007312833089147621817036851276111964898734022794700122827444854947)
(42181696175119369852613642818168055609726913997313538977450877772345284116500, 9844926061501886811803369928846120575402269452312877926396348651872911440254)
(66136301537002842836817588252827389434354772150463143258637074246966542574050, 40179237579762663098604891208246052072476264271372972425562554108399403298795)
(28759447425094984124057238672075080352158483766211322160596339820824930247130, 31809179023991813094371890170356817265600467849999331763205655801654108159032)
(46713611880672324334213026166944979498146683097425440783760089321619754080806, 23270114877894114090584274918755188867365261145736710892185678426446455871613)
(57079205189933243387798430767693634017842334556643904914267966016857671112460, 18247249527866143497935092319901700668290600772967638096649240924154901762810)
(10688647176294432598580110142909961685073598720504815121442568862023227643325, 54331697420125697460151875535555752680845260504979536685075170636565355173106)
(156169498993837300941969389078565637464689185713213578550979549862042014984607, 78084749496918650470984694539282818732344592856606789275489774931021007492303, 2, 59080272611010540206200716660225398487916425104605746321153704646003914371135)

Writeup：

移步：

https://wbuildings.github.io/Crypto/DSA/#more

EZshamir

task.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import os
from random import getrandbits
from hashlib import sha256, md5
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag

class Shamir:
    def __init__(self, pbits, noise_bit, n, m):
        self.pbits = pbits
        self.noise_bit = noise_bit
        self.n = n
        self.m = m
        self.p = getPrime(pbits)
        P.<x> = PolynomialRing(Zmod(self.p))
        self.poly = P([bytes_to_long(sha256(os.urandom(32)).digest()) for i in range(self.n)])

    def sample(self):
        t = getrandbits(self.pbits)
        y = int(self.poly(t))
        noise = getrandbits(noise_bit)
        return (t, y | noise)

    def get_msg(self):
        res = []
        for i in range(self.m):
            res.append(self.sample())
        return res

pbits = 400
noise_bit = 32
n = 100
m = 75

shamir = Shamir(pbits, noise_bit, n, m)
coefficient = shamir.poly()
key = "".join([str(i) for i in list(coefficient)[1:]])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
ct = aes.encrypt(pad(flag, 16))

with open("data.txt", "w") as f:
    f.write(str(shamir.p)+'\n')
    f.write(str(shamir.get_msg())+'\n')
    f.write(str(bytes_to_long(ct))+'\n')

Writeup：

移步：

Shamir 门限方案 | W’Blog (wbuildings.github.io)

-------------　　　　本文结束　　感谢阅读　　　　-------------