BUUCTF刷题笔记(crypto)

[V&N2020 公开赛]Fast

题目：

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
from Crypto.Util.number import *
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
N = p * q

g, r1, r2 = [getRandomRange(1, N) for _ in range(3)]
g1 = pow(g, r1 * (p-1), N)
g2 = pow(g, r2 * (q-1), N)

def encrypt(m):
    s1, s2 = [getRandomRange(1, N) for _ in range(2)]
    c1 = (m * pow(g1, s1, N)) % N
    c2 = (m * pow(g2, s2, N)) % N
    return (c1, c2)

def decrypt(c1, c2):
    xp = c1 % p
    xq = c2 % q
    # Chinese Remainder Theorem
    m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N
    return m
    
c = encrypt(bytes_to_long(flag))

# N = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283
# g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208
# g2 = 14068322834597276347776814624877614869834816383564391664570268934537693322688875343215293618493363798985047779057952636529313879548457643220996398640913517182122425631198219387988691569709691279442005545716133131472147592456812502863851227108284027033557263611949365667779259585770738623603814004666845554284808166195201470503432803440754207350347128045893594280079379926676477680556845095378093693409219131090910168117334308781843178748431526974047817218228075136005979538773141427004682344298827618677773735288946271346252828348742296301538573408254015281232250841148556304927266143397565889649305095857756884049430
# c1, c2 = (3976514029543484086411168675941075541422870678409709261442618832911574665848843566949154289825219682094719766762966082440586568781997199077781276145091509192208487682443007457513002005089654365915817414921574344557570444253187757317116858499013550050579856269915915792827620535138057468531410166908365364129001407147467636145589396570815405571923148902993581000542566387654639930651683044853608873583911638108204074537952317056718986683846742909366072461130053275195290631718363272923316002049685111871888148244026652658482359335651889139243735138819453744763293112267738369048641158946411500606588429007794613880534, 18524535479582837341745231233387403662294605513261199630593257391163433751052467785080620993007681605662927226603747560698627838567782891522546977611597418150309028806158429831471152782211111046118637630899456903846057977815397285171313888516791822545633820066408276065732715348834255021260666966934592884548856831383262013360819013814149529393178712576141627031723067564594282618223686778534522328204603249125537258294561872667849498796757523663858312311082034700705599706428944071848443463999351872482644584735305157234751806369172212650596041534643187402820399145288902719434158798638116870325144146218568810928344)

分析题目，我们发现给了解密函数，只差p和q，我们的目标就是去求p、q。又注意到g1和g2的生成，指数上分别有(p-1)和(q-1)，很容易想到费马小定理，下面是推导过程：
$g1 = g^{r1*(p-1)} \mod N$
$g1 = g^{r1*(p-1)} \mod p$
费马小定理后得到下式
$g1 = 1 \mod p$
即 g1 = k * p ，所以 gcd(g1-1,N)，就可以得到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
from math import gcd
from Crypto.Util.number import *

N = 
g1 = 
g2 = 
c1, c2 = 

kp = g1-1
kq = g2-1

p = gcd(kp, N)
q = gcd(kq, N)
print(isPrime(p))   # true
print(isPrime(q))   # true

def decrypt(c1, c2):
    xp = c1 % p
    xq = c2 % q
    # Chinese Remainder Theorem
    m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N
    return m
  
m = decrypt(c1, c2)
print(long_to_bytes(m))
# flag{1CE9514E-12AF-49BE-B002-6A3D7E6078FA}

[DASCTF2024八月开学季！新生逐浪，热血向前]EZsignin

题目：

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

p = 174523845247570741054964008585718839267
E = EllipticCurve(GF(p), [0, 486662, 0, 1, 0])
G=E(2247961404505753398791635923994899528, 108711418033303501028455466081133667288)
n=G.order()
Cofactor = E.order() // n
f = 128+1
lambda_ = 100

def retbar(P):
    index = (f + 1) // 2
    return (int(P[0]) % (2 ^ index) + 2 ^ index) % n

def genkey():
    w = randint(1, n - 1)
    W = w * G
    return (w, W)

B_pri_w, B_pub_W = genkey()
print(B_pub_W[0:2])

LS = []
LR = []
BR = []

def Exchange(i):
    A_pri_w, A_pub_W = genkey()
    A_pri_r, A_pub_R = genkey()
    B_pri_r, B_pub_R = genkey()

    sa = (A_pri_r + retbar(A_pub_R) * A_pri_w) % n
    sb = (B_pri_r + retbar(B_pub_R) * B_pri_w) % n

    Ka = Cofactor * (B_pub_R + retbar(B_pub_R) * B_pub_W) * sa
    Kb = Cofactor * (A_pub_R + retbar(A_pub_R) * A_pub_W) * sb

    assert (Ka == Kb)

    leakageS = sb >> lambda_
    leakageR = B_pri_r >> lambda_

    LS.append(leakageS), LR.append(leakageR)
    BR.append(B_pub_R[0:2])

