20220826-网鼎杯-CryptoSecWriteUp

Posted on Edited on In , Views: Symbols count in article: 17k Reading time ≈ 15 mins.

 

青龙组

crypto091

已知信息

1
2
3
4
5
安全顶会USENIX Security 2021
AirDrop
170号段首批放号的联通号码
c22a563acc2a587afbfaaaa6d67bc6e628872b00bd7e998873881f7c6fdc62fc
flag格式：flag{13位电话号码（纯数字，含国家代码）}

首批放号的联通号码是1709打头，再加上中国的地区码86，爆破一下就是

1
2
3
4
5
6
7
8
9
10
11
from itertools import product
from string import digits
from hashlib import sha256

hash_res = 'c22a563acc2a587afbfaaaa6d67bc6e628872b00bd7e998873881f7c6fdc62fc'

for i in product(digits, repeat=7):
    tmp = sha256(('861709'+''.join(i)).encode()).hexdigest()
    if tmp == hash_res:
        print('861709'+''.join(i))
# 8617091733716

crypto405-grasshopper

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from random import randrange
from grassfield import flag

p = getPrime(16)

k = [randrange(1,p) for i in range(5)]

for i in range(len(flag)):
    grasshopper = flag[i]
    for j in range(5):
        k[j] = grasshopper = grasshopper * k[j] % p
    print('Grasshopper#'+str(i).zfill(2)+':'+hex(grasshopper)[2:].zfill(4))
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
Grasshopper#00:2066
Grasshopper#01:a222
Grasshopper#02:cbb1
Grasshopper#03:dbb4
Grasshopper#04:deb4
Grasshopper#05:b1c5
Grasshopper#06:33a4
Grasshopper#07:c051
Grasshopper#08:3b79
Grasshopper#09:6bf8
Grasshopper#10:2131
Grasshopper#11:2c40
Grasshopper#12:91ba
Grasshopper#13:7b44
Grasshopper#14:5f25
Grasshopper#15:0208
Grasshopper#16:7edb
Grasshopper#17:62b5
Grasshopper#18:cec5
Grasshopper#19:5ab3
Grasshopper#20:3c46
Grasshopper#21:c272
Grasshopper#22:714b
Grasshopper#23:9e0b
Grasshopper#24:48ee
Grasshopper#25:44cc
Grasshopper#26:05a0
Grasshopper#27:3da3
Grasshopper#28:11b1
Grasshopper#29:259f
Grasshopper#30:899d
Grasshopper#31:a130
Grasshopper#32:e58f
Grasshopper#33:23f3
Grasshopper#34:5829
Grasshopper#35:6beb
Grasshopper#36:3681
Grasshopper#37:0054
Grasshopper#38:a189
Grasshopper#39:2765
Grasshopper#40:c63d
Grasshopper#41:bc68

总共42轮，加密流程大致如下，已知每次轮密钥的最后一个数，即每次的密文

image-20220826192452216

