CryptoCTF 2024

Author:堇姬

Rank: 29th

Warm-up 🤑

Welcome! 👋

Crtl+c
Crtl+v

CCTF{Harn3sS_Y0ur_CrYptO9rAphy_Pr0wEs5_💪_⚡_💥_🔥!}

Easy 😁

Alibos

source code

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

get_context().precision = 1337

def pad(m, d):
	if len(str(m)) < d:
		m = str(m) + '1' * (d - len(str(m)))
	return int(m)

def genkey(d):
	skey = getRandomRange(10 ** (d - 1), 10 ** d)
	pkey = int(10**d * (sqrt(skey) - floor(sqrt(skey))))
	return pkey, skey

def encrypt(m, pkey):
	m = pad(m, len(str(pkey)))
	d = len(str(pkey))
	c = (pkey + d ** 2 * m) % (10 ** d)
	return c

pkey, skey = genkey(d)

m = bytes_to_long(flag)
c = encrypt(m, pkey)

print(f'pkey = {pkey}')
print(f'enc  = {c}')

output.txt

1
2
pkey = 8582435512564229286688465405009040056856016872134514945016805951785759509953023638490767572236748566493023965794194297026085882082781147026501124183913218900918532638964014591302221504335115379744625749001902791287122243760312557423006862735120339132655680911213722073949690947638446354528576541717311700749946777
enc  = 6314597738211377086770535291073179315279171595861180001679392971498929017818237394074266448467963648845725270238638741470530326527225591470945568628357663345362977083408459035746665948779559824189070193446347235731566688204757001867451307179564783577100125355658166518394135392082890798973020986161756145194380336

分析

給了你、

、

簡單的移項，直接計算就可以了(要注意右邊他pad了很多的1要刪掉)

1
2
3
4
def pad(m, d):
	if len(str(m)) < d:
		m = str(m) + '1' * (d - len(str(m)))
	return int(m)

script

1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *
pkey = 8582435512564229286688465405009040056856016872134514945016805951785759509953023638490767572236748566493023965794194297026085882082781147026501124183913218900918532638964014591302221504335115379744625749001902791287122243760312557423006862735120339132655680911213722073949690947638446354528576541717311700749946777
enc = 6314597738211377086770535291073179315279171595861180001679392971498929017818237394074266448467963648845725270238638741470530326527225591470945568628357663345362977083408459035746665948779559824189070193446347235731566688204757001867451307179564783577100125355658166518394135392082890798973020986161756145194380336
d = len(str(pkey))
m=((enc-pkey)*pow(d,-2,10**d))%(10**d)

print(int(str(m))) #6170704326493336128242608193100736601774626903966803036318189045381903593682775829229200905376968543264526051111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

print(long_to_bytes(617070432649333612824260819310073660177462690396680303631818904538190359368277582922920090537696854326452605))

CCTF{h0M3_m4De_cRyp70_5ySTeM_1N_CryptoCTF!!!}

Mashy

source code

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
#!/usr/bin/env python3

import sys
from hashlib import md5
from binascii import *
from secret import salt, flag

def die(*args):
    pr(*args)
    quit()

def pr(*args):
    s = " ".join(map(str, args))
    sys.stdout.write(s + "\n")
    sys.stdout.flush()

def sc():
    return sys.stdin.buffer.readline()

def xor(s1, s2):
    return bytes([s1[_] ^ s2[_] for _ in range(len(s1))])

def main():
    border = "┃"
    pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
    pr(border, ".: Hi all, she did Mashy, you should do it too! Are you ready? :. ", border)
    pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")

    REC = []
    cnt, STEP = 0, 7
    sh = md5(salt).digest()

    while True:
        pr(border, f'Please send your first input:  ')
        d1 = sc().strip()
        pr(border, f'Please send your second input: ')
        d2 = sc().strip()
        try:
            d1 = hexlify(unhexlify(d1))
            d2 = hexlify(unhexlify(d2))
            h1 = md5(unhexlify(d1)).digest()
            h2 = md5(unhexlify(d2)).digest()
        except:
            die(border, 'Your inputs are not valid! Bye!!!')
        if d1 != d2 and d1 not in REC and d2 not in REC:
            if md5(xor(d1, d2)).hexdigest() != 'ae09d7510659ca40eda3e45ca70e9606':
                if hexlify(xor(xor(h1, h2), sh)) == b'a483b30944cbf762d4a3afc154aad825':
                    REC += [d1, d2]
                    if cnt == STEP:
                        die(border, f'Congrats! the flag: {flag}')
                    pr(border, 'Good job, try next level :P')
                    cnt += 1
                else:
                    die(border, 'Your input is not correct! Bye!')
            else:
                die(border, 'No this one! Sorry!!')
        else:
            die(border, 'Kidding me!? Bye!!')

