糖醋小鸡块的blog
0%

2024-DASCTF十月挑战赛-wp-crypto

发表于 更新于 分类于 Valine：

记录一下DASCTF系列赛。

ez_RSA

题目描述：

1
一道简单的RSA

题目：

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

num1 = getPrime(512)
num2 = getPrime(512)
while num1<num2 :
    num2 = getPrime(512)
ring = RealField(1050)
num3 = ring(num1) /ring(num2)
print("num3=",num3)
p = getPrime(512)
q = getPrime(512)
n=p*q
e=65537
m = bytes_to_long(flag)
c=pow(m,e,n)

print("n=",n)
print("c=",c)

n2 = getPrime(512) * getPrime(512)
e1 = randint(1000,2000)
e2 = randint(1000,2000)
c1 = pow(p+num1,e1,n2)
c2 = pow(p+num2,e2,n2)

q1 = getPrime(512)
leak1 = pow(q+q1,2024,n)
leak2 = pow(q1+2024,q,n)


print("n2=",n2)
print("e1=",e1)
print("e2=",e2)
print("c1=",c1)
print("c2=",c2)
print("leak1=",leak1)
print("leak2=",leak2)



"""
num3= 1.36557212221826657073387899060669771982679822943621690677450888408226656788387273887547841291114809989272635809810564202247340711087479554863446719786359395466961253205133910506682801159622545780721946115442033391600881399634390008053822158098121985270501317972263356522400827768601773721146954464269212959784543085
n= 85105083975491693151454182116844944807066048677068373328227644321539783064315677834754866742549592569194223084173286381150626593510265361114796714226058887906219454795525438819082646860141163940340082006344850825956811992304447978369108606993344902286569100146695092703383844402883938506877787042873586279543
c= 8090472119640930864901421058741085326954308673260202542020919764880488559370287585797498390920330336595858609617432370825503480936376306766495089200286004922821787548265246289552343468177624634434613746605553770994437785042510225956023382347023663125411103947669109085411939772215657220674436476279268458980
n2= 101642316595332652021348165259853423287787139517550249986161819826180514401858258316466101056877182367161299111697465439636861942636526396547011727147471566130633614685728563576613692851860684686033186826342178072882901576159305747639645374751566751967096281105148714033096611618024355982220235949274576036321
e1= 1630
e2= 1866
c1= 8857135083997055103287497833179378469532619748945804429057682575070405217145941944821968708809563240261403711644389684947851643865895254406194464015430673347359589677809515117412321862622147634752091324365628790687343748145339949310696116239361890881096088375070083053010564890401663562726144984405628773323
c2= 44531030636557714647477473185500183066851251320453194953972504422367649302810396344051696851757189817391648356459225688318373454949578822468293099948132700460437006478679492801335689493431764882835346904225119630026545592437198370606462285405519745361570058335573353886454277790277663038008240372746639859253
leak1= 82301473255013183706458389946960254392188270550712533886416705365418418731488346328643954589202172816597173052792573628245245948345810581701878535280775967863966009605872386693838526935762655380705962833467046779524956212498594045378770790026387120339093736625186401934354434702063802537686761251873173518029
leak2= 43580171648136008789232340619597144591536098696024883687397347933098380327258730482377138309020375265135558484586783368757872008322883985094403855691297725907800406097129735499961231236473313141257901326737291586051506797429883866846199683028143924054925109557329949641367848264351523500925115860458645738192

"""

题目比较套但也很常规，一步一步来。

part1

给出$R = RealField(1050)$上的：

其中num1、num2都是512bit的素数，连分数展开一下并做check就有num1和num2了。

part2

生成两个512bit的素数乘积n2，并给出：

而这个式子里除了p我们什么都有，并且e也不大，所以做个gcd就有p了。得到p之后自然也能求出q，所以其实已经完全可以求解flag。

part3

这里把第三部分也做一做，第三部分先生成一个512bit的随机素数q，并给出了：

显然在模q下有：

所以有：

exp

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

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)


