Moectf2020’s wp for Crypto

写在前面

​ 虽然人被hidden了，但这么好的题总得写篇wp纪念一下，师傅出题真的好强，有些题目做法非常巧妙，而我当时第一次解题的算法极度丑陋，听过师傅的预期解才知道自己有多蠢，打完下来真是学到了不少新思路和新想法，果然我还是太菜了啊qwq shallow,yyds!

crypto入门指北

12.png

下载文件flag就在后头

1
flag: moectf{I_L0Ve_M@th_AnD_CRypT0}

Stream

13.png

下载下来看一下加密脚本，看起来事先异或然后base64编码一下，那就反着搞一边，因为太懒所以就全部输出人工检验

15.png

sol.py

1
2
3
4
5
6
7
8
9
import base64

a = b'Og9hNAFrCjU9aQ4+C2psLzxpYRE6azw+FmphPgk2EjQBDyw+DWsKIQIPHiwAaBYoOx8wNBU2aGU='
b = base64.b64decode(a)
c = str(b,encoding='utf-8')
print(c)
for xor in range(0,256):
	d = "".join([chr(ord(i)^xor) for i in list(c)])
	print(d)

16.png

看到关键代码base64解码一下就行了

17.png

1
flag: moectf{U_Kn0w_How_7o_Break_Stream_Ciphe2}

easycrypto

18.png

究极大水题，方程系数小得离谱，爆破就完事了

19.png

sol.py

1
2
3
4
5
6
7
cipher = [60051, 62263, 51603, 49591, 67968, 52624, 76375, 38359, 51603, 58960, 49591, 62263, 60051, 51603, 45687, 67968, 62263, 45687, 22839, 65656, 73923, 63384, 67968, 62263, 78867]
flag = []
for i in cipher:
	for j in range(0,10000):
		if((5 * j ** 2 + 6 * j - 8) == i):
			print(chr(j),end='')
			pass
1
flag: moectf{Welcome_to_Crypto}

simple_number_theory

20.png

也是水题，据出题人说应该要求求逆元啊啥的，但是a,b,p都小的离谱，直接爆破……

21.png

然后每8位倒着排一下，再写个flag处理脚本就行了

sol.py

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
p = 702642074436764837683441695539
a = 1086077784009247
b = 862805818180723
cipher = [609157021623541347403691228214, 296649570588624720860438742570, 56199496972820506761619039889, 95133897800551968959628311224]
_long = []
_flag = []
def enc_block(m):
    return (a * m + b) % p