if __name__ == '__main__':
    main()

分析

輸入八組的 、

要求

並且

1
a483b30944cbf762d4a3afc154aad825 -> emelinjulca

當下還真沒看出來這要怎麼解，後來才知道

所以就只是要找八組碰撞的來解

解法

https://github.com/cr-marcstevens/hashclash
直接拿八組送就可以了

CCTF{mD5_h4Sh_cOlL!Si0N_CrYp7o_ch41lEnGe!!!}

Medium 🤔

Bada

1
2
3
4
5
6
7
8
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Hey! It's time to solve the equation of a function f: N x N -> Z.    ┃
┃ Function f has given certain conditions. In each step, solve the     ┃
┃ equation f(x, y) = z with the given value of z. We know f(a+1, b) =  ┃
┃ f(a, b) + a, and f(a, b+1) = f(a, b) - b, for every `a' and `b'.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┃ We know: f(1, 1) = 394111134899 and f(x, y) = 1085928033286
┃ Please send x, y separated by comma:

分析

對所有a b滿足

給定

f(1,1)跟f(x,y)，要求x跟y

這題其實很簡單

因為我們可以知道

如果設成這樣可以得

得證

script

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from pwn import *
r=remote('01.cr.yp.toc.tf', 17113)

r.recvlines(6)
for i in range(100):
    a=r.recvline().split()
    print(a)
    n1=int(a[6].decode())
    n2=int(a[11].decode())

    m=n2-n1
    print(m)
    r.sendlineafter(b'Please send x, y separated by comma: ',f'{m+1},{m}'.encode())
    r.recvlines(2)
r.interactive()

CCTF{BADA_iZ_4_K0r3An_5!ngeR!!}

RM2

source code

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
import sys
from Crypto.Util.number import *
from string import *
from random import *
from flag import flag
	
def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()
	
def sc(): 
	return sys.stdin.buffer.readline()

def randstr(l):
	return ''.join([printable[randint(0, 90)] for _ in range(l)])

def encrypt(msg, p, q):
	e = 65537
	m1, m2 = msg[:len(msg) >> 1], msg[len(msg) >> 1:]
	m1, m2 = bytes_to_long(m1), bytes_to_long(m2)
	c1, c2 = pow(m1, e, (p - 1) * (q - 1)), pow(m2, e, (2*p + 1) * (2*q + 1))
	return (c1, c2)

def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, ".: Welcome to RM2 task! Your mission is break our cryptosystem :. ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	nbit, _b = 1024, False
	pr(border, f"Please provide your desired {nbit}-bit prime numbers p, q:")
	inp = sc().decode()
	try:
		p, q = [int(_) for _ in inp.split(',')]
		if p.bit_length() == q.bit_length() == nbit and isPrime(p) and isPrime(q) and p != q:
			_b = True
	except:
		die(border, f"The input you provided is is not valid!")
	if _b:
		e, n =  65537, p * q
		s = randstr(nbit >> 4).encode()
		m = bytes_to_long(s)
		assert m < n >> 2
		c1, c2 = encrypt(s, p, q)
		pr(border, f'c1 = {c1}')
		pr(border, f'c2 = {c2}')
		pr(border, f'Now, send us the secret string to get the flag: ')
		_m = sc().strip()
		if _m == s:
			die(border, f'Congrats, you got the flag: {flag}')
		else:
			die(border, f'The secret string is not correct! Bye!!')
	else:
		die(border, f"Your input does not meet the requirements!!!")

