前言

这里记录了一些平常做题或者打比赛时遇到的有趣的不会做的Crypto题目，*表示赛时没有做出来，赛后复现的题目；持续更新（大概）。

Bytectf 2024

一道可能有思路但有思路不太可能的lfsr和一道0解的抽象dlp题目构成了我这个抽象的周末（悲）。

*magic_lfsr

题目

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
from Crypto.Cipher import AES
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from hashlib import sha512
from secret import flag

mask1 = 211151158277430590850506190902325379931
mask2 = 314024231732616562506949148198103849397
mask3 = 175840838278158851471916948124781906887
mask4 = 270726596087586267913580004170375666103

def lfsr(R, mask):
    R_bin = [int(b) for b in bin(R)[2:].zfill(128)]
    mask_bin = [int(b) for b in bin(mask)[2:].zfill(128)]
    s = sum([R_bin[i] * mask_bin[i] for i in range(128)]) & 1
    R_bin = [s] + R_bin[:-1]
    return int("".join(map(str, R_bin)), 2), s

def ff(x0, x1, x2, x3):
    return int(sha512(long_to_bytes(x0 * x2 + x0 + x1 ** 4 + x3 ** 5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4)).hexdigest(), 16) & 1

def round(R, R1_mask, R2_mask, R3_mask, R4_mask):
    out = 0
    R1_NEW, _ = lfsr(R, R1_mask)
    R2_NEW, _ = lfsr(R, R2_mask)
    R3_NEW, _ = lfsr(R, R3_mask)
    R4_NEW, _ = lfsr(R, R4_mask)
    for _ in range(270):
        R1_NEW, x1 = lfsr(R1_NEW, R1_mask)
        R2_NEW, x2 = lfsr(R2_NEW, R2_mask)
        R3_NEW, x3 = lfsr(R3_NEW, R3_mask)
        R4_NEW, x4 = lfsr(R4_NEW, R4_mask)
        out = (out << 1) + ff(x1, x2, x3, x4)
    return out
key = getRandomNBitInteger(128)
out = round(key, mask1, mask2, mask3, mask4)
cipher = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
print(f"out = {out}")
print(f"enc = {cipher.encrypt(pad(flag, 16))}")
# out = 1024311481407054984168503188572082106228007820628496173132204098971130766468510095
# enc = b'\r\x9du\xa15q\xd2\x81\x0b\xceq2\x8d)*\xe9\xf0;a\xad\xbe?\xa2\xb2\x1f\x88O\x8c\xa2[\xcb\x9a\xa9\x8d\xac\x0b\x85\xb4j@]\x0e}EF{\xb1\x91'

赛时想到了打ff的真值表去简化这个不可逆的函数，但是并没有想出如何去构造新函数；赛后参考W&M的wp复现才发现对LFSR的理解还是太浅了。

EXP

首先打ff的真值表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from hashlib import sha512

def ff(x0, x1, x2, x3):
    return (int(sha512(long_to_bytes(x0 * x2 + x0 + x1**4 + x3**5 + x0 * x1 * x2 * x3 + (x1 * x3) ** 4)).hexdigest(), 16) & 1)

n0 = 0
for x0 in range(2):
    for x1 in range(2):
        for x2 in range(2):
            for x3 in range(2):
                r = ff(x0,x1,x2,x3)
                print((x0,x1,x2,x3),r,(x0+x1+x3)%2)
                n0 += int(r==(x0+x1+x3)%2)	
print(n0)

这里构造了一个新函数：(x0+x1+x3)%2，打表发现只有1种情况不符合，考虑爆破最后一种情况构造m，使得

m⋅key=outputm · key = output

根据out中1位填充m的前n(n=127)列，并爆破最后两列所有可能的0位，解AES获得flag 完整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
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
68
69
70
71
72
73
74
75
from Crypto.Cipher import AES
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from hashlib import sha512  
from copy import deepcopy

out = 1024311481407054984168503188572082106228007820628496173132204098971130766468510095
enc = b'\r\x9du\xa15q\xd2\x81\x0b\xceq2\x8d)*\xe9\xf0;a\xad\xbe?\xa2\xb2\x1f\x88O\x8c\xa2[\xcb\x9a\xa9\x8d\xac\x0b\x85\xb4j@]\x0e}EF{\xb1\x91'


mask1 = 211151158277430590850506190902325379931
mask2 = 314024231732616562506949148198103849397
mask3 = 175840838278158851471916948124781906887
mask4 = 270726596087586267913580004170375666103

m = matrix(GF(2),128,129)
M1,M2,M3 = matrix(GF(2),128,128),matrix(GF(2),128,128),matrix(GF(2),128,128)

for i in range(128):
    M1[i,0] = int(bin(mask1)[2:][i])
    M2[i,0] = int(bin(mask2)[2:][i])
    M3[i,0] = int(bin(mask4)[2:][i])
    if i != 127:
        M1[i,i+1] = 1
        M2[i,i+1] = 1
        M3[i,i+1] = 1

out = bin(out)[2:].zfill(270)
print(out)
si = []
for i in range(270):
    if out[i] == '1':
        si.append(i)
print(si,len(si))

n = 0
MM1,MM2,MM3 = identity_matrix(GF(2),128),identity_matrix(GF(2),128),identity_matrix(GF(2),128)
MM1 *= M1
MM2 *= M2
MM3 *= M3
for i in range(270):
    MM1 *= M1
    MM2 *= M2
    MM3 *= M3
    if i in si:
        m[:,n] = (MM1+MM2+MM3)[:,0]
        n += 1

assert n == 127
output = matrix([1]*127+[0]*2)
MM1,MM2,MM3 = identity_matrix(GF(2),128),identity_matrix(GF(2),128),identity_matrix(GF(2),128)
MM1 *= M1
MM2 *= M2
MM3 *= M3
for i in range(270):
    MM1 *= M1
    MM2 *= M2
    MM3 *= M3
    if i not in si:
        m[:,-2] = (MM1+MM2+MM3)[:,0]
        MMM1,MMM2,MMM3 = deepcopy(MM1),deepcopy(MM2),deepcopy(MM3)
        for j in range(i+1,270):
            MMM1 *= M1
            MMM2 *= M2
            MMM3 *= M3
            if j not in si:
                m[:,-1] = (MMM1+MMM2+MMM3)[:,0]
                try:
                    key = (m.solve_left(output))[0]
                    key = ''.join(str(_) for _ in key)
                    key = int(key,2)
                    cipher = AES.new(long_to_bytes(key), mode=AES.MODE_ECB)
                    print(cipher.decrypt(enc))
                except:
                    continue

*decipher Diffie-Hellman

题目

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
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Util.Padding import pad
from libnum import s2n

flag = r"ByteCTF{******}"
g = 5
p = getPrime(512)
a = random.randrange(2, p - 1)
A = pow(g, a, p)

al = getPrime(512)
m = getPrime(512)
s = getPrime(512)

outputs = []
for i in range(10):
    s = (al * s + p) % m
    outputs.append(s)

key_int = int(input("Input my public key?\n"))

while not 1 < key_int < (p - 1):
    key_int = int(input("Input correct format public key again between 2 to p-1\n"))
dh_key = pow(key_int, a, p)
key = hashlib.md5(long_to_bytes(dh_key)).digest()
cipher = AES.new(key, AES.MODE_ECB)
enc = cipher.encrypt(pad(flag.encode(), 16))
print("al = ", al)
print("m = ", m)
print("ouputs[4] = ", outputs[4])
print("ouputs[5] = ", outputs[5])
print(f'encrypted flag: {s2n(enc)}')
"""
al =  6987418709836280122539809582453286069061059342934250273196952239100173470340380619195424571025033102643293098735246498899499230393741046775729762352856927
m =  12710688490958956530748900564817776351569320915377221868023985388799130768128470437062609956810086256451091702161476567347660442541036645863742363823898071
ouputs[4] =  2728757049131678605235016854422985829565908585923048338298110282069173390888632945247368807787912947016658675182897909709569230885213734719022623969520979
ouputs[5] =  3753895881656195471988191329401971327506920732845692422476480236229772053653896503280676494663976886598118940522017209044648665134625067341824484655112146
encrypted flag: 4421203891267550791983036920779652137711362976404304304369030116210000459547739643046609216016679658345753605804218976790719901924890550963123070032471900
"""

hint: 有限空间爆破

根据lcg生成的两个相邻值可以解出p，然后开始挂机

SCTF 2024

学长们尽力了，密码手在干什么？（）

Signin

题目

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
from sage.all import *
from Crypto.Util.number import *
from hashlib import md5

