# WannaGame Cyber Knight 2023
> Đây là giải đấu do clb Wanna.W1n tổ chức nhằm tuyển thành viên vào câu lạc bộ. Trong giải đấu này mình đã 'may mắn' giải được 2 câu trong phần cryptography và xếp vị thứ 4 chung cuộc.
> Sau đây mình sẽ trình bày sơ sơ write-up 2 bài mình đã làm được ^^.
## DHLCG
- DHLCG.py

from Crypto.Util.number import long_to_bytes as ltb , getPrime, isPrime, getRandomRange
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES 
from Crypto.Util.Padding import pad, unpad 
import random
from secret import FLAG, hint
from hashlib import sha256 

def f(a, b, x, mod):
    return (a*x + b) % mod 

def Xn(a, b, x, n, mod):
    X = x 
    for i in range(n):
        X = f(a, b, X, mod)
    return X 
    #you may think:"How da heo can this compute such a large number?"
    #because I have a supercomputer, idiot :P

p = 253124343713187900774555463876030540737349270963561331390907876266826416285173608781046103998025571922987541328220629719904523466259089107010586433496746979699703152921471010925715339786724191668080154086619451623075539654108918173538947700048917690068763753304706837347078871045230506141231379595014672208368105497383
#print(p)
a = getRandomRange(1, p)
b = getRandomRange(1, p)

print(f"p : {p}")
print(f"a : {a}")
print(f"b : {b}")

random.seed(random.randint(1, 0x1337)) #to spice things up, I will random the x0, so you have to find it yourself

x = random.randint(1, p - 1)


AliceKey = getRandomRange(1, p)
BobKey = getRandomRange(1, p)
AlicePubkey = Xn(a, b,x, AliceKey, p)
BobPubkey = Xn(a, b, x, BobKey, p)

print(f"Alice Public Key : {AlicePubkey}")
print(f"Bob Public Key : {BobPubkey}")

assert(Xn(a, b, AlicePubkey, BobKey, p) == Xn(a, b, BobPubkey, AliceKey, p))

sharekey = Xn(a, b, AlicePubkey, BobKey, p)
#LCG is hard, so I will probaly give you some hint about flag
print(f"hint : {hint}")

#it's time for final part: encrypting
iv = get_random_bytes(16)
key = sha256(str(sharekey).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv) 
encrypted = cipher.encrypt(pad(FLAG, 16))
print(f"iv : {iv.hex()}")
print(f"enc : {encrypted.hex()}")
print(f"complete!")
#another thing, you will probaly gonna receive a gift from me when you "decrypt the FLAG"