if __name__ == '__main__':
	main()

流程

我們需要先輸入一組(p,q) 1024 bits的質數。

e = 65537
n = p × q

並產生了一個64 bytes 隨機字串，並拆成兩半m1、m2，來做加密

、

印出 、給你，如果你能提交正確的m，就可以拿到flag

分析

一開始使用getprime來隨機生成質數，當你把產生的p-1、q-1、2p+1、2q+1丟入factorDB是沒辦法全部分解的。
仔細分析後可以採用一個策略:

如果(p-1)/2和(q-1)/2是個質數，模數可以分解為2*2*((p-1)/2)*((q-1)/2)，那可以發現p、q是個safe prime。
因為p=2k+1、q=2k+1，這裡k是個質數

另外有個東西叫做Sophie Germain prime就滿足後面的p是個質數，2p+1是個質數
https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes

總之這題就是要找到同時滿足他是safe prime又是Sophie Germain prime

所以可以先生成safe prime再看看他是不是Sophie Germain prime

報錯可以看
https://blog.csdn.net/kulala082/article/details/68484314

1
2
3
4
5
6
7
import gensafeprime
from Crypto.Util.number import *

while True:
	a=gensafeprime.generate(1024)
	if(isPrime(2*a+1)):
		print(a)

找到

1
2
179038869479476343977624700131648035601030062609971358083068495264644773504891672033533628862180996104202480213255611201971674539999191838522787167917937277791863007890816459071795930442010669455816651153734397964768807485960692876685651034343992232617890851248047651749184487885382752475267482617769156174759
152626939093408062491455965189078085895710089466647132413566213985550098559310878828326396205570489809521107684567398503589855307057076999293252855393269557521587237138401310097549911211946862768385413685627911058536556141489179850863603684246330469754375715654686482993778608649026542257474853574317156591723

找到後直接搞就行了

script

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
import gmpy2
p=179038869479476343977624700131648035601030062609971358083068495264644773504891672033533628862180996104202480213255611201971674539999191838522787167917937277791863007890816459071795930442010669455816651153734397964768807485960692876685651034343992232617890851248047651749184487885382752475267482617769156174759
q=152626939093408062491455965189078085895710089466647132413566213985550098559310878828326396205570489809521107684567398503589855307057076999293252855393269557521587237138401310097549911211946862768385413685627911058536556141489179850863603684246330469754375715654686482993778608649026542257474853574317156591723
e=65537

p1=(p-1)//2
q1=(q-1)//2
d1=gmpy2.invert(e,(p1-1)*(q1-1))

p2=2*p+1
q2=2*q+1
d2=gmpy2.invert(e,(p2-1)*(q2-1))

#填入他輸出的cipher
c1 = 21151742531993710573547425710897641927865431812251870367074974615476947196023818990937531773721159817831540568326430012771017029204594858269615447374733393822719585019585152715616197619193913161508325323839747240362129247645941345454286273602633894772910487947675430526030392912094071192182218560002280246667719201806989032579217004398478404090393023045039212545353542372800473861051345217645271812032186457308143485566373819952733316934166884288561219139097503424061053231093875547232358595532171506731349688703159272518561988896741004483822812740400298954300908353976564035378839236849325436452912994141172684017111
c2 = 62818183008146329276409056323055998354752395300349878829271733651648571584856579955406068012482976250828090842810182898608457729894893815602684355086134126669218213205573891105258191447501061485257311674410706802749496991308792653037584070607980150860459775608776599334891419227439681465071717929183819653616572164900010542536129620906931790306808081402185470322959323706416193282801532918045577387102395289413100245487590409835139147487248899300717713713205000590198945159560687851165611513865142445942256258211044243177734485934949356680940836049836877050416783354434003664343258794638147445260137578779031632214093

m1=pow(c1,d1,2*2*p1*q1)
m2=pow(c2,d2,p2*q2)

