SRCTF Crypto 复现
justez
题目
1 | from Crypto.Util.number import * |
花里胡哨的，看了半天没看明白，一看 e 很大,试了试 wiener 一下出了
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
53import gmpy2
import libnum
import hashlib
import random
from Crypto.Util.number import *
def continuedFra(x, y):
cf = []
while y:
cf.append(x // y)
x, y = y, x % y
return cf
def gradualFra(cf):
numerator = 0
denominator = 1
for x in cf[::-1]:
numerator, denominator = denominator, x * denominator + numerator
return numerator, denominator
def solve_pq(a, b, c):
par = gmpy2.isqrt(b * b - 4 * a * c)
return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
gf = []
for i in range(1, len(cf) + 1):
gf.append(gradualFra(cf[:i]))
return gf
def wienerAttack(e, n):
cf = continuedFra(e, n)
gf = getGradualFra(cf)
for d, k in gf:
if k == 0: continue
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
p, q = solve_pq(1, n - phi + 1, n)
if p * q == n:
return d
n = 59447861832652211537262617254184281479829852166925461903662081261289292515576905767937322840660932440029530280492275752616941795671201953079301018060203465429579475061460085183882511211044583402328605487602525290853335843501892756351462762579677498265076859047191958682405236293711382106634923860856875702197
e= 14983946116420718695910350497572468216707179624388443450376271801029353003883222766239928455540840247101746285898514708092585961191614089889673789620455880325382360817355279757931949420354758283821942288319417005937365971171869321539979940627452543996523114498789386921202216406398001675382099523934286309463
c=5531240943076956185419252532740075458153435638783876058593858932704838715927408036778103767030441428608060995278765402621496571055270582748608426450102229896581270452441624390124702053351607096961665933344552694074590045043665839297172339145388284294053051066633951096064582407552698859869765532283938542919
d = wienerAttack(e, n)
print(d)
print(long_to_bytes(pow(c,d,n)))1
SRCTF{Wi3ner_is_often_encountered_on_RSA!}
leak
题目
1 | from Crypto.Util.number import * |
一看便知是 $d_p$ 高位泄露,推式子进行 coppersmith 可解
只需将原来博客的 $d_p$ 泄露变形可得。
于是，对 k 进行爆破，然后 coppersmith 求解 x
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
34from sage.all import *
from Crypto.Util.number import *
n = 110213245423787811834518112811871374057182659656333171180583906182098866895106152169202974253392946952670696530676210762805363864263383224528537325490112353868969261155364863882874549993204597016739119560224274234085791998310748667903130690276875928801213222945825623033159412256315898753155041172844790881283
e = 1013
leak = 2111661101489986207946671243111315656386526068378675693749037940046822939637002369276880737091
c = 44953911831010760674028216893023771903735777342102642215298073259026291235527656090988244571561391378675170728470813535186907109257362776905391646755360995924417928753904003476238093726521687524894340317021957879542128875867159267372684219741723042726979008939837475097290381429403885987472234565635819680600
F= PolynomialRing(Zmod(n),'x')
x=F.gen()
for k in range(1, e):
f = e*((leak << 200) + x )+ (k - 1)
x0 = f.monic().small_roots(X=2 ** (200 + 1), beta=0.44, epsilon=1/32)
if len(x0) != 0:
dp = x0[0] + (leak << 200)
for i in range(2, e):
p = (e * Integer(dp) - 1 + i) // i
if n % p == 0:
break
if p < 0:
continue
else:
print('k = ',k)
print('p = ',p)
print('dp = ',dp)
break
k = 408
p = 8425052872189860196277887295078450264003332273673576496739640825877578791706584134790827422650971920893248291608498662987569073222104075696946298915286253
dp = 3393308560566103613110935850337618665067482297787580662062955041419597381062474162877253295598811987881979568584666786277322983094391375009234047341990909
q=n//p
d=inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n))) 1
SRCTF{do_you_hear_of_the_high_dp_leak}
Who_is_Bob
题目
1 | from Crypto.Util.number import * |
分析一下题目
所以
因为 Bob 是一个 30 位左右的数，我们可以把 n-leak 进行分解，然后把小因子组合成三十位左右的数，遍历破解
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
27from tqdm import tqdm
from sympy import *
e=65537
n = 83551533637791995343217075093207075888114751056630372530634434127047066670630844940247145420790307521479826874365675804269523298586266076638571271567234671704671269359605807984410204884607410984160816036002212842986210090410991351912353876745392317665760163054027137901527714797966126447118700149990317258891
c = 78309281660733853390608911365864030224721696340767714309397025309727923007988734506317736073773797381428997269420533151442862487934268321488021490923820201215298630613307224160553995648878611049792491221454161735360351132054599297761941011233121670402299191829524451472897533682050463933866813803099215448841
leak = 83551533637791995343217075093207075888114751056630372530634434127047066670630844940247145420790307521479826874365675804269523298586266076638571257216554908695119517636260243773643003707817620018239877623870076598042268179945412307565612034852201182156671007990234097768953570942262083345175668126848614778091
t=n-leak
a=[32,25,41,41399,95222249]
bob1=a[0]*a[1]*a[2]*a[3]//2
bob2=a[4]*8
bob3=a[4]*10
pqsum1=(t//bob1)+bob1
pqsum2=(t//bob2)+bob2
pqsum3=(t//bob3)+bob3
pqsum=[pqsum1,pqsum2,pqsum3]
'''
for i in pqsum:
pqmin=int(sqrt((i*i)-4*n))
#print(pqmin)
p=(i+pqmin)//2
print(p)
'''
pp=11692922501282668874022132757465052074830894777545589851919999009583302109770521986233252511087974403084746456540880192584440061782414824853752632260753401
print(isPrime(pp))
qq=n//pp
d=inverse(e,(pp-1)*(qq-1))
print(long_to_bytes(pow(c,d,n)))1
SRCTF{Bob_is_a_b@d_b0y_He_cuts_in_line_everywh3re..}
leak revenge
题目
1 | from Crypto.Util.number import * |
这个题唯一与 leak 不同的点就是这个题的 e 很大，无法像普通的 $d_p$ 泄露那样去遍历
所以可以设两个未知数进行二元 coppersmith
(但是长时间的调参确实挺烦的)
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
71from sage.all import *
from Crypto.Util.number import *
from tqdm import tqdm
import itertools
def small_roots(f, bounds, m=1, d=None):
if not d:
d = f.degree()
if isinstance(f, Polynomial):
x, = polygens(f.base_ring(), f.variable_name(), 1)
f = f(x)
R = f.base_ring()
N = R.cardinality()
f /= f.coefficients().pop(0)
f = f.change_ring(ZZ)
G = Sequence([], f.parent())
for i in range(m+1):
base = N**(m-i) * f**i
for shifts in itertools.product(range(d), repeat=f.nvariables()):
g = base * prod(map(power, f.variables(), shifts))
G.append(g)
B, monomials = G.coefficient_matrix()
monomials = vector(monomials)
factors = [monomial(*bounds) for monomial in monomials]
for i, factor in enumerate(factors):
B.rescale_col(i, factor)
B = B.dense_matrix().LLL()
B = B.change_ring(QQ)
for i, factor in enumerate(factors):
B.rescale_col(i, 1/factor)
H = Sequence([], f.parent().change_ring(QQ))
for h in filter(None, B*monomials):
H.append(h)
I = H.ideal()
if I.dimension() == -1:
H.pop()
elif I.dimension() == 0:
roots = []
for root in I.variety(ring=ZZ):
root = tuple(R(root[var]) for var in f.variables())
roots.append(root)
return roots
return []
n = 99808598778276923350368946118829564161543192771741967304113142692217693457972421525964898372688505220132024575461230316318177765543298394717753949509523080306599063058808987337840085569950414884529534449801215600413303898393849792345972321407524999652571659221193654323489992751031985715286873931985408130197
e = 9550490518460184889
dph = 4239371595915398923623854132330356869028911602649930928560125044718768467773415379438150660838271530302945945606708178367182566660953659123879375907323904
c = 18661814437233106799783882536249538287931377372915334052147813302071480339780465378376553936510407532657463793836895065758256947765504246845601788497861702555369338586376572381147331367628136147491699775987490116748428373153021965663362046971594255692960097313870139384700219810117047587229718472407783734575
F= PolynomialRing(Zmod(n),'x,k')
x,k=F.gens()
f=e*(dph+x)+(k-1)
'''
roots=small_roots(f,[2**115,2**64],m=3,d=6)
print(roots)
'''
x=3027685711070484531889028075542545
k=3406275539771437164
dp=dph+x
t=pow(2,e*dp,n)-2
p=GCD(t,n)
q=n//p
d=inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))1
SRCTF{00adb8189e3580577be8b97d1da8e205d0b64d4e65570547d7a67850fad1e4a2}
baby
题目
1 | from enc import flag |
首先还是对题目进行分析，p 和 q 都是质数，r 和 t 已知, 而 tmp 又很小,于是可以对 tmp 进行爆破
然后便可以使用扩展欧几里得方法求解质数的丢番图方程
即
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
52from Crypto.Util.number import *
from tqdm import tqdm
from sympy import *
import math
def extended_gcd(a, b):
if b == 0:
return (a, 1, 0)
else:
g, x, y = extended_gcd(b, a % b)
return (g, y, x - (a // b) * y)
def solve_diophantine_prime(a, b, c):
# Find the modular inverse of a modulo b (since a and b are coprime)
def mod_inverse(x, m):
# Using Fermat's little theorem for modular inverse since m is prime
return pow(x, m - 2, m)
# Compute the modular inverse of a modulo b
a_inv = mod_inverse(a, b)
# Compute the solution for x and y
x = (c * a_inv) % b
y = (c - a * x) // b
if y > 0:
return (x, y)
else:
return None
e=65537
c = 30075387915048470863070050827629191303436443913395824732907226821054460652219815718226645166341618100700084925720992983286419204902032573926790086035422540879196867669665497753447829812026327367178333296715527968448124126434045869420695221514125724904849358819864918062875310272203931927234053359553779163755
leak = 52407066630998720273731758848751180003129908965730006096464345923549459617438414126937562326106182853585345246472838907532807236677219886418149723311118855918338387062301958904467478605422673207935942348215552655035846974843053690523359908921489934306458440759517598485452824210146131626776354968352617955744704892906092826257342911994753745093428990023111339468228443855826492957321799005181961
r = 4515378990844403115229704433484433833022655205121974667074150580454343643752811757675793959795169040704894972951300994535151410073321406165168737850534934347874731893617893819762340858239387281147345869706971753
t = 6006929234728180950140499814342609393927042935104177663404375056306287820676434237439964941788093406713118055152122129530273026459457066165368157449726903765601586482566299501860863052052121811433466409338266730837645652741024637475218039773
''''
for i in tqdm(range(2**10)):
solution = solve_diophantine_prime(r, t, leak-i)
if solution:
x, y = solution
print(f"Positive integer solution: x = {x}, y = {y}")
else:
print("No positive integer solution found.")
'''
p=10107036304221590140315537220898906759095811790937615837692120715006548746019505046230668048672611600884439559253340540831445253603270525554564368273932957
q=8724435494930578791898201381855906261499199490201926298013879508413402076594452143243163216133538607634050021589040517038447172885148196774972396508093843
n=p*q
d=inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))1
SRCTF{0896649c53c145919ce741f180957834}
Elementary Chinese
题目
1 | 漐訦硁剏鐐遑瓜谠黥噻麚俵曧玫甠媸辌戋黥巹飖煭谨晋瑢鳵鲢醢厨広癕讚鲛徣蟥昉豜雴餭謡爮裹涛僦茺仦蔯餭猳鼣譋壵鐄碝攡驑鐐钾髯蒥躚烗黥犬蝒虇雯緥畋讅瑊肰擁襙蝒寃輲镁饶穩泾姲騂讅噻竊蚇擹坕缀裶糆萾瓬睁問擹鹨巹鷬鵷礟緥巅殱麺铦氋颷黜磘勆镭碾泾赞锽侭瀾晶晗鲠哰齝摛缀爂膼麏褦鸉覴羘剙脡巑黥餅婴広蛟橳佳爮麚踺嘊徖賍鱝広筝鶵曍瓣棾 |
根据题目的解释，要注意拼音，所以猜测是四进制，但是有一个字的拼音出题人好像弄错了，半天没搞出来1
鐐: liáo 还是 liào
这里是 liáo 但上网查的是 liào
后面就四个一组将四进制转化为字符即可
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
31from Crypto.Util.number import *
#cipher=b"漐訦硁剏鐐遑瓜谠黥噻麚俵曧玫甠媸辌戋黥巹飖煭谨晋瑢鳵鲢醢厨広癕讚鲛徣蟥昉豜雴餭謡爮裹涛僦茺仦蔯餭猳鼣譋壵鐄碝攡驑鐐钾髯蒥躚烗黥犬蝒虇雯緥畋讅瑊肰擁襙蝒寃輲镁饶穩泾姲騂讅噻竊蚇擹坕缀裶糆萾瓬睁問擹鹨巹鷬鵷礟緥巅殱麺铦氋颷黜磘勆镭碾泾赞锽侭瀾晶晗鲠哰齝摛缀爂膼麏褦鸉覴羘剙脡巑黥餅婴広蛟橳佳爮麚踺嘊徖賍鱝広筝鶵曍瓣棾"
pinyin="zhí chén kēng chuàng liáo huáng guā dǎng qíng sāi jiā biào róng méi qíng chī liáng jiān qíng jǐn yáo liè jǐn jìn róng bǎo lián hǎi chú guǎng yōng zàn jiāo jiè huáng fǎng jiān chì huáng yáo páo guǒ tāo jiù chōng chào chén huáng jiā fèi lán zhuàng huáng ruǎn chī liú liáo jiǎ rán liú xiān kài qíng quǎn mián quǎn wén bǎo tián shěn jiān rán yōng cào mián yuān chuán měi ráo wěn jīng yàn xīng shěn sāi qiè chǐ tān jīng zhuì fēi miàn yíng fǎng zhēng wèn tān liù jǐn huáng yuān pào bǎo diān jiān miàn xiān méng biāo chù yáo láng léi niǎn jīng zàn huáng jǐn lán jīng hán gěng láo chī chī zhuì biāo zhuā jūn nài yáng dèng zāng chuàng tǐng cuán qíng bǐng yīng guǎng jiāo shèng jiā páo jiā jiàn ái cóng zāng fèn guǎng zhēng chú hào bàn qíng"
# 声调映射表
tone_map = {
'ā': 0, 'á': 1, 'ǎ': 2, 'à': 3,
'ō': 0, 'ó': 1, 'ǒ': 2, 'ò': 3,
'ē': 0, 'é': 1, 'ě': 2, 'è': 3,
'ī': 0, 'í': 1, 'ǐ': 2, 'ì': 3,
'ū': 0, 'ú': 1, 'ǔ': 2, 'ù': 3,
'ǖ': 0, 'ǘ': 1, 'ǚ': 2, 'ǜ': 3,
}
# 函数：将拼音转换为声调数字
def pinyin_to_tone_numbers(pinyin):
result = []
for char in pinyin:
if char in tone_map:
result.append(str(tone_map[char]))
return ''.join(result)
converted = pinyin_to_tone_numbers(pinyin)
print(len(converted))
print(converted)
oct_sum=0
flag=''
for i in range(0,len(converted),4):
for j in range(4):
oct_sum+=int(converted[len(converted)-i-j-1])*4**j
flag+=chr(oct_sum)
oct_sum=0
flag=flag[::-1]
print(flag)1
SRCTF{fc65c57ae6fa4f283c9815cdd079b158}
gen(复现参考了其他师傅的wp)
题目
1 | from Crypto.Util.number import * |
分析题目，可知 p 的最后一位和 q 的最后一位直接存在确定的映射关系
而 n 的最后一位是1，那么遍历 9 种情况，p 和 q 都只能为 9,根据最后一位一步步剪枝推出正确结果
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
44from Crypto.Util.number import *
n=540218955345736273157270500365412222635891331555885916094749429447522188097945587651602148011705042986794108314271976399685176209609565497683234538512051568892773567571780647542150095914514310788820174077474562960838254063787178970291739930150059487074686161337439933674264104852452665182142544893614405627421
c=64145178427862668977081119089224310813473899829361200429199320440654203799866988377450609415834134038989684748529337444191033925457821155131291654022850629061769294069279168614460327625093659378555734131036896690174186521680529952315042672582956230276121971979462073816915057029858827954023430179144497317212
Sbox = [
[6, 7, 5, 0, 8, 3, 4, 2, 1, 9],
[0, 7, 8, 3, 6, 4, 9, 1, 2, 5],
[9, 2, 6, 4, 5, 8, 7, 0, 3, 1],
[2, 6, 9, 0, 5, 7, 4, 8, 3, 1],
[3, 4, 0, 2, 6, 9, 1, 5, 7, 8],
[6, 1, 5, 4, 8, 9, 2, 0, 3, 7],
[1, 8, 6, 5, 4, 7, 9, 0, 3, 2],
[4, 9, 6, 0, 1, 8, 3, 2, 5, 7],
[9, 1, 7, 2, 0, 5, 8, 4, 6, 3],
[3, 0, 9, 8, 1, 4, 6, 2, 7, 5],
]
def find_p(p):
if len(p)==155:
P=int(p)
if n%P==0:
print("p = ", P)
print("q = ", n // P)
Q = n // P
d = inverse(65537, (P - 1) * (Q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))
return
else:
l=len(p)
pp=int(p)
qq=""
for i in range(l):
qq=str(Sbox[i%len(Sbox)][int(p[::-1][i])])+qq
if pp*int(qq)%(10**l)==n%(10**l):
find_p('0'+p)
find_p('1'+p)
find_p('2'+p)
find_p('3'+p)
find_p('4'+p)
find_p('5'+p)
find_p('6'+p)
find_p('7'+p)
find_p('8'+p)
find_p('9'+p)
find_p('9')1
SRCTF{ee986d80-387c-4c84-b84b-2712b0b67bcd}
ez_solve
题目
1 | import hashlib |
分析完题目逻辑，要根据 $M_1$ 和 $M_2$ 两个关于 M 的矩阵方程去解 M
我们可以建立一个生成元为 M 的矩阵的环，然后去求两个环多项式的因式
得出关于 M 的一次因式即可解出 M
exp:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22from Crypto.Util.number import *
from sage.all import *
import hashlib
from Crypto.Cipher import AES
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
c=b'\xaf\xd3!\\P\x0c$9\xfeG"x\xb3\xc7JM\x0b\'L\x8cTqV@\x9e\x9e\xca\xac\xdd\xe4\x895\xa3\x9eN\xe8I\xd5\xb0\x91\x11AF\xd2\x9aU\x13\x97'
n=126436888267781012728325147862192168074569338402123226307022297048826644481193368519869158824390349539092252616101267181512556989487056829549324008171102838036066363029806878372696377305159681565847972365181357622469349705573034076248549130732505935614642532285063301806885341154101123265057874816214806847677
M1=[70788049802210872657325474973365961442495115963939277111865641350055048819901449822465632485606809020379471344797466194449610657690124929335160372366988228457807825557779907523973200512849665350793199564054667797095235171828334472880330391081301022201012413131565133166332507683245743314875929810856790436028, 93946310204344655470602799904463622648439244872656217486655791642515217356156195473567620253966035813293372124117916489727251962676211225293104321516981316934405843429585710046938735376779352440126787506851899947800684153304312951755327163478544961002945679221651503277132313685024467548530758328430111859735, 96280788181347867387546511220835057901226801297359421216412587732796485902928071822366009289662352700051927639887171910509282396855557218492280060681547535867164958051250532899312830267988516922862014098628387540003902290370590147972903761411462873247308975754394195969694999091155197116885130653910521683842, 82968820255058883255035919030714183763637640426458940210286495015124852401276839072824063644723868173042409742829747820513526023772841551680844947180758028332567132440255523252901711427912620603874983324313253887270511317678867022612080327696264144752321538967369820957008434069521447129905236906803526449052, 23299939970678363067737192335571816938832859884862879524180056303051043776582248093649001894041305543962310176893242271115838409280326024222781284417771289946883993071845824610852423883414065657696777623395756513604997163135194317008850263759756833624467482947918313131551485197582615658945205896614289768844, 12983229406499732766141201642339110334498321705779917236046293992952541768389345853789584123291003231130829707571457826064936320037975264940065396109524266757004298297631174616695451557008050606667929361178266452374719656732014717973253518421162343858079544410372965537523850761391016472822972062324715285821, 102522723534333820647817806349916608091975463464876408921339270432881180080624135367414031830957392607669052112905585189043873269667208251596592543967942876255968974965698140745376987088298473350746668639863852806280742776259621730959806167803512848032747755591545712867081782475183677960718676607337573465642, 101666582535813407265759152164420943615616329707204869986587049904118224403977817390759622828336361005497206377740967334830281520359624652559092011610839320662635489533080837328012868032165362424052880565510492490317524446183777309040096699685518956281236647308550541625378511575250474514867226225253068719258, 79442597659147067581773733694758591827187291960025689084947969583130621716487571613128072331388014344690626587494794377775357639035269728387459627578598303445043911517221963728054055359832212876846727128042710915166446033690747475137976997044478962738285351194601741478649641210324553973743695513720007047865]
M2=[85011002078021702764472439338820924251455189945180267744980241098005803607511171258905278632018866003808163766109232407574158722086042726859565957224224010875065213612287866466761370710306083365809484078520495239041845733432413997652662145274025593229074870746684396607481127158456761704078728846871014283062, 18612493541785904649700966115790082384712245572041693066739605782836252870835030585662238851252782669670594810980638014446195757864801546734972135506912044894945083421004786093045806649929848545667867196747667200493107958865268190000456363702141159840947563300323427898417483671272951426375223346964668572202, 10409979193367499472238347512348607682499183547949721486066213585501558540546807632346892656854949402968057978796265467271586423071299360812471632877173810510426132082877303152085723994146887708361801458949991817004233513007750041281905357726928616237585294306617301025270702049840653918649824323245565456296, 97290271388985204317932363489916228438600093380586125891212597692547209089950446573430815456999358546548926193902149490545083783325024867522263244533702358555195302200103982600342219036362518186912529398096636367780716298443050757576707116185606208575548291849605483451107659242851579658350685748518020410211, 76411493174297200650248506483885046672690570276281714974696849296346055295820839317219387382826797610738355107033587767990534452288775589370108333558624084021822211400921546808923416455824771057494166214771225257186562668685129247626889962538777358945577011128780834633426695072195814100527260881504241756687, 5122114398009812781159747267707750339659355680409087605287249113203075596790778474420937161282283953877075026676474859652618480039163607844664641744859419097006197970206934095749955844481900067023204763191843938898938307689971028726469929005296920462303115960487419521108527765364965899343332761215507901639, 4190168064902985417336866300235101969303944554522816131917429195932521441903346161906106929451667035112869115516063816550722995394671535767072356133255240738814875494919929489253058192284807929170918975253490840121109704757447474130780255171436129225761920436787457240980477097737167025549908544228449437793, 92038810567168570182052926585081830349594291044515853041436552873038313936469360592524373391834296631010810767608882263488728123582514368288663729696416739745217893454185009768143978854066443924004089645733654847040545336889463479429136357813613024590889363749057519833244388485571762542928224585216650638133, 39733188009602619238067345618094689399116546385773633410090207141820523314320874815210874136182638764226311487300791611009147956447064627569336230354430504000875017912529708558255520653453380608857267698291775234169514019990026283886571060009487498041457927636329437842221965777862646266407961917351017019700]
M1=Matrix(Zmod(n),3,3,M1)
M2=Matrix(Zmod(n),3,3,M2)
PR=PolynomialRing(MatrixSpace(Zmod(n),3,3),'M')
M=PR.gen()
f = M**7 + 6*M**6 + 3*M**2 + M + 1 - M1
g = 4*M**5 + 7*M**4 + 2*M + 3 - M2
M=-gcd(f,g)[0]
key = hashlib.md5(str(M.list()).encode()).digest()
aes = AES.new(key, mode=AES.MODE_ECB)
print(aes.decrypt(c))1
SRCTF{4141614931b3e2a75a84f70af7f2adc5}
hash attack
题目
hash_attack.py1
2
3
4
5
6
7
8
9
10
11
12
13
14
15from Util import ez_hash, gensalt
from base64 import b64decode
FLAG = open("flag").read()
salt = gensalt()
key = "adwa_only_has_one_key"
hash_key = ez_hash(key, salt)
try:
password = b64decode(input("input your key: ")).decode("latin-1")
except:
print("wrong")
exit(0)
if password != key and ez_hash(password, salt) == hash_key:
print(FLAG)
print("Your key is wrong")
Util.py1
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
131import random
iv = 0x7380166F4914B2B9172442D7DA8A0600A96F30BC163138AAE38DEE4DB0FB0E4E
MAX = 2**32
def str_bin(msg):
return "".join([bin(ord(i))[2:].zfill(8) for i in msg])
def int_bin(a, l):
return bin(a)[2:].zfill(l)
def bin_hex(a, l):
return hex(int(a, 2))[2:].zfill(l)
def int_left_shift(a, k, bit=32):
return ((a << k) & 0xFFFFFFFF) | ((a & 0xFFFFFFFF) >> (bit - k))
def T(j):
return 0x79CC4519 if j <= 15 else 0x7A879D8A
def FF(x, y, z, j):
if j <= 15:
return x ^ y ^ z
else:
return (x & y) | (x & z) | (y & z)
def GG(x, y, z, j):
if j <= 15:
return x ^ y ^ z
else:
return (x & y) | ((x ^ 0xFFFFFFFF) & z)
def P0(x):
return x ^ int_left_shift(x, 9) ^ int_left_shift(x, 17)
def P1(x):
return x ^ int_left_shift(x, 15) ^ int_left_shift(x, 23)
def pad(msg):
if len(msg) < 512:
l = len(msg)
k = 512 - (l - 447) % 512
return msg + "1" + k * "0" + int_bin(l, 64)
else:
return msg
def msg_pad(bi):
w = []
for i in range(16):
w.append(int(bi[32 * i : 32 * i + 32], 2))
for i in range(16, 68):
w.append(
P1(w[i - 16] ^ w[i - 9] ^ int_left_shift(w[i - 3], 15))
^ int_left_shift(w[i - 13], 7)
^ w[i - 6]
)
w_ = []
for i in range(64):
w_.append(w[i] ^ w[i + 4])
return w, w_
def cf(vi, bi):
w, w_ = msg_pad(bi)
abcdefgh = []
for i in range(8):
abcdefgh.append(int(vi[i * 32 : (i + 1) * 32], 2))
a, b, c, d, e, f, g, h = abcdefgh
for j in range(64):
ss1 = int_left_shift(
int_left_shift(a, 12) + e + int_left_shift(T(j), j % 32) % MAX, 7
)
ss2 = ss1 ^ (int_left_shift(a, 12))
tt1 = (FF(a, b, c, j) + d + ss2 + w_[j]) % MAX
tt2 = (GG(e, f, g, j) + h + ss1 + w[j]) % MAX
d = c
c = int_left_shift(b, 9)
b = a
a = tt1
h = g
g = int_left_shift(f, 19)
f = e
e = P0(tt2)
vi_1 = int(
int_bin(a, 32)
+ int_bin(b, 32)
+ int_bin(c, 32)
+ int_bin(d, 32)
+ int_bin(e, 32)
+ int_bin(f, 32)
+ int_bin(g, 32)
+ int_bin(h, 32),
2,
) ^ int(vi, 2)
return int_bin(vi_1, 256)
def iteration_func(msg):
n = len(msg) // 512
bi = []
for i in range(n):
bi.append(msg[512 * i : 512 * i + 512])
v = [int_bin(iv, 256)]
for i in range(n):
v.append(cf(v[i], bi[i]))
return bin_hex(v[n], 64)
def ez_hash(msg, salt=None):
bin_msg = str_bin(msg)
pad_msg = pad(bin_msg)
if salt is not None:
pad_msg += salt
c = iteration_func(pad_msg)
return c
def gensalt():
strings = """0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ """
return "".join([random.choice(strings) for _ in range(32)])
这道题看着很复杂，其实将代码意思理清楚后很简单
主要的漏洞在这一点1
2
3
4
5
6
7def pad(msg):
if len(msg) < 512:
l = len(msg)
k = 512 - (l - 447) % 512
return msg + "1" + k * "0" + int_bin(l, 64)
else:
return msg
pad 会将信息填充到512位，但 salt 只有32位，下面接着看主要逻辑的函数1
2
3
4
5
6
7
8
9def iteration_func(msg):
n = len(msg) // 512
bi = []
for i in range(n):
bi.append(msg[512 * i : 512 * i + 512])
v = [int_bin(iv, 256)]
for i in range(n):
v.append(cf(v[i], bi[i]))
return bin_hex(v[n], 64)
ez_hash 的加密会导致 iteration_func 中的 n 只能为1，那么加不加盐其实加密的结果是一样的
再看主函数的要求1
2
3
4
5
6
7
8
9
10
11salt = gensalt()
key = "adwa_only_has_one_key"
hash_key = ez_hash(key, salt)
try:
password = b64decode(input("input your key: ")).decode("latin-1")
except:
print("wrong")
exit(0)
if password != key and ez_hash(password, salt) == hash_key:
print(FLAG)
print("Your key is wrong")
要求提交的 key 解密后不能等于题目给出的 key,分析 pad 函数，可以得知每次 pad 得到的东西都是唯一的，且 key 进行 pad 得到的东西和 pad 进行 pad 得到的东西一定是相同的。
我们只需进行反解，然后将原文加上 pad 进行 base64 提交即可
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
141from Crypto.Util.number import *
import base64
import random
from pwn import *
r=remote('110.40.35.62','34246')
MAX = 2**32
iv = 0x7380166F4914B2B9172442D7DA8A0600A96F30BC163138AAE38DEE4DB0FB0E4E
def str_bin(msg):
return "".join([bin(ord(i))[2:].zfill(8) for i in msg])
def int_bin(a, l):
return bin(a)[2:].zfill(l)
def bin_hex(a, l):
return hex(int(a, 2))[2:].zfill(l)
def int_left_shift(a, k, bit=32):
return ((a << k) & 0xFFFFFFFF) | ((a & 0xFFFFFFFF) >> (bit - k))
def T(j):
return 0x79CC4519 if j <= 15 else 0x7A879D8A
def FF(x, y, z, j):
if j <= 15:
return x ^ y ^ z
else:
return (x & y) | (x & z) | (y & z)
def GG(x, y, z, j):
if j <= 15:
return x ^ y ^ z
else:
return (x & y) | ((x ^ 0xFFFFFFFF) & z)
def P0(x):
return x ^ int_left_shift(x, 9) ^ int_left_shift(x, 17)
def P1(x):
return x ^ int_left_shift(x, 15) ^ int_left_shift(x, 23)
def pad(msg):
if len(msg) < 512:
l = len(msg)
k = 512 - (l - 447) % 512
return msg + "1" + k * "0" + int_bin(l, 64)
else:
return msg
def msg_pad(bi):
w = []
for i in range(16):
w.append(int(bi[32 * i : 32 * i + 32], 2))
for i in range(16, 68):
w.append(
P1(w[i - 16] ^ w[i - 9] ^ int_left_shift(w[i - 3], 15))
^ int_left_shift(w[i - 13], 7)
^ w[i - 6]
)
w_ = []
for i in range(64):
w_.append(w[i] ^ w[i + 4])
return w, w_
def cf(vi, bi):
w, w_ = msg_pad(bi)
abcdefgh = []
for i in range(8):
abcdefgh.append(int(vi[i * 32 : (i + 1) * 32], 2))
a, b, c, d, e, f, g, h = abcdefgh
for j in range(64):
ss1 = int_left_shift(
int_left_shift(a, 12) + e + int_left_shift(T(j), j % 32) % MAX, 7
)
ss2 = ss1 ^ (int_left_shift(a, 12))
tt1 = (FF(a, b, c, j) + d + ss2 + w_[j]) % MAX
tt2 = (GG(e, f, g, j) + h + ss1 + w[j]) % MAX
d = c
c = int_left_shift(b, 9)
b = a
a = tt1
h = g
g = int_left_shift(f, 19)
f = e
e = P0(tt2)
vi_1 = int(
int_bin(a, 32)
+ int_bin(b, 32)
+ int_bin(c, 32)
+ int_bin(d, 32)
+ int_bin(e, 32)
+ int_bin(f, 32)
+ int_bin(g, 32)
+ int_bin(h, 32),
2,
) ^ int(vi, 2)
return int_bin(vi_1, 256)
def iteration_func(msg):
n = len(msg) // 512
bi = []
for i in range(n):
bi.append(msg[512 * i : 512 * i + 512])
v = [int_bin(iv, 256)]
for i in range(n):
v.append(cf(v[i], bi[i]))
return bin_hex(v[n], 64)
def ez_hash(msg, salt=None):
bin_msg = str_bin(msg)
pad_msg = pad(bin_msg)
print(pad_msg)
if salt is not None:
pad_msg += salt
c = iteration_func(pad_msg)
return c
def gensalt():
strings = """0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ """
return "".join([random.choice(strings) for _ in range(32)])
key = "adwa_only_has_one_key"
salt=gensalt()
ez_hash(key)
pad_msg =0b01100001011001000111011101100001010111110110111101101110011011000111100101011111011010000110000101110011010111110110111101101110011001010101111101101011011001010111100110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010101000
msg=long_to_bytes(pad_msg)
key=base64.b64encode(msg)
r.sendline(key)
r.interactive()1
SRCTF{0a2df8b4-3745-4046-9465-55cd12c7c4b4}
miniRSA
题目
1 | from Crypto.Util.number import * |
其实这个题分析完后发现还是简单的
由于 lists 的第一个本来是 n ,mod n 后等于0,进行运算后的结果应该是 n-psum(plist 的和)
因为 psum 可以算出来，因此可求出 n,因为 e,p,q 都太小，所以没有被覆盖
因此可以使用公因数将 p,q 解出，从而变成正常的 RSA
exp:1
2
3
4
5
6
7
8
9
10
11
12
13
14from Crypto.Util.number import *
lists = [19034306342361575075980551192712932322561988507704505619003321414454907641123196592043365494891212486631173617896128451305418561737688048967513695641921599895309500342048432076585214210554842683457585293799208643896433433876203082395319550418122273580170345397532087392101148847164139646172755862708188955074277199371835992255416573480806974852069162630676280643957223609636372925574762048260194971667671613092718354976535258179882483301719485865787139872158633048232174665688800039155623876126394585564220031878057948716342605048404401736509363831312390340124864856687925198309333062696436226782334117439595759538940, 735330208874124234708140189708190509639084585785019826186806221072030230392356294636951475819901892456531468208010283670339949843143111658956194009976314737497, 1602301325810709453980853329085731847189218243782953569904960880815334610650572082382219179731782825651268085475709993054918232934300216394178608235615344495673512692541974847829942480171431671140039053286087943307976082240770926172332448900407286986345896064450121772794727122073540966838136136436311798370861018787733155173660981857717532831514899794350952923611979062563752154655540017198341394961130185339410014663001790342283582793527539631430062006919362717, 1490871212681506284400346092290638774030823320747089448463392252548500186740778483192999592745868050668105386341645983368296594796392901704435327383316688779360786838012347149230273755275378107539155514295046237111681414693463240979896636803365784453108997600704264840021949772185282342808188139710222290864584233541392564011658505044015371776137094111399194018534838868815570165823623635735936443128581542320020795321638570854400035174475756508084590680356839283]
c = 15709429897819175308791479593882604989090989118233668933670906164260634913646468935153698184826048828639442348549719275685262082300536207994989372917456166207109082588994547995099508074828988380667184703433477180995225527115780075500780238386354394158860518835289592441774944550726238379621327375074110844317019009627210693272418127362069725045971765997290253778268185565684106141611166424581425058580613958929007167669365312045402281728283642414980252973340376734458355144454456208389560426222274622157045069419138452349507377359387075362422897820554817185082519230849569674743365163066580506210507870872289317520453
p_lists = [159514797898368694161035323666560455482927593628677715144231158683776654589410889361171506677869798913439553045649444471426486937156757512923737117257266219702305948490272092580126724358398210101455463243496876546152497051194626631388993441751102173455821084385690114474413278066052568157824769407231302148231,164502040257301220127513609478443722760842040728679662285075057209725349316105183287859838362165949816685266852802699646133095636456140274119704558163346582955848072668773982942422021335047461181890966859173748565841810779262398379776937252911005772364747785905459772986563538358107206075165619121918994313769,12067354386497776843231760139208442059041398520525521383656281303341787642443750743770398376846740004903417368242663172521036538264680412501426825455937841,110389310327674438994512412189140404012421052386936465666855251542042378560401291600983416103427179353607040781976104766195786129003714052707327680357018140453491041540444836366277074087514554288700445714013715928343998664686187619330641898588950044266264672614012387217326725054091455281834050284619735562549,131168948504860583548757651969440837258361128569062609463069944727375174669195551932348531223057116675553618553732609541174461910935866787631844529969966272525720171277182239591792328433851360949404595252497565480569603077853913064387239844154330498879841647697426578252738103633954750574330627202596111430527]
sum=0
for i in p_lists:
sum+=i
n=sum+lists[0]
e=65537
p=GCD(n,lists[2])
q=GCD(n,lists[3])
assert p*q==n
d=inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))1
SRCTF{1a2650c7-ba61-4fd7-b149-f087151bd06c}
poly
题目
1 | from sage.all import * |
这道题是我原来没见过的环上 lwe 问题，是在 mod p 的环上又除以了一个 $x^{44}+7$ 的多项式变成商环
然后将多项式的乘法转换为矩阵形式，并且根据商环的性质进行降次，但是这道题没有告诉 G
因此，只能造一个二维的格，然后去规约向量。
设 c 经过降次进行多项式乘法得到的矩阵为 C
又因为是 mod p 的环，所以可以得到如下式子
P 是 p 倍的 n 阶单位矩阵，I 是 n 阶单位矩阵, O 全为0
从而通过 LLL 算法规约出 M
exp:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21from Crypto.Util.number import *
from sage.all import *
n = 44
p = 76891131940393761705102995562451713716977513168151987122997698584077754434833
C=[33222500502316035616044442135960372497847961950485396449413543317883083038926, 37551883051023930209923814926663073615919611988658153864463372769156803888469, 6885819064632061993006721865975003168384486440800591106499315365485465123229, 39150781748560521282853118128987061565148646929624060895186981310505753042252, 9568187802811298965958948039003497460787285968756679037977894645041230605230, 37039707763200944116157977937398298700793465090822704196315684480524635756767, 52441772669424143174194878726638184660923200094214687016411659332366279566709, 33850405996304683137606272215449280389895051179518925120841689901077170269078, 15341672652784040453406716813014117299923786049907728865648634461092201606792, 56703196137744207452658592474062072883337973945083048857817108299542982976405, 61533436483609026382515005265341298411416881075792188250913245704638670030364, 66270669234290634938273377483953787496878362727975700849857389711011329780385, 68771491186591065608776822349174317474206206047585157630835108539697573971707, 3620540881702324693423502545001853679462640825354858276336125119756853401905, 53202792716812461928600680015496343136944059665848327350339519613632064314757, 55487906128655370245600430399584233480871206797186097717636498427481151521146, 24995778407868584306262430379279435923173858877131513575891155096706151560305, 26385021978283873070159223082747035201123213515216708286528602666689096572218, 75365256675053469553088716449423544790753638639428613263343571868459971553770, 7422642100742781104584859886241184379428101465047527306303207728012404554193, 21144076150831753362879700818362317541523415787624597530803644520157481989204, 11602131177213835800960780897300674931503149599436521029879191182697478989706, 269997034105887335932766435931957570226213091339493873697552817860500168798, 29592170769785676613770053060673595071183678309290305132514446341983310057605, 24608795020106050833673118614839318384738246238815037121228767642217605648805, 22129662168611841560758046123292241716232133669102309112724365812287930117701, 41819704925092226760551510707586882035079374882586684192893538006114228105476, 73387865731018950174100484941706140946589506913954231243924048130854401158970, 25772039328336068784600147029354208742237468081402872119647154618121339370144, 23878524887580811269284698304144369917813550916798991814242506737886915169609, 32651749018417205016614364575299285991871099208178617132955238539365552391829, 59025332692723731611419140375270204975464077495385523826794315887072186545135, 25379327588975988278959581354810488734224203430505421849901883250638122130273, 61435431838377069957555323132491713473896209781310430077916023034884542211875, 21948105745040304591828123835549540713605709311616849774188554136924562275030, 17122665797421754783955128405890580310316298670477799297889918571006476834354, 23771597187658350970465494159881184887335083411030494510375934645166615928309, 70659370674679121941279027090647056688378913650216555641359152878944275503654, 14442265238338035221061312637099599690996583630232531108769592425227252771140, 56171157458244810447661382507002995139214745429468641679613301401736104291976, 53791118180662787206327356942829168306676099220493071885479019705662488298391, 7339916594913560091967746623160329630569283548552475349534457652810179939101, 35268939876658587708773169547987291475313529613437305476095674851828645203393, 64853224339996552144448604332136216831902409567122258863695738304153705809491]
#part1 construct matrix of poly_mul
poly_mul_mat = Matrix(ZZ,n,n)
for i in range(n):
for j in range(i+1):
poly_mul_mat[j,i] = C[i-j]
for j in range(n-i-1):
poly_mul_mat[j+i+1,i] = C[-(j+1)]*(-7)
#part2 construct Lattice of RLWE
I=identity_matrix(n)
O = diagonal_matrix([0]*n)
L=block_matrix(ZZ,[[p*I,O],[poly_mul_mat,I]])
#part3 LLL to get s and get flag
res=L.LLL()[0]
s=res[n:2*n]
for i in s:
print(chr(abs(i)),end = "")1
SRCTF{630927c4-05a0-4814-be58-71effff2667b}
broke_prime(解释直接搬题解了，赛后复现出来的)
题目
1 | from Crypto.Util.number import * |
LCG
我们已知LCG的递推方式为
利用$X_i-X_{i-1}$得到
其可以写成
故
我们记$p=X_{i},q=X_{j}$那么$p=A_0X_0+B_0,q=A_1X_0+B_1$，其中$A_i,B_i,i\in\{0,1\}$为矩阵计算中的系数
我们未知的是$p,q$的低位及$X_0$，那么这就是一个hnp问题
HNP
利用二者消去$X_0$得到
其中$C$为只包含$A_i,B_i,p_h,q_h,i\in\{0,1\}$的系数
构造格
即可解出短向量$\left[\begin{matrix}e_1,e_2,1,0\end{matrix}\right]$
进而恢复$p,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
42from Crypto.Util.number import *
from gmpy2 import *
from sage.all import *
from tqdm import tqdm
mod = 354252708427750240229260978193205484318571536272112991343431793849964373726922463628613145814371373260028683490026950541602265331657638161041835445105208291
a = 237900048765544226238606951931485142842805199598265659541214836217396990325502179274242649127973632458845665307476813590275841979202728059697763417557857652
b = 13181797456611043076861621596229452465596236739465663534833159120373125242860992712109343179847088690433413264607017889258274469596421834574886130502704297
c = 41761716242103652084201480772302771510511622202566086490783949795002810521506969109162934497335266343959159394065053842621794178874404961380566756416164306
enc= 49413778670684043701101712067195406168770575146031767041873371910337742758286565131851416663826193705462720353166890852821396960382491317715463464433723470559989749532064756243470250498365928896006806459819182162923093375530509813688770261491678505176799616099814549247316518267701834540369749958922344112880476
ph=449102445150699600758919619594591097695198474900484586670894857878442127718377375168779706417242184820702347471107358
qh=1005180820885711801162429017222367006492489122545352977284777513576148651454304967952076877842792817940225372495541955
A=Matrix(Zmod(mod),[[a+1,b-a],[1,0]])
size=1000
bits=2**128
for i in tqdm(range(252,size)):
for j in range(i,size):
V0=A**i
V1=A**j
A0=(V0[0][0])*a+(V0[0][1])
B0=(V0[0][0])*c
A1=(V1[0][0])*a+(V1[0][1])
B1=(V1[0][0])*c
C=A1*(ph*bits-B0)-A0*(qh*bits-B1)
L=Matrix(ZZ,
[
[1, 0, 0, A1],
[0, 1, 0, A0],
[0, 0, 1, C],
[0, 0, 0, mod],
],)
M=L.LLL()
for l in M:
e1, e2 = int(abs(l[0])), int(abs(l[1]))
p = bits * ph + e1
q = bits * qh + e2
if isPrime(p) and isPrime(q) and l[-1]==0 :
n = p * q
d = inverse(e, (p - 1) * (q - 1))
print(i,j)
print(p, q, e1, e2)
1
SRCTF{e65f98ac87f1c7a02b252d30eb2db69d5368da9fa23cc1fcf1c435b669359938}