2023-全国智能驾驶测试赛-车联网安全专项赛-wp-crypto

包含三道crypto题目的题解。

crypto1

题目描述：

crypto1

题目：

from Crypto.Util.number import *
from Crypto.Random import *
from math import gcd
from flag import flag

gift = bytes_to_long(get_random_bytes(128))

e = 7
p = getStrongPrime(1024)
q = getStrongPrime(1024)

tmp = 0
while gcd(e, (p-1)*(q-1)) != 1:
    p = getStrongPrime(1024)
    q = getStrongPrime(1024)

N = p * q

print("N = "+str(N))
print("e = "+str(e))

ciphertext = []
ciphertext.append(pow(gift << 48, e, N))

for i in flag:
    ciphertext.append(pow(pow(i, e, N)+2023*(gift << 48), e, N))

print("ciphertext = "+ str(ciphertext))

题目首先生成了一个128字节的gift，并给出一个加密值：

$c_0 = (gift<<48)^7 \quad (mod \; N)$

然后，对flag的每一个字节mi又进行如下加密，并给出密文：

$c_i = (m_i^7 +2023(gift<<48))^7 \quad (mod \; N)$

显然只要知道gift就可以对密文逐字节爆破，为了求出gift我这里采用groebner，首先把gift<<48看作一个整体，然后令：

$y = gift<<48$