print((long_to_bytes(m1) + long_to_bytes(m2)).decode())
1
2
3
┃ Now, send us the secret string to get the flag:
@:PG;RVp&o4Hm9];Hj;U9cZb'Y'DaU(+io%vn,=I3)Kpl.tj@C'xfK(CJ)Rfdj7c
┃ Congrats, you got the flag: b'CCTF{i_l0v3_5UpeR_S4fE_Pr1m3s!!}'

CCTF{i_l0v3_5UpeR_S4fE_Pr1m3s!!}

JOE-19

source code

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/env sage

from GPT import GPT6 # deep fake 
from Crypto.Util.number import *
from flag import flag

P = [GPT6('A 512-bit prime appears in consecutive digits of e') for _ in range(4)]
n, m = prod(P), bytes_to_long(flag)
c = pow(m, 0x10001, n)
print(f'n = {n}')
print(f'c = {c}')

output.txt

1
2
n = 8098851734937207931222242323719278262039311278408396153102939840336549151541408692581651429325092535316359074019383926520363453725271849258924996783681725111665666420297112252565291898169877088446887149672943461236879128453847442584868198963005276340812322871768679441501282681171263391133217373094824601748838255306528243603493400515452224778867670063040337191204276832576625227337670689681430055765023322478267339944312535862682499007423158988134472889946113994555274385595499503495488202251032898470224056637967019786473820952632846823442509236976892995505554046850101313269847925347047514591030406052185186963433
c = 7109666883988892105091816608945789114105575520302872143453259352879355990908149124303310269223886289484842913063773914475282456079383409262649058768777227206800315566373109284537693635270488429501591721126853086090237488579840160957328710017268493911400151764046320861154478494943928510792105098343926542515526432005970840321142196894715037239909959538873866099850417570975505565638622448664580282210383639403173773002795595142150433695880167315674091756597784809792396452578104130341085213443116999368555639128246707794076354522200892568943534878523445909591352323861659891882091917178199085781803940677425823784662

分析

想法就是直接枚舉，512bits大概是154、155 digits。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from sage.all import e, is_prime
n = 8098851734937207931222242323719278262039311278408396153102939840336549151541408692581651429325092535316359074019383926520363453725271849258924996783681725111665666420297112252565291898169877088446887149672943461236879128453847442584868198963005276340812322871768679441501282681171263391133217373094824601748838255306528243603493400515452224778867670063040337191204276832576625227337670689681430055765023322478267339944312535862682499007423158988134472889946113994555274385595499503495488202251032898470224056637967019786473820952632846823442509236976892995505554046850101313269847925347047514591030406052185186963433

e_str = str(e.n(digits=100100))

def find_prime_in_e(length):
    for i in range(len(e_str) - length):
        num_str = e_str[i:i+length]
        if num_str.isdigit():  
			
            num = int(num_str)
            if is_prime(num) and n % num == 0:
                print(num)
    return None

find_prime_in_e(154)

輸出了，找到一個，接下來就一直枚舉，拿到四個就解了(上面的腳本要在微調成155，才可以拿到其他的)

1
2
7728751393377105569802455757436190501772466214587592374418657530064998056688376964229825501195065837843125232135309371235243969149662310110328243570065781
9688632098638681429535439991332657144752666147923336383829750592576742104399942931057096761773496510622226977570278994077236841491368959008277469453600569
1
2
3
4
5
6
7
8
9
from Crypto.Util.number import *

p=7728751393377105569802455757436190501772466214587592374418657530064998056688376964229825501195065837843125232135309371235243969149662310110328243570065781
q=9688632098638681429535439991332657144752666147923336383829750592576742104399942931057096761773496510622226977570278994077236841491368959008277469453600569
r=10019005372961705640183251650710051163228093250949727357306333102512304273058618645339800283588040423877666492199352609508401454089083503146788384653241593
s=10795109107229646654467923653403055635071360620150038008453082390943756377071343139771120080956310498862485323957447467376538994662280143050510681877597429

d=inverse_mod(65537,(p-1)*(q-1)*(r-1)*(s-1))
long_to_bytes(pow(c,d,n)).decode()

非預期解

這題的n在賽中後來可以用factorDB直接分解

CCTF{ASIS_h1r3_7aL3nT5_t0_cO1La8orAt3_!N_Crypto_CTF!}