for i in range(10): Exchange(i)
    
print("LS=", LS)
print("LR=", LR)
print("BR=", BR)
H=hashlib.md5()
H.update(long_to_bytes(B_pri_w))
key=H.hexdigest().encode()
aes = AES.new(key,AES.MODE_ECB)
print(aes.encrypt(flag))

从sb = (B_pri_r + retbar(B_pub_R) * B_pri_w) % n式子入手，能容易看出是hnp问题
sbl - Brl = retbar(B_pub_R) * B_pri_w + (brh - sbh)
与e = rx + c格式一致，直接构造格
求出短向量后，会发现一直是错的，我在生成十几组数据尝试后，发现LLL算出来的低32位（也有到33位）是错的，我一开始的思路是直接爆破低33位，试了很久没解出来
查了wp后才知道，是要爆破低36位（我试的样本数还是太少了…），因为低36bit位直接爆破所需时间太长，用了BSGS算法和中间相遇攻击

脚本：

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

B_pub_W=(56142839234500040174315077324489019612, 143186177525574678948140963663687495447)
LS= [12160779, 70634852, 136488679, 93279448, 51769705, 99408367, 94011238, 46255543, 136054320, 126842658]
LR= [117789932, 85602320, 136131278, 85538539, 33115646, 15821127, 122073977, 40205177, 40509142, 121833940]
BR= [(43128875586771925869851532015581155657, 108714366549720544283054523544596695631), (166053844834143846221197595138208659402, 9389299139547698081250285594708260233), (83160043610860066750778648875060399604, 160655466348101518011620435983302563358), (18306927902958362110653472691194540502, 141566997533915037448387258113883793369), (124719869188706449552550102421264489653, 111266021208672789646176095367638959348), (62115794167524204331339724293036031704, 24476842210910012261000793337134128911), (57017187772347635647835418540384524017, 149273114828279413180900590599119201032), (141865913804035015431129030802262884043, 11219445710980991629921733217597739715), (35994282847505215202392163277052083355, 5366425669461724819918825109516828913), (72621299937996657982583201267406651177, 39297013522202608324989011761142875947)]
c = b'\xd7\x8c\xf1Yx\x05W\x8ckq\xfdb\xd5\x81K"\xe7q\x88\x18\xedq\x9f\xcap\x1cTB\xc9)\xe1c\xf4~\x7f\xccwh\xfe\t\xbf\xb2!\xde\x84\xeeO\x0f8\xd1\xac\xbc\x1c \xf0F\x0c\x00\xc9\xa7\x9e\x06\xdan'

p = 174523845247570741054964008585718839267
E = EllipticCurve(GF(p), [0, 486662, 0, 1, 0])
G=E(2247961404505753398791635923994899528, 108711418033303501028455466081133667288)
n=G.order()
Cofactor = E.order() // n
f = 128+1
lambda_ = 100

def retbar(P):
    index = (f + 1) // 2
    return (int(P[0]) % (2 ^ index) + 2 ^ index) % n

C = []
for i in range(len(LS)):
    C.append((LR[i] << lambda_)-(LS[i] << lambda_))
#print(C)

fR = [retbar(i) for i in BR]
#print(fR)

LH = identity_matrix(10) * n
LL = matrix([[1,0],[0,1]])*matrix([fR,C])

#print(fR[0].nbits())# 66
#print(n.nbits())# 128

RL = matrix([[2^100/2^128,0],[0,2^100]])
x = 0 
M = block_matrix([[LH,0],[LL,RL]])
# print(M)
res = M.LLL()
for r in res:
    if r[-1] == 2^100:
        # print(r)
        x = r[-2] * 2 ^ 128 / 2^100 % n
        print(x)# 1178130499626730132053516695382476673

x = x >> 36 << 36
# 爆破低36位
# 可以看成 B_pub_W = x * G + y * G
#          y = high * 2 ^ 18 + low
print(x)
B_pub_W = E(B_pub_W)
y_G = B_pub_W - int(x) * G
maps = {}

for i in range(0,2**18):
    y_G -= G
    maps[y_G[0]] = i + 1

for i in range(0,2**18):
    high = (i << 18) * G
    if high[0] in maps:
#         print(high)
#         print("yes")
        y = (i << 18) + maps[high[0]]
        B_pri_w = x + y
        H=hashlib.md5()
        H.update(long_to_bytes(B_pri_w))
        key=H.hexdigest().encode()
        sys = AES.new(key,AES.MODE_ECB)
        m = sys.decrypt(c)
        print(m)
        break

        
# b'\x01\x02\x03\x00\x00\x00\x00DASCTF{C0ngRatul4tion5_On_y0ur_SuCc3ssfuL_S1gN_1n}\x00\x00\x00\x00\x00\x00\x00'

[NewStarCTF 2023 公开赛道]School of CRC32

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
题目：
import secrets
from secret import flag
import zlib

ROUND = 100
LENGTH = 20

