## choose_the_param
```python
#!/usr/bin/python3
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import os
from secret import flag
padded_flag = os.urandom(200) + flag + os.urandom(200)
m = bytes_to_long(padded_flag)
def chal():
print("""Choose your parameter
Enter the bit length of the prime!
I'll choose two prime of that length, and encrypt the flag using rsa.
Try decrypt the flag!
""")
while True:
bits = input("Enter the bit length of your primes> ")
try:
bit_len = int(bits)
except:
print("please enter a valid intergar")
continue
p1 = getPrime(bit_len)
p2 = getPrime(bit_len)
n = p1 * p2
e = 65537
c = pow(m, e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
if __name__ == "__main__":
chal()
```
Bài này sẽ được gửi số bit của 2 giá trị p và q, sau đó m sẽ được mã hóa bằng giá trị n đó.
Giờ ta sẽ gửi các bit nhỏ để có thể factor được giá trị n. Khi đó ta sẽ tìm được lại private key. Khi đó ta có được như sau:
$$
\begin{cases}
m \equiv m_1 \mod{n_1} \\
m \equiv m_2 \mod{n_2} \\
m \equiv m_3 \mod{n_3} \\
\vdots \\
m \equiv m_{n-1} \mod{n_{n-1}} \\
m \equiv m_n \mod{n_n}
\end{cases}
$$
Khi đó ta sẽ dùng CRT để có thể recover lại được giá trị m.
Trước hết, ta cần phải tính toán số bit cần gửi sao cho hợp lý nhất.
Giá trị m đã có 400 bytes = 3200 bits padding, flag cứ cho như là 100 bytes = 800 bits tổng là 4000 bits, giờ ta sẽ gửi 35 lần 64 bits cho chắc cú nheeeee.
```python
from pwn import *
from Crypto.Util.number import *
from sage.all import *
from tqdm import *
io = remote('gold.b01le.rs', 5001)
ms = []
ns = []
cs = []
for i in trange(35):
io.recvuntil(b'Enter the bit length of your primes> ')
io.sendline(b'64')
io.recvuntil(b'n = ')
n = int(io.recvuntil(b'\n',drop=True),16)
io.recvuntil(b'e = ')
e = int(io.recvuntil(b'\n',drop=True),16)
io.recvuntil(b'c = ')
c = int(io.recvuntil(b'\n',drop=True),16)
cs.append(c)
ns.append(n)
e = 65537
for i in range(len(cs)):
n = ns[i]
c = cs[i]
factors = factor(n)
p = int(factors[0][0])
q = int(factors[1][0])
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
ms.append(m)
flag = crt(ms,ns)
print(long_to_bytes(flag)[200:300])
```
**Flag: bctf{dont_let_the_user_choose_the_prime_length_>w<}**
## Half-Big-Rsa
```python
import math
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
import os
num_bits = 4096
e = (num_bits - 1) * 2
n = getPrime(num_bits)
with open("flag.txt","rb") as f:
flag = f.read()
m = bytes_to_long(flag)
c = pow(m, e, n)
print(c)
with open("output.txt", "w") as f:
f.write("e = {0}\n".format(e))
f.write("n = {0}\n".format(n))
f.write("c = {0}\n".format(c))
```
```python
e = 8190
n = 665515140120452927777672138241759151799589898667434054796291409500701895847040006534274017960741836352283431369658890777476904763064058571375981053480910502427450807868148119447222740298374306206049235106218160749784482387828757815767617741823504974133549502118215185814010416478030136723860862951197024098473528800567738616891653602341160421661595097849964546693006026643728700179973443277934626276981932233698776098859924467510432829393769296526806379126056800758440081227444482951121929701346253100245589361047368821670154633942361108165230244033981429882740588739029933170447051711603248745453079617578876855903762290177883331643511001037754039634053638415842161488684352411211039226087704872112150157895613933727056811203840732191351328849682321511563621522716119495446110146905479764695844458698466998084615534512596477826922686638159998900511018901148179784868970554998882571043992165232556707995154316126421679595109794273650628957795546293370644405017478289280584942868678139801608538607476925924119532501884957937405840470383051787503858934204828174270819328204062103187487600845013162433295862838022726861622054871029319807982173856563380230936757321006235403066943155942418392650327854150659087958008526462507871976852849
c = 264114212766855887600460174907562771340758069941557124363722491581842654823497784410492438939051339540245832405381141754278713030596144467650101730615738854984455449696059994199389876326336906564161058000092717176985620153104965134542134700679600848779222952402880980397293436788260885290623102864133359002377891663502745146147113128504592411055578896628007927185576133566973715082995833415452650323729270592804454136123997392505676446147317372361704725254801818246172431181257019336832814728581055512990705620667354025484563398894047211101124793076391121413112862668719178137133980477637559211419385463448196568615753499719509551081050176747554502163847399479890373976736263256211300138385881514853428005401803323639515624537818822552343927090465091651711036898847540315628282568055822817711675290278630405760056752122426935056309906683423667413310858931246301024309863011027878238814311176040130230980947128260455261157617039938807829728147629666415078365277247086868327600962627944218138488810350881273304037069779619294887634591633069936882854003264469618591009727405143494184122164870065700859379313470866957332849299246770925463579384528152251689152374836955250625216486799615834558624798907067202005564121699019508857929778460
```
Bài này mình có tham khảo code của [**Writeup**](https://hackmd.io/@65XZ9ZfDTb21FI-0un6Zhg/BJj1FqYUK#Defective-RSA) này.
```python
def roots_of_unity(e, phi, n, rounds=500):
# Divide common factors of `phi` and `e` until they're coprime.
phi_coprime = phi
while cun.GCD(phi_coprime, e) != 1:
phi_coprime //= cun.GCD(phi_coprime, e)
# Don't know how many roots of unity there are, so just try and collect a bunch
roots = set(pow(i, phi_coprime, n) for i in range(1, rounds))
assert all(pow(root, e, n) == 1 for root in roots)
return roots, phi_coprime
```
Solution của bài này là:
```python
from Crypto.Util.number import*
e = 8190
N = 665515140120452927777672138241759151799589898667434054796291409500701895847040006534274017960741836352283431369658890777476904763064058571375981053480910502427450807868148119447222740298374306206049235106218160749784482387828757815767617741823504974133549502118215185814010416478030136723860862951197024098473528800567738616891653602341160421661595097849964546693006026643728700179973443277934626276981932233698776098859924467510432829393769296526806379126056800758440081227444482951121929701346253100245589361047368821670154633942361108165230244033981429882740588739029933170447051711603248745453079617578876855903762290177883331643511001037754039634053638415842161488684352411211039226087704872112150157895613933727056811203840732191351328849682321511563621522716119495446110146905479764695844458698466998084615534512596477826922686638159998900511018901148179784868970554998882571043992165232556707995154316126421679595109794273650628957795546293370644405017478289280584942868678139801608538607476925924119532501884957937405840470383051787503858934204828174270819328204062103187487600845013162433295862838022726861622054871029319807982173856563380230936757321006235403066943155942418392650327854150659087958008526462507871976852849
c = 264114212766855887600460174907562771340758069941557124363722491581842654823497784410492438939051339540245832405381141754278713030596144467650101730615738854984455449696059994199389876326336906564161058000092717176985620153104965134542134700679600848779222952402880980397293436788260885290623102864133359002377891663502745146147113128504592411055578896628007927185576133566973715082995833415452650323729270592804454136123997392505676446147317372361704725254801818246172431181257019336832814728581055512990705620667354025484563398894047211101124793076391121413112862668719178137133980477637559211419385463448196568615753499719509551081050176747554502163847399479890373976736263256211300138385881514853428005401803323639515624537818822552343927090465091651711036898847540315628282568055822817711675290278630405760056752122426935056309906683423667413310858931246301024309863011027878238814311176040130230980947128260455261157617039938807829728147629666415078365277247086868327600962627944218138488810350881273304037069779619294887634591633069936882854003264469618591009727405143494184122164870065700859379313470866957332849299246770925463579384528152251689152374836955250625216486799615834558624798907067202005564121699019508857929778460
def roots_of_unity(e, phi, n, rounds=500):
# Divide common factors of `phi` and `e` until they're coprime.
phi_coprime = phi
while GCD(phi_coprime, e) != 1:
phi_coprime //= GCD(phi_coprime, e)
# Don't know how many roots of unity there are, so just try and collect a bunch
roots = set(pow(i, phi_coprime, n) for i in range(1, rounds))
return roots, phi_coprime
roots,phi = roots_of_unity(e, N-1, N)
d = pow(e, -1,phi)
a = pow(c,d,N)
for root in roots:
flag = long_to_bytes((root*a) % N)
if b'bctf' in flag:
print(flag)
```
**Flag: bctf{Pr1M3_NUM83r5_4r3_C001_bu7_7H3Y_4r3_57r0N6_0N1Y_WH3N_7H3Y_4r3_MU171P113D_3V3N_1F_7H3Y_4r3_b1g}**
## Fetus-rsa
```python
from Crypto.Util.number import bytes_to_long, getPrime, isPrime
from sage.all import matrix, Zmod
from flag import flag
def nextPrime(prim):
if isPrime(prim):
return prim
else:
return nextPrime(prim+1)
p1 = getPrime(128)
p2 = nextPrime(p1 * 1)
p3 = nextPrime(p2 * 3)
p4 = nextPrime(p3 * 3)
p5 = nextPrime(p4 * 7)
primes = [p1, p2, p3, p4, p5]
n = p1 * p2 * p3 * p4 * p5
fragments = [bytes_to_long(flag[5*i:5*i+5]) for i in range(25)]
e = 31337
topG = matrix(Zmod(n), [[fragments[5*i + j] for j in range(5)] for i in range(5)])
bottomG = topG ** e
with open("output.txt", "w") as file:
file.write(f"n = {n}\n\n")
file.write("Ciphertext Matrix:\n\n")
for row in bottomG:
for num in row:
file.write(str(num) + " ")
file.write("\n\n")
```
```python
n = 515034877787990680304726859216098826737559607654653680536655175803818486402820694536785452537613547240092505793262824199243610743308333164103851365420630137187276313271869670701737383708742526677
Ciphertext Matrix:
247714609729115034577268860647809503348452679955541765864525644036519903244610407544592438833012659821363982836831477850927621505723503202914955484784761468695340160789629882004055804409080695867 331625142917011732363496584111977497826539848810596405639715608289185491230192921594585113936516744954068559616963395888825085234835086592835782522823153199824647815923311303312529222423487842184 55437288185949549641415195099137917985198178875175317590356850868652628068256771878957686344008331498612071069691453711091201145528626750365270496738628725699281809961803599963127434726167609435 514660916099185196031776141538776359410382339048282799109733569738126784171011249457518653961429789338579350043906060924939800730829826389077489637524528092592193187169747629063004980325000389554 432908737089369750416720813650504950741227543859957288298129130571557758647818791153409184252564534925607409378801765727301405467691263041798341098982058861749568674152447781841703730861074171486
104171307746966345345857299403770324392522334886728513788970028646835780770090370816961277474173463662053179135418083415763603092683905102293259569143230591686555033557056635683615214642425173517 281995809329109899498417283591516891672267505291547187769414960759245222376040526984420670509684233818236456944690830422135256653807646369718495017051487254128669606210585168140190305476396414836 448210297704655248563230644309382726474650012116320871206976601497778210586480264554625801730855872456388662647389829317946932942681549854741993522145903386318540208729036379511878276729211658861 399193502999265141959383452857091791757532600793923480036782294759164203783245516880539439411508616363396395258745387111132143827593272610961260623660064934154238955120293971424750525097551648180 448909699677346701183758951038319440723583288307818355958233994863175886710495171317606803723159576428485212274726596045235998230677229224379125716760136092533604817049730746550292371970711497032
10383824979618791372207750490225860866360446289011667617367731854443817405025701872398853456038612719059056477356275566409859556622099910727870579661815727983662245805512246175424036918556245316 3042212133475156282375315438954933898496627384941849067508473136817427432524109900983912625376319043681252528210663860374506706029777992048856493297280439498831646567645849063286941560111486091 303901520908845557762276355500926092138935908381564097855093945643653520650021074626397106363589843089839561176214123648988682404983806374183953260408815900582907133898417354283905163971086566554 385414980407334346707284477209921028250475161696209076212214696858828374481374774762344617183479700018626970039426895699261230837253656355202103718574806419224338390036737550645417315148014935208 172437598435610362668691083369422058178612127588567286669952095014310724933793758671802664372505747578789080527221296229242137567445447449560987571505575740311394634799579166058011734727404038041
459726837943530454128170171077760511486009487765694189770202436458018005866133157577824055980174845256397040485330898693944501922148000904627621334536523927325451030816598478315788682056071758797 318766645374831072244114015670117551595181174553017703335802708316885112551395705202907958737214488185739954176085085611052360624160681549561415131064529778955941226762589967588568203157586014646 485361005374731090711430490780588207888099824436671620066599360058262282812311497518237782819588602409946446254729349547214950452718084694554650900064587640931729162822096611158015732013679765115 442488981185685119421099225895492967006907103880489001122993678677306129218035946328038537612725434883858276836497639772750576738969390151812664236525222680918250542360570252193283310559820113337 294017672174100375503817924437430140826863578191649796300540064690169411498877218939778928997294952104395700469268399214549954967540991489929488976904050382049934179672641195866868009511101289284
394288980150370144394508377797340867635320394706221783789360450886862330500083595146934277232717671435601428999455723360437715407992902972393377872146437245909234935183690525050686313034961250106 174537062539250527750306397111216900339583030576848484858177223085331307339246744122607759453386390209872407563526999813562242756044330978624067706177762337375480164381575660119163723806663394768 167378817268639407255382001659131271694745168867873206910416580974376327982114272760583238198872032832961214636912981493082249850676384736073683786291369414678559758485110038329085571864758144806 479478683656492256273719495784577239188841595512723735000697935028851355713461770920044121053505358284609828319371252306609569657211738503902322975549066701614139339082341370785743668742796520457 468925056254460005965810812432459057693038841264871939568448625553319440670497244388153862616274082271409346691280049609288322448351851208172939513793874861880752049454593563028452119997997329883
```
Bài này không có gì cả, chỉ cần tìm được giá trị p rồi tìm lại khóa p rồi sẽ thu được flag thôi.
$$
n = p_1*p_2*p_3*p_4*p_5
$$
$$
p_1 = p_2
$$
$$
p_3 \approx 3*p_1
$$
$$
p_4 \approx 9*p_1
$$
$$
p_5 \approx 63*p_1
$$
Từ đó ta có thể bruteforce giá trị p như sau:
```python
from gmpy2 import iroot
n = 515034877787990680304726859216098826737559607654653680536655175803818486402820694536785452537613547240092505793262824199243610743308333164103851365420630137187276313271869670701737383708742526677
a = iroot(n // (27*63), 5)[0]
for i in range(-10000, 10000):
if n % (a+i) == 0:
p1 = a + i
print(p1)
break
```
Từ đó
$$
p_1 = 197800081090910969169502702324035680453
$$
Hoặc bạn cũng có thể tham khảo tìm kiếm nhị phân như sau
```python
def binary_search(n):
l = 2**126
r = 2**129
while l < r:
mid = (l+r)//2
if n % mid == 0:
return mid
N = gen_modulus(mid)
if N > n:
r = mid - 1
else:
l = mid + 1
return None
```
Sau khi tìm được các số nguyên tố rồi, ta gặp một vấn đề nữa là tìm tolient. Mình có đọc được [**writeup**](https://writeup.gldanoob.dev/bitsctf/) này và tìm được hướng giải quyết.
```python
from Crypto.Util.number import *
from sage.all import Matrix, Zmod
def group_p(prime):
r = 1
for i in range(5):
r *= (prime**5 - prime**i)
return r
def nextPrime(prim):
if isPrime(prim):
return prim
else:
return nextPrime(prim+1)
p1 = 197800081090910969169502702324035680453
p2 = nextPrime(p1 * 1)
p3 = nextPrime(p2 * 3)
p4 = nextPrime(p3 * 3)
p5 = nextPrime(p4 * 7)
primes = [p1, p2, p3, p4, p5]
n = p1 * p2 * p3 * p4 * p5
print(n)
M = Matrix(Zmod(n), [
[247714609729115034577268860647809503348452679955541765864525644036519903244610407544592438833012659821363982836831477850927621505723503202914955484784761468695340160789629882004055804409080695867, 331625142917011732363496584111977497826539848810596405639715608289185491230192921594585113936516744954068559616963395888825085234835086592835782522823153199824647815923311303312529222423487842184 ,55437288185949549641415195099137917985198178875175317590356850868652628068256771878957686344008331498612071069691453711091201145528626750365270496738628725699281809961803599963127434726167609435 ,514660916099185196031776141538776359410382339048282799109733569738126784171011249457518653961429789338579350043906060924939800730829826389077489637524528092592193187169747629063004980325000389554 ,432908737089369750416720813650504950741227543859957288298129130571557758647818791153409184252564534925607409378801765727301405467691263041798341098982058861749568674152447781841703730861074171486 ],
[104171307746966345345857299403770324392522334886728513788970028646835780770090370816961277474173463662053179135418083415763603092683905102293259569143230591686555033557056635683615214642425173517, 281995809329109899498417283591516891672267505291547187769414960759245222376040526984420670509684233818236456944690830422135256653807646369718495017051487254128669606210585168140190305476396414836 ,448210297704655248563230644309382726474650012116320871206976601497778210586480264554625801730855872456388662647389829317946932942681549854741993522145903386318540208729036379511878276729211658861 ,399193502999265141959383452857091791757532600793923480036782294759164203783245516880539439411508616363396395258745387111132143827593272610961260623660064934154238955120293971424750525097551648180 ,448909699677346701183758951038319440723583288307818355958233994863175886710495171317606803723159576428485212274726596045235998230677229224379125716760136092533604817049730746550292371970711497032 ],
[10383824979618791372207750490225860866360446289011667617367731854443817405025701872398853456038612719059056477356275566409859556622099910727870579661815727983662245805512246175424036918556245316, 3042212133475156282375315438954933898496627384941849067508473136817427432524109900983912625376319043681252528210663860374506706029777992048856493297280439498831646567645849063286941560111486091 ,303901520908845557762276355500926092138935908381564097855093945643653520650021074626397106363589843089839561176214123648988682404983806374183953260408815900582907133898417354283905163971086566554 ,385414980407334346707284477209921028250475161696209076212214696858828374481374774762344617183479700018626970039426895699261230837253656355202103718574806419224338390036737550645417315148014935208 ,172437598435610362668691083369422058178612127588567286669952095014310724933793758671802664372505747578789080527221296229242137567445447449560987571505575740311394634799579166058011734727404038041 ],
[459726837943530454128170171077760511486009487765694189770202436458018005866133157577824055980174845256397040485330898693944501922148000904627621334536523927325451030816598478315788682056071758797 ,318766645374831072244114015670117551595181174553017703335802708316885112551395705202907958737214488185739954176085085611052360624160681549561415131064529778955941226762589967588568203157586014646 ,485361005374731090711430490780588207888099824436671620066599360058262282812311497518237782819588602409946446254729349547214950452718084694554650900064587640931729162822096611158015732013679765115 ,442488981185685119421099225895492967006907103880489001122993678677306129218035946328038537612725434883858276836497639772750576738969390151812664236525222680918250542360570252193283310559820113337 ,294017672174100375503817924437430140826863578191649796300540064690169411498877218939778928997294952104395700469268399214549954967540991489929488976904050382049934179672641195866868009511101289284 ],
[394288980150370144394508377797340867635320394706221783789360450886862330500083595146934277232717671435601428999455723360437715407992902972393377872146437245909234935183690525050686313034961250106 , 174537062539250527750306397111216900339583030576848484858177223085331307339246744122607759453386390209872407563526999813562242756044330978624067706177762337375480164381575660119163723806663394768 ,167378817268639407255382001659131271694745168867873206910416580974376327982114272760583238198872032832961214636912981493082249850676384736073683786291369414678559758485110038329085571864758144806 ,479478683656492256273719495784577239188841595512723735000697935028851355713461770920044121053505358284609828319371252306609569657211738503902322975549066701614139339082341370785743668742796520457 , 468925056254460005965810812432459057693038841264871939568448625553319440670497244388153862616274082271409346691280049609288322448351851208172939513793874861880752049454593563028452119997997329883 ]
])
e = 31337
phi = group_p(p1)*group_p(p2)*group_p(p3)*group_p(p4)*group_p(p5)
d = pow(e,-1,phi)
topG = M**d
for row in topG:
for element in row:
print(long_to_bytes(int(element)).decode(), end='')
```
**Flag: bctf{c0ngr4ts_y0u_35c4p3d_th3_m4tr1c3s, but really how? what color is your honda civic? sorry i just need to make this long.}**
## Count_the_Counter
```python
#!/bin/python3
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from secret import flag
import os
def Encrypt(key, message, nonce):
cipher = AES.new(key, AES.MODE_CTR, nonce=long_to_bytes(nonce))
return cipher.encrypt(message).hex()
def chal():
key = os.urandom(16)
print("Treat or Trick, count my thing. ")
nonce_counter = 1
print(Encrypt(key, flag, nonce_counter))
while True:
nonce_counter += 1
to_enc = input("Give me something to encrypt: ")
print(Encrypt(key, bytes.fromhex(to_enc), nonce_counter))
if __name__ == "__main__":
chal()
```
Nonce sau mỗi khi encrypt thì sẽ tăng lên 1 giá trị, thế nhưng nó sẽ lặp lại lúc này
Giờ mình có thể chạy vòng for như bình thường để giải thôi, nhưng mà giải này nó set time nên chạy thế sẽ bị timeout. Giờ mình sẽ phải dùng \n để làm trick lỏ. Cảm ơn [@wan_04]() đã chỉ mình trick lỏ này.
```python
from pwn import*
io = remote("gold.b01le.rs",5002)
io.recvuntil(b'Treat or Trick, count my thing. \n')
flag_enc = io.recvuntil(b'\n',drop=True).decode()
flag_enc = bytes.fromhex(flag_enc)
payload = ('aa'*96)
io.recvuntil(b'Give me something to encrypt: ')
io.sendline(('\n').encode() * 253)
data = io.recvuntil(b'\n',drop=True).decode()
print(data)
print(flag_enc.hex())
io.interactive()
```
Sau đó nhập 96 byte "aa" vào
Giờ lấy flag_enc phía trên, lướt lên trên là thấy xong chạy code
```python
from pwn import*
flag_enc = bytes.fromhex("61712d038c005b74cca284c5162b6ad13785d57daf0bb3e3092849f9101520e562d0b316ba9a94eef56c832c89d75e96b280e5d57d724a86d68d83afcc21824386001d7256bdf1b00f1686d888b972fedd6eb8")
a = bytes.fromhex("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
c = bytes.fromhex("a9b8f3cf5dde99bb146d7106cfdea124ef4a1ea46acf462fccf0bc21dbd1ee20a52577d37e535b1b3ea84dd954148054474c2607b2bcbf4019494e710ed4108a1ac8d1ed9d2668239dd81d141377e16111f56f3d49ab57ed25dc945532d4220b")
print(xor(xor(a,c),flag_enc))
```
**Flag: bctf{there_is_a_reason_for_random_nonce_and_with_fixed_length_8c6bf5a1398d1f1d95f1}**
## RC4
```python
import random
from Crypto.Util.number import getPrime, isPrime, bytes_to_long, long_to_bytes
"""
Key-scheduling algorithm (KSA)
"""
def KSA(key):
S = [i for i in range(0, 256)]
i = 0
for j in range(0, 256):
i = (i + S[j] + key[j % len(key)]) % 256
S[i] ^= S[j] ## swap values of S[i] and S[j]
S[j] ^= S[i]
S[i] ^= S[j]
return S
"""
Pseudo-random generation algorithm (PRGA)
"""
def PGRA(S):
i = 0
j = 0
while True: ## while GeneratingOutput
i = (1 + i) % 256
j = (S[i] + j) % 256
S[i] ^= S[j] ## swap values of S[i] and S[j]
S[j] ^= S[i]
S[i] ^= S[j]
yield S[(S[i] + S[j]) % 256]
if __name__ == '__main__':
FLAG = 'bctf{REDACTED}'
print("Would you like to pad the plaintext before encrypting it?")
print("(Just hit enter if you do not want to add any padding(s).)")
Padding = input()
input_text = ''
input_text += Padding
input_text += FLAG
plaintext = [ord(char) for char in input_text]
key = long_to_bytes(random.getrandbits(2048)) # 2048 bits = 256 bytes
key = [byte for byte in key]
S = KSA(key)
keystream = PGRA(S)
ciphertext = ''
for char in plaintext:
enc = char ^ next(keystream)
enc = (str(hex(enc)))[2:]
if len(enc) == 1: ## make sure they are all in the form 0x**
enc = '0' + enc
ciphertext += enc
print(ciphertext)
```
Chall này, ta thấy bị thay hai hàm KSA và PGRA vì hai hàm gốc là sẽ như thế này
```python
def KSA(key):
keylength = len(key)
S = range(256)
j = 0
for i in range(256):
j = (j + S[i] + key[i % keylength]) % 256
S[i], S[j] = S[j], S[i] # swap
return S
def PRGA(S):
i = 0
j = 0
while True:
i = (i + 1) % 256
j = (j + S[i]) % 256
S[i], S[j] = S[j], S[i] # swap
K = S[(S[i] + S[j]) % 256]
yield K
```
Giờ ta sẽ giảm 256 còn 16 byte cho key sẽ bé hơn nha
```python
import random
from Crypto.Util.number import getPrime, isPrime, bytes_to_long, long_to_bytes
"""
Key-scheduling algorithm (KSA)
"""
def KSA(key):
S = [i for i in range(0, 16)]
i = 0
for j in range(0, 16):
i = (i + S[j] + key[j % len(key)]) % 16
S[i] ^= S[j] ## swap values of S[i] and S[j]
S[j] ^= S[i]
S[i] ^= S[j]
return S
"""
Pseudo-random generation algorithm (PRGA)
"""
key_out = []
def PGRA(S):
i = 0
j = 0
while True: ## while GeneratingOutput
i = (1 + i) % 16
j = (S[i] + j) % 16
S[i] ^= S[j] ## swap values of S[i] and S[j]
S[j] ^= S[i]
S[i] ^= S[j]
key_out.append(S[(S[i] + S[j]) % 16])
yield S[(S[i] + S[j]) % 16]
if __name__ == '__main__':
FLAG = 'bctf{REDACTED}'
print("Would you like to pad the plaintext before encrypting it?")
print("(Just hit enter if you do not want to add any padding(s).)")
Padding = input()
input_text = ''
input_text += Padding
input_text += FLAG
plaintext = [ord(char) for char in input_text]
key = long_to_bytes(random.getrandbits(16*8)) # 2048 bits = 16 bytes
key = [byte for byte in key]
S = KSA(key)
print(key)
print(S)
keystream = PGRA(S)
ciphertext = ''
for char in plaintext:
enc = char ^ next(keystream)
enc = (str(hex(enc)))[2:]
if len(enc) == 1: ## make sure they are all in the form 0x**
enc = '0' + enc
ciphertext += enc
print(bytes.fromhex(ciphertext))
print(key_out)
```
Ta thấy rằng, thay vì hoán đổi như code cũ, vì S[i] và S[j] được hoán đổi cho nhau thông qua XOR, nếu chúng đạt đến điểm bằng nhau (nếu chuỗi rất dài thì cuối cùng chúng sẽ bằng nhau), chúng sẽ triệt tiêu lẫn nhau và bằng 0.
Giờ ta sẽ gửi thật nhiều giá trị, sau đó chạy bao giờ có flag thì thôi.
```python
from pwn import remote
import re
server = remote("gold.b01le.rs", 5004)
server.recvuntil(b'padding(s).)\n')
pad = b'aa'*100000
server.sendline(pad)
data = bytes.fromhex(server.recvline().strip().decode())
print(data)
```
**Flag: bctf{1f_gOOgL3_541D_1T_15_b4D_Th3n_1T_15_b4D}**
## schnore
```python
#!/usr/bin/python3
import sys
from Crypto.Util import number
from Crypto.Hash import SHA512
with open("flag.txt") as f:
flag = f.read()
# FIPS 186-4 Appendix A.1/A.2 compliant prime order q group and prime order p field
#from Crypto.PublicKey import DSA as FFCrypto
#(p,q,g) = FFCrypto.generate(2048).domain()
p = 32148430219533869432664086521225476372736462680273996089092113172047080583085077464347995262368698415917196323365668601969574610671154445337781821758494432339987784268234681352859122106315479086318464461728521502980081310387167105996276982251134873196176224643518299733023536120537865020373805440309261518826398579473063255138837294134742678213639940734783340740545998610498824621665838546928319540277854869576454258917970187451361767420622980743233300167354760281479159013996441502511973279207690493293107263225937311062981573275941520199567953333720369198426993035900390396753409748657644625989750046213894003084507
q = 25652174680121164880516494520695513229510497175386947962678706338003
g = 23174059265967833044489655691705592548904322689090091191484900111607834369643418104621577292565175857016629416139331387500766371957528415587157736504641585483964952733970570756848175405454138833698893579333073195074203033602295121523371560057410727051683793079669493389242489538716350397240122001054430034016363486006696176634233182788395435344904669454373990351188986655669637138139377076507935928088813456234379677586947957539514196648605649464537827962024445144040395834058714447916981049408310960931998389623396383151616168556706468115596486100257332107454218361019929061651117632864546163172189693989892264385257
def prove():
print("The oracles say that X is g^x and A is g^a. Be that as it may...")
print("Perhaps there exists a way to make their confidence sway!")
# (Sorry, can't choose a :)
A = 30210424620845820052071225945109142323820182565373787589801116895962027171575049058295156742156305996469210267854774935518505743920438652976152675486476209694284460060753584821225066880682226097812673951158980930881565165151455761750621260912545169247447437218263919470449873682069698887953001819921915874928002568841432197395663420509941263729040966054080025218829347912646803956034554112984570671065110024224236097116296364722731368986065647624353094691096824850694884198942548289196057081572758803944199342980170036665636638983619866569688965508039554384758104832379412233201655767221921359451427988699779296943487
h = SHA512.new(truncate="256")
h.update(number.long_to_bytes(g) + number.long_to_bytes(p) + number.long_to_bytes(A))
c = number.bytes_to_long(h.digest()) % p
z = int(input("a + cx = ")) % p
return (A,c,z)
def setup():
print("> I'm so sleepy, I almost forgot; we should share what we ought.")
print("> Just between you and me, can we agree on a verifying key...?")
X = int(input("> X = ")) % p
return X
def verify(A,c,z,X):
h = SHA512.new(truncate="256")
h.update(number.long_to_bytes(g) + number.long_to_bytes(p) + number.long_to_bytes(A))
cp = number.bytes_to_long(h.digest()) % p
if c != cp or pow(g, z, p) != ((A * pow(X, c, p)) % p):
print("> Oh, even my bleary eyes can tell your evidence is fau x !!")
print("> Are you sure that what you say is what you truly know?")
sys.exit()
else:
print("> ", end="")
print(flag)
if __name__ == "__main__":
(A,c,z) = prove()
X = setup()
verify(A,c,z,X)
```
Theo bài này, ta có
$$
g^z\equiv A*X^c \mod p
$$
Chuyển vế, ta được như sau:
$$
g^z*A^{-1} \equiv X^c \mod p
$$
Giờ ta sẽ làm tương tự như là RSA thôi. Tìm X với ciphertext là
$$
g^z*A^{-1}
$$
Thế nhưng,
$$
gcd(p-1,c) = 2
$$
, ta sẽ dựa vào [**Writeup**](https://medium.com/@motarekk/icmtc-ctf-finals-cryptography-challenge-writeup-broken-rsa-3d6c1715027a) này.
Từ đó ta sẽ tìm được khóa private và làm như bình thường.
```python
from Crypto.Util import number
from Crypto.Util.number import*
from Crypto.Hash import SHA512
from pwn import remote
from sage.all import *
import random
p = 32148430219533869432664086521225476372736462680273996089092113172047080583085077464347995262368698415917196323365668601969574610671154445337781821758494432339987784268234681352859122106315479086318464461728521502980081310387167105996276982251134873196176224643518299733023536120537865020373805440309261518826398579473063255138837294134742678213639940734783340740545998610498824621665838546928319540277854869576454258917970187451361767420622980743233300167354760281479159013996441502511973279207690493293107263225937311062981573275941520199567953333720369198426993035900390396753409748657644625989750046213894003084507
q = 25652174680121164880516494520695513229510497175386947962678706338003
g = 23174059265967833044489655691705592548904322689090091191484900111607834369643418104621577292565175857016629416139331387500766371957528415587157736504641585483964952733970570756848175405454138833698893579333073195074203033602295121523371560057410727051683793079669493389242489538716350397240122001054430034016363486006696176634233182788395435344904669454373990351188986655669637138139377076507935928088813456234379677586947957539514196648605649464537827962024445144040395834058714447916981049408310960931998389623396383151616168556706468115596486100257332107454218361019929061651117632864546163172189693989892264385257
A = 30210424620845820052071225945109142323820182565373787589801116895962027171575049058295156742156305996469210267854774935518505743920438652976152675486476209694284460060753584821225066880682226097812673951158980930881565165151455761750621260912545169247447437218263919470449873682069698887953001819921915874928002568841432197395663420509941263729040966054080025218829347912646803956034554112984570671065110024224236097116296364722731368986065647624353094691096824850694884198942548289196057081572758803944199342980170036665636638983619866569688965508039554384758104832379412233201655767221921359451427988699779296943487
h = SHA512.new(truncate="256")
h.update(number.long_to_bytes(g) + number.long_to_bytes(p) + number.long_to_bytes(A))
c = number.bytes_to_long(h.digest()) % p
phi = p - 1
phi_coprime = phi
while GCD(phi_coprime, c) != 1:
phi_coprime //= GCD(phi_coprime, c)
d = inverse(c,phi_coprime)
z = 0
gz = pow(g,z,p)
invA = pow(A,-1,p)
X = pow(gz*invA,d,p)
assert pow(g,z,p) == (((A * pow(X, c, p)) % p))
print (f"z= {z}, A= {A}")
print (f"X= {X}")
```
**Flag: bctf{t00_t1r3d_t0_n0t1c3_m1551n9_pub_k3y_1n_5t4t3m3nt}**
## shamir for dummies
```python
import os
import sys
import time
import math
import random
from Crypto.Util.number import getPrime, isPrime, bytes_to_long, long_to_bytes
def polynomial_evaluation(coefficients, x):
at_x = 0
for i in range(len(coefficients)):
at_x += coefficients[i] * (x ** i)
at_x = at_x % p
return at_x
flag = b'bctf{REDACTED}'
print("")
print("Thanks for coming in. I can really use your help.\n")
print("Like I said, my friend can only do additions. He technically can do division but he says he can only do it once a day.")
print("")
print("I need to share my secret using Shamir secret sharing. Can you craft the shares, in a way that my friend can recover it?\n")
print("")
print("Don't worry, I have the polynomial and I will do all the math for you.")
print("")
s = bytes_to_long(flag)
n = getPrime(4)
p = getPrime(512)
while p % n != 1:
p = getPrime(512)
print("Let's use \n")
print("n =", n)
print("k =", n)
print("p =", p)
print("")
coefficients = [s]
for i in range(1, n):
coefficients.append(random.randint(2, p-1))
print("Okay, I have my polynomial P(X) ready. Let me know when you are ready to generate shares with me.\n")
print("")
evaluation_points = []
shares = []
count = 1
while count < n+1:
print("Evaluate P(X) at X_{0} =".format(count))
print("> ", end="")
eval_point = int(input())
if eval_point % p == 0:
print("Lol, nice try. Bye.")
exit()
break
elif eval_point < 0 or eval_point > p:
print("Let's keep things in mod p. Please choose it again.")
else:
if eval_point not in evaluation_points:
evaluation_points.append(eval_point)
share = polynomial_evaluation(coefficients, eval_point)
shares.append(share)
count += 1
else:
print("You used that already. Let's use something else!")
print("Nice! Let's make sure we have enough shares.\n")
assert len(shares) == n
assert len(evaluation_points) == n
print("It looks like we do.\n")
print("By the way, would he have to divide with anything? (Put 1 if he does not have to)")
print("> ", end="")
some_factor = int(input())
print("Good. Let's send those over to him.")
for _ in range(3):
time.sleep(1)
print(".")
sys.stdout.flush()
sum_of_shares = 0
for s_i in shares:
sum_of_shares += s_i
sum_of_shares = sum_of_shares % p
sum_of_shares_processed = (sum_of_shares * pow(some_factor, -1, p)) % p
if sum_of_shares_processed == s:
print("Yep, he got my secret message!\n")
print("The shares P(X_i)'s were':")
print(shares)
print("... Oh no. I think now you'd know the secret also... Thanks again though.")
else:
print("Sorry, it looks like that didn't work :(")
```
Bài này, ta sẽ được dạng như sau:
Ta lấy
$$
n = 11
$$
làm ví dụ nha.
$$
\text{sumofshares} = s + c_1*x_1^1 + \cdot \cdot \cdot\ + c_{10}*x_1^{10}
$$
$$
\hspace{3.5cm} + s + c_1*x_2^1 + \cdot \cdot \cdot\ + c_{10}*x_3^{10}
$$
$$
....
$$
$$
....
$$
$$
....
$$
$$
\hspace{3.5cm} + s + c_1*x_{11}^1 + \cdot \cdot \cdot\ + c_{10}*x_{11}^{10}
$$
$$
\text{sumofshares} = s*11 + c_1*(x_1+x_2 + \cdot \cdot \cdot\ + x_{11})
$$
$$
....
$$
$$
....
$$
$$
....
$$
$$
\hspace{6cm} c_{10}*(x_1+x_2 + \cdot \cdot \cdot\ + x_{11})
$$
Ta sử dụng [**Root of unity modulo n**](https://en.wikipedia.org/wiki/Root_of_unity_modulo_n) để làm bài này tiếp.
```python
def roots_of_unity(e, phi, n):
phi_coprime = phi
while GCD(phi_coprime, e) != 1:
phi_coprime //= GCD(phi_coprime, e)
roots = pow(2, phi_coprime, n)
return roots
root= roots_of_unity(n,p-1, p)
```
Và dựa vào tính chất này
Để check var thì ta sẽ dùng sage để khai triển cho chuẩn.
```sage
from sage.all import *
x = var('x')
expression = (x-1)*(1 + x^1 + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10)
expanded_expression = expand(expression)
print(expanded_expression)
```
Giờ để chắc chắn một lần nữa thì hãy chạy code này.
```python
from pwn import remote
from Crypto.Util.number import long_to_bytes,GCD
from sage.all import PolynomialRing, GF
n = 11
k = 11
p = 7498373941443005268600959526786613028731880598939683509138235640278604496740931031938375197324165205081396179582326321596488546084897922903450124326943987
def roots_of_unity(e, phi, n):
phi_coprime = phi
while GCD(phi_coprime, e) != 1:
phi_coprime //= GCD(phi_coprime, e)
roots = pow(2, phi_coprime, n)
return roots
root = roots_of_unity(n,p-1, p)
print(f"Root of unity: {root}")
print((1 + pow(root,1,p) + pow(root,2,p) + pow(root,3,p) + pow(root,4,p) + pow(root,5,p) + pow(root,6,p) + pow(root,7,p) + pow(root,8,p) + pow(root,9,p) + pow(root,10,p))%p)
```
Giờ ta sẽ tìm root, sau đó sẽ gửi lần lượt như trên, từ đó
$$
\text{sumofshares} = s*n
$$
và ta sẽ gửi n để lấy được shares.
Có được shares rồi, ta giải hệ phương trình trong trường số nguyên tố p bình thường thôi.
```python
from pwn import remote
from Crypto.Util.number import long_to_bytes,GCD
from sage.all import *
server = remote("gold.b01le.rs", 5006)
server.recvuntil(b"Let's use \n\n")
n = int(server.recvline(b'n =').strip().split(b"=")[1])
k = int(server.recvline(b'k =').strip().split(b"=")[1])
p = int(server.recvline(b'p =').strip().split(b"=")[1])
def roots_of_unity(e, phi, n):
phi_coprime = phi
while GCD(phi_coprime, e) != 1:
phi_coprime //= GCD(phi_coprime, e)
roots = pow(2, phi_coprime, n)
return roots
root= roots_of_unity(n,p-1, p)
count = 0
lst_root = []
while count < n:
lst_root.append((root**count) % p)
server.sendlineafter(b'> ',str((root**count) % p).encode())
count += 1
server.recvuntil(b'> ')
server.sendline(str(n).encode())
server.recvuntil(b"The shares P(X_i)'s were':\n")
shares = list(map(int,server.recvline().strip().decode()[1:-1].split(", ")))
F = GF(p)
M = []
for element in lst_root:
row = []
for i in range(n):
row.append(F(element**i))
M.append(row)
M = Matrix(F,M)
shares = vector(F,shares)
out = M.solve_right(shares)
print(long_to_bytes(int(out[0])))
```
**Flag: bctf{P0LYN0m14l_1N_M0d_P_12_73H_P0W3Rh0u23_0F_73H_5h4M1r}**
Sign in with Wallet
Connect another wallet