class RSA():
    def __init__(self, nbits):
        self.nbits = nbits
        self.p, self.q = self.getPrimes()
        self.n = self.p*self.q
        self.Gift = self.Gift()
        self.priv, self.pub = self.keyGen()
        
    
    def getPrimes(self):
        nbits = self.nbits
        p = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        while p == q:
            q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        return p,q
    
    def Gift(self):
        p,q = self.p, self.q
        return (p^2 + p + 1)*(q^2 + q + 1)
    
    def keyGen(self):
        nbits = self.nbits
        while True:
            d = randint(2^(nbits//4),2^(nbits//2))
            if gcd(d,self.Gift) != 1:
                d = randint(2^(nbits//4),2^(nbits//2))
            e = pow(d,-1,self.phi)
            return (self.p,self.q,self.n,e,d),(self.n,e)
    

RRR = RSA(512)

bp = long_to_bytes(int(RRR.p))
FLAG = 'SCTF{'+md5(bp).hexdigest()+'}'


print(f'N = {RRR.n}')
print(f'e = {RRR.pub[1]}')

'''
N = 32261421478213846055712670966502489204755328170115455046538351164751104619671102517649635534043658087736634695616391757439732095084483689790126957681118278054587893972547230081514687941476504846573346232349396528794022902849402462140720882761797608629678538971832857107919821058604542569600500431547986211951
e = 334450817132213889699916301332076676907807495738301743367532551341259554597455532787632746522806063413194057583998858669641413549469205803510032623432057274574904024415310727712701532706683404590321555542304471243731711502894688623443411522742837178384157350652336133957839779184278283984964616921311020965540513988059163842300284809747927188585982778365798558959611785248767075169464495691092816641600277394649073668575637386621433598176627864284154484501969887686377152288296838258930293614942020655916701799531971307171423974651394156780269830631029915305188230547099840604668445612429756706738202411074392821840
'''

exp

注意到d的位数在128bit到256bit之间，且满足：

ed=1+k(p2+p+1)(q2+q+1)ed = 1 + k(p^2 + p + 1)(q^2 + q + 1)

k与d数量级接近 对上式进行变换，可以构造copper如下：

ed=1+k[n2−n+1+(n+1)(p+q)+(p+q)2]ed = 1 + k[n^2 - n + 1 + (n + 1)(p + q) + (p + q)^2]

mod e下有如下的多项式：

f=1+x[n2−n+1+(n+1)y+y2](mod  e)f = 1 + x[n^2 - n + 1 + (n + 1)y + y^2]\quad(mod\;e)

copper解出k与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
68
69
70
from Crypto.Util.number import *
from hashlib import md5
from gmpy2 import *
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 = 32261421478213846055712670966502489204755328170115455046538351164751104619671102517649635534043658087736634695616391757439732095084483689790126957681118278054587893972547230081514687941476504846573346232349396528794022902849402462140720882761797608629678538971832857107919821058604542569600500431547986211951
e = 334450817132213889699916301332076676907807495738301743367532551341259554597455532787632746522806063413194057583998858669641413549469205803510032623432057274574904024415310727712701532706683404590321555542304471243731711502894688623443411522742837178384157350652336133957839779184278283984964616921311020965540513988059163842300284809747927188585982778365798558959611785248767075169464495691092816641600277394649073668575637386621433598176627864284154484501969887686377152288296838258930293614942020655916701799531971307171423974651394156780269830631029915305188230547099840604668445612429756706738202411074392821840

PR.<x,y>=PolynomialRing(Zmod(e))
f = 1 + x*(n**2-n+1 + (n+1)*y + y**2)
res = small_roots(f, (2^128,2^512), m=2, d=3)

pplusq = int(res[0][1])
pminusq = iroot(pplusq**2-4*n,2)[0]
p = (pplusq + pminusq) // 2
q = n // p
print(p)
print(q)

p = 5984758006806378809956519900535567746479053908385004504598524889746027259134602871258417614666511624425382102292754198444334667792470478919346145707972191
q = 5390597488072767109361706002186244359146023656052952666052036845964423888084380390710080004831930978524731104593204614023979740021938370218984226690661361
bp = long_to_bytes(p)
bq = long_to_bytes(q)
print('SCTF{'+md5(bp).hexdigest()+'}')
print('SCTF{'+md5(bq).hexdigest()+'}')

不完全阻塞干扰

题目

题目给出了部分私钥，手撕发现有p和q的高位

1
2
3
4
n = 0x67f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e5
e = 0x10001
ph = 0x8063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e57019400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
qh = 0xe4f0fe49f9ae1492c097a0a988fa71876625fe4fce05b0204f1fdf43ec64b4dac699d28e166efdfc7562d19e58c3493d9100365cf2840b46c0f6ee8d964807170ff2c13c4eb8012ecab37862a3900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

后根据pkl文件可以发现公钥生成方法和密文

1
2
3
4
5
6
7
8
9
# The ship crashed into the sun, causing a massive magnetic storm
# part of script
msg = bytes_to_long(FLAG)
n = p^5*q^2
phi = p^4*(p-1)*q*(q-1)
e = 65537
d = inverse(d,phi)
c = pow(m,e,n)
# c = 145554802564989933772666853449758467748433820771006616874558211691441588216921262672588167631397770260815821197485462873358280668164496459053150659240485200305314288108259163251006446515109018138298662011636423264380170119025895000021651886702521266669653335874489612060473962259596489445807308673497717101487224092493721535129391781431853820808463529747944795809850314965769365750993208968116864575686200409653590102945619744853690854644813177444995458528447525184291487005845375945194236352007426925987404637468097524735905540030962884807790630389799495153548300450435815577962308635103143187386444035094151992129110267595908492217520416633466787688326809639286703608138336958958449724993250735997663382433125872982238289419769011271925043792124263306262445811864346081207309546599603914842331643196984128658943528999381048833301951569809038023921101787071345517702911344900151843968213911899353962451480195808768038035044446206153179737023140055693141790385662942050774439391111437140968754546526191031278186881116757268998843581015398070043778631790328583529667194481319953424389090869226474999123124532354330671462280959215310810005231660418399403337476289138527331553267291013945347058144254374287422377547369897793812634181778309679601143245890494670013019155942690562552431527149178906855998534415120428884098317318129659099377634006938812654262148522236268027388683027513663867042278407716812565374141362015467076472409873946275500942547114202939578755575249750674734066843408758067001891408572444119999801055605577737379889503505649865554353749621313679734666376467890526136184241450593948838055612677564667946098308716892133196862716086041690426537245252116765796203427832657608512488619438752378624483485364908432609100523022628791451171084583484294929190998796485805496852608557456380717623462846198636093701726099310737244471075079541022111303662778829695340275795782631315412134758717966727565043332335558077486037869874106819581519353856396937832498623662166446395755447101393825864584024239951058366713573567250863658531585064635727070458886746791722270803893438211751165831616861912569513431821959562450032831904268205845224077709362068478

很显然可以直接构造二元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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import pickle
from Crypto.Util.number import *
import itertools
# with open("intelligence.pkl", "rb") as f:
#     ld = pickle.load(f)
#
# print(ld)

# with open('cert.pem', 'r') as f:
#     data = f.read()
#
# key_64 = ''.join(data.split('\n')[1:-1])
# key_num = libnum.s2n(base64.b64decode(key_64))
# key_hex = hex(key_num)[2:]
# print(key_hex)



n = 0x67f0aa4e974a63a1ffe8d5c23e5d3c431653ae41cc746f305f62a9f193f22486cb7ef1b275634818f46d0752a5139e19918271fa0d7d27bc660d2b72414d08ea52c8837f949c7baecc3029ba31727ef3bf120d9926c02d7412f187e98dc56dd07b987d2cc191ad56164a144f28b2f70a15d105588a4f27fbb2891fc527bd6890a5f795b5c48476a6bf9dfb67b7e1ebc7b1b086cd28b58c68955bfdf44ecce11ffacdf654551b159b7832040cc28ee8ebea48f8672d53e3de88fcfbb5fb276b503880dd34d5993335ddf8ccb96c1b4d79f502d72104765ad9c2b1858a17af3d5be44fa3cbf4b8eeb942aa3942a3871d2c65ac70289123fc2e9f9b25cbfcbd7841096060fa504c3a07b591493c64c88d0bb45285a85b5f7d59db98faa00c2cd3fbb63da599205f1cab0df52cf7b431a0ee4a7e35696546ce9d03ef595ecee92d2142c92e97d2744939703455b4c70dec27c321ec6b83c029622e83a9e0d55d0b258d95d4e61291865dda76dc619fce9577990429c6e77e9d40781e3b2f449701b83e8b0c6c66eb380f96473e5d422efee8b2b0e88b716b00a79c9d514ca3ad9d2dee526609ff9541732a4198d11b9dbfbb2e55c24d80ea522d0786e3355f23606a5d38a72de4eefc8b6bfc482248a2862cb69d8e0e3d316597da9d80828be85054faf15fc369caacafb815c6973c171940683d56a1a1967b09b7ffa3fbe5b2e08699759d84d71603f516447696bb27322a69f39f6ca253e00dc9555d5f97328070c467f3663cc489aad130f28c42f35bf88c571920ab92acb8f75d03e35a75103c5bd96f061c96bd02af6e1d191b0dd164bc721377003edbf5d3ef65a5e9046385356b521623bee37f164850a0a7afb0ed4e7e8bd9afe1298f7d532bc9ad941812d332aece75d1cccb1ff69fd42b31f248ae579d9e0d6a14b0546e784ba940e32bd01c395df8ff4584040462b5479fa07336d503dc332e70fc06d9463297fc042b623d56f87efaa525a9b580e314d90d1211893ed407a26508deaa0a13c9ee8c902b9e1c3a02fe9a51452c02ee7bdcc85c0eff63891e24703bd265d9c9dbf456e2af9409538bce0fecc7ebab20266aaab06c766c3ea6cda9cb9ba5e1d024b7dc3d73e76f6a333197bad87c4fb34d565a0014aac72825e41adcfeadadc87acef40ad84b7c55691abad561be0550ea0a988470c427432acb8feb2b9d2d2598fb2089bb91bbd9cb199e892d36164d8bf3ecd54576a97134047a12da84207485bb4e5
e = 0x10001
ph = 0x8063d0a21876e5ce1e2101c20015529066ed9976882d1002a29efe0f2fdfcc2743fc9a4b5b651cc97108699eca2fb1f3d93175bae343e7c92e4a41c72d05e57019400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
qh = 0xe4f0fe49f9ae1492c097a0a988fa71876625fe4fce05b0204f1fdf43ec64b4dac699d28e166efdfc7562d19e58c3493d9100365cf2840b46c0f6ee8d964807170ff2c13c4eb8012ecab37862a3900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
c = 145554802564989933772666853449758467748433820771006616874558211691441588216921262672588167631397770260815821197485462873358280668164496459053150659240485200305314288108259163251006446515109018138298662011636423264380170119025895000021651886702521266669653335874489612060473962259596489445807308673497717101487224092493721535129391781431853820808463529747944795809850314965769365750993208968116864575686200409653590102945619744853690854644813177444995458528447525184291487005845375945194236352007426925987404637468097524735905540030962884807790630389799495153548300450435815577962308635103143187386444035094151992129110267595908492217520416633466787688326809639286703608138336958958449724993250735997663382433125872982238289419769011271925043792124263306262445811864346081207309546599603914842331643196984128658943528999381048833301951569809038023921101787071345517702911344900151843968213911899353962451480195808768038035044446206153179737023140055693141790385662942050774439391111437140968754546526191031278186881116757268998843581015398070043778631790328583529667194481319953424389090869226474999123124532354330671462280959215310810005231660418399403337476289138527331553267291013945347058144254374287422377547369897793812634181778309679601143245890494670013019155942690562552431527149178906855998534415120428884098317318129659099377634006938812654262148522236268027388683027513663867042278407716812565374141362015467076472409873946275500942547114202939578755575249750674734066843408758067001891408572444119999801055605577737379889503505649865554353749621313679734666376467890526136184241450593948838055612677564667946098308716892133196862716086041690426537245252116765796203427832657608512488619438752378624483485364908432609100523022628791451171084583484294929190998796485805496852608557456380717623462846198636093701726099310737244471075079541022111303662778829695340275795782631315412134758717966727565043332335558077486037869874106819581519353856396937832498623662166446395755447101393825864584024239951058366713573567250863658531585064635727070458886746791722270803893438211751165831616861912569513431821959562450032831904268205845224077709362068478

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 []
PR.<x,y> = PolynomialRing(Zmod(n))
f = (ph + x) ** 5 * (qh + y) ** 2
res = small_roots(f, (2^500,2^400), m=2, d=3)
print(res)
p = ph + res[0][0]
q = qh + res[0][1]

phi = p^4*(p-1)*q*(q-1) 
d = pow(e, -1, phi)
flag = long_to_bytes(int(pow(c,inverse(e,phi),n))) 
print(flag)

感觉是我对二元copper的参数理解有问题（

*whisper

题目

题目给出了两个公钥pem和一个密文，根据pem可以得到：

1
2
3
n1 = 0x1b5d4fe0aa6782e275d4ce12a6d57562efbbe7db6f5277255b891729bfa2a18d3edb49843d7989a37b9516be2df8ca939058e65f64b5fb2071bea4f5f8d1392895b32bf0377d99f4f79979125e5db01cdb5080a1c2d665c9ac31b5823025499c9513277bae5e7a846cd271c4396e2ba219020e58a9055cb18a28d36a00bf717b
e = 0x079f5ccc665767b4a257e5c1ff56e9803df2e5650302daad420105fe672447743bd3f0bea1c46a4987932e9a886ca87a7afd7796abf1e5629c4986fe4f22e89cdce7abb06624465146a2e2b6ca9ab3196ceab7467974c1dc45608a200411b291fdaf99f7d80dce4db3566f4a9e2e574c6224cd07d80638d28f7820bcf4b49143
n2 = 0x071c324e8769493187c15f72d5cc695729b48488ee3fbd01db00d5c478f08c7cf32093ba61745051d3e9d169523aa91438181f47679aff5edd22950f74a1eb1443320aaa5d97f5c1e81b5ef9a3e69ba669abc4c6c4b405f5088a603a74f9bcef88823b4523574114c810600838728196f8e5e0d4aeeeeab79dd8683a72f3c017

一开始的思路

一开始完全不知道这是什么，去网上查了解了Dual RSA的密钥体制，意识到这题应该是通过d过小攻击，先想到如下构造：

M=(Aee0−n1000−n2)M = \left( \begin{array}{cccc} A & e & e\\ 0 & -n1 & 0\\ 0 & 0 & -n2\\ \end{array} \right)

理论上对A配平后规约可以得到AdAd，然而改了半天跑不出来

exp

看wp发现有专用于攻击dual 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
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
from sage.all import *
import math
import itertools
from Crypto.Util.number import *

def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = f'{ii:02d} '
        for jj in range(BB.dimensions()[1]):
            a += ' ' if BB[ii, jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

def dual_rsa_liqiang_et_al(e, n1, n2, delta, mm, tt):
    N = (n1 + n2) // 2
    A = ZZ(math.floor(N**0.5))

    _XX = ZZ(math.floor(N**delta))
    _YY = ZZ(math.floor(N**0.5))
    _ZZ = ZZ(math.floor(N**(delta - 1./4)))
    _UU = _XX * _YY + 1

    M = Matrix(ZZ, [[A, e], [0, n1]])
    B = M.LLL()
    l11, l12 = B[0]
    l21, l22 = B[1]
    l_11 = ZZ(l11 // A)
    l_21 = ZZ(l21 // A)

    modulo = e * l_21
    F = Zmod(modulo)

    PR = PolynomialRing(F, 'u, x, y, z')
    u, x, y, z = PR.gens()

    PK = PolynomialRing(ZZ, 'uk, xk, yk, zk')
    uk, xk, yk, zk = PK.gens()

    PQ = PK.quo(xk * yk + 1 - uk)
    f = PK(x * (n2 + y) - e * l_11 * z + 1)
    fbar = PQ(f).lift()

    gijk = {}
    for k in range(mm + 1):
        for i in range(mm - k + 1):
            for j in range(mm - k - i + 1):
                gijk[i, j, k] = PQ(xk**i * zk**j * PK(fbar)**k * modulo**(mm - k)).lift()

    hjkl = {}
    for j in range(1, tt + 1):
        for k in range(math.floor(mm / tt) * j, mm + 1):
            for l in range(k + 1):
                hjkl[j, k, l] = PQ(yk**j * zk**(k - l) * PK(fbar)**l * modulo**(mm - l)).lift()

    monomials = []
    for k in gijk.keys():
        monomials += gijk[k].monomials()
    for k in hjkl.keys():
        monomials += hjkl[k].monomials()

    monomials = sorted(set(monomials), reverse=True)
    assert len(monomials) == len(gijk) + len(hjkl)
    dim = len(monomials)

    M = Matrix(ZZ, dim)
    row = 0
    for k in gijk.keys():
        for i, monomial in enumerate(monomials):
            M[row, i] = gijk[k].monomial_coefficient(monomial) * monomial.subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ)
        row += 1
    for k in hjkl.keys():
        for i, monomial in enumerate(monomials):
            M[row, i] = hjkl[k].monomial_coefficient(monomial) * monomial.subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ)
        row += 1

    matrix_overview(M)
    print('=' * 128)

    B = M.LLL()

    matrix_overview(B)

    H = {i: 0 for i in range(dim)}
    for j in range(dim):
        for i in range(dim):
            H[i] += PK((monomials[j] * B[i, j]) / monomials[j].subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ))
    H = list(H.values())

    PQ = PolynomialRing(QQ, 'uq, xq, yq, zq')
    uq, xq, yq, zq = PQ.gens()

    for i in range(dim):
        H[i] = PQ(H[i].subs(uk=xk * yk + 1))

    I = Ideal(*H[1:20])
    g = I.groebner_basis('giac')[::-1]
    mon = [t.monomials() for t in g]

    PX = PolynomialRing(ZZ, 'xs')
    xs = PX.gen()

    x_pol = y_pol = z_pol = None

    for i in range(len(g)):
        if mon[i] == [xq, 1]:
            print(g[i] / g[i].lc())
            x_pol = g[i] / g[i].lc()
        elif mon[i] == [yq, 1]:
            print(g[i] / g[i].lc())
            y_pol = g[i] / g[i].lc()
        elif mon[i] == [zq, 1]:
            print(g[i] / g[i].lc())
            z_pol = g[i] / g[i].lc()

    if x_pol is None or y_pol is None or z_pol is None:
        print('[-] Failed: we cannot get a solution...')
        return

    x0 = x_pol.subs(xq=xs).roots()[0][0]
    y0 = y_pol.subs(yq=xs).roots()[0][0]
    z0 = z_pol.subs(zq=xs).roots()[0][0]

    assert f(x0 * y0 + 1, x0, y0, z0) % modulo == 0

    a0 = z0
    a1 = (x0 * (n2 + y0) + 1 - e * l_11 * z0) // (e * l_21)

    d = a0 * l_11 + a1 * l_21
    return d

if __name__ == '__main__':
    delta = 0.334
    mm = 4
    tt = 2

    n1 = 0x1b5d4fe0aa6782e275d4ce12a6d57562efbbe7db6f5277255b891729bfa2a18d3edb49843d7989a37b9516be2df8ca939058e65f64b5fb2071bea4f5f8d1392895b32bf0377d99f4f79979125e5db01cdb5080a1c2d665c9ac31b5823025499c9513277bae5e7a846cd271c4396e2ba219020e58a9055cb18a28d36a00bf717b
    e = 0x079f5ccc665767b4a257e5c1ff56e9803df2e5650302daad420105fe672447743bd3f0bea1c46a4987932e9a886ca87a7afd7796abf1e5629c4986fe4f22e89cdce7abb06624465146a2e2b6ca9ab3196ceab7467974c1dc45608a200411b291fdaf99f7d80dce4db3566f4a9e2e574c6224cd07d80638d28f7820bcf4b49143
    n2 = 0x071c324e8769493187c15f72d5cc695729b48488ee3fbd01db00d5c478f08c7cf32093ba61745051d3e9d169523aa91438181f47679aff5edd22950f74a1eb1443320aaa5d97f5c1e81b5ef9a3e69ba669abc4c6c4b405f5088a603a74f9bcef88823b4523574114c810600838728196f8e5e0d4aeeeeab79dd8683a72f3c017

    d = dual_rsa_liqiang_et_al(e, n1, n2, delta, mm, tt)
    print(d)
    c = b'\x15\xaa\xdfCO\x05\xfcG\xe0oi\x97\xa5T\xc1\xde|\xec\xda\xd1\xfa\xf4\nt\xbc|m|L_\xa53\xfe,`[\xcd\xe6\xac\xaa\x0e\xe3Wo`{\xe6P81\xb3=T\x92\x8e\xaa\xd1\xf8\xd6A\x87\xcf\xf8\xf4\xf1\xa6\x7f\xf6\xd8Fq[\xfcG\x95\xb2.!n\xc7\xec\x92\x10m\xb6\xa1\xfd\xeb\x9dd\x99h\xa8\x1c\xbb\x10\xa3\xe5\xc8(\x16z\xf2\xfd\x0e\x81SO\x11\x19\x8bc\xca\xad\x0e\xd8\xe9\xf8D\xdb\x84\x03\x02{\xa3\xeb\x1aV'
    m = power_mod(bytes_to_long(c), Integer(d), n1)
    print(long_to_bytes(m))
# SCTF{Ju5t_3njoy_th3_Du4l_4nd_Copper5m1th_m3thod_w1th_Ur_0wn_1mplem3nt4t10n}

*LinearARTs

题目

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
from random import choices
import json
from sage.all import *
from Crypto.Util.number import *
from sage.groups.perm_gps.permgroup_named import SymmetricGroup

def Young(FLAG):
    f = int.from_bytes(FLAG, "big")
    q = 65537

    s = []
    while f:
        s.append(f % q)
        f //= q
    s = vector(GF(q), s)

    n, m = len(s), len(s) ** 2

    A = Matrix(GF(q), m, n, lambda i, j: randint(0, q - 1))
    e = vector(choices(range(2^8), k=m), GF(q))*Matrix(ZZ,PermutationGroupElement(SymmetricGroup(m).random_element()).matrix())
    b = (A*s) + e


    return A,b


def Old(m, nbits):
    Sn = SymmetricGroup(m)
    p = [getPrime(360) for i in range(m)]
    N = sorted([getRandomNBitInteger(nbits) for _ in range(m)])
    S = []
    for i in range(m):
        r = [N[_] % p[i] for _ in range(m)]
        r = vector(ZZ,r)

        Per = Sn.random_element()
        P = PermutationGroupElement(Per)
        Pm = Matrix(ZZ,P.matrix())
        r *= Pm
        S.append(r)
    S = matrix(ZZ,S)

    with open('Old.matrix','w') as f:
        json.dump({"S": str(list(S)),"p": str(p)}, f)
    
    return N
def chall(nn):
    # The challenge lasted nn rounds
    # Young_level * virtue >= Old_level , where virtue = nn + 1

    h = []
    HP = []
    MP = []
    Old_level = 625*2*2
    Young_level = 25*5*5*2

    M = getPrime(Old_level)
    XP = getRandomRange(1,M)
    for _ in range(nn):
        a = getRandomRange(1,M)
        b = a*XP % M
        HP.append(a)
        MP.append(b)
        delta_level = Old_level - Young_level
        h.append(b >> delta_level << delta_level)
    return XP,M,HP,MP,h
    

mm = 16
nn = 9
nbits = 3840

A,b = Young(FLAG)
N = Old(mm, nbits)

XP,M,HP,MP,h = chall(nn)

# MP is useful ,I can use him to cast five lightning spells
D = diagonal_matrix(GF(0x10001),N+MP)
Sn = SymmetricGroup(5*5)
Per = Sn.random_element()

P = PermutationGroupElement(Per)
PM = Matrix(GF(0x10001),P.matrix())

AA = A*D*PM

with open('D.matrix','w') as f:
    json.dump({"D": str(list(D))}, f)
# OK! Find your martial arts, and then you can get the flag.
with open("output.txt", "w") as f:
    json.dump({"AA": str(list(AA)), "b": str(b)}, f)
print(f'My SymmetricGroup is {Sn}, and my element is {Per}')
print(f'M = {M}')
print(f'h = {h}')
print(f'HP = {HP}')

'''
My SymmetricGroup is Symmetric group of order 25! as a permutation group, and my element is (1,23,2,13,3,16,15,6,22,18,14,4,25,11,20,24,21,9,5,17,7,19,10,12,8)
M = 309169501373330124045649100152326414225457160505584328527283516968464416389302355829097052128714780092162406614467026044744098784954762500832278190406881802198303575338158311874491341970444579146638248815636164413771772581964591833455055886833879504320098506335328910379223983277573694356846337961823081287986674791459748001014087760336006966850192999063236788568848765812192775492248445517060690151700498331622538367493718859724934115228375142396923937735633684527869745420378950550480692200706066019831688796077313463059296313396035429537407627377675974680696279162072713257960965681304091009329215383850223530139165455326927677102783057396241883175412729216204807235187239596365892879371542214145426492827777125727970815789114727245511828912252143569
h = [3565625090222584896920916237461241765625829204082396377386021101162536812411479309464325956424849651112502540095796665989782448302150047491000013081443589381171861802823657878857754676608742927932812781165716659755896099505195018830422885342733139127785165794897376463794696074605473512720672450888626374504772116915620258088753289255996096552892614801083370595759624402874902282635442418547645823133641783382626721416313803991932439793168113855890150599332984583295219543856049901518912201443065300476561372304830840276820139993555523469165273121628823953454126151208689489078628524850757272649061955436843893289237414654732290904213005377463766762255194199607599718375650615493280298611532927519686558670313416090562438894368509350896602591065538560, 286740894693471986151090603562932147965458822098297907353215124508138484491994267754471216888566417392843923796488725160656461314962959042706124173470952968241147487040483767911639159119505992553207913863135028688626896196178757909088128827455625174341894140582939848620368540355056452428553556546413465430152617836247505772663758606552662729528340901377490256234099815707208769579251833692482247933846648593307680305448986314447242583396656418769737861680456297522358131674037354880608888487272985141452871763297604747444764332049229204365395410106847606241968638474099061876569990163879954288002836750959104349076854993248516655758322107956062243468530601256243967323153547535726777712582210098524981336526310800007425464476736381605758610129914167296, 202445786178968197828946112166667682571891905248793492278433983415264905988886412319222803698650008275405441752508434114212113517053913972304515710532012288036732448805044856628337036478357496484044773293960097063848568051250774170422935810965491124102107450786197166927290614807575403261921855599437944525251033428950982061449203659272914014109623656149839199935645660386382459896840619916225080206084500617856222897968865436783548821187873430635315967325778835200418210099836625362334832448337496843986398001079590846483593452928602841826412074751479179471599709999916393508418744578599831517548843854866251289525136765297969136698285441109232446206843977149859059568434871554288377088102779550812057943402777376610057499017696210394059743209313009664, 114630215368349491250326648494149748728124718005857201833657753308980378360823813480094685056650954220208569495921715772409260048257134505583210349697604470912610748671738387322753221966031149012764535612682778184882174392537951540598166408100353995693537007226929298573802177602978136134506604598926968767277963229517115896872176785224081721198822306288029114228955110090342800494317915814873698062519566559427796027618459996738296291782097320521350172532923653864250838232011730592925952612867718426259229217480911558421879422300001641170190840092379605603655701803649801243406059797147753118709730213303123683329677068533772082060407549189564758770771711148071596602056935716438347268248190581386987972757911856155781563899140822797888004226036006912, 128249367678574240079270694387429301574447189368221420750047602082333294620192478593526403955673394674124614483528399397766799072294205407818283464218350759458734269850052374022374583516046462573242829813776315162366850512131805663098817008453376098230770350796562755291771240680188153978483320771657621585572523650775437065002970862224206343896650474078023744187172724827284900132434561870157274624749481073656218832950661419154809116630241897087363941068977482336058825222409922455565132842885044852488100437379745993397785019888492704177085025661715401393223084613786993440233186999961708361656323625565518221228007812487647507152403406194060777071074419667727156839380340460479471882700515901974677682591933244024896502221255164137619867236474814464, 59331241745881917257932833661253483407124868132789104057434303748460794035055450167305496229505776497962206681068504038089886777631651664100577079680933516972657892279730519042800959265778075851643260975944157575808540832473360789304763830393990596483325556391563383526131388426655998362610795663009444329530380313582369506744601127066018505286584082074112032220681653032998814836135211241601616761559477125123260865574463289315537641250468595444847485104869371846138937594815717839233479424297762637589843061706537365341325349697086472650360732699495909942722893269089976271337217878676728476285757191230122449283410993290558727101211299826258005529280347023431637543174327095221833097882251371141896661614980087581376418853642047359092191718247759872, 194175487858295065586566223420720835354218714701012787036868166885106803179611016852320235121944886794854103233580220709024806072743993477154116046455972680314714490810103482613775169723949822599089353607462687446238694112422779778557153306320141326888706724709408146840971915646939721136724368012432988045478440516756541030644897102338343015620307071124895653986756365725579987250601332133147888516462970772662004254372283824275049130754409522022155104472953510056515893487814795314057133448327072939691256835996305152489881345263632544581620669637374642183724635278556621665654137071320546871015687481523597402928763713183489458838102245889150936728919959706046092027960728825776566021949524779914956226078468441681639597976295123311554992063660425216, 115807966653135071136266364151575193370063353963428994232152558690537462513652457844803096649471511022423130391640990718769139833768597282872892832632006932256100725142377601958457582836326282142674470340977659300588249614977457789078637672424804434580082554677223019302922992562279282682989740074843377451539592513262883913515900320935326048141177654658002842824967867990878423576079246988742657580816398545604320575322509216636723893917401586976250940528255869144608693606581992658961868351662299980182039083401570931369157275822911645710245831972301615048181855392924402552747776587682847866506513589721569586179062186510923857682304736484524409943982860419833114775174973677241133994963586243092033231181717755422868113246798964708435895447826989056, 35892864763676162390876495832131732661057713103645821857653105944898881372368808709419507620431545862639883539544774550258981962490994311035563824804791343118179784911204081384298523734092852978345353083620780025983844560713535542579917199852557029443606552741189260726705956142592472777625642697686483587065598383553745177190736612246797880186504227507540789056735743669295160656843457591270441961646851151123270490417727787782300206183313402455683157806373799412772262389178947152383087432869175216907112201344491993073522598897459497720231382736974467891671184580545749653915968971302794570679028312275641136161418552643700105215949462752782765599606395043723535992514850129235084780569665298381129831228968986167487292913320768400938041503014453248]
HP = [182123398439336131233484419016500805950625530876289136147992418330368556518782504528500478328506268530182121028338611308706301778495117293952384271741141930454826813234222655694969514594179399691491676343267560926415204796892285953757083137635724586246679285504584200603423040990857955982592545447321735123888380669252758270022750955484747603018957220340523162322224297824154306196315662236519394066376582303992842999145368668536271548561974662730580382535581064544751603313110317522142473855128127879421866476758202400277448627166191464212616826131845112048518089279156877724351779259697512559047606602356481432326384500230304234630224805224043299183292854524931957718694768306272627669496947333830650701612740067754226344379590044087735385490127725862, 143170049879066655087340950742576943114220056125957541251904657597420632960015895981469092773424062349481612793313849969949143634455140221504418524950906026552571808412365313452770620316647140315635576351924131570731151371864300979486246561311374091503771233474221846682477948158595874825046725186096019808916856990568087679235183223125111635340379631262792582193894921427748477534899648278496684573736979116799130367368459501772350225298850161734598992871658808303947946703790369232633550983464071710073626283163523659905448412753809088559015473221667463885047754120012784534383142422681768521744011385759111784771218858429141270195947803513052066866898605116497618560152428747336114471742600059289342252682494024257280492765302681978041917175224445454, 181932081065216017223259767432026159751069100962417675256904857171174594214631105569878401257202843288868067795959660425655397502682572819329811836847256980387967545675607257191386494389870983892416162767006265255985611267066664459013834260578459679814704254643652527448346657946799415019242620362556994094217501805852227552561431064112972359577708305419407712233651342990435225577864469921706228376386943352990854043536613387681781610381704457332320684886669558444649325853462867815167473502469305672972117003639658784729134706896312010708005781941993559519054971159338636279746679220293668476785752715272037394473281514117697060980377364913173031572794672785720241295564153405600993322639561228795731008971285970805298272968367327982292736365952177736, 152197501838094386559667505260111556746524794647762036036984156853293482749405051706379215782024625767996604204199239858042655575156447769644733342469940464962491758196879181740442958683860120188153222622045687386550968060691333980045707578681522952010130720785366069103645756481641865768541014660604224000448808608848607142992914438243019336580286597455942208546183871629991237012627078724041815698483916930337697145596477943636313719062754662224057190310995369364817444976298713991954316505112491477110025799278176478205958831032614361098570277711286905522504386261323350696026797810604096448605140635754896533192146402989175530945145957561334345659035675075518654525640506611082619111666729303712983450765181951782352125875791130477959487243678637091, 13260127114160132039578764564277724908293717164091148143281881592450508800268944502885346275659282139962084615098549527321116911955505649119891798866789702019684393024690093331965422247341532921411724247274538089836518071897735012248880718279028139698315282234778842097294789834605571276706239190589177804771135138639650083317735678737873354475068162084129555751126946723880482765306519620594499615623179141020788167278111494656031619604249830332631535459164808166638124806843052957919064456863967475953053614347964520430672883482509352453640521720313380086324061829310129198351733197836811498655541708077300463414261809122652381872563486116022996781876662952751320598808796685963865092538114154484684417346701057121540968905340884852819266786655758589, 7726965701613058376939617426173930484905424609871511448979899585789330472291184137208473525618669017229437131718602138062693323242254540169837667647945751730728109543890184121875756549720616016417689684297714982752898170211522441794931085191911567142756874944612942983995000585648922927662513704308624388978740497618316239028274910398075357992565743563209649419566296437582035744561981287334953927069851636537379718348745797306743042426246174030053256711319421877929342022143063981126785133505358707977994735220823800241921524140116409926290245600210702333580796340264633188699655847265231481741281891892263047439742010063674785264961945504178892794083333407945969304699309469264200568906760592035714702098416830232068808480043043046899584880476365211, 180019050945153380400290419089497765220330628588910896281952550416089875088850281952204916892735263785902815673400396668990373595469072648699918494008065197996354855591310768398651316061183602708507734278231600299784123286043254063248471261126675877896352754705297219631260970186401862696837291306580096200621090959901083133979809165850290006958174043988594120292941019793669119321273860506863788556691180109910206811333775009617945993184652622929206661236756401337666271307645630166144277622050610823301758570383783302397752531144991093835433241988398747399949918853848203882961092951831645541246295873588649289531107814613167236073250185453276804880016561013769084225682634383784489652871867815664211238325551136693769474979447466046146633345857611195, 153629149463789849413429112784055293255734339122176408662359601604336509143473758509975758863274395783633189549584941125392600362702091233425733911049553699926215208790821097092121122480643207790283486114884596194662369389215802952635756543090033023067139610689568413680910122744788001731552268160061684744631583107942765508030881967516350806276166348479082293252825499156766363138008724860360262292088895234376252334258828427316419408016153682496909981178280572676774045522450227853270448821337580837554794712541359286413423248459963738684095208415746808201768526760043282181933350859027227907243501251390338333188167931974689538439823388790515993422873395205982049903304374197483641428361419371833919139638015039992779119950859870347438758668679332495, 276427336329209668688130277925589460360311327851014652110707325284581770430564994121969230515633704248812997375123175470056237355182594647858048847262042361717893313893682161435196235153101006253340527909451448103893104917041136181377802230394106849393237486928849495116195885563734324888330607632821513438897200091110205098807840437587357564885934968344589488833398453563587665373858111713149172110412979734635024012258145628247175689960363707897865274630069427102722542299814253018238192096822853168130596686909789751383470674093768125446566821380042192204089190375373896356618809538058749144194802493153530124585829617231928160073305696376878930156414497547968857648212679322981790227182840452493558367673102471438871220031633314842129410346869161197]
'''

看着一堆东西，但是给了一堆信息，最后居然只需要造格子打lwe就行 早知道当时就应该先做这个（）

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from Crypto.Util.number import *
import json

def primal_attack2(A,b,m,n,p,esz):
    L = block_matrix(
        [
            [matrix(Zmod(p), A).T.echelon_form().change_ring(ZZ), 0],
            [matrix.zero(m - n, n).augment(matrix.identity(m - n) * p), 0],
            [matrix(ZZ, b), 1],
        ]
    )
    #print(L.dimensions())
    Q = diagonal_matrix([1]*m + [esz])
    L *= Q
    L = L.LLL()
    L /= Q
    for res in L:
        if(res[-1] == 1):
            e = vector(GF(p), res[:m])
        elif(res[-1] == -1):
            e = -vector(GF(p), res[:m])
        s = matrix(Zmod(p), A).solve_right((vector(Zmod(p), b)-e))
        mm = 0
        j = 0
        for i in s.list():
            mm+=int(i)*65537**j
            j+=1
        flag = long_to_bytes(int(mm))
        if b'SCTF' in flag:
            print(flag)
            return

q = 65537
Sn = SymmetricGroup(5*5)
per = Sn((1,23,2,13,3,16,15,6,22,18,14,4,25,11,20,24,21,9,5,17,7,19,10,12,8))
P = PermutationGroupElement(per)
PM = Matrix(GF(0x10001),P.matrix())
with open("output.txt", "r") as f:
    d1 = json.load(f)
with open("D.matrix", "r") as f:
    d2 = json.load(f)
AA = matrix(GF(q),eval(d1["AA"]))
b = vector(GF(q),eval(d1["b"]))
D = matrix(GF(q),eval(d2["D"]))
A =  AA * PM**(-1) * D**(-1)

primal_attack2(A, b, 625,25,65537,1)
# SCTF{HunYu4n_TaiChi-5tyl3_P3rmut4t10nProup_m4st3r}

moectf 2024

被新生赛薄纱（）

rsa_revenge

题目

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 getPrime, isPrime, bytes_to_long
from secret import flag

def emirp(x):
    y = 0
    while x != 0:
        y = y * 2 + x % 2
        x = x // 2
    return y

while True:
    p = getPrime(512)
    q = emirp(p)
    if isPrime(q):
        break
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(f"{n = }")
print(f"{c = }")
"""
n = 141326884939079067429645084585831428717383389026212274986490638181168709713585245213459139281395768330637635670530286514361666351728405851224861268366256203851725349214834643460959210675733248662738509224865058748116797242931605149244469367508052164539306170883496415576116236739853057847265650027628600443901
c = 47886145637416465474967586561554275347396273686722042112754589742652411190694422563845157055397690806283389102421131949492150512820301748529122456307491407924640312270962219946993529007414812671985960186335307490596107298906467618684990500775058344576523751336171093010950665199612378376864378029545530793597
"""

二进制下的反素数，逐位爆破，注意判断p*q高位是否与n一致即可

*hidden_poly

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Crypto.Cipher import AES
import os
q = 264273181570520944116363476632762225021
key = os.urandom(16)
iv = os.urandom(16)
root = 122536272320154909907460423807891938232
f = sum([a*root**i for i,a in enumerate(key)])
assert key.isascii()
assert f % q == 0

with open('flag.txt','rb') as f:
    flag = f.read()

cipher = AES.new(key,AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pad(flag,16)).hex()

with open('output.txt','w') as f:
    f.write(f"{iv = }" + "\n")
    f.write(f"{ciphertext = }" + "\n")

我的思路

已知如下等式：

∑i=015airooti=kq\sum_{i=0}^{15}a_iroot^i = kq

直接构造格子有：

L=(111root⋱⋮1root15q)(a0,a1,a2,…,a15,k)L=(a0,a1,a2,…,a15,0)L = \left( \begin{array}{cccc} 1 & & & & 1\\ & 1 & & & root\\ & &\ddots& & \vdots\\ & & & 1 & root^{15}\\ & & & & q \end{array} \right) \\(a_0,a_1,a_2,…,a_{15},k)L=(a_0,a_1,a_2,…,a_{15},0)

但是根本没法配平，卡住了（）

EXP

对等式转化一下得到：

∑i=115airooti−kq=−a0\sum_{i=1}^{15}a_iroot^i - kq = -a_0

可以构造格子：

L=(1root⋱⋮1root15q)(a1,a2,…,a15,k)L=(a1,a2,…,a15,a0)L = \left( \begin{array}{cccc} 1 & & & root\\ &\ddots& & \vdots\\ & & 1 & root^{15}\\ & & & q \end{array} \right) \\(a_1,a_2,…,a_{15},k)L=(a_1,a_2,…,a_{15},a_0)

可以直接得到系数 代码如下

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.Padding import pad
from Crypto.Util.number import *
from Crypto.Cipher import AES
from sage.all import *
iv = b'Gc\xf2\xfd\x94\xdc\xc8\xbb\xf4\x84\xb1\xfd\x96\xcd6\\'
ciphertext = 'd23eac665cdb57a8ae7764bb4497eb2f79729537e596600ded7a068c407e67ea75e6d76eb9e23e21634b84a96424130e'
q = 264273181570520944116363476632762225021
root = 122536272320154909907460423807891938232
length = 16
L = Matrix(ZZ, length, length)
for i in range(length - 1):
    L[i, i] = 1
    L[i, -1] = root ** (i + 1)
L[-1, -1] = -q
x = L.LLL()
print(x)
ciphertext = bytes.fromhex(ciphertext)
for i in x:
    try:
        key = ''
        for j in range(16):
            key = key + chr(abs(int(i[j])))
        key = key[-1] + key[:-1]
        key = key.encode()
        cipher = AES.new(key, AES.MODE_CBC, iv)
        ciphertext = cipher.decrypt(ciphertext)
        if b'moectf' in ciphertext:
            print(ciphertext)
            break
    except:
        pass

*ezLCG

题目

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from sage.all import *
from random import getrandbits, randint
from secrets import randbelow
from Crypto.Util.number import getPrime,isPrime,inverse
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secret import priKey, flag
from hashlib import sha1
import os


q = getPrime(160)
while True:
    t0 = q*getrandbits(864)
    if isPrime(t0+1):
        p = t0 + 1
        break


x = priKey
assert p % q == 1
h = randint(1,p-1)
g = pow(h,(p-1)//q,p)
y = pow(g,x,p)


def sign(z, k):
    r = pow(g,k,p) % q
    s = (inverse(k,q)*(z+r*priKey)) % q
    return (r,s)


def verify(m,s,r):
    z = int.from_bytes(sha1(m).digest(), 'big')
    u1 = (inverse(s,q)*z) % q
    u2 = (inverse(s,q)*r) % q
    r0 = ((pow(g,u1,p)*pow(y,u2,p)) % p) % q
    return r0 == r


def lcg(a, b, q, x):
    while True:
        x = (a * x + b) % q
        yield x


msg = [os.urandom(16) for i in range(5)]

a, b, x = [randbelow(q) for _ in range(3)]
prng = lcg(a, b, q, x)
sigs = []
for m, k in zip(msg,prng):
    z = int.from_bytes(sha1(m).digest(), "big") % q
    r, s = sign(z, k)
    assert verify(m, s, r)
    sigs.append((r, s))


print(f"{g = }")
print(f"{h = }")
print(f"{q = }")
print(f"{p = }")
print(f"{msg = }")
print(f"{sigs = }")
key = sha1(str(priKey).encode()).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC,iv)
ct = cipher.encrypt(pad(flag,16))
print(f"{iv = }")
print(f"{ct = }")


'''
g = 81569684196645348869992756399797937971436996812346070571468655785762437078898141875334855024163673443340626854915520114728947696423441493858938345078236621180324085934092037313264170158390556505922997447268262289413542862021771393535087410035145796654466502374252061871227164352744675750669230756678480403551
h = 13360659280755238232904342818943446234394025788199830559222919690197648501739683227053179022521444870802363019867146013415532648906174842607370958566866152133141600828695657346665923432059572078189013989803088047702130843109809724983853650634669946823993666248096402349533564966478014376877154404963309438891
q = 1303803697251710037027345981217373884089065173721
p = 135386571420682237420633670579115261427110680959831458510661651985522155814624783887385220768310381778722922186771694358185961218902544998325115481951071052630790578356532158887162956411742570802131927372034113509208643043526086803989709252621829703679985669846412125110620244866047891680775125948940542426381
msg = [b'I\xf0\xccy\xd5~\xed\xf8A\xe4\xdf\x91+\xd4_$', b'~\xa0\x9bCB\xef\xc3SY4W\xf9Aa\rO', b'\xe6\x96\xf4\xac\n9\xa7\xc4\xef\x82S\xe9 XpJ', b'3,\xbb\xe2-\xcc\xa1o\xe6\x93+\xe8\xea=\x17\xd1', b'\x8c\x19PHN\xa8\xbc\xfc\xa20r\xe5\x0bMwJ']
sigs = [(913082810060387697659458045074628688804323008021, 601727298768376770098471394299356176250915124698), (406607720394287512952923256499351875907319590223, 946312910102100744958283218486828279657252761118), (1053968308548067185640057861411672512429603583019, 1284314986796793233060997182105901455285337520635), (878633001726272206179866067197006713383715110096, 1117986485818472813081237963762660460310066865326), (144589405182012718667990046652227725217611617110, 1028458755419859011294952635587376476938670485840)]
iv = b'M\xdf\x0e\x7f\xeaj\x17PE\x97\x8e\xee\xaf:\xa0\xc7'
ct = b"\xa8a\xff\xf1[(\x7f\xf9\x93\xeb0J\xc43\x99\xb25:\xf5>\x1c?\xbd\x8a\xcd)i)\xdd\x87l1\xf5L\xc5\xc5'N\x18\x8d\xa5\x9e\x84\xfe\x80\x9dm\xcc"
'''

exp

DSA签名，且nonce为LCG生成；注意到LCG的模数和DSA使用的一致，考虑去造同余方程组去解但是我完全不会Groebner

代码如下：

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
from hashlib import sha1
from Crypto.Util.number import *
from gmpy2 import *
from Crypto.Cipher import AES
from sage.all import *

g = 81569684196645348869992756399797937971436996812346070571468655785762437078898141875334855024163673443340626854915520114728947696423441493858938345078236621180324085934092037313264170158390556505922997447268262289413542862021771393535087410035145796654466502374252061871227164352744675750669230756678480403551
h = 13360659280755238232904342818943446234394025788199830559222919690197648501739683227053179022521444870802363019867146013415532648906174842607370958566866152133141600828695657346665923432059572078189013989803088047702130843109809724983853650634669946823993666248096402349533564966478014376877154404963309438891
q = 1303803697251710037027345981217373884089065173721
p = 135386571420682237420633670579115261427110680959831458510661651985522155814624783887385220768310381778722922186771694358185961218902544998325115481951071052630790578356532158887162956411742570802131927372034113509208643043526086803989709252621829703679985669846412125110620244866047891680775125948940542426381
msg = [b'I\xf0\xccy\xd5~\xed\xf8A\xe4\xdf\x91+\xd4_$', b'~\xa0\x9bCB\xef\xc3SY4W\xf9Aa\rO',
       b'\xe6\x96\xf4\xac\n9\xa7\xc4\xef\x82S\xe9 XpJ', b'3,\xbb\xe2-\xcc\xa1o\xe6\x93+\xe8\xea=\x17\xd1',
       b'\x8c\x19PHN\xa8\xbc\xfc\xa20r\xe5\x0bMwJ']
sigs = [(913082810060387697659458045074628688804323008021, 601727298768376770098471394299356176250915124698),
        (406607720394287512952923256499351875907319590223, 946312910102100744958283218486828279657252761118),
        (1053968308548067185640057861411672512429603583019, 1284314986796793233060997182105901455285337520635),
        (878633001726272206179866067197006713383715110096, 1117986485818472813081237963762660460310066865326),
        (144589405182012718667990046652227725217611617110, 1028458755419859011294952635587376476938670485840)]
iv = b'M\xdf\x0e\x7f\xeaj\x17PE\x97\x8e\xee\xaf:\xa0\xc7'
ct = b"\xa8a\xff\xf1[(\x7f\xf9\x93\xeb0J\xc43\x99\xb25:\xf5>\x1c?\xbd\x8a\xcd)i)\xdd\x87l1\xf5L\xc5\xc5'N\x18\x8d\xa5\x9e\x84\xfe\x80\x9dm\xcc"

M = [bytes_to_long(sha1(m).digest()) for m in msg]

R = []
S = []
for i in sigs:
    R.append(i[0])
    S.append(i[1])

PR = PolynomialRing(Zmod(q), names='k1, k2, k3, k4, k5, a, b, x')
k1, k2, k3, k4, k5, a, b, x = PR.gens()
f1 = a * k1 + b - k2
f2 = a * k2 + b - k3
f3 = a * k3 + b - k4
f4 = a * k4 + b - k5
f5 = M[0] + R[0] * x - S[0] * k1
f6 = M[1] + R[1] * x - S[1] * k2
f7 = M[2] + R[2] * x - S[2] * k3
f8 = M[3] + R[3] * x - S[3] * k4
f9 = M[4] + R[4] * x - S[4] * k5

F = [f1, f2, f3, f4, f5, f6, f7, f8, f9]
I = Ideal(F)
GB = I.groebner_basis()
print(GB)
x = -1144162652064701115049643134487732928553039124427 % q
key = sha1(str(int(x)).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
flag = cipher.decrypt(ct)
print(flag)
# b'moectf{w3ak_n0nce_is_h4rmful_to_h3alth}\t\t\t\t\t\t\t\t\t'

基本是照着板子抄的，后面该认真学一下groebner了（）

DASCTF 十月

太会套了crypto()

ez_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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from Crypto.Util.number import *
from secret import flag
from sage.all import *

num1 = getPrime(512)
num2 = getPrime(512)
while num1<num2 :
    num2 = getPrime(512)
ring = RealField(1050)
num3 = ring(num1) /ring(num2)
print("num3=",num3)
p = getPrime(512)
q = getPrime(512)
n=p*q
e=65537
m = bytes_to_long(flag)
c=pow(m,e,n)

print("n=",n)
print("c=",c)

n2 = getPrime(512) * getPrime(512)
e1 = randint(1000,2000)
e2 = randint(1000,2000)
c1 = pow(p+num1,e1,n2)
c2 = pow(p+num2,e2,n2)

q1 = getPrime(512)
leak1 = pow(q+q1,2024,n)
leak2 = pow(q1+2024,q,n)


print("n2=",n2)
print("e1=",e1)
print("e2=",e2)
print("c1=",c1)
print("c2=",c2)
print("leak1=",leak1)
print("leak2=",leak2)

"""
num3= 1.36557212221826657073387899060669771982679822943621690677450888408226656788387273887547841291114809989272635809810564202247340711087479554863446719786359395466961253205133910506682801159622545780721946115442033391600881399634390008053822158098121985270501317972263356522400827768601773721146954464269212959784543085
n= 85105083975491693151454182116844944807066048677068373328227644321539783064315677834754866742549592569194223084173286381150626593510265361114796714226058887906219454795525438819082646860141163940340082006344850825956811992304447978369108606993344902286569100146695092703383844402883938506877787042873586279543
c= 8090472119640930864901421058741085326954308673260202542020919764880488559370287585797498390920330336595858609617432370825503480936376306766495089200286004922821787548265246289552343468177624634434613746605553770994437785042510225956023382347023663125411103947669109085411939772215657220674436476279268458980
n2= 101642316595332652021348165259853423287787139517550249986161819826180514401858258316466101056877182367161299111697465439636861942636526396547011727147471566130633614685728563576613692851860684686033186826342178072882901576159305747639645374751566751967096281105148714033096611618024355982220235949274576036321
e1= 1630
e2= 1866
c1= 8857135083997055103287497833179378469532619748945804429057682575070405217145941944821968708809563240261403711644389684947851643865895254406194464015430673347359589677809515117412321862622147634752091324365628790687343748145339949310696116239361890881096088375070083053010564890401663562726144984405628773323
c2= 44531030636557714647477473185500183066851251320453194953972504422367649302810396344051696851757189817391648356459225688318373454949578822468293099948132700460437006478679492801335689493431764882835346904225119630026545592437198370606462285405519745361570058335573353886454277790277663038008240372746639859253
leak1= 82301473255013183706458389946960254392188270550712533886416705365418418731488346328643954589202172816597173052792573628245245948345810581701878535280775967863966009605872386693838526935762655380705962833467046779524956212498594045378770790026387120339093736625186401934354434702063802537686761251873173518029
leak2= 43580171648136008789232340619597144591536098696024883687397347933098380327258730482377138309020375265135558484586783368757872008322883985094403855691297725907800406097129735499961231236473313141257901326737291586051506797429883866846199683028143924054925109557329949641367848264351523500925115860458645738192
"""

exp

part 1

已知在R=Realfield(1050)R = Realfield(1050)上的等式：

num3=R(num1)R(num2)num_3 = \frac{R(num_1)}{R(num_2)}

连分数展开得到num1和num2

part 2

生成两个512素数乘积得到n2，并给出以下等式：

c1=(p+num1)e1  mod  n2c2=(p+num2)e2  mod  n2c_1 = (p + num_1)^{e_1} \; mod\; n2 \\ c_2 = (p + num_2)^{e_2} \; mod \; n2

因为num1和num2已知，且e1, e2并不大，因此直接做多项式GCD就可以得到p，至此就可以解RSA获得flag

part 3

已知：

leak1=(q+q1)2024  mod  n//leak2=(q1+2024)q  mod  nleak_1 = (q + q_1)^{2024} \; mod\; n // leak_2 = (q1+2024)^q \; mod \; n

在模q下显然有：

leak1=q12024  mod  q//leak2=q1+2024  mod  qleak_1 = q_1^{2024} \; mod \; q // leak_2 = q_1 + 2024 \; mod \; q

所以有：

q=gcd(leak1−(leak2−2024)2024,n)q = gcd(leak_1 - (leak_2 - 2024)^{2024}, 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
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
68
69
70
71
72
73
from Crypto.Util.number import *
import math

num3 = 1.36557212221826657073387899060669771982679822943621690677450888408226656788387273887547841291114809989272635809810564202247340711087479554863446719786359395466961253205133910506682801159622545780721946115442033391600881399634390008053822158098121985270501317972263356522400827768601773721146954464269212959784543085
n = 85105083975491693151454182116844944807066048677068373328227644321539783064315677834754866742549592569194223084173286381150626593510265361114796714226058887906219454795525438819082646860141163940340082006344850825956811992304447978369108606993344902286569100146695092703383844402883938506877787042873586279543
c = 8090472119640930864901421058741085326954308673260202542020919764880488559370287585797498390920330336595858609617432370825503480936376306766495089200286004922821787548265246289552343468177624634434613746605553770994437785042510225956023382347023663125411103947669109085411939772215657220674436476279268458980
n2 = 101642316595332652021348165259853423287787139517550249986161819826180514401858258316466101056877182367161299111697465439636861942636526396547011727147471566130633614685728563576613692851860684686033186826342178072882901576159305747639645374751566751967096281105148714033096611618024355982220235949274576036321
e1 = 1630
e2 = 1866
c1 = 8857135083997055103287497833179378469532619748945804429057682575070405217145941944821968708809563240261403711644389684947851643865895254406194464015430673347359589677809515117412321862622147634752091324365628790687343748145339949310696116239361890881096088375070083053010564890401663562726144984405628773323
c2 = 44531030636557714647477473185500183066851251320453194953972504422367649302810396344051696851757189817391648356459225688318373454949578822468293099948132700460437006478679492801335689493431764882835346904225119630026545592437198370606462285405519745361570058335573353886454277790277663038008240372746639859253
leak1 = 82301473255013183706458389946960254392188270550712533886416705365418418731488346328643954589202172816597173052792573628245245948345810581701878535280775967863966009605872386693838526935762655380705962833467046779524956212498594045378770790026387120339093736625186401934354434702063802537686761251873173518029
leak2 = 43580171648136008789232340619597144591536098696024883687397347933098380327258730482377138309020375265135558484586783368757872008322883985094403855691297725907800406097129735499961231236473313141257901326737291586051506797429883866846199683028143924054925109557329949641367848264351523500925115860458645738192

# part 1
cf = continued_fraction(num3) 
cvg = cf.convergents()  
for cv in cvg:
    Num2 = cv.denominator() 
    Num1 = cv.numerator()  
    if is_prime(Num1) and is_prime(Num2) and int(Num1).bit_length() == 512:
#         print(Num1)
#         print(Num2)
        break


# part 2
def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11

def GCD(a, b):
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)


PR.<x> = PolynomialRing(Zmod(n2))
f1 = (x + num1)^e1 - c1
f2 = (x + num2)^e2 - c2
res = GCD(f1,f2)
print(-res.monic().coefficients()[0])
P = -res.monic().coefficients()[0]
Q = n // P
print(long_to_bytes(int(pow(c,inverse(65537,(P-1)*(Q-1)),P*Q))))


# part 3
q = math.gcd(leak1 - (leak2 - 2024)^2024, n)

*easy_xor

题目

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
68
69
70
import os
from Crypto.Util.number import *
from hashlib import *
from sage.all import *

def encrypt(msg):
    p = getPrime(256)
    n = 2**512
    x = msg[0] << 7
    for i in msg:
        x = int(x*p % n)
        x ^= i
    return x ^ len(msg) ,p


def prime_to_matrix(p , n):
    
    binary_rep = bin(p)[2:].zfill(n^2)
    matrix = Matrix(GF(2), n, n, [int(b) for b in binary_rep])
    
    return matrix

def matrix_to_prime(matrix, n):

    binary_rep = ''.join(str(matrix[i, j]) for i in range(n) for j in range(n))
    p = int(binary_rep, 2)
    
    return p

key = os.urandom(16)
key_list = [i for i in key]
c,p = encrypt(key_list)

P = prime_to_matrix(p,16)

q = getPrime(256) 
Q = prime_to_matrix(q,16)

R = P*Q
r = matrix_to_prime(R,16)

s = p^r
S = prime_to_matrix(s,16)

array_q = []
t = q
while t > 0:
    array_q.append(t%256)
    t = t//256

m = len(array_q)
A = matrix(ZZ,m,m)
for i in  range(m):
    for j in range(m):
        A[i,j] = randint(65537//2,65537)

x = matrix(ZZ,[array_q])
x = x.T
e = matrix(ZZ,m,1)
for i in range(m):
    e[i,0] = randint(1,256)
b = A*x + e  

with open("out.txt","w") as f:
    f.write(f"c = {c}\n")
    f.write(f"S = {S}\n")
    f.write(f"A = {A}\n")
    f.write(f"b = {b}\n")
    
flag = "CBCTF{"+sha256(key).hexdigest()+"}"

exp

part 1

最后的b = A*x + e显然是一个LWE样本，解LWE可以得到向量x，也就得到了q，从而得到矩阵Q

part 2

根据代码有如下等式：

R=P∗Q//s=p⊕rR = P * Q // s = p \oplus r

而第二个式子在矩阵意义下等价于：

S=P+RS = P + R

因此有：

S=P(Q+E)S = P(Q + E)

解矩阵方程得到P，从而得到p

*part 3

铸币了，打的时候没想到咋做

最后一步的key进行了如下操作：

c=((((27k1)p⊕k1)p⊕k2)p…)p⊕k16⊕16  mod  2512c = ((((2^7k_1)p \oplus k_1)p \oplus k_2)p …)p \oplus k_{16} \oplus 16 \; mod\; 2^{512}

该式可以转化为：

c⊕16=((((27k1)p+k1′)p+k2′)p…)p+k16′  mod  2512c \oplus 16 = ((((2^7k_1)p + k_1^{'})p + k_2^{'})p …)p + k_{16}^{'} \; mod\; 2^{512}

展开多项式得到：

c⊕16=27k1p16+k1′p15+k2′p14+…+k16′  mod  2512c \oplus 16 = 2^7k_1p^{16} + k_1^{'}p^{15} + k_2^{'}p^{14} + … + k_{16}^{'} \; mod\; 2^{512}

系数都很小，造格子LLL即可获得系数，然后从后往前两两做差并异或，就能恢复key

代码如下：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
from sage.all import *
from Crypto.Util.number import *
from hashlib import *


def prime_to_matrix(p, n):
    binary_rep = bin(p)[2:].zfill(n ^ 2)
    matrix = Matrix(GF(2), n, n, [int(b) for b in binary_rep])

    return matrix


def matrix_to_prime(matrix, n):
    binary_rep = ''.join(str(matrix[i, j]) for i in range(n) for j in range(n))
    p = int(binary_rep, 2)

    return p


c = 3235165504936419327001182958857604252407894106191511594689199770239529482330201776634335054024549532136197669522057846845936856432300465191006002492337710
S = [[0,0,0,1,1,0,0,0,1,1,0,0,1,0,1,0],
[1,1,0,1,1,1,0,0,1,0,1,0,0,0,0,0],
[1,0,1,0,0,1,0,1,1,0,1,0,1,0,0,1],
[0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,1],
[1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,1],
[0,1,0,1,0,0,1,0,0,1,0,1,0,0,1,1],
[0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,0],
[0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,0],
[0,1,1,0,1,1,1,0,0,1,1,0,0,1,0,1],
[0,1,1,0,0,1,0,1,0,0,0,1,0,0,0,1],
[0,1,0,0,0,0,0,1,1,1,1,0,0,1,1,1],
[0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1],
[1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0],
[0,1,0,0,1,1,0,0,0,1,0,1,1,0,1,0],
[0,0,1,0,1,1,1,1,0,1,1,1,0,1,1,0],
[1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0]]
A = [[58759,40201,39541,50266,35606,44877,56746,51320,40748,58265,48198,36126,48722,38757,34645,49875,39713,39344,34596,44689,40300,55926,43000,56106,63327,47482,39178,49257,45418,48650,50427,41214],
[37223,34740,55875,61596,60851,42409,41726,54223,37354,44483,35507,64442,65181,65016,52834,59838,45696,50951,64689,55931,44398,62595,54959,40901,53153,37642,49294,44606,54073,65437,35212,45412],
[48231,47498,50751,54438,52483,45749,46482,53434,64253,62408,48700,34564,57730,54295,53081,42645,56470,49043,41516,35479,61962,56805,64471,48806,56148,64688,50255,50303,48066,63253,45081,37202],
[39500,47944,47148,55510,41735,34408,42033,47874,52667,65230,38185,57224,57960,57242,43751,40229,50706,48842,56675,63792,38602,43856,47968,36029,46316,33861,43062,52545,36833,38576,33160,47188],
[34763,52602,34003,38138,52214,37082,46267,41357,53209,46658,37405,38698,48689,58684,65468,53156,37151,42127,52088,60960,40078,54636,55496,63227,39694,39226,42924,46628,51678,47049,57251,39950],
[47060,53229,53324,34857,53402,57558,41164,32890,40952,63714,59742,64510,45578,35856,53314,33442,55935,53065,47134,46908,34203,63156,40093,40012,42585,48353,42197,40052,55471,56463,59090,43410],
[42707,46054,36404,47963,47992,38350,33551,63065,53172,62321,51122,42997,60500,47212,39884,38212,35359,64344,35149,36069,49665,34591,34888,46184,46025,43702,50458,43440,42957,55777,38349,62364],
[45114,54936,52699,38175,56136,37236,42829,36618,60030,45321,63661,42951,62906,57387,39828,65151,46434,48641,48942,46877,64558,62541,54391,42591,63174,60575,57658,43790,61543,61629,43407,39256],
[41315,61872,47514,42455,60909,54071,50796,40555,40903,48007,58870,48415,59960,52920,54333,49750,43868,36540,53277,55958,56116,55847,50861,39109,63323,51663,40245,61514,49405,38631,40884,41575],
[58569,51882,33541,51174,56449,62583,39528,52284,61467,61079,35129,38211,46027,45383,51330,56124,62629,44368,42101,58060,50492,44668,56796,60349,52581,56199,61597,42695,38011,57044,53206,54786],
[47321,62828,42621,47424,33743,62088,49711,61521,57670,43704,57504,64149,48406,61490,35062,47479,49000,53346,34652,64934,60709,42379,55886,38403,32818,49335,34353,38220,55492,53597,43511,65458],
[36970,58823,43553,34488,45459,54107,36469,33268,48487,37195,50544,41167,64538,44132,47555,52965,33728,38671,60378,51219,42761,33794,35819,52469,48730,57793,59596,54642,34866,65462,60317,58309],
[57083,59902,43498,58168,51020,48060,40540,40849,52773,34442,56495,51822,52167,36704,56534,38609,65188,36395,63399,58948,64253,61676,42001,40624,42533,61537,65194,50368,37166,55338,64318,60883],
[38819,55867,35918,36263,55150,61800,40998,51487,60551,55103,64935,37621,44826,60725,37993,59843,54224,55716,36215,37215,41474,33618,63366,43856,50237,58623,37522,50735,44656,38173,50608,53558],
[34900,37778,46423,39412,60092,51148,38323,53310,56808,51387,45360,51882,33763,52239,58031,38137,53084,57559,42893,47903,53781,44518,57306,50958,39625,64130,54299,36323,55685,39663,32956,40248],
[52223,62894,35658,47955,53222,33292,40082,55850,35931,57385,61556,36711,55509,64333,55598,63410,54748,33026,44444,46688,34221,41402,37978,56794,51509,33728,46849,58278,51893,41375,47226,46681],
[52976,34891,47925,43442,59515,34153,59957,55001,55731,51519,58333,49760,55771,35969,37262,34006,51319,33088,58729,43841,61794,46314,60137,36895,64435,37994,60705,48788,37855,61710,47819,42593],
[61352,40709,36161,47983,45760,53141,39843,64766,43219,59102,41023,35212,34127,55560,59265,51853,36176,36365,64261,58669,55196,54380,54787,56392,51638,46506,33332,64068,47810,64586,55243,34259],
[55770,57863,57900,49538,62388,49553,49700,65293,59573,34557,45202,38030,37606,63523,60307,60828,56235,34309,33666,54514,61250,36319,34338,64016,48939,64224,60796,39570,47126,57106,64591,52600],
[44615,45732,55786,36582,42334,49303,60246,33709,48035,45869,51532,55821,50199,54772,44909,50088,38610,45149,39935,64626,41655,57944,53886,40673,36939,33676,40293,50839,61527,60699,51922,44106],
[65377,62356,55220,59201,43963,64568,37991,40846,45998,51359,47140,54987,52330,44097,48724,40654,33688,44820,44244,50178,57279,55648,63665,41583,32832,57810,57402,59925,51002,58322,36333,51125],
[41287,34166,56834,40393,59397,38911,49904,36849,58510,35840,57339,54476,40809,39457,50758,40572,46317,61096,62870,49606,38598,47450,60284,58987,51986,45080,63220,40176,36875,45807,43529,56068],
[48193,48774,33289,42145,49312,47521,39914,51925,39917,48165,47224,63940,49652,57371,39924,48775,41194,48318,48655,46114,53818,42672,52893,63011,62802,44759,46134,47433,54340,36563,41569,60490],
[44350,46084,52253,34130,42256,42059,57465,53689,55189,58968,57975,36629,59833,56538,41512,53160,65479,57214,42956,59310,44119,58409,56941,43799,63205,64438,62116,46552,64986,55088,63289,64992],
[59981,65120,50830,49306,65152,33117,45446,59937,59628,50051,52405,58739,51865,50946,39868,43945,51093,43390,51371,56690,54484,59380,34086,55929,35559,57879,57400,62067,39189,35199,36107,60269],
[53525,51814,63825,54602,63470,51388,41444,42796,64239,39348,32780,34184,40353,46874,46188,56655,49280,44606,53601,52204,51605,61067,38266,53926,50113,62374,55836,35390,58903,55867,62906,35522],
[63603,53936,57720,64444,34320,61868,51306,64322,38351,42819,53198,49825,43151,39952,36588,43407,63775,44609,50383,55258,56905,32794,64407,42274,42412,32771,37915,52745,36204,61105,44689,57883],
[57362,57294,63492,60398,45797,53784,56740,33939,44595,65455,37575,33954,53422,57271,52175,55068,49522,40490,53837,56155,46962,51752,60461,45680,32875,44901,33050,46546,41262,51455,35039,60243],
[41721,44309,60714,49640,38811,50954,35039,61157,55683,37992,64013,38705,41688,61244,55284,39208,34102,44140,42076,44126,39098,37919,47494,38276,39471,57038,39324,45531,33300,32850,63827,61734],
[50638,49699,44478,58948,41101,54366,56564,44044,51920,45510,56763,59125,61576,43849,48245,38731,34149,35902,64669,50273,51014,54000,59856,41923,53353,35259,60315,48177,43783,58570,39743,33108],
[60559,36829,47021,64117,52389,38518,49663,63281,45882,53052,42438,58989,53339,34039,48095,43454,64678,64406,48996,40125,44353,45907,42903,62292,63644,55109,43597,49842,61754,49182,55595,34419],
[43089,62593,42823,39712,41287,63496,48540,37423,33935,65267,40334,41665,42970,38119,36223,45388,41159,38337,48393,60078,57130,48281,32779,33470,63099,38404,58265,40245,59839,56526,63269,65521]]
b = [[199010799],
[211695410],
[210217770],
[187225056],
[190479150],
[194625008],
[185661914],
[211167858],
[206237868],
[212420633],
[201482391],
[194210580],
[213090600],
[195153487],
[184935683],
[200284604],
[201920950],
[207287467],
[212872468],
[198033410],
[205187404],
[192392168],
[196682634],
[221830743],
[207500337],
[208973913],
[206595711],
[203711457],
[185840896],
[199676057],
[212282405],
[197217773]]

# part 1 LWE
def primal_attack1(A, b, m, n, esz):
    L = block_matrix(
        [
            # [matrix.identity(m)*p,matrix.zero(m, n+1)],
            [(matrix(A).T).stack(-vector(b)).change_ring(ZZ), matrix.identity(n + 1)],
        ]
    )
    L = L.LLL()
    e = list(map(abs, L[0][:m]))
    s = list(map(abs, L[0][m:-1]))

    return (s, e)


A = Matrix(ZZ, A)
b = Matrix(ZZ, b)
m, n = A.dimensions()
array_q, e = primal_attack1(A, b, m, n, 128)
q = sum([array_q[i] * 256 ** i for i in range(len(array_q))])
print(q)
print(is_prime(q))


# part 2 solve P
# S = P + R  R = P * Q -> S = P * (Q + E)
Q = prime_to_matrix(q, 16)
E = matrix.identity(16)
S = matrix(S)
P = (Q + E).solve_left(S)
p = matrix_to_prime(P, 16)
print(p)
print(is_prime(p))


# part 3 solve key
nums = 16
c = c ^ nums
n = 2 ** 512
L = block_matrix(ZZ, [
    [1, (Matrix(ZZ,[pow(p,(nums - i),n) for i in range(nums)]).T).stack(vector(ZZ,[-c]))],
    [0,n]
])
ans = list(map(int, L.LLL()[0]))
ans = ans[:-2] + [-ans[-1]]
ans = ans[::-1]
ans = [ans[-1] // abs(ans[-1]) * i for i in ans]

key = b""
for i in range(len(ans[:-1])):
    key += long_to_bytes((c - ans[i]) ^ c)
    c = (c - ans[i]) % n
    c = c * inverse(p,n) % n
key = key[::-1]

flag = "DASCTF{"+sha256(key).hexdigest()+"}"
print(flag)