print('Extreme hard CRC32 challenge')
print('ARE YOU READY')

for i in range(ROUND):
    print('ROUND', i, '!'*int(i/75 + 1))
    target = secrets.randbits(32)
    print('Here is my CRC32 value: ', hex(target))
    
    dat = input('Show me some data > ')
    raw = bytes.fromhex(dat)
    
    if zlib.crc32(raw) == target and len(raw) == LENGTH:
        print("GREAT")
    else:
        print("OH NO")
        exit()

print("Congratulation! Here is your flag")
print(flag)

题目返回target，接收我们发送的数据后经过crc32，校验是否通过（该过程循环100次）。因为首次接触crc32算法，先去了解下源码。
crc32算法源码：

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
#include <inttypes.h>
#include <stdio.h>

uint32_t crc32(const char* s){

    uint32_t crc = 0xffffffff;
    size_t i = 0;
    while (s[i] != '\0')
    {
        uint8_t byte = s[i];
        crc = crc ^ byte;
        for (uint8_t j = 8; j > 0; --j)
        {
            crc = (crc >> 1) ^ (0xEDB88320 & (-(crc & 1)));
        }

        i++;
    }
    return crc ^ 0xffffffff;
}

int main(){
    printf("%" PRIu32 "\n", crc32("hello world"));//222957957
    printf("%" PRIx32 "\n", crc32("hello world"));//d4a1185
    return 0;
}

link: [C语言实现CRC32算法 - 完美代码](https://www.perfcode.com/c/examples/crc32)

将c代码转成python

1
2
3
4
5
6
def crc32(binary):
    init = 0xffffffff
    crc = init
    for i in range(len(binary)):
        crc = crc32_table[(crc & 0xff) ^ binary[i]] ^ (crc >> 8)
    return crc ^ init

根据源码，我们可以发现，crc32是种迭代的算法（crc32算法叫循环冗余校验，是一种常用的校验算法）。

我的思路是：题目给的target是32位，也就是4字节，直接用中间相遇攻击，从target逆推爆破每个字节，下面是我的函数

1
2
3
4
5
6
7
8
9
def decode(target):
    res = {}
    for crc_last_low in range(256):
        for j,table_num in enumerate(crc32_table):
            crc_last_high = target ^ table_num
            byte = j ^ crc_last_low
            crc_last = (crc_last_high << 8) + crc_last_low
            res[crc_last] = bytes([byte])
    return res

遇到的问题是，这个函数每次只能爆破一字节，而且只是将所有可能的结果全部存贮在res表中，一开始我试了将decode函数迭代，但并没有成功，在看了大佬的wp(后附)后才有所思路, 下面直接贴大佬的wp（[BUUCTF NewStar 2023] week5 Crypto/pwn_[newstarctf 2023 公开赛道]school of crc32-CSDN博客）。

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
from pwn import *
from zlib import crc32
crc32_table =[
0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940,
0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116,
0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A,
0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818,
0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C,
0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086,
0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4,
0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE,
0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252,
0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60,
0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04,
0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A,
0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E,
0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0,
0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6,
0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D]

#向前爆破两字节
def get_rcrc1(cin):  #cin是经过去0xFFFFFFF的
    res = {}
    for crc_tail in range(256): #last 8 bit
        for i,v in enumerate(crc32_table):
            h = cin^v
            if h>= 0x1000000: continue
            h <<=8  #高24位
            j = crc_tail^i #对应的字符
            #print(chr(j))
            res[h+crc_tail] = bytes([j])
    return res
    
#向后爆破两字节存字典
res_f = {}
for i in range(256):
  for j in range(256):
      res_f[crc32(b'0'*16+bytes([i,j]))^0xffffffff] = bytes([i,j])
      
def get_rcrc2(cin):
    cin = cin^0xffffffff
    res = get_rcrc1(cin) #向前1字节
    for k in res:
        res2 = get_rcrc1(k)
        for v in res2:
            if v in res_f:
                #found
                ret = res_f[v]+res2[v]+res[k]
                return ret                

#a = get_rcrc2(3984772369)
#print(b'0'*16+a)

p = remote('node4.buuoj.cn', 28267)
context.log_level = 'debug'

for i in range(100):
    p.recvuntil(b'Here is my CRC32 value: ')
    hash = int(p.recvline(),16)
    a = get_rcrc2(hash)
    p.sendlineafter(b'Show me some data > ', (b'0'*16+a).hex().encode())
    print('recv:', p.recvline())

print('recv:', p.recvline())
print('recv:', p.recvline())

p.interactive()

反思：在遇到新算法的时候可以多去看看算法的源码实现，并了解了解可能的攻击思路

#crypto #刷题
BUUCTF刷题笔记(crypto)
https://baymax-fools.github.io/2026/03/09/crypto/BUUCTF刷题笔记(crypto)/
Author
Baymax
Posted on
March 9, 2026
Updated on
March 11, 2026
Licensed under