# CryptoCTF 2024
> Author:堇姬
> Rank: 29th
# Warm-up 🤑
## Welcome! 👋
Crtl+c
Crtl+v
> CCTF{Harn3sS_Y0ur_CrYptO9rAphy_Pr0wEs5_💪_⚡_💥_🔥!}
# Easy 😁
## Alibos
### source code
```python=
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
```
pkey = 8582435512564229286688465405009040056856016872134514945016805951785759509953023638490767572236748566493023965794194297026085882082781147026501124183913218900918532638964014591302221504335115379744625749001902791287122243760312557423006862735120339132655680911213722073949690947638446354528576541717311700749946777
enc = 6314597738211377086770535291073179315279171595861180001679392971498929017818237394074266448467963648845725270238638741470530326527225591470945568628357663345362977083408459035746665948779559824189070193446347235731566688204757001867451307179564783577100125355658166518394135392082890798973020986161756145194380336
```
### 分析
給了你
$pkey、c$
$d=len(str(pkey))$
$c = (pkey + d^2 \times m) \pmod {10^d}$
$(c-pkey) \times inv(d^2) = m \pmod {10^d}$
簡單的移項，直接計算就可以了(要注意右邊他pad了很多的1要刪掉)
```python
def pad(m, d):
if len(str(m)) < d:
m = str(m) + '1' * (d - len(str(m)))
return int(m)
```
### script
```python=
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
```python=
#!/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()
```
### 分析
輸入八組的 $d_1、d_2$
要求
$md5(d_1 ⊕ d_2)\ne ae09d7510659ca40eda3e45ca70e9606$
並且
$md5(x1) ⊕ md5(x2) ⊕ md5(salt) = a483b30944cbf762d4a3afc154aad825$
```
a483b30944cbf762d4a3afc154aad825 -> emelinjulca
```
當下還真沒看出來這要怎麼解，後來才知道 $md5(salt) = a483b30944cbf762d4a3afc154aad825$，所以就只是要找八組碰撞的來解...
### 解法
https://github.com/cr-marcstevens/hashclash
直接拿八組送就可以了
> CCTF{mD5_h4Sh_cOlL!Si0N_CrYp7o_ch41lEnGe!!!}
# Medium 🤔
## Bada
```
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ 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:
```
### 分析
$f(x, y) = z$
對所有a b滿足
$f(a+1, b) = f(a, b) + a$
$f(a, b+1) = f(a, b) - b$
給定
$f(1,1)跟f(x,y)$，要求x跟y
這題其實很簡單，
$t=f(x,y)-f(1,1)$
$x=t+1$
$y=t$
因為我們可以知道
$f(x,y)=f(1,1)+(1+2+...+x-1)-(1+2+...+y-1)$
如果設成這樣可以得
$f(x,y)=f(1,1)+(1+2+...+t)-(1+2+...+t-1)$
$f(x,y)-f(1,1)=t$
得證
### script
```python=
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
```python=
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 \times q$
並產生了一個64 bytes 隨機字串，並拆成兩半m1、m2，來做加密
$C_1={m_1}^e \pmod {(p-1)(q-1)}$
$C_2={m_2}^e \pmod {(2p+1)(2q+1)}$
印出 $C_1、C_2$ 給你，如果你能提交正確的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
```python=
import gensafeprime
from Crypto.Util.number import *
while True:
a=gensafeprime.generate(1024)
if(isPrime(2*a+1)):
print(a)
```
找到
```
179038869479476343977624700131648035601030062609971358083068495264644773504891672033533628862180996104202480213255611201971674539999191838522787167917937277791863007890816459071795930442010669455816651153734397964768807485960692876685651034343992232617890851248047651749184487885382752475267482617769156174759
152626939093408062491455965189078085895710089466647132413566213985550098559310878828326396205570489809521107684567398503589855307057076999293252855393269557521587237138401310097549911211946862768385413685627911058536556141489179850863603684246330469754375715654686482993778608649026542257474853574317156591723
```
找到後直接搞就行了
### script
```python=
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())
```
```
┃ 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
```python=
#!/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
```
n = 8098851734937207931222242323719278262039311278408396153102939840336549151541408692581651429325092535316359074019383926520363453725271849258924996783681725111665666420297112252565291898169877088446887149672943461236879128453847442584868198963005276340812322871768679441501282681171263391133217373094824601748838255306528243603493400515452224778867670063040337191204276832576625227337670689681430055765023322478267339944312535862682499007423158988134472889946113994555274385595499503495488202251032898470224056637967019786473820952632846823442509236976892995505554046850101313269847925347047514591030406052185186963433
c = 7109666883988892105091816608945789114105575520302872143453259352879355990908149124303310269223886289484842913063773914475282456079383409262649058768777227206800315566373109284537693635270488429501591721126853086090237488579840160957328710017268493911400151764046320861154478494943928510792105098343926542515526432005970840321142196894715037239909959538873866099850417570975505565638622448664580282210383639403173773002795595142150433695880167315674091756597784809792396452578104130341085213443116999368555639128246707794076354522200892568943534878523445909591352323861659891882091917178199085781803940677425823784662
```
### 分析
想法就是直接枚舉，512bits大概是154、155 digits。
```python=
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，才可以拿到其他的)
```
7728751393377105569802455757436190501772466214587592374418657530064998056688376964229825501195065837843125232135309371235243969149662310110328243570065781
9688632098638681429535439991332657144752666147923336383829750592576742104399942931057096761773496510622226977570278994077236841491368959008277469453600569
```
```python=
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!}
## Nazdone
### source code
```python=
#!/usr/bin/env python3
from Crypto.Util.number import *
from random import *
from secret import params, flag
def sol(m, a, z):
p = m * (a - 1) % 2 + 1
while True:
R = list(range(1, a))
shuffle(R)
for r in R[:z]:
p += getRandomRange(0, 2) * m ** r
if isPrime(p):
return p
else:
p = m * (a - 1) % 2 + 1
p, q, r = [sol(*params) for _ in '007']
n = p * q * r
m = bytes_to_long(flag)
c = pow(m, params[0] ** 3 + params[2] - 2, n)
print(f'n = {n}')
print(f'c = {c}')
```
### output.txt
```
n = 301929748923678449872944933611657670834216889867340028357609265175830693931365828840717548752313862343315133541384709574659039910206634528428504034051556622114290811586746168354731258756502196637977942743110508997919976400864419640496894428180120687863921269087080600917900477624095004141559042793509244689248253036809126205146653922738685595903222471152317095497914809983689734189245440774658145462867680027337
c = 104375152140523502741159687674899095271676058870899569351687154311685938980840028326701029233383897490722759532494438442871187152038720886122756131781086198384270569105043114469786514257765392820254951665751573388426239366215033932234329514161827069071792449190823827669673064646681779764841034307000600929149689291216313319444583032339045277433847691961234044840927155960887984372868669401051358701522484473320
```
### 分析
未知的三個param -> $m、a、z$
$n=p \times q \times r$
$e=m^3+z-2$
$p、q、r$ 為三個質數
生成方式為:
有一個初始化的陣列
$R=[1、2、3、...、a]$ 並把他打亂
$R=[R_0、R_1、R_2、...、R_{a-1}]$
```python=
R = list(range(1, a))
shuffle(R)
```
之後以以下方式產生
$p、q、r= \displaystyle\sum_{i=0}^z b_i \times m^i$,
$b_i \in (0, 1)$
```python=
for r in R[:z]:
p += getRandomRange(0, 2) * m ** r
```
也就是構造一個多項式
$f(x)=b_0+b_1 \times x+b_2 \times x^2+...+b_z \times x^z$
$p、q、r=f(m)$
Sign in with Wallet
Connect another wallet