num3= 1.36557212221826657073387899060669771982679822943621690677450888408226656788387273887547841291114809989272635809810564202247340711087479554863446719786359395466961253205133910506682801159622545780721946115442033391600881399634390008053822158098121985270501317972263356522400827768601773721146954464269212959784543085
n= 85105083975491693151454182116844944807066048677068373328227644321539783064315677834754866742549592569194223084173286381150626593510265361114796714226058887906219454795525438819082646860141163940340082006344850825956811992304447978369108606993344902286569100146695092703383844402883938506877787042873586279543
c= 8090472119640930864901421058741085326954308673260202542020919764880488559370287585797498390920330336595858609617432370825503480936376306766495089200286004922821787548265246289552343468177624634434613746605553770994437785042510225956023382347023663125411103947669109085411939772215657220674436476279268458980
n2= 101642316595332652021348165259853423287787139517550249986161819826180514401858258316466101056877182367161299111697465439636861942636526396547011727147471566130633614685728563576613692851860684686033186826342178072882901576159305747639645374751566751967096281105148714033096611618024355982220235949274576036321
e1= 1630
e2= 1866
c1= 8857135083997055103287497833179378469532619748945804429057682575070405217145941944821968708809563240261403711644389684947851643865895254406194464015430673347359589677809515117412321862622147634752091324365628790687343748145339949310696116239361890881096088375070083053010564890401663562726144984405628773323
c2= 44531030636557714647477473185500183066851251320453194953972504422367649302810396344051696851757189817391648356459225688318373454949578822468293099948132700460437006478679492801335689493431764882835346904225119630026545592437198370606462285405519745361570058335573353886454277790277663038008240372746639859253
leak1= 82301473255013183706458389946960254392188270550712533886416705365418418731488346328643954589202172816597173052792573628245245948345810581701878535280775967863966009605872386693838526935762655380705962833467046779524956212498594045378770790026387120339093736625186401934354434702063802537686761251873173518029
leak2= 43580171648136008789232340619597144591536098696024883687397347933098380327258730482377138309020375265135558484586783368757872008322883985094403855691297725907800406097129735499961231236473313141257901326737291586051506797429883866846199683028143924054925109557329949641367848264351523500925115860458645738192


################################################# 1
t = continued_fraction(num3)
for i in range(1000):
    num1 = t.numerator(i)
    if(isPrime(num1) and len(bin(num1)[2:]) == 512):
        num2 = t.denominator(i)
        break

################################################# 2
PR.<x> = PolynomialRing(Zmod(n2))
f1 = (x + num1)^e1 - c1
f2 = (x + num2)^e2 - c2
res = GCD(f1,f2)
P = -res.monic().coefficients()[0]

Q = n // P
print(long_to_bytes(int(pow(c,inverse(65537,(P-1)*(Q-1)),P*Q))))


################################################# 3
q = gcd(leak1 - (leak2 - 2024)^2024, n)


#DASCTF{c0ngr4tu1ati0n$_0n_$ucccc3$$1ng_1n!}



easy_xor

题目描述：

1
xor is an interesting operation.

题目：

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

def encrypt(msg):
    p = getPrime(256)
    n = 2^512
    x = msg[0] << 7
    for i in msg:
        x = int(x*p % n)
        x ^^= i
    return x ^^ len(msg) ,p


def prime_to_matrix(p , n):
    
    binary_rep = bin(p)[2:].zfill(n^2)
    matrix = Matrix(GF(2), n, n, [int(b) for b in binary_rep])
    
    return matrix

def matrix_to_prime(matrix, n):

    binary_rep = ''.join(str(matrix[i, j]) for i in range(n) for j in range(n))
    p = int(binary_rep, 2)
    
    return p

key = os.urandom(16)
key_list = [i for i in key]
c,p = encrypt(key_list)

P = prime_to_matrix(p,16)

q = getPrime(256) 
Q = prime_to_matrix(q,16)

R = P*Q
r = matrix_to_prime(R,16)

s = p^^r
S = prime_to_matrix(s,16)

array_q = []
t = q
while t > 0:
    array_q.append(t%256)
    t = t//256

