# corCTF 2022
- [ ] Có giải thích (Added explanation)
- [x] [tadpole](#tadpole---262-solves)
- [x] [luckyguess](#luckyguess---150-solves)
- [x] [exchange](#exchange---94-solves)
- [x] [hidE](#hidE---88-solves)
- [ ] [generous](#generous---49-solves)
- [ ] [corrupted-curves](#corrupted-curves---20-solves)
- [ ] [threetreasures](#threetreasures---19-solves)
## tadpole - 262 solves
> tadpoles only know the alphabet up to b... how will they ever know what p is?
Attachments:
1. tadpole.py
```python=0
from Crypto.Util.number import bytes_to_long, isPrime
from secrets import randbelow
p = bytes_to_long(open("flag.txt", "rb").read())
assert isPrime(p)
a = randbelow(p)
b = randbelow(p)
def f(s):
return (a * s + b) % p
print("a = ", a)
print("b = ", b)
print("f(31337) = ", f(31337))
print("f(f(31337)) = ", f(f(31337)))
```
* output.txt
```
a = 7904681699700731398014734140051852539595806699214201704996640156917030632322659247608208994194840235514587046537148300460058962186080655943804500265088604049870276334033409850015651340974377752209566343260236095126079946537115705967909011471361527517536608234561184232228641232031445095605905800675590040729
b = 16276123569406561065481657801212560821090379741833362117064628294630146690975007397274564762071994252430611109538448562330994891595998956302505598671868738461167036849263008183930906881997588494441620076078667417828837239330797541019054284027314592321358909551790371565447129285494856611848340083448507929914
f(31337) = 52926479498929750044944450970022719277159248911867759992013481774911823190312079157541825423250020665153531167070545276398175787563829542933394906173782217836783565154742242903537987641141610732290449825336292689379131350316072955262065808081711030055841841406454441280215520187695501682433223390854051207100
f(f(31337)) = 65547980822717919074991147621216627925232640728803041128894527143789172030203362875900831296779973655308791371486165705460914922484808659375299900737148358509883361622225046840011907835671004704947767016613458301891561318029714351016012481309583866288472491239769813776978841785764693181622804797533665463949
```
Phân tích file `tadpole.py` ta thấy có hàm `f()` với công thức: $f\left(x\right) = ax + b$
File `output.txt` cho ta biết $a$, $b$, $f(31337)\bmod{p}$ (mình sẽ gọi $f_1$), $f(f(31337))\bmod{p}$ (cái này thì $f_2$). Flag chính là số chia $p$ dùng để chia dư sau khi tính $f(x)$. Cách giải:
* Ta có:
\begin{align}
f(31337) &= 31337a + b \\
&= k_1p + f_1 \\
\iff f(31337) - f_1 &= k_1p \\
\end{align}
* Ta lại có:
\begin{align}
f(f(31337)) &= f_1a + b \\
&= k_2p + f_2 \\
\iff f(f(31337)) - f_2 &= k_2p \\
\end{align}
* Kết luận:
\begin{align}
\mathit{gcd}\left(f(31337)-f_1, f(f(31337))-f_2\right) &= \mathit{gcd}(k_1, k_2)p \\
\iff p &= \frac{\mathit{gcd}\left(f(31337)-f_1, f(f(31337))-f_2\right)}{\mathit{gcd}(k_1, k_2)}
\end{align}
Vì bài này $f_1$ có $x = 31337$ do đó $k_1$ còn bé hơn 31337. Nên nếu $\mathit{gcd}(k_1, k_2)$ không bằng 1 thì ta cũng có thể bruteforce tìm $p$ được.
Script bằng **python**:
```python=0
from gmpy2 import gcd, is_prime
from Crypto.Util.number import long_to_bytes
a = 7904681699700731398014734140051852539595806699214201704996640156917030632322659247608208994194840235514587046537148300460058962186080655943804500265088604049870276334033409850015651340974377752209566343260236095126079946537115705967909011471361527517536608234561184232228641232031445095605905800675590040729
b = 16276123569406561065481657801212560821090379741833362117064628294630146690975007397274564762071994252430611109538448562330994891595998956302505598671868738461167036849263008183930906881997588494441620076078667417828837239330797541019054284027314592321358909551790371565447129285494856611848340083448507929914
f1= 52926479498929750044944450970022719277159248911867759992013481774911823190312079157541825423250020665153531167070545276398175787563829542933394906173782217836783565154742242903537987641141610732290449825336292689379131350316072955262065808081711030055841841406454441280215520187695501682433223390854051207100
f2= 65547980822717919074991147621216627925232640728803041128894527143789172030203362875900831296779973655308791371486165705460914922484808659375299900737148358509883361622225046840011907835671004704947767016613458301891561318029714351016012481309583866288472491239769813776978841785764693181622804797533665463949
def f(s):
return a * s + b
p = gcd(f(f1)-f2, f(31337)-f1)
k = 2
while not is_prime(p):
if p % k == 0:
p //= k
k += 1
print(long_to_bytes(p).decode())
```
## luckyguess - 150 solves
> i hope you're feeling lucky today
> ==*nc be.ax 31800*==
Atachment:
1. luckyguess.py
```python=
#!/usr/local/bin/python
from random import getrandbits
p = 2**521 - 1
a = getrandbits(521)
b = getrandbits(521)
print("a =", a)
print("b =", b)
try:
x = int(input("enter your starting point: "))
y = int(input("alright, what's your guess? "))
except:
print("?")
exit(-1)
r = getrandbits(20)
for _ in range(r):
x = (x * a + b) % p
if x == y:
print("wow, you are truly psychic! here, have a flag:", open("flag.txt").read())
else:
print("sorry, you are not a true psychic... better luck next time")
```
Bài này giống với bài trước ở chổ dùng hàm `f()`. Vì bài trước không cần đụng quá sâu vào phân tích hàm này nhưng bài này và bài sau sẽ cần đi sâu hơn vào hàm `f()` hay còn gọi là **Linear Congruential Generator**(không biết dịch :crying_cat_face: ), gọi là LCG luôn nha.
Trong LCG thì ta sẽ có 3 tham số là số nhân $a$, số tăng $b$ và số chia $p$. Công thức để sinh 1 số tiếp theo:
$$
X_{n} = aX_{n-1} + b\pmod{p}
$$
Hay công thức tổng quát sinh 1 số sau $n$ lần sinh:
\begin{align}
X_{n} &= a^nX + b\left(a^{n-1} + a^{n-2} + \dots + 1\right)\pmod{p} \\
&= a^nX + b\frac{a^n-1}{a-1}\pmod{p} \\
\end{align}
Phân tích bài thì mình thấy là muốn là lấy được Flag, ta cần nhập vào 2 số $x$ và $y$ sao cho $y$ là kết quả của $x$ sau 1 số ngẫu nhiên $n$ lần sinh từ LCG (với $a, b, p$ đã cho trước) thì sẽ hiện Flag. $n$ được tạo ngẫu nhiên sau khi nhập $x$ và $y$ do đó chứng tỏ luôn tồn tại số mà số lần sinh bao nhiêu đi nữa thì vẫn chỉ có một đáp án được sinh ra duy nhất. Chứng minh:
$$
\begin{align}
X_n &= a^nX + b\frac{a^n-1}{a-1}\pmod{p} \\
&= a^nX + \frac{a^nb}{a-1} - \frac{b}{a-1} \\
&= a^n\left(X + \frac{b}{a-1}\right)- \frac{b}{a-1} \pmod{p}
\end{align}
\\
\implies\text{ Với }X = \frac{-b}{a-1}\pmod{p}\text{ thì } X_n = \frac{-b}{a-1}\pmod{p}\ \forall n \in \mathbb{Z}
$$
Như vậy ta chỉ cần gửi 2 số $x = y = \frac{-b}{a-1}$ là thoả đề bài bất chấp $n$
Script bằng python:
```python=
from telnetlib import Telnet
from gmpy2 import powmod, mpz, invert
HOST='be.ax'
io=Telnet(HOST, 31800)
def readline(io):
return io.read_until(b'\n').strip()
def writeline(io,a):
io.write(a+b'\n')
def writelineafter(io,a,b):
io.read_until(a)
io.write(b+b'\n')
p = 2**521 - 1
a = mpz(readline(io).decode().split(' = ')[-1])
b = mpz(readline(io).decode().split(' = ')[-1])
print(f'{a = }')
print(f'{b = }')
d=b*invert(a-1, p) % p
def mult(s, n):
return (powmod(a, n, p)*(s+d) - d) % p
x=-d % p
print(f'{x = }')
writelineafter(io, b'enter your starting point: ', str(x).encode())
writelineafter(io, b"alright, what's your guess? ", str(x).encode())
io.interact()
```
```
a = mpz(5815852120647221830743456624914356390039371105830699270464029590874475456657117550074855812011884480607802918282419847545467433600776148519838488752631362952)
b = mpz(952181975324355351570551489379321109065547547255327479943224484487947395583129880350817984292577909751440515965493779280220863275205203433947008756513743810)
x = mpz(4166248842373150773632623416381435197263539095549119825550632267999141448474641407273907289361842204021767551168821838666596572981635445121985783739875667990)
wow, you are truly psychic! here, have a flag: corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}
```
## exchange - 94 solves
> you could make an exchange out of this
Attachments:
1. exchange.py
```python=
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from secrets import randbelow
p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
a = randbelow(p)
b = randbelow(p)
s = randbelow(p)
print("p =", p)
print("a =", a)
print("b =", b)
print("s =", s)
a_priv = randbelow(p)
b_priv = randbelow(p)
def f(s):
return (a * s + b) % p
def mult(s, n):
for _ in range(n):
s = f(s)
return s
A = mult(s, a_priv)
B = mult(s, b_priv)
print("A =", A)
print("B =", B)
shared = mult(A, b_priv)
assert mult(B, a_priv) == shared
flag = open("flag.txt", "rb").read()
key = sha256(long_to_bytes(shared)).digest()[:16]
iv = long_to_bytes(randint(0, 2**128))
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
print(iv.hex() + cipher.encrypt(pad(flag, 16)).hex())
```
2. output.txt
```
p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
a = 118090659823726532118457015460393501353551257181901234830868805299366725758012165845638977878322282762929021570278435511082796994178870962500440332899721398426189888618654464380851733007647761349698218193871563040337609238025971961729401986114391957513108804134147523112841191971447906617102015540889276702905
b = 57950149871006152434673020146375196555892205626959676251724410016184935825712508121123309360222777559827093965468965268147720027647842492655071706063669328135127202250040935414836416360350924218462798003878266563205893267635176851677889275076622582116735064397099811275094311855310291134721254402338711815917
s = 35701581351111604654913348867007078339402691770410368133625030427202791057766853103510974089592411344065769957370802617378495161837442670157827768677411871042401500071366317439681461271483880858007469502453361706001973441902698612564888892738986839322028935932565866492285930239231621460094395437739108335763
A = 27055699502555282613679205402426727304359886337822675232856463708560598772666004663660052528328692282077165590259495090388216629240053397041429587052611133163886938471164829537589711598253115270161090086180001501227164925199272064309777701514693535680247097233110602308486009083412543129797852747444605837628
B = 132178320037112737009726468367471898242195923568158234871773607005424001152694338993978703689030147215843125095282272730052868843423659165019475476788785426513627877574198334376818205173785102362137159225281640301442638067549414775820844039938433118586793458501467811405967773962568614238426424346683176754273
e0364f9f55fc27fc46f3ab1dc9db48fa482eae28750eaba12f4f76091b099b01fdb64212f66caa6f366934c3b9929bad37997b3f9d071ce3c74d3e36acb26d6efc9caa2508ed023828583a236400d64e
```
Câu này là 1 dạng trao đổi khoá Diffie-Hellman nhưng dựa trên LCG: $s_{n} = as_{n-1} + b\pmod{p}$. Ta được cho biết $a, b, p, s, A, B$ với $A$ và $B$ lần lượt là khoá công khai của Alice và Bob, $A=s_{n_a}$ và $B=s_{n_B}$. Yêu cầu là cần tìm $n_A$ hoặc $n_B$ từ đó tính $s_{n_A+n_B}$ rồi băm ra lấy được `key` và giải mã `Flag`.
Đây là một bài toán ==discrete log== điển hình nhưng trên LCG. Áp dụng công thức đã chứng minh ở câu trên, ta có:
\begin{align}
s_{n_A} &= a^{n_A}(s+\frac{b}{a-1}) - \frac{b}{a-1} \pmod{p} \\
s_{n_A} + \frac{b}{a-1} &= a^{n_A}(s+\frac{b}{a-1}) \pmod{p} \\
\frac{s_{n_A} + \frac{b}{a-1}}{s+\frac{b}{a-1}} &= a^{n_A} \pmod{p} \\
\end{align}
Tất cả các số ta đều có trừ $n_A$, do đó ta đã thành công đưa về bài toán ==discrete log== trong $(\mathbb{Z}/\mathcal{p}\mathbb{Z})^{\mathbb{x}}$. Cộng với việc $p-1$ **smooth**, ta có thể sử dụng thuật toán **Pollig-Hellman** để tìm $n_A$ dễ dàng từ $a^{n_A}$.
Sau đó tìm `shared` rồi băm ra thành khoá giải mã.
Thuật toán Pollig-Hellman: [wiki](https://en.m.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm)
Hàm `discrele_log` trong sagemath sử dụng ==Pollig-Hellman== kết hợp ==Baby-step/Giant-step== để giải các bài toán logarithm rời rạc. Vì `muliplicative_order` của $a$ trên $p$ bằng $p-1$ là 1 số smooth(có các ước nguyên tố nhỏ), do đó ==Pollig-Hellman== đã giảm độ phức tạp tìm kiếm xuống ngang với các số nguyên tố bé đó giúp ==Baby-step/Giant-step== tìm số mũ nhỏ 1 cách nhanh chóng. Sau khi tìm được từng số mũ ứng với các số nguyên tố nhỏ ($(\mathbb{Z}/\mathcal{p_i}\mathbb{Z})^{\mathbb{x}}$ với $p_i$ là các ước nguyên tố của $p$), sử dụng [Định lý số dư Trung Hoa](https://en.m.wikipedia.org/wiki/Chinese_remainder_theorem) để tìm số mũ lớn cuối cùng trên $(\mathbb{Z}/\mathcal{p}\mathbb{Z})^{\mathbb{x}}$. Script bằng sagemath:
```python=
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha256
from sage.all import *
p = 142031099029600410074857132245225995042133907174773113428619183542435280521982827908693709967174895346639746117298434598064909317599742674575275028013832939859778024440938714958561951083471842387497181706195805000375824824688304388119038321175358608957437054475286727321806430701729130544065757189542110211847
a = 118090659823726532118457015460393501353551257181901234830868805299366725758012165845638977878322282762929021570278435511082796994178870962500440332899721398426189888618654464380851733007647761349698218193871563040337609238025971961729401986114391957513108804134147523112841191971447906617102015540889276702905
b = 57950149871006152434673020146375196555892205626959676251724410016184935825712508121123309360222777559827093965468965268147720027647842492655071706063669328135127202250040935414836416360350924218462798003878266563205893267635176851677889275076622582116735064397099811275094311855310291134721254402338711815917
s = 35701581351111604654913348867007078339402691770410368133625030427202791057766853103510974089592411344065769957370802617378495161837442670157827768677411871042401500071366317439681461271483880858007469502453361706001973441902698612564888892738986839322028935932565866492285930239231621460094395437739108335763
A = 27055699502555282613679205402426727304359886337822675232856463708560598772666004663660052528328692282077165590259495090388216629240053397041429587052611133163886938471164829537589711598253115270161090086180001501227164925199272064309777701514693535680247097233110602308486009083412543129797852747444605837628
B = 132178320037112737009726468367471898242195923568158234871773607005424001152694338993978703689030147215843125095282272730052868843423659165019475476788785426513627877574198334376818205173785102362137159225281640301442638067549414775820844039938433118586793458501467811405967773962568614238426424346683176754273
enc='e0364f9f55fc27fc46f3ab1dc9db48fa482eae28750eaba12f4f76091b099b01fdb64212f66caa6f366934c3b9929bad37997b3f9d071ce3c74d3e36acb26d6efc9caa2508ed023828583a236400d64e'
def f(s):
return (a * s + b) % p
F=GF(p)
a=F(a)
b=F(b)
s=F(s)
A=F(A)
B=F(B)
d=b/(a-1)
def mult(s, n):
return (a^n)*(s+d) - d
def logp(h, g):
x=h
x += d
x /= (g+d)
return discrete_log(x, a)
a_priv=logp(A, s)
print(a_priv)
shared=mult(B, a_priv)
key = sha256(long_to_bytes(shared)).digest()[:16]
iv = bytes.fromhex(enc[:32])
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
print(unpad(cipher.decrypt(bytes.fromhex(enc[32:])), 16).decode())
```
```
63497966771228335993935218724355716676359926182967975463093060105894867914802051403524263838451533117998140812842659902100945139428076742018151358770711075499718955791059569760306592803008376586431708302909649602374612770031446609941268056564386982932718212036534269872682126736591975854896102855270700008372
corctf{th1s_lcg_3xch4ng3_1s_4_l1ttl3_1ns3cur3_f0r_n0w}
```
## hidE - 88 solves
> This RSA encryption service is so secure we're not even going to tell you how we encrypted it
> ==nc be.ax 31124==
Attachments:
1. main.py
```python=
#!/usr/local/bin/python
import random
import time
import math
import binascii
from Crypto.Util.number import *
p, q = getPrime(512), getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
flag = open('./flag.txt').read().encode()
random.seed(int(time.time()))
def encrypt(msg):
e = random.randint(1, n)
while math.gcd(e, phi) != 1:
e = random.randint(1, n)
pt = bytes_to_long(msg)
ct = pow(pt, e, n)
return binascii.hexlify(long_to_bytes(ct)).decode()
def main():
print('Secure Encryption Service')
print('Your modulus is:', n)
while True:
print('Options')
print('-------')
print('(1) Encrypt flag')
print('(2) Encrypt message')
print('(3) Quit')
x = input('Choose an option: ')
if x not in '123':
print('Unrecognized option.')
exit()
elif x == '1':
print('Here is your encrypted flag:', encrypt(flag))
elif x == '2':
msg = input('Enter your message in hex: ')
print('Here is your encrypted message:', encrypt(binascii.unhexlify(msg)))
elif x == '3':
print('Bye')
exit()
if __name__ == '__main__':
main()
```
Câu này là một lỗi cơ bản của RSA, dùng chung số modulus $n$ cho nhiều lần mã hoá nhưng mỗi lần mã hoá lain dùng 1 $e$ khác nhau.
Giải thuật Euclid mở rộng chỉ ra rằng nếu $d = \mathit{GCD}(a, b)$ thì luôn tồn tại 2 giá trị nguyên $x, y$ sao cho:
$$ax + by = d$$
Từ công thức trên, nếu ta lấy được từ server 2 **Flag** đã bị mã hoá bằng 2 $e$ khác nhau và $\mathit{GCD}(e_1, e_2)=1$. Lúc này sử dụng giải thuật Euclid mở rộng tìm ra 2 số $x, y$ thoả:
$$e_1x+e_2y=1$$
Cụ thể:
\begin{align}
c_1^xc_2^y &\equiv (m^{e_1})^x(m^{e_2})^y \pmod{n} \\
&\equiv m^{e_1x+e_2y} \pmod{n} \\
&\equiv m \pmod{n}
\end{align}
Mặc dù server không cho ta thấy $e$ nhưng lại dùng `seed` là `time.time()` (thời gian hiện tại), nên ta hoàn toàn biết trước được server đã `random` ra số nào. Server chỉ chọn những $e$ có $\mathit{gcd}(e, phi)=1$ mà ta lại không biết $phi$ nên mình sẽ tạo 1 lần 20 số $e$ (lấy số lẻ thôi vì $phi$ luôn chẵn) và lấy ra tất cả tổ hợp 2 số trong 20 số $e$ đó để dùng giải thuật euclid tìm **Flag** thử.
Lặp đi lặp lại đến khi có **Flag** thì thôi. Script bằng python:
```python=
import random
import time
from telnetlib import Telnet
from gmpy2 import mpz, powmod
from Crypto.Util.number import long_to_bytes
from itertools import combinations
def readline():
return io.read_until(b'\n').strip()
def writeline(a):
io.write(a+b'\n')
def writelineafter(a,b):
io.read_until(a)
io.write(b+b'\n')
def sendoption(a):
writelineafter(b'Choose an option: ',str(a).encode())
def getflag():
sendoption(1)
res=readline().decode()
return res.split(': ')[-1]
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
while True:
HOST='be.ax'
io=Telnet(HOST, 31124)
t=int(time.time())
random.seed(t)
print('*'*20, 'time =', t, '*'*20)
readline()
n=mpz(readline().decode().split(': ')[-1])
print('n =', n)
enc1=mpz(getflag(), 16)
print('enc_flag =', enc1)
enc2=mpz(getflag(), 16)
print('enc_flag =', enc2)
es=[]
for i in range(20):
e = random.randint(1, n)
while e%2 == 0:
e = random.randint(1, n)
es.append(e)
for ee in combinations(es, 2):
e1, e2 = ee
g, x, y = egcd(e1, e2)
if g>1:
continue
m1 = powmod(enc1, x, n)
m2 = powmod(enc2, y, n)
m = (m1 * m2) % n
flag=long_to_bytes(m)
if b'corctf' in flag:
print('Flag:', flag.decode())
exit()
```
Một phát được luôn này =))
```
******************** time = 1660533167 ********************
n = 71801129361761221506154609745995886583695621533063171597520933770446332171041575649152508516201009762312913762704234742518226822856803457217363549518685648184230977945707284788062854185363735316578544380517526584155929138979880549293956304995032341892137257316530769335248274546713892934689862219179090342387
enc_flag = 3377628949218061168453738285772637160938243516024918800012735905348622180723225709358555530381858456968564182689080064903503516500262077496365892425220971263663148355670499492751291535504662382295408850204238012866940543243483683686475874684631219973597987694056995625713543222717401520546305306251658018238
enc_flag = 47552380856364571942923570580889278085982214976056322300507315594593302628985583058925934079483474137761213474543871901386636641283495080306878956064909935647160002991159435705450734756996210806608388936970814971237577948358453047403062454783190327513173358068325218195860137972390205404877823865433599382022
Flag: corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}
```
## generous - 49 solves
Attachments:
1. generous.py
```python=
#!/usr/local/bin/python
from Crypto.Util.number import getPrime, inverse, bytes_to_long
from random import randrange
with open("flag.txt", "rb") as f:
flag = f.read().strip()
def gen_keypair():
p, q = getPrime(512), getPrime(512)
n = (p**2) * q
while True:
g = randrange(2, n)
if pow(g, p-1, p**2) != 1:
break
h = pow(g, n, n)
return (n, g, h), (g, p, q)
def encrypt(pubkey, m):
n, g, h = pubkey
r = randrange(1, n)
c = pow(g, m, n) * pow(h, r, n) % n
return c
def decrypt(privkey, c):
g, p, q = privkey
a = (pow(c, p-1, p**2) - 1) // p
b = (pow(g, p-1, p**2) - 1) // p
m = a * inverse(b, p) % p
return m
def oracle(privkey, c):
m = decrypt(privkey, c)
return m % 2
pub, priv = gen_keypair()
n, g, h = pub
print(f"Public Key:\n{n = }\n{g = }\n{h = }")
print(f"Encrypted Flag: {encrypt(pub, bytes_to_long(flag))}")
while True:
inp = int(input("Enter ciphertext> "))
print(f"Oracle result: {oracle(priv, inp)}")
```
Bài này cho phép giải mã `input` chúng ta gửi lên nhưng chỉ leak 1 bit cuối sau khi giải mã.
Script bằng python:
```python=
from telnetlib import Telnet
from gmpy2 import powmod, mpz, invert
from random import randrange
from Crypto.Util.number import long_to_bytes
def readline():
return io.read_until(b'\n').strip()
def writeline(a):
io.write(a+b'\n')
def writelineafter(a,b):
io.read_until(a)
io.write(b+b'\n')
def encrypt(pubkey, m):
n, g, h = pubkey
r = randrange(1, n)
c = powmod(g, m, n) * powmod(h, r, n) % n
return c
def oracle(enc):
writelineafter(b"Enter ciphertext> ", str(enc).encode())
res=readline().decode()
print(res)
return res[-1]
HOST='be.ax'
io=Telnet(HOST, 31244)
print(readline().decode())
n=mpz(readline().decode().split(' = ')[-1])
g=mpz(readline().decode().split(' = ')[-1])
h=mpz(readline().decode().split(' = ')[-1])
print(f'{n = }\n{g = }\n{h = }')
enc=mpz(readline().decode().split(': ')[-1])
print(f'{enc = }')
flag=''
while True:
bit = oracle(enc)
flag=bit + flag
if bit == '1':
enc=(enc*encrypt((n,g,h), -1 % n))%n
enc = pow(enc, invert(2, n), n)
msg=long_to_bytes(int(flag, 2))
if b'corctf' in msg:
print(msg.decode())
break
```
```
Public Key:
n = mpz(646216861115612033449639030716237139242303555060604399178522250048092454138457122953862614101074260300396163373370955458865545073300064652603555099441639621756297195641894434730473072428980293466066451967172976918994480827032576657933404175976794466635850361956060543485278258089021033433810981861958861935967832240177397324429437564496950671547952321478343929164684394853121179892434275315451742695675655668241008818346609867613694593006602324068982847663683891)
g = mpz(307246213620426918687914319918159880944972247416473590525876006288125706142679224216321356495825787357048475830956967557360393024510462960460124326154878966008584802605557741951939387452642456572262466259739191319302236302042812359123996959272362778228151815421795770442777505193052762458624237488247511342605983657206962251805731014508144193052112122014889173854833202658547932585771378422294110407648863329904642400946601751115360819653065955862283687814994257)
h = mpz(609970360087891514690232313269440347100333736247341804674307577861167452920911277278031444704051063146570044200879868563131802967842122116419285941302445712354401728232111614438434354357990946515005799437535851345930919490597134688600466558843985891854033492932170044464994996924768734055608936635835441090764590896358056975689462953352979048143948974489967610366449653874440181775660391125045198990167774816614329350765655171997528896171081201452182633035438535)
enc = mpz(570122027895082305574434470604509118820984251810326905638073001986284293858498056381970752863841200558716606640464054346661840054472669237409699110115636900381998413505100376774553232009134178194752521909102074882921998798261232075728735456107654387893651405806410688142641410405826983811613037468562218154538982918764808599253374298386323910140782182337740318510275833141281915070927876183029255523755974814340874461902981432033108929922442516077661754210549548)
Oracle result: 1
Oracle result: 0
Oracle result: 1
Oracle result: 1
Oracle result: 1
Oracle result: 1
...
Oracle result: 1
Oracle result: 0
Oracle result: 0
Oracle result: 0
Oracle result: 1
Oracle result: 1
corctf{see?1_bit_is_very_generous_of_me}
```
## corrupted-curves - 20 solves
> all these fake curves, but where's the real one?
> ==nc be.ax 31345==
Attachments:
1. corruptedcurves.py
```python=
#!/usr/local/bin/python
from secrets import randbits
from Crypto.Util.number import getPrime
def square_root(a, p):
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return 0
elif p % 4 == 3:
return pow(a, (p + 1) // 4, p)
s = p - 1
e = 0
while s % 2 == 0:
s //= 2
e += 1
n = 2
while legendre_symbol(n, p) != -1:
n += 1
x = pow(a, (s + 1) // 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e
while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = pow(t, 2, p)
if m == 0:
return x
gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
def legendre_symbol(a, p):
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
class EllipticCurve:
def __init__(self, p, a, b):
self.a = a
self.b = b
self.p = p
if not self.check_curve():
raise Exception("Not an elliptic curve!")
def check_curve(self):
discrim = -16 * (4*pow(self.a, 3) + 27*pow(self.b, 2))
if discrim % self.p:
return 1
return 0
def lift_x(self, px):
y2 = (pow(px, 3) + self.a*px + self.b) % self.p
py = square_root(y2, self.p)
if py == 0:
raise Exception("No point on elliptic curve.")
return py
with open("flag.txt", "rb") as f:
flag = f.read()
flag = int.from_bytes(flag, 'big')
print("Generating parameters...")
while True:
p = getPrime(512)
a, b = randbits(384), randbits(384)
try:
E = EllipticCurve(p, a, b)
fy = E.lift_x(flag)
print(f"p = {p}")
print(f"flag y = {fy}")
break
except:
continue
checked = set()
count = 0
while count < 64:
x = int(input("x = ")) % p
if int(x) in checked or x < 2**384 or abs(x - p) < 2**384:
print(">:(")
continue
e = randbits(64)
print(f"e = {e}")
try:
E = EllipticCurve(p, a^e, b^e)
py = E.lift_x(x)
checked.add(int(x))
print(f"y = {py}")
count += 1
except:
print(":(")
print("bye!")
```
Script bằng sagemath:
```python=
from telnetlib import Telnet
from gmpy2 import mpz
from secrets import randbits
need=70
icon1=b">:("
icon2=b":("
def readline():
return io.read_until(b'\n').strip()
def writeline(a):
io.write(a+b'\n')
def writelineafter(a,b):
io.read_until(a)
io.write(b+b'\n')
def solve(res, e):
l1, l2 = res
x=l1[-1]
t1=(l1[0] - pow(l1[-1], 3))%p
t2=(l2[0] - pow(l2[-1], 3))%p
_a=(t2 - t1)%p
if _a.bit_length() > 450: return None
_a = _a % x
_a = (_a >> need) << need
_b = ((t1 - _a*x) % p) % x
_b = (_b >> need) << need
print(f"high_a = {_a}")
print(f"high_b = {_b}")
t3 = (t1 - _a*x - _b) % p
a_=t3//x
b_=t3%x
print(f"low_a = {a_^^e}")
print(f"low_b = {b_^^e}")
a=(_a + a_)^^e
b=(_b + b_)^^e
return (a, b)
HOST='be.ax'
io=Telnet(HOST, 31345)
readline().decode()
p=mpz(readline().decode().split(' = ')[-1])
flagy=mpz(readline().decode().split(' = ')[-1])
print(f"p = {p}")
print(f"flagy = {flagy}")
count=0
while count < 64:
_x=randbits(385)
xs=[_x, _x+1]
res=[]
es=[]
for i in range(2):
x=xs[i]
writelineafter(b"x = ", str(x).encode())
line=readline()
if line == icon1:
break
es.append(mpz(line.decode().split(' = ')[-1]))
line=readline()
if line == icon2:
break
y=mpz(line.decode().split(' = ')[-1])
res.append([(y**2)%p, x])
count += 1
if len(res) != 2: continue
ans=solve(res, es[0])
if not ans:
continue
a, b= ans
if res[0][0] == (pow(_x, 3) + (a^^es[0])*_x +(b^^es[0]))%p:
print(f"a = {a}")
print(f"b = {b}")
break
else:
print('Not Found!')
y2=GF(p)(flagy^2)
PF.<x>=PolynomialRing(GF(p))
f=x^3 + a*x + b - y2
x=int(f.roots()[0][0])
print('x =', x)
print('Flag:', x.to_bytes((x.bit_length()+7)//8, 'big').decode())
```
> `^^` là phép xOR trong sagemath vì `^` đã được định nghĩa là lũy thừa
```
p = 13387807327366432118019435649047642368794794612950022741671500540028456588862522492073493363345871340671655824429479684632787052830134235256218924489281787
flagy = 111015323710222217749171570085093618604205755655636018359214210282667133020770881013460387419077373610240473179231724512266173323071887945194208209741945
high_a = 37561463133651386926453198044340289225989571282932296022150868643063209614243862186848561552288136193975296160956416
high_b = 2297366883974705026856556566267462468158092716966249445677867944340874163700063885162721333224672415808786813419520
low_a = 156858732709096936120
low_b = 455319443649105001759
a = 37561463133651386926453198044340289225989571282932296022150868643063209614243862186848561552288293052708005257892536
b = 2297366883974705026856556566267462468158092716966249445677867944340874163700063885162721333225127735252435918421279
x = 5207851285831991063142066581625787706314199045100321092773175149680378836678124766164328598941631048157824833933555981490578600657038994486797794996267389
Flag: corctf{i_h0pe_you_3njoyed_p1ecing_t0geth3r_th4t_curv3_puzz1e_:)}
```
## threetreasures - 19 solves
> Let's find the treasures of three amongst the order of three.
Attachments:
1. source.py
```python=
from sage.all import *
from Crypto.Util.number import bytes_to_long, getPrime
from random import getrandbits
from secret import flag, p, x, y
def random_pad(n, length):
return (n << (length - n.bit_length())) + getrandbits(length - n.bit_length())
flag = bytes_to_long(flag)
fbits = flag.bit_length()
piece_bits = fbits // 3
a, b, c = flag >> (2 * piece_bits), (flag >> piece_bits) % 2**piece_bits, flag % 2**piece_bits
print(f'flag bits: {fbits}')
assert p.bit_length() == 512
q = getPrime(512)
n = p * q
ct = pow(random_pad(c, 512), 65537, n)
E = EllipticCurve(GF(p), [a, b])
G = E(x, y)
assert G * 3 == E(0, 1, 0)
print(f"n = {n}")
print(f"ct = {ct}")
print(f"G = {G}")
```
2. output.txt
```
flag bits: 375
n = 97915144495462666300795364589570761584322186881492143950078938328867290046424857019504657598883431857075772605985768551863478086544857915637724181292135280539943713583281151707224031808445390796342632369109562433275679473233398168787639940620683354458292117457239552762694657810883738834935391913698852811737
ct = 20363336204536918055183609604474634074539942561101208682977506918349108499764147141944713060658857301108876346227077713201766486360148051069618774935469969057808945271860025712869868421279488925632657486125211168314387620225601572070169746014988350688548088791906161773656057212229972967244998930356157725393
G = (3115938227771961657567351113281194074601897467086373590156577019504528350118731801249444974253028485083440228959842232653488953448859690520619223338133881 : 2665631524518629436093690344927156713668794128141943350227439039472817541262750706395352700109556004195261826476428128993836186741129487842876154876730189 : 1)
```
Câu này lúc giải đang diễn ra thì mình bị ngáo nên vừa hết giải mới làm ra :)). Lý do là vì mình quên trong phần đầu của flag có chữ `corctf{`, do đó ta đã biết được $55$ bits của $a$ => chỉ cần tìm $70$ bits còn lại của $a$ là được ($a = b = c = 375\div{3} = 125$). Mà mình lại tìm thẳng 125 bits (có vẻ lớn hơn điều kiện của phương pháp **Coppersmith** tìm `small_root`) :crying_cat_face:
Script bằng sagemath:
```python=
from sage.all import *
n = 97915144495462666300795364589570761584322186881492143950078938328867290046424857019504657598883431857075772605985768551863478086544857915637724181292135280539943713583281151707224031808445390796342632369109562433275679473233398168787639940620683354458292117457239552762694657810883738834935391913698852811737
ct = 20363336204536918055183609604474634074539942561101208682977506918349108499764147141944713060658857301108876346227077713201766486360148051069618774935469969057808945271860025712869868421279488925632657486125211168314387620225601572070169746014988350688548088791906161773656057212229972967244998930356157725393
G = (3115938227771961657567351113281194074601897467086373590156577019504528350118731801249444974253028485083440228959842232653488953448859690520619223338133881, 2665631524518629436093690344927156713668794128141943350227439039472817541262750706395352700109556004195261826476428128993836186741129487842876154876730189)
Z=Zmod(n)
xg=Z(G[0])
yg=Z(G[1])
P.<x> = PolynomialRing(Z)
high=int.from_bytes(b'corctf{', 'big') << 70
f = (3*xg^2 + high + x)^2 - 12*xg*yg^2
a=f.small_roots(X=2^70, beta=0.5)[0]
p=gcd(ZZ(f(a)), n)
assert is_prime(p)
a+=high
b = (G[1]^2 - G[0]^3 - a*G[0]) % p
q = n//p
d = inverse_mod(0x10001, (p-1)*(q-1))
m = int(Z(ct)^d)
c = m >> (512 - 125)
flag = (int(a) << (2*125)) + (int(b) << 125) + int(c)
print(flag.to_bytes((flag.bit_length()+7)//8,'big').decode())
```
```
corctf{you_have_conquered_the_order_of_three!!}
```
Hết rồi đó :wave:.Cảm ơn mọi người đã đọc blog về mấy bài CTF về ~~Toán~~ Cryptography nhạt nhẽo của mình :rolling_on_the_floor_laughing:
Sign in with Wallet
Connect another wallet