网鼎杯预赛2022密码

CRYPTO

crypto091

13位电话提示含国家代码 86开头

搜到联通是1709开头的

爆破后7位

import hashlib
from itertools import product

h='c22a563acc2a587afbfaaaa6d67bc6e628872b00bd7e998873881f7c6fdc62fc'
a='0123456789'
head='861709'
for i in product(a,repeat=7):
    b=''.join(i)
    t = hashlib.sha256((head + b).encode()).hexdigest()
    if(t==h):
        print(head+b)
1
2
3
4
5
6
7
8
9
10
11

crypto405

p和k都未知

我们可以得到下面的式子 分别为模p之后的前5项

构成方程组

102*k0*k1*k2*k3*k4,
 1192407267456*k0^5*k1^4*k2^3*k3^2*k4,
 1918196473060530916599580974905403195260928*k0^15*k1^10*k2^6*k3^3*k4,
 56112321905504104058889432264614118677688107359359075763851172322711550767834986156510191423865157053692191440896*k0^35*k1^20*k2^10*k3^4*k4,
 53396244662367707127856864007524389027579357260572582679744127850279999404450619312604004485139827409110793046460181646479623909080635340073160838110289140978788817626824929446784411034165296270303004366240008622426141394072733814130556872463873302593536*k0^70*k1^35*k2^15*k3^5*k4

1
2
3
4
5
6

通过爆破p解方程求得k

from Crypto.Util.number import *
from gmpy2 import *
a=[8294, 41506, 52145, 56244, 57012, 45509, 13220, 49233, 15225, 27640, 8497, 11328, 37306, 31556, 24357, 520, 32475, 25269, 52933, 23219, 15430, 49778, 29003, 40459, 18670, 17612, 1440, 15779, 4529, 9631, 35229, 41264, 58767, 9203, 22569, 27627, 13953, 84, 41353, 10085, 50749, 48232]
p=next_prime(max(a))
def get_key(p,a):
    P.<k0,k1,k2,k3,k4>=PolynomialRing(Zmod(p))
    f1=102 * k0 * k1 * k2 * k3 * k4-a[0]
    f2=1192407267456 * k0 ^ 5 * k1 ^ 4 * k2 ^ 3 * k3 ^ 2 * k4-a[1]
    f3=1918196473060530916599580974905403195260928 * k0 ^ 15 * k1 ^ 10 * k2 ^ 6 * k3 ^ 3 * k4-a[2]
    f4=56112321905504104058889432264614118677688107359359075763851172322711550767834986156510191423865157053692191440896 * k0 ^ 35 * k1 ^ 20 * k2 ^ 10 * k3 ^ 4 * k4-a[3]
    f5=53396244662367707127856864007524389027579357260572582679744127850279999404450619312604004485139827409110793046460181646479623909080635340073160838110289140978788817626824929446784411034165296270303004366240008622426141394072733814130556872463873302593536 * k0 ^ 70 * k1 ^ 35 * k2 ^ 15 * k3 ^ 5 * k4-a[4]
    G = Ideal([f1, f2, f3,f4,f5]).groebner_basis()
    k=[]
    for i in G:
       k.append(p-int(str(i).split('+ ')[1]))
    return k
while p<2**16:
    flag = ''
    k = get_key(p, a[:5])
    for i in range(len(a)):
        t = a[i]
        s = 1
        for j in range(5):
            s *= k[j]
        t = t * invert(s, p) % p
        k[0] = t * k[0] % p
        k[1] = k[1] * k[0] % p
        k[2] = k[2] * k[1] % p
        k[3] = k[3] * k[2] % p
        k[4] = k[4] * k[3] % p
        flag += chr(t)
    if flag[-1]=='}':
        print(flag)
        break
    p=next_prime(p)
#flag{749d39d4-78db-4c55-b4ff-bca873d0f18e}
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

crypto162

求数列第200000个数据

之前做到过类似的 矩阵快速幂

不过这个不用推通项
$$f(n)=f(n-1)\ast cof[0]+f(n-2)\ast cof[1]+f(n-3)\ast cof(2)$$
转成矩阵
$$\left|\begin{array}{lcr}cof[0]& cof[1]& cof[2]\\ 1& 0& 0\\ 0& 1& 0\end{array}\right|\ast \left|\begin{array}{l}f(n-1)\\ f(n-2)\\ f(n-3)\end{array}\right|=\left|\begin{array}{l}f(n)\\ f(n-1)\\ f(n-2)\end{array}\right|$$
即为
$${\left|\begin{array}{lcr}cof[0]& cof[1]& cof[2]\\ 1& 0& 0\\ 0& 1& 0\end{array}\right|}^{n-3}\ast \left|\begin{array}{l}f(3)\\ f(2)\\ f(1)\end{array}\right|=\left|\begin{array}{l}f(n)\\ f(n-1)\\ f(n-2)\end{array}\right|$$

from hashlib import md5,sha256

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

def cal1(i,cof):
    m = Matrix(ZZ, [[cof[0], cof[1], cof[2]], [1, 0, 0], [0, 1, 0]])
    v=vector(ZZ,[cal(3,cof),cal(2,cof),cal(1,cof)])
    b=m^(i-3)*v
    return b[0]

s = 0
for i in range(100):
    s+= cal1(200000,cof_t[i])
    
s=str(s)[-2000:-1000]

s='8365222366127410597598169954399481033882921410074214649102398062373189165630613993923060190128768377015697889610969869189338768501949778819512483009804114510646333513147157016729806311717181191848898389803672575716843797638777123435881498143998689577186959772296072473194533856870919617472555638920296793205581043222881816090693269730028856738454951305575065708823347157677411074157254186955326531403441609073128679935513392779152628590893913048822608749327034655805831509883357484164977115164240733564895591006693108254829407400850621646091808483228634435805213269066211974452289769022399418497986464430356041737753404266468993201044272042844144895601296459104534111416147795404108912440106970848660340526207025880755825643455720871621993251258247195860214917957713359490024807893442884343732717743882154397539800059579470352302688717025991780505564794824908605015195865226780305658376169579983423732703921876787723921599023795922881747318116849413935343800909756656082327558085457335537828343666748'


#key = md5(s).hexdigest().decode('hex').encode('hex')
key = long_to_bytes(0x5332394f9af35a87e5bc7b3f44607842)
check = sha256(key).hexdigest()

verify = '2cf44ec396e3bb9ed0f2f3bdbe4fab6325ae9d9ec3107881308156069452a6d5'
assert(check == verify)
aes = AES.new(key,AES.MODE_ECB)
c=0x4f12b3a3eadc4146386f4732266f02bd03114a404ba4cb2dabae213ecec451c9d52c70dc3d25154b5af8a304afafed87
print(aes.decrypt(long_to_bytes(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