m = len(array_q)
A = matrix(ZZ,m,m)
for i in  range(m):
    for j in range(m):
        A[i,j] = randint(65537//2,65537)

x = matrix(ZZ,[array_q])
x = x.T
e = matrix(ZZ,m,1)
for i in range(m):
    e[i,0] = randint(1,256)
b = A*x + e  

with open("out.txt","w") as f:
    f.write(f"c = {c}\n")
    f.write(f"S = {S}\n")
    f.write(f"A = {A}\n")
    f.write(f"b = {b}\n")
    
flag = "CBCTF{"+sha256(key).hexdigest()+"}"

仍然比较套，流程有三个主要步骤：

  • 先生成一个16字节的随机key，并按如下方式对key进行加密：

    其中p是个256bit的素数，暂时没有给出，仅仅给出了c

  • 随机生成256bit的素数q，并按比特生成一个16x16的矩阵，记为Q，同时也记p的矩阵为P，计算：

    将R转为256bit的数字r，然后计算：

    将s对应的矩阵记为S，给出S

  • 最后一步是将q的256进制表示成一个向量x，然后生成随机矩阵A和误差向量e，计算：

    并给出b、A

从后往前，首先最后一步显然是ZZ上的LWE样本，所以可以得到向量x，得到向量x也就得到了q，自然也就得到了对应的矩阵Q。

那么对于第二步，我们有下面两个式子：

其实第二个式子在模2下也可以写成矩阵形式：

我们有Q和S，所以联立两个式子可以得到：

所以解矩阵方程就可以得到P：

模2下加减号其实没差

得到P之后自然有p，那么最后一步就是根据p、c以及如下关系式计算key：

这在国赛其实有出现过，由于异或其实也就是加一个-256到256的数字，所以上式其实就是：

可以看出这是个关于p的迭代多项式，所以展开一下就是：

多项式系数都很小，所以LLL一下就能得到全部系数，之后从后往前两两做差并异或，就可以把系数转化回key了。

exp：

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
from Crypto.Util.number import *
from hashlib import *

def prime_to_matrix(p , n):
    
    binary_rep = bin(p)[2:].zfill(n^2)
    matrix = Matrix(GF(2), n, n, [int(b) for b in binary_rep])
    
    return matrix

def matrix_to_prime(matrix, n):

    binary_rep = ''.join(str(matrix[i, j]) for i in range(n) for j in range(n))
    p = int(binary_rep, 2)
    
    return p

c = 3235165504936419327001182958857604252407894106191511594689199770239529482330201776634335054024549532136197669522057846845936856432300465191006002492337710
S = [[0,0,0,1,1,0,0,0,1,1,0,0,1,0,1,0],
[1,1,0,1,1,1,0,0,1,0,1,0,0,0,0,0],
[1,0,1,0,0,1,0,1,1,0,1,0,1,0,0,1],
[0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,1],
[1,0,0,1,1,1,0,1,1,0,0,0,1,1,0,1],
[0,1,0,1,0,0,1,0,0,1,0,1,0,0,1,1],
[0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,0],
[0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,0],
[0,1,1,0,1,1,1,0,0,1,1,0,0,1,0,1],
[0,1,1,0,0,1,0,1,0,0,0,1,0,0,0,1],
[0,1,0,0,0,0,0,1,1,1,1,0,0,1,1,1],
[0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1],
[1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0],
[0,1,0,0,1,1,0,0,0,1,0,1,1,0,1,0],
[0,0,1,0,1,1,1,1,0,1,1,1,0,1,1,0],
[1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0]]
A = [[58759,40201,39541,50266,35606,44877,56746,51320,40748,58265,48198,36126,48722,38757,34645,49875,39713,39344,34596,44689,40300,55926,43000,56106,63327,47482,39178,49257,45418,48650,50427,41214],
[37223,34740,55875,61596,60851,42409,41726,54223,37354,44483,35507,64442,65181,65016,52834,59838,45696,50951,64689,55931,44398,62595,54959,40901,53153,37642,49294,44606,54073,65437,35212,45412],
[48231,47498,50751,54438,52483,45749,46482,53434,64253,62408,48700,34564,57730,54295,53081,42645,56470,49043,41516,35479,61962,56805,64471,48806,56148,64688,50255,50303,48066,63253,45081,37202],
[39500,47944,47148,55510,41735,34408,42033,47874,52667,65230,38185,57224,57960,57242,43751,40229,50706,48842,56675,63792,38602,43856,47968,36029,46316,33861,43062,52545,36833,38576,33160,47188],
[34763,52602,34003,38138,52214,37082,46267,41357,53209,46658,37405,38698,48689,58684,65468,53156,37151,42127,52088,60960,40078,54636,55496,63227,39694,39226,42924,46628,51678,47049,57251,39950],
[47060,53229,53324,34857,53402,57558,41164,32890,40952,63714,59742,64510,45578,35856,53314,33442,55935,53065,47134,46908,34203,63156,40093,40012,42585,48353,42197,40052,55471,56463,59090,43410],
[42707,46054,36404,47963,47992,38350,33551,63065,53172,62321,51122,42997,60500,47212,39884,38212,35359,64344,35149,36069,49665,34591,34888,46184,46025,43702,50458,43440,42957,55777,38349,62364],
[45114,54936,52699,38175,56136,37236,42829,36618,60030,45321,63661,42951,62906,57387,39828,65151,46434,48641,48942,46877,64558,62541,54391,42591,63174,60575,57658,43790,61543,61629,43407,39256],
[41315,61872,47514,42455,60909,54071,50796,40555,40903,48007,58870,48415,59960,52920,54333,49750,43868,36540,53277,55958,56116,55847,50861,39109,63323,51663,40245,61514,49405,38631,40884,41575],
[58569,51882,33541,51174,56449,62583,39528,52284,61467,61079,35129,38211,46027,45383,51330,56124,62629,44368,42101,58060,50492,44668,56796,60349,52581,56199,61597,42695,38011,57044,53206,54786],
[47321,62828,42621,47424,33743,62088,49711,61521,57670,43704,57504,64149,48406,61490,35062,47479,49000,53346,34652,64934,60709,42379,55886,38403,32818,49335,34353,38220,55492,53597,43511,65458],
[36970,58823,43553,34488,45459,54107,36469,33268,48487,37195,50544,41167,64538,44132,47555,52965,33728,38671,60378,51219,42761,33794,35819,52469,48730,57793,59596,54642,34866,65462,60317,58309],
[57083,59902,43498,58168,51020,48060,40540,40849,52773,34442,56495,51822,52167,36704,56534,38609,65188,36395,63399,58948,64253,61676,42001,40624,42533,61537,65194,50368,37166,55338,64318,60883],
[38819,55867,35918,36263,55150,61800,40998,51487,60551,55103,64935,37621,44826,60725,37993,59843,54224,55716,36215,37215,41474,33618,63366,43856,50237,58623,37522,50735,44656,38173,50608,53558],
[34900,37778,46423,39412,60092,51148,38323,53310,56808,51387,45360,51882,33763,52239,58031,38137,53084,57559,42893,47903,53781,44518,57306,50958,39625,64130,54299,36323,55685,39663,32956,40248],
[52223,62894,35658,47955,53222,33292,40082,55850,35931,57385,61556,36711,55509,64333,55598,63410,54748,33026,44444,46688,34221,41402,37978,56794,51509,33728,46849,58278,51893,41375,47226,46681],
[52976,34891,47925,43442,59515,34153,59957,55001,55731,51519,58333,49760,55771,35969,37262,34006,51319,33088,58729,43841,61794,46314,60137,36895,64435,37994,60705,48788,37855,61710,47819,42593],
[61352,40709,36161,47983,45760,53141,39843,64766,43219,59102,41023,35212,34127,55560,59265,51853,36176,36365,64261,58669,55196,54380,54787,56392,51638,46506,33332,64068,47810,64586,55243,34259],
[55770,57863,57900,49538,62388,49553,49700,65293,59573,34557,45202,38030,37606,63523,60307,60828,56235,34309,33666,54514,61250,36319,34338,64016,48939,64224,60796,39570,47126,57106,64591,52600],
[44615,45732,55786,36582,42334,49303,60246,33709,48035,45869,51532,55821,50199,54772,44909,50088,38610,45149,39935,64626,41655,57944,53886,40673,36939,33676,40293,50839,61527,60699,51922,44106],
[65377,62356,55220,59201,43963,64568,37991,40846,45998,51359,47140,54987,52330,44097,48724,40654,33688,44820,44244,50178,57279,55648,63665,41583,32832,57810,57402,59925,51002,58322,36333,51125],
[41287,34166,56834,40393,59397,38911,49904,36849,58510,35840,57339,54476,40809,39457,50758,40572,46317,61096,62870,49606,38598,47450,60284,58987,51986,45080,63220,40176,36875,45807,43529,56068],
[48193,48774,33289,42145,49312,47521,39914,51925,39917,48165,47224,63940,49652,57371,39924,48775,41194,48318,48655,46114,53818,42672,52893,63011,62802,44759,46134,47433,54340,36563,41569,60490],
[44350,46084,52253,34130,42256,42059,57465,53689,55189,58968,57975,36629,59833,56538,41512,53160,65479,57214,42956,59310,44119,58409,56941,43799,63205,64438,62116,46552,64986,55088,63289,64992],
[59981,65120,50830,49306,65152,33117,45446,59937,59628,50051,52405,58739,51865,50946,39868,43945,51093,43390,51371,56690,54484,59380,34086,55929,35559,57879,57400,62067,39189,35199,36107,60269],
[53525,51814,63825,54602,63470,51388,41444,42796,64239,39348,32780,34184,40353,46874,46188,56655,49280,44606,53601,52204,51605,61067,38266,53926,50113,62374,55836,35390,58903,55867,62906,35522],
[63603,53936,57720,64444,34320,61868,51306,64322,38351,42819,53198,49825,43151,39952,36588,43407,63775,44609,50383,55258,56905,32794,64407,42274,42412,32771,37915,52745,36204,61105,44689,57883],
[57362,57294,63492,60398,45797,53784,56740,33939,44595,65455,37575,33954,53422,57271,52175,55068,49522,40490,53837,56155,46962,51752,60461,45680,32875,44901,33050,46546,41262,51455,35039,60243],
[41721,44309,60714,49640,38811,50954,35039,61157,55683,37992,64013,38705,41688,61244,55284,39208,34102,44140,42076,44126,39098,37919,47494,38276,39471,57038,39324,45531,33300,32850,63827,61734],
[50638,49699,44478,58948,41101,54366,56564,44044,51920,45510,56763,59125,61576,43849,48245,38731,34149,35902,64669,50273,51014,54000,59856,41923,53353,35259,60315,48177,43783,58570,39743,33108],
[60559,36829,47021,64117,52389,38518,49663,63281,45882,53052,42438,58989,53339,34039,48095,43454,64678,64406,48996,40125,44353,45907,42903,62292,63644,55109,43597,49842,61754,49182,55595,34419],
[43089,62593,42823,39712,41287,63496,48540,37423,33935,65267,40334,41665,42970,38119,36223,45388,41159,38337,48393,60078,57130,48281,32779,33470,63099,38404,58265,40245,59839,56526,63269,65521]]
b = [[199010799],
[211695410],
[210217770],
[187225056],
[190479150],
[194625008],
[185661914],
[211167858],
[206237868],
[212420633],
[201482391],
[194210580],
[213090600],
[195153487],
[184935683],
[200284604],
[201920950],
[207287467],
[212872468],
[198033410],
[205187404],
[192392168],
[196682634],
[221830743],
[207500337],
[208973913],
[206595711],
[203711457],
[185840896],
[199676057],
[212282405],
[197217773]]


#################################################################################### part1 LWE to get q
#primal_attack1
def primal_attack1(A,b,m,n,esz):
    L = block_matrix(
        [
            #[matrix.identity(m)*p,matrix.zero(m, n+1)],
            [(matrix(A).T).stack(-vector(b)).change_ring(ZZ),matrix.identity(n+1)],
        ]
    )
    L = L.LLL()
    e = list(map(abs,L[0][:m]))
    s = list(map(abs,L[0][m:-1]))
    
    return (s,e)

A = Matrix(ZZ,A)
b = Matrix(ZZ,b)
m, n = A.dimensions()
array_q, e = primal_attack1(A,b,m,n,128)
q = sum([array_q[i]*256^i for i in range(len(array_q))])


#################################################################################### part2 get p
Q = prime_to_matrix(q,16)
S = Matrix(GF(2), S)
E = Matrix(GF(2), identity_matrix(16))
P = (Q-E).solve_left(S)
p = matrix_to_prime(P, 16)


#################################################################################### part3 LLL to get key and flag
nums = 16
c = c ^^ nums
n = 2^512
L = block_matrix(ZZ, [
    [1, (Matrix(ZZ,[pow(p,(nums-i),n) for i in range(nums)]).T).stack(vector(ZZ,[-c]))],
    [0,n]
])
ans = list(map(int, L.LLL()[0]))
ans = ans[:-2] + [-ans[-1]]
ans = ans[::-1]
ans = [ans[-1]//abs(ans[-1]) * i for i in ans]

key = b""
for i in range(len(ans[:-1])):
    key += long_to_bytes((c - ans[i]) ^^ c)
    c = (c - ans[i]) % n
    c = c * inverse(p,n) % n
key = key[::-1]

flag = "CBCTF{"+sha256(key).hexdigest()+"}"
print(flag)


#CBCTF{0d3f156b0c831817e366a437fc80c0e2c14a5e36ebd5c27f9ad835dd9d6a3855}



symmetric_cipher

题目描述：

1
do you know symmetric_cipher?

题目：

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
116
117
118
119
120
121
r_con = (0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,0x80, 0x1B, 0x36)
s_box = [
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
]

     
def xor_bytes(a, b):
    return bytes(i^j for i, j in zip(a, b))

def add_round_key(s, k):
    for i in range(4):
        for j in range(4):
            s[i][j] ^= k[i][j]

def sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = s_box[s[i][j]]

def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]


xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)