def dec_block(m):
	n = m - b
	while(int(n) % int(a) != 0):	n += p
	_long.append(n // a)

def bytes_to_long(s):
    res = 0
    for i in s:
        res *= 256
        res += i
    return res

def long_to_bytes(s):
	while s != 0:
		c = s % 256
		_flag.append(c)
		s -= c
		s //= 256

for i in cipher:
	dec_block(i)
for i in _long:
	i = long_to_bytes(i)
for i in _flag:
	print(chr(i),end='')
print()
1
flag: moectf{Integers_@re_W0nderful}

rsa_begin

22.png

该有的都有了，网上的题解满天飞，顺手推一下我们的云影安全微信公众号（狗头

23.png

sol.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from gmpy2 import *
from Crypto.Util.number import *
# from flag import flag

c = 12786994906832886031173089454539830225421640443805160963440942546071910322282773910135388020414967368794768319321460372875327006020157548651622969466323905189761834455201291838045352561790791600881627927594863932384116760236609096504346833060291203939690475993692410973499329433726175351882818053841075210942250478835641657575946226612389154039920962506062857726362447590070697348315291411570674334126096132112365825105842643843896421848410966564321518660727994853036555116782763422065173850238826345797198901647320210828033061322523971939726188821545177029535860881611210887039411052848607563035583276075332653567834
p = 161719691876167304386300539654699854745688262478039691942271426308613132466937889105173933022986654040443219708318126579048996288583272346602042650222520127626611975688909019632479930508343350314542889627461529623000987307169157443265879212155437165660477850241678385286601587538517091605374764970915451201471
q = 131679150542057883837006988923642169851011066771905140540444762603374903776910595387305441746623070810587630852182725227845916400198693359271062585498062084740896090668288333576457754165324164735966791029516030696195703650691726650990903496820364700241229117883279657833543807874786274886417501405960125022153
n = 21295111652177049852547386222656846645616549922902112221240647622752994625687294739828756977846793220378085163155773051922086862363248151399852421844018730199066331944608000906761112010951655369036878807145188296884981895884278542857120225505310980291226351653588799242142355376939447934804833830853036785704513557039806761305316841740131204576974408869765714675230132247412774215945663807730855436503625577606009921411947891570324777735323489304604987902364932089976811865007609745513534209603256719511305317200247134396733168695387708420206468160279271453425776388025425790010391137010735121696446552257334341187063
e = 65537
fn = (p-1) * (q-1)

d = inverse(e,fn)

flag = pow(c , d , n)

print(long_to_bytes(flag))
1
flag: moectf{uLl_f1Nd_th@t_RsA_1s_1nte2eSt1nG}

easy木大定理

24.png

题目说是考欧拉定理，看看代码

25.png

把该给的都给了，加密的时候用了nlist，那反过来用n的计算式回推一下philist就行了

26.png

sol.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from gmpy2 import *
from Crypto.Util.number import *

p = 271025496017434332035320753340939587753
q = 187062615477826075738455044071781085709
r = 264397348115983548873673645475684815267
e = 14436419940785226047

c = [79782042635181913487761772413093921465, 107105488436932482013906334623869740338, 3509151100641734446618186842681522103526622068330460330390027482293268995394, 44354713639146606352347981311754502280362685562054139875438634255351381551517, 7171349658970005627908887988207921395623970773677857712592896110910571654197390635906137916220127293111749219597125, 58862655174446752862856422604624433087552362298932033062526721301095820867360, 3090488671394364096763874366619864017834796691989365240435579932872211345861700323240994096818599239942176113337679, 53242497022725707314805904569598522652513669651433432760834670648465562534867455830168023766511087312372214790085176655801545624726261017112578045706948404488664028834533439478580770424859450, 81020119172085603626908922002571725744]

nlist = [p , q  , p*q , q*r ,  p*q*r , p*p , p*p*r , q*q*q*p*r , r]

philist = [p-1,q-1,(p-1)*(q-1),(q-1)*(r-1),(p-1)*(q-1)*(r-1),p*(p-1),p*(p-1)*(r-1),q*(q-1)*q*(p-1)*(r-1),r-1]

flag = b''
for i in range(9):
	d = inverse(e, philist[i])
	flag += long_to_bytes(pow(c[i], d, nlist[i]))
	print(flag)

1
flag: moectf{EULEREu1erEule2Eu1erEulerEyoulerEU1e2Mud@MuDaMudamuDaMudaMUDA}

rsa_begin_revange

36.png

37.png

给了n,c和hint，先去看看hint是个啥，自己瞎**推一下

$g=gcd(p-1,q=1)$

$a\times\lfloor\frac{p-1}{g}\rfloor\equiv 1\ (mod\ \lfloor\frac{q-1}{g}\rfloor)$

则$a\times(p-1)\equiv g\ (mod\ q-1)$

$hint=\lfloor\frac{(p-1)\times(q-1)}{a\times (p-1)-b\times(q-1)}\rfloor$

$=\lfloor\frac{(p-1)\times(q-1)}{a\times(p-1)-\lfloor\frac{a\times (p-1)}{q-1}\rfloor\times(q-1)}\rfloor$

$=\lfloor\frac{(p-1)\times(q-1)}{a\times(p-1)\ (mod\ q-1)}\rfloor$

综上$hint=\frac{(p-1)\times(q-1)}{g}=lcm(p-1,q-1)$

有了$lcm(p-1,q-1)$有什么用呢？请接着向下看：

我们假设存在d满足：$d\times e\equiv 1\ (mod\ lcm(p-1,q-1))$

则$d\times e=k\times\frac{(p-1)\times(q-1)}{g}+1$

则$d\times e \equiv 1\ (mod\ p-1)$且$d\times e\equiv 1\ (mod\ q-1)$

则$m^{d\times e}\equiv m\ (mod\ p)$且$m^{d\times e}\equiv m\ (mod\ q)$

则$c^{d}\equiv m\ (mod\ n)$

这样就能求flag啦~

sol.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from gmpy2 import *
from Crypto.Util.number import *

n = 15274905724187007976062688111694208171648245755926549723930848331679370559382277309531883193568893950618537696621973335715700448284819087159038713951851073149185059446912643737897880614890160880188620908714690264385997668798598389032843113850150234625318214472029794048309337944915760403977123127640741083061552842650243876818145471482782844942192939655496977995968249462959762107837545653910780501609410891704623755469701321490811972540402711220544261239624303000287494271883971664842734435125499746514235466736472849516113471303106458562434410438884653988546034083582407195140859293841032731147334776795622031282337
c = 7649873402645557904267318087204875676435882168796613316947771411609304536744042271054002728333680669285687627190582808948237918163341052473768906643435100209262290073776103059228983982708395050561155725257946981193880353145980419181148155547397493995821331967887083756241716647822351384179244060471199391747247330626972048194624897878342927011604047320501737138088098886160729919147364903324687064902431207489782684719866060626978706852094198695277585012692022694665155389477850250459470673339445457036367744618480100621696259061108892762604574152145934126164545321261689749666332036548040709163385969039424795114798
e = 65537
qwq = 136383086823098285500559715282984001532573622820772765392239717247137237137341761692248957085436553130522658005553333354604468288257313278205702803141527438832009459347434319088373934061519293573112686684952591646303550614273199902078956373662055666297484057785980304002761945936747860749795742211078045384475927861288347886650709611481381810997147044818139672858846272475970913014053853869202882345022377291447526811470070434720728876836913344962560289448011351932763985591362052051400141727936920979500079923065746957505390028959028016923551115667081325793801590895434210158036784591723251672614624035408035726128

d = inverse(e,qwq)
d = d // gcd(qwq,d)
print(gcd(qwq,d))

flag = pow(c , d , n)
print(long_to_bytes(flag))
1
flag: moectf{N0_NeEd_0F_phi}

middle_number_theory

27.png

下载下来看看代码

28.png

我们发现 $n=p\times p\times q$ ，那么可以推知 $\varphi(n)=p\times (p-1)\times (q-1)$ ，易得 $gcd(phi,n)=p$ ，那么我们就可以利用这一点来分解n

题目给出了 $d^e$ ，而我们只知道 $e\cdot d=1mod(\varphi(n))$ ，所以就要想办法凑出 $e\cdot d$ ，那么很容易就会想到计算 $e^e$ ，进而得到$(e\cdot d)^e$ ，那这个玩意有什么用呢？

已知 $e\cdot d=k*\varphi(n)+1$ ，那么利用二项式定理可得 $(e\cdot d)^e=k’*\varphi(n)+1^e$ ，也就是说 $(e\cdot d)^e-1$ 里含有 $\varphi(n)$ 这个因子，那么我们利用上面的发现就可以推知 $p=gcd(n,(e\cdot d)^e-1)$ ，进而轻松的分解n

29.png

sol.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from gmpy2 import *
from Crypto.Util.number import *

c = 4448609753611737184783460118930573289974694828209309175709949628465223463405042537603307361264761380400800350729175604496885732375438319175307011826514239216844042845183325716835960262669255068613919692934369346218209713074470153225198829274586356256625802581378453700430995893798833625329886795030977601102315708416972421382472094601951556773175452075331439121107255232114811021725981668874569161063548983009784894416802911422859936359527482179901438086738326065526817697057803865158059963425602001042753756386164877391445821738133062042393332307186524909204126104658874232514066187286573576444075900795178016884461229586058251765908406312947283296549422962032951453806059978614112639366858737616956050597703536432152195980016832543565107903030313390118042295315068984272529539696018361520511026902310387433645917417048944557075704198152942755292614975227076165842566871076387574381219659759554381960975806672100713624265645
dc = 4309364092091276388004718814102373553758980405817595679564074805153803411597209984472887910928838871439616337549817714231235995002349688101757956086314510197676354800597513087069272391935644254109136020957742504477468917529533637783598686192029088455752051601994770096972887977072952830171524146576714713502392664215692986646580843840303793878982584144644461159568931881588661756617717236884047105112888668648146085473657815040008134047308021734053728606524063506802175439005328642429159744216509543042159848740769165565673410747859836374160557014359965487933469822407200828390566264453086213027820399525489653073934351074166844643531380375787825536559792929397263081185360290665106662493622257356673769350619066454911986660848940520828757576389225105604313249568540781542345773967776633630823614537884871302450446987591091071183429649635305050366645973091463546902372443777545374881273351758466627834180698108933752834817285
n = 4614906805424062812904180777200626046851600804405428869320812834275160358610245198952889965237539464660657424060388577114957090724061303957724139453224008409554575380917602175702589416351163348116539369954124434724030360077640773011962121222393438345287763424336034763222619912337209640071585617726182823159807086530908043427223925438705353227949815783748421947577806634179740448479898342114286195890964814951325985489970330592893692081398041627328233752207807000402328087854304665341410463982442480669667193129646182867078229731360036941666813874606858859151295101218320962268157296221914290253164253552948488097844393207759852637434267746827609021901752347505733752021520614040176946109474363193301817028834190212049397172296876559821964894005643234444288624733187970674437976138837683481932013520334816274720064195689201450246239553950559829017102457374901493133385110017605849195394953758165592759005572440915877949376621
e = 65537
ec = pow(e , e , n)

qwq = ec * dc - 1

p = gcd(qwq,n)
q = n // ( p * p )

phi = p * (p-1) * (q-1)
d = invert(e,phi)
print(long_to_bytes(pow(c,d,n)))
1
flag: moectf{0H_y0U_@re_Real1y_G0od_@_1t}

cbc and its bytes

​ 怎么说，这题当时卡了我两天左右，原因就是文件在E盘然后我在C盘运行代码……这种nt错误还是少犯点好……

30.png

31.png

其实这个提示没啥实质性作用，就是让你去了解一下AES加密的CBC模式

简单这么说，CBC模式还需要另外一个参数iv，对明文加密完毕之后会利用iv对密文进行异或处理，因为这样即使明文相同加密出来的密文也绝对不同

该题循环16次每次随机生成一位key，然后把这玩意加密的结果输出到文件里去，16位key生成完毕之后，再用这个AES_CBC加密系统对flag进行加密，那既然是接着使用这个加密系统，那不难推知，在加密flag时的iv就是最后一次输出的密文，现在模式确定 废话 ，iv确定，现在只要找到key，问题就迎刃而解了

既然data这东西是key逐位加密出来的，那应该用这东西推key，那既然每次只生成一位key，而且这一位key以前的key是已知的，那只要爆破(1,256)的bytes就可以爆破出这一位的key了，接着重复16遍，key就拿到了

这里存在一个问题，就是当chr(i)中的i到达一定大小时，将其转换为bytes之后会变成两位，这其实是utf-8编码的问题，后来问了出题师傅，才知道解决办法，add_key = chr(i).encode('latin1')，这样就可以愉快的爆破key了

33.png

sol.py

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
from Crypto.Cipher import AES
from os import urandom

def pad(m):
    padlen = 16 - len(m) % 16
    return m + chr(padlen).encode() * padlen
    
clist = []
def dec_aes():
	f = open('./data' , 'rb')
	cipher = f.read()
	f.close()
	print(cipher)
	for i in range(16):
		clist.append(cipher[i*16:i*16+16])

def fuck(key,deep):
	if(deep ==  16):
		print('find key!')
		print(key)
		return
	# print('fuck(',key,',',deep,')')
	tmp_key = bytes([key[i%len(key)] for i in range(16)])
	for i in range(1,256):
		add_key = chr(i).encode('latin1')
		# print(add_key)
		de_aes = AES.new(tmp_key,AES.MODE_CBC,pad(add_key))
		iv = de_aes.decrypt(clist[deep])
		find_ = add_key + bytes([key[-1]])
		if(add_key == bytes(chr(iv[0]).encode('latin1')) and bytes(chr(iv[1]).encode('latin1')) == bytes(chr(key[-1]).encode('latin1'))):
			fuck(key + add_key,deep + 1)

def get_key():
	mlist = []
	for i in range(1,256):
		key = chr(i).encode('latin1')
		fuck(key,0)

dec_aes()
# get_key()

# '''
en_flag = b'L\xe0\x06\xa1|\x98S\x10\xbfQe8\x91\x9cJq\xe6\xb2\x0b\xdc\xd30\xae\x85\x00\xa1qC\x12R\xef\x00\xe2\x1eg\x9a\xb1j\xac\xdc@-fKn\x88\x80\xbd'
real_key = b'\x0e\xedj\x9d\x0eL\x9bs_\xa3e/I\xa6\xf5\xe0'
de_aes = AES.new(real_key,AES.MODE_CBC,clist[15])
ans = de_aes.decrypt(en_flag)
print(ans[::-1])
# '''

函数名太恶臭啊代码不好看啊啥的就假装没看见就行了主要是出题人太过**，代码越写我越生气（逃

35.png

但是我的做法特别复杂就是太垃圾了，后来问了出题人，可以通过列表来解决，因为列表和bytes的运算方法基本一致，然后这样代码写起来就比较清楚比较短

34.png

solve.py

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
from Crypto.Cipher import AES
def get_key():
    f = open('./data' , 'rb')
    c = f.read()
    print(len(c))
    c = [c[i*16:i*16+16] for i in range(16)]
    key = []
    for i in c:
        cipher = i
        for j in range(256):
            tmp_key = key + [j]
            tmp_key = bytes([tmp_key[k%len(tmp_key)] for k in range(16)])
            aes = AES.new(tmp_key , AES.MODE_ECB)
            tmp = aes.decrypt(cipher)
            if tmp[0] == 0 and tmp[1] == 15 ^ j:
                key.append(j)
                break
        else:
            print('wrong')
    return bytes(key) , c[-1]

key , iv = get_key()

c = b'L\xe0\x06\xa1|\x98S\x10\xbfQe8\x91\x9cJq\xe6\xb2\x0b\xdc\xd30\xae\x85\x00\xa1qC\x12R\xef\x00\xe2\x1eg\x9a\xb1j\xac\xdc@-fKn\x88\x80\xbd'
aes = AES.new(key , AES.MODE_CBC , iv)
print(aes.decrypt(c)[::-1])

这么强的出题人我只能爪巴 shallow,yyds!

1
flag: moectf{@lways_us1ng_ByTes_1s_N0t_bad}

Easy RSA

39.png

Hint是两个链接

LLL coppersmath

Waiting to upgrade……

我还是太菜了呜呜呜呜qwq