然后我们又知道前几个被加密的flag字符应该是”flag{“，取第一个字符就能造出如下的groebner用法：

PR.<x,y> = PolynomialRing(Zmod(N))
f1 = y^7 - c[0]
f2 = (x^7 + 2023*y)^7 - c[1]
f3 = x - ord("f")
F = [f1,f2,f3]
res = Ideal(F).groebner_basis()

就可以求出y的值，然后对flag逐个爆破即可。

exp：

from Crypto.Util.number import *
from gmpy2 import *

N = 28030238512690531111510905324352711028769445699753206071074774407031349518295509831143882962724716770686092065650727417424394155902220289445197720282229148032418681708758247443216915115346756827153571890808547818879975685654209367532485173383474558982943808515469933268791874369723230872496387952426801105889239421726038202707792418475366902957126686490303887476298738095685810654749088802190128957347808198709306257669747864457057771350717967926804755766522667557179166590745298378520106551612092770314645497872046345140216957631796089002032258793559875097613544314340760025734895215641403266709209531616900387420627
e = 1
c = 

PR.<x,y> = PolynomialRing(Zmod(N))
f1 = y^7 - c[0]
f2 = (x^7 + 2023*y)^7 - c[1]
f3 = x - ord("f")
F = [f1,f2,f3]
res = Ideal(F).groebner_basis()
print(res)

g248 = N - 28030238512690531111510905324352711028769445699753206071074774407031349518295509831143882962724716770686092065650727417424394155902220289445197720282229148032418681708758247443216915115346756827153571890808547818879975685654209367532485173383474558982943808515469933268791874369723230872496387925061950679751229508334737846581849642718943487664911224579796160120937971798591654116334523485101275149393366539625116275024319843218472007925637243314071824464480684660459813510853780314528442564016238041088056042144573478710939561442357078845551274653928291288835456159318263865158121183756404921395911389431593404971475

flag = ""
for j in range(len(c)):
    for i in range(32,127):
        if((i^7 + 2023*g248)^7 % N == c[j]):
            flag += chr(i)
print(flag)

#flag{78bf24db-7e98-4e95-af9d-b9b3ca7ddff4}

然后其实用groebner确实也有点大材小用，其实用相关明文攻击就可以，仍然令：

$x = gift<<48$

那么还是取第一个字符的加密值，就有下面的两个等式：

$c_0 = x^7 \quad (mod \; N)$ $c_1 = (m_1^7 +2023x)^7 \quad (mod \; N)$

显然两个多项式有公共根x，所以求gcd就能得到x。

exp：

from Crypto.Util.number import *
from gmpy2 import *

N = 28030238512690531111510905324352711028769445699753206071074774407031349518295509831143882962724716770686092065650727417424394155902220289445197720282229148032418681708758247443216915115346756827153571890808547818879975685654209367532485173383474558982943808515469933268791874369723230872496387952426801105889239421726038202707792418475366902957126686490303887476298738095685810654749088802190128957347808198709306257669747864457057771350717967926804755766522667557179166590745298378520106551612092770314645497872046345140216957631796089002032258793559875097613544314340760025734895215641403266709209531616900387420627
e = 1
c = 

def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2
    return g1.monic()

PR.<x> = PolynomialRing(Zmod(N))
f1 = x^7 - c[0]
f2 = (ord("f")^7 + 2023*x)^7 - c[1]

g248 = -gcd(f1, f2)[0]
flag = ""
for j in range(len(c)):
    for i in range(32,127):
        if((i^7 + 2023*g248)^7 % N == c[j]):
            flag += chr(i)
print(flag)

#flag{78bf24db-7e98-4e95-af9d-b9b3ca7ddff4}

一种新的密码算法

题目描述：

1	车厂好像在搞一些很新的东西。

题目：

import flag
pk_mt = matrix(ZZ, 6, 6)

pk_mt[0] = [24, -246, 6, 2, -188, -7]
pk_mt[1] = [-28, -243, 6, -1, 2, -9]
pk_mt[2] = [-29, 251, -6, 0, -206, 14]
pk_mt[3] = [-101, 246, -6, -16, 575, 5]
pk_mt[4] = [2, 230, -7, -37, 206, 19]
pk_mt[5] = [425, -734, 30, 52, -3089, -8]

assert hadamard_ratio(pk_mt) < 0.1

plain = []
for i in flag:
    plain.append(ord(i))
    
def encrypt(m, pk):
    r = vector(ZZ, [-1, -0, 1, -1, 2, 3])
    return m * pk + r

def hadamard_ratio(mt):
    d = abs(mt.determinant())
    # print("d", d)
    if mt.rank() != mt.nrows():
        return 0
    dim = mt.rank()
    a = 1
    for i in mt:
        a *= i.norm()
    a = float(a)
    return (d/a)^(1/mt.rank())

i = 0
cipher = []

while i < len(plain):
    cipher.extend(encrypt(vector(ZZ, plain[i:i+6]), pk_mt))
    i += 6

print("cipher ",cipher)

cipher：

cipher  [8107, -15748, 921, -2565, -124146, 1775, 33149, -50478, 2349, 168, -267559, 1183, 35010, -50623, 2407, 2758, -304997, 959, 34378, -71456, 2807, 700, -280622, 498, 29055, -68814, 2638, 1126, -249750, 76, 30408, -47829, 2106, -559, -262141, 1698, 9089, -18788, 974, -1915, -128297, 1542, 31591, -50627, 2338, 410, -276685, 1315, 36859, -66598, 2856, 1250, -330512, 1210, 8776, -11380, 793, -1469, -111219, 1361, 25034, -38643, 1945, 965, -226238, 849, 35515, -39060, 2164, 187, -304231, 2176]

估计预期要用LWE之类的，所以才给了500分。但实际上r向量给定了，并且pk_mt矩阵满秩，所以直接解矩阵方程就可以得到作为flag的唯一解，最大的槽点是解出来的那一坨居然就是flag，甚至不需要包一个”flag{}”，我还以为套了一层古典。

exp：



pk_mt = matrix(ZZ, 6, 6)

pk_mt[0] = [24, -246, 6, 2, -188, -7]
pk_mt[1] = [-28, -243, 6, -1, 2, -9]
pk_mt[2] = [-29, 251, -6, 0, -206, 14]
pk_mt[3] = [-101, 246, -6, -16, 575, 5]
pk_mt[4] = [2, 230, -7, -37, 206, 19]
pk_mt[5] = [425, -734, 30, 52, -3089, -8]

r = vector(ZZ, [-1, -0, 1, -1, 2, 3])
c = [8107, -15748, 921, -2565, -124146, 1775, 33149, -50478, 2349, 168, -267559, 1183, 35010, -50623, 2407, 2758, -304997, 959, 34378, -71456, 2807, 700, -280622, 498, 29055, -68814, 2638, 1126, -249750, 76, 30408, -47829, 2106, -559, -262141, 1698, 9089, -18788, 974, -1915, -128297, 1542, 31591, -50627, 2338, 410, -276685, 1315, 36859, -66598, 2856, 1250, -330512, 1210, 8776, -11380, 793, -1469, -111219, 1361, 25034, -38643, 1945, 965, -226238, 849, 35515, -39060, 2164, 187, -304231, 2176]
c = [c[6*i:6*i+6] for i in range(len(c)//6)]

flag_ = ""
for i in c:
    temp = vector(ZZ,i)
    flag = pk_mt.solve_left(temp-r)
    for j in flag:
        flag_ += chr(j)
print(flag_)

#ftlnd6a13fdg33f00ebe56bbfd88EVtQb9yZOwiRY37hUJcemnxAaof2PlB1D4Cj6X0KgSup

DSA

题目描述：

1	这个签名有什么问题呢

题目：

#!/usr/bin/env python
from secret import flag
from Crypto.Hash import SHA256
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.PublicKey import DSA
message = b"We1c0me to My DSA~"

key = DSA.generate(2048)
g = key.g
p = key.p
q = key.q
x = key.x

y = pow(g,x,p)

def pad(mes):
    return mes+b'\x00'*(16-(len(mes)%16))

def sign(m, sk):
    k = getRandomInteger(210)
    r = pow(g, k, p) % q
    h = int(SHA256.new(m).hexdigest(),16)
    s = (pow(k,-1, q) * (h + sk * r)) % q
    return (r,s)

def verify(m, sig, pk):
    r, s = sig
    if not (0 < r < q) or not (0 < s < q):
        return False
    h = int(SHA256.new(m).hexdigest(),16)
    w = pow(s,-1, q)
    u1 = (w * h) % q
    u2 = (w * r) % q
    v = ( (pow(g, u1, p) * pow(pk, u2, p)) % p ) % q
    
    return v == r

f = open("result.txt",'w')
for i in range(19):
    s = sign(message, x)
    f.write(str(s)+'\n')
    assert(verify(message,s,y))


hash = SHA256.new(long_to_bytes(x)).hexdigest()
key, iv =int(hash[:32],16),int(hash[32:],16)
Cry = AES.new(key=long_to_bytes(key),iv=long_to_bytes(iv),mode=AES.MODE_CBC)
Cip = Cry.encrypt(pad(flag))
print("y = %d"%y)
print("g = %d"%g)
print("p = %d"%p)
print("q = %d"%q)
print(Cip)

# cipher = b'\x95\xf7\xa4\xec\xd9X\x83\x8b\x07\x80\xfe\x13\x1f\xb7\xbc\xdb>D\xd9\x81\xea \xde\xa4\xe2\x1dqbVh\x05\x7fSql\xcb\xbc>\xa7\x97\xc43\xf5\x9b\x007$\xc9'
# y = 10865252628977982718403069421818763814235837963131657427013029838115823600026336301447650009296905255642313560614829551414305461349368310042639287174589738371871741669394848449628044522285747368712081660541770583698167114808057698350786229602723897528207412571691070008591305998686441545245935074526540367888505082808339119240505754542244988927696478960460825964816624418555049437463940360457911924601327318567655697900820622946726145105652407044994786590422434786210702091749354399109010238703002733213717843576865823660052640934212789357807787991082174138275574313009398721223181931145132115294972007801753173408741
# g = 10878177066786201817104669144134368086712364755276065919108711478199751092510166851087043647216283625336810425197547358392780958373012106267072258504608165416441218758023152298309265892294553201074526777067230246439537417511861809178218169256652718105178190531196938563066075049513162080607898394164761142987189540919834231524565226906188464783536188862914987217998962718991606850419980530798524804129840222467271485055647515909053842052939260751746609937602730547514994036006926590348766594949197409442317049666999374778475862558340612771396592183794892824814325810064157857169327255025279120759002239011771662085338
# p = 20384762745031920484342583090217007578889531799944456287350542020280428183544133614297677240387166875661657848083207276915863377102624811969097780972047544492418067487713520174772431897063705267454857523565989648021927658166607167532208110984841922116249828872341082286532560521732253899817674270499471088325222125596455980431820124332946754612276146984417926433629287154223788213445218119081147675710811509544642585633492685907180108137818208905518403931854775047349966947896551628689905814775976869615951137482223176231926274859815993780667146033144320174578733368829000886681042308444467510423523202661128031456749
# q = 16059555483679266293519046196529336235978742561121132269882524559139

标准的DSA签名实现，造的HNP的格子也很标准，如下：

$\left( \begin{matrix} Tq & & & & & & \\ &Tq & & & & & \\ & &... & & & & \\ & & &Tq & & & \\ & & & &Tq & & \\ Tr_1s_1^{-1} &Tr_2s_2^{-1} & &Tr_{i-1}s_{i-1}^{-1} &Tr_is_i^{-1} &1 & \\ Ts_1^{-1}H(m_1) & Ts_2^{-1}H(m_2) & & Ts_{i-1}^{-1}H(m_{i-1}) & Ts_i^{-1}H(m_i) & &KT \\ \end{matrix} \right)$

线性关系是：

$(t_1,t_2,...t_{i-1},t_i,x,1) \left( \begin{matrix} Tq & & & & & & \\ &Tq & & & & & \\ & &... & & & & \\ & & &Tq & & & \\ & & & &Tq & & \\ Tr_1s_1^{-1} &Tr_2s_2^{-1} & &Tr_{i-1}s_{i-1}^{-1} &Tr_is_i^{-1} &1 & \\ Ts_1^{-1}H(m_1) & Ts_2^{-1}H(m_2) & & Ts_{i-1}^{-1}H(m_{i-1}) & Ts_i^{-1}H(m_i) & &KT \\ \end{matrix} \right) = (Tk_1,Tk_2,...Tk_{i-1},Tk_i,x,KT)$

这部分的原理不明白的话可以去la佬博客看，或者也可以看我写的这篇文章中的LLL-Third Blood一题：

2023-0xGame-week4-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

而之所以要乘T，是因为测试一下会发现x大约在221比特的数量级，而k是210比特，因此用最经典的这个不消x的格子的话，要对前面数列均乘上一个2^11的平衡系数。然后题目把界也小卡了一下，导致x并不在规约出的前几行，但是可以在后面的行中找到结果。

如果这样出不了结果的话，就必须消去x后再利用消去后的表达式造格。

exp：

from Crypto.Util.number import *
from tqdm import *
from hashlib import sha256,sha1
from Crypto.Hash import SHA256
from Crypto.Cipher import AES

y = 10865252628977982718403069421818763814235837963131657427013029838115823600026336301447650009296905255642313560614829551414305461349368310042639287174589738371871741669394848449628044522285747368712081660541770583698167114808057698350786229602723897528207412571691070008591305998686441545245935074526540367888505082808339119240505754542244988927696478960460825964816624418555049437463940360457911924601327318567655697900820622946726145105652407044994786590422434786210702091749354399109010238703002733213717843576865823660052640934212789357807787991082174138275574313009398721223181931145132115294972007801753173408741
g = 10878177066786201817104669144134368086712364755276065919108711478199751092510166851087043647216283625336810425197547358392780958373012106267072258504608165416441218758023152298309265892294553201074526777067230246439537417511861809178218169256652718105178190531196938563066075049513162080607898394164761142987189540919834231524565226906188464783536188862914987217998962718991606850419980530798524804129840222467271485055647515909053842052939260751746609937602730547514994036006926590348766594949197409442317049666999374778475862558340612771396592183794892824814325810064157857169327255025279120759002239011771662085338
p = 20384762745031920484342583090217007578889531799944456287350542020280428183544133614297677240387166875661657848083207276915863377102624811969097780972047544492418067487713520174772431897063705267454857523565989648021927658166607167532208110984841922116249828872341082286532560521732253899817674270499471088325222125596455980431820124332946754612276146984417926433629287154223788213445218119081147675710811509544642585633492685907180108137818208905518403931854775047349966947896551628689905814775976869615951137482223176231926274859815993780667146033144320174578733368829000886681042308444467510423523202661128031456749
q = 16059555483679266293519046196529336235978742561121132269882524559139

A = []
B = []
signature = [(2651558219817923218885823963897260420176545960343598667867618915660, 11285816086368751074109807519682248739109554636148737271500083537417),
(15159143958487838460075807722657200246551544153777271489563240754127, 15574028065051178976252376196210445119143972043472176642720172824755),
(7334771057693645276373675422605645698307853033502318431556090316928, 6063664160680809155067032900851770429777185431953964702591332774751),
(928813147850498035541325046699769660854294047481987393214283003280, 2359099476212088034126071969947328704946886362350965235806751873933),
(10756179914730048417034591322991978275926820605297796431931889472674, 2349069276798971208875587309205974111570897310059935267460698787788),
(5395032251012269871339702026358544368409728696829831137765135028710, 14541819319033398596067833169973598645287341185811419362483931783080),
(7707755349429495659081900965148964403842406770852558806614847175682, 7916779517282712595083104629413988726608383004702906141922602933402),
(8098866315261554816535142111632690419097404681325212258803857977062, 7486882204317626188147283131494263880908962953665482516614967081469),
(6585255977570662636366961627967477649303885975481667867002696710900, 7050405537230656640841278656385704509298147260795206532189278359688),
(9733185020571255364851834495254193616397113258442029083450145893092, 14538877554014218885469149222290514169647117667714352125531034512881),
(476382690090526362242110565278819708767706623772259921405889478044, 6629120796071917463067134836627343917592036512490288602623696238384),
(11658423900110864391219329183839322243249235714791059601340802196208, 6309138805333718533163024368819064891035022958432616288605553865275),
(6624480284442737902170118511976620228495533535417309953409286312688, 1585040354840052038493822588306877769807152286806711020282983083323),
(12500492501896641877943474224842595722088756387252325695802412043965, 15791887939377716915772190131671032089627700508416675633562539289043),
(790911772304570751431732853300786781785988499657744022403336570087, 7290481987895296622377849484817569567851785511571138304802515237238),
(14768876072589989591802829850125118348444835711265544481946738102522, 12276139584405885626209147904885272298662855591983062665819395492901),
(2720379820192652433716681505472760118612194441261895908434968343267, 11009896938993997051452180649011069356079650275512031692997316449738),
(10929710272021428918709699423132485135279826072973367875338765673546, 5609221737242798070789409810240458330622610364332606783276719790040),
(6138570840922629831774582509339593535872131768273566238642001258637, 5091543827605292439524069263267534093895949138610994913158756383227),
]
message = b"We1c0me to My DSA~"
for i in range(len(signature)):
    R = signature[i][0]
    S = signature[i][1]
    A.append(inverse(S,q)*R % q)
    B.append(inverse(S,q)*int(SHA256.new(message).hexdigest(),16) % q)

K = 2^210
T = 2^11
length = 19
L = Matrix(ZZ, length+2,length+2)

for i in range(length):
    L[i,i] = q*T
    L[length,i] = A[i]*T
    L[length+1,i] = B[i]*T
L[length,length] = 1
L[-1,-1] = K*T
res = L.LLL()

for t in res:
    try:
        x = abs(int(t[-2]))
        cipher = b'\x95\xf7\xa4\xec\xd9X\x83\x8b\x07\x80\xfe\x13\x1f\xb7\xbc\xdb>D\xd9\x81\xea \xde\xa4\xe2\x1dqbVh\x05\x7fSql\xcb\xbc>\xa7\x97\xc43\xf5\x9b\x007$\xc9'
        hash = SHA256.new(long_to_bytes(x)).hexdigest()
        key, iv =int(hash[:32],16),int(hash[32:],16)
        Cry = AES.new(key=long_to_bytes(key),iv=long_to_bytes(iv),mode=AES.MODE_CBC)
        flag = Cry.decrypt(cipher)
        print(flag)
    except:
        pass

#flag{db32daec-dde9-63e4-0afe-e49a80a745db}