def mix_single_column(a):
    
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)

def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])

def _expand_key(s):
    for i in range(10):
        word = list(s[-1])
        word.append(word.pop(0))
        word = [s_box[b] for b in word] 
        word[0] ^= r_con[i]

        s.append(xor_bytes(word, s[-4]))
        s.append(xor_bytes(s[-1], s[-4]))
        s.append(xor_bytes(s[-1], s[-4]))
        s.append(xor_bytes(s[-1], s[-4]))

    return [s[4*i : 4*(i+1)] for i in range(len(s) // 4)]

def bytes2matrix(text):

    return [list(text[i:i+4]) for i in range(0, len(text), 4)]



def encrypt(plain,r,skeys):
    plain = bytes2matrix(plain)
    add_round_key(plain, skeys[0])

    for i in range(1, r+1):
        sub_bytes(plain)
        if i %2 == 1:
            shift_rows(plain)
        if i % 2 == 0 :
            mix_columns(plain)
         
        add_round_key(plain, skeys[i])
    enc = bytes(plain[0]+plain[1]+plain[2]+plain[3])
    return enc

import os
from hashlib import *
import json

key = os.urandom(16)
flag = "DASCTF{"+ sha256(key).digest().hex()+"}"
skeys = _expand_key(bytes2matrix(key))

   
pt = []
ct = []

from Crypto.Util.number import *

for i in range(2**8):
    if i == 0:
        p = b"\x00" + b"\xCB"*15
    else:
        p = long_to_bytes(i) + b"\xCB"*15
    pt.append(p)
    c = encrypt(p,7,skeys)
    ct.append(c)

pt_serializable = [list(p) for p in pt] 
ct_serializable = [list(c) for c in ct]  


data = {'pt': pt_serializable, 'ct': ct_serializable}

with open("out.json", "w") as f:
    json.dump(data, f)

本题基于AES，其与AES的标准实现主要区别在：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def encrypt(plain,r,skeys):
    plain = bytes2matrix(plain)
    add_round_key(plain, skeys[0])

    for i in range(1, r+1):
        sub_bytes(plain)
        if i %2 == 1:
            shift_rows(plain)
        if i % 2 == 0 :
            mix_columns(plain)
         
        add_round_key(plain, skeys[i])
    enc = bytes(plain[0]+plain[1]+plain[2]+plain[3])
    return enc

对明文的加密只有7轮，并且每一轮中，奇数轮会进行行移位，偶数轮会进行列混合。

而我们能获得的数据为如下明文的加密结果：

1
long_to_bytes(i,1) + b"\xCB"*15 (i from 0 to 255)

这显然对应着square attack里面的$\Lambda$集，有关square attack的详细解释可以看春乎：

初探AES square attack：以0ctf 2016 - people square为例 - 知乎 (zhihu.com)

要注意，虽然题目AES加密是七轮，然而列混淆其实仅有三轮，而影响$\Lambda$集性质的只有列混淆，因此其实对应的是4轮的square attack。

主要思路在于，在三轮列混淆后，同一位置的所有明文具有一个特性——相加起来为0，而最后一轮操作为：

  • 字节代换——破坏了这个特性
  • 行移位
  • 轮密钥加

也就是说，在进行这三个操作之前，同一位置的所有明文应当相加起来为0，而字节代换破坏了这个性质。然而，我们可以逐字节爆破最后一轮的轮密钥，然后倒过去做字节代换，检查该位置的明文是否具有这个特性，就可以获得第七轮轮密钥的可能值。

之后对所有可能的轮密钥反推主密钥，然后检查加密结果是否等于给定值就可以确定哪个才是正确的主密钥了。

exp：

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
from itertools import *
import json
from hashlib import *

with open(r"D:\CTF_challs\py\crypto\2024\DASCTF 2024 0rays\output.json", "r") as f:
    c = json.load(f)

pt = c['pt']
ct = c['ct']

################################################################################# part1 gen sbox
r_con = (0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,0x80, 0x1B, 0x36)
s_box = [
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
]

     
def xor_bytes(a, b):
    return bytes(i^j for i, j in zip(a, b))

def add_round_key(s, k):
    for i in range(4):
        for j in range(4):
            s[i][j] ^= k[i][j]

def sub_bytes(s):
    for i in range(4):
        for j in range(4):
            s[i][j] = s_box[s[i][j]]

def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]


xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)