关键是目测出前5个明文为flag{，可以列5个方程，如下

1
2
3
4
5
6
7
8
9
10
11
12
flag = b'flag{'
var('x0 x1 x2 x3 x4')
k = [x0, x1, x2, x3, x4]
res = []
for i in range(len(flag)):
    grasshopper = flag[i]
    for j in range(5):
        k[j] = grasshopper = grasshopper * k[j]
    res.append(grasshopper)
print(res)
# (x0, x1, x2, x3, x4)
# [102*x0*x1*x2*x3*x4, 1192407267456*x0^5*x1^4*x2^3*x3^2*x4, 1918196473060530916599580974905403195260928*x0^15*x1^10*x2^6*x3^3*x4, 56112321905504104058889432264614118677688107359359075763851172322711550767834986156510191423865157053692191440896*x0^35*x1^20*x2^10*x3^4*x4, 53396244662367707127856864007524389027579357260572582679744127850279999404450619312604004485139827409110793046460181646479623909080635340073160838110289140978788817626824929446784411034165296270303004366240008622426141394072733814130556872463873302593536*x0^70*x1^35*x2^15*x3^5*x4]

可用Gröbner基解方程，当然$p$不知道需要爆破，之后解密环节也是可以逆回去的，每轮解密都需要用到上一轮产生的轮密钥

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
from Crypto.Util.number import *
from gmpy2 import invert

with open("output.txt", 'r') as fp:
    tmp = fp.readlines()
    code = []
    for i in tmp:
        code.append(int(i[:-1][-4:], 16))


def decrypt(key, modulus):
    pt = ''
    for _ in range(len(code)):
        pre_key = key.copy()
        grasshopper = code[_]
        for j in [3, 2, 1, 0]:
            key[j] = grasshopper = grasshopper * invert(int(pre_key[j + 1]), modulus) % modulus
        key[4] = int(key[4]) * int(key[3]) % modulus
        grasshopper = grasshopper * invert(int(pre_key[0]), modulus) % modulus
        pt += chr(grasshopper)
    if '}' in pt:
        print(pt)


p_list = []
for i in range(65537):
    if isPrime(i) and i.bit_length() == 16 and i > max(code):
        p_list.append(i)

for p in p_list:
    P.<x0, x1, x2, x3, x4> = PolynomialRing(Zmod(p))
    G = [102*x0*x1*x2*x3*x4,
         1192407267456*x0^5*x1^4*x2^3*x3^2*x4,
         1918196473060530916599580974905403195260928*x0^15*x1^10*x2^6*x3^3*x4,
         56112321905504104058889432264614118677688107359359075763851172322711550767834986156510191423865157053692191440896*x0^35*x1^20*x2^10*x3^4*x4,
         53396244662367707127856864007524389027579357260572582679744127850279999404450619312604004485139827409110793046460181646479623909080635340073160838110289140978788817626824929446784411034165296270303004366240008622426141394072733814130556872463873302593536*x0^70*x1^35*x2^15*x3^5*x4]
    for i in range(len(code[:5])):
        G[i] = G[i] - code[i]
    B = Ideal(G).groebner_basis()
    k = []
    for i in range(len(B)):
        k.append(p - B[i] + (p + 1) * eval('x' + str(i)))
    try:
        decrypt(k, p)
    except:
        pass
# flag{749d39d4-78db-4c55-b4ff-bca873d0f18e}

  • 其他解法（由尚师傅提供

    关于解方程，次数有一定规律，可以考虑用消元法。从编程实现角度来说，可以将幂指数和等号右边的数列一个矩阵，即（可以发现是一个斜着的杨辉三角）
    $$
    \begin{bmatrix}
    1 & 1 & 1 & 1 & 1 & | & c_0’\\
    5 & 4 & 3 & 2 & 1 & | & c_1’\\
    15 & 10 & 6 & 3 & 1 & | & c_2’\\
    35 & 20 & 10 & 4 & 1 & | & c_3’\\
    70 & 35 & 15 & 5 & 1 & | & c_4’
    \end{bmatrix}\notag
    $$
    通过初等行变换将左边的方针化成单位矩阵，得到的右边就是方程的解。要注意的是，和线性方程不一样，这里初等行变换对于原等式来说

    • 某一行乘以$a$：原等式两边同时幂上$a$

    • 将某一行减去另外一行的$c$倍：相当于做除法，也就是乘以相应逆元

    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
    from Crypto.Util.number import *
    from gmpy2 import invert

    with open("output.txt", 'r') as fp:
        tmp = fp.readlines()
        code = []
        for i in tmp:
            code.append(int(i[:-1][-4:], 16))

    left = [102,
            1192407267456,
            1918196473060530916599580974905403195260928,
            56112321905504104058889432264614118677688107359359075763851172322711550767834986156510191423865157053692191440896,
            53396244662367707127856864007524389027579357260572582679744127850279999404450619312604004485139827409110793046460181646479623909080635340073160838110289140978788817626824929446784411034165296270303004366240008622426141394072733814130556872463873302593536]
    cof = [[1, 1, 1, 1, 1],
           [5, 4, 3, 2, 1],
           [15, 10, 6, 3, 1],
           [35, 20, 10, 4, 1],
           [70, 35, 15, 5, 1]]

    p = 59441
    for i in range(5):
        cof[i].append((code[i] * invert(left[i], p)) % p)

    for i in range(4):
        tmp = cof[i][5]
        for j in range(i+1, 5):
            mul = cof[j][i]
            for k in range(5):
                cof[j][k] = -cof[j][k] + mul * cof[i][k]
            cof[j][5] = (pow(tmp, mul, p) * invert(cof[j][5], p)) % p
    for i in range(4, 0, -1):
        tmp = cof[i][5]
        for j in range(i-1, -1, -1):
            mul = cof[j][i]
            for k in range(5):
                cof[j][k] -= mul * cof[i][k]
            cof[j][5] = (cof[j][5] * invert(pow(tmp, mul, p), p)) % p
    print(cof)
    # [[1, 0, 0, 0, 0, mpz(28358)], [0, 1, 0, 0, 0, mpz(39970)], [0, 0, 1, 0, 0, mpz(28105)], [0, 0, 0, 1, 0, mpz(42009)], [0, 0, 0, 0, 1, mpz(46211)]]

    和Gröbner解得的是一样的

crypto162-david_homework

考点

  • Fibonacci
  • 矩阵快速幂

题目代码

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
from secret import flag
from hashlib import md5, sha256
from Crypto.Cipher import AES

cof_t = [[353, -1162, 32767], [206, -8021, 42110], [262, -7088, 31882], [388, -6394, 21225], [295, -9469, 44468],
         [749, -3501, 40559], [528, -2690, 10210], [354, -5383, 18437], [491, -8467, 26892], [932, -6984, 20447],
         [731, -6281, 11340], [420, -5392, 44071], [685, -6555, 40938], [408, -8070, 47959], [182, -9857, 49477],
         [593, -3584, 49243], [929, -7410, 31929], [970, -4549, 17160], [141, -2435, 36408], [344, -3814, 18949],
         [291, -7457, 40587], [765, -7011, 32097], [700, -8534, 18013], [267, -2541, 33488], [249, -8934, 12321],
         [589, -9617, 41998], [840, -1166, 22814], [947, -5660, 41003], [206, -7195, 46261], [784, -9270, 28410],
         [338, -3690, 19608], [559, -2078, 44397], [534, -3438, 47830], [515, -2139, 39546], [603, -6460, 49953],
         [234, -6824, 12579], [805, -8793, 36465], [245, -5886, 21077], [190, -7658, 20396], [392, -7053, 19739],
         [609, -5399, 39959], [479, -8172, 45734], [321, -7102, 41224], [720, -4487, 11055], [208, -1897, 15237],
         [890, -4427, 35168], [513, -5106, 45849], [666, -1137, 23725], [755, -6732, 39995], [589, -6421, 43716],
         [866, -3265, 30017], [416, -6540, 34979], [840, -1305, 18242], [731, -6844, 13781], [561, -2728, 10298],
         [863, -5953, 23132], [204, -4208, 27492], [158, -8701, 12720], [802, -4740, 16628], [491, -6874, 29057],
         [531, -4829, 29205], [363, -4775, 41711], [319, -9206, 46164], [317, -9270, 18290], [680, -5136, 12009],
         [880, -2940, 34900], [162, -2587, 49881], [997, -5265, 20890], [485, -9395, 23048], [867, -1652, 18926],
         [691, -7844, 11180], [355, -5990, 13172], [923, -2018, 23110], [214, -4719, 23005], [921, -9528, 29351],
         [349, -7957, 20161], [470, -1889, 46170], [244, -6106, 23879], [419, -5440, 43576], [930, -1123, 29859],
         [151, -5759, 23405], [843, -6770, 36558], [574, -6171, 33778], [772, -1073, 44718], [932, -4037, 40088],
         [848, -5813, 27304], [194, -6016, 39770], [966, -6789, 14217], [219, -6849, 40922], [352, -6046, 18558],
         [794, -8254, 29748], [618, -5887, 15535], [202, -9288, 26590], [611, -4341, 46682], [155, -7909, 16654],
         [935, -5739, 39342], [998, -6538, 24363], [125, -5679, 36725], [507, -7074, 15475], [699, -5836, 47549]]


def cal(i, cof):
    if i < 3:
        return i + 1
    else:
        return cof[2] * cal(i - 3, cof) + cof[1] * cal(i - 2, cof) + cof[0] * cal(i - 1, cof)


s = 0
for i in range(100):
    s += cal(200000, cof_t[i])

s = str(s)[-2000:-1000]
key = md5(s).hexdigest().decode('hex')
check = sha256(key).hexdigest()
verify = '2cf44ec396e3bb9ed0f2f3bdbe4fab6325ae9d9ec3107881308156069452a6d5'
assert (check == verify)
aes = AES.new(key, AES.MODE_ECB)
data = flag + (16 - len(flag) % 16) * "\x00"
print(aes.encrypt(data).encode('hex'))
# 4f12b3a3eadc4146386f4732266f02bd03114a404ba4cb2dabae213ecec451c9d52c70dc3d25154b5af8a304afafed87

类似求斐波那契数列的优化，比较基础

大约跑一个多小时

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
from hashlib import md5,sha256
from Crypto.Cipher import AES
from tqdm import tqdm

cof_t = [[353, -1162, 32767], [206, -8021, 42110], [262, -7088, 31882], [388, -6394, 21225], [295, -9469, 44468], [749, -3501, 40559], [528, -2690, 10210], [354, -5383, 18437], [491, -8467, 26892], [932, -6984, 20447], [731, -6281, 11340], [420, -5392, 44071], [685, -6555, 40938], [408, -8070, 47959], [182, -9857, 49477], [593, -3584, 49243], [929, -7410, 31929], [970, -4549, 17160], [141, -2435, 36408], [344, -3814, 18949], [291, -7457, 40587], [765, -7011, 32097], [700, -8534, 18013], [267, -2541, 33488], [249, -8934, 12321], [589, -9617, 41998], [840, -1166, 22814], [947, -5660, 41003], [206, -7195, 46261], [784, -9270, 28410], [338, -3690, 19608], [559, -2078, 44397], [534, -3438, 47830], [515, -2139, 39546], [603, -6460, 49953], [234, -6824, 12579], [805, -8793, 36465], [245, -5886, 21077], [190, -7658, 20396], [392, -7053, 19739], [609, -5399, 39959], [479, -8172, 45734], [321, -7102, 41224], [720, -4487, 11055], [208, -1897, 15237], [890, -4427, 35168], [513, -5106, 45849], [666, -1137, 23725], [755, -6732, 39995], [589, -6421, 43716], [866, -3265, 30017], [416, -6540, 34979], [840, -1305, 18242], [731, -6844, 13781], [561, -2728, 10298], [863, -5953, 23132], [204, -4208, 27492], [158, -8701, 12720], [802, -4740, 16628], [491, -6874, 29057], [531, -4829, 29205], [363, -4775, 41711], [319, -9206, 46164], [317, -9270, 18290], [680, -5136, 12009], [880, -2940, 34900], [162, -2587, 49881], [997, -5265, 20890], [485, -9395, 23048], [867, -1652, 18926], [691, -7844, 11180], [355, -5990, 13172], [923, -2018, 23110], [214, -4719, 23005], [921, -9528, 29351], [349, -7957, 20161], [470, -1889, 46170], [244, -6106, 23879], [419, -5440, 43576], [930, -1123, 29859], [151, -5759, 23405], [843, -6770, 36558], [574, -6171, 33778], [772, -1073, 44718], [932, -4037, 40088], [848, -5813, 27304], [194, -6016, 39770], [966, -6789, 14217], [219, -6849, 40922], [352, -6046, 18558], [794, -8254, 29748], [618, -5887, 15535], [202, -9288, 26590], [611, -4341, 46682], [155, -7909, 16654], [935, -5739, 39342], [998, -6538, 24363], [125, -5679, 36725], [507, -7074, 15475], [699, -5836, 47549]]


def cal(i, cof):
    if i < 3:
        return i+1
    else:
        return cof[2]*cal(i-3,cof)+cof[1]*cal(i-2,cof)+cof[0]*cal(i-1,cof)


s = 0
for cof in tqdm(cof_t):
    a = b = c = 0
    for i in range(200001):
        if i == 0:
            a = i + 1
        elif i == 1:
            b = i + 1
        elif i == 2:
            c = i + 1
        else:
            tmp = c
            c = cof[2] * a + cof[1] * b + cof[0] * c
            a = b
            b = tmp
    s += c

s = str(s)[-2000:-1000]
print(s)
# 8365222366127410597598169954399481033882921410074214649102398062373189165630613993923060190128768377015697889610969869189338768501949778819512483009804114510646333513147157016729806311717181191848898389803672575716843797638777123435881498143998689577186959772296072473194533856870919617472555638920296793205581043222881816090693269730028856738454951305575065708823347157677411074157254186955326531403441609073128679935513392779152628590893913048822608749327034655805831509883357484164977115164240733564895591006693108254829407400850621646091808483228634435805213269066211974452289769022399418497986464430356041737753404266468993201044272042844144895601296459104534111416147795404108912440106970848660340526207025880755825643455720871621993251258247195860214917957713359490024807893442884343732717743882154397539800059579470352302688717025991780505564794824908605015195865226780305658376169579983423732703921876787723921599023795922881747318116849413935343800909756656082327558085457335537828343666748
key = bytes.fromhex(md5(s.encode()).hexdigest())
check = sha256(key).hexdigest()
verify = '2cf44ec396e3bb9ed0f2f3bdbe4fab6325ae9d9ec3107881308156069452a6d5'
assert(check == verify)
cipher = '4f12b3a3eadc4146386f4732266f02bd03114a404ba4cb2dabae213ecec451c9d52c70dc3d25154b5af8a304afafed87'
aes = AES.new(key, AES.MODE_ECB)
print(aes.decrypt(bytes.fromhex(cipher)))
# b'flag{519427b3-d104-4c34-a29d-5a7c128031ff}\x00\x00\x00\x00\x00\x00'

  • 更简便的思路（由尚师傅提供

    因为通式可以写成$f(n) = a\times f(n-1)+b\times f(n-2)+c\times f(n-3)$的形式，对应矩阵相乘
    $$
    \begin{bmatrix}
    a & b & c\\
    1 & 0 & 0\\
    0 & 1 & 0
    \end{bmatrix}\times
    \begin{bmatrix}
    f(n-1)\\
    f(n-2)\\
    f(n-3)
    \end{bmatrix}=
    \begin{bmatrix}
    f(n)\\
    f(n-1)\\
    f(n-2)
    \end{bmatrix}\notag
    $$
    最终
    $$
    \begin{bmatrix}
    f(n)\\
    f(n-1)\\
    f(n-2)
    \end{bmatrix}=
    {\begin{bmatrix}
    a & b & c\\
    1 & 0 & 0\\
    0 & 1 & 0
    \end{bmatrix}}^{n-5}\times
    \begin{bmatrix}
    f(5)\\
    f(4)\\
    f(3)
    \end{bmatrix}\notag
    $$
    仔细观察可以发现和Fibonacci的优化算法异曲同工，但是可以用矩阵快速幂的算法

    比如[353, -1162, 32767]，用sage来求解就是

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def cal(i, cof):
        if i < 3:
            return i + 1
        else:
            return cof[2] * cal(i - 3, cof) + cof[1] * cal(i - 2, cof) + cof[0] * cal(i - 1, cof)

      
    cof = [353, -1162, 32767]
    a = [[cof[2],cof[1],cof[0]],[1,0,0],[0,1,0]]
    b = [cal(5, cof),cal(4, cof),cal(3, cof)]
    a, b = map(Matrix, [a, b])
    f200000 = Matrix(a) ^ (200000 - 5) * vector(b)
    f200000 = f200000[0]

矩阵快速幂

和模运算时的快速幂类似，基本思想就是

1
2
3
4
5
while(n):
    if n & 1:
        ans = ans * A
    A = A * A
    n >>= 1

朱雀组

ezenc（not solve）

题目代码

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

def gen():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    a = randint(0, n-1)
    b = randint(0, n-1)
    c = randint(0, n-1)
    start_point = (randint(0, n-1), randint(0, n-1))
    PR.<x, y> = PolynomialRing(Zmod(n))
    f = a*x^3 + b*y^2 + c*x
    return f, start_point, (a, b, c, n)

def xor(a, b):
    return int(a) ^^ int(b)

def encrypt(m, start_point, f):
    cipher = []
    sx, sy = start_point
    blocks = [bytes_to_long(m[i:i+16]) for i in range(0, len(m), 16)]
    for i in range(len(blocks) // 2):
        cipher.append(xor(blocks[2*i], sx))
        cipher.append(xor(blocks[2*i+1], sy))
        sx = f(sx, sy)
        sy = xor(sx, sy)
    return cipher

pad_m = flag + os.urandom(64 - 42)#42+22
assert len(pad_m) == 64
f, start_point, params = gen()
cipher = encrypt(pad_m, start_point, f)
print(f'a, b, c, n = {params}')
print(f'cipher = {cipher}')

'''
a, b, c, n = (58493180206280995166949088630862935121692293113070761942379997624567255888151607244256631923177650490930782760990090787682410201009127952217892502070139819981674291217076800514444243638820470025558188967481739832439810276776378787519964303141648963489444067852648391943163109731120778425494909150889411093960, 46172366336089831310960755143578889376532743663172860361755571772045221100008959424451660130568125362348845700703892929931199132712766234925485835764012353070376629613618993293431459323400914977271705861801910493602818994744426491141527497337817119369641045625744704350707375573550772144564620665684928683402, 19189488576034606278863899117074027036173823269039652400309540590815668931372254062253619566958050219640223372310069399693298464732429911410276551240655016204531187058049695870661744117916899532025943121779633685407125808798681987042989575590207041108021793502768068139096739214548284546156443090523266237695, 96858276722767871484147893298651762032220583566011065141277240237378043309615589180222737624804751395689172090800725457062314655780262177626957611384295523383685398453637801374491348384377908010627404394154126710614350975830951712470907093477634347204814343074898039290917090444878133088626570804871873226699)
cipher = [36633609478519497861136475666666131938858956077548606395105606184820738572062990745374972833075141354801792520683058064142161512397434518688745037696555179845418569596852487897422589925520259409135734075737024343011330760896819422786398519488763062105596840549716630252206405469813121898101567839019850931844, 23524585966298765544236980271623612593914558804805054533399955152347568782225411158142631088979145146563310031427110338406256923631563043072551994688620473377870043252294838164270350992774986366442886166068139475337886271853648397473459702043901905284762977136945862820101477925867338639978375737328118999227, 1102439887180135561431657997817460680692014258509945181865836151269639246079406495910998861884434840665151281896830481714227581936868745376175012076116764252587571117909341730821665831730321507457962006041189062099218524397545218232451004021434505804369376939264252846742417597925366709199906574958075895812, 22520353865056818982168277535613639358274312179108677256321891481092108780327375090493515197999741993613989586892673712445716632517839643096522368192894635959109661974340061388404500207534834738399942080529805365093747750038205217617083091097812414303621023181843233639691256800929555956870277339243953270044]

'''

一个块加密，加密流程很简单。用CopperSmith求解三元小根方程失败，应该是模数不够大，将参数pq换成1024bits的就可以。