2022第三届网鼎杯青龙组

crypto405

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

利用好flag的格式进行分析。

将前5个grasshopper的产生过程列出公式来，有：

我们已知$k_{14},k_{24},k_{34},k_{44},k_{54}$，就可以推出$k_{23},k_{33},k_{43},k_{53}$，如$k_{23}=k_{24}*invert(k_{14},p)\%p$，同理可以求出$k_{32},k_{42},k_{52}$，继续有$k_{41},k_{51}$，最后求出$k_{50}$，这样一来，我们就求出了$k_{50},k_{51},k_{52},k_{53},k_{54}$，即加密 ‘{‘ 之后的密钥k。

知道密钥k，通过g_i*invert(k0*k1*k2*k3*k4,p)%p求得明文字符，然后重复一遍加密过程可以得到下一轮的密钥k。

p的值可以进行爆破。

代码如下：

from gmpy2 import invert,gcd
#利用flag格式flag{      }
know = b'flag{'
#爆破p
g = [0x2066, 0xa222, 0xcbb1, 0xdbb4, 0xdeb4, 0xb1c5, 0x33a4, 0xc051, 0x3b79, 0x6bf8, 0x2131, 0x2c40, 0x91ba, 0x7b44, 0x5f25, 0x0208, 0x7edb, 0x62b5, 0xcec5, 0x5ab3, 0x3c46, 0xc272, 0x714b, 0x9e0b, 0x48ee, 0x44cc, 0x05a0, 0x3da3, 0x11b1, 0x259f, 0x899d, 0xa130, 0xe58f, 0x23f3, 0x5829, 0x6beb, 0x3681, 0x0054, 0xa189, 0x2765, 0xc63d, 0xbc68]
maxg = max(g)
for p in range(maxg+1, 2**16):
    if gcd(know[0], p) == 1 and gcd(know[1], p) == 1 and gcd(know[2], p) == 1 and gcd(know[3], p) == 1 and gcd(know[4], p) == 1:
        g04 = g[0]

        g14 = g[1]
        if gcd(g04,p) != 1:
            continue
        g13 = g14 * invert(g04, p) % p

        g24 = g[2]
        if gcd(g14,p) != 1 or gcd(g13,p) != 1:
            continue
        g23 = g24 * invert(g14, p) % p
        g22 = g23 * invert(g13, p) % p

        g34 = g[3]
        if gcd(g24,p) != 1 or gcd(g23,p) != 1 or gcd(g22,p) != 1:
            continue
        g33 = g34 * invert(g24, p) % p
        g32 = g33 * invert(g23, p) % p
        g31 = g32 * invert(g22, p) % p

        g44 = g[4]
        if gcd(g34,p) != 1 or gcd(g33,p) != 1 or gcd(g32,p) != 1 or gcd(g31,p) != 1:
            continue
        g43 = g44 * invert(g34, p) % p
        g42 = g43 * invert(g33, p) % p
        g41 = g42 * invert(g32, p) % p
        g40 = g41 * invert(g31, p) % p

        k = [g40, g41, g42, g43, g44]
        flag = ''
        for i in range(5,42):
            _k = k[0]*k[1]*k[2]*k[3]*k[4]
            if gcd(_k, p) != 1:
                break
            alp = g[i] * invert(_k, p) % p
            flag += chr(alp)
            for j in range(5):
                k[j] = alp = alp * k[j] % p

        if flag.endswith('}'):
            print(f'p = {p}')
            print(flag.encode())
#flag{749d39d4-78db-4c55-b4ff-bca873d0f18e}

crypto162

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

print(s)
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

根据题目提示，想到将递归公式转换成矩阵（参考 线性代数求解递推形式数列的通项公式_wdq347的博客-CSDN博客）

#sagemath
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]]
B = [[3],[2],[1]]
B = matrix(B)
s = 0
for i in range(100):
    A = [cof_t[i],[1,0,0],[0,1,0]]
    A = matrix(A)
    C = A^(200000-2)*B
    s += C[0][0]
    
print(str(s)[-2000:-1000])


#python
from hashlib import md5,sha256
from binascii import unhexlify
from Crypto.Cipher import AES
s = '8365222366127410597598169954399481033882921410074214649102398062373189165630613993923060190128768377015697889610969869189338768501949778819512483009804114510646333513147157016729806311717181191848898389803672575716843797638777123435881498143998689577186959772296072473194533856870919617472555638920296793205581043222881816090693269730028856738454951305575065708823347157677411074157254186955326531403441609073128679935513392779152628590893913048822608749327034655805831509883357484164977115164240733564895591006693108254829407400850621646091808483228634435805213269066211974452289769022399418497986464430356041737753404266468993201044272042844144895601296459104534111416147795404108912440106970848660340526207025880755825643455720871621993251258247195860214917957713359490024807893442884343732717743882154397539800059579470352302688717025991780505564794824908605015195865226780305658376169579983423732703921876787723921599023795922881747318116849413935343800909756656082327558085457335537828343666748'
key = unhexlify(md5(s.encode()).hexdigest())
print(key)
check = sha256(key).hexdigest()
verify = '2cf44ec396e3bb9ed0f2f3bdbe4fab6325ae9d9ec3107881308156069452a6d5'
assert check == verify
aes = AES.new(key, AES.MODE_ECB)
cipher = unhexlify('4f12b3a3eadc4146386f4732266f02bd03114a404ba4cb2dabae213ecec451c9d52c70dc3d25154b5af8a304afafed87')
print(aes.decrypt(cipher))