> Đây là bài mà mình được first blood:knife:🩸(●'◡'●) ~~và nhận được [1M](https://cdn.discordapp.com/attachments/1084701428167229524/1152845886121050193/20230916_165607.jpg)~~. Sở dĩ được first blood là vì mình đã may mắn được làm qua dạng này từ trước đó trong 1 giải CTF trước đó. Mọi người có thể theo dõi wu bài đó tại đây https://hackmd.io/@GNF6eq5FT3W48I2WRj0Wlg/r1AOQWVo3
- Bài này khác duy nhất bài mình đã làm ở chỗ đề bài random giá trị x, tuy nhiên ramdom scheme này có seed từ 0 đến 0x1337. Do đó ta dễ dàng brute-force seed và tìm được x dễ dàng. Từ đó dễ dàng tìm sharekey và get flag i như bài trên.
- solve.py

p = 253124343713187900774555463876030540737349270963561331390907876266826416285173608781046103998025571922987541328220629719904523466259089107010586433496746979699703152921471010925715339786724191668080154086619451623075539654108918173538947700048917690068763753304706837347078871045230506141231379595014672208368105497383
a = 236980503663131916745383319367628912529719661721974885682452997888851388115592431643616595886551596456880343910407279239525313460409807672928638025004150328675607355678823548974715744447967351357073652016109888603689966540425586260204629631252461654520080681232418379585694433628242967067483620058262935046157068200840
b = 229846911309744969375833535945955054778909265778779820734660700510889584916845040310314881529676984252884590464101858093600297004896945862624825385465776467489059245213881166145288509791113634746363781489600709970005103442554390814078987754476542071226133328737685853281826183073930051968522687627724104762415136378285
Akey = 13035987322048310166857021868949995471117799262130633171010623103933986247984123484036238302128208556136112482147989102531984085451905404721959217184444611071906285152581751915829299698168746640673958224289631677012988017746406865509305807928965475916312071440779131570632275186707665507510534324837131999826554929322
Bkey =  184755395016347238616689459531551377481032936286107931359668197731574906307472711191190322098928615457225804695255925500593675247896328181996406536086387553579659753976339744292155936320495186544230247157581869969082077115504165150597454726083437674912737321066107102667017555180873644283375605169989962570314656434687
iv = bytes.fromhex("6fbdbe144bb0556860b02179457fa917")

enc = bytes.fromhex("62d777585f5dbe9d727daf8682b2dd0cb5a2455340cdd64c34ce5a90bc754e77bc79fa78c52565f3a6c25c26b1c46bca9927017ae10be30886d0ea4318eed07b")
from hashlib import sha256
from Crypto.Util.number import *
from Crypto.Cipher import AES 
from tqdm import trange
def decompose_f(C):
	ans = (C - x) % p
	ans = (ans * (a-1) * pow(b + (a-1)*x, -1,p) + 1) % p
	# assert (ans - 1) * (s*(a-1)+b) % p == (a-1)*(C - s) % p
	return ans

import random
for seed in trange(0x1337):
	random.seed(seed)
	x = random.randint(1,p-1)
	pow_nb = decompose_f(Akey)
	pow_na = decompose_f(Bkey)
	shared_secret = ((pow_na * pow_nb - 1) * (x*(a-1) + b) * pow(a-1,-1,p) + x) % p
	# assert (a-1)*(shared_secret - s)% p == (pow_nb * pow_na -1) * (s*(a-1) + b) % p
	key = sha256(str(shared_secret).encode()).digest()[:16]
	cipher = AES.new(key, AES.MODE_CBC, iv) 

	flag = cipher.decrypt(enc)
	if b'W1{' in flag:
		break
print(flag)

## Warm up
- chall.py

from Crypto.Util.number import getPrime, isPrime 
from Crypto.Util.number import long_to_bytes as ltb, bytes_to_long as btl 
from random import randint 
from secret import FLAG


def genprimes1():
    while True:
        p = getPrime(512)
        q = p + int(str(p), 12) + 1
        if isPrime(q):
            return p, q
        
def genprimes2():
    ok =  btl(b'd4rkn19ht_w4s_h3r3')
    while True:
        p = getPrime(512)
        q = ok *p +  randint(pow(2,255), pow(2, 256) - 1)
        if isPrime(q):
            return p, q 

def gensmoothprime(bitlen, smoothness ):
    p = 2
    while (bitlen - p.bit_length()) > 2*smoothness:
        p = p * getPrime(smoothness)
    while True:
        bit = bitlen - p.bit_length()
        q = p * getPrime(bit//2) * getPrime(bit//2)
        if isPrime(q+1):
            return q + 1

def genprimes3():
    p = gensmoothprime(1024, 18)
    q = getPrime(1024)
    return p, q 

p1, q1 = genprimes1()

p2, q2 = genprimes2()

p3, q3 = genprimes3()


n1 = p1 * q1 
n2 = p2 * q2 
n3 = p3 * q3

e1 = e2 = e3 = 65537
L = len(FLAG)
part1 = btl(FLAG[ : L // 3])
part2 = btl(FLAG[L // 3 : (2*L)//3])
part3 = btl(FLAG[(2 * L) // 3 : ])

c1 = pow(part1, e1, n1)
c2 = pow(part2, e2, n2)
c3 = pow(part3, e3, n3)

print(f"{n1 = }")
print(f"{e1 = }")
print(f"{c1 = }")

print(f"{n2 = }")
print(f'{e2 = }')
print(f"{c2 = }")

print(f"{n3 = }")
print(f"{e3 = }")
print(f"{c3 = }")

- Bài này đơn giản họ sẽ chia flag ra thành 3 phần bằng nhau, mỗi phần được mã hóa bằng một hệ mã RSA khác nhau và hoàn toàn độc lập với nhau. Vì vậy mình sẽ giải quyết từng phần.
### Part 1
- Nhìn vào hàm `genprimes1()`

def genprimes1():
    while True:
        p = getPrime(512)
        q = p + int(str(p), 12) + 1
        if isPrime(q):
            return p, q

- Dễ dàng đánh giá rằng q hoàn toàn phụ thuộc vào p và p càng lớn thì làm cho q lớn theo, do đó `n=p*q` cũng càng lớn. Tới đây thì quá rõ ràng, key ở đây chính là binary search. Ta sẽ binary-search giá trị p trên khoảng ($2^{511}$, $2^{512}$), vì binary search chỉ có O(logn) nên ta chỉ mất tối đa 511 step để có được kết quả.

def f(can):
	p = can 
	q = p + int(str(p), 12) + 1
	return p*q

l = 2**511
r = 2**512

while True:

	candidate = floor((l+r)//2)
	# print(candidate)
	if candidate >= 2**512:
		break
	if f(candidate) == n1:
		p1 = candidate
		q1 = n1//p1 
		break
	elif f(candidate) < n1:
		l = candidate + 1 
	else:
		r = candidate - 1

assert p1*q1 == n1 and isPrime(p1) and isPrime(q1)

### Part 2
- Nhìn vào hàm `genprime2()`

def genprimes2():
    ok =  btl(b'd4rkn19ht_w4s_h3r3')
    while True:
        p = getPrime(512)
        q = ok *p +  randint(pow(2,255), pow(2, 256) - 1)
        if isPrime(q):
            return p, q 

- Ta thấy đề bài gen `q = ok*p + x` với x rất nhỏ so với p và q. Từ khóa giúp ta giải quyết ở đây chính là "rất nhỏ". Vì x "rất nhỏ" tức `q - ok*p` rất nhỏ. Do đó nếu ta nhân `n` với `ok` sẽ được số có 2 factor rất "gần" nhau. Ta có 1 thuật toán để phân tích những số như vậy, nó là [Fermat's factorization algorithm](https://fermatattack.secvuln.info/). Mình có tham khảo implementation ở [đây](https://github.com/truong92cdv/ctf_tool/blob/master/RsaCtfTool/fermat.py)

ok = bytes_to_long(b'd4rkn19ht_w4s_h3r3')
def isqrt(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x


def fermat(n):
    a = isqrt(n)
    b2 = a*a - n
    b = isqrt(n)
    count = 0
    while b*b != b2:
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2)
        count += 1
    p = a+b
    q = a-b
    assert n == p * q
    return p, q
n = n2 * ok 

p2, q2 = fermat(n)
q2 = q2 // ok 
assert p2*q2 == n2

### Part 3
- Nhìn vào 2 hàm `genprime3` và `gensmoothprime`

def gensmoothprime(bitlen, smoothness ):
    p = 2
    while (bitlen - p.bit_length()) > 2*smoothness:
        p = p * getPrime(smoothness)
    while True:
        bit = bitlen - p.bit_length()
        q = p * getPrime(bit//2) * getPrime(bit//2)
        if isPrime(q+1):
            return q + 1

def genprimes3():
    p = gensmoothprime(1024, 18)
    q = getPrime(1024)
    return p, q

- `p` được tạo từ hàm `gensmoothprime`, nhìn tên hàm thì ta dễ dàng biết mục đích nó làm gì và kiểu attack mình nên sử dụng là gì ở đây rồi đúng không =))). Đó là [Pollard's p-1](https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm)
> Mình sẽ implement hơi khác, thay vì xét toàn bộ j từ 2 tới bound thì mình chỉ xét các prime trên khoảng đó nhằm tiết kiệm số lần lặp.

from sympy import primerange
def polard_p_1(n, bound, max_exponent = None):
	if not max_exponent:
		max_exponent = 100 # choose bigger if u want
	prime = list(primerange(0,bound))
	m = 2
	for p in tqdm(prime):
		m = pow(m,pow(p,max_exponent),n)
		g = GCD(m - 1, n)
		if 1 < g < n:
			return g

p3 = polard_p_1(n3,2**18)
# p3 = 34302378001524268765721972889612653650983341291105371564207304500444850849226646030402506299652849180254819837296965711073149728603386400320040960818141113159855391067137019913846389938820834584083933687632175802958740132807718353391277806953920781509000521492461678009894860124162620619971833231615146852679
q3 = n3//p3
assert n3 == p3*q3
print(p3)
print(q3)

- Full solve

n1 = 211455521422020258783290017786833203694890601609542266572436689343387975873851663714826878488933573192758684466992443467575547666866148922830759132550414787179476403839100558419435557761636689850531979449862710134176010990573930089590543054663710498337567392413667902039363909716461423780921274784964048201261615244456563
e1 = 65537
c1 = 155418209978735408945517158166215780665415976629503903289584371825469697474469343720429315161504813773884932054871475346668022365253354309172510206853178681311268276851307960534785621244053849034169181072159335358550066055001840012695163671358539407821466685911438264884558726042393234252026079141088412007925402309181305
n2 = 1556419694977074420750239158897899631469826483957603939360368802327653630130981740036704150568796140290764000336428428488285423441865456015063486859824968187861539255264172310760537054139580128911600222858752984388304888111133106642922872407380377205772921378334031465881260979584977844288646384759864854775319523643613669692525031061599635491191498349

e2 = 65537
c2 = 814853698863591711616294956238631732573315851128484059387714793653181142383960479109157116069042282680832432053035109228714088507195567442154173032565469226942472090529328452132107943811408737294966578597692504678621473678055677609726740706850101983317960048448310998482312534333138456629762423325180613370693789240335308211213919600203990152520269025
n3 = 3993193907009943655630571031029488807651266438317568663483791746675374480884841475846941780549436733527157152622547743749865993415756807272582234085567951844648680787553253234423625845487826860988553995685527888492246204541421972864421335071765915451441830451498783420498130746986190652474314925189790891632266843591316211442273150964679169025504263980998481563244440787983555826067831717381311713782245979706619729054780078140296347468352791645492038792748920064037539868854753851135845319699845278305219332816250661827780267748573080430881938636610669022125346981839219169743131435780102335356123362116245634666019
e3 = 65537
c3 = 3038260918139845903074652597748841639455687273919226184257585711899516866664647973911092701304989844742443789090639605869993114311780464276426644555372038897779711647654834593931443264191893734612861453608801393950275435588799921767292542465787248532376276920658237311699672046201586224320506731637656286323866642053860452092904286129575302841341060886728622409806032791873719801623552252933762835350644368024272122563384527013406586202093124271242114121604135749274213770981572917875049020014649835636798619380796309394877135974984198332443434780773175200892355325975094655738946378919412649188846687302492873166182

from Crypto.Util.number import *
from math import floor
# from sage.all import *
from tqdm import tqdm
from sympy import primerange
# ----part1----
def f(can):
	p = can 
	q = p + int(str(p), 12) + 1
	return p*q

l = 2**511
r = 2**512

while True:

	candidate = floor((l+r)//2)
	# print(candidate)
	if candidate >= 2**512:
		break
	if f(candidate) == n1:
		p1 = candidate
		q1 = n1//p1 
		break
	elif f(candidate) < n1:
		l = candidate + 1 
	else:
		r = candidate - 1

assert p1*q1 == n1 and isPrime(p1) and isPrime(q1)

d = pow(65537,-1,(p1-1)*(q1-1))
part1 = long_to_bytes(pow(c1,d,n1))
print(part1)

# ---part2---
ok = bytes_to_long(b'd4rkn19ht_w4s_h3r3')
def isqrt(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x


def fermat(n):
    a = isqrt(n)
    b2 = a*a - n
    b = isqrt(n)
    count = 0
    while b*b != b2:
        a = a + 1
        b2 = a*a - n
        b = isqrt(b2)
        count += 1
    p = a+b
    q = a-b
    assert n == p * q
    return p, q
n = n2 * ok 

p2, q2 = fermat(n)
q2 = q2 // ok 
assert p2*q2 == n2
part2 = long_to_bytes(pow(c2,pow(65537,-1,(p2-1)*(q2-1)),n2))
print(part2)

# ---part3---

def polard_p_1(n, bound, max_exponent = None):
	if not max_exponent:
		max_exponent = 100 # choose bigger if u want
	prime = list(primerange(0,bound))
	m = 2
	for p in tqdm(prime):
		m = pow(m,pow(p,max_exponent),n)
		g = GCD(m - 1, n)
		if 1 < g < n:
			return g

# p3 = polard_p_1(n3,2**18)
# it takes me 5m 55s to calculate p3 :) so i enter its value for saving time :v
p3 = 34302378001524268765721972889612653650983341291105371564207304500444850849226646030402506299652849180254819837296965711073149728603386400320040960818141113159855391067137019913846389938820834584083933687632175802958740132807718353391277806953920781509000521492461678009894860124162620619971833231615146852679
q3 = n3//p3
assert n3 == p3*q3
print(p3)
print(q3)
part3 = long_to_bytes(pow(c3,pow(65537,-1,(p3-1)*(q3 - 1)),n3))
print(part3)
print(part1 + part2 + part3)