2024dasctf部分crypto复现

发表于 分类于 阅读次数： Disqus： 本文字数： 5.3k 阅读时长 ≈ 10 分钟
2024dasctf部分crypto复现

[TOC]

2024Dasctf 部分crypto

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
32
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))

利用背包密码超递增序列的特点，从尾部依次往前判断是否在背包中，把key最后一个元素删掉，因为key最开始不是空数组。

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

c=287687761937146187597379915545639385740275457170939564210821293233370716878150576
key=[....]
m = []
for i in range(len(key)):
    if(c > key[len(key)-1-i]or c == key[len(key)-1-i]):
        m.append("1")
        c -= key[len(key)-1-i]
    else:
        m.append("0")

m = int("".join(m)[::-1],2)
print(long_to_bytes(m))
#b'DASCTF{you_kn0w_b@ckpack_Crypt0?}'

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
'''

＜

但相差较小可以有

然后通过模运算、整除和解方程得到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
26
27
28
from Crypto.Util.number import *
from sympy import *
import os
n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691

M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
nn=n//(2**240*10**79+1)
for i in range(nn-800,nn+800):
    if(n-i*(2**240*10**79+1))%(2**120*10**39)==0:
        leak=(n-i*(2**240*10**79+1))//(2**120*10**39)
        p,q=symbols('p,q')
        res=solve([p**2+10*q**2-leak,p*q-i],[p,q])
        print(res)
        for pp,qq in res:
            if pp>0 and qq>0:
                PQ=int(str(int(pp)<<120)+str(int(qq)))
                QP=int(str(int(qq)<<120)+str(int(pp)))
                PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
                QQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))
                N = PP * QQ
                print(N)
                print(PQ)
                print(QP)
                break
        break
#763933528218428362740063144747893290714655295576768532896029874141179804730143020017430379534079773751531037961074867132893544981605022026151484151321515584652838724809597675412676810669583078026377048734720511960708515190930979

然后copper

1
2
3
4
5
6
7
8
9
10
11
12
from Crypto.Util.number import*
N=763933528218428362740063144747893290714655295576768532896029874141179804730143020017430379534079773751531037961074867132893544981605022026151484151321515584652838724809597675412676810669583078026377048734720511960708515190930979
M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
PR.<k>= PolynomialRing(Zmod(N))
f=(M+k*l)^3-c
f=f.monic()
t=f.small_roots(x=2^239,epsilon =0.02)[0]
m=M+t*l
print(long_to_bytes(int(m)))
#DASCTF{Ar3_Y0u_Su93_Abt139??}