def mix_single_column(a):
    
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)

def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])

def _expand_key(s):
    for i in range(10):
        word = list(s[-1])
        word.append(word.pop(0))
        word = [s_box[b] for b in word] 
        word[0] ^= r_con[i]

        s.append(xor_bytes(word, s[-4]))
        s.append(xor_bytes(s[-1], s[-4]))
        s.append(xor_bytes(s[-1], s[-4]))
        s.append(xor_bytes(s[-1], s[-4]))

    return [s[4*i : 4*(i+1)] for i in range(len(s) // 4)]

def bytes2matrix(text):

    return [list(text[i:i+4]) for i in range(0, len(text), 4)]



def encrypt(plain,r,skeys):
    plain = bytes2matrix(plain)
    add_round_key(plain, skeys[0])

    for i in range(1, r+1):
        sub_bytes(plain)
        if i %2 == 1:
            shift_rows(plain)
        if i % 2 == 0 :
            mix_columns(plain)
         
        add_round_key(plain, skeys[i])
    enc = bytes(plain[0]+plain[1]+plain[2]+plain[3])
    return enc

invS = [0 for i in range(256)]
for i in range(256):
    invS[s_box[i]] = i


################################################################################# part2 get possible Round key
Roundkey = [[] for i in range(16)]
for i in range(16):
    for ki in range(256):
        temp = 0
        for ind in range(256):
            temp ^= invS[ct[ind][i] ^ ki]
        if(temp == 0):
            Roundkey[i].append(ki)


################################################################################# part3 brute key
def func(k, ind):
    for i in range(ind)[::-1]:
        tmp = [
            xor_bytes(k[-3], k[-4]),
            xor_bytes(k[-2], k[-3]),
            xor_bytes(k[-1], k[-2]),
        ]
        word = list(tmp[-1])
        word.append(word.pop(0))
        word = [s_box[b] for b in word] 
        word[0] ^= r_con[i]
        tmp = [xor_bytes(k[-4], word)] + tmp
        k = tmp
    return b''.join(k)

for possible_key in product(*Roundkey):
    key = func([bytes(possible_key[i:i+4]) for i in range(0, 16, 4)], 7)
    skeys = _expand_key(bytes2matrix(key))
    for i in range(2**8):
        pti = pt[i]
        cti = ct[i]
        if encrypt(pti, 7, skeys) != bytes(cti):
            break
    else:
        print("DASCTF{"+ sha256(key).digest().hex()+"}")
        break


#DASCTF{e52c1ddd360fd584b5f3da33f9813d6f9d29d330113d8f6c78aa6cf904081369}